Gradient Boosting 🚀

Открой таблицу лидеров почти любого соревнования по табличным данным на Kaggle — предсказание цены жилья, оттока клиентов, кредитного скоринга, вероятности клика по рекламе — и в решениях призёров почти наверняка встретится одно и то же название модели: XGBoost, LightGBM или CatBoost. Все три — это конкретные промышленные реализации одной и той же идеи, которая по-русски называется «градиентный бустинг» (в тексте дальше используется именно этот перевод). На структурированных, табличных данных градиентный бустинг годами остаётся самым результативным семейством алгоритмов классического машинного обучения, зачастую обгоняя даже нейросети — там, где данные не картинки и не текст, а обычная таблица со строками и столбцами, бустинг чаще всего побеждает.

В предыдущем уроке (317) ты разобрал Random Forest — ансамбль, где сотни деревьев решений (урок 316) строятся независимо друг от друга и затем голосуют или усредняются. Градиентный бустинг — это принципиально другая философия ансамблирования. Вместо параллельного «комитета экспертов», каждый из которых работает в одиночку и не знает о существовании остальных, бустинг строит деревья строго последовательно, одно за другим, и каждое новое дерево целенаправленно занимается тем, с чем не справились предыдущие. Не голосование, а эстафета: первое дерево делает грубый, но быстрый прогноз, второе дерево изучает именно те случаи, где первое ошиблось, третье — то, что не исправило второе, и так далее.

Такая последовательная коррекция ошибок делает градиентный бустинг обычно точнее случайного леса при прочих равных, но у этой точности есть цена: бустинг чувствительнее к настройке гиперпараметров и заметно более склонен к переобучению, если не следить за числом деревьев и скоростью обучения. Сегодняшний урок — последний в блоке классических моделей машинного обучения (уроки 310–318): мы разберём, как деревья исправляют ошибки друг друга, почему этот процесс математически является градиентным спуском — только не по весам модели, как в уроке 285, а по самим предсказаниям, — какие гиперпараметры определяют поведение бустинга, чем отличаются друг от друга XGBoost, LightGBM и CatBoost, и как не дать бустингу переобучиться.

История

Первый работоспособный алгоритм бустинга появился не как градиентный метод, а как алгоритм голосования по ошибкам: в 1995 году Йоав Фройнд и Роберт Шапире предложили AdaBoost (англ. Adaptive Boosting, «адаптивный бустинг») — метод, который на каждой итерации увеличивал вес неправильно классифицированных примеров, заставляя следующий слабый классификатор уделять им больше внимания. AdaBoost работал и показывал отличные результаты, но долгое время оставался скорее удачной эвристикой, чем частью общей теории: было неясно, что это за метод такой на самом деле и почему он вообще работает так хорошо.

Общую теоретическую рамку предложил Джером Фридман (Jerome Friedman) из Стэнфорда в серии работ 1999–2001 годов. Фридман показал, что AdaBoost — лишь частный случай гораздо более общей идеи: бустинг можно построить для любой дифференцируемой функции потерь, если на каждом шаге обучать новый слабый алгоритм не абы как, а предсказывать антиградиент этой функции потерь — то есть направление, в котором нужно скорректировать текущий прогноз, чтобы ошибка уменьшилась быстрее всего. Так появилась Gradient Boosting Machine (GBM, «машина градиентного бустинга») в её современном, общем виде — универсальный рецепт, применимый и к регрессии, и к классификации, и вообще к любой задаче с гладкой функцией потерь.

Следующие полтора десятилетия ушли на инженерное превращение красивой идеи Фридмана в промышленный инструмент. В 2014 году аспирант Тяньцы Чэнь (Tianqi Chen) выпустил XGBoost — реализацию, которая добавила к идее Фридмана регуляризацию, использование вторых производных функции потерь и агрессивную оптимизацию под многопроцессорные вычисления; именно XGBoost стал первой библиотекой градиентного бустинга, массово выигрывавшей соревнования Kaggle. В 2017 году Microsoft выпустила LightGBM, сделав ставку на скорость на больших датасетах, а компания Яндекс — CatBoost, сделав ставку на качественную работу с категориальными признаками без ручного кодирования. Три библиотеки, три разных набора инженерных компромиссов вокруг одной и той же математической идеи Фридмана — и именно эта идея сегодняшний урок разбирает по шагам.

Последовательное исправление ошибок: как строится ансамбль

Интуиция

Представь репетитора, который готовит тебя к экзамену по трём предметам сразу и работает так: сначала даёт очень грубую общую оценку твоего уровня («в среднем ты знаешь тему на 6 из 10»), затем прогоняет тебя по пробному тесту и смотрит, где именно эта грубая оценка ошиблась — где ты знаешь заметно лучше среднего, а где заметно хуже. После этого он не выкидывает первую оценку и не спрашивает мнение ещё одного независимого репетитора (как это делал бы Random Forest) — он берёт именно эти отклонения от первой оценки и учит следующего помощника предсказывать конкретно их: насколько именно нужно поправить исходную оценку вверх или вниз в каждом конкретном случае. Затем процесс повторяется: смотрим, что осталось неисправленным после первой поправки, учим следующего помощника исправлять уже это, и так снова и снова, пока итоговая сумма всех грубых прикидок и последовательных мелких поправок не станет достаточно точной.

Именно так работает градиентный бустинг: первое дерево (обычно даже не дерево, а просто константа — среднее значение целевой переменной) даёт грубый общий прогноз. Дальше вычисляются остатки — разница между истинным значением и текущим прогнозом ансамбля, то есть в точности то, что ансамбль пока не «объяснил». Следующее дерево обучается не на исходной целевой переменной, а именно на этих остатках: его задача — предсказать, куда и насколько нужно сдвинуть текущий прогноз. Предсказание этого дерева добавляется к общему ансамблю не целиком, а с небольшим весом (скорость обучения, learning rate), чтобы не «перепрыгнуть» верный ответ одним резким скачком. Процесс повторяется десятки, сотни или тысячи раз.

Формула

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

$$F_0(x) = \bar y = \frac1N\sum_{i=1}^N y_i$$

На каждой следующей итерации $m = 1, 2, \dots, M$ вычисляются остатки текущего ансамбля

$$r_i^{(m)} = y_i - F_{m-1}(x_i)$$

обучается новое (обычно неглубокое) дерево $h_m(x)$, предсказывающее эти остатки, и ансамбль обновляется с шагом $\eta$ (скорость обучения, learning rate, он же коэффициент усадки, shrinkage):

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

Итоговый прогноз после $M$ деревьев — это сумма начального приближения и всех последовательных поправок с учётом их веса: $F_M(x) = F_0(x) + \eta\sum_{m=1}^M h_m(x)$.

Разбор примеров

