LightGBM › Formula

The mathematical foundation of LightGBM builds upon the standard gradient boosting framework, but with key modifications to the tree construction process. Let's start with the fundamental gradient boosting objective function and then see how LightGBM optimizes it.

Note: The Loss function should look very similar to the one in XGBoost, hence we will not repeat the details here. Please refer to the XGBoost section for more detail.

The standard gradient boosting objective function combines a loss function with regularization terms:

$$\mathcal{L}^{(t)} = \sum_{i=1}^{n} l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t)$$

where $l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i))$ is the loss function, $f_t$ is the $t$-th tree we're adding, and $\Omega(f_t)$ is the regularization term for the tree.

In LightGBM, we use a second-order Taylor expansion to approximate this objective:

$$\mathcal{L}^{(t)} \approx \sum_{i=1}^{n} \left[ l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t)$$

where:

• $g_i = \frac{\partial l(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}$: first-order gradient (the slope of the loss function with respect to the prediction for instance $i$)
• $h_i = \frac{\partial^2 l(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)^2}}$: second-order gradient or Hessian (the curvature of the loss function with respect to the prediction for instance $i$)

This second-order approximation provides a more accurate representation of the loss function around the current prediction.

The key innovation in LightGBM lies in its unique approach to constructing decision trees, which is fundamentally different from the traditional level-wise method used in most gradient boosting frameworks.

Let's break down the LightGBM tree construction process step by step:

1. Leaf-wise Growth Strategy:

   • In traditional level-wise tree growth (as in XGBoost by default), all leaves at the current depth are split simultaneously, resulting in a balanced tree.
   • LightGBM, however, adopts a leaf-wise (best-first) growth strategy. At each step, it searches among all current leaves and selects the one whose split would result in the largest reduction in the loss function (i.e., the greatest "gain").
   • This means that LightGBM can grow deeper, more complex branches where the model can most effectively reduce error, potentially leading to higher accuracy with fewer trees.

2. Calculating the Split Gain:

   • When considering splitting a particular leaf $j$, LightGBM evaluates all possible splits and calculates the "gain" for each.
   • The gain measures how much the split would reduce the overall loss function. The formula for the gain when splitting a leaf $j$ into left ($I_L$) and right ($I_R$) children is:

