boosting.tex

\section{Усиление простых классификаторов. Алгоритм AdaBoost}
Усиление простых классификаторов --- подход к решению задачи классификации путем комбинирования примитивных ``слабых'' (\emph{weak}) классификаторов в один ``сильный'' (\emph{strong}). Под ``силой'' классификатора в данном случае подразумевается эффективность (качество) решения задачи классификации. В данном разделе речь пойдет о семействе алгоритмов, в основе которых лежит алгоритм \emph{AdaBoost}, описанный в \cite{freund99}. Этот алгоритм был успешно использован во многих областях, в частности для задачи поиска лиц на изображении. Подход усиления простых классификаторов применяется во многих задачах и до сих пор является объектом множества как прикладных, так и теоретических исследований.

\subsection{Введение}
В основе метода усиления простых классификаторов лежит простая предпосылка: скомбинировать некоторое количество элементарных (простых) признаков таким образом, чтобы получить один, но более мощный. Классический пример: пусть человек, играющий на скачках, решил создать программу, которая бы предсказывала, придет ли интересующая его лошадь первой к финишу. Опросив некоторое количество играющих людей, он смог определить несколько эмпирических правил: ставь на лощадь, которая победила в трех предыдущих заездах, ставь на лощадь, ставки на которую максимальны и т.д. Ясно, что каждой из таких правил по отдельности недостаточно надежно и встает вопрос можно ли их оптимально скомбинировать для получения надежных результатов.

\subsection{AdaBoost}
Мы рассмотрим один из самых ранних алгоритмов из данного семейства --- AdaBoost. Этот алгоритм был опубликован в 1996 году и послужил основой для всех последующих исследований в данной области. На его основе была построена на данных момент, пожалуй, самая эффективная (как по уровню распознавания, так и по скорости работы) система поиска объектов на изображении \cite{viola01}. На данный момент наиболее распростаненными вариантами базового алгоритма являются \emph{Gentle AdaBoost} и \emph{Real AdaBoost}, превосходящие базовый алгоритм по своим характеристикам, но сохраняющие все основные принципы. К основным достоинствам \emph{AdaBoost} и его вариантов можно отнести высокую скорость работы, высокую эффективность распознавания, простоту реализации, общность.

\subsubsection{Описание алгоритма}
Требуется построить классифицирующую функцию $F : X \to Y$, где $X$ --- пространство векторов признаков, $Y$ --- пространство меток классов. Пусть в нашем распоряжении имеется обучающая выборка $(x_1, y_1), \dots, (x_M, y_M)$, где $x_i \in X$ --- вектор признаков, а $y_i \in Y$ --- метка класса, к которому принадлежит $x_i$. Для простоты изложения мы будем рассматривать задачу с двумя классами, то есть $Y = \{-1; +1\}$. Также у нас есть семейство простых классифицирующих функций $H: X \to Y$. Мы будем строить финальный классификатор в следующей форме:
\begin{displaymath}
  F(x) = \sign{\sum_{t = 1}^T{\alpha_th_t(x)}},
\end{displaymath}
где $\alpha_t \in R, h_t \in H.$ Построим итеративный процесс, где на каждом шаге будем добавлять новое слагаемое:
\begin{displaymath}
  f_t(x) = \alpha_th_t(x),
\end{displaymath}
вычисляя его с учетом работы уже построенной части классификатора.

\begin{algorithm}
  \caption{Алгоритм AdaBoost}
  \label{adaboost-algorithm}
  \begin{enumerate}
  \item Пусть $(x_1, y_1), \dots, (x_M, y_M)$ --- обучающая выборка и $D_1(i) = \frac{1}{M}$ --- начальное распределение.
  \item Для каждого шага $t = 1,2,..,T$:
    \begin{enumerate}
      \item Тренируем слабый классификатор, используя распределение $D_t$.
      \item Получаем слабый классификатор $h_t(x) \in H$ с ошибкой классификации:
        \begin{displaymath}
          \epsilon_t = \sum_{i = 1}^M{D_t(i) \cdot (h_t(x_i) \neq y_i)}).
        \end{displaymath}
      \item Вычисляем коэффициент $\alpha_t = \frac{1}{2}\ln{\frac{1 - \epsilon_t}{\epsilon_t}}$.
      \item Обновляем:
        \begin{displaymath}
          D_{t + 1}(i) = \frac{D_t(i)\exp{(-\alpha_ty_ih_t(x_i))}}{Z_t},
        \end{displaymath}
        где $Z_t$ --- нормализующий делитель, такой что $D_{t + 1}$ будет распределением.
    \end{enumerate}
  \item Составляем сильный классификатор следующим образом:
    \begin{displaymath}
      F(x) = \sign{\sum_{t = 1}^T{\alpha_th_t(x)}}.
    \end{displaymath}
  \end{enumerate}