Пример 1 (полная трассировка трёх итераций бустинга). Возьмём небольшой датасет: $x = (1,2,3,4,5,6)$, $y = (5,7,8,13,14,20)$ — зависимость растёт, но не строго линейно. Все деревья в этом примере — «пни» (stumps), деревья глубиной 1 с единственным порогом разбиения, а скорость обучения $\eta = 0{,}1$.

Начальное приближение — среднее по всем шести значениям: $F_0 = \frac{5+7+8+13+14+20}{6} = 11{,}1667$.

Остатки первой итерации: $r^{(1)} = (-6{,}1667;\ -4{,}1667;\ -3{,}1667;\ 1{,}8333;\ 2{,}8333;\ 8{,}8333)$.

Первое дерево $h_1$ разбивает выборку по порогу $x < 3{,}5$: в левом листе ($x=1,2,3$) среднее остатков равно $-4{,}5000$, в правом листе ($x=4,5,6$) — $4{,}5000$. Обновляем ансамбль: для $x<3{,}5$ получаем $F_1 = 11{,}1667 + 0{,}1\cdot(-4{,}5000) = 10{,}7167$, для $x\ge3{,}5$ — $F_1 = 11{,}1667 + 0{,}1\cdot4{,}5000 = 11{,}6167$.

Остатки второй итерации: $r^{(2)} = y - F_1 = (-5{,}7167;\ -3{,}7167;\ -2{,}7167;\ 1{,}3833;\ 2{,}3833;\ 8{,}3833)$. Второе дерево $h_2$ разбивает по порогу $x < 5{,}5$: в левом листе ($x=1..5$) среднее остатков равно $-1{,}6767$, в правом листе (одна точка $x=6$) — $8{,}3833$. Новый ансамбль: для $x<5{,}5$ — $F_2 = F_1 + 0{,}1\cdot(-1{,}6767)$, для $x=6$ — $F_2 = F_1 + 0{,}1\cdot8{,}3833$.

Остатки третьей итерации: $r^{(3)} = y - F_2 = (-5{,}5490;\ -3{,}5490;\ -2{,}5490;\ 1{,}5510;\ 2{,}5510;\ 7{,}5450)$. Третье дерево $h_3$ разбивает по порогу $x < 4{,}5$: слева ($x=1..4$) среднее остатков $-2{,}5240$, справа ($x=5,6$) — $5{,}0480$.

Сведём всё в единую таблицу по всем шести точкам и трём итерациям:

А вот как убывает среднеквадратичная ошибка (MSE) по всем шести точкам на каждом шаге:

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

Пример 2 (почему шаг должен быть маленьким — сравнение $\eta=0{,}1$ и $\eta=1{,}0$ на одном и том же первом дереве). Возьмём то же первое дерево $h_1$ из примера 1 (листья $-4{,}5000$ и $4{,}5000$), но обновим ансамбль сразу с полным шагом $\eta = 1{,}0$: $F_1^{\text{full}} = 11{,}1667 + 1{,}0\cdot(-4{,}5000) = 6{,}6667$ для $x<3{,}5$ и $F_1^{\text{full}} = 11{,}1667 + 1{,}0\cdot4{,}5000 = 15{,}6667$ для $x\ge3{,}5$. Посчитаем MSE этого прогноза: разности с истинными $y$ равны $(-1{,}6667;\ 0{,}3333;\ 1{,}3333;\ -2{,}6667;\ -1{,}6667;\ 4{,}3333)$, а MSE $= 5{,}5556$.

Сравни: после ровно одного дерева $\eta=1{,}0$ даёт MSE $= 5{,}5556$, тогда как $\eta=0{,}1$ после того же самого дерева даёт MSE $=21{,}9580$ (из таблицы примера 1). Формально полный шаг выглядит гораздо эффективнее — ошибка обучения падает намного быстрее. Но здесь и кроется главный риск: одно грубое дерево уже «выжало» из данных почти всё, что можно, полным шагом, и следующим деревьям почти нечего будет исправлять содержательно — они начнут подстраиваться под шум и случайные детали конкретной обучающей выборки, а не под настоящую закономерность. Небольшой шаг $\eta=0{,}1$, наоборот, намеренно оставляет пространство для десятков последующих аккуратных уточнений — эта идея — прямой аналог выбора скорости обучения в обычном градиентном спуске (урок 285), и мы разберём её отдельно в разделе про гиперпараметры.

Пример 3 (принципиальное отличие от голосования Random Forest). Возьмём тот же датасет $x=(1,2,3,4,5,6)$, $y=(5,7,8,13,14,20)$ и сравним, что «видит» второе дерево ансамбля в Random Forest и в градиентном бустинге. В Random Forest (урок 317) дерево №2 обучается на собственной bootstrap-выборке и предсказывает исходную целевую переменную $y$ напрямую — оно ничего не знает о том, что предсказало дерево №1, и в принципе могло бы дать очень похожий на первое дерево прогноз, если оба дерева видят похожие данные. В градиентном бустинге дерево №2 в принципе не видит исходный $y$ — на вход ему подаются остатки $r^{(2)} = y - F_1$, то есть именно то, что дерево №1 (точнее, весь ансамбль до текущего момента) не объяснило. Из таблицы примера 1: для $x=6$ остаток после первого дерева составляет $r^{(2)}_{x=6} = 20 - 11{,}6167 = 8{,}3833$ — крупная недооценка именно этой точки, и второе дерево совершенно осознанно выделяет её в отдельный лист именно потому, что это самая большая непокрытая ошибка. Random Forest так поступить не может в принципе: у него нет общего «текущего состояния ансамбля», на ошибки которого можно было бы целенаправленно настраиваться, — каждое дерево работает изолированно.

Почему это важно

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

Функциональный градиентный спуск: почему бустинг «градиентный»

Интуиция

В уроке 285 ты разбирал классический градиентный спуск: у модели есть набор весов $w$, и на каждом шаге веса сдвигаются против градиента функции потерь по этим весам, $w \leftarrow w - \eta\nabla L(w)$. Градиентный бустинг устроен внешне совсем иначе — там нет одного набора весов, которые постепенно подкручиваются, а есть последовательность целых деревьев. Но за этим внешним отличием прячется в точности та же самая идея, если сменить точку зрения на то, что вообще является «параметром», который оптимизируется.

Представь, что вместо весов модели параметром считается сам вектор прогнозов на обучающей выборке — $N$ чисел $\bigl(F(x_1), F(x_2), \dots, F(x_N)\bigr)$, по одному на каждый обучающий пример. Функция потерь — это функция именно от этого вектора: $L\bigl(F(x_1),\dots,F(x_N)\bigr) = \sum_i \ell\bigl(y_i, F(x_i)\bigr)$. У этой функции, как и у любой другой, есть градиент — только теперь это не градиент по весам, а градиент по значениям прогноза в каждой точке, покоординатно. Двигаться против этого градиента — значит для каждого обучающего примера отдельно сдвинуть его прогноз в сторону уменьшения ошибки именно на этом примере. Проблема в том, что такой «идеальный» шаг определён только в $N$ конкретных точках обучающей выборки — он не задаёт правило для новых, ранее не виденных объектов. Именно эту проблему решает дерево $h_m$: вместо того чтобы напрямую использовать антиградиент только в обучающих точках, мы обучаем дерево аппроксимировать этот антиградиент как функцию от признаков $x$ — и тогда дерево умеет обобщать это направление коррекции на любой новый объект.

