AdaBoost

Дано: ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$ где ${\displaystyle x_{i}\in X,\,y_{i}\in Y=\{-1,+1\}}$

Инициализируем ${\displaystyle D_{1}(i)={\frac {1}{m}},i=1,\ldots ,m.}$

Для каждого ${\displaystyle t=1,\ldots ,T}$:

• Находим классификатор ${\displaystyle h_{t}:X\to \{-1,+1\}}$ который минимизирует взвешенную ошибку классификации: ${\displaystyle h_{t}=\arg \min _{h_{j}\in {\mathcal {H}}}\epsilon _{j}}$, где ${\displaystyle \epsilon _{j}=\sum _{i=1}^{m}D_{t}(i)[y_{i}\neq h_{j}(x_{i})]}$
• Если величина ${\displaystyle \epsilon _{t}\geqslant 0.5}$, то останавливаемся.
• Выбираем ${\displaystyle \alpha _{t}\in \mathbf {R} }$, обычно ${\displaystyle \alpha _{t}={\frac {1}{2}}{\textrm {ln}}{\frac {1-\epsilon _{t}}{\epsilon _{t}}}}$ где ${\displaystyle \epsilon _{t}}$ взвешенная ошибка классификатора ${\displaystyle h_{t}}$.
• Обновляем:

${\displaystyle D_{t+1}(i)={\frac {D_{t}(i)\,e^{-\alpha _{t}y_{i}h_{t}(x_{i})}}{Z_{t}}}}$

где ${\displaystyle Z_{t}}$ является нормализующим параметром (выбранным так, чтобы ${\displaystyle D_{t+1}}$ являлось распределением вероятностей, то есть ${\displaystyle \sum _{i=1}^{m}D_{t+1}(i)=1}$).

Строим результирующий классификатор:

${\displaystyle H(x)={\textrm {sign}}\left(\sum _{t=1}^{T}\alpha _{t}h_{t}(x)\right)}$

Выражение для обновления распределения ${\displaystyle D_{t}}$ должно быть сконструировано таким образом, чтобы выполнялось условие:

${\displaystyle e^{-\alpha _{t}y_{i}h_{t}(x_{i})}{\begin{cases}<1,&y(i)=h_{t}(x_{i})\\>1,&y(i)\neq h_{t}(x_{i})\end{cases}}}$

Таким образом, после выбора оптимального классификатора ${\displaystyle h_{t}}$ для распределения ${\displaystyle D_{t}}$, объекты ${\displaystyle x_{i}}$, которые классификатор ${\displaystyle h_{t}}$ идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении ${\displaystyle D_{t+1}}$, он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.

• AdaBoost (англ.) Презентация, посвящённая Adaboost.
• A Short Introduction to Boosting (англ.) Введение в Adaboost, Freund и Schapire, 1999
• A decision-theoretic generalization of on-line learning and an application to boosting Journal of Computer and System Sciences, no. 55. 1997 (англ.) (Оригинальная работа Yoav Freund и Robert E.Schapire, где впервые был предложен Adaboost.)
• An applet demonstrating AdaBoost (англ.)
• Ensemble Based Systems in Decision Making, R. Polikar, IEEE Circuits and Systems Magazine, vol.6, no.3, pp. 21-45, 2006 (недоступная ссылка) (англ.) Учебник, дающий общее представление об AdaBoost, включая псевдокод, схемы алгоритмов, вопросы реализации и других алгоритмах распознавания образов.
• A Matlab Implementation of AdaBoost (англ.)
• Additive logistic regression: a statistical view of boosting. Jerome Friedman, Trevor Hastie, Robert Tibshirani (англ.) Обсуждаются вероятностные аспекты AdaBoost, описывается GentleBoost.
• Boosting — Усиление простых классификаторов. Александр Вежневец, Владимир Вежневец. Компьютерная графика и мультимедиа. Выпуск № 2(12)/2006.