Split Finding Algorithm: Exact Greedy

XGBoost utilizes a regularized learning objective to build the decision trees that constitute its ensemble. A primary component of this tree-building process is the split finding algorithm. For each potential node in a tree being constructed, the algorithm must identify the best feature and the best split point for that feature to partition the data. The "best" split maximizes the reduction in the objective function value, which is commonly referred to as the gain.

XGBoost employs several strategies for finding splits, and the most fundamental one is the Exact Greedy Algorithm. It's termed "exact" because it meticulously evaluates every possible split point for every feature among the instances currently residing in that node. It's "greedy" because it makes the locally optimal choice at each node, selecting the split with the highest gain without considering the impact on subsequent splits further down the tree.

Quantifying the Split Quality: The Gain Calculation

Recall the XGBoost objective function at step $t$, incorporating the complexity penalty:

$Obj^{(t)} \approx \sum_{i=1}^{n} [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)$

Where $g_i$ and $h_i$ are the first and second-order gradients of the loss function with respect to the prediction for instance $i$ at step $t-1$. $f_t(x_i)$ is the prediction of the new tree for instance $i$, and $\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$ is the regularization term, with $T$ being the number of leaves and $w_j$ the weight of leaf $j$.

For a fixed tree structure, the optimal weight $w_j^*$ for a leaf $j$ containing the set of instances $I_j$ is:

$w_j^* = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}$

And the corresponding optimal objective value contributed by this tree structure is:

$Obj^* = - \frac{1}{2} \sum_{j=1}^{T} \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T$

Let's define $G_j = \sum_{i \in I_j} g_i$ and $H_j = \sum_{i \in I_j} h_i$. The objective becomes:

$Obj^* = - \frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T$

Now, consider splitting a leaf (node) containing instances $I$ into two children: a left child with instances $I_L$ and a right child with instances $I_R$, such that $I = I_L \cup I_R$. The gain from this split is the objective value for the parent node (if it remained a leaf) minus the sum of the objective values for the two new child leaves.

The objective value if the node $I$ is not split (remains a single leaf) is: $Obj_{nosplit} = - \frac{1}{2} \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} + \gamma$

The objective value if the node is split into $I_L$ and $I_R$ is: $Obj_{split} = - \frac{1}{2} \left( \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} \right) + 2\gamma$

The gain is defined as $Gain = Obj_{nosplit} - Obj_{split}$. However, XGBoost literature often defines gain slightly differently, focusing purely on the improvement in the first part of the objective function and subtracting the penalty $\gamma$ for adding a leaf (since splitting replaces one leaf with two, adding complexity):

$Gain = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma$

This formula is the core calculation used by the exact greedy algorithm. A split is considered beneficial only if the resulting gain is positive (or greater than a minimum threshold parameter, min_split_loss, also known as gamma in the API). The term $\gamma$ acts as a regularization parameter, controlling the complexity by setting a minimum gain required to make a split.

The Exact Greedy Algorithm Steps

The algorithm proceeds as follows for each node:

1. Initialize max_gain = 0.
2. For each feature $k$ from $1$ to $d$ (number of features): a. Let $I$ be the set of instances in the current node. b. Calculate the total gradient $G = \sum_{i \in I} g_i$ and hessian $H = \sum_{i \in I} h_i$. c. Sort the instances in $I$ based on their values for feature $k$. d. Initialize $G_L = 0$, $H_L = 0$. e. Iterate through the sorted instances $i$ from left to right: i. Update $G_L = G_L + g_i$, $H_L = H_L + h_i$. ii. Calculate $G_R = G - G_L$, $H_R = H - H_L$. iii. Consider a potential split point between the current instance $i$ and the next instance (or typically, use unique sorted feature values as potential split points). iv. Calculate the gain for this potential split using the formula: $Gain = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G^2}{H + \lambda} \right] - \gamma$ v. If $Gain > max\_gain$, update $max\_gain = Gain$ and store the current feature $k$ and split point as the best split found so far.
3. If $max\_gain > 0$ (or max\_gain \ge \text{min_split_loss}), split the node using the best feature and split point found. Otherwise, declare the node a leaf.

The following diagram illustrates the process for finding the best split for a single feature:

Iterative process within the exact greedy algorithm for a single feature. Instances are sorted, and each potential split point is evaluated based on the gain calculation. The best split across all features determines the node's fate.

Computational Approaches

The main computational bottleneck in the exact greedy algorithm is sorting the feature values at each node. If there are $n$ instances reaching a node and $d$ features:

• Sorting takes $O(n \log n)$ time for each feature.
• Scanning the sorted instances to find the best split point takes $O(n)$ time after sorting.
• Doing this for all $d$ features results in a complexity of roughly $O(d \times n \log n)$ per node.

While thorough, this enumeration can become computationally demanding, especially when dealing with:

• Large number of instances ($n$).
• Large number of features ($d$).
• Deep trees (where the process repeats many times).

This computational cost motivates the development of approximate split finding algorithms, which we will discuss in the next section. They trade off some accuracy in finding the absolute best split for significant gains in computational efficiency, making XGBoost practical for very large datasets.

The exact greedy algorithm forms the foundation for tree construction in XGBoost. Its strength lies in its exhaustive search for the locally optimal split based on the regularized objective function. Understanding this process is important for appreciating how XGBoost builds highly effective trees and why alternative methods like approximate algorithms are sometimes necessary.