AdaBoost (сокращение от англ. adaptive boosting ) — алгоритм машинного обучения , предложенный и . Может использоваться в сочетании с несколькими алгоритмами классификации для улучшения их эффективности. Алгоритм усиливает классификаторы, объединяя их в ансамбль . Является адаптивным в том смысле, что каждый следующий ансамбль классификаторов строится по объектам, неверно классифицированным предыдущими комитетами. AdaBoost чувствителен к шуму в данных и выбросам . Однако он менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения.

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

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

Дано: ${\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, Freund и Schapire, 1999
• (англ.) (Оригинальная работа Yoav Freund и Robert E.Schapire, где впервые был предложен Adaboost.)
• (англ.)
• (недоступная ссылка) (англ.) Учебник, дающий общее представление об AdaBoost, включая псевдокод, схемы алгоритмов, вопросы реализации и других алгоритмах распознавания образов.
• (англ.)
• (англ.) Обсуждаются вероятностные аспекты AdaBoost, описывается GentleBoost.
• Александр Вежневец, Владимир Вежневец. Компьютерная графика и мультимедиа. Выпуск № 2(12)/2006.