Алгоритм AdaBoost

Справочные данные не проверены и ожидают проверку. Если вы заметили какую то ошибку, напишите пожалуйста в комментариях.

Справочник требует, расстановки ссылок на лица.

Алгоритм 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. Инициализация весов объектов: p_i = 1/l, i = 1,\dots, l;
  2. Для всех t=1,\dots, T, пока не выполнен критерий останова.
    1. Находим классификатор b_{t}: X \to \{-1,+1\} который минимизирует взвешенную ошибку классификации; b_t = \arg \min_b Q(b,W^l);
    2. Пересчитываем кооэффициент взвешенного голосования для алгоритма классификации b_t\alpha_t = \frac{1}{2} \ln\frac{1 - Q(b,W^l)}{Q(b,W^l)};
    3. Пересчет весов объектов: w_i = w_i \exp{(-\alpha_t y_i b_t(x_i))}" />, [latex]i = 1,\dots, l;
    4. Нормировка весов объектов: w_0 = \sum_{j=1}^{l}w_j; w_i = w_i/w_0" />, [latex]i = 1,\dots, l;
  3. Возвращаем: a(x) = sign \left(\sum_{i=1}^{T} \alpha_i b_i(x)\right)

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

Достоинства

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

Недостатки

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

 

Источник

comments powered by HyperComments

Посмотрите также

процедура последовательного построения композиции алгоритмов машинного обучения

Бустинг

Бустинг (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда …