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

Бэггинг и случайный лес из предыдущей заметки усредняют деревья, выращенные независимо. Усреднение сохраняет смещение отдельного дерева и снижает только его разброс, поэтому ему нужны глубокие деревья с малым смещением, и оно ничего не может сделать с систематической ошибкой, общей для всех деревьев. Бустинг (boosting) строит ансамбль наоборот. Деревья небольшие и выращиваются одно за другим, и каждое новое дерево подгоняется под то, в чём текущий ансамбль ещё ошибается. Тогда у суммы многих слабых деревьев смещение мало, а разброс контролируется тем, что каждый шаг делается малым и обучение вовремя останавливается. Фридман (2001) показал, что это градиентный спуск, выполняемый в пространстве функций, а не в пространстве параметров, и поэтому он работает для любой дифференцируемой функции потерь. Градиентный бустинг над деревьями в реализациях XGBoost, LightGBM и CatBoost — метод по умолчанию для табличных данных.

Обозначения. $L(y, F)$ — дифференцируемая функция потерь предсказания $F$ (числа: значения регрессии или логарифма шансов в классификации). Модель после $m$ шагов — $F_m(x) = F_0 + \nu \sum_{k=1}^m b_k(x)$ , где $F_0$ — лучшая константа, $b_k$ — регрессионное дерево (базовый алгоритм, base learner), а $\nu \in (0, 1]$ — шаг обучения (learning rate). На шаге $m$ величины $g_i = \partial L(y_i, F) / \partial F$ и $h_i = \partial^2 L(y_i, F) / \partial F^2$ вычисляются при $F = F_{m-1}(x_i)$ . У дерева с $J$ листьями области $R_1, \dots, R_J$ и значения в листьях $w_1, \dots, w_J$ .

Подгонка остатков#

Начнём с квадратичной функции потерь и константной модели $F_0 = \bar y$ . Её ошибки на обучающей выборке — остатки (residuals) $r_i = y_i - F_0$ . Дерево $b_1$ , подогнанное к остаткам методом наименьших квадратов, предсказывает, где модель слишком занижает и где слишком завышает, поэтому $F_1 = F_0 + \nu b_1$ ближе к данным; новые остатки $y_i - F_1(x_i)$ подгоняются деревом $b_2$ , и так далее. Игрушечный пример с четырьмя точками, $x = 1, 2, 3, 4$ и $y = 1, 3, 4, 8$ , пнями (stumps) и $\nu = 0.5$ : $F_0 = 4$ , остатки равны $-3, -1, 0, 4$ . Лучший пень разбивает между 3 и 4 и предсказывает $-4/3$ слева и $4$ справа, поэтому $F_1 = (3.333, 3.333, 3.333, 6)$ , а MSE на обучении падает с $6.5$ до $2.5$ . Ещё два пня доводят её до $1.139$ и $0.470$ .

Рисунок

Бустинг шаг за шагом

Квадратичная функция потерь, 50 точек y = sin 2πx + шум (σ = 0.3), пни (деревья глубины 1), шаг обучения 0.5. На панелях «остатки и пень b»: остатки yᵢ − Fₘ₋₁(xᵢ) (зелёные) и пень bₘ, подогнанный к ним методом наименьших квадратов (янтарный). На панелях «модель F»: модель Fₘ = Fₘ₋₁ + 0.5·bₘ (синяя) поверх данных и истинной функции (пунктир). Ошибка на обучении (MSE) после 1, 2, 5 и 40 шагов: 0.331, 0.223, 0.152, 0.055; последнее значение ниже шума σ² = 0.09 — модель уже начала запоминать шум.

На рисунке та же процедура применяется к 50 зашумлённым точкам синусоиды:

Первый пень делит остатки константной модели на положительную и отрицательную половины; к модели добавляется половина пня.
У остатков $F_1$ всё ещё есть явная форма, и второй пень подгоняется под неё.
После пяти шагов у модели шесть ступенек, и остатки малы.
После сорока модель следует синусоиде, а остатки похожи на шум. Если продолжить, бустинг подгонится и под этот шум: ошибка на обучении, $0.055$ , уже ниже дисперсии шума $0.09$ .

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

