Out-of-Fold Target Encoding for High-Cardinality Categoricals

A user identifier with 200,000 distinct values cannot be one-hot encoded: the design would have more columns than rows, each column would be non-zero once, and a linear model would have no way to separate an effect from noise. The compressible alternative is to replace the identifier with the average target over its rows. A level with a mean outcome far from the global mean is informative, the column becomes one number per row, and the fit sees a real effect rather than a set of near-empty columns. The trouble is that the row’s own label is inside the average that replaces it.

The group-mean estimator and its bias

For a level with n rows, an unregularised target encoding assigns each row the level’s mean label, which is its label sum divided by n. For a binary target with base rate p the estimator’s variance is p (1 - p) / n, which is negligible for a level with a thousand rows and enormous for a level with two. Worse, the estimator is correlated with the row’s own label by construction: the contribution of the row’s own label to its level mean is 1/n, so the feature is a partially self-referential copy of the target. A model that learns a positive coefficient on the column partially learns to predict each row from its own label. The training loss falls and the generalisation does not.

The standard remedy for the variance is shrinkage toward a prior, usually the global mean ybar:

shrunk estimate: (n * level_mean + m * ybar) / (n + m)

The strength m has a clear reading: it is the number of prior observations with mean ybar that the level’s estimate is combined with. As n grows the estimate converges to the level mean; as n goes to zero it converges to the global mean. Equivalently, the encoding is written as ybar + (n / (n + m)) * (level_mean - ybar), a multiplier on the level’s deviation from the base rate that goes to 1 for common levels. This is the same form as a Beta-Binomial posterior mean with prior strength m, and m is best set by validation rather than assumed. Values in the tens are typical for levels of moderate count; the cost of setting m too high is that real effects get flattened, and the cost of setting it too low is that rare levels carry noise.

In denormalised data, where each entity appears many times, the count n is not the sample size for the estimate. Ten thousand transactional rows from one customer are one customer’s worth of evidence about that customer’s behaviour, not ten thousand. Counting rows rather than independent entities makes the shrinkage too weak exactly where it is needed.

Why a global mean leaks and the fold mean does not

Shrinkage addresses variance. It does nothing about the self-reference, which is a bias: after shrinkage the encoding is still a function of the row’s own label. The fix changes the source of the statistic. Split the training set into k folds; for rows in fold j, compute the level means from the other folds only. Then the row’s label is absent from its own encoding, and the feature is a legitimate function of other rows.

The absence has a price. Each row is encoded with a statistic computed from a fraction (k - 1) / k of the training data, so the encoding inherits that estimator’s noise, which is k / (k - 1) times the variance of the full-sample estimate for large levels. More seriously, the encodings for rows in different folds are computed from overlapping but different subsets, so the same level receives slightly different values depending on which fold a row landed in. The model sees a level as a cluster of adjacent values rather than a single point. For a level with many rows the spread is small; for a level with a handful of rows it is not, and rare levels become noisier than the shrinkage alone would suggest.

import numpy as np

def oof_target_encode(levels, y, folds, m=20.0, prior=None):
    prior = np.mean(y) if prior is None else prior
    out = np.empty(len(y))
    for j in np.unique(folds):
        held = folds == j
        # Statistics come only from rows outside the held-out fold
        src_levels, src_y = levels[~held], y[~held]
        counts = {}
        sums = {}
        for lv, yy in zip(src_levels, src_y):
            counts[lv] = counts.get(lv, 0) + 1
            sums[lv] = sums.get(lv, 0.0) + yy
        for i in np.flatnonzero(held):
            n = counts.get(levels[i], 0)
            s = sums.get(levels[i], 0.0)
            out[i] = (s + m * prior) / (n + m)
    return out

Two consequences fall out of this loop. First, a level that appears in only one fold receives no rows from the other folds and is encoded entirely by the prior; the model cannot use it at all, which is the correct behaviour for an entity seen once. Second, the transform is not idempotent in the sense transform libraries assume: applying it to a validation matrix requires the fold assignment to be irrelevant, and it is, because every validation row is encoded from all training rows. That asymmetry, fit on training with folds, apply to anything else with full training statistics, is the state that libraries such as category_encoders implement and that a naive fit/transform split gets wrong.

Inner folds and the double-split cost

There is a second leak that survives the loop above. The encoding for the training rows was constructed using labels from folds other than their own, and when the model is later validated on a held-out fold, the training rows in that held-out fold were encoded using labels from rows adjacent to it. In the usual arrangement, the rows in the outer validation fold are not part of the encoding of the outer training rows, so the outer estimate is clean; but if the encoder is fitted on the whole outer training set and then applied to the outer validation set, its statistics are computed over rows the validation fold must remain blind to in aggregate only, not individually.

The precise requirement is a nesting: the encoding used to fit the model for outer fold j must come from a partition that never places a row used in the encoding of a validation row among the model’s own training rows. The standard construction is nested cross-validation, where the encoder’s folds live inside the outer training partition. The cost is that each outer fold now runs k inner encodings, so the total number of encodings is k^2 per outer fit, and each one is a pass over the label vector. With 2,000 levels and 5 outer folds the constant is small; with 500,000 levels the hash tables dominate the fit time and the encoder becomes the expensive part of the pipeline.

An alternative that avoids inner folds uses leave-one-out encoding, subtracting the row’s own label from the level sum: (label_sum - own_label + m * ybar) / (n - 1 + m). This is exactly unbiased for the row, and it is worse in practice, because the mapping from the feature to the target becomes deterministic and inverted: a row with label 1 gets an encoding biased low, so the model learns a negative relationship for levels with few rows and then applies it to new data where the inversion does not exist. Leave-one-out encoding is a canonical example of a leak that survives a per-row fix and is only removed by a genuine hold-out.

Choosing the encoding for the model that consumes it

The encoding is not model-free. For a linear model the column’s scale matters: a level mean near 0.5 and a level mean near 0.01 differ by a factor of fifty in the units the coefficient is expressed in, and some implementations benefit from transforming the count-weighted deviation before use. For trees the encoding acquires a second role, becoming a form of one-dimensional target summarisation that the split search can exploit; on the training fold the encoding is monotone in the level mean, so trees can split levels by mean outcome, which is what a categorical split would do natively and without the risk. That is why target encoding is most valuable for linear and neural models, where the alternative is many sparse columns.

The connection to the earlier encoding discussion is direct: the one-hot design in one-hot geometry and the dummy trap spends k - 1 degrees of freedom on a factor, while target encoding spends one column and borrows the label to build it. The leakage mechanism inside the encoding is the same aggregation leak described in how a feature becomes a leak, and the reason it is worth a separate treatment is that it is the case where the leak is introduced deliberately and by the intended construction, so the fix has to be built into the transform rather than avoided.

A last property matters at serving time. The encoding learned in training is a lookup table from level to number, plus a prior and a strength. A level never seen in training gets the prior, which is the shrunk estimate for a level with zero observations. That behaviour is well-defined and worth keeping, but it means the model’s output for new levels is constant, and a pipeline that silently maps all unseen levels to a single value can concentrate traffic on one behaviour after a schema change. Keeping the count alongside the encoding, and monitoring how much of the encoded traffic falls back to the prior, is the only way to see this happen.