AdaBoost

AdaBoost (сокращение от Adaptive Boosting) — алгоритм машинного обучения, предложенный Йоавом Фройндом (en:Yoav Freund) и Робертом Шапирe (en:Robert Schapire). Этот алгоритм может использоваться в сочетании со многими другими алгоритмами обучения для улучшения их эффективности. AdaBoost является адаптивным в том смысле, что каждый следующий классификатор строится по объектам, неверно классифицированным предыдущими классификаторами. AdaBoost чувствителен к шуму в данных и выбросам. Однако он менее подвержен переобучению, чем многие другие алгоритмы обучения.

AdaBoost вызывает слабый классификатор в цикле $t = 1,\ldots,T$. После каждого вызова обновляется распределение весов $D_{t}$, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый классификатор «фокусирует своё внимание» на этих объектах.

Алгоритм для задачи построения бинарного классификатора

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

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

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

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

$D_{t+1}(i) = \frac{ D_{t}(i) \, e^{- \alpha_{t} y_{i} h_{t}(x_{i})} }{ Z_{t} }$
где $Z_{t}$ является нормализующим параметром (выбранным так, чтобы $D_{t+1}$ являлось распределением вероятностей, то есть $\sum_{i=1}^{m} D_{t+1}(i) = 1$).

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

$H(x) = \textrm{sign}\left( \sum_{t=1}^{T} \alpha_{t}h_{t}(x)\right)$

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

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

Таким образом, после выбора оптимального классификатора $h_{t} \,$ для распределения $D_{t} \,$, объекты $x_{i} \,$, которые классификатор $h_{t} \,$ идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении $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.

Для улучшения этой статьи желательно?: Проверить достоверность указанной в статье информации. Проставив сноски, внести более точные указания на источники.