XGBoost

Материал из MachineLearning.

Версия от 20:57, 4 июля 2026; Nikita Saveliuk (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Статья написана с использованием LLM Claude Opus 4.8 и проверена участником Nikita Saveliuk 00:57, 5 июля 2026 (MSD)


Содержание

XGBoost (от англ. eXtreme Gradient Boosting) — это масштабируемая реализация градиентного бустинга над решающими деревьями, объединяющая регуляризованную целевую функцию, разложение потерь второго порядка и набор инженерных приёмов для эффективной работы на больших и разреженных данных. Метод предложен Тяньци Ченом и Карлосом Гестрином в 2016 году и на протяжении нескольких лет оставался фактическим стандартом для задач обучения на табличных данных, регулярно принося победы в соревнованиях по машинному обучению (Chen, Guestrin, 2016).

Ключевое отличие XGBoost от классического градиентного бустинга Фридмана состоит в том, что каждое очередное дерево строится не по одному лишь градиенту функции потерь, а по её локальному квадратичному приближению — с учётом второй производной. Это даёт более точный шаг оптимизации на каждой итерации и, что важнее, позволяет вывести замкнутую формулу для оптимальных весов листьев и единую метрику качества структуры дерева. Регуляризация здесь встроена прямо в целевую функцию, а не добавляется постфактум, поэтому контроль сложности модели становится частью самого критерия расщепления.

Значимость XGBoost выходит за пределы конкретной библиотеки: сформулированный в ней подход — регуляризованный бустинг со вторым порядком и аппроксимированным поиском расщеплений — задал шаблон, который затем развивали LightGBM (Ke et al., 2017) и CatBoost (Prokhorenkova et al., 2018). Понимание XGBoost поэтому необходимо для осмысленного выбора между современными реализациями градиентного бустинга.

Историческая справка

Идея бустинга — последовательного построения ансамбля слабых моделей, каждая из которых исправляет ошибки предыдущих, — восходит к работам Шапире и Фройнда конца 1990-х годов (AdaBoost). Обобщение бустинга как градиентного спуска в пространстве функций дал Джером Фридман в 2001 году, введя Gradient Boosting Machine (GBM): очередная базовая модель приближает антиградиент функции потерь на текущих предсказаниях ансамбля.

К середине 2010-х градиентный бустинг над деревьями стал одним из самых результативных методов для табличных данных, однако существующие реализации плохо масштабировались: при большом числе объектов и признаков поиск оптимальных расщеплений требовал многократного прохода по всем данным. XGBoost, представленный Ченом и Гестрином на конференции KDD 2016 года, решал именно эту проблему. Авторы предложили не столько новую математическую модель, сколько цельную систему: регуляризованную постановку с разложением второго порядка, аппроксимированный алгоритм поиска расщеплений на основе взвешенного квантильного эскиза, учёт разреженности данных и низкоуровневые оптимизации доступа к памяти. Совокупность этих приёмов позволила обучать модели на миллиардах примеров при существенно меньших вычислительных ресурсах, чем у аналогов.

Библиотека быстро стала стандартом де-факто в прикладном ML и на платформах вроде Kaggle. Последовавшие LightGBM и CatBoost переняли базовую идеологию XGBoost, оптимизируя отдельные её компоненты — стратегию роста дерева, обработку категориальных признаков и борьбу со смещением предсказаний.

Постановка задачи

Рассматривается обучающая выборка из n объектов с признаковыми описаниями x_i \in \mathbb{R}^{m} и целевыми значениями y_i. Модель XGBoost — аддитивный ансамбль из K решающих деревьев:

\hat{y}_i = \sum_{k=1}^{K} f_k(x_i),

где каждое f_k принадлежит пространству регрессионных деревьев. Дерево задаётся структурой, которая относит объект к одному из T листьев, и вектором весов листьев w \in \mathbb{R}^{T}; предсказание дерева на объекте x равно весу того листа, в который этот объект попадает.

Отличие постановки XGBoost от обычного бустинга — в форме оптимизируемого функционала. Минимизируется регуляризованная целевая функция:

\mathcal{L} = \sum_{i=1}^{n} \ell(y_i,\, \hat{y}_i) + \sum_{k=1}^{K} \Omega(f_k),

где \ell — дифференцируемая выпуклая функция потерь, измеряющая расхождение предсказания и цели, а \Omega — штраф за сложность отдельного дерева:

\Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^{2},

Здесь T — число листьев дерева, w_j — вес j-го листа, \gamma штрафует за количество листьев (управляет обрезкой дерева), \lambda задаёт L_2-регуляризацию весов. Именно наличие \Omega внутри критерия отличает XGBoost: сложность модели ограничивается не эвристиками пост-обрезки, а самой оптимизируемой функцией.

Алгоритм

Ансамбль строится жадно и аддитивно: на итерации t к уже накопленному предсказанию добавляется одно новое дерево f_t, минимизирующее целевую функцию при фиксированных предыдущих деревьях.

Разложение второго порядка

Обозначим \hat{y}_i^{(t-1)} предсказание ансамбля после t-1 итераций. Целевая функция на шаге t равна:

\mathcal{L}^{(t)} = \sum_{i=1}^{n} \ell\bigl(y_i,\, \hat{y}_i^{(t-1)} + f_t(x_i)\bigr) + \Omega(f_t),

Раскладывая потери в ряд Тейлора до второго порядка по приращению f_t(x_i), получаем:

\mathcal{L}^{(t)} \simeq \sum_{i=1}^{n} \Bigl[ \ell\bigl(y_i,\, \hat{y}_i^{(t-1)}\bigr) + g_i\, f_t(x_i) + \frac{1}{2} h_i\, f_t^{2}(x_i) \Bigr] + \Omega(f_t),

где g_i и h_i — первая и вторая производные потерь по текущему предсказанию:

g_i = \partial_{\hat{y}^{(t-1)}}\, \ell\bigl(y_i,\, \hat{y}_i^{(t-1)}\bigr), \qquad h_i = \partial^{2}_{\hat{y}^{(t-1)}}\, \ell\bigl(y_i,\, \hat{y}_i^{(t-1)}\bigr),

Величины g_i (градиент) и h_i (гессиан) вычисляются один раз в начале итерации и полностью описывают вклад каждого объекта. Слагаемое \ell(y_i, \hat{y}_i^{(t-1)}) не зависит от f_t и как константа отбрасывается. В отличие от GBM Фридмана, использующего только первый порядок, здесь учитывается кривизна потерь, что делает шаг оптимизации ближе к ньютоновскому.

Оптимальные веса листьев и оценка структуры

Структура дерева задаётся функцией q, относящей каждый объект к индексу листа. Обозначим через I_j множество объектов, попавших в лист j, то есть тех, для которых q(x_i) = j:

I_j = \{\, i \mid q(x_i) = j \,\},

Поскольку все объекты одного листа получают один и тот же вес w_j, упрощённую целевую функцию (без константы) можно сгруппировать по листьям:

\tilde{\mathcal{L}}^{(t)} = \sum_{j=1}^{T} \Bigl[ G_j\, w_j + \frac{1}{2}(H_j + \lambda)\, w_j^{2} \Bigr] + \gamma T,

где введены суммарный градиент и суммарный гессиан листа:

G_j = \sum_{i \in I_j} g_i, \qquad H_j = \sum_{i \in I_j} h_i,

При фиксированной структуре дерева каждое слагаемое — парабола по w_j. Приравнивая производную к нулю, находим оптимальный вес листа:

w_j^{*} = -\frac{G_j}{H_j + \lambda},

Подставляя w_j^{*} обратно, получаем оптимальное значение целевой функции для данной структуры:

\tilde{\mathcal{L}}^{(t)}(q) = -\frac{1}{2} \sum_{j=1}^{T} \frac{G_j^{2}}{H_j + \lambda} + \gamma T,

Эта величина играет роль оценки качества структуры (structure score): чем она меньше, тем лучше дерево. Она аналогична индексу неоднородности для обычных деревьев, но выведена напрямую из функции потерь и регуляризации, а не постулирована. Знаменатель H_j + \lambda показывает роль L_2-регуляризации: она сглаживает веса листьев с малым суммарным гессианом, не давая модели переобучаться на малочисленных листьях.

Критерий расщепления

Перебирать все возможные структуры дерева невозможно, поэтому дерево наращивается жадно: начиная с одного листа, на каждом шаге лист расщепляется, если это уменьшает целевую функцию. Выигрыш от расщепления листа на левую (L) и правую (R) части выводится как разность структурных оценок до и после:

\mathrm{Gain} = \frac{1}{2}\left[ \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} \right] - \gamma,

