# LightGBM

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

Source: https://www.mlfoundry.in/learn/lightgbm  
Section: ML Algorithms › Supervised · Classification  
Level: advanced · 18 min read · updated 2026-10-07

**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.

- **Task:** Binary and multiclass classification (also regression and ranking — see *LightGBM regression*)
- **Input → output:** feature vector $x$ → raw score $F(x)$ → probability $p=\sigma(F(x))$ (softmax over $K$ scores for multiclass)
- **Learns:** $M$ trees; each stores bin-threshold splits and a real-valued leaf weight $w$ added to the log-odds
- **Training:** per tree: one pass over the rows of the smaller child to build a histogram, then $O(\text{bins}\times d)$ to scan splits; rows and features can be sub-sampled (GOSS, bagging, EFB)
- **Prediction:** $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 $n$ rows and $d$ features that costs about $O(n\,d)$ per tree level *after* an $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 $10^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\frac{p}{1-p}$, the sum of all trees' leaf weights plus the starting value $F_0$
- **Gradient $g_i$:** $\partial \ell/\partial F$ at row $i$; for log-loss $g_i=p_i-y_i$ — how far and in which direction the current probability is off
- **Hessian $h_i$:** $\partial^2 \ell/\partial F^2=p_i(1-p_i)$ — the curvature; it is small for confident rows, large near $p=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 $G_b=\sum g_i$, $H_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 $a$ fraction of rows by $|g|$, sample a $b$ fraction of the rest, multiply the sampled rows' $g$ and $h$ by $\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\in\{0,1\}$ and a raw score $F$, the loss of one row is the log-loss (binary cross-entropy):

$$
\ell(y,F)=-\big[y\log p+(1-y)\log(1-p)\big],\qquad p=\sigma(F)=\frac{1}{1+e^{-F}}
$$

- $y$: true class, 0 or 1
- $F$: current raw score (log-odds) of the row
- $p$: predicted probability of class 1
- $\sigma$: logistic sigmoid

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

$$
g=\frac{\partial \ell}{\partial F}=p-y,\qquad h=\frac{\partial^2 \ell}{\partial F^2}=p(1-p)
$$

- $g$: gradient: positive when p is too high (y = 0), negative when too low (y = 1)
- $h$: hessian: at most 0.25 (at p = 0.5); near 0 for confident rows

Training starts from the best constant, $F_0=\log\frac{\bar p}{1-\bar p}$ with $\bar p$ the fraction of positives. A new tree adds $w_j$ to every row in its leaf $j$. 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 $j$ is $\sum_{i\in j}\big(g_i w_j+\tfrac12 h_i w_j^2\big)+\tfrac12\lambda w_j^2$. Write $G_j=\sum_{i\in j} g_i$ and $H_j=\sum_{i\in j} h_i$ and set the derivative to zero:

$$
w_j^\star=-\frac{G_j}{H_j+\lambda},\qquad \Delta\mathcal L_j=-\frac12\,\frac{G_j^2}{H_j+\lambda}
$$

- $w_j^\star$: optimal leaf weight (added to the log-odds, times the learning rate)
- $G_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)
- $\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 $\tfrac12$ (a constant factor that does not change which split wins):

$$
\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}
$$

- $G_L,H_L$: gradient and hessian sums of the rows sent left
- $G_R,H_R$: the same for the right child

The key observation: the gain needs only the **sums** $G$ and $H$ on each side — not the individual rows. If a feature is binned, then for a threshold at the edge after bin $k$, $G_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(n_{\text{leaf}})$ per feature), and the scan costs $O(\text{bins})$ regardless of $n$.

$$
\text{hist}_{\text{sibling}}[b]=\text{hist}_{\text{parent}}[b]-\text{hist}_{\text{child}}[b]\quad\text{for } G,\,H,\,\text{count}
$$

- $b$: bin index; the identity holds because each row lands in exactly one child

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

$$
\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
$$

- $a$: `top_rate`: fraction of rows kept by largest |g| (default 0.2)
- $b$: `other_rate`: fraction sampled from the remaining rows (default 0.1)
- $\tfrac{1-a}{b}$: weight of each sampled row: $B$ stands in for all $(1-a)n$ small-gradient rows

Because $E\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$ rows: 30% with the defaults.