Формула

Функциональный градиентный спуск. Пусть $\ell(y, F)$ — функция потерь на одном примере (например, $\ell(y,F) = \frac12(y-F)^2$ для регрессии). Антиградиент (псевдо-остаток) в точке $F = F_{m-1}(x_i)$ определяется как

$$g_i = -\left.\frac{\partial \ell(y_i, F)}{\partial F}\right|_{F=F_{m-1}(x_i)}$$

Дерево $h_m(x)$ обучается методом наименьших квадратов приближать значения $g_i$ по признакам $x_i$, а обновление ансамбля $F_m = F_{m-1} + \eta\,h_m$ — это в точности шаг градиентного спуска $w \leftarrow w - \eta\nabla L(w)$, только роль «весов» играет вектор прогнозов, а роль «направления градиента, применимого к любому новому объекту», играет обученное на псевдо-остатках дерево.

Разбор примеров

Пример 1 (среднеквадратичная ошибка — псевдо-остаток совпадает с обычным остатком). Для $\ell(y,F) = \frac12(y-F)^2$ производная по $F$ равна $\frac{\partial \ell}{\partial F} = -(y-F) = F - y$, значит антиградиент $g = -(F-y) = y-F$ — это в точности обычный остаток, которым мы пользовались в предыдущем разделе. Проверим на конкретном примере из раздела выше: $x=1$, $y=5$, $F_0 = 11{,}1667$. Тогда $g = y - F_0 = 5 - 11{,}1667 = -6{,}1667$ — ровно то значение, с которого мы начинали таблицу трассировки. Это объясняет, почему в примере 1 предыдущего раздела мы имели полное право называть то, что предсказывают деревья, просто «остатками»: для среднеквадратичной ошибки псевдо-остаток градиентного бустинга и обычный остаток $y-F$ — буквально одно и то же число.

Пример 2 (абсолютная ошибка — псевдо-остаток это знак, а не разность). Для $\ell(y,F) = |y-F|$ производная по $F$ не определена в точке $F=y$, а всюду, где определена, равна $\frac{\partial \ell}{\partial F} = -\,\mathrm{sign}(y-F)$, значит антиградиент $g = \mathrm{sign}(y-F)$ принимает только значения $+1$, $-1$ или $0$ — не саму величину ошибки, а лишь её знак. Возьмём точку $y=8$, $F=5$: $g = \mathrm{sign}(8-5) = \mathrm{sign}(3) = +1$. Сравни с точкой $y=100$, $F=5$: несмотря на то что фактическая ошибка здесь в тридцать раз больше ($100-5=95$ против $3$), псевдо-остаток остаётся тем же самым $+1$. Именно поэтому бустинг с функцией потерь MAE (Mean Absolute Error) гораздо устойчивее к редким выбросам с огромной ошибкой, чем бустинг с MSE: выброс с ошибкой в тысячу единиц «тянет» дерево к себе ровно так же слабо, как обычная ошибка в единицу, потому что дерево видит лишь знак отклонения, а не его масштаб.

Пример 3 (второй порядок — почему XGBoost называют Newton boosting). Классический алгоритм Фридмана использует только первую производную (градиент) функции потерь. Современные реализации вроде XGBoost идут на шаг дальше и используют ещё и вторую производную (гессиан) $h_i = \frac{\partial^2 \ell(y_i,F)}{\partial F^2}$, приближая функцию потерь квадратичной параболой второго порядка (разложение Тейлора) вместо линейной — это в точности идея метода Ньютона из курса оптимизации, применённая не к весам, а к предсказаниям. Для среднеквадратичной ошибки гессиан $h_i = \frac{\partial^2}{\partial F^2}\left[\frac12(y_i-F)^2\right] = 1$ — константа, одинаковая для всех примеров, поэтому для MSE использование второй производной ничего не меняет и Newton boosting в точности совпадает с обычным градиентным бустингом. А вот для логистической функции потерь (классификация) гессиан равен $h_i = p_i(1-p_i)$, где $p_i$ — текущая предсказанная вероятность, и он разный для разных примеров: чем ближе $p_i$ к $0{,}5$ (модель ещё не уверена), тем больше гессиан и тем сильнее XGBoost доверяет градиенту в этой точке при построении дерева — а на уверенно классифицированных примерах ($p_i$ близко к $0$ или $1$) гессиан мал, и такие примеры меньше влияют на форму дерева. Это тонкая, но практически значимая причина, по которой XGBoost на задачах классификации сходится быстрее и точнее, чем бустинг первого порядка.

Почему это важно

Понимание бустинга как градиентного спуска в пространстве предсказаний, а не в пространстве весов, объясняет сразу три вещи, которые иначе выглядели бы просто набором разрозненных правил. Во-первых, почему смена функции потерь (MSE, MAE, логистическая функция потерь, квантильная функция потерь для предсказания процентилей) не требует переписывания всего алгоритма — меняется только формула для псевдо-остатка, а сам механизм «обучить дерево приближать псевдо-остаток и добавить с весом $\eta$» остаётся неизменным. Во-вторых, почему learning rate в бустинге играет ровно ту же роль, что и в обычном градиентном спуске урока 285, — слишком большой шаг рискует «перепрыгнуть» и переобучиться, слишком маленький требует непропорционально много итераций. В-третьих, почему более совершенные реализации вроде XGBoost, использующие вторую производную, обычно сходятся быстрее и стабильнее «наивного» бустинга первого порядка — это прямая аналогия с тем, зачем в общей теории оптимизации нужны методы Ньютона и квазиньютоновские методы, учитывающие кривизну функции потерь, а не только направление её убывания.

Гиперпараметры: число деревьев, learning rate и глубина слабых деревьев

Интуиция

У градиентного бустинга три взаимосвязанных «рычага», которые вместе определяют, насколько сложную зависимость способен выучить ансамбль и насколько сильно он рискует переобучиться: сколько всего деревьев добавить ($M$), с каким весом добавлять каждое из них ($\eta$) и насколько сложным разрешить быть каждому отдельному дереву (глубина). Все три параметра тянут в разные стороны одного и того же компромисса между недообучением и переобучением (урок 304): слишком мало деревьев, слишком маленький шаг или слишком мелкие деревья — недообучение, слишком много деревьев, слишком большой шаг или слишком глубокие деревья — переобучение.

