LightGBM
Материал из MachineLearning.
| Статья написана с использованием LLM Claude и проверена участником Nikita Saveliuk 01:07, 5 июля 2026 (MSD) |
|
LightGBM (от англ. Light Gradient Boosting Machine) — это реализация градиентного бустинга над решающими деревьями, оптимизированная для высокоразмерных данных большого объёма. Библиотека предложена группой исследователей Microsoft под руководством Голина Кэ в 2017 году и построена вокруг двух оригинальных приёмов — одностороннего градиентного сэмплирования (GOSS) и связывания взаимоисключающих признаков (EFB), — которые сокращают вычислительную стоимость поиска расщеплений, почти не жертвуя точностью.
В основе LightGBM лежит тот же каркас, что и у XGBoost: аддитивный ансамбль деревьев, обучаемый по градиентам функции потерь. Отличие — не в математической модели, а в том, как метод борется с главным узким местом бустинга над деревьями. Чтобы найти оптимальное расщепление, классические реализации перебирают все точки разбиения по всем признакам, а значит, на каждой итерации сканируют все объекты для каждого признака. При большом числе объектов и признаков это доминирующая по времени операция. GOSS сокращает число объектов, участвующих в оценке выигрыша, а EFB — число признаков; вместе они дают ускорение обучения в разы при сопоставимом качестве (Ke et al., 2017).
Понимание LightGBM полезно на фоне соседних реализаций: он развивает идеи XGBoost (Chen, Guestrin, 2016), заменяя точный и приближённый перебор гистограммным поиском с сэмплированием, тогда как CatBoost (Prokhorenkova et al., 2018) фокусируется на другой проблеме — смещении предсказаний и обработке категориальных признаков. Выбор между тремя методами почти всегда сводится к тому, какой из различающихся компонентов важнее для конкретной задачи.
Историческая справка
Градиентный бустинг над деревьями, восходящий к Gradient Boosting Machine Джерома Фридмана (2001), к середине 2010-х стал ведущим методом для табличных данных. Реализация XGBoost (2016) впервые сделала его по-настоящему масштабируемым за счёт регуляризованной постановки, разложения потерь второго порядка и аппроксимированного поиска расщеплений через взвешенный квантильный эскиз.
Однако и у аппроксимированного поиска оставался предел: для оценки информационного выигрыша по каждому признаку всё равно требовалось агрегировать все объекты. При высокой размерности и больших выборках это оставалось дорого. LightGBM, представленный Кэ и соавторами на конференции NeurIPS 2017 года, атаковал именно эти два множителя стоимости — число объектов и число признаков. Авторы заметили, что объекты вносят в выигрыш неодинаковый вклад (он тем больше, чем больше градиент), а признаки в разреженных данных часто взаимно исключают друг друга. Отсюда два приёма: GOSS прореживает объекты с малыми градиентами, EFB связывает разреженные признаки в один. Дополнительно LightGBM по умолчанию использует гистограммное представление признаков и листовую стратегию роста дерева.
Результатом стало ускорение обучения по сравнению с прежними реализациями GBDT при почти неизменной точности. LightGBM быстро вошёл в стандартный инструментарий прикладного ML наряду с XGBoost и последовавшим CatBoost.
Постановка задачи
Рассматривается обучающая выборка из объектов с признаковыми описаниями
и целевыми значениями
. Как и в общем градиентном бустинге, строится аддитивный ансамбль деревьев, минимизирующий суммарную функцию потерь; на каждой итерации к ансамблю добавляется дерево, приближающее антиградиент потерь на текущих предсказаниях. Обозначим через
градиент функции потерь по предсказанию на объекте
.
Специфика LightGBM — в том, что оптимизируется не модель, а стоимость её обучения. Ключевая операция при построении дерева — выбор расщепления по критерию выигрыша дисперсии. Для узла с множеством объектов , признака
и точки разбиения
выигрыш определяется как:
,
где — число объектов в узле, а
и
— числа объектов, уходящих в левую и правую ветви при разбиении признака
по порогу
. Вычисление этого выражения для всех
и всех
требует прохода по всем объектам и признакам. Стоимость такого прохода пропорциональна произведению числа объектов на число признаков — именно эти два множителя LightGBM и стремится уменьшить.
Алгоритм
Гистограммный поиск расщеплений
Вместо перебора всех отсортированных значений признака LightGBM дискретизирует каждый непрерывный признак в фиксированное число корзин (бинов, по умолчанию 255). Для узла строится гистограмма — сумма градиентов объектов, попавших в каждый бин; выигрыш перебирается по границам бинов, а не по всем значениям. Это даёт два преимущества: значение признака хранится как индекс бина (один байт) вместо числа с плавающей точкой, а стоимость поиска расщепления в узле пропорциональна числу бинов, а не числу объектов.
Вычитание гистограмм. Неочевидная, но важная оптимизация: гистограмма родительского узла равна сумме гистограмм его дочерних узлов. Поэтому достаточно построить гистограмму только для того дочернего узла, в котором меньше объектов, а гистограмму второго получить вычитанием из родительской. Это вдвое сокращает число построений гистограмм на каждом уровне дерева.
Gradient-based One-Side Sampling (GOSS)
Идея GOSS исходит из наблюдения: объекты с малым по модулю градиентом уже хорошо приближены моделью и слабо влияют на информационный выигрыш, тогда как объекты с большим градиентом определяют выбор расщепления. Наивно отбросить объекты с малыми градиентами нельзя — это изменит распределение данных и сместит оценку выигрыша.
GOSS решает это так. Объекты сортируются по убыванию модуля градиента. Верхняя доля объектов с наибольшими градиентами сохраняется полностью (множество
). Из оставшихся случайно выбирается доля
(множество
). При оценке выигрыша вклад сэмплированных объектов из
домножается на коэффициент
, восстанавливающий их исходный «вес» в полной выборке. Оценка выигрыша принимает вид:
,
где и
— части множеств
и
, уходящие в левую и правую ветви. Смысл коэффициента
прямой: доля
малоградиентных объектов представлена в оценке лишь долей
из них, поэтому их суммарный градиент масштабируется в
раз. Именно эта нормировка удерживает оценку выигрыша приблизительно несмещённой, несмотря на отброс большинства малоградиентных объектов; авторы доказывают, что ошибка аппроксимации при этом ограничена и убывает с ростом выборки.
Exclusive Feature Bundling (EFB)
В высокоразмерных разреженных данных многие признаки взаимно исключающи — почти никогда не принимают ненулевые значения одновременно (типичный источник — one-hot-кодирование категорий). Такие признаки можно объединить в один «бандл» без потери информации, сократив эффективное число признаков.
EFB состоит из двух подзадач. Первая — какие признаки связывать. Она сводится к раскраске графа, где вершины суть признаки, а рёбра соединяют конфликтующие (часто одновременно ненулевые) признаки; задача NP-трудна, поэтому применяется жадная эвристика, допускающая малую долю конфликтов. Вторая — как слить признаки в один. Диапазоны значений разных признаков разводятся смещениями так, чтобы не пересекаться: например, если первый признак лежит в диапазоне , а второй — в
, ко второму добавляется смещение
, и его значения занимают
. По итоговому значению бандла однозначно восстанавливается, какой признак был ненулевым. За счёт EFB стоимость построения гистограмм падает с порядка «число объектов на число признаков» до «число объектов на число бандлов».
Листовой рост дерева
LightGBM по умолчанию наращивает дерево листовым способом (leaf-wise): на каждом шаге расщепляется тот лист среди всех текущих, который даёт наибольший выигрыш. Это отличается от уровневого роста (level-wise) XGBoost, где расщепляются все листья очередного уровня. При равном числе листьев листовой рост достигает меньшей ошибки, поскольку «тратит» расщепления там, где они полезнее всего, но строит более глубокие несимметричные деревья и потому сильнее склонен к переобучению. Контролируется это ограничениями на число листьев и максимальную глубину.
Свойства
Преимущества
- Высокая скорость обучения и низкое потребление памяти за счёт гистограммного представления, GOSS и EFB.
- Хорошая масштабируемость на данные с большим числом объектов и признаков, включая разреженные.
- Листовой рост даёт меньшую ошибку при фиксированном числе листьев по сравнению с уровневым.
- Оптимизация вычитанием гистограмм вдвое сокращает построение гистограмм на каждом уровне.
- Поддержка категориальных признаков без явного one-hot-кодирования, параллельного и GPU-обучения.
Ограничения
- Листовой рост при недостаточной регуляризации легко переобучается, особенно на малых выборках.
- Гистограммная дискретизация огрубляет пороги расщепления, что на небольших данных может немного снижать точность.
- Чувствительность к числу листьев, размеру бинов и параметрам GOSS требует аккуратной настройки.
- Как всякий бустинг, чувствителен к шуму в целевой переменной.
Сравнение с XGBoost и CatBoost
Все три метода реализуют регуляризованный градиентный бустинг над деревьями и различаются в нескольких компонентах.
Против XGBoost. XGBoost (Chen, Guestrin, 2016) использует уровневый рост и аппроксимированный поиск расщеплений со взвешенным квантильным эскизом, опираясь на разложение потерь второго порядка. LightGBM заменяет это листовым ростом и гистограммным поиском, а число объектов и признаков в оценке выигрыша сокращает через GOSS и EFB. На практике LightGBM обычно быстрее и экономнее по памяти на очень больших и высокоразмерных данных, тогда как XGBoost нередко устойчивее на малых выборках. Стоит отметить, что современные версии XGBoost также поддерживают гистограммный режим, так что разрыв в скорости сократился.
Против CatBoost. CatBoost (Prokhorenkova et al., 2018) решает иную проблему — смещение предсказаний и утечку целевой переменной. Он применяет упорядоченные целевые статистики для категориальных признаков и упорядоченный бустинг (ordered boosting), оценивающий градиенты на объектах, предшествующих текущему в некоторой перестановке, а также симметричные (oblivious) деревья. LightGBM таких механизмов не имеет и полагается на скорость и гистограммную обработку категорий. При обилии категориальных признаков и риске утечек CatBoost обычно точнее «из коробки», тогда как LightGBM выигрывает по скорости на числовых высокоразмерных данных.
Практический итог: LightGBM — выбор по умолчанию, когда критичны скорость и объём данных; XGBoost — зрелый универсальный вариант, надёжный на средних выборках; CatBoost — когда доминируют категориальные признаки. Различие конкретных компонентов, а не общая «сила» метода, объясняет расхождение результатов на данной задаче.
Применение
LightGBM применяется в тех же областях, что и прочий градиентный бустинг над табличными данными, но особенно там, где важны скорость обучения и объём выборки: ранжирование в поисковых и рекомендательных системах, кредитный скоринг, детекция мошенничества, прогнозирование оттока, спроса и кликов в онлайн-рекламе. Благодаря высокой скорости он удобен для частого переобучения моделей на потоковых данных и для перебора гиперпараметров, а также как сильный базовый уровень и компонент ансамблей в соревновательном ML.
См. также
Ссылки
- Ke et al. LightGBM: A Highly Efficient Gradient Boosting Decision Tree (NeurIPS)
- Официальная документация LightGBM
- Репозиторий LightGBM на GitHub
Литература
- Ke G., Meng Q., Finley T., Wang T., Chen W., Ma W., Ye Q., Liu T.-Y. LightGBM: A Highly Efficient Gradient Boosting Decision Tree // Advances in Neural Information Processing Systems (NeurIPS). — 2017. — Т. 30. — С. 3146–3154.
- Chen T., Guestrin C. XGBoost: A Scalable Tree Boosting System // Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '16). — 2016. — С. 785–794.
- Prokhorenkova L., Gusev G., Vorobev A., Dorogush A. V., Gulin A. CatBoost: unbiased boosting with categorical features // Advances in Neural Information Processing Systems (NeurIPS). — 2018. — Т. 31. — С. 6638–6648.
- Friedman J. H. Greedy Function Approximation: A Gradient Boosting Machine // The Annals of Statistics. — 2001. — Т. 29. — № 5. — С. 1189–1232.
