Внутренняя механика AdaBoost

В этой части мы попытаемся пролить немного света на внутреннюю механику алгоритма. Фактически, AdaBoost осуществляет два действия:

• Отбор простых классификаторов (простых признаков)
• Комбинирование отобранных классификаторов

Первое действие является своеобразным отображением пространства входных векторов в пространство значений простых классификаторов:

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

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

Стоит заметить, что работа AdaBoost в значительной мере напоминает работу алгоритма ядерной машины опорных векторов (Kernel Support Vector Machine - kernel SVM). Исследования последних лет показывает глубокую связь этих двух алгоритмов, что является серьёзным теоретическим результатом [9].

Одна из интерпретаций работы алгоритмов на основе AdaBoost основана на понятие <грани> (margin). В случае AdaBoost грань определяется как:

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

Если учесть то, как на каждом шаге вычисляются веса примеров, то легко видеть, что на каждом шаге AdaBoost пытается максимизировать минимальную грань тренировочной выборки. Утверждается, что данное действие положительно сказывается на обобщающих способностях алгоритма. Больше про данную интерпретацию семейства алгоритмов на основе AdaBoost можно прочитать в [9].