Boosting: weak learner → strong learner

1988 год. Майкл Кернс и Лесли Вэлиант задают вопрос в духе теории сложности: эквивалентна ли «слабая» обучаемость «сильной»? Если алгоритм гарантированно бьёт случайное угадывание хотя бы на 1% - можно ли собрать из него классификатор с точностью 99%? В 1990 году Роберт Шапир ответил: да, конструктивно. В 1995-м Фройнд и Шапир создали AdaBoost - алгоритм, который в 2003 году получил Гёдель-премию (высшая награда в CS). А загадка «почему AdaBoost не переобучается?» держалась несколько лет, пока margin theory не дала ответ.

• Applied in practice.

Предварительные знания

• (no prerequisites)

• VC dimension: как измеряется сложность класса гипотез

Гипотеза Кернса-Вэлианта: слабый = сильный?

1988 год. Майкл Кернс и Лесли Вэлиант задают вопрос, который кажется странным: если у вас есть алгоритм, который угадывает правильно хотя бы в 51% случаев - можно ли из него сделать алгоритм с точностью 99%? Или между «немного лучше случайного» и «почти идеальным» - непреодолимая пропасть?

Слабый обучающийся (weak learner): алгоритм A - это weak PAC-learner для класса C, если существует γ > 0 такое, что для любого распределения D и любой целевой функции c ∈ C алгоритм A с вероятностью ≥ 3/4 возвращает гипотезу h с ошибкой ε(h) ≤ 1/2 - γ. Параметр γ - «преимущество над случайным угадыванием». Сильный обучающийся (strong learner): то же, но ε(h) ≤ ε для произвольного ε > 0.

Кернс и Вэлиант сформулировали гипотезу, что эти два понятия эквивалентны. Прямое направление - сильный обучающийся является слабым (берём γ = 1/2 - ε). Содержательное - может ли слабый обучающийся стать сильным?

В 1990 году Роберт Шапир доказал: ДА. Его первый алгоритм использовал три вызова слабого обучающегося. Идея: обучи h1 на исходном распределении. Обучи h2 на отфильтрованном распределении, где h1 ошибается ровно в половине случаев. Обучи h3 на примерах, где h1 и h2 расходятся. Итоговый классификатор: мажоритарное голосование h1, h2, h3. Затем конструкция применяется рекурсивно, чтобы загнать ошибку сколь угодно низко.

Если существует weak PAC-learner для класса C с преимуществом γ > 0, то существует strong PAC-learner для C. Доказательство конструктивное: оно даёт явный алгоритм, а не просто гарантирует существование.

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

AdaBoost: перевзвешивание ошибок

Алгоритм Шапира 1990 был теоретически важен, но практически неудобен: жёсткая рекурсивная структура с трудно настраиваемыми размерами подвыборок. В 1995 году Йоав Фройнд и Роберт Шапир представили AdaBoost (EuroCOLT 1995, полная версия в Journal of Computer and System Sciences, 1997) - алгоритм, который запускает слабый обучающийся T раз, каждый раз меняя веса примеров так, чтобы следующий обучающийся концентрировался на ошибках предыдущего.

Вход: обучающая выборка (x1,y1),...,(xm,ym), yi ∈ {-1,+1}, число раундов T. Инициализация: D1(i) = 1/m. Для t = 1,...,T: обучи weak learner на Dt, получи ht; вычисли ошибку εt = Σ_{i: ht(xi)≠yi} Dt(i); вычисли вес αt = 1/2 · ln((1-εt)/εt); обнови Dt+1(i) = Dt(i) · exp(-αt · yi · ht(xi)) / Zt, где Zt - нормировочная константа. Итоговый классификатор: H(x) = sign(Σt αt ht(x)).

Смысл формулы весов: если ht правильно классифицирует пример i (yi · ht(xi) = +1), то вес уменьшается на коэффициент exp(-αt). Если ошибается (yi · ht(xi) = -1), вес увеличивается. Следующий обучающийся видит выборку, где «трудные» примеры стали важнее.

Теорема о тренировочной ошибке: если каждый слабый обучающийся имеет преимущество γt ≥ γ > 0, то после T раундов тренировочная ошибка AdaBoost не превышает exp(-2Tγ²). Значит, при T = O(1/γ² · log(1/δ)) тренировочная ошибка обнуляется. Но это не говорит о generalization - там история другая.

Обратите внимание на динамику: в начале все примеры равноправны (вес = 1/m). К раунду 20-30 несколько «трудных» примеров получают веса в 10-100 раз больше нормального. Weak learner в каждом раунде видит «другую задачу» - фактически AdaBoost последовательно решает всё более сложные подзадачи.

Margin theory: почему AdaBoost не переобучается

