Разбираемся в ML без воды: от базы до Attention. Часть 11: Градиентный бустинг

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

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

Градиентный бустинг

Для начала рассмотрим пример. Представьте, что мы готовим студентов к экзамену по машинному обучению, но у нас жесткое ограничение — мы выдаем материал порциями ровно по 1 часу.

На первом часе мы бегло читаем лекцию обо всем понемногу. Проводим пробный тест: студенты хорошо ответили про линейную регрессию, но полностью провалили SVM и KNN.

Мы понимаем, где ошиблись, и на втором часе не повторяем регрессию, а тратим всё время строго на SVM. На следующем тесте студенты знают уже две темы, но всё ещё «плавают» в KNN. Тогда на третьем часе мы прицельно разбираем KNN.

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

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

Для начала в качестве базового алгоритма рассмотрим самый популярный на практике вариант — деревья решений.

Представим, что мы хотим приблизить неизвестную функцию

Через последовательное приближение вида

$F_M(x) = \sum_{m=0}^{M}\gamma_mh_m(x)$

где
— очередное дерево,
$\gamma_m$ — его вес,
— число итераций.

Как это происходит:

Шаг 1

В начале никакого дерева нет. Для мы берем некоторое значение, например среднее по таргету. Мы хотим уменьшить ошибку. И у нас есть два варианта:

Обучение на остатках
Здесь всё крайне просто. Мы оцениваем разность между истинным значением предсказанием , то есть , строим дерево на данных и называем его .
Метод обучения на остатках хорош, но остатки — это частный случай отрицательного градиента функции потерь.
Функциональный градиентный спуск

Вспомним как выглядит обычный градиентный спуск:

$\omega_{new}= \omega−\eta\nabla L$

Разница будет только в том, что у нас нет параметров, есть лишь сама функция . Поэтому посчитаем градиент относительно значений функции:

$g_i = \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}$

И антиградиент будет .

К слову для MSE $\left(L = \frac{1}{2}(y-F)^2\right)$ получим а значит ,

то есть, то же самое, что и для обучения на остатках. Именно поэтому многие думают, что бустинг обучается на ошибках. Но на самом деле это частный случай. Он обучается на антиградиентах

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

Шаг 2

Нам нужно понять, насколько мы доверяем каждому из наших 100500 деревьев. Для этого решаем задачу

$\gamma_m = \arg\!\min_{\gamma}\sum_{i}L(y_i,F_{m-1}(x_i) + \gamma h_m(x_i))$

Для MSE эта задача решается аналитически. Перепишем её для MSE и выведем решение.

$\gamma_m = \arg\!\min_{\gamma} \sum_{i=1}^{n}\frac{1}{2}\bigg(y_i - (F_{m-1}(x_i) + \gamma h_m(x_i))\bigg)^2$

Чтобы найти минимум, возьмем производную по целевой переменной $\gamma$ и приравняем её к нулю:

$\frac{\partial}{\partial \gamma}\sum_{i=1}^{n}\frac{1}{2}\bigg(y_i - F_{m-1}(x_i) + \gamma h_m(x_i)\bigg)^2 = 0$

Немного посчитав и упростив, получим:

$\sum_{i=1}^{n}\bigg(-(y_i - F_{m-1}(x_i))h_m(x_i) - \gamma h_m(x_i)^2\bigg) = 0$

Заметим, что $y_i - F_{m-1}(x_i)$ — это не что иное, как обычный остаток, который мы ранее обозначили как $r_{i}$ . Перепишем уравнение:

$\sum_{i=1}^{n}\Big(-r_{i}h_{m}(x_{i})+\gamma h_{m}(x_{i})^{2}\Big)=0$

Отсюда легко выразить $\gamma$ :

$\gamma = \frac{\sum_{i=1}^{n}r_{i}h_{m}(x_{i})}{\sum_{i=1}^{n}h_{m}(x_{i})^{2}}$

Как это работает на пальцах

Пусть у нас есть всего 3 объекта, для которых мы знаем истинные значения таргета : $y_1 = 1, \ y_2 = 3, \ y_3 = 5$

Шаг 1. Базовое предсказание

Мы стартуем с константы — берем среднее по таргету:

$F_0(x) = \frac{1 + 3 + 5}{3} = 3$

Начальные предсказания для всех трех объектов равны: $\{3, 3, 3\}$ .

Шаг 2. Вычисляем остатки

Итак,:
, , . Таким образом мы получили остатки: $\{-2, 0, 2\}$ .

Именно на этих значениях мы строим новое дерево решений. Новое дерево выдает прогнозы . Дерево не всегда может идеально повторить остатки. Допустим, после обучения на векторе $\{-2, 0, 2\}$ наше дерево выдало следующие прогнозы для объектов:,,.

