The bonsai guide: gradient boosting from math to code¶
Production GBT libraries document their parameters; the papers document the math; the code that connects them is hundreds of thousands of lines tuned past readability. This guide is the missing middle, and it is the reason bonsai exists: every chapter takes one concept from intuition, through the (light) math, to the actual lines in this repository that implement it (usually a few dozen), and ends with an experiment you can run against XGBoost, LightGBM, and CatBoost with the same knob turned.
The code the guide references is the shipping code, not a simplification. When a chapter says "this is all there is to GOSS", the linked function is the whole implementation.
Chapters¶
| # | Chapter | One-line pitch |
|---|---|---|
| 0 | A tree by hand | One boosting round on eight rows, every number traced |
| 1 | Gradient boosting | Why trees fit gradients, why second order, where leaf values come from |
| 2 | Binning & histograms | Why 255 buckets beat exact splits, and the subtraction trick |
| 3 | Finding splits | The gain formula, one prefix scan, and where missing values go |
| 4 | Growing trees | Depth-wise vs best-first vs level-wise: three answers to "which leaf next?" |
| 5 | Sampling | Training on fewer rows: Bernoulli, GOSS, and a bug worth learning from |
| 6 | Regularization & constraints | L1/L2, column sampling, monotone and interaction constraints |
| 7 | Early stopping & DART | Knowing when to stop, and dropout for trees |
| 8 | Feature importance | Split vs gain, why they disagree, and what to distrust |
| 9 | Parallelism & determinism | Deterministic models at a fixed thread count, and what that costs |
| 10 | GPU training | Where the host/device boundary goes, and the precision scheme that makes it honest |
| 11 | Performance engineering | The compute-DAG method: price moves before playing them |
| 12 | Multiclass | Softmax boosting: K trees per round and one diagonal approximation |
| 13 | Categorical features | Ordered target statistics: the encoding that doesn't leak, and why the core stays numeric |
| 14 | Feature selection | Ten selection methods raced on real data: who wins at which budget, and what it costs |
| 15 | Explaining predictions | From a broken attribution to Shapley to the path trick to global importance, every step a hand-checkable table |
The shape of a chapter¶
Most chapters share a skeleton:
- The idea: what problem this solves, in plain language.
- The math: just enough notation to make the code inevitable.
- In bonsai: the real implementation, with file links.
- Try it: CLI and Python commands, and what to look for.
- Gotchas & war stories: where the decision log supplies genuine ones (a divergence bug, a deadlock, a factor-of-20 normalization mistake), not hypotheticals.
Chapters 14 and 15 are built around one measured survey and one worked example, so they run their own section order. Every chapter still links the implementation and ends somewhere you can run something.
Reading order¶
Chapter 0 is the on-ramp. Chapters 1 to 4 are the core algorithm and build on each other. Chapters 5 to 9 are independent; read each as the matching knob becomes relevant. Chapters 10 and 11 go where the engineering is: GPU training, then performance. Chapters 12 to 15 put the core to work: multiclass, categorical features, feature selection, then explaining predictions. For design rationale (why this data layout, why this dispatch mechanism) see the invariants; for the audit trail of every non-trivial choice, decisions.md.