CatBoost: The Interpreter Who Refused to Peek at Tomorrow's Newspaper

The One-Line Summary: Replacing a category with the average target for that category is the most common feature-engineering trick in tabular machine learning and it quietly hands the model the answer - measured here, it turned a column containing literally no signal into a training loss of 0.2466 and a test loss of 2.7975, five times worse than deleting the column; CatBoost's ordered target statistics fix the leak by letting each row see only rows that came before it. The Parable of the Court at Vashti The court employed interpreters, because testimony arrived in six languages and the judges read one. An interpreter's job was to render each witness's words faithfully, and for two centuries the court considered this a solved problem. Then someone noticed that the interpreters were extraordinarily good at old cases and merely average at new ones. The Old Way: Read the Whole File First Every interpreter was handed the complete case file before beginning. This was considered basic professionalism - how could you translate testimony about a boundary dispute without knowing it was a boundary dispute? The file included the verdict. WHY THE OLD INTERPRETERS LOOKED SO GOOD ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Witness says a word that could mean "he took it" or "he was given it". Interpreter has read the file. The file says GUILTY. She writes "he took it." She is not lying. She is not even conscious of choosing. The ambiguity resolved itself the moment she knew how it ended. On closed cases her renderings are uncanny. On open cases she is ordinary, and nobody can work out why. The interpreters were not corrupt. They were contaminated, which is worse, because contamination leaves no one to blame and nothing obvious to fix. The Investigation A clerk named Ilaya was asked to audit the interpreters and did something nobody had tried: she took a hundred old cases, stripped the verdicts, and had them re-translated by the same people. THE SAME INTERPRETERS, VERDICTS HIDDEN ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ with the file (as always) near-perfect renderings without the verdict ordinary renderings indistinguishable from a first-year apprentice The skill everyone had been admiring for two centuries was not skill. It was the verdict, travelling backwards into the testimony. The court's instinct was to ban case files entirely. Ilaya argued against it: context genuinely helps, and an interpreter working blind is worse than one working informed. The problem was never the file. It was which parts of the file. "Let her read everything that was written before the words she is translating. Nothing that was written after. The rule is not ignorance - it is chronology." ILAYA'S RULE ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Translating testimony from the 3rd of the month? You may read: everything filed on the 1st, 2nd. You may not read: the 4th onward. Ever. Especially the verdict. Each document is translated using only the court's knowledge AS IT STOOD at that moment. Slower. Occasionally the interpreter has almost no context and must simply admit it. Those renderings are honest, and they hold up. The first interpreters trained this way looked worse on the court's historical records. They were the first ones who did not get worse when the case was live. What Is Target Encoding, and Why Does It Leak? Hard pivot. You have a categorical column with many levels - city, merchant, user ID, product SKU. One-hot encoding it produces thousands of columns. The popular alternative is target encoding: replace each level with the mean of the target for that level. Look at the index set. It includes . Row 's own label is in the numerator of row 's feature. If a level appears once, its encoding is its label, exactly. If it appears three times, the encoding is two-thirds someone else's answer and one-third your own. That is the verdict travelling backwards into the testimony. The Fix, Formally CatBoost computes ordered target statistics. Fix a random permutation of the rows. For row , use only rows that precede it: where is a prior (the global mean) and its weight. Row is excluded by construction - it hasn't happened yet. The prior does the work when history is thin. The same principle is applied to the gradients during boosting, which is where the name "ordered boosting" comes from, but the target-statistic version is where the damage usually is. Measuring the Leak The cleanest possible test: build a categorical column that carries no information whatsoever, and see whether target encoding can conjure signal out of it. 6,000 rows, 2,000 levels - roughly three rows per level, which is exactly the regime where people reach for target encoding. import numpy as np, pandas as pd from sklearn.model_selection import train_test_split, KFold from sklearn.metrics import log_loss from sklearn.ensemble import HistGradientBoostingClassifier rng = np.random.default_rng(0) n, K = 6000, 2000 cat = rng.integers(0, K, n) # pure noise: 2,000 levels x1 = rng.normal(size=n) y = (0.9 * x1 + rng.normal(0, 1.0, n) > 0).astype(int) # y ignores cat X = pd.DataFrame({"cat": cat, "x1": x1}) Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0) ctr, cte = Xtr["cat"].values, Xte["cat"].values gm = ytr.mean() def score(A, B): m = HistGradientBoostingClassifier(max_iter=200, random_state=0).fit(A, ytr) return (log_loss(ytr, m.predict_proba(A)[:, 1]), log_loss(yte, m.predict_proba(B)[:, 1])) full_mean = pd.Series(ytr).groupby(ctr).mean() B = Xte.copy(); B["cat"] = pd.Series(cte).map(full_mean).fillna(gm).values A = Xtr.copy(); A["cat"] = pd.Series(ctr).map(full_mean).fillna(gm).values tr, te = score(A, B) print(f" naive target encoding train {tr:.4f} test {te:.4f} gap {te-tr:+.4f}") A2 = Xtr.copy(); enc = np.full(len(Xtr), np.nan); ys = pd.Series(ytr) for itr, iva in KFold(5, shuffle=True, random_state=0).split(Xtr): mm = ys.iloc[itr].groupby(ctr[itr]).mean() enc[iva] = pd.Series(ctr[iva]).map(mm).fillna(ys.iloc[itr].mean()).values A2["cat"] = enc tr, te = score(A2, B) print(f" out-of-fold encoding train {tr:.4f} test {te:.4f} gap {te-tr:+.4f}") tr, te = score(Xtr[["x1"]], Xte[["x1"]]) print(f" drop the column train {tr:.4f} test {te:.4f} gap {te-tr:+.4f}") naive target encoding train 0.2466 test 2.7975 gap +2.5508 out-of-fold encoding train 0.4436 test 0.5823 gap +0.1388 drop the column train 0.4964 test 0.5464 gap +0.0500 Sit with the first row. The column is random integers. It has no relationship to the target - I generated y from x1 alone. And naive target encoding produced a training loss of 0.2466, better than the honest model can achieve, and a test loss of 2.7975 - roughly five times worse than simply deleting the column. A model that has memorised the training set and learned nothing looks, during training, exactly like a breakthrough. Ordered Target Statistics from Scratch Ilaya's rule is about thirty lines. Walk the rows in a random permutation, encode each one from the running totals so far, then add it to the totals. import numpy as np def ordered_target_stats(cat, y, prior, a=1.0, seed=0): """Each row is encoded using only rows earlier in the permutation.""" rng = np.random.default_rng(seed) perm = rng.permutation(len(cat)) enc = np.empty(len(cat)) csum, ccnt = {}, {} for pos in perm: c = cat[pos] s, k = csum.get(c, 0.0), ccnt.get(c, 0) enc[pos] = (s + a * prior) / (k + a) # history only - self excluded csum[c] = s + y[pos] # now add self, for later rows ccnt[c] = k + 1 return enc The two lines after the assignment are the whole idea. The row contributes to everyone after it and never to itself. Run all four encodings on the same data, both when the column is noise and when it genuinely carries signal, three seeds each: === NO signal in the column (test logloss, 3 seeds) === seed naive oof ordered drop 0 2.7975 0.5823 0.5812 0.5464 1 3.2548 0.5780 0.6050 0.5545 2 2.9780 0.5988 0.6014 0.5702 MEAN 3.0101 0.5863 0.5959 0.5570 === REAL signal in the column (test logloss, 3 seeds) === seed naive oof ordered drop 0 2.2485 0.5707 0.6737 0.6398 1 2.5480 0.5564 0.6239 0.6139 2 2.0538 0.5601 0.6670 0.6518 MEAN 2.2834 0.5624 0.6549 0.6352 Four readings, and the third one surprised me. Naive encoding is a catastrophe either way - 3.0101 and 2.2834 against roughly 0.56 for every honest method. It does not matter whether the column has signal. The leak dominates. When the column carries real signal, encoding it pays. Out-of-fold scored 0.5624 against 0.6352 for dropping the column. That is the case for target encoding, and it is a real one. My ordered implementation lost to plain out-of-fold - 0.6549 against 0.5624. I expected the opposite, and I am reporting it because it is what the code printed. Dropping a signal-free column beats every encoding of it. 0.5570 against 0.5863 out-of-fold. No scheme recovers information that was never there; encoding only adds noise with a plausible face. Why the Ordered Version Underperformed A result you did not expect is worth ten minutes before you publish it. The obvious suspect is variance: early rows in the permutation have almost no history, so their encodings are mostly prior. CatBoost's actual answer to this is to average several permutations - so I tried that. import numpy as np, pandas as pd from sklearn.model_selection import train_test_split from sklearn.metrics import log_loss from sklearn.ensemble import HistGradientBoostingClassifier def ordered_target_stats(cat, y, prior, a=1.0, seed=0): rng = np.random.default_rng(seed) perm = rng.permutation(len(cat)) enc = np.empty(len(cat)); csum, ccnt = {}, {} for pos in perm: c = cat[pos]; s, k = csum.get(c, 0.0), ccnt.get(c, 0) enc[pos] = (s + a * prior) / (k + a) csum[c] = s + y[pos]; ccnt[c] = k + 1 return enc rng = np.random.default_rng(0) n, K = 6000, 2000 cat = rng.integers(0, K, n) eff = rng.normal(0, 1.5, K) # this time the column MATTERS x1 = rng.normal(size=n) y = (eff[cat] + 0.9 * x1 + rng.normal(0, 1.0, n) > 0).astype(int)