Градиентный спуск в пространстве функций#

Почему остатки и что заменяет их для других функций потерь? Функция потерь на обучении

Q(F) = \sum_{i=1}^n L\big(y_i, F(x_i)\big)

зависит от функции $F$ только через её $n$ значений $F(x_1), \dots, F(x_n)$ . Будем считать эти значения параметрами. Градиентный спуск по ним, как в заметке о градиентном спуске, сдвигает каждое значение против частной производной $Q$ :

F(x_i) \leftarrow F(x_i) - \eta \, g_i , \qquad g_i = \frac{\partial L(y_i, F)}{\partial F}\Big|_{F = F_{m-1}(x_i)} .

Для квадратичной функции потерь $L = \frac12 (y - F)^2$ антиградиент $-g_i = y_i - F_{m-1}(x_i)$ — ровно остаток: подгонка остатков и есть градиентный спуск. Но этот шаг определён только в обучающих точках, а модель должна предсказывать везде. Решение Фридмана — заменить вектор $-g$ ближайшей функцией из базового класса, подогнав дерево к псевдоостаткам (pseudo-residuals) $-g_i$ методом наименьших квадратов (Friedman, 2001, раздел 3, формула 11):

b_m = \arg\min_{b} \sum_{i=1}^n \big(-g_i - b(x_i)\big)^2 .

Почему этот шаг снижает функцию потерь? По разложению Тейлора первого порядка добавление $\varepsilon b$ меняет функцию потерь на

Q(F_{m-1} + \varepsilon b) - Q(F_{m-1}) \approx \varepsilon \sum_{i=1}^n g_i \, b(x_i) ,

и это изменение отрицательно и наиболее круто, когда вектор $(b(x_1), \dots, b(x_n))$ направлен вдоль $-g$ . Среди функций базового класса подгонка к $-g$ методом наименьших квадратов ближе всех к параллельности с ним — по словам Фридмана, это член класса, «сильнее всего коррелированный с $-g$ ». Дерево выбирает только направление; насколько далеко идти — отдельная одномерная задача. Для деревьев она решается в каждом листе отдельно, поскольку листья не пересекаются:

w_j = \arg\min_{w} \sum_{x_i \in R_j} L\big(y_i, F_{m-1}(x_i) + w\big) ,

и модель делает сжатый шаг $F_m = F_{m-1} + \nu \sum_j w_j [x \in R_j]$ . Это TreeBoost Фридмана, алгоритм 10.3 у Hastie, Tibshirani and Friedman (2009). Структура дерева выбирается по квадратичной ошибке на псевдоостатках, какой бы ни была функция потерь, а сама функция потерь входит дважды: в псевдоостатки и в значения в листьях.

Функции потерь#

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

Функция потерь $L(y, F)$	Псевдоостаток $-g$	Значение в листе	Предсказывает
квадратичная $\frac12 (y - F)^2$	$y - F$	среднее остатков	условное среднее
абсолютная $\lvert y - F \rvert$	$\operatorname{sign}(y - F)$	медиана остатков	условную медиану
Хьюбера (Huber)	остаток, обрезанный на уровне $\delta$	оценка положения Хьюбера по остаткам	робастное среднее
пинбол-функция (pinball) уровня $q$	$q$ или $q - 1$	$q$ -квантиль остатков	условный $q$ -квантиль
логистическая, $y \in \{0, 1\}$ , $p = \sigma(F)$	$y - p$	шаг Ньютона $\frac{\sum (y_i - p_i)}{\sum p_i (1 - p_i)}$	логарифм шансов
пуассоновская, $F = \log \mu$	$y - e^F$	$\log \frac{\sum y_i}{\sum e^{F_i}}$	логарифм среднего числа событий

