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 oblivious: 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 template¶
Every chapter has the same 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.
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 and 13 are applied chapters that put the core to work: multiclass, then categorical features. For design rationale (why this data layout, why this dispatch mechanism) see the architecture notes; for the audit trail of every non-trivial choice, decisions.md.