Формула

Бюджет обучения бустинга. Итоговый прогноз $F_M(x) = F_0(x) + \eta\sum_{m=1}^M h_m(x)$ зависит от произведения $\eta \cdot M$ примерно так же, как от каждого множителя по отдельности: удвоение $\eta$ при том же $M$ или удвоение $M$ при том же $\eta$ дают сопоставимый по масштабу суммарный «сдвиг» ансамбля относительно начального приближения $F_0$. Эмпирическое практическое правило: уменьшение $\eta$ в $k$ раз при увеличении $M$ примерно в $k$ раз обычно сохраняет или улучшает качество (за счёт более мелких, аккуратных шагов), но пропорционально увеличивает время обучения.

Глубина слабого дерева. Дерево глубины $d$ способно моделировать взаимодействия не более чем между $d$ признаками одновременно (дерево глубины 1, «пень», может использовать только один признак на весь прогноз; дерево глубины 2 — учесть совместное влияние уже двух признаков, и так далее). Типичная глубина деревьев в промышленном градиентном бустинге — от 3 до 8–10, заметно меньше, чем у отдельного дерева решений (урок 316), которое часто растят почти до листьев с одним объектом.

Разбор примеров

Пример 1 (почему пень не всегда справляется — взаимодействие признаков). Возьмём искусственную задачу-«исключающее ИЛИ» (XOR): два бинарных признака $x_1, x_2 \in \{0,1\}$, целевая переменная $y = 10$, если $x_1 \ne x_2$, и $y=0$, если $x_1 = x_2$. Четыре точки: $(0,0){\to}0$, $(0,1){\to}10$, $(1,0){\to}10$, $(1,1){\to}0$. Начальное приближение $F_0 = \frac{0+10+10+0}{4} = 5$, остатки — $(-5,\ 5,\ 5,\ -5)$. Попробуем обучить дерево-пень глубины 1, разбивающее только по $x_1$: в группе $x_1=0$ остатки $(-5,5)$ со средним $0$, в группе $x_1=1$ остатки $(5,-5)$ тоже со средним $0$. Пень по $x_1$ (и точно так же пень по $x_2$) предсказывает ровно $0$ в обоих листьях — совершенно бесполезная итерация: MSE как была равна $25$ (среднее квадратов остатков $-5,5,5,-5$), так и осталась. Возьмём вместо пня дерево глубины 2, которое сначала делит по $x_1$, а затем внутри каждой ветви ещё раз делит по $x_2$: получаются четыре чистых листа, каждый из которых в точности предсказывает свой остаток ($-5$, $5$, $5$, $-5$). При $\eta=1{,}0$ ансамбль после этого единственного дерева глубины 2 предсказывает истинные значения $y$ идеально. Взаимодействие признаков $x_1$ и $x_2$ принципиально требует глубины дерева не меньше двух — ни один пень с этим не справится, сколько бы их ни строить последовательно по одному признаку за раз.

Пример 2 (learning rate и число деревьев — сопоставимый бюджет двумя разными путями). На нашем основном датасете из шести точек ($x=1..6$, $y=(5,7,8,13,14,20)$) первый шаг дерева $h_1$ (листья $-4{,}5000$ и $4{,}5000$) при $\eta=0{,}1$ сдвигает прогноз всего на $\pm0{,}45$ за одну итерацию, а при $\eta=1{,}0$ — сразу на $\pm4{,}5$. Чтобы достичь сопоставимого суммарного сдвига в $\pm4{,}5$ при $\eta=0{,}1$, потребовалось бы порядка десяти аналогичных по величине шагов вместо одного — именно поэтому на практике для малого $\eta$ всегда нужно кратно увеличивать число деревьев $M$, а не оставлять его прежним. Типичные промышленные диапазоны: $\eta \in [0{,}01;\ 0{,}3]$, $M \in [100; 2000]$, причём меньший $\eta$ почти всегда сопровождается заметно большим $M$ — например, $\eta=0{,}3$ с $M=100$ или $\eta=0{,}03$ с $M=1000$ дают сопоставимый по масштабу итоговый сдвиг ансамбля, но второй вариант обычно чуть точнее ценой десятикратно большего времени обучения.

Пример 3 (типичная сетка гиперпараметров на табличном датасете). Допустим, ты настраиваешь бустинг для задачи кредитного скоринга и перебираешь три конфигурации при фиксированной глубине $d=4$:

Конфигурация A с крупным шагом и малым числом деревьев быстрее всего обучается (Train AUC самый высокий), но заметно переобучается — разрыв между обучением и валидацией ($0{,}91$ против $0{,}84$) самый большой. Конфигурация C с маленьким шагом и большим числом деревьев обучается на порядок дольше, но даёт наилучшее качество именно там, где это важно — на валидации ($0{,}875$), а разрыв между train и val почти отсутствует. Это типичная иллюстрация практического правила: маленький learning rate с достаточным числом деревьев почти всегда даёт лучшее итоговое качество на новых данных, но требует значительно больше вычислительного времени — компромисс, который на практике решается через early stopping (мы разберём его в разделе про переобучение).

Почему это важно

Три гиперпараметра — число деревьев, скорость обучения и глубина — редко настраиваются по отдельности: изменение одного почти всегда требует пересмотра остальных. Понимание этой связанности избавляет от типичной ошибки новичка — перебирать только один параметр (например, число деревьев) при фиксированных значениях остальных и удивляться, почему результат не улучшается: чаще всего дело не в «неправильном» числе деревьев самом по себе, а в несогласованной комбинации learning rate, глубины и числа итераций.

XGBoost, LightGBM и CatBoost: три кита современного бустинга

Интуиция

Общий алгоритм Фридмана 1999–2001 годов описывает математическую идею, но не решает инженерные вопросы: как быстро найти лучший порог разбиения дерева на миллионах строк, что делать с пропущенными значениями, как эффективно закодировать категориальный признак с тысячами уникальных значений (город, ID товара), как распараллелить обучение на многих ядрах или машинах. XGBoost, LightGBM и CatBoost — три разных, во многом конкурирующих ответа индустрии на эти вопросы поверх одной и той же математической идеи бустинга.

Формула

XGBoost (Extreme Gradient Boosting, 2014). Использует второй порядок разложения функции потерь (градиент $g_i$ и гессиан $h_i$, см. предыдущий раздел) и добавляет явную регуляризацию сложности дерева. Оптимальное значение в листе с примерами $g_i, h_i$ и коэффициентом регуляризации $\lambda$:

$$w^\* = -\frac{\sum_i g_i}{\sum_i h_i + \lambda}$$

