CatBoost, XGBoost и выразительная способность решающих деревьев21.01.2022 15:47

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

Данный обзор охватывает сразу несколько тем. Мы начнем с устройства решающего дерева и градиентного бустинга, затем подробно поговорим об XGBoost и CatBoost. Среди основных особенностей алгоритма CatBoost:

Упорядоченное target-кодирование категориальных признаков с большим числом значений (параметр one_hot_max_size)
Использование решающих таблиц (параметр по умолчанию grow_policy='SymmetricTree')
Разделение ветвей не только по отдельным признакам, но и по их комбинациям (параметр max_ctr_complexity)
Упорядоченный бустинг (параметр boosting_type='Ordered') для датасетов небольшого размера
Возможность работы с текстовыми признаками (параметр text_features метода fit) с помощью bag-of-words
Возможность обучения на GPU (параметр task_type='GPU' в методе fit), хотя это может сказаться на качестве

В конце обзора поговорим о методах интерпретации решающих деревьев (MDI, SHAP) и о выразительной способности решающих деревьев. Удивительно, но ансамбли деревьев ограниченной глубины, в том числе CatBoost, не являются универсальными аппроксиматорами: в данном обзоре приведено собственное исследование этого вопроса с доказательством (и экспериментальным подтверждением) того, что ансамбль деревьев глубины N не способен сколь угодно точно аппроксимировать функцию $y = x_1 x_2 \dots x_{N+1}$ . Поговорим также о выводах, которые можно из этого сделать.

Содержание

Структура решающих деревьев
Обучение решающих деревьев
    Построение решающего дерева
    Оптимальное разделение в задаче регрессии
    Оптимальное разделение в задаче классификации
    Критерий остановки и обрезка дерева
    Работа с категориальными признаками
    Другие особенности решающих деревьев
Ансамблирование решающих деревьев
    Бэггинг
    Бустинг
    Ранний вариант бустинга: AdaBoost
    Градиентный бустинг
    Алгоритм градиентного бустинга
    Регуляризация градиентного бустинга
    Особенности градиентного бустинга
    Связь с градиентным спуском
XGBoost
CatBoost: несмещённый упорядоченный бустинг
    Упорядоченное target-кодирование
    Использование решающих таблиц
    Проблема смещённости бустинга
    Упорядоченный бустинг
    Алгоритм CatBoost
    Комбинирование признаков в CatBoost
    Обзор некоторых параметров CatBoost
Интерпретация ансамблей решающих деревьев
    Оценка важности признаков в решающих деревьях
    SHAP values
Выразительная способность ансамблей решающих деревьев
    Понятие выразительной способности
    Выразительная способность решающего дерева
    Выразительная способность ансамбля решающих деревьев
    Выводы и эксперименты
Список источников

Структура решающих деревьев

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

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

Рис. 1. Пример решающего дерева для задачи бинарной классификации. Принятие решения начинается с верхней вершины графа (корня).

Модели такого вида появились больше полувека назад (Morgan and Sonquist, 1963), и с тех пор практически не изменились. В наши дни одни из наиболее эффективных моделей машинного обучения для работы с табличными данными (scikit-learn, XGBoost, LightGBM, CatBoost) основаны на суммировании предсказаний множества решающих деревьев.

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

Позитивный пример. Многие способы принятия решений выглядят как блок-схема. Например при постановке диагноза врач сначала может измерить температуру. Если температура выше определенного порога, то может заподозрить простуду и посмотреть горло, послушать легкие и так далее. Листьями решающего дерева окажутся конкретные диагнозы. В целом, решающее дерево хорошо следует идее о том, что на некоторые признаки нужно обращать внимание только при условии определенных значений других признаков.

Негативный пример. Попробуем аппроксимировать функцию y(x) = x_2 - x_1 (рис. 2a) решающим деревом (рис. 2b). Решающее дерево разбивает все пространство признаков на прямоугольные области, в каждой из которых ответом является константа. В данной задаче такой подход явно неоптимален. Во-первых, если решающее дерево представить в виде функции f(x) , то эта функция будет разрывной (кусочно-постоянной), тогда как целевая функция y(x) непрерывна. Во-вторых, на ответ влияет разность x_2 - x_1 , а в каждом звене дерева проверяется либо x_1 , либо x_2 , что тоже неоптимально. Для достижения хорошей точности потребуется большое и сложное дерево, хотя сама задача определения очень проста. И наконец, поскольку решающее дерево обучается на данных (о способе обучения мы поговорим далее), то в тех областях, где мало данных или они вовсе отсутствуют, функция f(x) будет продолжена неправильно (проблема экстраполяции).

