Бустинг: AdaBoost

Бустинг

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

Процедура последовательного построения линейного ансамбля (Forward stagewise additive modeling (FSAM))

Рассматривается задача классификации или регрессии. Пусть $h_i(x), i = \overline{0, M}$ — базовые алгоритмы, $c_i \in \mathbb{R}, i = \overline{1, M}$ — числовые коэффициенты. Тогда $F(x) = h_0(x) + c_1\cdot h_1(x) + \dots + c_M\cdot h_M(x)$ — линейный ансамбль. Для задачи регрессии $F(x)$ представляет собой значение целевой переменной. Для задачи классификации $F(x)$ представляет собой уверенность в принадлежности объекта к определённому классу.

Совместная оптимизация $h_i(x), i = \overline{0, M}$, $c_i, i = \overline{1, M}$ затратна по времени для больших $M$. Основная идея FSAM состоит в жадной оптимизации $h_0(x), (c_i, h_i(x)), i = \overline{1, M}$. После жадной процедуры можно дополнительно настроить $c_i, i = \overline{1, M}$, решив задачу линейной регрессии/классификации с признаками $h_i(x), i = \overline{0, M}$.

Алгоритм жадной оптимизации

• Вход: обучающая выборка $(x_i, y_i), i = \overline{1, N}$; функция потерь $\mathfrak{L}(h(x), y)$; общий вид базового алгоритма $h(x) = h(x|\gamma), \gamma$ — параметр; $M$ — число итераций
• Начальное приближение $f_0(x) = \arg\min\limits_{h}\sum\limits_{i = 1}^{N}\mathfrak{L}(h(x_i), y_i)$
• Для $m = 1, 2, \dots, M$:
  • Поиск следующего лучшего алгоритма $(c_m, h_m) = \arg\min\limits_{h, c}\sum\limits_{i = 1}^{N}\mathfrak{L}(f_{m - 1}(x_i) + c\cdot h(x_i), y_i)$
  • Присвоение $f_m(x) = f_{m - 1}(x) + c_m\cdot h_m(x)$
• Выход: приближение $f_M(x) = h_0(x) + \sum\limits_{m = 1}^{M}c_m\cdot h_m(x)$

Комментарии:

• Значение $M$ следует подбирать по валидации.
• Начальное приближение не обязательно решать в пространстве функций $h(x)$, можно $f_0 = \arg\min\limits_{\beta \in \mathbb{R}}\sum\limits_{i = 1}^{N}\mathfrak{L}(\beta, y_i)$ или $f_0(x) \equiv 0$. Ожидается исправление ошибок на последующих итерациях.
• По схожим причинам не требуется высокая точность при нахождении $f_m(x)$.
• Для некоторых функций потерь FSAM имеет аналитическое решение.
• В общем случае используется схема градиентного бустинга.

AdaBoost

Рассмотрим задачу бинарной классификации с метками $y \in \{-1, +1\}$. Общий вид базового алгоритма $h(x) = h(x|\gamma), h(x) \in \{-1, +1\}$, классификатор $\hat{y}(x) = sign\{h_0(x) + \sum\limits_{i = 1}^{N}c_i\cdot h_i(x))\}$, функция потерь $\mathfrak{L}(h(x), y) = e^{-y\cdot h(x)}$. Для построения ансамбля AdaBoost используем модификацию FSAM.

Алгоритм (дискретная версия)

• Вход: обучающая выборка $(x_i, y_i), i = \overline{1, N}$; базовый алгоритм $h(x) \in \{-1, +1\}$, обучаемый на взвешенных выборках; $M$ — число итераций
• Инициализация весов $w_i = \frac{1}{N}, i = \overline{1, N}$
• Для $m = 1, 2, \dots, M$:
  • Обучить $h^m(x)$ на обучающей выборке, используя веса $w_i, i = \overline{1, N}$
  • Вычислить взвешенную ошибку классификации $E_m = \frac{\sum\limits_{i = 1}^{N}w_i\cdot\mathbb{I}[h^m(x_i)\neq y_i]}{\sum\limits_{i = 1}^{N}w_i}$
  • Если $E_m > 0.5$ или $E_m = 0$: остановить процедуру
  • Вычислить $c_m = \frac{1}{2}\cdot\ln\frac{1 - E_m}{E_m}$
  • Увеличить все веса, где базовый алгоритм ошибся: $w_i := w_i\cdot e^{2\cdot c_m}, i \in \{i: h^m(x_i) \neq y_i\}$
• Выход: результирующий ансамбль $F(x) = sign\{\sum\limits_{m = 1}^{M}c_m\cdot h^m(x)\}$

Детали нахождения ($(c_m, h^m)$) в дискретном AdaBoost

Начальное приближение $f_0(x) \equiv 0$

Рассмотрим $m$-ую итерацию процедуры FSAM:

$(c_m, h^m) = \arg\min\limits_{c_m, h^m}\sum\limits_{i = 1}^{N}\mathfrak{L}(f_{m - 1}(x_i) + c_m\cdot h^m(x_i), y_i)=$

$=\arg\min\limits_{c_m, h^m}\sum\limits_{i = 1}^{N}e^{-y_i\cdot f_{m - 1}(x_i)}\cdot e^{-y_i\cdot c_m\cdot h^m(x_i)}=$

