Бустинг: 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}}$, значит, классификаторы на последующих итерациях будут считать более важными объекты, неверно классифицированные на предыдущей итерации. Существенно важный недостаток данного ансамбля (комитета) состоит в неустойчивости к выбросам из-за используемой экспоненциальной функции потерь.