LightGBM

Fast gradient boosting: histogram splits, leaf-wise trees, and GOSS / EFB to skip work on easy rows and sparse features.

18 min read2009 wordsadvanced9 viewsupdated 2026-10-07

Definition

LightGBM (Light Gradient Boosting Machine, Microsoft 2017) is gradient-boosted decision trees engineered for speed. For classification it fits each new tree to the gradients and hessians of the log-loss, finds splits by scanning histograms of binned features instead of sorted values, grows trees leaf-wise (always splitting the leaf with the largest gain), and uses GOSS and EFB to skip rows that are already well fit and to merge sparse features that never overlap.

At a glance

Task
Binary and multiclass classification (also regression and ranking — see LightGBM regression)
Input → output
feature vector xx → raw score F(x)F(x) → probability p=σ(F(x))p=\sigma(F(x)) (softmax over KK scores for multiclass)
Learns
MM trees; each stores bin-threshold splits and a real-valued leaf weight ww added to the log-odds
Training
per tree: one pass over the rows of the smaller child to build a histogram, then O(bins×d)O(\text{bins}\times d) to scan splits; rows and features can be sub-sampled (GOSS, bagging, EFB)
Prediction
O(M×depth)O(M\times\text{depth}) comparisons, then one sigmoid
Key hyperparameters
num_leaves, learning_rate, n_estimators (with early stopping), min_child_samples, max_bin, reg_lambda, feature_fraction, data_sample_strategy='goss'
Assumes
nothing about distributions; rows are i.i.d.; the order of feature values carries the signal (splits are thresholds on bins)

The problem

Classic gradient boosting (see Gradient boosting and XGBoost) finds each split by sorting every feature and trying every threshold between consecutive distinct values. For nn rows and dd features that costs about O(n d)O(n\,d) per tree level after an O(nlog⁡n)O(n\log n) sort, and it reads 4–8 bytes per value from memory in a cache-unfriendly order. On a click-log with 10810^8 rows and thousands of sparse features, a single model can take hours, and a hyperparameter search becomes impossible.

Two kinds of work are wasted. Late in training most rows are already predicted confidently — their gradients are near zero, so they barely change any split score, yet every split still loops over them. And many features are sparse one-hot columns that are almost never non-zero together, yet each one gets its own scan. LightGBM attacks each source of waste with one idea.

The idea

Keep the boosting recipe — each tree is a Newton step on the log-loss — but make the split search cheap. Bin each feature once into at most 255 buckets, so a node summarizes its rows as a small histogram of gradient sums and the split search scans bins, not rows. Build only the smaller child's histogram and get its sibling by subtraction. Spend the leaf budget where it helps most by growing leaf-wise. Then cut the input itself: GOSS keeps every row with a large gradient but only a random fraction of the easy ones (re-weighted to stay unbiased), and EFB packs mutually exclusive sparse features into one dense column.

Vocabulary

Raw score / log-odds
F(x)=log⁡p1−pF(x)=\log\frac{p}{1-p}, the sum of all trees' leaf weights plus the starting value F0F_0
Gradient $g_i$
∂ℓ/∂F\partial \ell/\partial F at row ii; for log-loss gi=pi−yig_i=p_i-y_i — how far and in which direction the current probability is off
Hessian $h_i$
∂2ℓ/∂F2=pi(1−pi)\partial^2 \ell/\partial F^2=p_i(1-p_i) — the curvature; it is small for confident rows, large near p=0.5p=0.5
Bin
an interval of a feature's values; all rows in the same bin are indistinguishable to the split search. Edges are chosen once, before training, from quantiles
Histogram
for one leaf and one feature: per bin, the sums Gb=∑giG_b=\sum g_i, Hb=∑hiH_b=\sum h_i and the row count
Histogram subtraction
parent histogram − one child's histogram = the other child's histogram, so only the smaller child is built from rows
Leaf-wise (best-first) growth
always split the current leaf whose best split has the largest gain, until num_leaves leaves exist; trees can be deep and lopsided
Depth-wise (level-wise) growth
split every leaf of one depth before going deeper (classic XGBoost); trees are balanced
GOSS
Gradient-based One-Side Sampling: keep the top aa fraction of rows by ∣g∣|g|, sample a bb fraction of the rest, multiply the sampled rows' gg and hh by 1−ab\frac{1-a}{b}
EFB
Exclusive Feature Bundling: merge features that are (almost) never non-zero in the same row into one feature, by offsetting their bins

The math

For a label y∈{0,1}y\in\{0,1\} and a raw score FF, the loss of one row is the log-loss (binary cross-entropy):