**Hyperparameters, mathematically.** $\lambda$ shrinks every leaf weight toward 0 ($w=-G/(H+\lambda)$) and lowers the gain of splits that create leaves with small $H$, i.e. few or confident rows. `min_child_weight` is a floor on $H$ per leaf; `min_child_samples` a floor on the row count. The learning rate $\eta$ scales each tree's contribution, $F\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 $\bar p=5/12=0.417$ and $F_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, $\lambda=0$ and $\eta=0.3$.

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.

| Pages | Bought | Bin | g = p − y | h = p(1 − p) |
| --- | --- | --- | --- | --- |
| 2 | 0 | 1 | 0.417 | 0.243 |
| 3 | 0 | 1 | 0.417 | 0.243 |
| 5 | 0 | 1 | 0.417 | 0.243 |
| 6 | 0 | 2 | 0.417 | 0.243 |
| 8 | 1 | 2 | −0.583 | 0.243 |
| 9 | 0 | 2 | 0.417 | 0.243 |
| 11 | 1 | 3 | −0.583 | 0.243 |
| 12 | 1 | 3 | −0.583 | 0.243 |
| 14 | 1 | 3 | −0.583 | 0.243 |
| 16 | 0 | 4 | 0.417 | 0.243 |
| 18 | 1 | 4 | −0.583 | 0.243 |
| 21 | 0 | 4 | 0.417 | 0.243 |

**One tree by hand**

1. **Histogram.** Sum per bin: $G=(1.25,\;0.25,\;-1.75,\;0.25)$ and $H=0.729$ in every bin. The total is $G=0$ — at the best constant the gradients balance — and $H=2.917$.
2. **Scan the root.** Edge 5.5: $\frac{1.25^2}{0.729}+\frac{(-1.25)^2}{2.188}-0=2.143+0.714=2.857$. Edge 10: $\frac{1.5^2}{1.458}+\frac{(-1.5)^2}{1.458}=3.086$. Edge 15: $\frac{0.25^2}{2.188}+\frac{0.25^2}{0.729}=0.114$. **Best: pages ≤ 10, gain 3.086.**
3. **Subtract.** Both children have 6 rows; LightGBM builds the left histogram, $(1.25, 0.25)$, and gets the right one, $(-1.75, 0.25)$, as root − left without touching its rows.
4. **Best split inside each leaf.** Left (bins 1–2), edge 5.5: $\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: $\frac{1.75^2}{0.729}+\frac{0.25^2}{0.729}-\frac{1.5^2}{1.458}=2.743$.
5. **Leaf-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. **Leaf weights** $w=-G/H$: pages ≤ 10: $-1.5/1.458=-1.029$; 10 < pages ≤ 15: $1.75/0.729=2.400$; pages > 15: $-0.25/0.729=-0.343$.
7. **Update** $F=F_0+0.3\,w$: the three leaves now predict $p=\sigma(-0.645)=0.344$, $\sigma(0.384)=0.595$ and $\sigma(-0.439)=0.392$. Training log-loss falls from 0.679 to 0.556.
8. **Predict** a new visitor with 13 pages: bin 3 → the middle leaf → $p=\sigma(-0.336+0.3\times2.400)=0.595$, so the model predicts **buys** after a single tree.

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.

| Tree | Leaves (pages) | p per bin 1 / 2 / 3 / 4 | Train log-loss |
| --- | --- | --- | --- |
| Stump (2 leaves) | ≤ 10 · > 10 | 0.344 / 0.344 / 0.493 / 0.493 | 0.614 |
| **Leaf-wise, 3 leaves** | ≤ 10 · 10–15 · > 15 | **0.344 / 0.344 / 0.595 / 0.392** | **0.556** |
| Depth-wise, 3 leaves | ≤ 5.5 · 5.5–10 · > 10 | 0.299 / 0.392 / 0.493 / 0.493 | 0.599 |
| 4 leaves (one per bin) | every bin | 0.299 / 0.392 / 0.595 / 0.392 | 0.541 |

> Figure: 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.036$ in bin 1 and $p=0.917$ in bin 3, with $|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\approx0.358$: those rows stay *hard*, with $|g|=0.358$ (non-buyers) or $0.642$ (buyers).

GOSS with $a=0.5$, $b=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$. The next tree's histogram is built from 9 rows instead of 12:

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.

