Бустинги›LightGBM

LightGBM

Histogram binning ускоряет поиск сплита в сотни раз, а leaf-wise рост дерева исправляет ошибки там, где они максимальны — без лишних разбиений.

Интерактивная визуализация

Наблюдайте как leaf-wise дерево и histogram binning работают на каждом шаге

Задача

РегрессияКлассиф.

Датасет

Деревьев10

Learning rate0.50

Листьев (num_leaves)7

Мин. точек в листе3

Бинов (num_bins)8

Регуляризация λ1.0

Вычисляю...

Шаг 0 / 0

Предсказание F_m(x)

Данные y

Остаток >0

Остаток <0

Числовой пример

Гистограмма бинов и таблица предсказаний для текущего шага.

Нет данных для отображения.

Идея алгоритма

Две фишки, которые делают LightGBM быстрым и точным

Аналогия из жизни

Представь хирурга, который оперирует пациентов по очереди. Обычный врач лечит всех по одному плану: сначала все проходят диагностику, потом все — назначение, потом всем делают операцию одного и того же уровня сложности. Это level-wise: послойно, равномерно.

LightGBM работает как опытный хирург, который смотрит на все случаи сразу и говорит: «Вот этот пациент в критическом состоянии — его оперируем первым, и идём так глубоко, насколько нужно». Это leaf-wise: дерево растёт туда, где ошибка максимальна, а не равномерно во все стороны.

При этом вместо того, чтобы смотреть на каждый случай отдельно (O(N)), хирург пользуется стандартизированной формой осмотра с несколькими категориями симптомов — это аналог гистограммных бинов: O(B) вместо O(N), в сотни раз быстрее.

Ключевые идеи

Histogram Binning

Вместо перебора всех N значений признака ищем лучший порог среди B бинов. Сумма градиентов ΣG и гессианов ΣH накапливаются за O(N), а поиск оптимума — O(B). При N=100 000 и B=256: в 390× меньше работы.

Leaf-wise Growth

Каждый раз выбираем лист с максимальным Gain и разбиваем его. Дерево растёт асимметрично — глубже туда, где ошибка больше. При тех же num_leaves это даёт меньший bias, чем level-wise.

Формула Gain для выбора сплита

Gain = G_L² / (2*(H_L+λ)) + G_R² / (2*(H_R+λ)) − (G_L+G_R)² / (2*(H_L+H_R+λ))

Чем больше Gain — тем лучше сплит. Λ (лямбда) штрафует за слабые разбиения, предотвращая переобучение. Если Gain ≤ 0 — сплит не нужен.

LightGBM vs GBM

Аспект	GBM	LightGBM
Поиск сплита	O(N × F) — перебор всех точек	O(B × F) — по бинам гистограммы
Рост дерева	Level-wise: все листья глубины d	Leaf-wise: лист с max Gain
Параметр глубины	max_depth	num_leaves
Скорость	Базовая	В 10–20× быстрее на больших данных
Память	O(N) для сортировок	O(B) для гистограмм
Риск переобучения	max_depth контролирует	num_leaves без min_data рискованно

Ключевая идея: при одном и том же числе листьев leaf-wise строит более точное дерево, потому что каждый сплит выбирается глобально оптимальным — а не «по расписанию» послойно.

Bias и Variance

LightGBM использует leaf-wise рост: каждое дерево идёт туда, где ошибка наибольшая. Это значит, что bias падает быстро — уже за несколько итераций модель сильно улучшает предсказание на «трудных» точках. Оборотная сторона: variance растёт активнее, чем у level-wise бустинга — асимметричные глубокие деревья легко запоминают шум.

Главный регулятор баланса — параметр num_leaves: он ограничивает сложность дерева вне зависимости от глубины. Плюс min_data_in_leaf и λ (регуляризация) сдерживают variance, штрафуя за слабые сплиты.

Bias падает быстро благодаря leaf-wise агрессии, но variance растёт заметно — у LightGBM есть чёткий оптимум по числу итераций. Используй early stopping.

Параметр	Bias	Variance	Рекомендация
num_leaves ↑	↓ снижает	↑ повышает	Начни с 31, снижай при переобучении
learning_rate ↑	↓ снижает	↑ повышает	Малый lr + больше деревьев
min_data_in_leaf ↑	↑ повышает	↓ снижает	Увеличь при шумных данных
num_bins ↓	↑ повышает	↓ снижает	Меньше бинов — быстрее, но грубее
lambda ↑	↑ повышает	↓ снижает	Явная регуляризация gain

Стартовые параметры: num_leaves=31 + min_data_in_leaf=20 + learning_rate=0.05 + lambda=1.0. Добавь early stopping и дай побольше деревьев — модель сама найдёт оптимум.

Плюсы

