Введение в бустинг (boosting). Алгоритм AdaBoost при классификации

На предыдущем занятии мы с вами познакомились с идеей бэггинга (bagging), когда формируется T независимых простых алгоритмов и вычисляется выходное значение в виде усреднения ответов от каждого из них:

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

Но в этой схеме есть два тонких момента:

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

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

Как можно было бы улучшить этот подход? В 1995 году два ученых Йоав Фройнд (Yoav Freund) и Роберт Шапир (Robert Schapire) предложили более общую схему для композиции алгоритмов – с разными весами:

            (1)

где  - веса (положительные числа);  - простые алгоритмы обработки входного вектора . Причем, будем полагать, что алгоритмы выдают вещественное значение:

Например, в задачах классификации – это может быть величина отступа (margin), который для линейных алгоритмов мы определяли как скалярное произведение:

Или вероятность принадлежности к тому или иному классу. И так далее. То есть, алгоритмы  выдают не жесткие (конечные) решения, а более точные (промежуточные) вещественные. В этом случае композиция, как правило, приводит к лучшим результатам.

Итак, при объединении алгоритмов по формуле (1) нам необходимо уметь вычислять весовые коэффициенты и строить набор из T алгоритмов так, чтобы минимизировался заданный показатель качества. Давайте для определенности дальше будем рассматривать задачу бинарной классификации. Тогда показатель качества логично выбрать, как число неверно классифицируемых образов:

Напомню, что когда отступ для i-го образа меньше нуля (), значит произошла ошибка классификации и квадратные скобки (нотация Айзерсона) вернут 1. Иначе возвращается 0.

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

Глядя на полученный функционал качества, мы понимаем, что его нужно оптимизировать и по весовым коэффициентам и по алгоритмам:

Но это довольно сложная математическая задача, поэтому Фройнд и Шапиро предложили использовать следующие две эвристики:

  • «Жадное» построение композиции – поиск (выбор) текущего алгоритма  и весового множителя  при фиксации ранее найденных алгоритмов и весовых множителей:  и . То есть, на каждом шаге t мы вычисляем только один весовой коэффициент и обучаем только один алгоритм  преимущественно на тех образах обучающей выборки, на которых предыдущие алгоритмы показали слабые результаты.
  • Аппроксимировать исходный (пороговый) функционал качества гладкой дифференцируемой функцией потерь, чтобы мы могли численно или аналитически решать оптимизационную задачу.

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

Алгоритм AdaBoost

Чтобы все это лучше понять, рассмотрим конкретный пример – алгоритм AdaBoost (сокращение от Adaptive Boosting), который и предложили Фройнд с Шапиро применительно к задачам бинарной классификации с метками классов . Для аппроксимации порогового функционала качества было предложено использовать экспоненциальную функцию потерь:

Если расписать это выражение, то получим выражение:

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

Обе формулы – одно и то же, но во второй мы явно (отдельно) вынесли . И перед второй экспонентой появляется множитель (вес) , так как предыдущие алгоритмы и коэффициенты зафиксированы.

Давайте проанализируем и посмотрим, какой смысл имеют эти веса. Во-первых, они вычисляются для каждого объекта  обучающей выборки, то есть, это, фактически, веса объектов. Во-вторых, множитель будет тем больше, чем более отрицательным будет отступ (margin). То есть, множитель возрастает для плохо классифицируемых объектов. В результате, текущий алгоритм  в большей степени при обучении будет учитывать эти плохо классифицируемые образы и настраиваться на них. Это и есть реализация принципа бустинга – последовательно обучать алгоритмы на объектах, на которых предыдущая композиция показала худшие результаты.

Далее, по алгоритму, веса  нормируются при поиске каждого следующего алгоритма по формуле:

То есть, мы делаем так, чтобы в сумме нормированные веса давали единицу:

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

Очевидно, лучший текущий алгоритм должен минимизировать долю неверных классификаций:

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

Все, это и есть основа алгоритма AdaBoost. Фактически, мы на каждой итерации (от 1 до T) обучаем текущий алгоритм  на взвешенных объектах обучающей выборки. Само обучение выполняется любым известным нам способом. А, затем, для него вычисляется коэффициент .

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

Вход: обучающая выборка  и параметр T (число алгоритмов в композиции)

Выход: набор базовых алгоритмов  с весами

1: начальная инициализация весов объектов:

2: для всех

3:     найти наилучший текущий алгоритм по правилу:

4:     вычислить оптимальный коэффициент:

5:     обновить веса объектов:

6:     нормировать веса объектов:

Реализация алгоритма AdaBoost для задачи классификации на Python

А теперь, как и обещал, приведу реализацию алгоритма AdaBoost на Python с использованием решающих деревьев в качестве базовых алгоритмов .

Предположим, у нас имеется обучающая выборка в виде следующего набора точек двух классов:

Мы будем их разделять (классифицировать) композицией из T деревьев глубиной два. Программу можно скачать по адресу:

machine_learning_42_adaboost_classification.py

В итоге, получаем следующие результаты:

Ожидаемо, что при увеличении числа деревьев в композиции, число ошибок также уменьшается. При этом, мы использовали очень простые деревья уровня два. Каждое из них по отдельности не смогло бы справиться с задачей, но в композиции получается безошибочная классификация на обучающей выборке. И, возможно, здесь у вас появится вопрос. Раз алгоритм так хорошо подстраивается под обучающую выборку, то возможно он переобучился и на тестовых данных будет показывать значительно худшие результаты? Именно так предполагали в самом начале появления бустинга и считали, что чем больше взять алгоритмов в композиции, тем сильнее он будет подстраиваться под обучающую выборку и, соответственно, сильнее переобучаться. Но к удивлению исследователей картина оказалась кардинально иной: даже при очень большом числе алгоритмов (порядка 1000) переобучение практически не проявляется и композиция в целом демонстрирует хорошие обобщающие способности на новых тестовых данных.

То есть бустинг ведет себя также как и бэггинг при увеличении числа алгоритмов. И это очень здорово! Это значит, мы можем получать очень хорошие результаты классификации или регрессии просто увеличивая число простых алгоритмов, входящих в бустинг. Благодаря этому свойству он приобрел очень широкую популярность и является буквально настольным инструментов инженеров в области машинного обучения. Например, знаменитый Матрикснет от компании Яндекс использует бустинг над решающими деревьями для формирования ранжирования в поисковой выдаче. Правда там используется алгоритм не AdaBoost, а более совершенная техника. Но о некоторых этих аспектах мы поговорим уже на последующих занятиях.

Видео по теме