| Bin | Rows kept | G (all rows) | G (GOSS) | H (all rows) | H (GOSS) |
| --- | --- | --- | --- | --- | --- |
| 1 (easy) | pages 3 ×2 | 0.108 | 0.072 | 0.104 | 0.069 |
| 2 (hard) | all 3 | 0.074 | 0.074 | 0.689 | 0.689 |
| 3 (easy) | pages 11, 14 ×2 | −0.250 | −0.334 | 0.229 | 0.306 |
| 4 (hard) | all 3 | 0.075 | 0.075 | 0.690 | 0.690 |

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/\sqrt{n})$), and the saving — 70% of rows skipped with the defaults — is what matters.

> **Why sampling by gradient is safe:** A row's influence on any gain is through $g_i$ (and $h_i$). Dropping a row with $|g_i|\approx0$ removes almost nothing from $G_L$ and $G_R$. Uniform subsampling (bagging) throws away hard rows at the same rate as easy ones; GOSS throws away only easy ones, so for the same number of rows it keeps far more of the information that actually moves the splits.

## 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.

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.

| Order | card | paypal | voucher | gift_wrap | bundle = card + 2·paypal + 3·voucher |
| --- | --- | --- | --- | --- | --- |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 | 2 |
| 3 | 0 | 0 | 1 | 0 | 3 |
| 4 | 1 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 1 | 0 |
| 6 | 0 | 1 | 0 | 0 | 2 |
| 7 | 1 | 0 | 0 | 0 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 |
| 9 | 0 | 1 | 0 | 0 | 2 |
| 10 | 0 | 0 | 1 | 0 | 3 |

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 ($\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.

> Figure: 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.

> **num_leaves is not 2^max_depth:** With leaf-wise growth, `num_leaves = 31` can produce a chain 30 levels deep that isolates a handful of rows — far more specific than a depth-5 tree with 32 leaves. On small or noisy data keep `num_leaves` small (8–31), raise `min_child_samples`, and optionally cap `max_depth` as a safety net. Setting `num_leaves` near 2^`max_depth` throws away the benefit of leaf-wise growth while keeping its overfitting risk.

## The algorithm, step by step

**LightGBM for binary classification**

1. **Bin 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. **Initialize** $F_0=\log\frac{\bar p}{1-\bar p}$ for every row.
3. **For** $m=1\dots M$: compute $p_i=\sigma(F_i)$, $g_i=p_i-y_i$, $h_i=p_i(1-p_i)$.
4. **Sample (optional).** GOSS: keep the top $a\,n$ rows by $|g|$ and a random $b\,n$ of the rest, multiplying the latter's $g,h$ by $\frac{1-a}{b}$ (skipped for the first $1/\eta$ rounds). Or bagging with `subsample`. Optionally sample features (`feature_fraction`).
5. **Root histogram.** One pass over the kept rows: add g, h and 1 to the bin of each feature.
6. **Grow 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. **Leaf weights** $w_j=-G_j/(H_j+\lambda)$ (with L1 soft-thresholding if `reg_alpha` > 0), computed from the kept rows.
8. **Update every row** — sampled or not: $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. **Predict:** $p(x)=\sigma\!\big(F_0+\eta\sum_m w^{(m)}_{\text{leaf}_m(x)}\big)$; class 1 if $p\ge 0.5$ (or a tuned threshold). Multiclass trains $K$ trees per round on softmax gradients $g_{ik}=p_{ik}-[y_i=k]$.

**Complexity per tree**

- **Exact (pre-sorted):** $O(n\,d)$ per level to scan sorted values, plus an $O(n\log n)$ sort per feature up front; 4–8 bytes per value
- **Histogram:** $O(n_{\text{leaf}}\,d)$ to build a leaf's histogram, but only for the smaller child (subtraction does the other); $O(\text{bins}\cdot d)$ to scan it
- **With GOSS:** rows touched drop from $n$ to $(a+b)\,n$ — 30% with the defaults
- **With EFB:** $d$ 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

The settings that matter most for classification, in the order to tune them. Defaults are LightGBM 4.x (scikit-learn API names).

| Parameter | Default | Effect | Typical search |
| --- | --- | --- | --- |
| `learning_rate` | 0.1 | scales each tree; smaller needs more trees but generalizes better | 0.01–0.1, fixed early |
| `n_estimators` | 100 | number of rounds; choose by early stopping on validation log-loss | up to a few thousand |
| `num_leaves` | 31 | capacity of each tree (leaf-wise); the main overfitting knob | 8–255 |
| `min_child_samples` | 20 | minimum rows per leaf; blocks tiny leaves deep in a leaf-wise tree | 10–200 |
| `max_depth` | −1 (none) | safety cap on depth for leaf-wise trees | −1 or 6–12 |
| `reg_lambda` / `reg_alpha` | 0 / 0 | L2 / L1 on leaf weights: $w=-G/(H+lambda)$ | 0–10 |
| `feature_fraction` (`colsample_bytree`) | 1.0 | features sampled per tree; decorrelates trees | 0.5–1.0 |
| `subsample` + `subsample_freq` | 1.0, 0 | row bagging (needs freq ≥ 1) | 0.5–0.9, freq 1 |
| `data_sample_strategy` | 'bagging' | `'goss'` with `top_rate` 0.2, `other_rate` 0.1 | on for very large n |
| `max_bin` | 255 | thresholds per feature; fewer = faster, coarser, more regularized | 63–511 |
| `scale_pos_weight` / `is_unbalance` | 1 / False | re-weights the positive class's gradients | for rare positives |

> **Variants inside LightGBM:** `boosting_type='gbdt'` is the standard algorithm; `'dart'` drops random earlier trees each round (dropout for boosting; no early stopping); `'rf'` builds a random forest with the same histogram machinery. Native categorical features (`categorical_feature=`) sort categories by $G/H$ and find the best two-group partition in one scan — handy, but for high-cardinality categories prefer *CatBoost*'s ordered target statistics. Missing values get their own treatment: each split learns whether NaN rows go left or right.

## In code

```python
import numpy as np

def bin_edges(x, max_bins):
    """Cut points between distinct values so each bin holds about n/max_bins rows."""
    xs = np.sort(x)
    cuts = [xs[int(len(xs) * q / max_bins) - 1] for q in range(1, max_bins)]
    return np.unique([(c + xs[xs > c].min()) / 2 for c in cuts if (xs > c).any()])

def histogram(Xb, g, h, rows, nb):
    """Per feature: sum of g, sum of h and row count in every bin — one pass over the rows."""
    return [np.stack([np.bincount(Xb[rows, j], g[rows], nb),
                      np.bincount(Xb[rows, j], h[rows], nb),
                      np.bincount(Xb[rows, j], None, nb)]) for j in range(Xb.shape[1])]

def best_split(hist, lam, min_leaf):
    """Scan bin boundaries: gain = G_L²/(H_L+λ) + G_R²/(H_R+λ) − G²/(H+λ)."""
    best = (0.0, None, None)                                    # (gain, feature, last bin of left)
    for j, (hg, hh, hn) in enumerate(hist):
        G, H, N = hg.sum(), hh.sum(), hn.sum()
        GL, HL, NL = np.cumsum(hg)[:-1], np.cumsum(hh)[:-1], np.cumsum(hn)[:-1]
        with np.errstate(divide="ignore", invalid="ignore"):
            gain = GL**2 / (HL + lam) + (G - GL)**2 / (H - HL + lam) - G**2 / (H + lam)
        gain[(NL < min_leaf) | (N - NL < min_leaf) | np.isnan(gain)] = -np.inf
        k = int(np.argmax(gain))
        if gain[k] > best[0] + 1e-12:
            best = (float(gain[k]), j, k)
    return best

def grow_tree(Xb, g, h, rows, nb, num_leaves, lam, min_leaf):
    """Leaf-wise growth: always split the leaf whose best split has the largest gain."""
    d = Xb.shape[1]
    leaves = [dict(rows=rows, lo=[0] * d, hi=[nb - 1] * d, hist=histogram(Xb, g, h, rows, nb))]
    leaves[0]["best"] = best_split(leaves[0]["hist"], lam, min_leaf)
    log = []
    while len(leaves) < num_leaves:
        i = max(range(len(leaves)), key=lambda t: leaves[t]["best"][0])
        gain, j, k = leaves[i]["best"]
        if j is None:
            break                                               # no leaf can be split
        P = leaves.pop(i)
        go_left = Xb[P["rows"], j] <= k
        L = dict(rows=P["rows"][go_left], lo=P["lo"][:], hi=P["hi"][:])
        R = dict(rows=P["rows"][~go_left], lo=P["lo"][:], hi=P["hi"][:])
        L["hi"][j], R["lo"][j] = k, k + 1
        small, big = (L, R) if len(L["rows"]) <= len(R["rows"]) else (R, L)
        small["hist"] = histogram(Xb, g, h, small["rows"], nb)  # build the smaller child ...
        big["hist"] = [p - s for p, s in zip(P["hist"], small["hist"])]   # ... subtract for the bigger
        for c in (L, R):
            c["best"] = best_split(c["hist"], lam, min_leaf)
        leaves[i:i] = [L, R]
        log.append((round(gain, 4), j, k))
    for leaf in leaves:
        r = leaf["rows"]
        leaf["w"] = -g[r].sum() / (h[r].sum() + lam)            # Newton step for the leaf
    return leaves, log

def tree_predict(leaves, Xb):
    out = np.zeros(len(Xb))
    for leaf in leaves:
        inside = np.all((Xb >= leaf["lo"]) & (Xb <= leaf["hi"]), axis=1)
        out[inside] = leaf["w"]
    return out

def goss_weights(g, a, b, rng):
    """Keep the top a·n rows by |g|; sample b·n of the rest and up-weight them by (1−a)/b."""
    n = len(g)
    order = np.argsort(-np.abs(g), kind="stable")
    top, rest = order[:int(a * n)], order[int(a * n):]
    w = np.zeros(n)
    w[top] = 1.0
    w[rng.choice(rest, int(b * n), replace=False)] = (1 - a) / b
    return w

class LightGBMScratch:
    def __init__(self, rounds=10, lr=0.1, num_leaves=3, max_bins=255, lam=0.0, min_leaf=1, goss=None, seed=0):
        self.rounds, self.lr, self.num_leaves, self.max_bins = rounds, lr, num_leaves, max_bins
        self.lam, self.min_leaf, self.goss, self.seed = lam, min_leaf, goss, seed

    def fit(self, X, y):
        self.edges = [bin_edges(X[:, j], self.max_bins) for j in range(X.shape[1])]
        Xb = self.bin(X)
        nb = max(len(e) for e in self.edges) + 1
        self.F0 = np.log(y.mean() / (1 - y.mean()))             # log-odds of the base rate
        F, rng, self.trees = np.full(len(y), self.F0), np.random.default_rng(self.seed), []
        for _ in range(self.rounds):
            p = 1 / (1 + np.exp(-F))
            g, h = p - y, p * (1 - p)                           # log-loss gradient and hessian
            rows = np.arange(len(y))
            if self.goss:
                w = goss_weights(g, *self.goss, rng)
                g, h, rows = g * w, h * w, np.flatnonzero(w)
            leaves, log = grow_tree(Xb, g, h, rows, nb, self.num_leaves, self.lam, self.min_leaf)
            self.trees.append((leaves, log))
            F = F + self.lr * tree_predict(leaves, Xb)          # every row moves, sampled or not
        return self

    def bin(self, X):
        return np.column_stack([np.searchsorted(e, X[:, j]) for j, e in enumerate(self.edges)])

    def predict_proba(self, X):
        Xb = self.bin(X)
        F = self.F0 + self.lr * sum(tree_predict(t, Xb) for t, _ in self.trees)
        return 1 / (1 + np.exp(-F))

if __name__ == "__main__":
    pages = np.array([2, 3, 5, 6, 8, 9, 11, 12, 14, 16, 18, 21], float)
    bought = np.array([0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0])
    m = LightGBMScratch(rounds=1, lr=0.3, num_leaves=3, max_bins=4).fit(pages[:, None], bought)
    leaves, log = m.trees[0]
    print("edges", m.edges[0], "F0", round(m.F0, 4))
    print("splits (gain, feature, bin):", log)
    print("leaf values", [round(float(l["w"]), 4) for l in leaves])
    print("p(new customer, 13 pages) =", round(float(m.predict_proba(np.array([[13.0]]))[0]), 4))
    p = m.predict_proba(pages[:, None])
    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
edges [ 5.5 10.  15. ] F0 -0.3365
splits (gain, feature, bin): [(3.0857, 0, 1), (2.7429, 0, 2)]
leaf values [-1.0286, 2.4, -0.3429]
p(new customer, 13 pages) = 0.5947
train log-loss 0.5555
```

Output of the from-scratch script.

```python
import numpy as np
import lightgbm as lgb

pages = np.array([2, 3, 5, 6, 8, 9, 11, 12, 14, 16, 18, 21], float).reshape(-1, 1)
bought = np.array([0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0])

params = dict(num_leaves=3, learning_rate=0.3, max_bin=5,        # 5 → the four bins 5.5 / 10 / 15
              min_data_in_bin=1, min_child_samples=1, min_child_weight=1e-3,
              reg_lambda=0.0, verbose=-1)
one = lgb.LGBMClassifier(n_estimators=1, **params).fit(pages, bought)

def show(node, pad=""):
    if "split_index" in node:
        print(f"{pad}pages <= {node['threshold']:.1f}   gain {node['split_gain']:.4f}")
        show(node["left_child"], pad + "  "); show(node["right_child"], pad + "  ")
    else:   # LightGBM folds F0 into the first tree's leaves: value = F0 + lr * w
        print(f"{pad}leaf  raw {node['leaf_value']:.4f}   rows {node['leaf_count']}")

show(one.booster_.dump_model()["tree_info"][0]["tree_structure"])
print("p(13 pages) =", one.predict_proba([[13.0]])[0, 1].round(4))

ten = lgb.LGBMClassifier(n_estimators=10, **params).fit(pages, bought)
p = ten.predict_proba(pages)[:, 1]
print("after 10 rounds p =", p.round(4))
print("|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
pages <= 10.0   gain 3.0857
  leaf  raw -0.6450   rows 6
  pages <= 15.0   gain 2.7429
    leaf  raw 0.3835   rows 3
    leaf  raw -0.4393   rows 3
p(13 pages) = 0.5947
after 10 rounds p = [0.0359 0.0359 0.0359 0.3579 0.3579 0.3579 0.9166 0.9166 0.9166 0.3582
 0.3582 0.3582]
|g| = [0.0359 0.0359 0.0359 0.3579 0.6421 0.3579 0.0834 0.0834 0.0834 0.3582
 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.

> **Defaults are tuned for big data:** `min_child_samples = 20` means a 12-row dataset cannot split at all, and `max_bin = 255` with fewer distinct values just uses one bin per value. On small data you must lower `min_child_samples` — and on small data a single well-regularized model (or *Random forests*) often does as well. LightGBM's advantage is speed at scale, not magic accuracy.

> **Early stopping needs a separate validation set:** Pass `eval_set=[(X_val, y_val)]` and `callbacks=[lgb.early_stopping(100)]`, then report performance on a *third* held-out test set. Using the test set for early stopping leaks it into model selection. Also: the predicted probabilities of a boosted model are usually well calibrated on log-loss, but class weighting (`is_unbalance`) distorts them — recalibrate if you need true probabilities.

**Strengths**

- 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.

**Limitations**

- 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).

- **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.

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

- A. g = −0.8, h = 0.16
- B. g = 0.8, h = 0.16
- C. g = 0.8, h = 0.64
- D. g = 0.2, h = 0.16

**Answer:** B. g = 0.8, h = 0.16 — $g=p-y=0.8$ (positive: the score should go down) and $h=p(1-p)=0.8\times0.2=0.16$.

**Question:** 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?

- A. gain 8.17, w = 2 and −1.5
- B. gain 4.75, w = 1 and −1
- C. gain 2.375, w = −1 and 1
- D. gain 4.75, w = −1 and 1

**Answer:** B. gain 4.75, w = 1 and −1 — $\frac{4}{2}+\frac{9}{3}-\frac{1}{4}=2+3-0.25=4.75$; $w_L=-(-2)/(1+1)=1$, $w_R=-3/(2+1)=-1$. Without λ the gain would be 8.17 — the penalty discounts leaves with small hessian.

**Question:** 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?

- A. 100,000 rows, weight 1
- B. 300,000 rows, weight 8
- C. 300,000 rows, weight 10
- D. 200,000 rows, weight 0.8

**Answer:** B. 300,000 rows, weight 8 — $0.2\cdot10^6+0.1\cdot10^6=300{,}000$ rows. The 100,000 sampled rows stand for the 800,000 small-gradient rows, so each gets weight $(1-a)/b=0.8/0.1=8$.

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

- A. Builds both from their rows: 10,000 row visits
- B. Builds the 2,000-row child from its rows, and the other as parent − child: 2,000 row visits
- C. Builds the 8,000-row child, then subtracts: 8,000 row visits
- D. Re-sorts the parent's rows by every feature

**Answer:** B. Builds the 2,000-row child from its rows, and the other as parent − child: 2,000 row visits — Each row lands in exactly one child, so per bin parent = left + right. Building the smaller child and subtracting from the cached parent histogram costs O(bins) instead of 8,000 row visits.

**Key points**

- For classification each tree is a Newton step on log-loss: $g=p-y$, $h=p(1-p)$, leaf weight $w=-G/(H+\lambda)$, split gain $\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 $\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
