Алгоритм AdaBoost: как слабые классификаторы дают сильный

AdaBoost (Adaptive Boosting) - классический алгоритм бустинга, который из набора слабых, едва угадывающих классификаторов собирает один сильный. Идея проста и красива: модели обучаются по очереди, и каждая следующая сосредотачивается на тех объектах, где предыдущие ошиблись. Объекты, которые упорно классифицируются неверно, постепенно «тяжелеют» и притягивают к себе внимание ансамбля. Ниже разберём механику пошагово, выведем ключевые формулы и посмотрим на калькуляторе, как вес одного классификатора зависит от его ошибки.

Что такое бустинг и зачем он нужен

Бустинг - это семейство ансамблевых методов, в которых базовые модели строятся последовательно, а не параллельно. В этом его отличие от бэггинга, где деревья учатся независимо на бутстрэп-выборках. В бустинге каждая новая модель исправляет ошибки уже построенного ансамбля.

AdaBoost, предложенный Йоавом Фройндом и Робертом Шапире в 1995 году, был первым практичным алгоритмом бустинга и принёс авторам премию Гёделя. Главная его задача - снижать смещение (bias): отдельный слабый классификатор систематически недообучен, но их взвешенная сумма приближает сложную разделяющую границу.

Слабый классификатор (weak learner) - это модель, которая работает лишь немного лучше случайного угадывания: её ошибка чуть меньше $0{,}5$ для бинарной задачи. Чаще всего в роли слабого ученика выступает решающий пень (decision stump) - дерево глубиной 1, делающее единственное разбиение по одному признаку. Поразительный результат теории бустинга в том, что из таких заведомо примитивных моделей можно собрать ансамбль со сколь угодно малой ошибкой на обучении, если только каждая базовая модель чуть-чуть лучше монетки.

Перевзвешивание объектов: сердце алгоритма

Ключевой механизм AdaBoost - адаптивные веса объектов. В начале всем $N$ объектам обучающей выборки присваивается одинаковый вес $w_i = 1/N$. После каждого раунда веса пересчитываются: объекты, на которых ансамбль ошибся, получают больший вес, а верно классифицированные - меньший.

Рассчитать для своей задачи

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

Вес классификатора: формула и её смысл

После того как очередной слабый классификатор $h_t$ обучен, считается его взвешенная ошибка - сумма весов объектов, на которых он ошибся:

$$\varepsilon_t = \sum_{i:\, h_t(x_i) \neq y_i} w_i$$

По ней вычисляется вес самого классификатора в итоговом ансамбле:

$$\alpha_t = \frac12 \ln \frac{1 - \varepsilon_t}{\varepsilon_t}$$

Эта формула - не произвольная: она получается минимизацией экспоненциальной функции потерь $\sum_i e^{-y_i F(x_i)}$, которую AdaBoost оптимизирует по сути методом покоординатного спуска. Логику веса хорошо видно на графике.

Рассчитать для своей задачи

При малой ошибке $\varepsilon_t \to 0$ вес $\alpha_t \to +\infty$: почти безошибочный классификатор получает огромное право голоса. При $\varepsilon_t = 0{,}5$ вес обнуляется - классификатор не лучше монетки и в ансамбль не входит. При $\varepsilon_t > 0{,}5$ вес отрицателен, и AdaBoost попросту инвертирует ответы такого классификатора.

Правило обновления весов

Зная $\alpha_t$, веса объектов обновляются по экспоненциальному правилу:

$$w_i \leftarrow w_i \cdot e^{-\alpha_t\, y_i h_t(x_i)}$$

Для бинарных меток $y_i, h_t(x_i) \in \{-1, +1\}$ произведение $y_i h_t(x_i)$ равно $+1$ на верных объектах и $-1$ на ошибочных. Поэтому правило распадается на два случая:

$$\begin{aligned} \text{верный объект:}\quad & w_i \leftarrow w_i \cdot e^{-\alpha_t} \\ \text{ошибочный объект:}\quad & w_i \leftarrow w_i \cdot e^{+\alpha_t} \end{aligned}$$

После этого веса нормируются делением на сумму $Z_t = \sum_i w_i$, чтобы снова получить корректное распределение. Чем больше $\alpha_t$ (чем точнее классификатор), тем сильнее раздвигаются веса верных и ошибочных объектов.

Разберём один раунд на числах. Пусть в выборке 5 объектов с равными весами $w_i = 0{,}2$, и классификатор ошибся на двух из них. Тогда взвешенная ошибка $\varepsilon = 0{,}2 + 0{,}2 = 0{,}4$, вес классификатора $\alpha = \tfrac12\ln\frac{0{,}6}{0{,}4} \approx 0{,}2$. Верные объекты домножаются на $e^{-0{,}2} \approx 0{,}82$, ошибочные - на $e^{+0{,}2} \approx 1{,}22$. После нормировки доля «трудных» объектов в общем весе вырастает примерно с $40\%$ до $46\%$ - именно на них и будет настраиваться следующий слабый классификатор.

