Бустинг, 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 может быть использован для распознавания лиц как пример двоичной классификации. Две категории — это лица и фон. Общий алгоритм выглядит следующим образом:

Дано: [math](x_1,y_1),...,(x_m,y_m)[/math], где [math]x_i \in X, y_i \in Y = \{-1,+1\}[/math]

Инициализируем [math]D_1(i) = \frac{1}{m},i=1,...,m[/math].

Для каждого [math]t=1,...,T[/math]:

1. Находим классификатор [math]h_t:X\to \{-1,+1\}[/math] который минимизирует взвешенную ошибку классификации: [math]h_t = \arg \min_{h_j \in \mathcal{H}} \epsilon_j[/math], где [math]\epsilon_j = \sum\limits_{i=1}^{m} D_t(i) [y_i\neq h_j(x_i)][/math]
2. Если величина [math]\epsilon_t \geqslant 0.5[/math], то останавливаемся.
3. Выбираем [math]\alpha_t \in \mathbf{R}[/math], обычно [math]\alpha_t = \frac{1}{2}\mathcal{ln}\frac{1-\epsilon_t}{\epsilon_t}[/math], где [math]\epsilon_t[/math] взвешенная ошибка классификатора [math]h_t[/math]
4. Обновляем: [math]D_{t+1}(i) = \frac{D_t(i)\exp^{-\alpha_t y_i h_t(x_i)}}{Z_t}[/math], где [math]Z_t[/math] является нормализующим параметром (выбранным так, чтобы [math]D_{t+1}[/math] являлось распределением вероятностей, то есть [math]\sum\limits_{i-1}^{m} D_{t+1}(i) = 1[/math]).

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

[math]H(x) = \textrm{sign}(\sum\limits_{t=1}^{T} \alpha_t h_t(x))[/math]

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

[math]\exp^{\alpha_t y_i h_t(x_i)} \begin{cases}\lt 1,\ y(i) = h_t(x_i) \\ \gt 1,\ y(i) \neq h_t(x_i)\end{cases}[/math]

Таким образом, после выбора оптимального классификатора [math]h_t[/math] для распределения [math]D_t[/math], объекты [math]x_i[/math], которые классификатор [math]h_t[/math] идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении [math]D_{t+1}[/math], он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.