Navigate
Courses Tutorials Practice Pricing Tools Upgrade
Lesson 2 of 6

LightGBM and CatBoost in R

In Lesson 1 you built a booster by hand: start at the average, fit each shallow tree to the leftover errors, and add a shrunken slice. It works. But that hand-rolled loop is slow, because at every split it sorts each feature and tries every possible threshold.

Sam's riverside kiosk has grown into a citywide bike-share, with a log of a few million rides. Each ride has a temperature, an hour, one of 300 start stations, and a weekday. To predict demand, the hand-rolled loop would have to test millions of thresholds at every split, and choke on those 300 stations. The production boosters keep the exact same boosting idea from Lesson 1 and make it fast enough for data like this.

By the end of this lesson you will be able to:

  • Explain histogram splits: why bucketing a feature makes the split search fast, and why that speed holds as the data grows
  • Contrast leaf-wise (best-first) tree growth with the older level-by-level way, and the knob that keeps it honest
  • Turn a 300-value category into one useful number instead of 300 one-hot columns, without leaking the target
  • Pick between LightGBM, CatBoost, and XGBoost for a given problem, and write the R that trains each

Prerequisites: Lesson 1, Gradient Boosting from Scratch (the residual loop and the learning rate), and you have met overfitting (the Bias-Variance Tradeoff lesson).

The bottleneck

The slow part is the split search

Remember what a tree does at every node: it tries to find the best place to split. For a numeric feature like temperature, "best" means testing a threshold between each pair of neighbouring values, "below 8.2 vs above", "below 8.4 vs above", and so on, scoring each one. With \(n\) rows a feature can have up to \(n\) distinct values, so up to \(n\) candidate thresholds to score, per feature, at every single node.

Write \(n\) for the number of rows and \(p\) for the number of features. Scanning every candidate at a node costs on the order of \(n \cdot p\) work, and a booster grows hundreds of trees, each with many nodes. On Sam's few-million-row log that is the wall you hit: the arithmetic is simple, but there is an enormous amount of it.

Key Insight
The exact split search is what makes a from-scratch booster slow. Its cost grows with the number of rows, and it repeats at every node of every tree. The two modern boosters attack exactly this, and the first idea is almost embarrassingly simple.