Ordered boosting changes how a boosting model learns from training examples. Instead of repeatedly computing residuals from the full training data, it first places examples in a random permutation and lets each example use only the examples that came earlier. This prevents the model from indirectly learning from a target value while constructing the prediction used to calculate that example’s residual. section 8.2.1
The motivation is prediction shift: ordinary gradient or Newton boosting reuses training data across iterations, changing the gradient distribution and biasing estimates of generalization. Ordered boosting addresses this by using permutation-based histories when training weak estimators. The same ordering principle supports ordered target statistics for categorical features, but the two operations solve related problems at different stages. section 8.2.1
A simplified ordered-boosting procedure is:
- Randomly permute the training examples. section 8.2.1
- For each example, construct the information used for its training update from only the preceding examples in the permutation. section 8.2.1
- Use multiple randomized sequences in practice because examples appearing early have shorter histories and therefore less information. section 8.2.1
A small permutation
Suppose eight examples are ordered as 4, 7, 1, 8, 2, 6, 5, 3. When calculating an ordered quantity for example 2, use only 4, 7, 1, and 8. When calculating it for example 6, use those four examples plus 2. The current example’s own target is never included. section 8.2.1
CatBoost packages ordered target statistics and ordered boosting into one workflow for categorical data. It identifies categorical columns, performs the needed ordered encoding during training, and uses ordered boosting without requiring a separate category-encoding step. Its base estimators are oblivious decision trees. section 8.2 section 8.3.4