LightGBM (2017). Строит деревья по листьям (leaf-wise), а не по уровням (level-wise): на каждом шаге разбивается не «все листья текущего уровня», а тот единственный лист, который сильнее всего уменьшит функцию потерь, — это даёт более глубокие, асимметричные, но обычно более точные при том же числе листьев деревья. Ускоряется за счёт гистограммного разбиения признаков на бины и техники GOSS (англ. Gradient-based One-Side Sampling — «одностороннее сэмплирование по градиенту»): сохраняются все примеры с большим по модулю градиентом (они «интереснее» — модель на них ошибается сильнее) и лишь случайная подвыборка примеров с малым градиентом, с весовой поправкой $(1-a)/b$ для сохранения несмещённости оценки, где $a$ — доля сохранённых «крупных» градиентов, $b$ — доля случайно взятых «мелких».

CatBoost (2017, Яндекс). Обрабатывает категориальные признаки нативно через упорядоченные статистики целевой переменной (ordered target statistics), избегая утечки данных, и строит симметричные («oblivious») деревья, где на всех узлах одного уровня используется один и тот же признак и порог разбиения, а также применяет упорядоченный бустинг (ordered boosting) — вариант построения ансамбля, при котором остаток для каждого примера считается только по модели, обученной на «предшествующих» ему примерах случайной перестановки, что снижает систематический сдвиг (prediction shift) от повторного использования обучающих данных.

Разбор примеров

Пример 1 (XGBoost — формула оптимального листа на конкретных числах). Допустим, в одном листе оказались два обучающих примера с градиентами (для задачи бинарной классификации, логистическая функция потерь) $g = (-0{,}3;\ -0{,}5)$ и гессианами $h = (0{,}21;\ 0{,}25)$, коэффициент регуляризации $\lambda = 1$. Сумма градиентов $G = -0{,}8$, сумма гессианов $H = 0{,}46$. Оптимальное значение листа $w^\* = -\dfrac{-0{,}8}{0{,}46+1} = \dfrac{0{,}8}{1{,}46} \approx 0{,}5479$. Сравни это с «наивным» усреднением одних лишь градиентов без учёта гессиана и регуляризации: $\dfrac{-(-0{,}3-0{,}5)}{2} = 0{,}4$. Разница ($0{,}5479$ против $0{,}4$) — прямое следствие того, что XGBoost взвешивает вклад каждого примера его локальной кривизной функции потерь (гессианом) и «придерживает» итоговое значение слагаемым регуляризации $\lambda$ в знаменателе, не давая листу принять слишком экстремальное значение по паре примеров.

Пример 2 (LightGBM GOSS — во сколько раз меньше данных обрабатывается за итерацию). Пусть обучающая выборка содержит $N=10\,000$ примеров, доля сохраняемых «крупных» градиентов $a=0{,}2$, доля случайной подвыборки среди оставшихся — $b=0{,}1$. GOSS сохраняет топ-$20\%$ примеров по модулю градиента целиком: это $0{,}2\cdot10\,000=2\,000$ примеров. Из оставшихся $8\,000$ примеров с малым градиентом случайно берётся ещё $10\%$: $0{,}1\cdot8\,000=800$ примеров. Итого на построение одного дерева используется $2\,000+800=2\,800$ примеров вместо $10\,000$ — экономия свыше $70\%$ вычислений на каждой итерации при этом веса случайно отобранных «мелких» примеров умножаются на компенсирующий коэффициент $(1-a)/b = 0{,}8/0{,}1 = 8$, чтобы суммарная статистика градиента по подвыборке оставалась несмещённой оценкой статистики по всей выборке. Именно эта техника — одна из главных причин, почему LightGBM на больших табличных датасетах (миллионы строк) обучается заметно быстрее XGBoost при сопоставимом качестве.

Пример 3 (CatBoost — почему наивное кодирование категорий это утечка данных). Представь признак «город» с сотней уникальных значений и задачу предсказания дохода. Наивный способ превратить категорию в число — посчитать среднее значение целевой переменной по всем строкам с этим городом (целевое кодирование, «target encoding») и подставить это среднее как признак. Проблема в том, что при вычислении такого среднего для конкретной строки используется в том числе и сама целевая переменная этой строки — модель получает информацию о правильном ответе через «чёрный ход», прямо как утечка данных, которую ты разбирал в уроке 305. CatBoost решает это через ordered boosting: для каждого примера статистика по категории считается только по тем примерам, которые в случайно выбранной перестановке данных идут раньше текущего — модель в момент вычисления признака для конкретной строки не имеет доступа ни к целевой переменной этой строки, ни к строкам, которые «ещё не наступили» в этом искусственном временном порядке. Это тот же самый принцип, что и корректное разбиение данных временных рядов на обучающую и тестовую выборки (train/test, тоже из урока 305), только применённый не к разбиению всего датасета, а к внутреннему механизму построения каждого отдельного дерева ансамбля.

Почему это важно

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

Переобучение и сравнение с Random Forest

Интуиция

У Random Forest (урок 317) есть встроенная защита от переобучения: каждое дерево обучается независимо на своей bootstrap-выборке, а усреднение большого числа слабо коррелированных деревьев снижает разброс (variance) итогового прогноза — добавление сотого или пятисотого дерева почти ничего не меняет, ошибка на валидации выходит на плато и там и остаётся. У градиентного бустинга такой встроенной защиты нет: каждое новое дерево целенаправленно уменьшает смещение (bias), подгоняя ансамбль всё точнее и точнее под конкретную обучающую выборку, — и если не остановиться вовремя, рано или поздно ансамбль начнёт подгоняться не под общую закономерность, а под шум и случайные особенности именно этих обучающих данных.

Формула

Асимметрия переобучения Random Forest и градиентного бустинга. Для Random Forest ошибка на обучении и на валидации с ростом числа деревьев $B$ обе выходят на плато и держатся на нём: $\mathrm{Err}_{\text{val}}^{RF}(B) \to \text{const}$ при $B \to \infty$ (усреднение уменьшает variance, но не может уменьшить bias ниже некоторого предела). Для градиентного бустинга ошибка на обучении при росте $M$ стремится к нулю, $\mathrm{Err}_{\text{train}}^{GB}(M) \to 0$, тогда как ошибка на валидации сначала убывает, достигает минимума при некотором $M^\*$, а затем снова начинает расти: $\mathrm{Err}_{\text{val}}^{GB}(M)$ имеет форму буквы U. Практическая защита — ранняя остановка (early stopping): прекратить добавление деревьев в точке $M^\* = \arg\min_M \mathrm{Err}_{\text{val}}^{GB}(M)$, определяемой по отдельной валидационной выборке, а не по числу итераций, заданному заранее.

Разбор примеров

