Addressing Prediction Shift: Ordered Boosting

Ordered Target Statistics (Ordered TS) provides a principled method for encoding categorical features, utilizing only the observed history within the data. This technique substantially reduces the risk of target leakage compared to naive target encoding methods. However, a subtle issue known as prediction shift can still arise during the standard gradient boosting training process.

Prediction shift occurs because the gradient (or residual) calculated for a specific training example at iteration $m$ depends on the model $F_{m-1}$ built using all preceding iterations. If target statistics were used to build the trees in $F_{m-1}$, the model has implicitly gained information about the target variable of the current example, even if Ordered TS was used for the encoding itself. The model updating process itself can re-introduce bias. Specifically, when calculating the residual for example $x_i$, the model has already been influenced by example $i$'s target value through the target statistics used in previous boosting steps.

CatBoost introduces Ordered Boosting to directly address this prediction shift. Instead of training a single sequence of models on the original dataset, Ordered Boosting uses random permutations of the training data.

Consider the standard boosting process where the model $F_m$ is built sequentially:

$$F_m(x) = F_{m-1}(x) + \alpha \cdot h_m(x)$$

Here, $h_m(x)$ is the tree trained at step $m$, typically fitted to the negative gradient (residuals) $r_{m-1}$ calculated using $F_{m-1}$. The issue arises when $r_{m-1}$ for example $x_i$ is calculated using $F_{m-1}$, a model which might have been influenced by $y_i$ via target encoding in steps $1, ..., m-1$.

Ordered Boosting modifies this process. It works as follows:

1. Generate Permutations: CatBoost generates multiple random permutations, let's say $\sigma_1, \sigma_2, ..., \sigma_S$, of the training data indices $\{1, ..., n\}$.
2. Train Permutation-Specific Models: For each permutation $\sigma_s$, CatBoost maintains a separate sequence of models $M^s_0, M^s_1, ..., M^s_{m_{max}}$.
3. Ordered Residual Calculation: When building the $m$-th tree for permutation $\sigma_s$, the residual for the $i$-th example in that specific permutation (i.e., the example at index $\sigma_s(i)$) is calculated using only the model $M^s_{m-1}$ trained on the first $i-1$ examples of that permutation $\sigma_s$. That is, the residual $r_{\sigma_s(i)}$ depends on $M^s_{m-1}(\mathbf{x}_{\sigma_s(j)})$ for $j < i$.
4. Model Update: The weak learner (tree) $h^s_m$ is trained using these carefully calculated residuals. The model for permutation $s$ is updated: $M^s_m = M^s_{m-1} + \alpha h^s_m$.
5. Final Model: The final prediction model is derived from these permutation-specific models. The exact mechanism is complex, but it aggregates the learning across permutations.

This procedure ensures that when calculating the gradient estimate for a given example, the model used for this calculation has not been influenced by the target value of that same example. It mimics the situation during inference, where the target is unknown.

Let's visualize this with a simplified concept for a single permutation $\sigma$.

Simplified view of Ordered Boosting for one permutation $\sigma$ at boosting step $m$. The model used to calculate the residual for example $x_{\sigma(i)}$ is built using only examples preceding it in the permutation ($x_{\sigma(1)}$ to $x_{\sigma(i-1)}$).

Ordered Boosting complements Ordered TS. Ordered TS ensures the feature encoding for an example $x_i$ uses target information only from preceding examples in a permutation. Ordered Boosting ensures the gradient calculation for $x_i$ uses a model trained only on preceding examples in that permutation. Together, they provide a defense against target leakage contaminating both the feature representation and the model update steps.

While maintaining $S$ separate models seems computationally intensive, CatBoost employs efficient implementation techniques, particularly leveraging the structure of its Oblivious Trees (discussed in the "Oblivious Trees" section), to make Ordered Boosting practical.

"The primary benefit of Ordered Boosting is a significant reduction in prediction shift, leading to models that generalize better from training to unseen data. This is especially impactful when dealing with datasets containing strong categorical predictors where target leakage can easily lead to inflated performance metrics during training that do not translate to performance. The resulting models are generally more reliable."

The main trade-off is potentially increased training time compared to standard gradient boosting implementations that do not employ such a mechanism. However, CatBoost's overall optimizations, including GPU acceleration and efficient handling of categorical data, often make it competitive or even faster in practice, especially on datasets where its specialized features are advantageous.

By tackling prediction shift head-on, Ordered Boosting, in conjunction with Ordered TS, represents a substantial advancement in how gradient boosting algorithms handle categorical data, contributing considerably to CatBoost's reputation for accuracy and robustness out-of-the-box.