Вектор предсказаний дерева: $\{-1, 0, 1\}$ .

Шаг 3. Считаем оптимальный вес дерева $\gamma_1$

Применяем выведенную выше формулу:

$\gamma_1 = \frac{\sum r_i h_1(x_i)}{\sum h_1(x_i)^2}$

Считаем числитель (перемножаем реальные остатки на прогнозы дерева и складываем):

$(-2 \cdot -1) + (0 \cdot 0) + (2 \cdot 1) = 2 + 0 + 2 = 4$

Считаем знаменатель (возводим прогнозы дерева в квадрат и складываем):

3. Делим числитель на знаменатель: $\gamma_1 = \frac{4}{2} = 2$ .

Итог: Оптимальный вес для этого дерева равен 2. Теперь мы можем применить его и обновить наш ансамбль:

$F_1(x) = F_0(x) + 2 \cdot h_1(x)$

Посмотрим, какими стали новые предсказания для наших объектов:

Для 1-го: $3 + 2 \times (-1) = 1$
Для 2-го: $3 + 2 \times 0 = 3$
Для 3-го: $3 + 2 \times 1 = 5$

Таким образом MSE в данном примере идеально упала до нуля.

На других лосс-функций, аналитического решения чаще всего не существует. В таких случаях используют численный поиск.

Шаг 3

Обновляем ансамбль:

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

где $\eta$ — learning rate. Дальше повторяем процесс заново.

При большом значении $\eta$ модель может подстраиваться под шум. Потому обычно на практике берут маленький learning rate и большое количество деревьев. Сами деревья, как правило, делают неглубокими (max_depth = 3-10): цель дерева состоит в исправлении локальной ошибки, а не решать всю задачу целиком. Такие деревья называются слабыми учениками

Если посмотрим на весь процесс сверху вниз, можно дать ему очень красивую интерпретацию:

Мы находимся в пространстве функций $\mathbb{F}$ , а точнее в некотором $\mathbb{F}_B$ , вложенного в него (пространство базовых моделей).

Антиградиент показывает, при каком выборе $F \in \mathbb{F}$ лосс уменьшиться быстрее всего. Но поскольку мы находимся в $\mathbb{F}_B$ , мы ищем базовую модель (дерево), максимально похожее на этот антиградиент.

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

MSE даёт нам регрессионный бустинг;
LogLoss даёт бинарную классификацию;
Другая функция потерь даст другую модель.

Деревья не меняются, меняется функция, чья антиградиент они пытаются апроксимировать.

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

Ньютоновский бустинг

Тот алгоритм градиентного бустинга, который мы разобрали выше, использует разложение функции потерь в ряд Тейлора только до первого члена (первой производной). По сути, на каждой итерации мы аппроксимируем направление спуска, а затем отдельно подбираем шаг $\gamma _{m}$ с помощью одномерного поиска (argmin).

Но можно использовать информацию не только о направлении спуска, но и о кривизне самой функции потерь. Для этого рассмотрим разложение Тейлора до второго члена включительно.

На каждой итерации мы хотим найти такую поправку в виде нового дерева , которая минимизирует лосс. Разложим функцию потерь для одного объекта в окрестности текущего предсказания $F_{m-1}(x_i)$ :

$L\big(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i})\big) \approx L\big(y_{i},F_{m-1}(x_{i})\big)+g_{i}h_{m}(x_{i})+\frac{1}{2}h_{i}h_{m}(x_{i})^{2}$

Где:

$g_i = \frac{\partial L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}$

первая производная (градиент), которая говорит, куда падает функция.

$h_i = \frac{\partial^2 L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)^2}$

вторая производная (гессиан), которая показывает скорость изменения градиента (кривизну поверхности).

Важное примечание по обозначениям: не путайте гессиан объекта $h_{i}$ и функцию самого дерева .

Теперь просуммируем этот лосс по всей выборке. Наша задача — найти такое дерево , которое минимизирует эту аппроксимацию. Константное слагаемое $L\big(y_i, F_{m-1}(x_i)\big)$ от самого дерева не зависит, поэтому его можно выкинуть из задачи оптимизации:

$\sum_{i=1}^{n}\left[g_{i}h_{m}(x_{i})+\frac{1}{2}h_{i}h_{m}(x_{i})^{2}\right]\rightarrow \min_{h_{m}}$

Если вспомнить, что дерево выдает константные предсказания $w_{j}$ для каждого своего листа $j = 1, \dots, J$ , мы можем переписать эту сумму по листьям. Обозначим за $I_{j}$ множество индексов объектов, попавших в лист . Тогда задача для каждого отдельного листа превращается в обычную квадратичную параболу относительно веса листа $w_{j}$ :

$\sum_{i\in I{j}}g_{i}w_{j}+\frac{1}{2}\sum_{i\in I{j}}h_{i}w_{j}^{2}\rightarrow \min_{w_{j}}$