Пример 1 (крошечный датасет — к чему приводит бустинг без остановки). Вернёмся к нашему датасету из шести точек, где MSE обучения после трёх деревьев снизилась с $25{,}8056$ до $16{,}8666$ (раздел «Последовательное исправление ошибок»). Если продолжать добавлять новые деревья тем же путём — каждое следующее дерево находит новый порог разбиения и корректирует оставшийся остаток, — при достаточной глубине деревьев и десятке-другом итераций MSE на этих же шести точках неизбежно приблизится к нулю: у деревьев довольно «степеней свободы», чтобы в конце концов буквально запомнить все шесть значений $y$ по отдельности. Это ровно тот сценарий, которого стоит опасаться: ошибка на обучении, стремящаяся к нулю на крошечном датасете, — не признак прекрасной модели, а прямое свидетельство того, что модель запоминает конкретные шесть точек вместо того, чтобы выучивать закономерность, которая обобщилась бы на седьмую, ранее не виденную точку.

Пример 2 (сопоставление кривых RF и GB по числу деревьев на большем датасете). Представим задачу на $50\,000$ строк, где для Random Forest и градиентного бустинга (learning rate $\eta=0{,}1$, фиксированная глубина) сняты значения MSE при разном числе деревьев:

Кривая Random Forest ведёт себя ровно так, как описано в уроке 317: после 200–500 деревьев и train, и val практически перестают меняться (уже знакомое правило «после 100–500 деревьев улучшение минимально»). Кривая градиентного бустинга ведёт себя принципиально иначе: train MSE продолжает падать почти до нуля даже на 1000 деревьях, а val MSE достигает минимума около $200$ деревьев ($3{,}8$), а затем при $500$ и особенно при $1000$ деревьях резко ухудшается ($5{,}9$, затем $9{,}2$) — классическая U-образная кривая переобучения, при том что ошибка на обучении в это же время выглядит всё лучше и лучше.

Пример 3 (практическая ранняя остановка по этой же таблице). Используя данные примера 2, оптимальное число деревьев для этой задачи — $M^\* = 200$: именно здесь val MSE минимальна ($3{,}8$), при $500$ деревьях она уже заметно хуже ($5{,}9$), а при $1000$ — хуже почти в два с половиной раза относительно оптимума. На практике для этого не нужно вручную перебирать десятки значений $M$: библиотеки градиентного бустинга поддерживают параметр вроде early_stopping_rounds, который отслеживает метрику на отдельной валидационной выборке после каждого нового дерева и автоматически останавливает обучение, если метрика не улучшалась заданное число итераций подряд, — возвращая в итоге модель ровно с тем числом деревьев, при котором была зафиксирована лучшая валидационная метрика, без необходимости заранее угадывать правильное $M$.

Почему это важно

Сравнение с Random Forest подытоживает главный практический компромисс всего блока моделей курса: Random Forest — более «безопасная по умолчанию» модель, которую сложно серьёзно испортить неудачным выбором числа деревьев, но которая упирается в потолок точности, заданный качеством одного дерева и объёмом признаков. Градиентный бустинг способен пробить этот потолок и обычно даёт заметно более точный итоговый результат именно за счёт целенаправленной последовательной коррекции ошибок, но эта же особенность требует активного контроля — валидационной выборки, ранней остановки, аккуратного подбора learning rate и глубины деревьев — без которого легко получить модель, прекрасно показывающую себя на обучающих данных и заметно разочаровывающую на новых.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Дан датасет $y = (4,6,8)$. Найти начальное приближение $F_0$ градиентного бустинга (для среднеквадратичной ошибки).

Задание 2: Для датасета из задания 1 ($y=(4,6,8)$, $F_0=6$) найти остатки $r_i = y_i - F_0$.

Задание 3: Дерево $h_1$ предсказывает в некотором листе значение $-2$. Текущий прогноз ансамбля в этом листе $F_0=10$, скорость обучения $\eta=0{,}1$. Найти $F_1$.

Задание 4: Функция потерь $\ell(y,F)=\frac12(y-F)^2$, $y=10$, $F=7$. Найти производную $\partial\ell/\partial F$ и антиградиент (псевдо-остаток).

Задание 5 (машинное обучение): Верно ли утверждение «увеличение числа деревьев в градиентном бустинге всегда снижает ошибку на валидации»? Обоснуй.

Задание 6: Функция потерь — абсолютная ошибка $\ell(y,F)=|y-F|$, $y=8$, $F=5$. Найти псевдо-остаток $g=\mathrm{sign}(y-F)$.

Задание 7: Какая типичная глубина деревьев используется в промышленном градиентном бустинге (XGBoost/LightGBM/CatBoost) — примерно такая же, как у отдельного дерева решений из урока 316, заметно меньше или заметно больше?

Задание 8: $F_0=5$. Дерево $h_1$ предсказывает $+2$, применяется с $\eta=0{,}5$, получаем $F_1$. Затем дерево $h_2$ предсказывает $-1$, тоже с $\eta=0{,}5$, получаем $F_2$. Найти $F_1$ и $F_2$.

Задание 9 (машинное обучение): При обучении бустинга ошибка на обучающей выборке равномерно снижается с каждой добавленной сотней деревьев, а ошибка на валидации начала расти после 300-го дерева. Как правильно поступить?

Задание 10: $F_0=20$, дерево $h_1(x)=-8$, скорость обучения $\eta=0{,}05$. Найти $F_1$.

Средние задания (11–20)

Задание 11: Датасет $x=(1,2,3)$, $y=(10,10,20)$. Найти $F_0$.

Задание 12: Для датасета из задания 11 найти остатки $r^{(1)}_i = y_i - F_0$.

Задание 13: Разбить $x=(1,2,3)$ порогом $x<2{,}5$ (левый лист $\{1,2\}$, правый лист $\{3\}$) и найти листовые значения дерева $h_1$ (средние остатков в каждом листе) для датасета из заданий 11–12.

Задание 14: Используя результат задания 13 и $\eta=0{,}1$, найти $F_1(x)$ для каждого $x=1,2,3$.

Задание 15 (машинное обучение): Объясни разницу в том, что «видит» на входе второе дерево ансамбля в Random Forest и в градиентном бустинге.

Задание 16: В листе XGBoost два примера с градиентами $g=(-0{,}3;\ -0{,}5)$ и гессианами $h=(0{,}21;\ 0{,}25)$, коэффициент регуляризации $\lambda=1$. Найти оптимальное значение листа $w^\*=-G/(H+\lambda)$.

Задание 17: LightGBM с GOSS: всего $N=10\,000$ примеров, доля сохраняемых «крупных» градиентов $a=0{,}2$, доля случайной подвыборки среди остальных $b=0{,}1$. Сколько примеров реально используется на одной итерации?

Задание 18: Learning rate уменьшили в 10 раз (с $0{,}1$ до $0{,}01$), но число деревьев оставили прежним. Что вероятнее всего произойдёт с качеством модели?