Для логистической функции потерь $F$ — логарифм шансов, как в логистической регрессии, и $L = -y \log p - (1 - y) \log(1 - p)$ , где $p = 1/(1 + e^{-F})$ . Её производные по $F$ равны $g = p - y$ и $h = p(1 - p)$ , поэтому псевдоостаток — разность между меткой и предсказанной вероятностью. У значения в листе нет замкнутой формулы, и его заменяет один шаг Ньютона из $w = 0$ , $-\sum g_i / \sum h_i$ (Friedman, 2001, алгоритм 5, где он записан для $y \in \{-1, 1\}$ и половины логарифма шансов). Каждый псевдоостаток лежит в $(-1, 1)$ : сильно ошибочно классифицированная точка тянет с весом не больше единицы. Экспоненциальная функция потерь $e^{-yF}$ , $y \in \{-1, 1\}$ , даёт AdaBoost (Freund and Schapire, 1997; Friedman, Hastie and Tibshirani, 2000); её псевдоостатки $y \, e^{-yF}$ неограниченно растут на ошибочно классифицированных точках, что делает её чувствительной к шуму в метках (Hastie, Tibshirani and Friedman, 2009, раздел 10.6).

Сжатие шага, размер деревьев и подвыборки#

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

Сжатие шага (shrinkage). Шаг обучения $\nu$ масштабирует каждое дерево. Меньшему $\nu$ нужно больше деревьев, чтобы достичь той же функции потерь на обучении, и на практике он обычно даёт меньшую ошибку на тесте — это эмпирическая закономерность, а не теорема; рекомендуемая стратегия — малое $\nu$ , не больше $0.1$ , с числом деревьев, выбранным ранней остановкой (Friedman, 2001, раздел 5; Hastie, Tibshirani and Friedman, 2009, раздел 10.12.1). На функции Фридмана в 10 измерениях с 500 обучающими точками и деревьями глубины 3 при $\nu = 1$ лучшая MSE на валидации, $5.72$ , достигается после 8 деревьев, а после 1000 она равна $6.75$ ; при $\nu = 0.1$ достигается $2.71$ после 189 деревьев, с MSE на тесте $2.66$ .
Размер деревьев. Дерево с $J$ листьями может представить взаимодействия не более чем $J - 1$ признаков, и сумма таких деревьев тоже. Пни дают аддитивную модель. Опыт подсказывает $4 \le J \le 8$ (Hastie, Tibshirani and Friedman, 2009, раздел 10.11): у небольших деревьев большое смещение и малый разброс, а это то, что нужно бустингу, — противоположность глубоким деревьям леса.
Подвыборки (subsampling). Стохастический градиентный бустинг (stochastic gradient boosting) выращивает каждое дерево на случайной доле обучающих точек, выбранной без возвращения, обычно на половине (Friedman, 2002; Hastie, Tibshirani and Friedman, 2009, раздел 10.12.2). Он быстрее и часто точнее: как и в бэггинге, случайность выборок снижает разброс. В примере выше подвыборка половины строк снижает лучшую MSE на валидации с $2.71$ до $2.38$ . XGBoost добавляет подвыборку столбцов, заимствованную у случайного леса (Chen and Guestrin, 2016, раздел 2.3).

Бустинг второго порядка: XGBoost#

Градиентный бустинг подгоняет дерево по квадратичной ошибке на градиенте, и это приближение затем исправляет шаг в листьях. XGBoost (Chen and Guestrin, 2016) с самого начала строит дерево для настоящей функции потерь, используя разложение второго порядка, и добавляет штраф на дерево. Целевая функция на шаге $m$ —

\sum_{i=1}^n L\big(y_i, F_{m-1}(x_i) + b(x_i)\big) + \gamma J + \frac{\lambda}{2} \sum_{j=1}^J w_j^2 ,

с ценой $\gamma$ за лист и штрафом $L_2$ с коэффициентом $\lambda$ на значения в листьях (формула 2). Разложив функцию потерь до второго порядка по $b(x_i)$ и отбросив константу, получаем

\sum_{i=1}^n \Big[ g_i \, b(x_i) + \frac12 h_i \, b(x_i)^2 \Big] + \gamma J + \frac{\lambda}{2} \sum_j w_j^2 .

Дерево постоянно в каждом листе, $b(x_i) = w_j$ для $x_i \in R_j$ , поэтому при $G_j = \sum_{x_i \in R_j} g_i$ и $H_j = \sum_{x_i \in R_j} h_i$ целевая функция — сумма независимых парабол, $\sum_j [G_j w_j + \frac12 (H_j + \lambda) w_j^2] + \gamma J$ . Каждая минимизируется при

