Градиентный бустинг
Идея
Каждая следующая модель корректирует ошибки предыдущих. Итоговая композиция:
\[a(x) = \sum_{n=1}^N \gamma_n b_n(x)\]
Бустинг для MSE
Модели строятся последовательно. Первая модель \(b_1(x)\) обучается на исходных ответах. Каждая следующая \(b_N(x)\) обучается предсказывать остатки — разность между истинным ответом и текущим прогнозом:
\[b_N(x):\ \frac{1}{\ell}\sum_{i=1}^\ell (b_N(x_i) - (y_i - a_{N-1}(x_i)))^2 \to \min_{b_N}\]
Коэффициент \(\gamma_N\) подбирается одномерной оптимизацией. Остановку контролируют по валидационной выборке — бустинг переобучается.
Общий случай — градиентный бустинг
Для произвольной дифференцируемой функции потерь \(L(y, z)\) на каждом шаге считаем антиградиент:
\[s_i = -\left.\frac{\partial}{\partial z} L(y_i, z)\right|_{z = a_{N-1}(x_i)}\]
Затем обучаем \(b_N(x)\) аппроксимировать \(s_i\):
\[\frac{1}{\ell}\sum_{i=1}^\ell (b_N(x_i) - s_i)^2 \to \min_{b_N}\]
Обновляем композицию: \(a_N(x) = a_{N-1}(x) + b_N(x)\).
Функции потерь в бустинге
| Задача | Функция потерь | Антиградиент \(s_i\) |
|---|---|---|
| Регрессия | MSE: \((y - z)^2\) | \(y_i - a_{N-1}(x_i)\) |
| Регрессия | MAE: \(|y - z|\) | \(-\text{sign}(y_i - a_{N-1}(x_i))\) |
| Классификация | Log-loss: \(\log(1 + e^{-yz})\) | \(\frac{y_i}{1 + \exp(y_i a_{N-1}(x_i))}\) |
Регуляризация
В бустинге важно использовать модели с низким variance — неглубокие деревья.
- Если деревья простые — качество ограничено их bias.
- Если деревья сложные — риск быстрого переобучения.
Learning rate (сокращение шага):
\[a_N(x) = a_{N-1}(x) + \eta b_N(x),\quad \eta \in (0; 1]\]
Чем меньше \(\eta\), тем больше оптимальное \(N\) и тем медленнее переобучение.
Стохастический градиентный бустинг: на каждом шаге обучаем \(b_N\) не на всей выборке, а на случайной подвыборке \(|\mathbb{X}_N|\) — гиперпараметр.
GBDT — бустинг над деревьями
После того как структура дерева на шаге \(N\) зафиксирована, переподбираем прогнозы в листьях оптимально по исходной функции потерь:
\[\sum_{(x_i, y_i) \in R_{Nj}} L(y_i, a_{N-1}(x_i) + c_j) \to \min_{c_j \in \mathbb{R}}\]
Для log-loss один шаг метода Ньютона-Рафсона из точки \(c_j = 0\) даёт:
\[c_j = -\frac{\sum_{(x_i, y_i) \in R_{Nj}} s_i}{\sum_{(x_i, y_i) \in R_{Nj}} |s_i|(1 - |s_i|)}\]
Бустинг второго порядка
Разложим функцию потерь по второму аргументу в ряд Тейлора до второго члена:
\[\sum_{i=1}^\ell L(y_i, a_{N-1}(x_i) + b_N(x_i)) \approx \sum_{i=1}^\ell \left(-s_i b_N(x_i) + \frac{1}{2} h_i b_N^2(x_i)\right) \to \min_{b_N}\]
Здесь \(h_i = \left.\frac{\partial^2}{\partial z^2} L(y_i, z)\right|_{z = a_{N-1}(x_i)}\) — вторая производная (кривизна функции потерь).
При добавлении регуляризации по числу листьев \(J\) и норме прогнозов \(\|b\|^2\):
\[\sum_{i=1}^\ell \left(-s_i b_N(x_i) + \frac{1}{2}h_i b_N^2(x_i)\right) + \gamma J + \frac{\lambda}{2}\sum_{j=1}^J b_j^2 \to \min_{b_N}\]
При фиксированной структуре дерева оптимальный прогноз в листе \(j\):
\[b_j^* = \frac{S_j}{H_j + \lambda},\quad \text{где}\ S_j = \sum_{R_{Nj}} s_i,\ H_j = \sum_{R_{Nj}} h_i\]
Значение функционала при оптимальных прогнозах:
\[H(B) = -\frac{1}{2}\sum_{j=1}^J \frac{S_j^2}{H_j + \lambda} + \gamma J\]
\(H(B)\) используется как impurity при построении дерева — именно так работает XGBoost:
\[Q(R, j, t) = H(R) - H(R_l) - H(R_r)\]
AdaBoost
Частный случай бустинга с экспоненциальной функцией потерь. Ключевая идея — механизм комитетов: на каждом шаге увеличиваются веса неправильно классифицированных объектов.
| Достоинства | Недостатки |
|---|---|
| Простая реализация | Склонен к переобучению при шуме в данных |
| Хорошая обобщающая способность | Требует длинных обучающих выборок |
| Идентификация выбросов по большим весам | Уступает бэггингу на малых выборках |