Задание 19 (машинное обучение): Дан ряд валидационных ошибок по числу деревьев: $M=50{\to}7{,}0$; $M=100{\to}5{,}2$; $M=150{\to}4{,}8$; $M=200{\to}4{,}5$; $M=250{\to}4{,}9$; $M=300{\to}5{,}6$. Найти $M^\*$, на котором стоит остановиться (early stopping).

Задание 20: Дерево-пень (глубина 1) на данных XOR ($x_1,x_2\in\{0,1\}$, $y=10\cdot[x_1\ne x_2]$) при разбиении по $x_1$ предсказывает $0$ в обоих листьях. Объясни, почему.

Продвинутые задания (21–30)

Задание 21 (машинное обучение): Датасет $x=(1,2,3,4)$, $y=(3,5,9,11)$. Найти $F_0$, обучить дерево $h_1$ с порогом $x<2{,}5$ (лево $\{1,2\}$, право $\{3,4\}$) и найти $F_1$ при $\eta=0{,}5$.

Задание 22: Продолжая задание 21, найти остатки $r^{(2)}=y-F_1$, обучить дерево $h_2$ с порогом $x<3{,}5$ (лево $\{1,2,3\}$, право $\{4\}$) и найти $F_2$ при $\eta=0{,}5$.

Задание 23: Используя результаты заданий 21–22, найти MSE до бустинга ($F_0$) и после двух деревьев ($F_2$) и сравнить.

Задание 24: Для среднеквадратичной функции потерь гессиан $h=\dfrac{\partial^2}{\partial F^2}\left[\frac12(y-F)^2\right]=1$ (константа). Покажи, что при $\lambda=0$ формула листа Newton boosting $w^\*=-G/H$ совпадает с обычным средним остатком градиентного бустинга.

Задание 25 (машинное обучение): На игрушечном датасете из шести точек ($x=1..6$) MSE после трёх деревьев снизилась с $25{,}8056$ до $16{,}8666$. Оцени, что произойдёт при продолжении добавления деревьев ещё на протяжении 15–20 итераций, и почему это тревожный сигнал.

Задание 26: После одного дерева на шести точках $\mathrm{MSE}(\eta=1{,}0)=5{,}5556$, а $\mathrm{MSE}(\eta=0{,}1)=21{,}9580$. Объясни компромисс между двумя скоростями обучения.

Задание 27: GOSS в LightGBM использует компенсирующий множитель веса $(1-a)/b$ для случайно отобранных примеров с малым градиентом. При $a=0{,}1$, $b=0{,}2$ найти этот множитель и объяснить его смысл.

Задание 28: Объясни, почему наивное target encoding категориального признака (среднее значение целевой переменной по всей обучающей выборке, посчитанное один раз до обучения) — это утечка данных, и как ordered boosting в CatBoost эту проблему решает.

Задание 29 (машинное обучение): На датасете 50 000 строк Random Forest с 500 деревьями достигает val MSE $=6{,}4$ и дальше почти не улучшается. Градиентный бустинг с 500 деревьями ($\eta=0{,}1$) достигает val MSE $=3{,}8$, но с 2000 деревьями (тот же $\eta$) val MSE вырастает до $9{,}2$ при train MSE $\approx0{,}05$. Что произошло и как это исправить?

Задание 30 (машинное обучение, синтез): Сформулируй одним связным ответом разницу между Random Forest (урок 317) и градиентным бустингом по трём осям: как строятся деревья, как комбинируются их предсказания и чем определяется переобучение каждого метода.

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

Разберём ошибки, которые чаще всего встречаются у тех, кто впервые применяет градиентный бустинг на практике.

• Настраивают число деревьев и learning rate независимо друг от друга. Как показано в разделе про гиперпараметры, эти два параметра сильно связаны через произведение $\eta\cdot M$: уменьшение learning rate почти всегда требует пропорционального увеличения числа деревьев, иначе модель окажется недообученной (задание 18). Перебор одного параметра при случайно зафиксированном другом почти гарантированно даёт неоптимальный результат.

• Не используют раннюю остановку и полагаются на фиксированное число деревьев. Валидационная ошибка градиентного бустинга ведёт себя не так, как у Random Forest, — она не выходит на плато, а после оптимума начинает расти (раздел про переобучение). Обучение с заранее заданным большим числом деревьев без мониторинга валидационной метрики регулярно приводит к переобученной модели, хотя обучающая ошибка при этом выглядит превосходно.

• Путают дерево бустинга с обычным одиночным деревом решений. Дерево из урока 316 часто растят глубоко, стремясь максимально точно описать обучающие данные. Дерево бустинга, наоборот, намеренно делают «слабым» и неглубоким (обычно 3–8 уровней) — глубокое дерево на каждой итерации бустинга лишь ускоряет переобучение, а не улучшает итоговое качество.

• Ожидают от Random Forest и градиентного бустинга одинаковой устойчивости к гиперпараметрам. Random Forest прощает не самые удачные значения числа деревьев или глубины — итоговое качество меняется плавно и незначительно. Градиентный бустинг гораздо чувствительнее: неудачная комбинация learning rate, глубины и числа деревьев может дать заметно худший результат, чем аккуратно подобранная, — с бустингом действительно стоит закладывать время на подбор гиперпараметров.

• Наивно кодируют категориальные признаки с большим числом уникальных значений. Как показано в задании 28, простое усреднение целевой переменной по категории без учёта порядка примеров создаёт утечку данных и завышает качество на кросс-валидации по сравнению с реальным поведением модели на новых данных. Либо используется корректная (упорядоченная) схема кодирования, либо CatBoost с встроенным ordered boosting, либо кодирование категорий отдельно на каждом фолде кросс-валидации (урок 306), а не по всему датасету сразу.

• Судят о качестве модели только по обучающей выборке. Раздел про переобучение показывает, что train MSE градиентного бустинга практически всегда продолжает улучшаться с ростом числа деревьев, даже когда модель уже давно переобучилась, — единственный надёжный ориентир для остановки обучения — отдельная валидационная выборка или кросс-валидация, а не метрика на данных, на которых модель обучалась.

Главное запомнить

• Градиентный бустинг строит деревья последовательно, а не независимо: каждое новое дерево $h_m$ обучается предсказывать остаток (или псевдо-остаток) текущего ансамбля и добавляется с весом $\eta$: $F_m(x) = F_{m-1}(x) + \eta\,h_m(x)$.

• Это принципиально другая философия ансамблирования, чем в Random Forest (урок 317): вместо параллельного независимого голосования — целенаправленная эстафета исправления ошибок.

• Название «градиентный» объясняется тем, что остаток $y-F$ для среднеквадратичной функции потерь в точности совпадает с антиградиентом функции потерь по прогнозу — бустинг является формой градиентного спуска в пространстве предсказаний, а не в пространстве весов модели (урок 285).