w_j^* = -\frac{G_j}{H_j + \lambda} , \qquad \text{со значением} \quad -\frac12 \sum_{j=1}^J \frac{G_j^2}{H_j + \lambda} + \gamma J

(формулы 5 и 6). Это значение оценивает структуру дерева, а прирост от разбиения узла на левую часть $L$ и правую часть $R$ — уменьшение этой оценки (формула 7):

\text{прирост} = \frac12 \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma .

Разбиение стоит делать, только если его прирост положителен, поэтому $\gamma$ действует как минимальный прирост, а $\lambda$ сжимает значения в листьях к нулю, сильнее в листьях с малой кривизной. Два частных случая связывают формулу с тем, что было раньше. Для квадратичной функции потерь $g_i = F_{m-1}(x_i) - y_i$ и $h_i = 1$ , поэтому $w_j^*$ — средний остаток листа, сжатый множителем $n_j / (n_j + \lambda)$ , а при $\lambda = \gamma = 0$ прирост — это уменьшение $\tfrac12 \sum_i r_i^2$ , половина уменьшения суммы квадратов остатков, критерий дисперсии из заметки о решающих деревьях. Для логистической функции потерь $w_j^*$ при $\lambda = 0$ — ньютоновское значение в листе из таблицы выше.

Разобранный пример с небольшими числами: один лист, логистическая функция потерь, текущий логарифм шансов 0, так что $p = 0.5$ , метки $1, 1, 0$ . Градиенты $p - y$ равны $-0.5, -0.5, 0.5$ , а каждая вторая производная (гессиан) равна $0.25$ , поэтому $G = -0.5$ и $H = 0.75$ . Без штрафа значение в листе равно $0.5/0.75 = 0.667$ , а приближение второго порядка к функции потерь уменьшается на $\frac12 \cdot 0.25/0.75 = 0.167$ ; точная логистическая функция потерь уменьшается на $0.170$ — близко, но не то же самое. При $\lambda = 1$ значение сжимается до $0.5/1.75 = 0.286$ , а приближение со штрафом, приближение второго порядка плюс $\frac{\lambda}{2} w^2$ , уменьшается на $0.071$ . Отделение двух положительных точек от отрицательной при $\lambda = 1$ имеет прирост $\frac12 (1/1.5 + 0.25/1.25 - 0.25/1.75) = 0.362$ .

XGBoost, LightGBM и CatBoost#

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

	XGBoost (Chen and Guestrin, 2016)	LightGBM (Ke et al., 2017)	CatBoost (Prokhorenkova et al., 2018)
Поиск разбиений	точный жадный по отсортированным значениям; приближённый по квантилям-кандидатам из взвешенного квантильного скетча (weighted quantile sketch) с весами $h_i$ (разделы 3.1–3.3)	гистограммы: признаки один раз разбиваются на бины, разбиения только по границам бинов (раздел 2.1)	—
Рост дерева	по уровням (depth-wise) в точном алгоритме, как отмечают Ke et al. в своём разделе 5.1	по листьям (leaf-wise): всегда разбивается лист с наибольшим приростом (best-first, раздел 5.1)	симметричные деревья (oblivious trees): одно разбиение на уровень, общее для всех узлов уровня (раздел 5)
Строки	подвыборка строк и столбцов (раздел 2.3)	GOSS: оставить верхнюю долю $a$ точек по $\lvert g_i \rvert$ , выбрать долю $b$ остальных и дать им вес $(1 - a)/b$ (раздел 3)	упорядоченный бустинг (ordered boosting): градиент каждой точки берётся от модели, которая её не видела, против сдвига предсказаний (раздел 4)
Признаки	разбиение с учётом разреженности и выученным направлением по умолчанию для пропусков (раздел 3.4)	EFB: объединение взаимоисключающих разреженных признаков в один (раздел 4)	упорядоченные целевые статистики (ordered target statistics) для категорий (раздел 3.2)