Аномалия, которую наблюдали в 1996-1997 годах: AdaBoost продолжает улучшать тестовую точность даже после того, как тренировочная ошибка стала нулевой. По классической теории (VC dimension, bias-variance) это невозможно - после нулевой тренировочной ошибки модель должна начать переобучаться. Почему AdaBoost ведёт себя иначе?

Ответ дала работа Шапира, Сингера, Бартлетта и Фройнда 1998 года: решает не только правильность классификации, но и уверенность - margin.

Для финального классификатора H(x) = sign(Σt αt ht(x)) margin примера (xi, yi) определяется как: ρi = yi · (Σt αt ht(xi)) / Σt|αt|. Это нормализованный «счёт уверенности» - значение в [-1, +1]. Положительный margin означает правильную классификацию с запасом. Минимальный margin по всей выборке: ρ = min_i ρi.

Ключевая теорема (Schapire-Singer-Bartlett-Freund 1998): с вероятностью 1-δ по тестовой выборке, для любого θ > 0:

Здесь d - VC dimension слабых обучающихся, m - размер выборки. Важно: этот bound не зависит от числа раундов T напрямую - только через margins. Если AdaBoost после нулевой train error продолжает увеличивать margin, bound продолжает уменьшаться без переобучения.

Эмпирическое наблюдение, подтверждённое теорией: AdaBoost не просто добивается нулевой ошибки - он продолжает «отталкивать» примеры от границы решения. Каждый новый раунд увеличивает margin для примеров с малым запасом. Это объясняет, почему добавление раундов сверх нулевой ошибки не вредит - ансамбль становится «увереннее», а не «сложнее».

Парадокс разрешён: AdaBoost не является «более сложной» моделью после добавления раундов в смысле VC dimension. VC dimension ensemble зависит от d слабых обучающихся и T, но bound через margin от T не зависит. Если margin растёт, bound уменьшается независимо от T.

От AdaBoost к XGBoost: gradient boosting

AdaBoost использует экспоненциальную функцию потерь. Фридман, Хасти и Тибширани (Annals of Statistics, 2000) показали, что AdaBoost - частный случай более общего принципа - gradient boosting, формализованного в работе Фридмана «Greedy Function Approximation: A Gradient Boosting Machine» (1999 tech report; Annals of Statistics, 2001). Каждый раунд boosting'а добавляет функцию в ансамбль, которая аппроксимирует антиградиент потерь в функциональном пространстве.

Вместо фиксированной экспоненциальной потери AdaBoost используем произвольную дифференцируемую L(y, F(x)). На каждом шаге вычисляем псевдорезидуалы ri = -∂L/∂F(xi) и обучаем слабый обучающийся на них. Это «функциональный градиентный спуск» - F(x) изменяется в пространстве функций, а не параметров.

XGBoost (Чэнь и Гэстрин, KDD 2016) добавляет: второй порядок Тейлора для более точной аппроксимации потерь, L1/L2 регуляризацию деревьев, histogram-based split finding. LightGBM (Microsoft 2017) решает проблему скорости: вместо сортировки O(n·d) для нахождения сплитов использует гистограммы O(n·bins), что на больших данных даёт 20-40x ускорение.

AdaBoost = gradient boosting с экспоненциальной потерей L(y, F) = exp(-y·F). Псевдорезидуалы при этой потере: ri = yi · exp(-yi · F(xi)) - это в точности взвешенные ошибки AdaBoost. Перевзвешивание примеров в AdaBoost и вычисление псевдорезидуалов в gradient boosting - один и тот же механизм в разных формулировках.

Главное

• Теорема Шапира 1990: weak и strong PAC-обучаемость эквивалентны - алгоритм с преимуществом γ > 0 можно «усилить» до произвольной точности
• AdaBoost: T раундов перевзвешивания примеров, тренировочная ошибка падает экспоненциально как exp(-2Tγ²)
• Margin theory: AdaBoost не переобучается, потому что продолжает увеличивать margin после нулевой train error - generalization bound зависит от margin, а не T
• Gradient boosting = AdaBoost, обобщённый на произвольные дифференцируемые потери через функциональный градиентный спуск; XGBoost и LightGBM - производственные реализации

Связи с другими концепциями

Boosting и SVM независимо пришли к margin theory - оба алгоритма стремятся максимизировать «расстояние до границы решения», только разными способами. PAC-learning (урок lt-01) даёт язык для формулировки теоремы об эквивалентности. VC dimension (lt-04) входит в margin bound через параметр d слабых обучающихся. Random Forest - альтернативный ensemble метод на основе bagging, а не boosting: деревья обучаются параллельно и независимо.

• Связанные темы — См. курс

Вопросы для размышления

• AdaBoost сильно концентрирует веса на «трудных» примерах. В реальных данных часто трудные примеры - это выбросы или ошибки разметки. Как это влияет на поведение алгоритма? Почему XGBoost и LightGBM по умолчанию используют регуляризацию, которой нет в оригинальном AdaBoost?

Связанные уроки

• stat-01-sampling