Как известно, минимум параболы $f(w) = B w + \frac{1}{2} A w^2$ находится в её вершине и вычисляется как .

Дифференцируем по $w_{j}$ , приравниваем к нулю и получаем аналитическую формулу для оптимального веса в листе:

$w_{j}^{*}=-\frac{\sum_{i\in I{j}}g_{i}}{\sum_{i\in I{j}}h_{i}}$

Именно этот математический трюк лег в основу «большой тройки» современного машинного обучения: XGBoost, LightGBM и CatBoost. Рассмотрим, в чем выгода:

Больше никакого argmin: Алгоритму больше не нужно делать итерационные численные поиски оптимального шага для сложных лосс-функций. Достаточно посчитать первые и вторые производные для объектов в листе, сложить их и поделить друг на друга. Оптимальный вес листа находится ровно за одну операцию деления;
Умный выбор сплитов: Подставив оптимальное значение $w_{j}^{*}$ обратно в уравнение лосса, получается формула так называемого структурного качества дерева (Gain). Модель строит дерево, выбирая такие сплиты по признакам, которые максимизируют этот Gain, завязанный на $g_{i}$ и $h_{i}$ ;
Встроенная регуляризация: В реальных библиотеках в знаменатель формулы веса листа сразу добавляется штраф за сложность дерева (L2-регуляризация ( $\lambda$ ):

$w_j = -\frac{\sum g_i}{\sum h_i + \lambda}\$

Если объектов в листе мало (сумма $h_{i}$ мала), а $\lambda$ большая, вес листа автоматически сжимается к нулю, защищая модель от переобучения.

XGBoost, LightGBM и CatBoost

Раз уж статья про градиентный бустинг, грех не упомянуть три метода градиентного бустинга, о которых слышали, наверное, все.

Математическое ядро у них общее. Однако каждая из этих трех библиотек завоевала признание за счет уникальных инженерных хаков вокруг того, как именно строить деревья и как обрабатывать признаки.

XGBoost

Первая библиотека, которая сделала ньютоновский бустинг массовым и параллельным.

Для построения дерева использует алгоритм Level-wise — дерево растет строго по уровням (слоями) горизонтально. Все узлы одного уровня делятся одновременно.

Главная фишка это алгоритм Sparsity-aware Split Finding. XGBoost на лету учится распределять пропущенные значения (NaN) в те ветки дерева, где они дают минимальную ошибку. За счет этого его не нужно предварительно очищать от пропусков.

LightGBM

Создан для работы с огромными датасетами, где XGBoost начинал тормозить.

Деревья строятся через алгоритм Leaf-wise — дерево растет вертикально. Алгоритм ищет один-единственный лист с максимальной ошибкой (Gain) по всей модели и разбивает только его, игнорируя уровни. Деревья получаются асимметричными, но сходятся в разы быстрее.

Фишка в GOSS (Gradient-based One-Side Sampling). Идея крайне проста: незачем считать градиенты для всей выборки, если большая часть объектов уже предсказывается хорошо. LightGBM оставляет объекты с большими градиентами (с больщой ошибкой), а объекты с маленькими градиентами берет случайной подвыборкой. Это снижает затраты памяти в разы почти без потери точности.

CatBoost

Пожалуй лучшее решение «из коробки», если в данных есть много категориальных признаков. Работает без предварительного One-Hot или Target encoding.

Для построение дерева использует Oblivious Trees (симметричные деревья). На каждом уровне дерева используется один и тот же признак и один и тот же сплит для всех узлов. Такое дерево менее склонно к переобучению и умеет быстро делать предсказания (на инференсе).

Главная фишка — Ordered Boosting. Классический бустинг считает градиент для объекта на основе модели, которая этот же объект видела при обучении базовых деревьев (что ведет к утечке данных и переобучению). CatBoost считает градиенты на основе случайных перестановок датасета, тем самым гарантируя, что таргет текущего объекта не влияет на расчет его собственного сдвига.

Какой из них выбрать?

При выборе одного из этих трех методов основное правило примерно такое:

Нужен быстрый базовый baseline на гигантских данных — LightGBM;
В датасете много категориальных фич — CatBoost;
Нужна проверенная стабильность и интеграция с GPU — XGBoost.

Заключение

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

На этом мы закрываем огромный блок, посвященный классическому машинному обучению и ансамблям. Мы разобрались с линейными моделями, метрическими алгоритмами, деревьями, бэггингом и бустингом.

В следующей части мы разберем несколько важных понятий (в основном понижение размерности), а дальше нас ждет самое интересное — погружение в мир глубокого обучения (Deep Learning).

ссылка на оригинал статьи https://habr.com/ru/articles/1047130/