Две из этих идей касаются утечки, и каждая заслуживает отдельного предложения. CatBoost заменяет категорию средним значением целевой переменной обучающих точек с этой категорией, сглаженным априорным значением, $\hat x_k = \big(\sum_{j} [x_j = x_k] \, y_j + a p\big) / \big(\sum_j [x_j = x_k] + a\big)$ , где суммы берутся только по точкам, которые идут раньше $k$ в случайной перестановке; если считать статистику по всем точкам, она включала бы само $y_k$ и переносила бы целевую переменную в признак — проблема из заметки о данных. Упорядоченный бустинг применяет тот же принцип к градиентам: остаток обучающей точки, вычисленный моделью, обученной на этой точке, меньше, чем был бы на новой точке, — это сдвиг предсказаний (prediction shift), который авторы называют утечкой целевой переменной в самом бустинге (раздел 4.1). Рост по листьям в LightGBM при том же числе листьев достигает меньшей функции потерь на обучении и именно поэтому требует ограничения на число листьев или глубину, чтобы избежать глубоких переобученных ветвей; симметричные деревья CatBoost — противоположный выбор, сильно регуляризованная и быстрая для вычисления форма.

Ранняя остановка#

Число деревьев $M$ — главный параметр регуляризации бустинга: функция потерь на обучении монотонно падает, а на тесте сначала падает, а потом растёт. Ранняя остановка (early stopping) отслеживает функцию потерь на валидационной выборке после каждого дерева и оставляет модель в её минимуме или останавливается, когда функция потерь на валидации не улучшалась заданное число раундов (Hastie, Tibshirani and Friedman, 2009, раздел 10.12, где её сравнивают с ранней остановкой для нейросетей).

Рисунок

Ранняя остановка и шаг обучения

Деревья глубины 3, 50 обучающих и 50 валидационных точек y = sin 2πx + шум (σ = 0.3). Ошибка на обучении (тонкие линии) падает к нулю при любом шаге обучения. Ошибка на валидации (толстые) сначала падает, потом растёт: с шагом обучения 1 минимум 0.177 достигается уже на 3-м раунде, с шагом 0.1 — 0.111 на 15-м. К 300-му раунду обе модели переобучены (0.238 и 0.236). Ранняя остановка берёт модель в точке минимума.

Два шага обучения показывают компромисс из предыдущего раздела на одной картинке: при $\nu = 1$ минимум на валидации наступает рано и высок; при $\nu = 0.1$ он наступает позже и ниже; обе модели переобучаются, если довести их до конца. На практике валидационную выборку откладывают из обучающих данных, как в заметке о валидации, или выбирают число раундов кросс-валидацией. HistGradientBoostingClassifier из scikit-learn, у которого 20% обучающей выборки о раке груди отложено для валидации и терпение (patience) составляет 20 раундов, останавливается после 73 деревьев и достигает доли правильных ответов (accuracy) на тесте $0.942$ .

Стекинг#

Бустинг и бэггинг комбинируют много моделей одного вида. Стекинг (stacking; Wolpert, 1992; Breiman, 1996) комбинирует несколько моделей разных видов — лес, бустинг, линейную модель, метод ближайших соседей: их предсказания становятся признаками метамодели (meta-model), часто линейной или логистической регрессии, которая выучивает, насколько доверять каждой.

Очевидный способ построить обучающую выборку метамодели — предсказания базовых моделей на их собственных обучающих данных — неверен. Модель, запомнившая свою обучающую выборку, идеально предсказывает обучающие значения целевой переменной, и метамодель учится полностью ей доверять. Это утечка целевой переменной в чистейшем виде, как описано в заметке о данных. Исправление — предсказания вне фолда (out-of-fold predictions): разбить обучающую выборку на $K$ фолдов и предсказывать каждый фолд копиями базовых моделей, обученными на остальных $K - 1$ . Тогда метапризнак каждой точки получен от моделей, которые её не видели, — так же, как во время теста. Метамодель обучается на предсказаниях вне фолда, а базовые модели для предсказания переобучаются на всех данных.