ℓ(y,F)=−[ylog⁡p+(1−y)log⁡(1−p)],p=σ(F)=11+e−F\ell(y,F)=-\big[y\log p+(1-y)\log(1-p)\big],\qquad p=\sigma(F)=\frac{1}{1+e^{-F}}
yy
true class, 0 or 1
FF
current raw score (log-odds) of the row
pp
predicted probability of class 1
σ\sigma
logistic sigmoid

Differentiate through the sigmoid, using σ′(F)=p(1−p)\sigma'(F)=p(1-p). The log⁡\log and the sigmoid cancel neatly:

g=∂ℓ∂F=p−y,h=∂2ℓ∂F2=p(1−p)g=\frac{\partial \ell}{\partial F}=p-y,\qquad h=\frac{\partial^2 \ell}{\partial F^2}=p(1-p)
gg
gradient: positive when p is too high (y = 0), negative when too low (y = 1)
hh
hessian: at most 0.25 (at p = 0.5); near 0 for confident rows

Training starts from the best constant, F0=log⁡pˉ1−pˉF_0=\log\frac{\bar p}{1-\bar p} with pˉ\bar p the fraction of positives. A new tree adds wjw_j to every row in its leaf jj. Expanding the loss to second order around the current scores (the Newton step — derived in full in XGBoost), the change in total loss from leaf jj is ∑i∈j(giwj+12hiwj2)+12λwj2\sum_{i\in j}\big(g_i w_j+\tfrac12 h_i w_j^2\big)+\tfrac12\lambda w_j^2. Write Gj=∑i∈jgiG_j=\sum_{i\in j} g_i and Hj=∑i∈jhiH_j=\sum_{i\in j} h_i and set the derivative to zero:

wj⋆=−GjHj+λ,ΔLj=−12 Gj2Hj+λw_j^\star=-\frac{G_j}{H_j+\lambda},\qquad \Delta\mathcal L_j=-\frac12\,\frac{G_j^2}{H_j+\lambda}
wj⋆w_j^\star
optimal leaf weight (added to the log-odds, times the learning rate)
Gj, HjG_j,\,H_j
sums of gradients and hessians of the rows in leaf j
λ\lambda
L2 penalty on leaf weights (reg_lambda, default 0 in LightGBM)
ΔLj\Delta\mathcal L_j
loss reduction the leaf achieves at its optimal weight

A split replaces one leaf by two, so its value is the improvement in that score. LightGBM reports it without the 12\tfrac12 (a constant factor that does not change which split wins):

gain=GL2HL+λ+GR2HR+λ−(GL+GR)2HL+HR+λ\text{gain}=\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}
GL,HLG_L,H_L
gradient and hessian sums of the rows sent left
GR,HRG_R,H_R
the same for the right child

The key observation: the gain needs only the sums GG and HH on each side — not the individual rows. If a feature is binned, then for a threshold at the edge after bin kk, GL=∑b≤kGbG_L=\sum_{b\le k}G_b is a prefix sum of the histogram. One left-to-right sweep over the bins scores every candidate threshold. The histogram is built in one pass over the leaf's rows (O(nleaf)O(n_{\text{leaf}}) per feature), and the scan costs O(bins)O(\text{bins}) regardless of nn.

histsibling[b]=histparent[b]−histchild[b]for G, H, count\text{hist}_{\text{sibling}}[b]=\text{hist}_{\text{parent}}[b]-\text{hist}_{\text{child}}[b]\quad\text{for } G,\,H,\,\text{count}
bb
bin index; the identity holds because each row lands in exactly one child

GOSS changes which rows enter the sums. Rows are ranked by ∣gi∣|g_i|; the top a⋅na\cdot n (set AA) are kept, a random b⋅nb\cdot n of the rest (set BB) are kept, and the others are dropped for this tree. To keep the sums unbiased, the sampled small-gradient rows are up-weighted:

G^=∑i∈Agi+1−ab∑i∈Bgi,H^=∑i∈Ahi+1−ab∑i∈Bhi\hat G=\sum_{i\in A} g_i+\frac{1-a}{b}\sum_{i\in B} g_i,\qquad \hat H=\sum_{i\in A} h_i+\frac{1-a}{b}\sum_{i\in B} h_i
aa
top_rate: fraction of rows kept by largest |g| (default 0.2)
bb
other_rate: fraction sampled from the remaining rows (default 0.1)
1−ab\tfrac{1-a}{b}
weight of each sampled row: BB stands in for all (1−a)n(1-a)n small-gradient rows

Because E[1−ab∑i∈Bgi]=∑i∉AgiE\big[\tfrac{1-a}{b}\sum_{i\in B}g_i\big]=\sum_{i\notin A}g_i, the estimated sums — and so the gains and leaf weights — are unbiased for the small-gradient part, and the large-gradient part is exact. The approximation error lives only in rows whose gradients are small, which is why it barely moves the split choice on large data. Each tree touches (a+b) n(a+b)\,n rows: 30% with the defaults.