Рис. 2. Приближение непрерывной функции одним решающим деревом и ансамблем решающих деревьев.

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

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

While deep learning models are more appropriate in fields like image recognition, speech recognition, and natural language processing, tree-based models consistently outperform standard deep models on tabular-style datasets where features are individually meaningful and do not have strong multi-scale temporal or spatial structures. (Lundberg et al., 2019)

Обучение решающих деревьев

Допустим мы имеем обучающую выборку из пар $\{x_i, y_i\}_{i=1}^N$ и хотим построить по нему решающее дерево. Можно без труда построить сколько угодно деревьев, дающих на обучающей выборке 100%-ю точность (если в ней нет примеров с одинаковыми , но разными ). Для этого достаточно в каждой вершине выбирать для разделения любой признак и любой порог, и тогда рано или поздно все примеры попадут в разные листья. Но нам важна не точность на обучающей выборке, а степень обобщения — то есть точность на всем порождающем распределении, из которого взята обучающая выборка.

Можно воспользоваться принципом бритвы Оккама, который говорит, что простые гипотезы предпочтительнее сложных, и попробовать построить как можно более простое дерево. Однако задача нахождения наиболее простого решающего дерева для данного датасета (по суммрному количеству листьев или по средней длине пути в графе) является NP-полной (Hancock et al., 1996; Hyafil and Rivest, 1976), то есть (если $P \neq NP$ ) экспоненциально сложной.

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

Примечание: пока работаем с количественными признаками, работу с категориальными признаками рассмотрим позднее.

Построение решающего дерева

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

Лист , который заменяем решающим правилом
Способ разделения (признак и порог)
Значения и $C^\prime$ на двух новых листьях

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

Шаг алгоритма выглядит следующим образом: мы перебираем все возможные листья, признаки и пороги (если обучающая выборка имеет размер , то каждый признак принимает не более различных значений, поэтому для каждого признака имеет смысл перебирать не более N-1 порогов). Для каждого листа, признака и порога определяем значения и $C^\prime$ на листьях и считаем функцию потерь получившегося дерева. В итоге мы выбираем тот лист, признак и порог, для которых значение функции потерь наименьшее, и дополняем дерево новым разделяющим правилом.

Осталось ответить на вопрос: как именно определяются значения и $C^\prime$ на двух новых листьях?

Пусть после добавления разделяющего правила в один лист попало N_1 примеров со значениями целевого признака $y_1, \dots, y_{N_1}$ , в другой лист попало N_2 примеров со значениями целевого признака $y^\prime_1, \dots, y^\prime_{N_2}$ . Запишем суммарную функцию потерь после разделения, и минимизируем ее по и $C^\prime$ :

$\sum\limits_{i=1}^{N_1} {Loss}(y_i, C) + \sum\limits_{i=1}^{N_2} {Loss}(y^\prime_i, C^\prime) \to \underset{C, C^\prime}{\min} \tag{1}$

Первое слагаемое зависит только от , второе только от $C^\prime$ , поэтому их можно минимизировать независимо по и $C^\prime$ , если известны примеры, попавшие в один и в другой лист.

Оптимальное разделение в задаче регрессии

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

$\sum\limits_{i=1}^{N_1} (C - y_i)^2 \to \underset{C}{\min}$

Поскольку y_i — константы, то задача означает поиск минимума функции от одной переменной. Взяв производную и приравняв ее к нулю мы найдем, что — среднее арифметическое значений y_i . Аналогично, $C^\prime$ — среднее арифметическое значений $y_i^\prime$ .

Если бы мы минимизировали не среднеквадратичную ошибку (MSE), а среднюю абсолютную ошибку (MAE), тогда оптимальным значением была бы медиана значений y_i .

Оптимальное разделение в задаче классификации

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

Минимизируем суммарную ошибку на первом листе. Количество примеров в первом листе, для которых верным ответом является класс , равно N_1 p_k . Суммируем ошибку по всем классам и будем искать минимум по $C_1, \dots, C_K$ :

