CatBoost › Formula

CatBoost builds upon the fundamental gradient boosting framework we've already explored, but introduces several key modifications to the standard gradient boosting formula. Let's examine how CatBoost's approach differs from traditional gradient boosting implementations.

The core gradient boosting formula remains the same foundation:

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

where:

• $F_m(x)$: The ensemble model at iteration $m$ (cumulative prediction after adding $m$ trees)
• $F_{m-1}(x)$: The ensemble model from the previous iteration (cumulative prediction after $m-1$ trees)
• $\gamma_m$: The learning rate at iteration $m$ (controls the contribution of each new tree)
• $h_m(x)$: The new tree added at iteration $m$ (trained on residuals or gradients)
• $x$: Input feature vector for a given observation

However, CatBoost modifies how we compute the gradients and how we build the trees.

Categorical Feature Processing:

CatBoost's most distinctive feature is its handling of categorical variables. Instead of preprocessing categorical features, CatBoost computes target statistics during training. For a categorical feature $x^k$ with categories $c_1, c_2, ..., c_k$, CatBoost computes an encoded value for each observation as follows:

$$\hat{x}^k_i = \frac{\sum_{j=1}^{n} [x^k_j = x^k_i] \cdot y_j + \alpha \cdot p}{\sum_{j=1}^{n} [x^k_j = x^k_i] + \alpha}$$

where:

• $\hat{x}^k_i$: The encoded numerical value for the $i$-th observation's category in feature $x^k$
• $x^k_i$: The categorical value of feature $k$ for observation $i$
• $[x^k_j = x^k_i]$: Indicator function that equals 1 if observation $j$ has the same category as observation $i$, and 0 otherwise
• $y_j$: The target value for observation $j$
• $n$: Total number of observations in the dataset
• $\alpha$: Smoothing parameter that controls regularization (typically set to 1)
• $p$: Prior probability of the target (usually the mean of the target variable across the entire dataset)

Numerator:
$\sum_{j=1}^{n} [x^k_j = x^k_i] \cdot y_j$ adds up the target values for all observations that share the same category as the $i$-th observation. The term $\alpha \cdot p$ is added to introduce smoothing, pulling the encoding towards the global mean when there are few samples for a category.

Denominator:
$\sum_{j=1}^{n} [x^k_j = x^k_i]$ counts how many times the category $x^k_i$ appears in the dataset. Adding $\alpha$ to the denominator ensures the encoding is well-defined even for rare categories and further smooths the result.

This formula computes a smoothed mean target value for each category. For each observation, the encoded value is the average target for its category, but "shrunk" towards the overall mean $p$ according to the smoothing parameter $\alpha$. This helps prevent overfitting, especially for categories that appear infrequently.

CatBoost uses this dynamic, smoothed target encoding for categorical features during training. By combining the mean target value for each category with the global mean, CatBoost creates numerical representations of categorical variables that capture their relationship with the target variable while reducing the risk of overfitting.

Symmetric Trees (Oblivious Trees):

CatBoost uses symmetric trees, also known as oblivious trees, where all nodes at the same depth (level) split on the same feature and threshold. This is in contrast to traditional decision trees, where each node can split on any feature independently. In a symmetric tree of depth $d$, there are $d$ binary splits, and thus $2^d$ leaf nodes. The structure of the tree is fully determined by the sequence of $d$ features (and their thresholds) chosen for each level.

Let's formalize the prediction function for a symmetric tree.

Suppose the $m$-th tree in the ensemble has depth $d$, and at each level $k$ ($k = 1, 2, ..., d$), the tree splits on feature $f_k$ at threshold $t_k$. For an input $x$, we can define a binary decision at each level:

$$b_k(x) = \begin{cases} 0 & \text{if } x_{f_k} \leq t_k \\ 1 & \text{if } x_{f_k} > t_k \end{cases}$$

where:

• $b_k(x)$: Binary decision at level $k$ for input $x$ (0 for left branch, 1 for right branch)
• $x_{f_k}$: Value of feature $f_k$ in input vector $x$
• $f_k$: Feature index used for splitting at level $k$
• $t_k$: Threshold value for the split at level $k$

