mirror of
https://github.com/hanzoai/ml.git
synced 2026-11-20 23:08:29 +00:00
A crate whose whole interface is two verbs. `Config` holds hyperparameters and has no `predict`. `Fit` maps `Config -> Data -> Model`. `Model` is immutable, has private fields and no public constructor, so an unfitted model is not a state to be checked for — it is a value that cannot be spoken, and `check_is_fitted` has no job to do. `Predict::Answer` is `f64` for a regressor and `Class` for a classifier: the two do not unify, so a regressor and a classifier are different types rather than one type with a mode flag. There is no `get_params`, no `BaseEstimator`, no clone protocol and no `Pipeline` — those exist in Python because a config and a fitted model are the same object there. Every fitted model is named by `Address`, a content address over its shape, its hyperparameters and its learned parameters, hashing floats as IEEE-754 bits and length-prefixing every sequence so the encoding is injective. Same construction and same reasoning as the risk plane's published model values, so a fit can be stored, cited by a decision, compared against a challenger and rolled back to without a registry. Three estimators: least squares by Householder QR on centred data (QR not the normal equations, which square the condition number; centring not a ones column, so the intercept never enters the factorisation), binary logistic regression by Newton steps on a strictly convex penalised objective, and gradient boosted CART regression trees. A TREE READS FEATURES AT IEEE-754 BINARY32, and that is the algorithm rather than a detail. scikit-learn casts X to float32 before its splitter sees it, XGBoost and LightGBM do the same, and ai.onnx.ml's TreeEnsembleRegressor stores nodes_values as floats. A tree never does arithmetic on a feature value — it only orders values and places thresholds between them — so precision decides only which side of a boundary a sample falls on. Placing the threshold at single(a)/2 + single(b)/2 instead of a/2 + b/2 moves it by 2e-8, which is enough to send a sample down the other branch. Measured over the 40 depth-1 trees of the stumps fixture, whose roots all see the full sample set: the single-precision midpoint reproduces scikit-learn's threshold bit-for-bit 40 times out of 40, the double-precision midpoint 0 times out of 40. Correctness is asserted against scikit-learn itself. Fixtures generated by 1.9.0 are committed and read as data, so `cargo test` needs no Python and the oracle's version is a recorded fact. 195 boosted trees / 1,977 split nodes agree node for node — split feature, threshold and both children all exact — with leaf values to 1.3e-15 and predictions to 8.9e-16 against a 1e-10 bound; least squares agrees to 1.1e-15 against 1e-10 and logistic to 1.2e-8 against 1e-7, with hard labels exact. Each tolerance is derived from the mathematics and every assertion prints the deviation it observed, so a regression that stays inside a bound is still visible. The generator refuses to record an oracle that is not a function of its data: at scikit-learn's default min_samples_leaf a tree's structure varies with random_state (20 structures over 40 seeds, prediction spread 3.9), so every case pins the tie away and proves determinism over 12 seeds before writing a number. This crate breaks split ties by lowest feature index instead, because a content address over a model an RNG helped choose would name one draw rather than one fit. The exhaustive split search is not lowered to hanzo-kernel, and the obstacle is specific: a launch geometry must be stated before the launch, and across all 69 launch sites in that crate Grid::Static is the only variant used, every geometry computed on the host from a count it already knows. A CART node's sample count is not such a number. The histogram formulation dissolves this — bin count is a hyperparameter, so the per-level geometry is host-knowable — but it quantises thresholds and so cannot hold the node-for-node bar. It is named, not built. scikit-learn is a test oracle only. No code or docstring is taken from it, and NOTICE records that, along with the obligation to add BSD-3 attribution if that ever changes. The crate also carries, unchanged and unclaimed, the anomaly-detection and preprocessing modules written concurrently on another track (isolation, neighbour, transform, scale, impute, encode, metric, moment, split, twister, plus benches and the perf oracle). They share lib.rs and tests/sklearn.rs with the estimator seam, so the crate cannot be committed in halves. Their `Transform` and `Outlier` traits extend this seam without changing `Fit` or `Predict`. One of their fixture tests, `the_imbalanced_metrics_match_scikit_learn`, is red on a fixture key that measure.json does not yet carry — which is why this is a branch and not main.
734 lines
28 KiB
Rust
734 lines
28 KiB
Rust
//! Regression trees: the base learner, and the irregular half of this crate.
|
|
//!
|
|
//! A CART regression tree, greedy, exhaustive over every feature and every distinct
|
|
//! value. Its split rule matches scikit-learn's `squared_error` splitter term for term
|
|
//! — including the two conventions that look like details and are not: the near-equal
|
|
//! grouping tolerance, and the exact arithmetic of the threshold midpoint.
|
|
//!
|
|
//! # A leaf has no threshold, and that is in the type
|
|
//!
|
|
//! scikit-learn stores one flat array per field and writes `-2` into `feature` and
|
|
//! `threshold` at leaves. That is an illegal state made representable: `-2` is a
|
|
//! perfectly good feature index in a language without sum types, and every consumer
|
|
//! must know the sentinel. [`Node`] is an enum, so a leaf HAS no threshold to read and
|
|
//! a split HAS no value to mistake for a prediction.
|
|
//!
|
|
//! # THE FEATURE SPACE IS SINGLE PRECISION, AND THAT IS THE ALGORITHM
|
|
//!
|
|
//! A tree never does arithmetic on a feature value. It only ORDERS values and places
|
|
//! thresholds BETWEEN them, so the only thing a feature's precision decides is which
|
|
//! side of a boundary a sample falls on. Every serious tree implementation therefore
|
|
//! reads features at binary32 — scikit-learn casts `X` to `float32` before its splitter
|
|
//! sees it, XGBoost and LightGBM do the same, and `ai.onnx.ml`'s `TreeEnsembleRegressor`
|
|
//! stores `nodes_values` as `floats`, which IS binary32. Single precision is the
|
|
//! interchange format of this model family, not a scikit-learn quirk.
|
|
//!
|
|
//! So [`single`] is applied wherever a feature value is read, and the consequence is
|
|
//! measurable. From this crate's own fixture, the two values straddling the root split of
|
|
//! the first boosted tree:
|
|
//!
|
|
//! ```text
|
|
//! a = -1.5903684017801702 b = -1.5771856983463417
|
|
//! a/2 + b/2 = -1.583777050063256 <- double precision
|
|
//! single(a)/2 + single(b)/2 = -1.5837770700454712 <- scikit-learn records THIS
|
|
//! ```
|
|
//!
|
|
//! Those differ by 2e-8 — nowhere near a rounding difference, and enough to send a
|
|
//! sample down the other branch. Measured over the 40 depth-1 trees of the `stumps`
|
|
//! fixture, whose roots all see the full sample set: the single-precision midpoint
|
|
//! reproduces scikit-learn's threshold bit-for-bit 40 times out of 40, and the
|
|
//! double-precision midpoint 0 times out of 40. That is why `tests/sklearn.rs` can
|
|
//! assert thresholds with `==` and not a tolerance.
|
|
//!
|
|
//! The targets stay `f64`. Only the feature side is single, because only the feature
|
|
//! side is ordered rather than summed — leaf values are means of `y` and want every bit.
|
|
//!
|
|
//! # WHERE THIS DIVERGES FROM SCIKIT-LEARN, DELIBERATELY
|
|
//!
|
|
//! Ties are broken by the LOWEST FEATURE INDEX, always. scikit-learn breaks them with a
|
|
//! `random_state`-seeded partial Fisher-Yates shuffle over the features, which means a
|
|
//! scikit-learn tree IS NOT A FUNCTION OF ITS TRAINING DATA at the default
|
|
//! `min_samples_leaf = 1`:
|
|
//!
|
|
//! ```text
|
|
//! DecisionTreeRegressor(max_depth=3) 20 structures over 40 seeds,
|
|
//! prediction spread 3.9e+00
|
|
//! GradientBoostingRegressor(max_depth=5) 12 structures over 12 seeds,
|
|
//! prediction spread 1.1e+00
|
|
//! ```
|
|
//!
|
|
//! measured on this crate's own fixture data. That spread is O(1) on a target whose own
|
|
//! spread is O(1) — a DIFFERENT MODEL, not a different rounding.
|
|
//!
|
|
//! The tie is not exotic, it is structural: at `min_samples_leaf = 1` the recursion
|
|
//! reaches nodes holding two samples, and EVERY feature splits two samples into the
|
|
//! same two singletons, so every feature earns an identical score and the shuffle
|
|
//! decides. Deeper trees reach more such nodes.
|
|
//!
|
|
//! Determinism is not a nicety here, it is what makes [`crate::Address`] mean anything:
|
|
//! a content address over a model that a hidden RNG helped choose names one draw, not
|
|
//! one fit. So the tie-break is the lowest index, the fit is a pure function of the
|
|
//! data, and the same data always names the same model.
|
|
//!
|
|
//! This is why the fixture pins a leaf bound on every boosted case and PROVES
|
|
//! scikit-learn deterministic there before recording it: at the defaults there is no
|
|
//! well-defined answer to match.
|
|
//!
|
|
//! # WHERE A GPU DSL DOES NOT REACH — the honest report
|
|
//!
|
|
//! The split search is `argmax` over `features x candidate positions` of a score built
|
|
//! from prefix sums, which IS data-parallel and would lower to `hanzo-kernel` cleanly.
|
|
//! The RECURSION around it does not:
|
|
//!
|
|
//! * The work at each node depends on a partition computed by the node above it, so the
|
|
//! tree's shape is not known until it is built — and a launch geometry has to be
|
|
//! stated BEFORE the launch. This is not a guess about the DSL, it is what the DSL
|
|
//! is: `hanzo-kernel` exposes the launch shape as `Grid` (`hanzo-kernel/src/lib.rs:35`,
|
|
//! re-exporting `cubecl::CubeCount`), and across all 69 launch sites in that crate
|
|
//! `Grid::Static(..)` is the ONLY variant that appears — every geometry is computed on
|
|
//! the host from a count it already knows, e.g. `Grid::Static(rows as u32, 1, 1)` in
|
|
//! `hanzo-kernel/src/norm.rs:248`. A CART node's sample count is not such a number.
|
|
//! Dispatching per node would need either a device-side launch (CUDA dynamic
|
|
//! parallelism, which ROCm, Metal and Vulkan do not offer alike, so a DSL that lowers
|
|
//! to all four cannot expose it) or a host round trip per tree level, which serialises
|
|
//! the build behind one synchronisation per level.
|
|
//! * The subproblems are wildly unbalanced. A node holding 3 samples and one holding
|
|
//! 3000 are the same dispatch, so a warp-per-node scheme idles almost all of it.
|
|
//! * Every node needs its samples ordered by the candidate feature. Sorting a
|
|
//! shrinking, irregular subset per node is the actual cost, and it is a
|
|
//! permutation-heavy scatter rather than arithmetic.
|
|
//!
|
|
//! The tractable lowering is the HISTOGRAM formulation — bin the features once, then a
|
|
//! node's split search is a fixed-size reduction over `bins x features` and the recursion
|
|
//! only reads histograms. That is exactly what dissolves the obstacle above: the bin count
|
|
//! is a HYPERPARAMETER, so `Grid::Static(nodes_at_level * features, 1, 1)` over a fixed
|
|
//! `bins`-wide reduction is host-knowable before the level runs, and one launch per level
|
|
//! replaces one per node. It is also why `HistGradientBoosting` is the family that gets
|
|
//! accelerated everywhere and exhaustive CART is not.
|
|
//!
|
|
//! But it is a DIFFERENT ALGORITHM with different answers — binning quantises the
|
|
//! thresholds, so it cannot reproduce the node-for-node agreement this module is held to.
|
|
//! It therefore belongs behind its own config rather than silently under this one. It is
|
|
//! NOT built. Naming the obstacle precisely is the finding; a slow port pretending to be
|
|
//! accelerated would not be.
|
|
|
|
use crate::data::Matrix;
|
|
use crate::error::{Error, Result};
|
|
|
|
/// A feature value as a tree reads it: rounded to IEEE-754 binary32.
|
|
///
|
|
/// ONE function, so the crate has exactly one answer to "what does the splitter see".
|
|
/// Applied when ordering values, when grouping near-equal ones, when placing a threshold
|
|
/// between two of them, and when walking a fitted tree — the four places a feature value
|
|
/// is read. Anywhere it were skipped, a fit and a prediction would disagree about which
|
|
/// side of a boundary a sample lies on, which is the one thing a tree must never be
|
|
/// vague about. Returned as `f64` because the midpoint of two binary32 values needs one
|
|
/// more mantissa bit than binary32 has; the threshold is genuinely double.
|
|
///
|
|
/// See the module header for the measurement that forces this.
|
|
fn single(v: f64) -> f64 {
|
|
v as f32 as f64
|
|
}
|
|
|
|
/// The tolerance for calling two feature values the same, in the single-precision space
|
|
/// [`single`] puts them in. Values within it are grouped and never split between.
|
|
///
|
|
/// It is 1e-7 because that is scikit-learn's own constant, and its size is not arbitrary:
|
|
/// binary32 carries ~7 decimal digits, so 1e-7 is the scale at which "these are two
|
|
/// values" and "these are one value the cast happened to separate" stop being
|
|
/// distinguishable.
|
|
const FEATURE_THRESHOLD: f64 = 1e-7;
|
|
|
|
/// A node's impurity at or below this is treated as pure. scikit-learn uses the same
|
|
/// constant for the same purpose, and it matters: without it a node of identical
|
|
/// targets splits forever on rounding noise.
|
|
const PURE: f64 = f64::EPSILON;
|
|
|
|
/// Below this many samples the split search runs sequentially. Thread dispatch costs
|
|
/// more than the scan at small `n`, and a boosted ensemble spends most of its nodes
|
|
/// there. Both paths reduce in ascending feature order, so the answer does not depend
|
|
/// on which one ran.
|
|
const PARALLEL_FLOOR: usize = 512;
|
|
|
|
/// How to grow one tree.
|
|
#[derive(Clone, Copy, PartialEq, Debug)]
|
|
pub struct Config {
|
|
/// Longest root-to-leaf path. Depth 1 is a single split.
|
|
pub depth: usize,
|
|
|
|
/// Fewest samples a node may hold and still be considered for splitting.
|
|
pub min_split: usize,
|
|
|
|
/// Fewest samples either side of a split may hold.
|
|
///
|
|
/// Raising this above 1 is what makes a fit REPRODUCIBLE — see the module header.
|
|
/// It is not only a regularisation knob.
|
|
pub min_leaf: usize,
|
|
}
|
|
|
|
impl Default for Config {
|
|
fn default() -> Self {
|
|
Self {
|
|
depth: 3,
|
|
min_split: 2,
|
|
min_leaf: 1,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Config {
|
|
fn validate(&self) -> Result<()> {
|
|
if self.depth == 0 {
|
|
return Err(Error::Config(
|
|
"depth 0 is a tree with no splits; use depth 1 for a single split".into(),
|
|
));
|
|
}
|
|
if self.min_leaf == 0 || self.min_split == 0 {
|
|
return Err(Error::Config(
|
|
"min_leaf and min_split count samples and must be at least 1".into(),
|
|
));
|
|
}
|
|
Ok(())
|
|
}
|
|
}
|
|
|
|
/// One node. A split or a leaf, never both and never neither.
|
|
#[derive(Clone, Copy, PartialEq, Debug)]
|
|
pub enum Node {
|
|
/// Go left when `row[feature] <= threshold`.
|
|
Split {
|
|
/// Which feature is tested.
|
|
feature: usize,
|
|
/// The value it is tested against.
|
|
threshold: f64,
|
|
/// Index of the `<=` child.
|
|
left: usize,
|
|
/// Index of the `>` child.
|
|
right: usize,
|
|
},
|
|
/// What this region answers.
|
|
Leaf {
|
|
/// The mean of the targets that reached it.
|
|
value: f64,
|
|
},
|
|
}
|
|
|
|
/// A fitted regression tree: a VALUE.
|
|
///
|
|
/// Nodes are in pre-order, left subtree before right — the same order scikit-learn's
|
|
/// depth-first builder emits, so a node-for-node comparison against its arrays needs no
|
|
/// remapping.
|
|
#[derive(Clone, PartialEq, Debug)]
|
|
pub struct Tree {
|
|
nodes: Vec<Node>,
|
|
}
|
|
|
|
impl Tree {
|
|
/// The nodes, pre-order.
|
|
pub fn nodes(&self) -> &[Node] {
|
|
&self.nodes
|
|
}
|
|
|
|
/// What this tree answers for one row.
|
|
///
|
|
/// Total: the walk starts at a node that exists and every `Split` names children
|
|
/// that exist, both established when the tree was built.
|
|
pub fn value(&self, row: &[f64]) -> f64 {
|
|
let mut at = 0;
|
|
loop {
|
|
match self.nodes[at] {
|
|
Node::Leaf { value } => return value,
|
|
Node::Split {
|
|
feature,
|
|
threshold,
|
|
left,
|
|
right,
|
|
// `single` here for the same reason it is in the split search: the
|
|
// threshold was placed between two single-precision values, so the
|
|
// comparison must happen in that space or a row whose f64 and f32
|
|
// values straddle the boundary would predict from the wrong leaf.
|
|
} => {
|
|
at = if single(row[feature]) <= threshold {
|
|
left
|
|
} else {
|
|
right
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/// Fold this tree's shape and parameters into a model's name.
|
|
pub(crate) fn digest(&self, d: crate::Digest) -> crate::Digest {
|
|
let mut d = d.size(self.nodes.len());
|
|
for node in &self.nodes {
|
|
d = match *node {
|
|
// The discriminant is written, so a leaf and a split can never hash
|
|
// alike however their numbers line up.
|
|
Node::Leaf { value } => d.flag(false).real(value),
|
|
Node::Split {
|
|
feature,
|
|
threshold,
|
|
left,
|
|
right,
|
|
} => d
|
|
.flag(true)
|
|
.size(feature)
|
|
.real(threshold)
|
|
.size(left)
|
|
.size(right),
|
|
};
|
|
}
|
|
d
|
|
}
|
|
}
|
|
|
|
/// Grow one tree against arbitrary targets.
|
|
///
|
|
/// `y` is taken as a plain slice rather than as [`crate::Samples`] because the boosting
|
|
/// loop above fits each tree to a RESIDUAL it just computed, which is not the caller's
|
|
/// data and has no business being wrapped as though it were.
|
|
pub(crate) fn grow(x: &Matrix, y: &[f64], config: &Config) -> Result<Tree> {
|
|
config.validate()?;
|
|
// The feature space is binary32, so a value beyond binary32's range becomes an
|
|
// infinity the instant the splitter reads it, and every ordering, grouping and
|
|
// threshold below would then be arithmetic over infinities. Refused here, naming the
|
|
// cell, rather than answered from a tree built on them.
|
|
//
|
|
// `Matrix` is the wrong place for this check even though it is where finiteness is
|
|
// established: `linear` and `logistic` work in double precision and are right to
|
|
// accept a 1e300 feature. The narrower domain belongs to the estimator that has it.
|
|
for i in 0..x.n() {
|
|
for (j, v) in x.row(i).iter().enumerate() {
|
|
if !single(*v).is_finite() {
|
|
return Err(Error::Shape(format!(
|
|
"value at row {i} column {j} is {v:e}, outside binary32's range; \
|
|
a tree reads features at single precision"
|
|
)));
|
|
}
|
|
}
|
|
}
|
|
let mut nodes = Vec::new();
|
|
let mut index: Vec<usize> = (0..x.n()).collect();
|
|
build(x, y, config, &mut index, 0, &mut nodes);
|
|
Ok(Tree { nodes })
|
|
}
|
|
|
|
/// Emits one node, then its left subtree, then its right — scikit-learn's own order.
|
|
///
|
|
/// Returns nothing: the node's own index is `nodes.len()` before it is pushed, and the
|
|
/// children's indices are only known after they are built, so the slot is reserved and
|
|
/// patched. That is why `Node::Split` is written twice.
|
|
fn build(
|
|
x: &Matrix,
|
|
y: &[f64],
|
|
config: &Config,
|
|
index: &mut [usize],
|
|
depth: usize,
|
|
nodes: &mut Vec<Node>,
|
|
) {
|
|
let n = index.len();
|
|
let total: f64 = index.iter().map(|i| y[*i]).sum();
|
|
let value = total / n as f64;
|
|
|
|
// The leaf tests, in scikit-learn's order and with its constant. `impurity <= PURE`
|
|
// is what stops a node of identical targets from splitting on rounding noise.
|
|
let square: f64 = index.iter().map(|i| y[*i] * y[*i]).sum();
|
|
let impurity = square / n as f64 - value * value;
|
|
let bounded = depth >= config.depth
|
|
|| n < config.min_split
|
|
|| n < 2 * config.min_leaf
|
|
|| impurity <= PURE;
|
|
|
|
let split = if bounded {
|
|
None
|
|
} else {
|
|
best(x, y, index, config, total)
|
|
};
|
|
|
|
let Some(found) = split else {
|
|
nodes.push(Node::Leaf { value });
|
|
return;
|
|
};
|
|
|
|
// Reorder this node's samples so the two sides are contiguous, then recurse into
|
|
// the halves. The order within a side is the chosen feature's ascending order,
|
|
// which is also the order the child's own sums accumulate in.
|
|
index.copy_from_slice(&found.order);
|
|
let at = nodes.len();
|
|
nodes.push(Node::Leaf { value });
|
|
let (left_index, right_index) = index.split_at_mut(found.position);
|
|
|
|
let left = at + 1;
|
|
build(x, y, config, left_index, depth + 1, nodes);
|
|
let right = nodes.len();
|
|
build(x, y, config, right_index, depth + 1, nodes);
|
|
|
|
nodes[at] = Node::Split {
|
|
feature: found.feature,
|
|
threshold: found.threshold,
|
|
left,
|
|
right,
|
|
};
|
|
}
|
|
|
|
/// The winning split at one node, or `None` when no candidate is admissible.
|
|
struct Split {
|
|
feature: usize,
|
|
threshold: f64,
|
|
/// Where the left side ends in `order`.
|
|
position: usize,
|
|
/// This node's samples, ascending in `feature`.
|
|
order: Vec<usize>,
|
|
score: f64,
|
|
}
|
|
|
|
/// Searches every feature and returns the best split.
|
|
///
|
|
/// Ties go to the LOWEST FEATURE INDEX — `>` rather than `>=`, folded in ascending
|
|
/// order. That is the whole of the determinism claim in the module header.
|
|
fn best(x: &Matrix, y: &[f64], index: &[usize], config: &Config, total: f64) -> Option<Split> {
|
|
let scan = |feature: usize| scan_feature(x, y, index, config, total, feature);
|
|
|
|
let candidates: Vec<Option<Split>> = if index.len() >= PARALLEL_FLOOR && x.p() > 1 {
|
|
use rayon::prelude::*;
|
|
(0..x.p()).into_par_iter().map(scan).collect()
|
|
} else {
|
|
(0..x.p()).map(scan).collect()
|
|
};
|
|
|
|
candidates
|
|
.into_iter()
|
|
.flatten()
|
|
.fold(None, |best: Option<Split>, next| match best {
|
|
Some(b) if b.score >= next.score => Some(b),
|
|
_ => Some(next),
|
|
})
|
|
}
|
|
|
|
/// The best split on ONE feature.
|
|
fn scan_feature(
|
|
x: &Matrix,
|
|
y: &[f64],
|
|
index: &[usize],
|
|
config: &Config,
|
|
total: f64,
|
|
feature: usize,
|
|
) -> Option<Split> {
|
|
let n = index.len();
|
|
let mut order: Vec<usize> = index.to_vec();
|
|
// Ascending in this feature. `sort_unstable_by` is safe here: values that compare
|
|
// equal are grouped and never split between, so their relative order cannot reach
|
|
// the answer.
|
|
order.sort_unstable_by(|a, b| {
|
|
single(x.at(*a, feature))
|
|
.partial_cmp(&single(x.at(*b, feature)))
|
|
.expect("grow refuses features that do not fit binary32")
|
|
});
|
|
|
|
let low = single(x.at(order[0], feature));
|
|
let high = single(x.at(order[n - 1], feature));
|
|
// A constant feature — within the same tolerance the candidate scan groups by, so a
|
|
// feature that offers no admissible split is skipped rather than scanned.
|
|
if high <= low + FEATURE_THRESHOLD {
|
|
return None;
|
|
}
|
|
|
|
// Prefix sums in ascending order, which is the order scikit-learn's criterion
|
|
// accumulates `sum_left` in as it advances the boundary.
|
|
let mut prefix = Vec::with_capacity(n);
|
|
let mut running = 0.0;
|
|
for i in &order {
|
|
running += y[*i];
|
|
prefix.push(running);
|
|
}
|
|
|
|
let mut best: Option<Split> = None;
|
|
let mut at = 0usize;
|
|
while at < n {
|
|
// Advance past every value within tolerance of this one, so a candidate is only
|
|
// ever placed between two genuinely distinct values.
|
|
while at + 1 < n
|
|
&& single(x.at(order[at + 1], feature))
|
|
<= single(x.at(order[at], feature)) + FEATURE_THRESHOLD
|
|
{
|
|
at += 1;
|
|
}
|
|
at += 1;
|
|
if at >= n {
|
|
break;
|
|
}
|
|
|
|
let (left, right) = (at, n - at);
|
|
if left < config.min_leaf || right < config.min_leaf {
|
|
continue;
|
|
}
|
|
|
|
// The proxy score for squared error: maximising it is equivalent to minimising
|
|
// the weighted variance of the two sides, with the terms that do not depend on
|
|
// the split dropped. scikit-learn maximises exactly this expression.
|
|
let sum_left = prefix[at - 1];
|
|
let sum_right = total - sum_left;
|
|
let score = sum_left * sum_left / left as f64 + sum_right * sum_right / right as f64;
|
|
|
|
if best.as_ref().is_none_or(|b| score > b.score) {
|
|
let (before, after) = (
|
|
single(x.at(order[at - 1], feature)),
|
|
single(x.at(order[at], feature)),
|
|
);
|
|
// `a/2 + b/2`, NOT `(a+b)/2`. The two differ in the last bit and can differ
|
|
// by more when `a+b` overflows toward infinity; scikit-learn writes the
|
|
// former and a threshold that differs in its last bit sends a boundary
|
|
// sample down the other branch. The halves are `f64` over `single` operands,
|
|
// which is exactly what scikit-learn's Cython computes when it divides a
|
|
// `float32` cell by a double literal.
|
|
let mut threshold = before / 2.0 + after / 2.0;
|
|
if threshold == after || !threshold.is_finite() {
|
|
threshold = before;
|
|
}
|
|
best = Some(Split {
|
|
feature,
|
|
threshold,
|
|
position: at,
|
|
order: order.clone(),
|
|
score,
|
|
});
|
|
}
|
|
}
|
|
best
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
fn matrix(rows: &[&[f64]]) -> Matrix {
|
|
Matrix::rows(&rows.iter().map(|r| r.to_vec()).collect::<Vec<_>>()).unwrap()
|
|
}
|
|
|
|
#[test]
|
|
fn a_pure_node_does_not_split() {
|
|
let x = matrix(&[&[0.0], &[1.0], &[2.0], &[3.0]]);
|
|
let t = grow(&x, &[5.0; 4], &Config::default()).unwrap();
|
|
assert_eq!(t.nodes(), &[Node::Leaf { value: 5.0 }]);
|
|
}
|
|
|
|
#[test]
|
|
fn a_constant_feature_offers_no_split() {
|
|
let x = matrix(&[&[1.0], &[1.0], &[1.0], &[1.0]]);
|
|
let t = grow(&x, &[1.0, 2.0, 3.0, 4.0], &Config::default()).unwrap();
|
|
// Impure targets but nothing to split ON, so one leaf at the mean.
|
|
assert_eq!(t.nodes().len(), 1);
|
|
assert!(matches!(t.nodes()[0], Node::Leaf { value } if (value - 2.5).abs() < 1e-15));
|
|
}
|
|
|
|
#[test]
|
|
fn a_single_split_lands_on_the_midpoint_of_the_two_straddling_values() {
|
|
let x = matrix(&[&[0.0], &[1.0], &[2.0], &[3.0]]);
|
|
let t = grow(
|
|
&x,
|
|
&[0.0, 0.0, 10.0, 10.0],
|
|
&Config {
|
|
depth: 1,
|
|
..Config::default()
|
|
},
|
|
)
|
|
.unwrap();
|
|
match t.nodes()[0] {
|
|
Node::Split {
|
|
feature, threshold, ..
|
|
} => {
|
|
assert_eq!(feature, 0);
|
|
assert_eq!(threshold, 1.0 / 2.0 + 2.0 / 2.0);
|
|
}
|
|
n => panic!("expected a split, got {n:?}"),
|
|
}
|
|
assert_eq!(t.value(&[0.5]), 0.0);
|
|
assert_eq!(t.value(&[2.5]), 10.0);
|
|
}
|
|
|
|
#[test]
|
|
fn nodes_are_pre_order_with_the_left_subtree_first() {
|
|
// scikit-learn's own emission order; a node-for-node comparison against its
|
|
// arrays depends on it.
|
|
let x = matrix(&[
|
|
&[0.0],
|
|
&[1.0],
|
|
&[2.0],
|
|
&[3.0],
|
|
&[4.0],
|
|
&[5.0],
|
|
&[6.0],
|
|
&[7.0],
|
|
]);
|
|
let y = [0.0, 1.0, 4.0, 9.0, 16.0, 25.0, 36.0, 49.0];
|
|
let t = grow(
|
|
&x,
|
|
&y,
|
|
&Config {
|
|
depth: 2,
|
|
..Config::default()
|
|
},
|
|
)
|
|
.unwrap();
|
|
// Root at 0, its left child at 1. Whatever the shape, the node right after a
|
|
// split is that split's left child.
|
|
match t.nodes()[0] {
|
|
Node::Split { left, .. } => assert_eq!(left, 1),
|
|
n => panic!("expected a split at the root, got {n:?}"),
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn the_leaf_bound_is_respected_on_both_sides() {
|
|
let x = matrix(&[&[0.0], &[1.0], &[2.0], &[3.0], &[4.0], &[5.0]]);
|
|
let y = [0.0, 1.0, 2.0, 3.0, 4.0, 5.0];
|
|
let t = grow(
|
|
&x,
|
|
&y,
|
|
&Config {
|
|
depth: 9,
|
|
min_split: 2,
|
|
min_leaf: 3,
|
|
},
|
|
)
|
|
.unwrap();
|
|
// 6 samples with a floor of 3 admits exactly one split, so 3 nodes.
|
|
assert_eq!(t.nodes().len(), 3, "{:?}", t.nodes());
|
|
}
|
|
|
|
#[test]
|
|
fn ties_go_to_the_lowest_feature_index_so_a_fit_is_a_function_of_its_data() {
|
|
// Two features that partition identically: every split scores the same. This is
|
|
// the case scikit-learn resolves with its RNG and this crate resolves by index.
|
|
let x = matrix(&[&[0.0, 0.0], &[1.0, 1.0], &[2.0, 2.0], &[3.0, 3.0]]);
|
|
let y = [0.0, 0.0, 10.0, 10.0];
|
|
for _ in 0..16 {
|
|
let t = grow(
|
|
&x,
|
|
&y,
|
|
&Config {
|
|
depth: 1,
|
|
..Config::default()
|
|
},
|
|
)
|
|
.unwrap();
|
|
match t.nodes()[0] {
|
|
Node::Split { feature, .. } => assert_eq!(feature, 0),
|
|
n => panic!("expected a split, got {n:?}"),
|
|
}
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn a_two_sample_node_is_the_tie_that_makes_sklearn_irreproducible() {
|
|
// Documents the mechanism named in the module header, as a live check: with two
|
|
// samples every feature yields the same proxy score, so only the tie-break rule
|
|
// decides. Ours is total; scikit-learn's is a draw.
|
|
let x = matrix(&[&[0.0, 5.0], &[1.0, -5.0]]);
|
|
let y = [1.0, 2.0];
|
|
let t = grow(
|
|
&x,
|
|
&y,
|
|
&Config {
|
|
depth: 1,
|
|
..Config::default()
|
|
},
|
|
)
|
|
.unwrap();
|
|
match t.nodes()[0] {
|
|
Node::Split { feature, .. } => assert_eq!(feature, 0, "lowest index must win"),
|
|
n => panic!("expected a split, got {n:?}"),
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn the_feature_space_is_single_precision_and_a_threshold_shows_it() {
|
|
// The two values straddling the root split of the first boosted fixture tree.
|
|
// Their two midpoints differ in the 8th significant digit, and scikit-learn
|
|
// records the single-precision one — the measurement the module header cites,
|
|
// kept here as a live check so a regression to double precision fails loudly
|
|
// instead of drifting a fixture's tolerance.
|
|
let (a, b) = (-1.5903684017801702f64, -1.5771856983463417f64);
|
|
assert_eq!(a / 2.0 + b / 2.0, -1.583777050063256, "double midpoint");
|
|
assert_eq!(
|
|
single(a) / 2.0 + single(b) / 2.0,
|
|
-1.5837770700454712,
|
|
"single midpoint — this is scikit-learn's threshold"
|
|
);
|
|
|
|
// And the splitter must produce the latter. Two samples, so the only admissible
|
|
// split is between them.
|
|
let x = matrix(&[&[a], &[b]]);
|
|
let t = grow(
|
|
&x,
|
|
&[0.0, 10.0],
|
|
&Config {
|
|
depth: 1,
|
|
..Config::default()
|
|
},
|
|
)
|
|
.unwrap();
|
|
match t.nodes()[0] {
|
|
Node::Split { threshold, .. } => assert_eq!(threshold, -1.5837770700454712),
|
|
n => panic!("expected a split, got {n:?}"),
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn two_values_that_collapse_to_one_in_binary32_are_not_split_between() {
|
|
// Distinct as f64, the SAME value as f32. A double-precision splitter would place
|
|
// a threshold between them and then be unable to honour it, because the walk
|
|
// reads the feature at single precision too and both rows land on one side.
|
|
let a = 1.0f64;
|
|
let b = f64::from_bits(a.to_bits() + 1); // 1.0000000000000002
|
|
assert_ne!(a, b);
|
|
assert_eq!(single(a), single(b));
|
|
let x = matrix(&[&[a], &[b]]);
|
|
let t = grow(
|
|
&x,
|
|
&[0.0, 10.0],
|
|
&Config {
|
|
depth: 1,
|
|
..Config::default()
|
|
},
|
|
)
|
|
.unwrap();
|
|
assert_eq!(
|
|
t.nodes(),
|
|
&[Node::Leaf { value: 5.0 }],
|
|
"one leaf at the mean"
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn a_feature_beyond_binary32_is_refused_rather_than_read_as_an_infinity() {
|
|
// Finite as f64, an infinity the moment a tree reads it: 1e39 is just past
|
|
// binary32's 3.4e38 ceiling. `Matrix` accepts it because a double-precision fit
|
|
// legitimately can; the tree refuses it because it cannot.
|
|
let x = matrix(&[&[1.0], &[1e39], &[2.0], &[3.0]]);
|
|
let e = grow(&x, &[1.0, 2.0, 3.0, 4.0], &Config::default()).unwrap_err();
|
|
let text = format!("{e}");
|
|
assert!(text.contains("row 1 column 0"), "{text}");
|
|
assert!(text.contains("binary32"), "{text}");
|
|
// The same matrix is fine for a double-precision estimator.
|
|
use crate::Fit as _;
|
|
assert!(crate::linear::Config::new()
|
|
.fit(&crate::Samples::new(x, vec![1.0, 2.0, 3.0, 4.0]).unwrap())
|
|
.is_ok());
|
|
}
|
|
|
|
#[test]
|
|
fn depth_zero_is_refused_rather_than_silently_yielding_a_stump() {
|
|
assert!(grow(
|
|
&matrix(&[&[0.0], &[1.0]]),
|
|
&[0.0, 1.0],
|
|
&Config {
|
|
depth: 0,
|
|
..Config::default()
|
|
}
|
|
)
|
|
.is_err());
|
|
}
|
|
}
|