$- \sum\limits_{k=1}^{K} N_1 p_k \log C_k \to \underset{C_1, \dots, C_K}{\min} \qquad \sum\limits_{k=1}^{K} C_k = 1$

Из данной формулы можно исключить N_1 , и тогда задача нахождения оптимального распределения C_k сводится к минимизации перекрестной энтропии между распределениями p_k и C_k . Это эквивалентно минимизации расхождения Кульбака-Лейблера между p_k и C_k и достигается при p_k = C_k для всех . Полученный результат интуитивно понятен: если, например, в листе 10% примеров класса 0 и 90% примеров класса 1, то предсказывая ответ для неизвестного примера оптимальным вариантом будет назначить классам вероятности 10% и 90%.

Таким образом, мы нашли, что оптимальное C_k равно p_k . Суммарная функция потерь на обоих листьях будет равна:

$- N_1 \sum\limits_{k=1}^{K} p_k \log p_k - N_2 \sum\limits_{k=1}^{K} p_k^\prime \log p_k^\prime = N_1 H(p_k) + N_2 H(p_k^\prime)$

Здесь H(p_k) — энтропия распределения p_k (ее более корректно записывать как $H(\{p_k\}_{i=1}^{K})$ ). Иными словами, нам нужно искать такой признак и порог, чтобы минимизировать взвешенную сумму энтропий распределений классов в обоих листьях. Энтропию можно интерпретировать как степень неопределенности, или «загрязненности» (impurity) распределения, и энтропия достигает минимума в том случае, если распределение вероятностей назначает вероятность 1 одному из классов.

Минимизация взвешенной суммы энтропий называется энтропийным критерием разделения (рис. 3). Интересно, что если мы будем минимизировать не кроссэнтропию, а среднюю абсолютную ошибку (MAE) между предсказанным распределением C_k и истинным (эмпирическим) распределением, которое назначает вероятность 1 верному классу, то придем к критерию Джини:

$N_1 \sum\limits_{k=1}^{K} p_k (1 - p_k) + N_2 \sum\limits_{k=1}^{K} p_k^\prime (1 - p_k^\prime) \to \min$

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

Рис. 3. Распределение классов до и после разделения. Второй способ разделения (c) дает больший выигрыш по энтропийному критерию, чем первый способ (b). Рис. 3. Распределение классов до и после разделения. Второй способ разделения © дает больший выигрыш по энтропийному критерию, чем первый способ (b).

Критерий остановки и обрезка дерева

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

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

Рис. 3. Обучение решающих деревьев в зависимости от максимального количества листьев.

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

На рис. 4а показана ситуация, когда добавление первого оптимального разделяющего правила не приведет к значимому снижению ошибки классификации, тогда как следующие два разделяющих правила ведут к радикальному снижению функции потерь. Более того, оптимальное значение порога для первого разделяющего правила сильно зависит от случайных факторов и может быть выбрано не равным нулю. На этом примере мы видим ситуацию «отложенного выигрыша», когда жадный алгоритм построения дерева может сработать не лучшим образом (см. также Biau et al., 2008, раздел 6).

Рис. 4. Первое решающее правило не даст выигрыша в точности. Рис. 4. Первое решающее правило не даст выигрыша в точности.

Обрезкой решающего дерева (pruning) называется процесс удаления из него отдельных ветвей, которые не приводят к существенному падению функции потерь. Имеел ли смысл сначала строить, а затем удалять ветви? Как мы увидели на рис. 4, при построении ветви мы не можем точно сказать, насколько сильно эта ветвь и дочерние к ней ветви помогут снизить функцию потерь. Это станет понятно только тогда, когда мы построим дочерние ветви, затем дочерние к дочерним и так далее. Если даже после этого функцию потерь на данной ветви не удалось сушественно снизить, тогда всю ветвь можно удалить, упростив дерево. См. также Соколов, 2018, раздел 5.

Работа с категориальными признаками

До сих пор мы рассматривали работу только с количественными признаками. Если в обучающей выборке примеров, то в количественном признаке имеет смысл перебирать не более N-1 значений порога. Теперь рассмотрим категориальный признак с категориями. Можно разделить все категории на два подмножества, и отправить эти подмножества в разные ветви. Но количество возможных делений всех категорий на два подмножества растет экспоненциально с ростом количества категорий , что делает невозможным полный перебор при большом .

