AdaBoost

Материал из Википедии — свободной энциклопедии

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

AdaBoost вызывает слабый классификатор в цикле . После каждого вызова обновляется распределение весов D_t, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый классификатор «фокусирует своё внимание» на этих объектах.

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

Дано: где

Инициализируем

Для каждого :

Находим классификатор который минимизирует взвешенную ошибку классификации:
, где
Если величина , то останавливаемся.
Выбираем , обычно где ε _t взвешенная ошибка классификатора h_t.
Обновляем:

где Z_t является нормализующим параметром (выбранным так, чтобы D_t _{+ 1} являлось распределением вероятностей, то есть ).

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

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

Таким образом, после выбора оптимального классификатора для распределения , объекты , которые классификатор идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении , он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.