# gizml:trees

decision trees and their ensembles: CART (scikit-learn's exact splitter and its random splitter for extra trees), forests, bagging, AdaBoost (SAMME and R2), gradient boosting, and one histogram GBDT with depth-wise, leaf-wise and oblivious growth that the xgboost, LightGBM, HistGradientBoosting and CatBoost defaults share. Matrices are row-major f64; a row goes left when its value is at most the threshold.

```gizlang
import * as Trees from "gizml:trees";
```

## Types

### `Tree`

```gizlang
type Tree = { feature: Vec<i64>; threshold: Vec<f64>; left: Vec<i64>; right: Vec<i64>; value: Vec<f64>; width: i64; column: i64; }
```

Node i is a leaf when feature[i] < 0. A leaf holds `width` values, which the tree adds to the outputs from `column`.

- `feature`: `Vec<i64>`
- `threshold`: `Vec<f64>`
- `left`: `Vec<i64>`
- `right`: `Vec<i64>`
- `value`: `Vec<f64>`
- `width`: `i64`
- `column`: `i64`

### `Ensemble`

```gizlang
type Ensemble = { trees: Vec<Tree>; weights: Vec<f64>; base: Vec<f64>; width: i64; combine: string; }
```

combine: mean (forests, bagging), sum (boosting: base + Σ weight × tree), vote (SAMME: the weights of each tree's
class) or median (AdaBoost R2: the weighted median of the trees).

- `trees`: `Vec<M35.Tree>`
- `weights`: `Vec<f64>`
- `base`: `Vec<f64>`
- `width`: `i64`
- `combine`: `string`

### `TreeParams`

```gizlang
type TreeParams = { classes: i64; criterion: string; maxDepth: i64; minSamplesSplit: i64; minSamplesLeaf: i64; maxFeatures: i64; extra: bool; }
```

classes: 0 for regression, else the class count (y is one column of class indexes). criterion: gini, entropy,
squared_error. maxDepth 0: no limit. extra: the random splitter of extremely randomized trees.

- `classes`: `i64`
- `criterion`: `string`
- `maxDepth`: `i64`
- `minSamplesSplit`: `i64`
- `minSamplesLeaf`: `i64`
- `maxFeatures`: `i64`
- `extra`: `bool`

### `BoostParams`

```gizlang
type BoostParams = { rounds: i64; rate: f64; growth: string; maxDepth: i64; maxLeaves: i64; lambda: f64; gamma: f64; minChildWeight: f64; minChildSamples: i64; bins: i64; subsample: f64; colsample: f64; parallel: i64; base: string; softmax: f64; counts: string; }
```

The histogram GBDT. growth: depth (xgboost), leaf (LightGBM, HistGradientBoosting) or oblivious (CatBoost).
A leaf's value is -G / (H + lambda) × rate. A split is made when its gain, GL²/(HL + λ) + GR²/(HR + λ) - G²/(H + λ),
is more than gamma (xgboost states its gamma on half that gain). parallel > 1 grows that many trees for each round on
row and column samples and averages them (xgboost's random forest). base: the tasks that start from their baseline
(the mean, the log-odds of the mean or the log of the class priors): "all", "binary" (regression and binary) or
"regression"; the others start at zero. softmax: the factor of the softmax hessian p(1 - p) (xgboost 2; a negative factor:
k / (k - 1), as LightGBM). counts: how a split counts the rows of a child for minChildSamples: "rows" counts them
in each bin (scikit-learn, CatBoost), "hessian" takes each bin's hessian times the leaf's rows over its hessian
(LightGBM), which keeps the histogram to g and h.

- `rounds`: `i64`
- `rate`: `f64`
- `growth`: `string`
- `maxDepth`: `i64`
- `maxLeaves`: `i64`
- `lambda`: `f64`
- `gamma`: `f64`
- `minChildWeight`: `f64`
- `minChildSamples`: `i64`
- `bins`: `i64`
- `subsample`: `f64`
- `colsample`: `f64`
- `parallel`: `i64`
- `base`: `string`
- `softmax`: `f64`
- `counts`: `string`

## Functions

### `orders`

```gizlang
function orders(x: Vec<f64>, n: i64, d: i64): Vec<Vec<i32>>
```

Each feature's rows 0..n by ascending value, ties in row order, on the threads. The trees on x share them: a node
keeps its rows in each of these orders, so no node sorts (a split parts each order stably).

Effects: fail.

### `growTree`

```gizlang
function growTree(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, width0: i64, weights: Vec<f64>, p: TreeParams, order: Vec<Vec<i32>>, rng: mut Random): Tree
```

A tree grown depth first on the rows with a positive weight (y: class indexes, or n × width targets); `order`
gives each feature's row order (orders(x, n, d)).

Effects: fail.

### `forest`

```gizlang
function forest(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, width: i64, count: i64, bootstrap: bool, p: TreeParams, rng: mut Random): Ensemble
```

Random forests, extra trees and bagging: `trees` trees on bootstrap samples (or on all rows), averaged. The trees
grow on the threads, each from its own seed (as scikit-learn's n_jobs).

Effects: fail.

### `adaBoost`

```gizlang
function adaBoost(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, count: i64, rate: f64, p: TreeParams, rng: mut Random): Ensemble
```

AdaBoost SAMME (classification, stumps by default) and AdaBoost R2 with the linear loss (regression, depth 3).

Effects: fail.

### `gradientBoosting`

```gizlang
function gradientBoosting(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, width: i64, task: string, count: i64, rate: f64, subsample: f64, p: TreeParams, rng: mut Random): Ensemble
```

scikit-learn's GradientBoosting: exact regression trees on the negative gradient, then a Newton step for each leaf.

Effects: fail.

### `boost`

```gizlang
function boost(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, width: i64, task: string, p: BoostParams, rng: mut Random): Ensemble
```

Boosting on histograms. task: regression (y is n × width), binary or multiclass (y holds class indexes). Each
feature is cut in at most p.bins bins (256 at most, xgboost's one-byte bin index), on all threads.

Effects: fail.

## Methods

### `Tree.leafOf`

```gizlang
function Tree.leafOf(self: Tree, row: Vec<f64>): i64
```

The leaf that ROW reaches.

Effects: fail.

### `Ensemble.scores`

```gizlang
function Ensemble.scores(self: Ensemble, row: Vec<f64>): Vec<f64>
```

The scores of ROW, combined over the trees of the ensemble.

Effects: fail.

### `Ensemble.scoresRows`

```gizlang
function Ensemble.scoresRows(self: Ensemble, x: Vec<f64>, d: i64, from: i64, to: i64): Vec<f64>
```

The scores of rows from..to of x (row-major, d wide), `width` for each row, as Ensemble.scores gives them. The rows
walk each tree in turn, four in step on its flat tables: no branch depends on a value, and the tree stays in the
cache. Fewer than WALK_ROWS rows walk each tree in place: the tables of a tree cost more than a few walks.

Effects: fail.

gizml:trees

decision trees and their ensembles: CART (scikit-learn's exact splitter and its random splitter for extra trees), forests, bagging, AdaBoost (SAMME and R2), gradient boosting, and one histogram GBDT with depth-wise, leaf-wise and oblivious growth that the xgboost, LightGBM, HistGradientBoosting and CatBoost defaults share. Matrices are row-major f64; a row goes left when its value is at most the threshold.

gizlang

import * as Trees from "gizml:trees";

Types

`Tree`

gizlang

type Tree = { feature: Vec<i64>; threshold: Vec<f64>; left: Vec<i64>; right: Vec<i64>; value: Vec<f64>; width: i64; column: i64; }

Node i is a leaf when feature[i] < 0. A leaf holds width values, which the tree adds to the outputs from column.

feature: Vec<i64>
threshold: Vec<f64>
left: Vec<i64>
right: Vec<i64>
value: Vec<f64>
width: i64
column: i64

`Ensemble`

gizlang

type Ensemble = { trees: Vec<Tree>; weights: Vec<f64>; base: Vec<f64>; width: i64; combine: string; }

combine: mean (forests, bagging), sum (boosting: base + Σ weight × tree), vote (SAMME: the weights of each tree's class) or median (AdaBoost R2: the weighted median of the trees).

trees: Vec<M35.Tree>
weights: Vec<f64>
base: Vec<f64>
width: i64
combine: string

`TreeParams`

gizlang

type TreeParams = { classes: i64; criterion: string; maxDepth: i64; minSamplesSplit: i64; minSamplesLeaf: i64; maxFeatures: i64; extra: bool; }

classes: 0 for regression, else the class count (y is one column of class indexes). criterion: gini, entropy, squared_error. maxDepth 0: no limit. extra: the random splitter of extremely randomized trees.

classes: i64
criterion: string
maxDepth: i64
minSamplesSplit: i64
minSamplesLeaf: i64
maxFeatures: i64
extra: bool

`BoostParams`

gizlang

type BoostParams = { rounds: i64; rate: f64; growth: string; maxDepth: i64; maxLeaves: i64; lambda: f64; gamma: f64; minChildWeight: f64; minChildSamples: i64; bins: i64; subsample: f64; colsample: f64; parallel: i64; base: string; softmax: f64; counts: string; }

The histogram GBDT. growth: depth (xgboost), leaf (LightGBM, HistGradientBoosting) or oblivious (CatBoost). A leaf's value is -G / (H + lambda) × rate. A split is made when its gain, GL²/(HL + λ) + GR²/(HR + λ) - G²/(H + λ), is more than gamma (xgboost states its gamma on half that gain). parallel > 1 grows that many trees for each round on row and column samples and averages them (xgboost's random forest). base: the tasks that start from their baseline (the mean, the log-odds of the mean or the log of the class priors): "all", "binary" (regression and binary) or "regression"; the others start at zero. softmax: the factor of the softmax hessian p(1 - p) (xgboost 2; a negative factor: k / (k - 1), as LightGBM). counts: how a split counts the rows of a child for minChildSamples: "rows" counts them in each bin (scikit-learn, CatBoost), "hessian" takes each bin's hessian times the leaf's rows over its hessian (LightGBM), which keeps the histogram to g and h.

rounds: i64
rate: f64
growth: string
maxDepth: i64
maxLeaves: i64
lambda: f64
gamma: f64
minChildWeight: f64
minChildSamples: i64
bins: i64
subsample: f64
colsample: f64
parallel: i64
base: string
softmax: f64
counts: string

Functions

`orders`

gizlang

function orders(x: Vec<f64>, n: i64, d: i64): Vec<Vec<i32>>

Each feature's rows 0..n by ascending value, ties in row order, on the threads. The trees on x share them: a node keeps its rows in each of these orders, so no node sorts (a split parts each order stably).

Effects: fail.

`growTree`

gizlang

function growTree(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, width0: i64, weights: Vec<f64>, p: TreeParams, order: Vec<Vec<i32>>, rng: mut Random): Tree

A tree grown depth first on the rows with a positive weight (y: class indexes, or n × width targets); order gives each feature's row order (orders(x, n, d)).

Effects: fail.

`forest`

gizlang

function forest(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, width: i64, count: i64, bootstrap: bool, p: TreeParams, rng: mut Random): Ensemble

Random forests, extra trees and bagging: trees trees on bootstrap samples (or on all rows), averaged. The trees grow on the threads, each from its own seed (as scikit-learn's n_jobs).

Effects: fail.

`adaBoost`

gizlang

function adaBoost(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, count: i64, rate: f64, p: TreeParams, rng: mut Random): Ensemble

AdaBoost SAMME (classification, stumps by default) and AdaBoost R2 with the linear loss (regression, depth 3).

Effects: fail.

`gradientBoosting`

gizlang

function gradientBoosting(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, width: i64, task: string, count: i64, rate: f64, subsample: f64, p: TreeParams, rng: mut Random): Ensemble

scikit-learn's GradientBoosting: exact regression trees on the negative gradient, then a Newton step for each leaf.

Effects: fail.

`boost`

gizlang

function boost(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, width: i64, task: string, p: BoostParams, rng: mut Random): Ensemble

Boosting on histograms. task: regression (y is n × width), binary or multiclass (y holds class indexes). Each feature is cut in at most p.bins bins (256 at most, xgboost's one-byte bin index), on all threads.

Effects: fail.

Methods

`Tree.leafOf`

gizlang

function Tree.leafOf(self: Tree, row: Vec<f64>): i64

The leaf that ROW reaches.

Effects: fail.

`Ensemble.scores`

gizlang

function Ensemble.scores(self: Ensemble, row: Vec<f64>): Vec<f64>

The scores of ROW, combined over the trees of the ensemble.

Effects: fail.

`Ensemble.scoresRows`

gizlang

function Ensemble.scoresRows(self: Ensemble, x: Vec<f64>, d: i64, from: i64, to: i64): Vec<f64>

The scores of rows from..to of x (row-major, d wide), width for each row, as Ensemble.scores gives them. The rows walk each tree in turn, four in step on its flat tables: no branch depends on a value, and the tree stays in the cache. Fewer than WALK_ROWS rows walk each tree in place: the tables of a tree cost more than a few walks.

Effects: fail.