На функции Фридмана с 500 обучающими точками и тремя базовыми моделями — 1 ближайший сосед, гребневая регрессия и случайный лес — разница разительна. Неотрицательная линейная метамодель, обученная на предсказаниях на обучающей выборке, даёт трём моделям веса $(1, 0, 0)$ : всё на 1-NN, который точно воспроизводит свои обучающие значения целевой переменной, и её MSE на тесте равна MSE 1-NN, $13.71$ . При обучении на предсказаниях вне фолда по 5 фолдам веса равны $(0.03, 0.32, 0.76)$ , а MSE на тесте — $4.29$ , ниже, чем у лучшей отдельной модели, леса с $4.76$ . Ограничение весов неотрицательными значениями — распространённая защита от неустойчивых комбинаций коррелированных предсказаний (Hastie, Tibshirani and Friedman, 2009, раздел 8.8).

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

Что изменилось#

	Бэггинг и случайный лес	Градиентный бустинг
Деревья	глубокие, выращиваются независимо	небольшие, выращиваются последовательно
Каждое дерево подгоняется под	бутстрэп-выборку значений целевой переменной	антиградиент функции потерь в текущей модели
Снижает	разброс	смещение (разброс контролируется $\nu$ , $M$ , подвыборками)
Функция потерь	квадратичная ошибка или Джини внутри деревьев	любая дифференцируемая функция потерь
Больше деревьев	никогда не вредит	в итоге переобучение: ранняя остановка
Настройка	небольшая	шаг обучения, число деревьев, глубина, штрафы

Ограничения#

Последовательность. Деревья нельзя выращивать параллельно на разных шагах, только внутри шага; обучение медленнее, чем у леса того же размера.
Настройка важна. Шаг обучения, число деревьев, размер деревьев, подвыборки и штрафы взаимодействуют, и значения по умолчанию редко оптимальны.
Переобучается, если работает слишком долго, в отличие от леса; нужна валидационная выборка или кросс-валидация.
Чувствителен к шуму в метках с функциями потерь, градиенты которых неограниченно растут, такими как экспоненциальная.
Признаки должны существовать. Деревья разбивают по заданным признакам по одному. На сырых пикселях, отсчётах звука или идентификаторах токенов отдельный признак обычно несёт мало информации, а полезная структура — край на изображении или словосочетание — живёт в сочетаниях, которые разбиения вдоль осей находят лишь медленно. Деревья на сырых входах всё же могут быть разумной базовой моделью, но на таких данных обычно лучше работают обученные представления.

Что нужно запомнить#

Бустинг добавляет небольшие деревья по одному, каждое подгоняется под текущие ошибки; для квадратичной функции потерь ошибки — остатки.
В общем случае каждое дерево подгоняется методом наименьших квадратов под антиградиент $-\partial L / \partial F$ в обучающих точках, а затем каждый лист делает собственный оптимальный (или ньютоновский) шаг: градиентный спуск в пространстве функций.
Логистическая функция потерь: псевдоостаток $y - p$ , ньютоновское значение в листе $\sum (y_i - p_i) / \sum p_i (1 - p_i)$ .
Сжатие шага $\nu \le 0.1$ с ранней остановкой, деревья с 4–8 листьями, подвыборка строк около половины.
XGBoost: целевая функция второго порядка со штрафами $\gamma J + \frac{\lambda}{2} \sum w_j^2$ ; $w_j^* = -G_j / (H_j + \lambda)$ ; прирост разбиения $\frac12 [G_L^2/(H_L + \lambda) + G_R^2/(H_R + \lambda) - G^2/(H + \lambda)] - \gamma$ .
LightGBM: гистограммы, рост по листьям, GOSS, EFB. CatBoost: симметричные деревья, упорядоченные целевые статистики, упорядоченный бустинг.
Стекинг обучает метамодель на предсказаниях вне фолда; предсказания на обучающей выборке переносят утечку целевой переменной и поощряют запоминание.

Код#

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

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import GradientBoostingRegressor, HistGradientBoostingClassifier, RandomForestRegressor
from sklearn.linear_model import LinearRegression, Ridge
from sklearn.model_selection import cross_val_predict, train_test_split
from sklearn.neighbors import KNeighborsRegressor
from sklearn.tree import DecisionTreeRegressor

# один лист, логистическая функция потерь, текущий логарифм шансов 0 (p = 0.5), метки 1, 1, 0: градиенты p - y, гессианы p(1 - p)
y = np.array([1, 1, 0]); p = 0.5
g, h = p - y, p * (1 - p) * np.ones(3)
for lam in (0, 1):
    print(lam, round(-g.sum() / (h.sum() + lam), 3), round(0.5 * g.sum() ** 2 / (h.sum() + lam), 3))