Первые два слагаемых в скобках — вклад дочерних листьев, третье — вклад исходного листа до расщепления. Параметр \gamma вычитается как порог: расщепление принимается, только если выигрыш превосходит стоимость добавления нового листа. Это встроенный механизм обрезки: при \mathrm{Gain} < 0 расщепление отвергается.

Точный и аппроксимированный поиск расщеплений

Точный жадный алгоритм (exact greedy) перебирает все возможные пороги по всем признакам: для каждого признака объекты сортируются, и величина \mathrm{Gain} пересчитывается для каждой возможной точки разбиения. Это гарантирует нахождение наилучшего расщепления, но требует хранить данные в памяти отсортированными и плохо масштабируется.

Аппроксимированный алгоритм рассматривает не все пороги, а лишь набор кандидатов — квантили распределения значений признака. Кандидаты можно предлагать один раз на всё дерево (глобальный вариант) или заново на каждом расщеплении (локальный, более точный, но более затратный). Между кандидатами объекты агрегируются в гистограммы сумм G_j и H_j, что резко сокращает число вычислений \mathrm{Gain}.

Взвешенный квантильный эскиз. Неочевидный, но принципиальный момент: квантили для кандидатов берутся не по равному числу объектов, а с весами h_i. Обоснование следует из переписывания упрощённой цели в виде взвешенной квадратичной ошибки. Выделяя полный квадрат:

\sum_{i=1}^{n} \Bigl[ g_i\, f_t(x_i) + \frac{1}{2} h_i\, f_t^{2}(x_i) \Bigr] = \sum_{i=1}^{n} \frac{1}{2} h_i \bigl( f_t(x_i) + g_i / h_i \bigr)^{2} + \mathrm{const},

Правая часть — это взвешенная квадратичная ошибка с «псевдо-метками» -g_i / h_i и весами h_i. Значит, каждый объект вносит в задачу вклад, пропорциональный своей второй производной, и разбивать диапазон признака на кандидаты нужно так, чтобы суммарный вес h_i между соседними кандидатами был примерно одинаков. Для этого авторы построили специальную структуру данных — взвешенный квантильный эскиз с гарантией точности, работающий в распределённой среде. Именно эта деталь связывает второй порядок разложения не только с весами листьев, но и с самим выбором точек расщепления.

Учёт разреженности

Реальные данные часто разрежены: пропуски, нулевые значения, признаки после one-hot-кодирования. XGBoost вводит для каждого узла направление по умолчанию: объекты с отсутствующим значением признака автоматически отправляются в одну из ветвей. Само это направление выбирается из данных — перебираются оба варианта, и берётся тот, что даёт больший \mathrm{Gain}. При этом в переборе участвуют только объекты с наличествующими значениями, поэтому сложность поиска расщепления пропорциональна числу непропущенных значений, а не всех объектов. Этот приём (sparsity-aware split finding) даёт многократное ускорение на разреженных матрицах.

Регуляризация и защита от переобучения

Помимо \gamma и \lambda в целевой функции, XGBoost использует два приёма, заимствованных из смежных методов. Усадка (shrinkage): вклад каждого нового дерева умножается на коэффициент скорости обучения \eta:

\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + \eta\, f_t(x_i),

Малое \eta оставляет «пространство» для последующих деревьев и снижает переобучение ценой большего числа итераций. Подвыборка признаков (column subsampling), позаимствованная у случайного леса, при построении каждого дерева использует случайное подмножество столбцов; это ускоряет обучение и дополнительно снижает корреляцию деревьев.

Свойства