✓В 10–20× быстрее GBM на больших датасетах (histogram binning)
✓Меньше памяти: O(B) гистограммы вместо O(N) сортировок
✓Высокая точность благодаря leaf-wise агрессивному поиску
✓Встроенная регуляризация: λ, min_data_in_leaf
✓Поддержка категориальных признаков и sparse данных

Минусы

✗Leaf-wise без min_data_in_leaf быстро переобучается
✗num_leaves менее интуитивен, чем max_depth
✗Чувствителен к шумным признакам при малом num_bins
✗На маленьких датасетах (<10K) GBM может быть точнее

Математика

Откуда берётся gain, зачем гессианы и как работает leaf-wise

Формула gain для выбора сплита:

\text{Gain} = \frac{G_L^2}{2(H_L+\lambda)} + \frac{G_R^2}{2(H_R+\lambda)} - \frac{(G_L+G_R)^2}{2(H_L+H_R+\lambda)}

Оптимальное значение листа:

\omega^*_\ell = -\frac{\sum_{i \in \ell} g_i}{\sum_{i \in \ell} h_i + \lambda}

Правило обновления (как в GBM):

F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)

\text{Gain}

— Насколько этот сплит снижает ошибку относительно несплитнутого листа

G_L, G_R

— Сумма градиентов точек в левом / правом листе после сплита

H_L, H_R

— Сумма гессианов — показывает кривизну ошибки в каждом листе

\lambda

— L2-регуляризация: штрафует за сложные сплиты, снижает переобучение

\omega^*_\ell

— Оптимальное значение листа: минимизирует аппроксимацию потерь

Псевдокод

Вход: данные (x, y), η, M, num_leaves, λ, num_bins
F₀ ← mean(y)# начальная константа
for m = 1 to M:
    gᵢ ← Fᵢ − yᵢ  (или pᵢ − yᵢ)# градиенты
    hᵢ ← 1  (или pᵢ·(1−pᵢ))# гессианы
    Hist ← buildHistogram(x, g, h, num_bins)# бинируем признаки
    T ← {root: все точки}# одно корневое «дерево»
    пока |листья(T)| < num_leaves:
        ℓ* ← argmax_{ℓ} Gain(ℓ, Hist)# лист с max gain
        если Gain(ℓ*) ≤ 0: стоп
        T ← split(T, ℓ*)# разбиваем лучший лист
    для каждого листа ℓ ∈ T:
        ωℓ ← −Σᵢ∈ℓ gᵢ / (Σᵢ∈ℓ hᵢ + λ)# значение листа
    Fₘ(x) ← Fₘ₋₁(x) + η · T(x)# обновляем ансамбль
return FM# финальный ансамбль

Разбор вручную

5 домов, 3 раунда, η=0.5, λ=1, num_bins=3 — считаем каждый шаг.

Шаг 1 — начальная константа. LightGBM (как и GBM) начинает с самого простого предсказания: средним по целевой переменной. Это отправная точка, от которой деревья будут «исправлять» ошибки.

F₀ = mean(y) = (10 + 20 + 35 + 30 + 40) / 5 = 135 / 5 = 27

Шаг 2 — гистограмма бинов. Диапазон x: [20, 100]. С num_bins=3 ширина бина ≈ 26.7. Каждая точка данных «укладывается» в свой бин — это и есть дискретизация признака.

Бин 0: x ∈ [20.0, 46.7) → точки 1, 2
Бин 1: x ∈ [46.7, 73.3) → точка 3
Бин 2: x ∈ [73.3, 100] → точки 4, 5

На реальных данных с N=100 000 и num_bins=256 это экономит ~390× вычислений при поиске сплита.

i	x (м²)	y (цена)	F₀
1	20	10	27
2	40	20	27
3	60	35	27
4	80	30	27
5	100	40	27

MSE₀ = [(10−27)² + (20−27)² + (35−27)² + (30−27)² + (40−27)²] / 5
= [289 + 49 + 64 + 9 + 169] / 5 = 116

Итог

Что важно запомнить

Ключевые выводы

1Histogram binning переводит поиск сплита из O(N) в O(B) — при N=100K и B=256 это ускорение в ~400×
2Leaf-wise growth исправляет ошибки там, где они максимальны: каждый сплит выбирается глобально оптимальным
3num_leaves — главный параметр вместо max_depth: он ограничивает сложность дерева напрямую
4λ (регуляризация) и min_data_in_leaf защищают от переобучения: без них leaf-wise быстро запоминает шум
5На маленьких датасетах (<10K строк) преимущества скорости нивелируются — GBM может быть точнее

Когда использовать LightGBM

Ситуация	Рекомендация
Большой датасет (>100K строк)	✅ LightGBM — в разы быстрее GBM
Нужна точность на табличных данных	✅ Leaf-wise даёт высокую точность
Маленький датасет (<10K)	⚠️ Риск переобучения, нужны num_leaves↓
Интерпретируемость модели	❌ Деревья асимметричны, сложнее читать

AdaBoost CatBoost