Есть два достаточно простых пути. Мы можем закодировать категориальный признак one-hot кодированием. Тогда если по этому признаку произойдет деление, то одна категория отправится в одву ветвь, все остальные в другую, то есть мы ищем только деления вида «одина категория против всех». Также мы можем оставить признаки в label-кодировании и рассматривать их как количественный признак, тогда в одну из ветвей отправятся все категории, индексы которых меньше определенного числа. Такие деления получаются менее осмысленными, но из этого напрямую не следует, что эффективность такого подхода будет ниже. Могут быть и другие подходы, например мы можем перебрать какое-то количество случайных делений всех категорий на два подмножества или упорядочить категории по среднему значению целевой переменной и искать разбиение как для количественного признака (см. Соколов, 2018, раздел 7).

На практике установлено, что для категориальных признаков небольшой размерности (т. е. с небольшим количеством категорий) лучше работает one-hot кодирование (см. Prokhorenkova et al., 2017). Для признаков большой размерности можно тоже применять one-hot кодирование, хотя если сделать это в явном виде, то получившаяся матрица признаков будет занимать очень много места в памяти. Более эффективным подходом к работе с категориальными признаками большой размерности считается target-кодирование.

При target-кодировании мы заменяем каждую категорию некой статистикой (обычно средним значением) целевой переменной, рассчитанной по объектам данной категории. Например, если категориальной переменной является модель автомобиля, а целевым признаком является цена, то мы рассчитываем среднюю цену по каждой модели, и используем полученные данные вместо модели автомобиля.

Данный подход имеет два недостатка. Во-первых, представим, что в каждой категории только один объект. Тогда после target-кодирования признак будет содержать готовые ответы. Модели, обучаемой на этом датасете, будет достаточно извлекать ответ из этого признака, не используя никакие другие признаки. Очевидно, такой подход приведет к переобучению. Как вариант, можно использовать две обучающие выборки: на первой расссчитывать статистику по целевой переменной, а на второй с помощью этой статистики делать target-кодирование и обучать модель.

Вторая проблема в том, что категориальные признаки могут влиять на целевой признак не независимо друг от друга. Например, пусть мы имеем два категориальных признака в label-кодировани, принимающие значения 0 или 1: если они не равны друг другу, то целевой признак равен 1, в противном случае целевой признак равен 0. Если мы выполним target-кодирование, то эта информация будет полностью утеряна.

Несмотря на эти недостатки, target-кодирование и его различные варианты остается одним из самых эффективных способов работы с категориальными признаками высокой размерности. Авторы библиотеки CatBoost разработали метод упорядоченного target-кодирования, при котором на обучающих примерах задается некий порядок, и для каждого -го примера статистика по целевой переменной рассчитывается только на основе примеров с индексами меньше (см. далее в разделе «CatBoost: несмещённый упорядоченный бустинг»). Обзор различных способов target-кодирования также можно найти в Pargent et al., 2021.

Другие особенности решающих деревьев

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

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

Ансамблирование решающих деревьев

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

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

Существует также стекинг, при котором предсказания одной модели используются в качестве входных данных для другой модели. Однако распространенные алгоритмы ансамблирования решающих деревьев (random forest, XGBoost, LightGBM, CatBoost) не включают в себя стекинг. Стекинг может выполняться поверх этих моделей, так же как и поверх любых других (нейронных сетей и пр.).

Бэггинг

Алгоритм бэггинга достаточно прост: каждое дерево обучается на своей подвыборке данных, взятой из обучающей выборки. Подвыборка делается с возвращением, то есть один пример может быть выбран более одного раза. Если при этом в каждом дереве мы также будем использовать случайную подвыборку признаков, то получим алгоритм построения случайного леса, реализованный, например, в sklearn. Можно внести еще больше случайности в процесс ансамблирования, если процесс построения дерева также будет содержать элементы случайности (см. Extremely Randomized Trees).

Бустинг

