Алгоритм LightGBM: быстрый градиентный бустинг

Алгоритм LightGBM (Light Gradient Boosting Machine) - это реализация градиентного бустинга над деревьями решений от Microsoft, которая обучается в разы быстрее классических бустингов на больших табличных данных и почти не уступает им в точности. Идея бустинга та же, что у XGBoost: деревья строятся последовательно, и каждое новое исправляет ошибки уже собранного ансамбля. Но LightGBM меняет три инженерных решения - как растить дерево, как искать разбиения и как отбирать данные, - и за счёт этого выигрывает по скорости и памяти. Ниже разберём рост по листьям, гистограммы признаков, GOSS и EFB, настройку num_leaves и learning rate и борьбу с переобучением. Чтобы сразу почувствовать, как число листьев влияет на ошибку, - покрути калькулятор ниже.

Что такое LightGBM и в чём его идея

LightGBM собирает прогноз как сумму вкладов всех деревьев - это обычная аддитивная модель градиентного бустинга:

$$\hat{y}_i = \sum_{m=1}^{M} \eta\, f_m(x_i),$$

где $f_m$ - $m$-е дерево, $\eta$ - learning rate (шаг бустинга), а $M$ - число деревьев. До сюда всё совпадает с любым бустингом. Отличие LightGBM не в формуле ансамбля, а в трёх ускоряющих приёмах: дерево растёт по листьям (leaf-wise), разбиения ищутся по гистограммам признаков, а объекты и признаки прореживаются методами GOSS и EFB. Вместе они дают тот самый «light» - лёгкость по времени и памяти на данных в миллионы строк, где XGBoost заметно медленнее.

Рост по листьям против роста по уровням

Главное концептуальное отличие LightGBM - стратегия выращивания дерева. Классический бустинг растит дерево по уровням (level-wise): расщепляет сразу все узлы текущего уровня, дерево остаётся сбалансированным. LightGBM растит по листьям (leaf-wise): на каждом шаге он находит один лист, разбиение которого даёт максимальное уменьшение потерь, и расщепляет именно его. Дерево получается несимметричным - одна ветка может уйти глубоко, пока другие остаются короткими.

Leaf-wise при том же числе разбиений снижает потери сильнее, потому что не тратит расщепления на бесполезные узлы. Но у этого есть цена: глубокая ветка легко переобучается. Поэтому в LightGBM сложность модели контролирует не глубина, а число листьев num_leaves - это центральный параметр. Эмпирическое правило: $\text{num\_leaves} < 2^{\text{max\_depth}}$, иначе дерево станет глубоким и начнёт запоминать шум.

Гистограммы признаков и поиск разбиений

Чтобы найти лучшее разбиение, бустинг перебирает признаки и пороги. Точный перебор всех уникальных значений признака дорог. LightGBM вместо этого заранее раскладывает непрерывные значения каждого признака по небольшому числу бинов (по умолчанию max_bin = 255) и строит гистограмму. Поиск порога идёт уже по бинам, а не по всем значениям.

Рассчитать для своей задачи

Сложность поиска разбиения падает с числа объектов до числа бинов, а гистограмму дочернего узла можно получить вычитанием: гистограмма меньшего ребёнка считается напрямую, а большего - как разность родительской и меньшего. Это и есть основной источник ускорения. Биннинг заодно экономит память (значения хранятся как индексы бинов) и слегка регуляризует модель, сглаживая шумные пороги.

GOSS - отбор объектов по градиенту

Второй приём ускорения - GOSS (Gradient-based One-Side Sampling). Градиент $g_i$ объекта показывает, насколько модель на нём ещё ошибается: объекты с большим градиентом «недоучены» и важны для следующего дерева, с малым - уже хорошо предсказаны. GOSS оставляет все объекты с большими градиентами и случайно подвыбирает только часть объектов с малыми, компенсируя это весовым множителем при подсчёте выигрыша от разбиения.

Рассчитать для своей задачи

Так дерево учится на меньшей выборке, не теряя информацию о «трудных» объектах. Третий приём - EFB (Exclusive Feature Bundling): разреженные признаки, которые почти никогда не бывают ненулевыми одновременно (например one-hot-кодировка), связываются в один признак-пучок. Это уменьшает фактическое число признаков и ускоряет построение гистограмм без потери информации.

Настройка num_leaves и learning rate

Скорость обучения $\eta$ и число листьев работают в связке. Маленький $\eta$ (0,01-0,05) делает шаги осторожными: ошибка падает медленнее, зато модель устойчивее, но нужно больше деревьев. Большой $\eta$ быстро снижает ошибку обучения, но рискует переобучиться. Снижение ошибки приближённо описывается законом насыщения:

$$\mathcal{L} \approx \mathcal{L}_{\min} + (\mathcal{L}_0 - \mathcal{L}_{\min})\, e^{-c\,\eta\, M},$$

