How does an ordered target statistic stop a row's own label from leaking into its encoding?

## What a target statistic is A categorical column with tens of thousands of distinct values — think a ZIP-code column with 40,000 levels in a home-insurance quote model — cannot be handed to a tree learner as a raw string. One route used inside modern gradient-boosting algorithms is to **summarise** the level: replace each category value with a number computed from the labels of the training rows that carry it. For a binary target that number is a smoothed mean: ``` TS(c) = (sum of y over rows with category c + a * p) / (count of rows with category c + a) ``` Here `p` is a prior (usually the overall positive rate) and `a > 0` is a weight that controls how strongly a rare level is pulled toward that prior. One numeric column now stands in for 40,000 levels, the tree splits on it with an ordinary threshold, and levels with almost no data degrade gracefully toward the prior. ## Why the naive version leaks The whole question is *which rows go into the sum*. Compute the statistic over the entire training set and every row's own label sits inside its own feature value. The damage scales with rarity. A ZIP code appearing in exactly two rows, with labels 1 and 0, gives both rows an encoding near the middle — but a ZIP code appearing once with label 1 gets a value near 1, and one appearing once with label 0 gets a value near 0. Sort the training rows by that feature and the labels line up. The learner sees an enormous split gain, spends capacity there, and at serving time the same feature is computed without the row's own label and carries nothing like that signal. The conditional distribution of the feature given the label therefore differs between training and serving. That mismatch is the **prediction shift**, and it is not fixed by adding trees or lowering the learning rate — the feature itself is a different feature in the two regimes. The property you actually need is simple to state: the encoding assigned to row `i` must not be a function of `y_i`. ## The ordered statistic Draw a random permutation of the training rows. Walk the rows in that order, holding a running sum and count per category value. When you reach row `i`, its encoding uses only the rows that came **before** it in the permutation and share its category: ``` TS_i = (sum of y_j for j before i with cat_j = cat_i + a * p) / (count of such j + a) ``` Only after the encoding is emitted is `y_i` folded into the running totals, so the next row with that category benefits from it. This is an online or streaming average over the permutation's history. Each row's value depends on other rows' labels but never on its own, so the leak is removed by construction rather than by tuning a parameter. ## What the ordering costs Rows near the front of the permutation have few or no predecessors with their category, so their encodings are dominated by the prior and are high-variance. Nothing is biased, but early rows carry less information than late ones. The standard remedy is not one ordering but several: the algorithm samples multiple random permutations and uses different ones for different trees, so a row that is unlucky in one ordering is well placed in another and the noise averages out across the ensemble. Read this as a deliberate bias-for-variance trade — the naive statistic is low-variance and badly biased, the ordered statistic is unbiased and noisier, and averaging over permutations claws the variance back. ## Training versus scoring At scoring time there is no leak left to prevent. The training labels have already been consumed to fit the model, and the row being scored has no label of its own. So the encoding for a category at inference is computed once from **all** training rows carrying it, which is the lowest-variance estimate available, and a value never seen in training falls back on the prior `p`. The training-time feature is deliberately noisier than the serving-time feature — the reverse of the usual worry, and a detail that distinguishes someone who has read the mechanism from someone who has heard the phrase. ## Feature combinations Algorithms built on ordered statistics typically also construct **combinations** of categorical features greedily while growing trees — treating a pair such as (ZIP code, coverage tier) as a single composite level and computing an ordered statistic for it. Much of the practical accuracy on categorical-heavy tables comes from these combinations, and they are only safe because the same ordering rule governs them. ## What it does not fix Leak-free encodings clean the **features**. The residuals that each boosting round fits are still computed with an ensemble that was trained on the row in question, which is the same shift one level up; removing that requires ordered boosting, a separate mechanism built on the same permutation idea.