Алгоритм AdaBoost

Материал из MachineLearning.

Перейти к: навигация, поиск
Данная статья является непроверенным учебным заданием.
Студент: Участник:DmitryKonstantinov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Алгоритм AdaBoost (сокр. от adaptive boosting) — алгоритм машинного обучения, предложенный Йоавом Фройндом (Yoav Freund) и Робертом Шапиром (Robert Schapire). Является мета-алгоритмом, в процессе обучения строит композицию из базовых алгоритмов обучения для улучшения их эффективности. AdaBoost является алгоритмом адаптивного бустинга в том смысле, что каждый следующий классификатор строится по объектам, которые плохо классифицируются предыдущими классификаторами.

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

Содержание

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

Рассмотрим задачу классификации на два класса, Y=\{-1,+1\}. Допустим, что базовые алгоритмы b_1, \dots, b_T также возвращают только два ответа -1 и +1. W^l = (w_1,\dots w_l) — вектор весов объектов.

Q(b,W^l) = \sum_{i=1}^{l}w_i[y_i b(x_i) < 0] — стандартный функционал качества алгоритма классификации b.

Задачу оптимизации параметра \alpha_t решаем аналитически, аппроксимируя пороговую функцию потерь [z < 0] с помощью экспоненты E(z) = \exp(-z). 

Алгоритм AdaBoost — построение линейной комбинации классификаторов.

Дано: X^l - обучающая выборка;

b_1, \dots, b_T - базовые алгоритмы классификации;

1. Инициализация весов объектов: \w_i = 1/l, i = 1,\dots, l;
2. Для всех t=1,\dots, T, пока не выполнен критерий останова.
    2.1 Находим классификатор b_{t}: X \to \{-1,+1\} который минимизирует взвешенную ошибку классификации;

        b_t = \arg \min_b Q(b,W^l);
    2.2 Пересчитываем кооэффициент взвешенного голосования для алгоритма классификации b_t:

        \alpha_t = \frac{1}{2} \ln\frac{1 - Q(b,W^l)}{Q(b,W^l)};
    2.3 Пересчет весов объектов: w_i = w_i \exp{(-\alpha_t y_i b_t(x_i))}, i = 1,\dots, l;
    2.4 Нормировка весов объектов: w_0 = \sum_{j=1}^{l}w_j; w_i = w_i/w_0, i = 1,\dots, l;
4. Возвращаем: a(x) = sign \left(\sum_{i=1}^{T} \alpha_i b_i(x)\right)

Замечание: После построения некоторого количества базовых алгоритмов(скажем, пары десятков) имеет смысл проанализировать распределение весов объектов. Объекты с наибольшими весами, скорее всего, являются шумовыми выбросами, которые стоит исключить из выборки, после чего начать построение композиции заново. Вообще, бустинг можно использовать как универсальный метод фильтрации выбросов перед применением любого другого метода классификации.

Достоинства

  • Хорошая обобщающая способность. В реальных задачах (не всегда, но часто) удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться (в некоторых задачах) по мере увеличения числа базовых алгоритмов.
  • Простота реализации.
  • Собственные накладные расходы бустинга невелики. Время построения композиции практически полностью определяется временем обучения базовых алгоритмов.
  • Возможность идентифицировать объекты, являющиеся шумовыми выбросами.

Недостатки

  • AdaBoost склонен к переобучению при наличии значительного уровня шума в данных. Экспоненциальная функция потерь слишком сильно увеличивает веса наиболее трудных объектов, на которых ошибаются многие базовые алгоритмы. Однако именно эти объекты чаще всего оказываются шумовыми выбросами. В результате AdaBoost начинает настраиваться на шум, что ведёт к переобучению. Проблема решается путём удаления выбросов или применения менее агрессивных функций потерь.
  • AdaBoost требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
  • Жадная стратегия последовательного добавления приводит к построению неоптимального набора базовых алгоритмов. Для улучшения композиции можно периодически возвращаться к ранее построенным алгоритмам и обучать их заново. Для улучшения коэффициентов можно оптимизировать их ещё раз по окончании процесса бустинга с помощью какого-нибудь стандартного метода построения линейной разделяющей поверхности. Рекомендуется использовать для этой цели SVM (машины опорных векторов).
  • Бустинг может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.

Софт

Ссылки

  1. К.В. Воронцов, Машинное обучение (курс лекций)
  2. 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.
  3. Additive logistic regression: a statistical view of boosting. Jerome Friedman, Trevor Hastie, Robert Tibshirani Обсуждаются вероятностные аспекты AdaBoost, описывается GentleBoost.
  4. A Short Introduction to Boosting Введение в Adaboost, Freund и Schapire, 1999
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_AdaBoost»
Личные инструменты