\end{algorithm}

На каждом шаге будем для каждого примера $(x_i, y_i)$ из обучающей выборки вычислять его ``вес''. Положим $D_1(i) = \frac{1}{M}$, тогда
\begin{displaymath}
  D_{t + 1}(i) = \frac{D_t(i)\exp{(-y_if_t(x_i))}}{Z_t},
\end{displaymath}
где $Z_t$ --- нормализующий коэффициент, такой что
\begin{displaymath}
  \sum_{i = 1}^M{D_{t + 1}(i)} = 1.
\end{displaymath}

Вес каждого элемента обучающей выборки на текущем шаге задает ``важность'' этого примера для очередного шага обучения алгоритма. Чем больше вес, тем больше алгоритм будет ``стараться'' на данном шаге классифицировать этот пример правильно. Как видно из формулы, чем уверенней пример распознается предыдущими шагами, тем его вес меньше; таким образом, самые большие веса получают примеры, которые предыдущими шагами были классифицированы неверно. Иначе говоря, мы варьируем веса таким образом, чтобы классификатор, включенный в комитет на текущем шаге, ``концентрировался'' на примерах,  с которыми предыдущие шаги ``не справились''. Таким образом на каждом шаге мы работаем с какой-то частью данных, плохо классифицируемой предыдущими шагами, а в итоге комбинируем все промежуточные результаты.

Очередной простой классификатор мы будем выбирать, исходя из взвешенной с распределением $D_t$ ошибки. Мы выбираем (тренируем) $h_t \in H$, минимизирующий взвешенную ошибку классификации
\begin{displaymath}
  \epsilon_t = \sum_{i = 1}^M{D_t(i) \cdot (h_t(x_i) \neq y_i)}.
\end{displaymath}

Заметим, что если рассмотреть $D_t$ как распределение вероятности над $X$, что правомерно, так как
\begin{displaymath}
  \sum_{i = 1}^M{D_{t + 1}(i)} = 1,
\end{displaymath}
то
\begin{displaymath}
  \epsilon_t = \underset{x \sim D_t}{\Pr}(h_t(x) \neq y).
\end{displaymath}

Далее вычисляется вклад текущего слагаемого классифицирующей функции
\begin{displaymath}
  \alpha_t = \frac{1}{2}\ln{\frac{1 - \epsilon_t}{\epsilon_t}}.
\end{displaymath}

Мы продолжаем процесс до некоторого шага $T$, номер которого определяется вручную.

\subsubsection{Роль простого классификатора}
В этом разделе мы уделим внимание фундаменту всех методов усиления простых классификаторов --- семейству простых классификаторов $H : X \to Y$.

Для ясности приведем пример. Пусть входные данные --- это $n$-мерные вектора $x \in R^n$, тогда
\begin{displaymath}
  H = h^{\Theta, k}(x = (x_1, \dots, x_k, \dots, x_n)) = \begin{cases}+1, x_k > \Theta,\\ -1, x_k < \Theta\end{cases},
\end{displaymath}
то есть это порог по $k$-той координате.

Как при таком множестве $H$ происходит выбор наилучшего классификатора $h^{\Theta, k}$ на каждой итерации? В данном случае делается следующее: для каждого $k = 1..n$ вычисляется порог $\Theta'_k$, реализующий минимум взвешенной ошибки $\epsilon_t$, затем из полученных классификаторов $h^{\Theta, k}, k = 1..n$ выбирается соответствующий минимальной $\epsilon_t$.

Несмотря на свою простоту, этот классификатор, усиленный алгоритмом \emph{AdaBoost}, дает весьма впечатляющий результаты. Система поиска объектов на изображении \cite{viola01} находит $95\%$ всех искомых объектов с $0,0001\%$ ложных срабатываний.

Какими свойствами должен обладать простой классификатор? В первую очередь, вероятность его ошибки должна быть хотя бы немного меньше $^1/_2$, то есть он должен работать лучше, чем ``подбрасывание монеты'':
\begin{displaymath}
  \exists \gamma > 0: \underset{x \sim D_m}{\Pr}(h(x) \neq y) \leq \frac{1}{2} - \gamma.
\end{displaymath}

Также простой классификатор должен быть максимально простой структуры (обладать малой $VC$-размерностью). Это связано с оценкой ошибки обобщения сильного классификатора.

Самыми часто используемыми на практике простыми классификаторами являются пороги (\emph{stumps}) и \emph{CART} решающие деревья.

\subsubsection{Внутреняя механика AdaBoost}

В этом разделе мы попытаемся пролить немного света на внутреннюю механику алгоритма. Фактически, \emph{AdaBoost} осуществляет два действия:
\begin{itemize}
  \item отбор простых классификаторов (простых признаков);
  \item комбинирование отобранных классификаторов.
\end{itemize}

Первое действие является своеобразным отображением пространства входных векторов в пространство значений простых классификаторов:
\begin{displaymath}
  x = (x_1, x_2, \dots, x_N) \to (h_1(x), h_2(x), \dots, h_M(x)).
\end{displaymath}

Комбинирование простых классификаторов происходит линейно (составляется линейная комбинация), а решение принимается в зависимости от знака полученной комбинации. Это фактически эквивалентно разделению пространства значений простых классификаторов гиперплоскостью и принятие решения в зависимости от того, по какую сторону гиперплоскости лежит отображение вектора признаков.

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

Стоит заметить, что работа \emph{AdaBoost} в значительной мере напоминает работу алгоритма ядерной машины опорных векторов (\emph{Kernel Support Vector Machine}).

Одна из интерпретаций работы алгоритмов на основе \emph{AdaBoost} основана на понятии ``грани'' (\emph{margin}). В случае \emph{AdaBoost} грань определяется как:
\begin{displaymath}
  \mu(x, y) = \frac{\sum_{m = 1}^M{y \cdot f_m(x)}}{\sum_{m = 1}^M{\alpha_m}}.
\end{displaymath}

Эту величину можно интерпретировать как меру ``уверенности'' классификатора в примере $(x, y)$. Если классификация правильная, то грань больше нуля, иначе грань отрицательна. Чем больше простых классификаторов правильно классифицируют пример, тем больше грань.

Если учесть то, как на каждом шаге вычисляются веса примеров, то легко видеть, что на каждом шаге \emph{AdaBoost} пытается максимизировать минимальную грань тренировочной выборки. Утверждается, что данное дейтсвие положительно сказывается на обобщающих способностях алгоритма. Больше про данную интерпретацию семейства алгоритмов на основе \emph{AdaBoost} можно прочитать в \cite{rosset04}.

\subsection{Заключение}

Как и любой алгоритм, \emph{AdaBoost} имеет свои достоинства и недостатки. К числу достоинств можно отнести:
\begin{itemize}
  \item Хорошая обобщающая способность. В реальных задачах (не всегда, но часто) удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться (в некоторых задачах) по мере увеличения числа базовых алгоритмов.
  \item Простота реализации.
  \item Собственные накладные расходы алгоритма \emph{AdaBoost} невелики. Время построения композиции практически полностью определяется временем обучения базовых алгоритмов.
  \item Возможность идентифицировать объекты, являющиеся шумовыми выбросами.
\end{itemize}

К недостаткам:
\begin{itemize}
  \item \emph{AdaBoost} склонен к переобучению при наличии значительного уровня шума в данных. Экспоненциальная функция потерь слишком сильно увеличивает веса наиболее трудных объектов, на которых ошибаются многие базовые алгоритмы. Однако именно эти объекты чаще всего оказываются шумовыми выбросами. В результате \emph{AdaBoost} начинает настраиваться на шум, что ведёт к переобучению. Проблема решается путём удаления выбросов или применения менее агрессивных функций потерь.
  \item \emph{AdaBoost} требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг (\emph{bagging}), способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
  \item Жадная стратегия последовательного добавления приводит к построению неоптимального набора базовых алгоритмов. Для улучшения композиции можно периодически возвращаться к ранее построенным алгоритмам и обучать их заново. Для улучшения коэффициентов можно оптимизировать их ещё раз по окончании процесса с помощью какого-нибудь стандартного метода построения линейной разделяющей поверхности. Рекомендуется использовать для этой цели SVM (машины опорных векторов).
  \item \emph{AdaBoost} может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.
\end{itemize}

Для более детального знакомства предлагаем обратиться к указанной в библиографии литературе, а также посетить сайт \url{http://www.boosting.org}.

\newpage