Histogram Split Finding (GBM)

Background

Histogram-based GBM (LightGBM, XGBoost's hist mode) bins each feature into a fixed number of bins, then computes per-bin gradient and Hessian sums. Sweeping candidate splits is now $O(\text{bins})$ rather than $O(n)$ — the trick behind LightGBM's speed.

Problem statement

Implement best_split(values, gradients, hessians, n_bins=32, reg_lambda=1.0). Steps:

1. Bin values into n_bins equal-width bins on $[\min, \max]$.
2. Accumulate g_sum[b] and h_sum[b] per bin.
3. For each candidate split (between bin $b$ and $b+1$, with $b \in [0, \text{n\_bins}-2]$), compute:

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

4. Pick the threshold (right edge of bin $b$) that maximises gain.

Input

• values — 1-D np.ndarray of floats, the feature column.
• gradients — 1-D np.ndarray same length, per-row first-order gradients.
• hessians — 1-D np.ndarray same length, per-row second-order Hessians.
• n_bins — int >= 2, histogram resolution.
• reg_lambda — float >= 0, L2 regularisation.

Output

Returns (threshold: float, gain: float). If no positive-gain split exists, return (values.min(), 0.0).

Examples

Example 1 — bimodal separable case → clear positive-gain split

Input:  values bimodal around ±5; gradients of opposite signs per cluster
Output: threshold near 0, gain > 0

Example 2 — all-zero gradients → gain = 0

Input:  gradients all 0
Output: gain == 0.0

Example 3 — degenerate values (lo == hi) → gain = 0

Input:  all values equal
Output: gain == 0.0

Constraints

• Skip splits where one side has zero Hessian (no rows on that side).
• Return Python floats.
• $n\_bins \ge 2$.

Notes

• Why equal-width. Production implementations use quantile bins for skewed features; equal-width is the simpler kernel.
• Categorical features. Categorical splits use a different split-finding routine (best-vs-rest after sorting by target mean) — out of scope here.