Бустинг, AdaBoost

Материал из Викиконспекты
Перейти к: навигация, поиск

Описание

Бустинг (англ. boosting) — это композиционный метаалгоритм обучения машин. Применяется, главным образом, для уменьшения смещения, а также дисперсии в обучении с учителем. Так же семейство алгоритмов обучения машин, преобразующих слабые обучающие алгоритмы к сильным. Слабый обучающий алгоритм определяется как классификатор, который слабо коррелирует с правильной классификацией (может пометить примеры лучше, чем случайное угадывание). В отличие от слабого алгоритма, сильный обучающий алгоритм является классификатором, хорошо коррелирующим с верной классификацией.

Алгоритмы бустинга

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

Исходные алгоритмы, предложенные Робертом Шапире (рекурсивное доминирование, англ. recursive majority gate formulation) и Йоавом Фройндом (бустинг по доминированию), не были адаптивными и не могли дать полного преимущества слабых обучений. Шапире и Фройнд затем разработали AdaBoost (сокр. Adaptive Boosting) – адаптивный алгоритм бустинга.

Только алгоритмы, для которых можно доказать, что они являются алгоритмами бустинга в формулировке приближённо правильного обучения, могут быть точно названы алгоритмами бустинга. Другие алгоритмы, близкие по духу алгоритмам бустинга, иногда называются «алгоритмами максимального использования» (англ. leveraging algorythms), хотя они иногда также неверно называются алгоритмами бустинга.

Основное расхождение между многими алгоритмами бустинга заключается в методах определения весовых коэффициентов точек тренировочных данных и гипотез. Алгоритм AdaBoost очень популярен и исторически наиболее знаменателен, так как он был первым алгоритмом, который смог адаптироваться к слабому обучению.

Алгоритмы бустинга могут основываться на выпуклых или невыпуклых алгоритмах оптимизации. Выпуклые алгоритмы, такие как AdaBoost и LogitBoost, могут «потерпеть крушение» из-за случайного шума, так как не могут обучить базовым и поддающимся научению комбинациям слабых гипотез. Алгоритмы бустинга, основанные на невыпуклой оптимизации, такие как BrownBoost, могут быть обучены из данных с шумами и лежащий в основе классификатор Лонг–Серведио для набора данных может быть обучен.

Классификация признаков в компьютерном зрении

Если даны изображения, содержащие различные известные в мире объекты, классификатор может быть обучен на основе них для автоматической классификации объектов в будущих неизвестных изображениях. Простые классификаторы, построенные на основе некоторых признаков изображения объекта, обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов — это путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификации.

Задача классификации объектов

Классификация признаков является типичной задачей компьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, идентификацией и обнаружением. Классификация по обнаружению объекта обычно содержит выделение признаков, обучение классификатора и применение классификатора к новым данным. Есть много способов представления категории объектов, например по анализу формы, с помощью модели «мешок слов», с помощью локальных описателей, таких как SIFT, и так далее. Примерами классификаторов с учителем служат наивные байесовские классификаторы, методы опорных векторов, смесь гауссиан и нейронные сети. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя. Распознавание категорий объектов в изображениях является сложной задачей в компьютерном зрении, особенно если число категорий велико. Это является следствием высокой внутренней изменчивости классов и необходимости обобщения различных понятий внутри класса. Объекты в одной категории могут выглядеть совершенно различными. Даже один и тот же предмет может выглядеть непохожим с различных точек обзора, при другом мастшабе или освещении. Шум заднего плана и частичные наложения также добавляют сложности в распознавание. Люди способны распознавать тысячи типов объектов, в то время как большинство существующих систем распознавания объектов тренируются для распознавания лишь нескольких, например человеческих лиц, автомобилей, простых объектов и т.д.. Увеличению числа категорий и возможности добавления новых категорий достигается, в частности, с помощью совместного использования признаков и бустинга.

AdaBoost

Описание

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

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

Бустинг для двоичной классификации

Пакет AdaBoost может быть использован для распознавания лиц как пример двоичной классификации. Две категории — это лица и фон. Общий алгоритм выглядит следующим образом:

  1. Формируем большой набор признаков
  2. Инициализируем веса для тренировочного набора изображений
  3. Делаем T прогонов
    • Нормализуем веса
    • Для доступных признаков из набора тренируем классификатор, используя один из признаков и вычисляем ошибку тренировки
    • Выбираем классификатор с наименьшей ошибкой
    • Обновляем веса тренировочных изображений: увеличиваем, если классифицировано неверно, и уменьшаем, если верно
  4. Формируем окончательный сильный классификатор как линейная комбинация T классификаторов (коэффициент больше, если ошибка тренировки меньше)

После бустинга классификатор, построенный из $200$ признаков, может достигать [math]95\%[/math] успешных распознаний при [math]10^{-5}[/math] ошибок положительного распознавания[15].