# 0 0.667 0.167 | 1 0.286 0.071   (значение в листе, уменьшение приближения второго порядка со штрафом)
# прирост от отделения двух положительных точек от отрицательной (lambda = 1, gamma = 0)
score = lambda G, H, lam=1: G ** 2 / (H + lam)
print(round(0.5 * (score(g[:2].sum(), h[:2].sum()) + score(g[2:].sum(), h[2:].sum()) - score(g.sum(), h.sum())), 3))   # 0.362

# квадратичная функция потерь: бустинг пней по остаткам вручную для четырёх точек, шаг обучения 0.5
x = np.array([[1.0], [2.0], [3.0], [4.0]]); t = np.array([1.0, 3.0, 4.0, 8.0])
F = np.full(4, t.mean())
print(0, round(float(((t - F) ** 2).mean()), 3))   # 0 6.5
for m in range(3):
    stump = DecisionTreeRegressor(max_depth=1).fit(x, t - F)
    F += 0.5 * stump.predict(x)
    print(m + 1, F.round(3), round(float(((t - F) ** 2).mean()), 3))
# 1 [3.333 3.333 3.333 6.] 2.5 | 2 [2.167 3.722 3.722 6.389] 1.139 | 3 [1.694 3.25 4.194 6.861] 0.47

# функция Фридмана: ошибка на валидации по итерациям для шагов обучения 1 и 0.1, деревья глубины 3
rng = np.random.default_rng(0)
f = lambda X: 10 * np.sin(np.pi * X[:, 0] * X[:, 1]) + 20 * (X[:, 2] - 0.5) ** 2 + 10 * X[:, 3] + 5 * X[:, 4]
X = rng.random((1500, 10)); yv = f(X) + rng.normal(size=1500)
Xtr, Xva, Xte = X[:500], X[500:1000], X[1000:]
ytr, yva, yte = yv[:500], yv[500:1000], yv[1000:]
for lr in (1.0, 0.1):
    gb = GradientBoostingRegressor(learning_rate=lr, n_estimators=1000, max_depth=3, random_state=0).fit(Xtr, ytr)
    va = [((yva - p) ** 2).mean() for p in gb.staged_predict(Xva)]
    best = int(np.argmin(va))
    te = ((yte - list(gb.staged_predict(Xte))[best]) ** 2).mean()
    print(lr, best + 1, round(va[best], 2), round(va[-1], 2), round(te, 2))
# 1.0 8 5.72 6.75 5.7 | 0.1 189 2.71 2.74 2.66   (лучший раунд, лучшая и итоговая MSE на валидации, MSE на тесте в лучшем раунде)
# подвыборка половины строк для каждого дерева (стохастический градиентный бустинг)
gb = GradientBoostingRegressor(learning_rate=0.1, n_estimators=1000, max_depth=3, subsample=0.5, random_state=0).fit(Xtr, ytr)
va = [((yva - p) ** 2).mean() for p in gb.staged_predict(Xva)]
print('subsample', int(np.argmin(va)) + 1, round(min(va), 2))   # subsample 205 2.38

# встроенная ранняя остановка на валидационной доле, логистическая функция потерь, рак груди
Xb, yb = load_breast_cancer(return_X_y=True)
Xb_tr, Xb_te, yb_tr, yb_te = train_test_split(Xb, yb, test_size=0.3, random_state=0, stratify=yb)
hgb = HistGradientBoostingClassifier(learning_rate=0.1, max_iter=1000, early_stopping=True, validation_fraction=0.2, n_iter_no_change=20, random_state=0).fit(Xb_tr, yb_tr)
print(hgb.n_iter_, round(hgb.score(Xb_te, yb_te), 3))          # 73 0.942

