Ordered Target Statistics (Ordered TS)

Handling categorical features effectively is a significant challenge in many machine learning tasks, especially within boosting frameworks. Traditional methods often fall short. One-hot encoding, while straightforward, becomes computationally expensive and can lead to sparsity issues when dealing with high-cardinality features (features with many unique categories). Another common approach, standard target encoding (also known as mean encoding), replaces each category with the average target value observed for that category in the training data. However, this method suffers from a critical flaw: target leakage. By using the target value of a data point to compute the feature encoding for that same data point, we inadvertently introduce information about the target into the features, leading to overly optimistic performance estimates during training and poor generalization to unseen data.

CatBoost introduces Ordered Target Statistics (Ordered TS) as an elegant and effective solution to this problem. The core idea is to calculate target statistics for each data point without using its own target value, thereby preventing direct leakage. This is achieved by imposing a specific order on the data.

The Ordered TS Mechanism

Instead of using the entire dataset to calculate the target statistic for a given category, Ordered TS uses an artificial "time" or order imposed on the training data. Here's how it works:

1. Random Permutation: First, the training dataset is randomly shuffled, creating a permutation $\sigma$ of the data indices $\{1, ..., n\}$. This permutation defines an ordering, akin to a sequence in time, where sample $\sigma(k)$ comes "after" sample $\sigma(j)$ if $k > j$.
2. Ordered Calculation: For each sample $x_{\sigma(k)}$ in this sequence, and for each of its categorical features $i$, the target statistic $TS_{k,i}$ is calculated using only the target values $y_{\sigma(j)}$ from the samples preceding it in the permutation (i.e., where $j < k$). Crucially, the target value $y_{\sigma(k)}$ of the current sample is excluded from this calculation.

The formula for the Ordered Target Statistic for sample $k$ and feature $i$ is typically calculated with smoothing:

$$TS_{k,i} = \frac{\sum_{j=1}^{k-1} [x_{\sigma(j), i} = x_{\sigma(k), i}] \cdot y_{\sigma(j)} + \alpha \cdot \text{prior}}{\sum_{j=1}^{k-1} [x_{\sigma(j), i} = x_{\sigma(k), i}] + \alpha}$$

Let's break down this formula:

• $[x_{\sigma(j), i} = x_{\sigma(k), i}]$: This is an indicator function. It equals 1 if the $i$-th categorical feature of the $j$-th sample (in the permutation) has the same category value as the $i$-th feature of the $k$-th sample, and 0 otherwise.
• $y_{\sigma(j)}$: The target value of the $j$-th sample in the permutation.
• $\sum_{j=1}^{k-1} ...$: The summation runs only up to $k-1$, ensuring that only samples appearing before the current sample $k$ in the permutation $\sigma$ are considered.
• $\alpha$: A smoothing parameter (a positive weight).
• $\text{prior}$: A prior value, often set to the overall average target value across the entire training dataset.

The term $\alpha \cdot \text{prior}$ acts as a regularizer. It's particularly important early in the permutation (small $k$) or for rare categories, where there might be very few (or zero) preceding samples with the same category value. The smoothing prevents the encoded value from becoming too noisy or relying heavily on just one or two previous examples. It "pulls" the estimate towards the overall average target value when local information is scarce.

Dependency flow for calculating the Ordered Target Statistic for sample $x_{\sigma(k)}$. The calculation uses target values ($y$) only from preceding samples ($j < k$) in the permutation $\sigma$ that share the same category for feature $i$, combined with a prior value for smoothing. The target $y_{\sigma(k)}$ is not used.

Robustness Through Multiple Permutations

Relying on a single random permutation could potentially introduce its own biases depending on the specific order generated. To mitigate this, CatBoost typically generates multiple random permutations during the training of an ensemble. Different permutations are used when constructing different trees in the boosting model. This averaging effect across various orderings makes the resulting target statistics more stable. This mechanism is closely linked to Ordered Boosting, which we will discuss in the next section, as it ensures that the model trained at each step doesn't suffer from prediction shift caused by the encoding process.

Handling Test Data

When predicting on new, unseen data (the test set), we cannot simply append it to the training permutation and calculate statistics, as this would violate the principle of using only past information. Instead, CatBoost typically uses the target statistics learned during training. For a given category observed in a test sample, the encoding might be calculated using all training samples belonging to that category (often still incorporating the prior and smoothing) or by using pre-calculated statistics stored during the training phase. The exact method can depend on the CatBoost implementation details and parameters.

Advantages of Ordered TS

• Reduces Target Leakage: By explicitly excluding the current sample's target value from its encoding calculation, Ordered TS significantly mitigates the target leakage problem inherent in standard target encoding.
• Effective for High Cardinality: It provides a numerically meaningful encoding for categorical features without resorting to high-dimensional sparse representations like one-hot encoding.
• Integrated Approach: CatBoost incorporates this sophisticated encoding strategy directly into the algorithm, simplifying the preprocessing pipeline for the user.

Ordered Target Statistics represent a substantial improvement in how gradient boosting models can learn from categorical data, forming a foundation for CatBoost's strong performance, particularly on datasets rich in such features.