Ensembles & Boosting

No Peeking, Snacks!

This is the idea behind CatBoost. Trees need numbers, but "Cookie" and "Celery" are names. A common trick swaps each name for "how often kids liked it". Done carelessly, that number peeks at the answer. CatBoost's fix: each row only looks at the rows that came before it.

Two boosters learn whether a kid likes a snack, from its sweetness and its name. One peeks, one does not. Press Train 10 rounds and compare their scores on new kids.

Rounds: 0

liked itdid notshading = the booster's guess

Left to right: how sweet. Bottom to top: the number that stands in for the snack's name. With peeking, rare snacks jump to the very top or bottom, right next to their own answer.

Challenges

Spot the cheat: switch between both views and find the rare snacks at the very top and bottom.
Fooled itself: train until the peeking booster's training score is higher than the no-peeking one's.
Honest wins: after 20 rounds or more, the no-peeking booster scores higher on new kids.
Too good to be true: get the peeking booster's gap at least 3 points bigger than the no-peeking one's.

What just happened?

How it works

  1. Shuffle the training kids into a random line.
  2. Walk down the line. For each kid, count how many earlier kids had the same snack and how many liked it.
  3. Snack number = (liked so far + a little of the overall average) ÷ (seen so far + a little). The first kid to try a snack just gets the average.
  4. Boost trees on sweetness and that snack number.
  5. For new kids, use all the training kids' counts. Their own answers were never in it.
For grown-ups: what's really going on

CatBoost (Prokhorenkova et al., 2018) handles categorical features with ordered target statistics. For a random permutation σ, example k gets x̂k = (Σj: σ(j) < σ(k), xj = xk yj + a·p) / (#{j: σ(j) < σ(k), xj = xk} + a), with prior p (the mean label) and strength a.

  • Greedy target encoding uses each example's own label, so E[x̂k | yk] differs between train and test. This target leakage causes a prediction shift, which hurts most for rare categories.
  • CatBoost also uses ordered boosting: the residuals for example k come from a model that never saw k, using the same permutation idea. It averages several permutations and grows symmetric (oblivious) trees. This demo shows only the ordered statistics, with ordinary boosting on top.
  • Other fixes for the leak: K-fold target encoding, or leave-one-out encoding plus noise. One-hot encoding avoids leakage but explodes with many categories.

Data: 300 training rows, 1500 fresh rows. 40 snacks with skewed popularity; P(like) = σ(6·(sweet − 0.5) + bonus), where only 6 snacks have a real bonus. Boosting: log loss, depth-2 trees, learning rate 0.2, prior strength a = 1.