# стекинг: неотрицательная линейная метамодель на предсказаниях на обучающей выборке против предсказаний вне фолда
base = {'1-NN': KNeighborsRegressor(1), 'ridge': Ridge(1.0), 'forest': RandomForestRegressor(200, random_state=0)}
ins = np.column_stack([m.fit(Xtr, ytr).predict(Xtr) for m in base.values()])
oof = np.column_stack([cross_val_predict(m, Xtr, ytr, cv=5) for m in base.values()])
test = np.column_stack([m.fit(Xtr, ytr).predict(Xte) for m in base.values()])
for name, Z in (('in-sample', ins), ('out-of-fold', oof)):
    meta = LinearRegression(positive=True).fit(Z, ytr)
    print(name, meta.coef_.round(2), round(((yte - meta.predict(test)) ** 2).mean(), 2))
# in-sample [1. 0. 0.] 13.71 | out-of-fold [0.03 0.32 0.76] 4.29
print({k: round(float(((yte - test[:, i]) ** 2).mean()), 2) for i, k in enumerate(base)})
# {'1-NN': 13.71, 'ridge': 6.63, 'forest': 4.76}

Дальше#

Каждая модель этого раздела разбивает по признакам, которые кто-то предоставил: доходу, возрасту, числу вхождений слова. На табличных данных, где каждый столбец что-то означает, этого достаточно, и бустинг над деревьями по-прежнему трудно превзойти; бенчмарк из 45 табличных наборов данных показал, что ансамбли деревьев всё ещё опережают глубокие сети на данных среднего размера, около десяти тысяч строк (Grinsztajn, Oyallon and Varoquaux, 2022). Но пиксель, отсчёт звука или идентификатор токена сами по себе обычно говорят мало, и порог по одному из них редко бывает хорошим вопросом; важен узор из многих таких значений. Для таких входов сами признаки нужно выучивать. Следующий раздел начинается с линейных моделей этого курса, ставит их друг на друга с нелинейностями между ними и обучает всю стопку тем же градиентным спуском, так что ранние слои вычисляют признаки, которые использует последний слой.

Литература#

J. H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine. Annals of Statistics, 29(5), 2001. Раздел 3 и алгоритм 1 (градиентный бустинг), алгоритм 5 (логистическая функция потерь для двух классов с шагом Ньютона в каждом листе), раздел 5 (сжатие шага).
J. H. Friedman. Stochastic Gradient Boosting. Computational Statistics & Data Analysis, 38(4), 2002.
J. Friedman, T. Hastie, R. Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics, 28(2), 2000.
Y. Freund, R. E. Schapire. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1), 1997.
T. Chen, C. Guestrin. XGBoost: A Scalable Tree Boosting System. KDD, 2016 (doi:10.1145/2939672.2939785). Формулы 2–7 (регуляризованная целевая функция, веса листьев, оценка структуры, прирост разбиения), раздел 2.3 (сжатие шага и подвыборка столбцов), разделы 3.1–3.4 (поиск разбиений, взвешенный квантильный скетч, разбиения с учётом разреженности).
G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, T.-Y. Liu. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. NeurIPS, 2017. Раздел 2.1 (алгоритм на гистограммах), раздел 3 (GOSS), раздел 4 (EFB), раздел 5.1 (рост по листьям).
L. Prokhorenkova, G. Gusev, A. Vorobev, A. V. Dorogush, A. Gulin. CatBoost: unbiased boosting with categorical features. NeurIPS, 2018. Раздел 3.2 (целевые статистики), раздел 4 (сдвиг предсказаний и упорядоченный бустинг), раздел 5 (симметричные деревья).
D. H. Wolpert. Stacked generalization. Neural Networks, 5(2), 1992.
L. Breiman. Stacked Regressions. Machine Learning, 24(1), 1996.
T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Раздел 8.8 (стекинг), разделы 10.6 (функции потерь и робастность), 10.10 (градиентный бустинг, алгоритм 10.3), 10.11 (размер деревьев), 10.12 (сжатие шага, подвыборки, ранняя остановка).
L. Grinsztajn, E. Oyallon, G. Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? NeurIPS Datasets and Benchmarks, 2022.
E. Sokolov et al. Машинное обучение (HSE). Конспект 2021, лекция 10: градиентный бустинг, лекция 11: XGBoost и стекинг; семинар 12: градиентный бустинг, часть 1, часть 2: XGBoost, LightGBM, CatBoost.