Преимущества

  • Регуляризация встроена в целевую функцию, а не добавляется эвристически, что даёт систематический контроль сложности модели.
  • Разложение второго порядка использует кривизну потерь и приближает ньютоновский шаг, обеспечивая быструю и устойчивую сходимость.
  • Поддерживает произвольную дважды дифференцируемую функцию потерь — достаточно задать g_i и h_i, что делает метод применимым к регрессии, классификации, ранжированию.
  • Аппроксимированный поиск со взвешенным квантильным эскизом и учётом разреженности обеспечивает масштабирование на миллиарды объектов.
  • Низкоуровневые оптимизации (блочное хранение в сжатом столбцовом формате, кэш-ориентированный доступ, внеоперативные вычисления) дают высокую скорость на практике.

Ограничения

  • Множество гиперпараметров (\eta, глубина, \gamma, \lambda, доли подвыборки и др.), требующих аккуратной настройки.
  • Уровневый рост дерева (по умолчанию) менее эффективен по числу листьев, чем листовой рост LightGBM, на очень больших данных.
  • Исходно категориальные признаки требовали ручного кодирования; нативная поддержка появилась позже и уступает по проработанности CatBoost.
  • Как и всякий бустинг, чувствителен к шуму в целевой переменной и склонен к переобучению при чрезмерном числе итераций без усадки.

Сравнение с LightGBM и CatBoost

Все три метода реализуют один и тот же каркас — регуляризованный градиентный бустинг со вторым порядком, — но расходятся в трёх ключевых компонентах.

Рост дерева. XGBoost по умолчанию наращивает дерево по уровням (level-wise): расщепляются все листья текущего уровня. LightGBM (Ke et al., 2017) использует листовой рост (leaf-wise): расщепляется лист с максимальным выигрышем, что при равном числе листьев даёт меньшую ошибку, но повышает риск переобучения и требует ограничения глубины.

Ускорение поиска расщеплений. LightGBM добавляет две техники. GOSS (Gradient-based One-Side Sampling) отбрасывает часть объектов с малыми градиентами: раз вклад объекта в информационный выигрыш растёт с величиной градиента, объекты с большими градиентами сохраняются полностью, а с малыми — прореживаются случайно. EFB (Exclusive Feature Bundling) объединяет взаимно разреженные признаки в один, сокращая эффективную размерность. XGBoost достигает похожей цели иначе — через взвешенный квантильный эскиз и учёт разреженности.

Категориальные признаки и смещение. CatBoost (Prokhorenkova et al., 2018) сфокусирован на двух проблемах. Упорядоченные целевые статистики кодируют категориальный признак средним значением цели, но вычисленным только по предшествующим в некоторой перестановке объектам — так устраняется утечка целевой переменной. Упорядоченный бустинг (ordered boosting) той же идеей борется со смещением предсказаний, когда градиенты оцениваются на тех же объектах, на которых обучается модель. CatBoost также использует симметричные (oblivious) деревья, где на каждом уровне применяется единое условие расщепления. XGBoost этих механизмов не имеет и полагается на регуляризацию и усадку.

Практический итог: XGBoost — надёжный универсальный выбор со зрелой экосистемой; LightGBM обычно быстрее на очень больших данных; CatBoost выигрывает при обилии категориальных признаков и склонности данных к утечкам. Различия компонентов, а не «магия», объясняют, почему на конкретной задаче один из методов может заметно опережать остальные.

Применение

XGBoost применяется прежде всего там, где данные представлены таблицами «объект — признаки»: кредитный скоринг и оценка рисков, детекция мошеннических транзакций, прогнозирование оттока клиентов, ранжирование в поисковых и рекомендательных системах, прогнозирование спроса и цен. На табличных данных он часто превосходит нейронные сети при меньших затратах на обучение и настройку. Метод также используется как сильный базовый уровень в исследованиях и как компонент ансамблей и стекинга в соревновательном ML.

См. также

Ссылки

Литература

  • Friedman J. H. Greedy Function Approximation: A Gradient Boosting Machine // The Annals of Statistics. — 2001. — Т. 29. — № 5. — С. 1189–1232.
Источник — «http://machinelearning.ru/wiki/index.php?title=XGBoost»
Личные инструменты