$=\arg\min\limits_{c_m, h^m}\sum\limits_{i = 1}^{N}w_i^m\cdot e^{-c_m\cdot y_i\cdot h^m(x_i)}, w_i^m = e^{-y_i\cdot f_{m - 1}(x_i)}$

$\sum\limits_{i = 1}^{N}w_i^m\cdot e^{-c_m\cdot y_i\cdot h^m(x_i)} = \sum\limits_{i: h^m(x_i) = y_i}w_i^m\cdot e^{-c_m} + \sum\limits_{i: h^m(x_i) \neq y_i}w_i^m\cdot e^{c_m}=$

$=e^{-c_m}\cdot\sum\limits_{i: h^m(x_i) = y_i}w_i^m + e^{c_m}\cdot\sum\limits_{i: h^m(x_i) \neq y_i}w_i^m=$

$=e^{c_m}\cdot\sum\limits_{i: h^m(x_i) \neq y_i}w_i^m + e^{-c_m}\cdot\sum\limits_{i = 1}^{N}w_i^m - e^{-c_m}\cdot\sum\limits_{i: h^m(x_i) \neq y_i}w_i^m=$

$=e^{-c_m}\cdot\sum\limits_{i = 1}^{N}w_i^m + (e^{c_m} - e^{-c_m})\cdot\sum\limits_{i: h^m(x_i) \neq y_i}w_i^m$

Так как в алгоритме $c_m \geq 0$, то $h_m(x)$ следует искать следующим образом (первое слагаемое условно является константой, тогда уменьшаем второе неотрицательное слагаемое): $h_m(x_i) = \arg\min\limits_{h}\sum\limits_{i = 1}^{N}w_{i}^{m}\cdot \mathbb{I}[h(x_i) \neq y_i]$

Дифференцирование оптимизируемого функционала

Обозначим $J(c_m) = \sum\limits_{i = 1}^{N}w_{i}^{m}e^{-c_m\cdot y_i\cdot h^m(x_i)}$. $J(c_m)$ — выпуклый, значит, необходимое условие экстремума является ещё и достаточным:

$\frac{\partial J(c_m)}{\partial c_m} = -\sum\limits_{i = 1}^{N}w_{i}^{m}\cdot e^{-c_m\cdot y_i\cdot h^m(x_i)}\cdot y_i\cdot h^m(x_i) = 0$

$-\sum\limits_{i: h^m(x_i) = y_i}w_{i}^{m}\cdot e^{-c_m} + \sum\limits_{i: h^m(x_i) \neq y_i}w_{i}^{m}\cdot e^{c_m} = 0$

$e^{2\cdot c_m} = \frac{\sum\limits_{i: h^m(x_i) = y_i}w_{i}^{m}}{\sum\limits_{i: h^m(x_i) \neq y_i}w_{i}^{m}}$

$c_m = \frac{1}{2}\cdot\ln\frac{(\sum\limits_{i: h^m(x_i) = y_i}w_{i}^{m})\cdot (\sum\limits_{j = 1}^{N}w_{j}^{m})}{(\sum\limits_{i: h^m(x_i) \neq y_i}w_{i}^{m})\cdot (\sum\limits_{j = 1}^{N}w_{j}^{m})} = \frac{1}{2}\cdot\ln\frac{1 - E_m}{E_m}, E_m := \frac{\sum\limits_{i: h^m(x_i) \neq y_i}w_{i}^{m}}{\sum\limits_{i = 1}^{N}w_{i}^{m}}$

Комментарии к вычислению весов ($w_{i}^{m}$)

$w_{i}^{m + 1} \overset{def}{=} e^{-y_i\cdot f_m(x_i)} = e^{-y_i\cdot f_{m - 1}(x_i)}\cdot e^{-y_i\cdot c_m\cdot h^m(x_i)}=$

$=\{-y_i\cdot h^m(x_i) = 2\cdot\mathbb{I}[h^m(x_i) \neq y_i] - 1\}=e^{-y_i\cdot f_{m - 1}(x_i)}\cdot e^{c_m\cdot (2\cdot\mathbb{I}[h^m(x_i) \neq y_i] - 1)}=$

$=w_{i}^{m}\cdot e^{2\cdot c_m\cdot\mathbb{I}[h^m(x_i) \neq y_i]}\cdot e^{-c_m}\propto w_{i}^{m}\cdot e^{2\cdot c_m\cdot\mathbb{I}[h^m(x_i) \neq y_i]}$(избавились от общей константы $e^{-c_m}$). Таким образом, $w_{i}^{m + 1} = w_{i}^{m}$ для правильно классифицированных объектов из обучающей выборки с помощью $h^m(x)$, для неправильно классифицированных объектов с помощью $h^m(x)$ вес на $(m+1)$-ой итерации будет равен $w_{i}^{m + 1} = w_{i}^{m}\cdot e^{2\cdot c_m}$, значит, классификаторы на последующих итерациях будут считать более важными объекты, неверно классифицированные на предыдущей итерации. Существенно важный недостаток данного ансамбля (комитета) состоит в неустойчивости к выбросам из-за используемой экспоненциальной функции потерь.