• Смена функции потерь (MSE, MAE, логистическая функция потерь) меняет лишь формулу псевдо-остатка, но не сам алгоритм построения ансамбля — универсальность этой рамки предложил Джером Фридман в 1999–2001 годах.

• Три ключевых гиперпараметра — число деревьев $M$, скорость обучения $\eta$ и глубина слабых деревьев — тесно связаны между собой через компромисс между недообучением и переобучением и почти никогда не настраиваются по отдельности.

• XGBoost (2014) использует вторую производную функции потерь (гессиан) и явную регуляризацию, LightGBM (2017) строит деревья по листьям и ускоряется техникой GOSS, CatBoost (2017) нативно и без утечки данных обрабатывает категориальные признаки через ordered boosting.

• Градиентный бустинг обычно точнее Random Forest, но заметно чувствительнее к настройке гиперпараметров и сильнее склонен к переобучению, поскольку целенаправленно снижает смещение (bias), а не разброс (variance).

• Валидационная ошибка бустинга имеет характерную U-образную форму по числу деревьев (в отличие от плато у Random Forest) — практическая защита от переобучения — ранняя остановка (early stopping) по отдельной валидационной выборке.

• Дерево бустинга глубины 1 (пень) не способно учесть взаимодействие нескольких признаков одновременно (пример с XOR) — поэтому промышленные реализации используют деревья глубины 3–8, а не только пни, как в классическом AdaBoost.

Связь с темами курса

Этот урок напрямую опирается на градиентный спуск из урока 285: формула обновления ансамбля $F_m = F_{m-1} + \eta\,h_m(x)$ — это тот же самый шаг $w_{new}=w-\eta\nabla L(w)$, только «параметром», который оптимизируется, становится не набор весов модели, а вектор прогнозов на обучающей выборке. Остаток $y-F$ — это в точности антиградиент среднеквадратичной функции потерь по прогнозу, что превращает бустинг в форму функционального градиентного спуска; а использование в XGBoost второй производной функции потерь (гессиана) напрямую перекликается с методами Ньютона и квазиньютоновскими методами, о которых шла речь в конце урока 285 применительно к обычной параметрической оптимизации, и с адаптивными методами вроде Adam из урока 293, где скорость шага тоже подстраивается под локальные свойства функции потерь, а не остаётся постоянной.

С уроком 317 (Random Forest) этот урок ведёт прямое сопоставление на протяжении всего материала: оба алгоритма — ансамбли деревьев решений (урок 316), но с диаметрально разными стратегиями построения и диаметрально разным характером переобучения — Random Forest снижает разброс через независимое усреднение, градиентный бустинг снижает смещение через последовательную коррекцию, и именно поэтому у них разная чувствительность к гиперпараметрам и разная форма кривой валидационной ошибки. Разбор переобучения бустинга напрямую продолжает урок 304 (переобучение и недообучение) и урок 306 (кросс-валидация): ранняя остановка по валидационной выборке — конкретное практическое применение той же самой идеи «оценивать модель не на тех данных, на которых она обучалась».

Этим уроком завершается блок классических моделей машинного обучения курса (уроки 310–318): от линейной и полиномиальной регрессии, через регуляризацию, логистическую регрессию, метод ближайших соседей и наивный байесовский классификатор — к деревьям решений, случайному лесу и, наконец, градиентному бустингу как самой мощной и требовательной модели этого блока. Дальше курс переходит к методу опорных векторов (урок 319) — модели с принципиально иной геометрической идеей, основанной на максимизации отступа между классами, а не на ансамблировании деревьев.

Интересные факты

• Строка, которая выводит финальное предсказание практически любой промышленной модели градиентного бустинга, суммирует вклад сотен или тысяч отдельных деревьев, каждое из которых по отдельности предсказывает жалкие доли процента точности, — но именно тысячи маленьких, аккуратно взвешенных поправок в сумме и дают модель, способную обгонять куда более сложные архитектуры на табличных данных.

• Алгоритм AdaBoost 1995 года, предшественник современного градиентного бустинга, был удостоен премии Гёделя (Gödel Prize) в 2003 году — одной из самых престижных наград в теоретической информатике, присуждаемой за выдающиеся работы в области теории вычислений.

• Названия всех трёх популярных библиотек отражают их главный инженерный приоритет: XGBoost («Extreme Gradient Boosting») — доведённая до предела производительность и регуляризация, LightGBM («Light Gradient Boosting Machine») — облегчённость и скорость на больших данных, CatBoost («Categorical Boosting») — прямое указание на специализацию по категориальным признакам.

• На множестве крупных соревнований по табличным данным на Kaggle в середине 2010-х годов подавляющее большинство призовых решений включало хотя бы одну из библиотек градиентного бустинга — настолько заметная доминация одного семейства алгоритмов в открытых соревнованиях по машинному обучению встречается редко.

Лайфхаки

• Начинай настройку бустинга не с малого learning rate, а с относительно крупного (например, $\eta=0{,}1$) и небольшого числа деревьев — так эксперименты идут быстро; после того как найдена разумная комбинация остальных гиперпараметров (глубина, регуляризация), уменьшай $\eta$ и пропорционально увеличивай число деревьев для финальной, более точной версии модели.

• Всегда используй раннюю остановку (early_stopping_rounds в XGBoost/LightGBM/CatBoost) вместо того, чтобы вручную угадывать число деревьев, — она автоматически находит близкое к оптимальному значение $M^\*$ по отдельной валидационной выборке и экономит и время обучения, и риск переобучения.

• Если признаков много и часть из них категориальные с большим числом уникальных значений, попробуй CatBoost первым — встроенная обработка категорий часто сразу даёт результат не хуже, чем ручная возня с target encoding и связанными с ним рисками утечки данных.

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

• Если данных очень много (миллионы строк) и обучение XGBoost занимает неприемлемо долго, попробуй LightGBM — гистограммное разбиение и GOSS часто дают в несколько раз более быстрое обучение при сопоставимом итоговом качестве.

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

Этим уроком закрывается большой блок классических моделей машинного обучения курса — от простой линейной регрессии, которая просто проводит прямую через облако точек, до градиентного бустинга, который последовательно, дерево за деревом, выжимает из данных всё, что только можно выжать. Пройденный путь не случаен: каждая следующая модель в этом блоке решала конкретное ограничение предыдущей — регуляризация справилась с переобучением линейных моделей, логистическая регрессия перенесла эту же идею на классификацию, деревья решений добавили способность улавливать нелинейные и пороговые зависимости, случайный лес научил деревья работать сообща через усреднение, а градиентный бустинг показал, что сообща работать можно ещё умнее — не голосованием, а последовательным исправлением общих ошибок. Теперь, глядя на любую новую задачу с табличными данными, ты понимаешь не только «какую модель выбрать», но и почему именно она подходит лучше других — а это понимание гораздо ценнее, чем умение вызвать .fit() у случайно выбранного класса из библиотеки.