Hyperparameters, mathematically. λ\lambda shrinks every leaf weight toward 0 (w=−G/(H+λ)w=-G/(H+\lambda)) and lowers the gain of splits that create leaves with small HH, i.e. few or confident rows. min_child_weight is a floor on HH per leaf; min_child_samples a floor on the row count. The learning rate η\eta scales each tree's contribution, F←F+η wF\leftarrow F+\eta\,w. max_bin sets how many thresholds exist per feature: fewer bins means coarser splits and less variance. num_leaves caps the leaves per tree — with leaf-wise growth it, not depth, is the main capacity knob.

Worked example: will this visitor buy?

Twelve sessions of an online shop: pages viewed, and whether the visitor bought. 5 of 12 bought, so pˉ=5/12=0.417\bar p=5/12=0.417 and F0=log⁡(5/7)=−0.336F_0=\log(5/7)=-0.336. Notice the pattern is not monotone: moderate browsers (11–14 pages) all bought, while heavy browsers (16–21 pages) mostly did not — window shoppers. We grow one LightGBM tree with 4 bins, num_leaves = 3, λ=0\lambda=0 and η=0.3\eta=0.3.

PagesBoughtBing = p − yh = p(1 − p)
2010.4170.243
3010.4170.243
5010.4170.243
6020.4170.243
812−0.5830.243
9020.4170.243
1113−0.5830.243
1213−0.5830.243
1413−0.5830.243
16040.4170.243
1814−0.5830.243
21040.4170.243
Sessions, their bin (edges 5.5, 10, 15 — three rows per bin) and the first-round gradients. Every row starts at p = 0.417, so every hessian is 0.417 × 0.583 = 0.243.