Более распространенным методом ансаблирования решающих деревьев является бустинг. Бустинг — это способ построения ансамбля, в котором обучается много копий более слабой модели («weak learner»), то есть такой модели, которая не может достичь высокой точности на обучающем датасете, переобучившись на нем. Как правило такой моделью является решающее дерево небольшой глубины. На каждом шаге новый weak learner концентрируется на исправлении ошибок, допущенных предыдущими weak learner’ами. В итоге предсказания всех weak learner’ов суммируются с определенными весами. Бустинг чем-то похож на бэггинг, но в бэггинге модели обучаются совершенно независимо и параллельно, а в бустинге последовательно, с оглядкой на предыдущие.

Ранний вариант бустинга: AdaBoost

Итак, в бустинге каждый следующий weak learner стремится скорректировать предсказания предыдущих. Это можно сделать разными способами. Одной из первых эффективных реализаций бустинга был AdaBoost — в нем каждый следующий weak learner фокусировал внимание на тех примерах, на которых предыдущие weak learner’ы дали неверные ответы. При этом он не знал, какие именно ответы даны предыдущими weak learner’ами — было лишь известно, что ответы неверны или неточны. Задачей нового weak learner’а было дать верные ответы преимущественно на этих примерах.

Заметим, что при этом не используется никакого валидационного датасета. Используется только обучающий датасет, на нем же оценивается точность предыдущих weak learner’ов. Это означает, что если очередной weak learner после обучения дал верные ответы на все примеры, то бустинг продолжить будет невозможно. Например, если в качестве weak learner’а мы используем решающее дерево неограниченной глубины, то так и произойдет. Нужно использовать решающие деревья небольшой глубины: weak learner должен быть действительно «слабым», не переобучаясь слишком сильно.

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

В градиентном бустинге (Friedman, 2001) целевыми данными для следующего weak learner’а является градиент (со знаком минус) функции потерь по предсказаниям предыдущих алгоритмов. Таким образом следующий weak learner корректирует предсказания предыдущих.

Например, производная среднеквадратичной ошибки $(y - \hat{y})^2$ по $\hat{y}$ равна $2(\hat{y} - y)$ , а значит предсказывая градиент weak learner как раз и предсказывает разность предсказания и правильного ответа. Но можно использовать и другие функции потерь.

Далее рассмотрим алгоритм градиентного бустинга более формально. Для дальнейшего изложения введем необходимые обозначения:

Алгоритм градиентного бустинга

Пусть мы имеем обучающую выборку, обучаемый алгоритм (weak learner) и функцию потерь. В качестве исходного приближения выберем константу так, чтобы сумма $\sum_{i=1}^n loss(y_i, C)$ была минимальна. К начальному приближению мы будем прибавлять предсказания weak learner’ов.
Заранее выберем число шагов .

for k = 0, …, N-1:

На -м шаге мы уже обучили weak learner’ов. Мы получаем предсказания с помощью их взвешенной суммы для всех примеров из обучающего датасета: $\hat{y}_i = С + \sum\limits_{j=0}^k w_i f(x_i, \theta_j)$
Считаем производную функции потерь со знаком минус по каждому предсказанию: $r_i = -\cfrac{\partial}{\partial \hat{y}_i} loss(y_i, \hat{y}_i)$ . Таким образом мы получаем информацию о том, как нам нужно изменить каждое предсказание, чтобы функция потерь уменьшилась (исходя из смысла понятия производной).
Обучаем новый weak learner предсказывать по . Обозначим параметры нового weak learner’а за $\theta_k$ .
Осталось выбрать вес для нового weak learner’а. Для этого получаем предсказания нового weak learner’а на всей обучающей выборке: $\hat{r}_i = f(x_i, \theta_k)$ . Затем подбираем такой вес , чтобы значение $sum\_loss(\mathbf{y}, \hat{\mathbf{y}} + w_k*\hat{\mathbf{r}})$ было минимально.

В итоге мы получаем ансамбль из weak learner’ов. Алгоритм инференса (то есть предсказания на произвольных данных) выглядит аналогично:

$\hat{y} = С + \sum_{j=0}^N w_i f(x, \theta_j)$

Про градиентный бустинг см. также в этом посте на Хабре.

Регуляризация градиентного бустинга

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

Subsampling. Мы обучаем каждый следующий weak learner не на всей обучающей выборке, а на случайной подвыборке. В этом случае градиентный бустинг называется стохастическим.

Shrinkage. После того, как мы расчитали вес нового weak learner’а w_k , мы умножаем его на некоторое число меньше 1 (learning ra