Итоговый ансамбль

Когда построены все $T$ слабых классификаторов, финальный прогноз - это взвешенное голосование по знаку:

$$H(x) = \operatorname{sign}\left( \sum_{t=1}^{T} \alpha_t\, h_t(x) \right)$$

Каждый классификатор голосует своим ответом $\pm 1$, но с весом $\alpha_t$: точные модели влияют сильнее, слабые - слабее. Знак суммы и даёт итоговую метку класса. По сравнению с одним деревом или случайным лесом AdaBoost достигает высокой точности за счёт фокуса на трудных примерах, а не за счёт усреднения независимых моделей.

Алгоритм целиком по шагам

Соберём механику в единый цикл:

1. Инициализировать веса $w_i = 1/N$ для всех объектов.
2. Для $t = 1, \dots, T$:
   • обучить слабый классификатор $h_t$ на выборке с весами $w_i$;
   • посчитать взвешенную ошибку $\varepsilon_t$;
   • вычислить вес $\alpha_t = \tfrac12 \ln\frac{1-\varepsilon_t}{\varepsilon_t}$;
   • обновить веса $w_i \leftarrow w_i\, e^{-\alpha_t y_i h_t(x_i)}$ и нормировать.
3. Вернуть ансамбль $H(x) = \operatorname{sign}\sum_t \alpha_t h_t(x)$.

Число раундов $T$ - главный гиперпараметр: слишком малое не успеет снизить ошибку, слишком большое грозит переобучением на шумных данных.

Сильные и слабые стороны

Преимущества AdaBoost:

• Простота и мало настроек. По сути единственный важный параметр - число раундов $T$; базовый ученик обычно фиксирован (пень).
• Высокая точность на чистых данных: ансамбль уверенно снижает смещение.
• Универсальность базы: в роли $h_t$ может выступать почти любой слабый классификатор.

Ограничения:

• Чувствительность к шуму и выбросам. Стабильно неверный объект бесконечно тяжелеет и перетягивает внимание ансамбля на себя.
• Уступает по гибкости градиентному бустингу, где минимизируется произвольная дифференцируемая функция потерь, а не только экспоненциальная.

Частые ошибки

• Брать сильный базовый классификатор. Если $h_t$ слишком мощный (глубокое дерево), он сам переобучится, и смысл бустинга теряется. Нужен именно слабый ученик.
• Игнорировать выбросы. Шумные и ошибочно размеченные объекты в AdaBoost «взрываются» по весу. Перед обучением стоит почистить данные.
• Путать с бэггингом. В бэггинге модели независимы и усредняются для снижения дисперсии; в AdaBoost они последовательны и взвешены для снижения смещения.
• Считать, что $\varepsilon_t > 0{,}5$ ломает алгоритм. Не ломает: вес становится отрицательным, ответы инвертируются. Проблема возникает только при $\varepsilon_t$ ровно $0{,}5$ - такой классификатор бесполезен.
• Брать слишком большое $T$ на шумных данных. Лишние раунды начинают подгонять ансамбль под выбросы.

FAQ

Чем AdaBoost отличается от градиентного бустинга? AdaBoost минимизирует экспоненциальную функцию потерь и делает это через перевзвешивание объектов. Градиентный бустинг обобщает идею: он строит модели по антиградиенту произвольной дифференцируемой функции потерь, что даёт больше гибкости (регрессия, разные метрики, регуляризация).

Можно ли применять AdaBoost к многоклассовой задаче? Да. Базовый алгоритм описан для бинарной классификации, но есть расширения SAMME и AdaBoost.M1, которые обобщают веса и правило обновления на несколько классов.

Почему именно решающий пень используют как слабого ученика? Пень - самая простая модель «чуть лучше монетки»: один порог по одному признаку. Он гарантированно слабый (нужное условие для бустинга), быстро обучается и не переобучается сам, оставляя всю работу по усложнению границы ансамблю.

Коротко

AdaBoost строит сильный классификатор как взвешенную сумму слабых, обучаемых по очереди. После каждого раунда веса ошибочно классифицированных объектов растут, и следующая модель сосредотачивается на трудных примерах. Вес классификатора в ансамбле задаётся формулой $\alpha_t = \tfrac12 \ln\frac{1-\varepsilon_t}{\varepsilon_t}$: он велик при малой ошибке, обнуляется при $\varepsilon_t = 0{,}5$ и отрицателен правее. Итоговый прогноз - знак взвешенного голосования $\sum_t \alpha_t h_t(x)$. Алгоритм прост и точен, но чувствителен к шуму, поэтому требует чистых данных и осторожного выбора числа раундов.