T16.md

Бустинг алгоритмов. Метод градиентного бустинга

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

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

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

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

$$ H_T(x) = \sum_{t = 1}^{T}{b_th(x,a_t)}, $$

где $b_t \in \mathbb{R}$ - коэффициенты, минимизирующие эмпирический риск. Сам по себе эмпирический риск выглядит так:

$$ \mathcal{L}(X_T, \mathcal{D}) = \sum_{i = 1}^{|\mathcal{D}|}{\mathcal{L}(H_T(x_i), y_i)} \to \text{min}, $$

где $H_T$ - алгоритм (он же: ансамбль), мы считаем ошибки по каждому объекту с функцией ошибок $\mathcal{L}$. Градиентом эмпирического риска будет:

$$ \nabla{\mathcal{L}{i}^{(t - 1)}} = \dfrac{\partial{\mathcal{L}(H{t - 1},,y_i)}}{\partial{H_{t - 1}}}(x_i) $$

Таким образом, мы получаем $H_t(x) = H_{t - 1}(x) - b_t\nabla{\mathcal{L}^{(t - 1)}}$ - то есть, фактически, каждый последующий алгоритм в ансамбле должен уметь находить вектор ошибок - фактически, это изменение вектора ошибок.

Обобщённый алгоритм градиентного бустинга:

1. Есть набор данных $\mathcal{D}$, количество моделей $T$.
2. $H_0(x)$ - обучаем нашу модель.
3. На каждом шаге $T$:
   1. Вычисляем градиент $\nabla{\mathcal{L}^{(t - 1)}}$.
   2. Каждый $a_t$ стремится предсказать $\delta$ между правильным решением и совокупностью всех подправок на ошибки.
   3. Вычисляем $b_t$ - то, что позволяет уменьшить эмпирический риск, ищется, например, градиентными методами.
   4. Нашли новый $H_t(x)$.