$$\text{Gain} = \frac{1}{2} \left[ \frac{\left(\sum_{i \in I_L} g_i\right)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{\left(\sum_{i \in I_R} g_i\right)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{\left(\sum_{i \in I} g_i\right)^2}{\sum_{i \in I} h_i + \lambda} \right] - \gamma$$

where:

• $g_i$: first-order gradient (the derivative of the loss with respect to the prediction for instance $i$)
• $h_i$: second-order gradient (the second derivative, or curvature, of the loss for instance $i$)
• $I$: set of all instances in the current leaf before the split
• $I_L$: set of instances that would go to the left child leaf after the split
• $I_R$: set of instances that would go to the right child leaf after the split
• $\lambda$: L2 regularization parameter (helps prevent overfitting by penalizing large leaf weights)
• $\gamma$: minimum gain threshold required to make a split (splits with gain less than $\gamma$ are not performed)

Observe that in the gain formula, each term of the form $\frac{\left(\sum g_i\right)^2}{\sum h_i + \lambda}$ represents a fraction: the numerator is the square of the sum of gradients for a group of instances (such as all instances in the left child), and the denominator is the sum of the Hessians (second-order gradients) for those instances plus the regularization parameter $\lambda$.

This fraction reflects the confidence in the leaf's prediction.a larger sum of gradients (numerator) indicates a greater potential adjustment, while a larger sum of Hessians (denominator) or stronger regularization reduces the magnitude of that adjustment. The difference between the fractions for the left and right children and the original leaf quantifies the net reduction in loss achieved by making the split.

1. Step-by-step Gain Calculation:
   • a. For each possible split, sum the gradients ($g_i$) and Hessians ($h_i$) for the left and right child nodes.
   • b. Compute the gain for the split using the formula above.
   • c. Compare the gain to the threshold $\gamma$. If the gain is greater than $\gamma$, the split is considered valid.
   • d. Among all possible splits across all leaves, select the split with the highest gain and perform it.
   • e. Repeat this process, always splitting the leaf with the largest potential gain, until a stopping criterion is met (such as maximum tree depth, minimum number of samples in a leaf, or minimum gain).

This leaf-wise, best-first approach allows LightGBM to focus its modeling capacity where it is most needed, often resulting in faster convergence and higher accuracy compared to level-wise methods. However, because it can create deeper, more complex trees, it may also be more prone to overfitting, especially on small datasets.so regularization and early stopping are important.

In summary, LightGBM's step-by-step tree construction process is:

1. At each iteration, evaluate all possible splits for all current leaves.
2. Calculate the gain for each split using the gradients and Hessians.
3. Select and perform the split with the highest gain (if it exceeds $\gamma$).
4. Repeat until stopping criteria are met.

This process is at the heart of LightGBM's efficiency and predictive power.

The Gradient-based One-Side Sampling (GOSS) technique is a core innovation in LightGBM that significantly accelerates training without sacrificing accuracy, especially on large datasets. GOSS is based on the observation that data instances with larger gradients (i.e., those that are currently poorly predicted by the model) contribute more to the information gain when building trees. Therefore, GOSS prioritizes these "hard" instances during the split-finding process.

GOSS proceeds through four steps:

1. Gradient Calculation:

   • For each data instance, compute the gradient of the loss function with respect to the current prediction. The magnitude of the gradient reflects how much the model's prediction for that instance needs to be updated.

2. Instance Selection:

   • Large-gradient instances: Select and retain all instances whose gradients are among the top $a$ fraction (e.g., the top 20%) of all gradients. These are the most "informative" samples for the current boosting iteration.
   • Small-gradient instances: From the remaining instances (those with smaller gradients), randomly sample a subset, typically a $b$ fraction (e.g., 20%) of the total data. This ensures that the model still sees a representative sample of "easy" instances, but at a much lower computational cost.

3. Reweighting for Unbiased Estimation:

   • Because the small-gradient instances are under-sampled, GOSS compensates by up-weighting their gradients and Hessians during the split gain calculation. Specifically, the gradients and Hessians of the randomly sampled small-gradient instances are multiplied by a factor of $(1-a)/b$ to ensure that the overall distribution of gradients remains unbiased.

Note: The reweighting factor $(1-a)/b$ ensures that the expected contribution of small-gradient instances matches what would be obtained from the full dataset, maintaining the statistical properties of the gradient boosting algorithm.

1. Split Finding:
   • The split-finding process (i.e., evaluating possible feature splits and calculating the gain for each) is then performed using the union of all large-gradient instances and the sampled, reweighted small-gradient instances. This dramatically reduces the number of data points considered at each split, leading to much faster training.

The sampling ratio for small-gradient instances is typically set to $a \times \frac{b}{1-a}$, where $a$ is the sampling ratio for large-gradient instances and $b$ is the sampling ratio for small-gradient instances. For example, if $a=0.2$ and $b=0.2$, then 20% of the data with the largest gradients are retained, and 20% of the remaining data with small gradients are randomly sampled and up-weighted.

The Gradient-based One-Side Sampling (GOSS) technique offers several important advantages. First, it greatly improves efficiency by concentrating computational effort on the most informative samples.those with the largest gradients.thereby reducing the amount of data that needs to be processed at each iteration and resulting in faster training times. Second, GOSS maintains high accuracy because it includes all large-gradient instances. Finally, the reweighting of the randomly sampled small-gradient instances guarantees that the calculation of split gain remains an unbiased estimate of what would be obtained if the full dataset were used, preserving the integrity of the learning process.

In summary, GOSS enables LightGBM to scale to very large datasets by reducing the computational burden of split finding while preserving model accuracy and stability.