The path from the root to a leaf is determined by the vector of decisions $(b_1(x), b_2(x), ..., b_d(x))$. This vector can be interpreted as a binary number, which uniquely identifies one of the $2^d$ leaves. The index of the leaf node $j$ for input $x$ can be computed as:

$$j(x) = 1 + \sum_{k=1}^d b_k(x) \cdot 2^{d - k}$$

where:

• $j(x)$: Index of the leaf node that input $x$ reaches (ranges from 1 to $2^d$, or 0 to $2^d-1$ if zero-indexed)
• $d$: Depth of the symmetric tree (number of levels)
• $2^{d-k}$: Binary weight for the decision at level $k$

The prediction of the $m$-th symmetric tree for input $x$ is then:

$$h_m(x) = c_{m, j(x)}$$

where:

• $h_m(x)$: Prediction of the $m$-th tree for input $x$
• $c_{m, j}$: The value (prediction) assigned to leaf $j$ in tree $m$
• $j(x)$: The leaf index reached by input $x$ (computed using the formula above)

Alternatively, this can be written in indicator function notation as:

$$h_m(x) = \sum_{j=1}^{2^d} c_{m, j} \cdot \mathbf{1}_{R_{m, j}}(x)$$

where:

• $R_{m, j}$: The region (set of all inputs $x$) corresponding to leaf $j$ in tree $m$

• $\mathbf{1}_{R_{m, j}}(x)$: Indicator function that equals 1 if $x$ falls into region $R_{m, j}$, and 0 otherwise

• $2^d$: Total number of leaves in the symmetric tree of depth $d$

• Each input $x$ is routed through $d$ binary splits (same feature per level for all nodes at that level).

• The sequence of split decisions forms a binary code that selects one of $2^d$ leaves.

• The output is the value assigned to that leaf.

This structure ensures that the tree is perfectly balanced and that the same features are considered at each level, which helps regularize the model and reduce overfitting.

Gradient Computation with Ordered Boosting:

CatBoost implements a technique called "ordered boosting" to reduce overfitting. Instead of using all available data to compute gradients, CatBoost uses only the data that came before the current observation in the training set. This approach simulates the real-world scenario where we don't have access to future data when making predictions.

Let's expand the math behind this process.

Suppose we have a training dataset of $n$ observations, ordered as $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$. At boosting iteration $m$, the model so far is $F_{m-1}(x)$. For each observation $i$, the gradient is:

$$g_{m,i} = \frac{\partial L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}$$

where:

• $g_{m,i}$: Gradient of the loss function for observation $i$ at iteration $m$
• $L$: Loss function (e.g., squared error for regression, log-loss for classification)
• $y_i$: Actual target value for observation $i$
• $F_{m-1}(x_i)$: Current model prediction for observation $i$ at iteration $m-1$
• $x_i$: Feature vector for observation $i$

Traditional boosting computes the split criteria for the next tree using all gradients $\{g_{m,1}, g_{m,2}, \ldots, g_{m,n}\}$, i.e., all data points contribute to the statistics used for finding the best splits.

Ordered boosting in CatBoost, however, restricts the information available for each observation. When computing the split statistics for observation $i$, only the gradients from observations with indices $j < i$ are used. That is, for each $i$, the statistics for building the tree at iteration $m$ are computed using:

$$\{g_{m,j} : j < i\}$$

This can be formalized as follows. For each observation $i$, the split statistics $S_{m,i}$ used to determine the best split are computed as:

$$S_{m,i} = \text{Aggregate}\left(\{g_{m,j} : j < i\}\right)$$

where "Aggregate" denotes the sum or other relevant statistic (such as sum of gradients and Hessians) required for the split-finding algorithm.

This process ensures that, for each observation, the model and the splits are built using only information that would have been available up to that point in the data sequence, thus preventing "target leakage" from future data and reducing overfitting.

In summary:

• The gradient for observation $i$ at iteration $m$ is: $$g_{m,i} = \frac{\partial L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}$$
• When building the tree at iteration $m$, CatBoost uses only the gradients from observations $j < i$ to compute the split criteria for observation $i$: $$S_{m,i} = \text{Aggregate}\left(\{g_{m,j} : j < i\}\right)$$

This ordered approach reduces leakage during training by simulating the real-world scenario where future data is not available.