где $\mathcal{L}_0$ - стартовая ошибка, $\mathcal{L}_{\min}$ - неустранимый «пол» (шум данных), а $c$ - эффективность одного шага. Из формулы видно правило: уменьшив learning rate, нужно пропорционально увеличить число деревьев, чтобы дойти до того же качества. На практике фиксируют небольшой $\eta$ и подбирают число деревьев ранней остановкой, а num_leaves настраивают как главный рычаг выразительности - именно его перебор показывает калькулятор выше.

Переобучение и ранняя остановка

Ошибка обучения у бустинга падает почти до нуля всегда, поэтому ориентироваться на неё нельзя. О переобучении говорит только ошибка на отложенной (валидационной) выборке: она сначала падает вместе с обучающей, затем выходит на минимум и растёт. Стандартный приём - ранняя остановка (early_stopping_rounds): обучение прекращается, если валидационная метрика не улучшается заданное число итераций подряд, и берётся модель на лучшей итерации.

Из-за leaf-wise роста LightGBM переобучается легче XGBoost, поэтому регуляризацию задают явно: уменьшают num_leaves, увеличивают min_data_in_leaf (минимум объектов в листе - не даёт расщеплять до отдельных примеров), ограничивают max_depth, добавляют L1/L2-штрафы (lambda_l1, lambda_l2) и подвыборку строк (bagging_fraction) и столбцов (feature_fraction).

Где LightGBM силён, а где нет

LightGBM - почти стандартный выбор для больших табличных данных: миллионы строк, смешанные числовые и категориальные признаки (категории он умеет обрабатывать нативно, без one-hot, через специальный поиск разбиения по категориям). На таких объёмах он обучается быстрее XGBoost и экономнее по памяти. На маленьких выборках его скоростное преимущество исчезает, а склонность к переобучению из-за leaf-wise роста становится заметнее - там осторожнее подходит CatBoost с упорядоченным бустингом. На изображениях, звуке и тексте, где важна пространственная или последовательная структура, деревья в принципе проигрывают нейросетям - ниша всех трёх библиотек именно табличные данные.

Частые ошибки

• Крутят max_depth вместо num_leaves. При leaf-wise росте сложность задаёт число листьев, а не глубина. Главный рычаг против переобучения - уменьшить num_leaves и поднять min_data_in_leaf, а не просто ограничить глубину.
• Ставят num_leaves слишком большим. Если num_leaves близко к $2^{\text{max\_depth}}$ или больше, дерево становится глубоким и запоминает шум. Держите num_leaves заметно меньше этого предела.
• Ориентируются на ошибку обучения. Она падает почти до нуля всегда; о переобучении говорит только рост ошибки на валидации. Нужна ранняя остановка по отложенной выборке.
• Кодируют категории через one-hot вручную. LightGBM обрабатывает категориальные признаки нативно (параметр categorical_feature) - ручной one-hot обычно хуже и медленнее, чем встроенный поиск разбиения по категориям.
• Считают LightGBM универсальным. На картинках и тексте он почти всегда проигрывает нейросетям, а на маленьких данных переобучается - его ниша именно большие табличные выборки.

FAQ

Чем LightGBM отличается от XGBoost? Тремя инженерными решениями. LightGBM растит дерево по листьям (leaf-wise), а классический XGBoost - по уровням; LightGBM ищет разбиения по гистограммам бинов, прореживает объекты методом GOSS и связывает разреженные признаки через EFB. За счёт этого он обучается быстрее и экономнее по памяти на больших данных, но из-за leaf-wise роста чуть легче переобучается.

Что важнее настраивать - num_leaves или learning rate? Их подбирают в связке, но при leaf-wise росте именно num_leaves задаёт выразительность модели и сильнее всего влияет на переобучение. Learning rate обычно фиксируют небольшим, а число деревьев определяют ранней остановкой; num_leaves и min_data_in_leaf настраивают по валидации как главную пару против переобучения.

Нужно ли масштабировать признаки для LightGBM? Нет. Деревья делят пространство по порогам и инвариантны к монотонным преобразованиям признаков, поэтому стандартизация и нормировка не нужны. Категориальные признаки кодировать вручную тоже не обязательно - LightGBM обрабатывает их нативно.

Коротко

LightGBM - это градиентный бустинг над деревьями с тремя ускорениями: рост по листьям (leaf-wise) вместо роста по уровням, поиск разбиений по гистограммам бинов и прореживание данных через GOSS и EFB. Главный рычаг сложности - num_leaves, а не глубина; learning rate и число деревьев настраиваются в связке, переобучение сдерживают num_leaves, min_data_in_leaf и ранней остановкой. Сильная сторона - большие табличные данные, где он обгоняет XGBoost по скорости; на маленьких выборках осторожнее подходит CatBoost, а на картинках и тексте выигрывают нейросети.