One tree by hand

  1. 1Histogram. Sum per bin: G=(1.25,  0.25,  −1.75,  0.25)G=(1.25,\;0.25,\;-1.75,\;0.25) and H=0.729H=0.729 in every bin. The total is G=0G=0 — at the best constant the gradients balance — and H=2.917H=2.917.
  2. 2Scan the root. Edge 5.5: 1.2520.729+(−1.25)22.188−0=2.143+0.714=2.857\frac{1.25^2}{0.729}+\frac{(-1.25)^2}{2.188}-0=2.143+0.714=2.857. Edge 10: 1.521.458+(−1.5)21.458=3.086\frac{1.5^2}{1.458}+\frac{(-1.5)^2}{1.458}=3.086. Edge 15: 0.2522.188+0.2520.729=0.114\frac{0.25^2}{2.188}+\frac{0.25^2}{0.729}=0.114. Best: pages ≤ 10, gain 3.086.
  3. 3Subtract. Both children have 6 rows; LightGBM builds the left histogram, (1.25,0.25)(1.25, 0.25), and gets the right one, (−1.75,0.25)(-1.75, 0.25), as root − left without touching its rows.
  4. 4Best split inside each leaf. Left (bins 1–2), edge 5.5: 1.2520.729+0.2520.729−1.521.458=0.686\frac{1.25^2}{0.729}+\frac{0.25^2}{0.729}-\frac{1.5^2}{1.458}=0.686. Right (bins 3–4), edge 15: 1.7520.729+0.2520.729−1.521.458=2.743\frac{1.75^2}{0.729}+\frac{0.25^2}{0.729}-\frac{1.5^2}{1.458}=2.743.
  5. 5Leaf-wise choice. With one leaf left in the budget, split where the gain is largest: the right leaf at pages ≤ 15 (2.743, four times the left's 0.686). A depth-wise learner would split the left leaf first.
  6. 6Leaf weights w=−G/Hw=-G/H: pages ≤ 10: −1.5/1.458=−1.029-1.5/1.458=-1.029; 10 < pages ≤ 15: 1.75/0.729=2.4001.75/0.729=2.400; pages > 15: −0.25/0.729=−0.343-0.25/0.729=-0.343.
  7. 7Update F=F0+0.3 wF=F_0+0.3\,w: the three leaves now predict p=σ(−0.645)=0.344p=\sigma(-0.645)=0.344, σ(0.384)=0.595\sigma(0.384)=0.595 and σ(−0.439)=0.392\sigma(-0.439)=0.392. Training log-loss falls from 0.679 to 0.556.
  8. 8Predict a new visitor with 13 pages: bin 3 → the middle leaf → p=σ(−0.336+0.3×2.400)=0.595p=\sigma(-0.336+0.3\times2.400)=0.595, so the model predicts buys after a single tree.
TreeLeaves (pages)p per bin 1 / 2 / 3 / 4Train log-loss
Stump (2 leaves)≤ 10 · > 100.344 / 0.344 / 0.493 / 0.4930.614
Leaf-wise, 3 leaves≤ 10 · 10–15 · > 150.344 / 0.344 / 0.595 / 0.3920.556
Depth-wise, 3 leaves≤ 5.5 · 5.5–10 · > 100.299 / 0.392 / 0.493 / 0.4930.599
4 leaves (one per bin)every bin0.299 / 0.392 / 0.595 / 0.3920.541
Same 3-leaf budget, two growth orders. Leaf-wise picks the split worth 2.743; depth-wise splits the left leaf (0.686) because it comes first in its level. Four leaves would reach 0.541.
▸ LightGBM · one tree on 12 customersstep 1/16
pages viewed · ● no purchase ● bought05101520235689111214161821every row: F = -0.336, p = 0.417
p̄ = 5/12 = 0.417 · F₀ = -0.336
  1. 1F₀ = log(p̄ / (1 − p̄))
  2. 2for m = 1 … M:
  3. 3 g = p − y ; h = p(1 − p)
  4. 4 GOSS: keep top a·n by |g|, sample b·n
  5. 5 hist[bin] += (g, h) # one pass
  6. 6 gain = G_L²/H_L + G_R²/H_R − G²/H
  7. 7 split root at the best boundary
  8. 8 sibling hist = parent − small child
  9. 9 while leaves < L: split max-gain leaf
  10. 10 w = −G / (H + λ) per leaf
  11. 11 F += η · w(x)
  12. 12predict p = σ(F(x))

Start every customer at the log-odds of the base rate: 5 of 12 bought, so F₀ = log(5/7) = -0.336 and p = 0.417 for everyone.

fig.The worked example, step by step. Top: the 12 sessions on the pages axis with the current leaves as bands. Bottom: per-row gradients, then the 4-bin histogram G = (1.25, 0.25, −1.75, 0.25). The three edges score 2.857, 3.086 and 0.114; after the root split at 10 the leaves propose 0.686 and 2.743 and leaf-wise growth takes the larger. Leaf weights −1.029, 2.400, −0.343 give p = 0.344 / 0.595 / 0.392, and 13 pages → 0.595. The last three frames fast-forward 10 rounds and apply GOSS (a = 0.5, b = 0.25).

GOSS on the same data

Run the same learner for 10 rounds. Bins 1 and 3 are pure (0/3 and 3/3 bought), so their rows become easy: p=0.036p=0.036 in bin 1 and p=0.917p=0.917 in bin 3, with ∣g∣|g| of 0.036 and 0.083. Bins 2 and 4 hold one buyer in three, so the best the model can say is p≈0.358p\approx0.358: those rows stay hard, with ∣g∣=0.358|g|=0.358 (non-buyers) or 0.6420.642 (buyers).

GOSS with a=0.5a=0.5, b=0.25b=0.25 keeps the 6 hard rows, draws 3 of the 6 easy ones — say pages 3, 11 and 14 — and gives them weight (1−0.5)/0.25=2(1-0.5)/0.25=2. The next tree's histogram is built from 9 rows instead of 12:

BinRows keptG (all rows)G (GOSS)H (all rows)H (GOSS)
1 (easy)pages 3 ×20.1080.0720.1040.069
2 (hard)all 30.0740.0740.6890.689
3 (easy)pages 11, 14 ×2−0.250−0.3340.2290.306
4 (hard)all 30.0750.0750.6900.690
Histogram for round 11: all 12 rows vs the GOSS estimate. Bins 2 and 4 contain only kept rows, so they are exact; the easy bins are estimated from the sampled rows ×2.

Root gains at the edges 5.5 / 10 / 15 become 0.088 / 0.088 / 0.034 under GOSS, against 0.118 / 0.075 / 0.013 with all rows. Late in training every gain is small, and here the two best candidates are within 0.001 of each other under GOSS (0.0875 at 5.5 vs 0.0880 at 10), so the sample tips the choice to 10 where the full data prefers 5.5. With 12 rows one draw is noisy; on millions of rows the estimate concentrates (the GOSS paper bounds the error at O(1/n)O(1/\sqrt{n})), and the saving — 70% of rows skipped with the defaults — is what matters.

Exclusive Feature Bundling

Wide data is usually sparse: one-hot columns, bag-of-words, user IDs. Two features that are never non-zero in the same row can share one column without losing information: shift the second feature's bins past the first's. Finding the optimal bundling is graph colouring (NP-hard), so LightGBM uses a greedy pass: sort features by how many non-zeros they have, and put each into the first bundle it conflicts with in at most max_conflict_rate × n rows.

Ordercardpaypalvouchergift_wrapbundle = card + 2·paypal + 3·voucher
110011
201002
300103
410001
500010
601002
710001
800000
901002
1000103
10 orders, 4 sparse binary columns. card, paypal and voucher have 0 pairwise conflicts and bundle into one column with values 0 (none), 1, 2, 3. gift_wrap conflicts with card in 1 row, so with no conflicts allowed it starts a second bundle: 4 features → 2.

A split on the bundle at "≤ 1" is the same as asking card or nothing; any original single-feature split can be recovered from bin ranges of the bundle. Histogram cost scales with the number of bundles instead of the number of raw features, which on sparse data is often a 10–100× reduction.

Explore: leaf-wise trees, bins and GOSS in 2-D

The figure below trains 40 rounds (η=0.2\eta=0.2, min_child_samples = 10) on 300 points whose true class boundary is a sine wave, and scores on 600 fresh points. Change the growth order, the leaf budget, the number of bins, or turn GOSS on, and watch both the decision surface and the log-loss curves.

p(class 1) after 40 trees● class 0 ● class 1 · ticks = bin edgeslog-loss vs trees0.40.50.60.7trees → 401— test— train- - test, depth-wise
growthGOSSmax_bin
train 0.287test 0.408 · acc 82.5%best test 0.379 @ 18tree 40: depth 5, rows seen 300/300
fig.Defaults: leaf-wise, 8 leaves, 16 bins. Training log-loss falls to 0.287 after 40 trees, but test log-loss bottoms out at 0.379 after 18 trees and climbs back to 0.408 — use early stopping. 24 leaves overfits faster (best 0.395 after 12 trees, 0.485 at 40); 4 leaves is slower but better here (best 0.370). 4 bins underfits the curve (train 0.399). GOSS (switched on after the first 1/η = 5 trees) builds each later tree from 90 of the 300 rows and acts as a regularizer: train 0.351, test 0.388 at 40. Ticks on the axes are the bin edges: every split must sit on one.

The algorithm, step by step

LightGBM for binary classification

  1. 1Bin once. For every feature, choose up to max_bin edges from (a sample of) the data's quantiles; store every value as a 1-byte bin index. Bundle exclusive sparse features (EFB).
  2. 2Initialize F0=log⁡pˉ1−pˉF_0=\log\frac{\bar p}{1-\bar p} for every row.
  3. 3For m=1…Mm=1\dots M: compute pi=σ(Fi)p_i=\sigma(F_i), gi=pi−yig_i=p_i-y_i, hi=pi(1−pi)h_i=p_i(1-p_i).
  4. 4Sample (optional). GOSS: keep the top a na\,n rows by ∣g∣|g| and a random b nb\,n of the rest, multiplying the latter's g,hg,h by 1−ab\frac{1-a}{b} (skipped for the first 1/η1/\eta rounds). Or bagging with subsample. Optionally sample features (feature_fraction).
  5. 5Root histogram. One pass over the kept rows: add g, h and 1 to the bin of each feature.
  6. 6Grow leaf-wise. Keep, for every current leaf, its best (feature, bin) split from a prefix-sum scan of its histograms. Repeatedly split the leaf with the largest gain; build the smaller child's histogram from its rows and the larger child's by subtraction; scan both children. Stop at num_leaves, or when no split has positive gain or satisfies min_child_samples / min_child_weight / max_depth.
  7. 7Leaf weights wj=−Gj/(Hj+λ)w_j=-G_j/(H_j+\lambda) (with L1 soft-thresholding if reg_alpha > 0), computed from the kept rows.
  8. 8Update every row — sampled or not: Fi←Fi+η wleaf(i)F_i\leftarrow F_i+\eta\,w_{\text{leaf}(i)}. Evaluate the validation log-loss and stop early when it has not improved for stopping_rounds rounds.
  9. 9Predict: p(x)=σ ⁣(F0+η∑mwleafm(x)(m))p(x)=\sigma\!\big(F_0+\eta\sum_m w^{(m)}_{\text{leaf}_m(x)}\big); class 1 if p≥0.5p\ge 0.5 (or a tuned threshold). Multiclass trains KK trees per round on softmax gradients gik=pik−[yi=k]g_{ik}=p_{ik}-[y_i=k].

Complexity per tree

Exact (pre-sorted)
O(n d)O(n\,d) per level to scan sorted values, plus an O(nlog⁡n)O(n\log n) sort per feature up front; 4–8 bytes per value
Histogram
O(nleaf d)O(n_{\text{leaf}}\,d) to build a leaf's histogram, but only for the smaller child (subtraction does the other); O(bins⋅d)O(\text{bins}\cdot d) to scan it
With GOSS
rows touched drop from nn to (a+b) n(a+b)\,n — 30% with the defaults
With EFB
dd drops to the number of bundles
Memory
1 byte per value when max_bin ≤ 255, versus 8 for a float plus an index for pre-sorting

Hyperparameters and tuning

ParameterDefaultEffectTypical search
learning_rate0.1scales each tree; smaller needs more trees but generalizes better0.01–0.1, fixed early
n_estimators100number of rounds; choose by early stopping on validation log-lossup to a few thousand
num_leaves31capacity of each tree (leaf-wise); the main overfitting knob8–255
min_child_samples20minimum rows per leaf; blocks tiny leaves deep in a leaf-wise tree10–200
max_depth−1 (none)safety cap on depth for leaf-wise trees−1 or 6–12
reg_lambda / reg_alpha0 / 0L2 / L1 on leaf weights: w=−G/(H+lambda)w=-G/(H+lambda)0–10
feature_fraction (colsample_bytree)1.0features sampled per tree; decorrelates trees0.5–1.0
subsample + subsample_freq1.0, 0row bagging (needs freq ≥ 1)0.5–0.9, freq 1
data_sample_strategy'bagging''goss' with top_rate 0.2, other_rate 0.1on for very large n
max_bin255thresholds per feature; fewer = faster, coarser, more regularized63–511
scale_pos_weight / is_unbalance1 / Falsere-weights the positive class's gradientsfor rare positives
The settings that matter most for classification, in the order to tune them. Defaults are LightGBM 4.x (scikit-learn API names).

In code

python
1import numpy as np
2
3def bin_edges(x, max_bins):
4 """Cut points between distinct values so each bin holds about n/max_bins rows."""
5 xs = np.sort(x)
6 cuts = [xs[int(len(xs) * q / max_bins) - 1] for q in range(1, max_bins)]
7 return np.unique([(c + xs[xs > c].min()) / 2 for c in cuts if (xs > c).any()])
8
9def histogram(Xb, g, h, rows, nb):
10 """Per feature: sum of g, sum of h and row count in every bin — one pass over the rows."""
11 return [np.stack([np.bincount(Xb[rows, j], g[rows], nb),
12 np.bincount(Xb[rows, j], h[rows], nb),
13 np.bincount(Xb[rows, j], None, nb)]) for j in range(Xb.shape[1])]
14
15def best_split(hist, lam, min_leaf):
16 """Scan bin boundaries: gain = G_L²/(H_L+λ) + G_R²/(H_R+λ) − G²/(H+λ)."""
17 best = (0.0, None, None) # (gain, feature, last bin of left)
18 for j, (hg, hh, hn) in enumerate(hist):
19 G, H, N = hg.sum(), hh.sum(), hn.sum()
20 GL, HL, NL = np.cumsum(hg)[:-1], np.cumsum(hh)[:-1], np.cumsum(hn)[:-1]
21 with np.errstate(divide="ignore", invalid="ignore"):
22 gain = GL**2 / (HL + lam) + (G - GL)**2 / (H - HL + lam) - G**2 / (H + lam)
23 gain[(NL < min_leaf) | (N - NL < min_leaf) | np.isnan(gain)] = -np.inf
24 k = int(np.argmax(gain))
25 if gain[k] > best[0] + 1e-12:
26 best = (float(gain[k]), j, k)
27 return best
28
29def grow_tree(Xb, g, h, rows, nb, num_leaves, lam, min_leaf):
30 """Leaf-wise growth: always split the leaf whose best split has the largest gain."""
31 d = Xb.shape[1]
32 leaves = [dict(rows=rows, lo=[0] * d, hi=[nb - 1] * d, hist=histogram(Xb, g, h, rows, nb))]
33 leaves[0]["best"] = best_split(leaves[0]["hist"], lam, min_leaf)
34 log = []
35 while len(leaves) < num_leaves:
36 i = max(range(len(leaves)), key=lambda t: leaves[t]["best"][0])
37 gain, j, k = leaves[i]["best"]
38 if j is None:
39 break # no leaf can be split
40 P = leaves.pop(i)
41 go_left = Xb[P["rows"], j] <= k
42 L = dict(rows=P["rows"][go_left], lo=P["lo"][:], hi=P["hi"][:])
43 R = dict(rows=P["rows"][~go_left], lo=P["lo"][:], hi=P["hi"][:])
44 L["hi"][j], R["lo"][j] = k, k + 1
45 small, big = (L, R) if len(L["rows"]) <= len(R["rows"]) else (R, L)
46 small["hist"] = histogram(Xb, g, h, small["rows"], nb) # build the smaller child ...
47 big["hist"] = [p - s for p, s in zip(P["hist"], small["hist"])] # ... subtract for the bigger
48 for c in (L, R):
49 c["best"] = best_split(c["hist"], lam, min_leaf)
50 leaves[i:i] = [L, R]
51 log.append((round(gain, 4), j, k))
52 for leaf in leaves:
53 r = leaf["rows"]
54 leaf["w"] = -g[r].sum() / (h[r].sum() + lam) # Newton step for the leaf
55 return leaves, log
56
57def tree_predict(leaves, Xb):
58 out = np.zeros(len(Xb))
59 for leaf in leaves:
60 inside = np.all((Xb >= leaf["lo"]) & (Xb <= leaf["hi"]), axis=1)
61 out[inside] = leaf["w"]
62 return out
63
64def goss_weights(g, a, b, rng):
65 """Keep the top a·n rows by |g|; sample b·n of the rest and up-weight them by (1−a)/b."""
66 n = len(g)
67 order = np.argsort(-np.abs(g), kind="stable")
68 top, rest = order[:int(a * n)], order[int(a * n):]
69 w = np.zeros(n)
70 w[top] = 1.0
71 w[rng.choice(rest, int(b * n), replace=False)] = (1 - a) / b
72 return w
73
74class LightGBMScratch:
75 def __init__(self, rounds=10, lr=0.1, num_leaves=3, max_bins=255, lam=0.0, min_leaf=1, goss=None, seed=0):
76 self.rounds, self.lr, self.num_leaves, self.max_bins = rounds, lr, num_leaves, max_bins
77 self.lam, self.min_leaf, self.goss, self.seed = lam, min_leaf, goss, seed
78
79 def fit(self, X, y):
80 self.edges = [bin_edges(X[:, j], self.max_bins) for j in range(X.shape[1])]
81 Xb = self.bin(X)
82 nb = max(len(e) for e in self.edges) + 1
83 self.F0 = np.log(y.mean() / (1 - y.mean())) # log-odds of the base rate
84 F, rng, self.trees = np.full(len(y), self.F0), np.random.default_rng(self.seed), []
85 for _ in range(self.rounds):
86 p = 1 / (1 + np.exp(-F))
87 g, h = p - y, p * (1 - p) # log-loss gradient and hessian
88 rows = np.arange(len(y))
89 if self.goss:
90 w = goss_weights(g, *self.goss, rng)
91 g, h, rows = g * w, h * w, np.flatnonzero(w)
92 leaves, log = grow_tree(Xb, g, h, rows, nb, self.num_leaves, self.lam, self.min_leaf)
93 self.trees.append((leaves, log))
94 F = F + self.lr * tree_predict(leaves, Xb) # every row moves, sampled or not
95 return self
96
97 def bin(self, X):
98 return np.column_stack([np.searchsorted(e, X[:, j]) for j, e in enumerate(self.edges)])
99
100 def predict_proba(self, X):
101 Xb = self.bin(X)
102 F = self.F0 + self.lr * sum(tree_predict(t, Xb) for t, _ in self.trees)
103 return 1 / (1 + np.exp(-F))
104
105if __name__ == "__main__":
106 pages = np.array([2, 3, 5, 6, 8, 9, 11, 12, 14, 16, 18, 21], float)
107 bought = np.array([0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0])
108 m = LightGBMScratch(rounds=1, lr=0.3, num_leaves=3, max_bins=4).fit(pages[:, None], bought)
109 leaves, log = m.trees[0]
110 print("edges", m.edges[0], "F0", round(m.F0, 4))
111 print("splits (gain, feature, bin):", log)
112 print("leaf values", [round(float(l["w"]), 4) for l in leaves])
113 print("p(new customer, 13 pages) =", round(float(m.predict_proba(np.array([[13.0]]))[0]), 4))
114 p = m.predict_proba(pages[:, None])
115 print("train log-loss", round(float(-np.mean(bought * np.log(p) + (1 - bought) * np.log(1 - p))), 4))
From scratch: quantile bins, log-loss gradients and hessians, histograms with subtraction, leaf-wise growth, Newton leaves and GOSS. Prints the worked example's tree.
text
1edges [ 5.5 10. 15. ] F0 -0.3365
2splits (gain, feature, bin): [(3.0857, 0, 1), (2.7429, 0, 2)]
3leaf values [-1.0286, 2.4, -0.3429]
4p(new customer, 13 pages) = 0.5947
5train log-loss 0.5555
Output of the from-scratch script.
python
1import numpy as np
2import lightgbm as lgb
3
4pages = np.array([2, 3, 5, 6, 8, 9, 11, 12, 14, 16, 18, 21], float).reshape(-1, 1)
5bought = np.array([0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0])
6
7params = dict(num_leaves=3, learning_rate=0.3, max_bin=5, # 5 → the four bins 5.5 / 10 / 15
8 min_data_in_bin=1, min_child_samples=1, min_child_weight=1e-3,
9 reg_lambda=0.0, verbose=-1)
10one = lgb.LGBMClassifier(n_estimators=1, **params).fit(pages, bought)
11
12def show(node, pad=""):
13 if "split_index" in node:
14 print(f"{pad}pages <= {node['threshold']:.1f} gain {node['split_gain']:.4f}")
15 show(node["left_child"], pad + " "); show(node["right_child"], pad + " ")
16 else: # LightGBM folds F0 into the first tree's leaves: value = F0 + lr * w
17 print(f"{pad}leaf raw {node['leaf_value']:.4f} rows {node['leaf_count']}")
18
19show(one.booster_.dump_model()["tree_info"][0]["tree_structure"])
20print("p(13 pages) =", one.predict_proba([[13.0]])[0, 1].round(4))
21
22ten = lgb.LGBMClassifier(n_estimators=10, **params).fit(pages, bought)
23p = ten.predict_proba(pages)[:, 1]
24print("after 10 rounds p =", p.round(4))
25print("|g| =", np.abs(p - bought).round(4))
The library on the worked example. max_bin = 5 makes LightGBM's own bin finder produce exactly the edges 5.5 / 10 / 15; gains and probabilities match the hand computation. For GOSS on real data add data_sample_strategy='goss'.
text
1pages <= 10.0 gain 3.0857
2 leaf raw -0.6450 rows 6
3 pages <= 15.0 gain 2.7429
4 leaf raw 0.3835 rows 3
5 leaf raw -0.4393 rows 3
6p(13 pages) = 0.5947
7after 10 rounds p = [0.0359 0.0359 0.0359 0.3579 0.3579 0.3579 0.9166 0.9166 0.9166 0.3582
8 0.3582 0.3582]
9|g| = [0.0359 0.0359 0.0359 0.3579 0.6421 0.3579 0.0834 0.0834 0.0834 0.3582
10 0.6418 0.3582]
Output: the same splits (gain 3.0857 then 2.7429), leaves F₀ + 0.3·w = −0.645 / 0.3835 / −0.4393, and p(13 pages) = 0.5947. After 10 rounds the easy and hard rows match the GOSS table.

Use when

  • +Tabular data with many rows (10⁵–10⁹) and you need a strong model fast, or many models for a hyperparameter search.
  • +Wide sparse features (one-hot, counts) where EFB collapses thousands of columns.
  • +You want probabilities trained on log-loss, early stopping, missing-value handling and feature importances out of the box.
  • +Training time or memory is the bottleneck for XGBoost-exact or scikit-learn's gradient boosting.

Avoid when

  • −The dataset is small (a few thousand rows): leaf-wise trees overfit easily and the speed advantage is irrelevant.
  • −Many high-cardinality categorical features: CatBoost's ordered encoding is usually more robust.
  • −Inputs are images, audio or text sequences: use neural networks.
  • −You need a smooth or monotone-by-default function, or extrapolation beyond the training range (trees are piecewise constant).

Where it's used

Click-through and conversion prediction

Ad and recommendation systems score billions of impressions with sparse features — the setting LightGBM was designed for (and the source of its GOSS/EFB benchmarks).

Credit and fraud scoring

Default or fraud probability from transaction histories; log-loss probabilities feed into thresholds and expected-loss calculations.

Learning to rank

Search engines use LightGBM's LambdaRank objective on the same histogram trees to order documents.

Tabular competitions and AutoML

A default first model in Kaggle solutions and AutoML systems because a full tuning sweep fits in minutes.

Check yourself

A row has label y = 0 and current probability p = 0.8. Its log-loss gradient and hessian are…

Check yourself

A split sends G_L = −2, H_L = 1 left and G_R = 3, H_R = 2 right, with λ = 1. What are LightGBM's gain and the two leaf weights?

Check yourself

With GOSS defaults (top_rate a = 0.2, other_rate b = 0.1) on 1,000,000 rows, how many rows build each histogram, and what weight do the sampled small-gradient rows get?

Check yourself

A leaf with 10,000 rows splits into children of 2,000 and 8,000 rows. How does LightGBM get both children's histograms?

Remember

  • ✓For classification each tree is a Newton step on log-loss: g=p−yg=p-y, h=p(1−p)h=p(1-p), leaf weight w=−G/(H+λ)w=-G/(H+\lambda), split gain GL2HL+λ+GR2HR+λ−G2H+λ\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{G^2}{H+\lambda}.
  • ✓Histograms of binned features turn the split search into a prefix-sum scan over ≤ 255 bins; subtraction means only the smaller child is built from rows.
  • ✓Leaf-wise growth spends each leaf on the largest gain — lower loss per leaf, but deeper trees; num_leaves and min_child_samples control overfitting.
  • ✓GOSS keeps all large-gradient rows and a re-weighted 1−ab\frac{1-a}{b} sample of the rest; EFB bundles mutually exclusive sparse features.
  • ✓Tune learning rate + early stopping first, then num_leaves / min_child_samples, then sampling and regularization.
← back to ML Algorithms roadmap