Bagging vs Boosting

Один врач может ошибиться с диагнозом, но консилиум из десяти специалистов ошибается намного реже. Что, если применить тот же принцип к алгоритмам машинного обучения? Взять десятки слабых моделей и объединить их в одну сильную? Именно это делают ансамблевые методы, и два главных подхода - Bagging и Boosting - делают это принципиально по-разному. Один строит команду независимых экспертов и собирает голоса. Другой выстраивает цепочку, где каждый следующий учится именно на провалах предыдущих. Какой подход лучше? Зависит от ситуации - и после этого урока вы будете точно знать, когда какой выбирать.

• **Kaggle-соревнования:** XGBoost и LightGBM (Boosting) были winning solution в большинстве соревнований на табличных данных 2015-2023 годов - от предсказания оттока клиентов до обнаружения мошенничества
• **Netflix Prize (1M):** победившая команда использовала ансамбль из сотен моделей - сочетание bagging, boosting и stacking позволило улучшить рекомендации на 10.06% по сравнению с базовым алгоритмом Netflix
• **Банковский скоринг:** Сбербанк, Тинькофф и другие банки используют Gradient Boosting (CatBoost от Яндекса) для оценки кредитоспособности - решение по заявке за секунды вместо дней ручного анализа

Теоретическая головоломка, ставшая практическим движком

Бустинг начинался как абстрактный вопрос, а не как алгоритм. В 1990 году Роберт Шапире ответил на головоломку, поставленную Майклом Кернсом и Лесли Вэлиантом: эквивалентен ли по силе обучатель, работающий лишь чуть лучше случайного угадывания (слабый), обучателю, который можно сделать сколь угодно точным (сильному)? Шапире доказал, что да, в работе «The Strength of Weak Learnability», и его конструктивное доказательство стало первой процедурой бустинга. Теория стала практикой в 1995 году, когда Йоав Фройнд и Роберт Шапире представили AdaBoost, перевзвешивающий ошибочно классифицированные примеры так, чтобы каждая новая модель сосредотачивалась на трудных случаях; позже это принесло им премию Гёделя. Тем временем Лео Брейман атаковал проблему со стороны дисперсии: в 1996 году он опубликовал Bagging, обучающий множество моделей на bootstrap-перевыборках с последующим усреднением, и вскоре развил его в Random Forest. Два ответа на один вопрос об объединении слабых моделей - последовательная коррекция и параллельное усреднение - стали двумя опорами ансамблевого обучения.

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

• Random Forest

Bootstrap: создание разнообразия

Представьте, что вам нужно оценить среднюю зарплату в городе, но опросить всех жителей невозможно. Вы берёте случайную выборку из 1000 человек и считаете среднее. Но насколько точна эта оценка? Может, вам просто повезло и в выборку попали одни программисты? **Bootstrap** - статистический метод, изобретённый Брэдли Эфроном в 1979 году, - решает именно эту проблему: он позволяет оценить надёжность любой статистики, имея только одну выборку.

Идея поразительно проста: если у нас есть выборка из N объектов, мы создаём **новую выборку того же размера N**, случайно выбирая объекты **с возвращением**. Это значит, что один и тот же объект может попасть в новую выборку несколько раз, а какие-то объекты не попадут вовсе. Повторяя этот процесс сотни раз, мы получаем сотни разных выборок - и каждая даёт немного другую статистику.

**Магическое число 63.2%** Вероятность того, что конкретный объект НЕ попадёт в bootstrap-выборку за N попыток: P(не попал) = (1 - 1/N)^N При большом N это стремится к 1/e = 0.368. Значит, каждая bootstrap-выборка содержит примерно **63.2% уникальных** объектов из оригинала. Оставшиеся 36.8% - это объекты, не попавшие в выборку, их называют **Out-of-Bag (OOB)** и используют как бесплатный validation set.

Зачем всё это в контексте ML? Главная проблема одной модели - она **зависит от конкретных данных**. Чуть изменили обучающую выборку - модель может дать совершенно другие предсказания. Это и есть **высокий variance**. Bootstrap позволяет из одного dataset создать множество разных выборок, обучить на каждой отдельную модель - и получить ансамбль с разнообразными "мнениями". А как эти мнения объединить - об этом следующий концепт.

Bagging: параллельные ансамбли

Лео Брейман в 1996 году предложил идею, которая оказалась гениально простой: обучить множество моделей на разных bootstrap-выборках и **объединить их предсказания**. Он назвал этот метод **Bagging** - от **B**ootstrap **AGG**regat**ING**. Ключевое слово - aggregating: сила не в отдельных моделях, а в способе их объединения.

Для **классификации** bagging использует голосование большинством: каждая модель голосует за свой класс, побеждает класс с наибольшим числом голосов. Для **регрессии** - просто усредняет предсказания всех моделей. Почему это работает? Математически, если ошибки моделей **некоррелированы**, то усреднение N моделей уменьшает variance в N раз. На практике ошибки частично коррелированы (все модели обучены на похожих данных), но эффект всё равно значительный.

**Bias-Variance разложение для Bagging** Ошибка модели = Bias^2 + Variance + Irreducible Noise. - **Bias** у bagging остаётся примерно таким же, как у базовой модели. Усреднение не исправляет систематическую ошибку - если каждое дерево underfits, ансамбль тоже underfits. - **Variance** значительно снижается. Для N некоррелированных моделей с variance = sigma^2, ансамбль имеет variance = sigma^2 / N. - Поэтому bagging наиболее эффективен с **нестабильными** моделями (high variance): глубокие деревья решений, нейронные сети. - Для стабильных моделей (k-NN, линейная регрессия) bagging почти бесполезен.

**Random Forest - это Bagging + случайный выбор признаков.** Брейман заметил, что деревья в bagging всё ещё слишком похожи друг на друга: если один признак очень сильный, все деревья будут его использовать, и их ошибки будут коррелировать. Решение: на каждом разбиении каждого дерева рассматривать только случайное подмножество из sqrt(p) признаков (для классификации) или p/3 (для регрессии). Это **декоррелирует** деревья и усиливает эффект bagging.

**Когда Bagging НЕ помогает:** - Если базовая модель имеет **высокий bias** (underfitting) - усреднение не исправит систематическую ошибку. Все модели будут одинаково ошибаться. - Если базовая модель **стабильна** (low variance) - нет смысла усреднять почти одинаковые предсказания. Линейная регрессия на bootstrap-выборках даст почти те же коэффициенты. - Если данных **очень мало** - bootstrap-выборки будут слишком похожи, разнообразие ансамбля снизится.

Boosting: последовательное обучение

Boosting переворачивает логику bagging с ног на голову. Вместо того чтобы обучать модели **параллельно и независимо**, boosting обучает их **последовательно**, и каждая следующая модель целенаправленно исправляет ошибки предыдущих. Если bagging - это демократия (каждая модель голосует независимо), то boosting - это **итеративное улучшение** (каждая модель учится на провалах команды).

Исторически первый алгоритм boosting - **AdaBoost** (Adaptive Boosting), предложенный Фройндом и Шапире в 1997 году. Идея: присвоить каждому обучающему примеру вес. Изначально все веса одинаковы. После обучения первой модели **неправильно** классифицированные примеры получают больший вес, а правильные - меньший. Следующая модель обучается на тех же данных, но с новыми весами - и поэтому фокусируется на «трудных» примерах.

**Gradient Boosting - обобщение идеи Boosting** Gradient Boosting (Фридман, 1999) заменяет перевзвешивание примеров на более общую идею: каждая следующая модель обучается предсказывать **остатки (residuals)** - разницу между истинными значениями и текущим предсказанием ансамбля. - Раунд 1: Модель M1 предсказывает y. Остаток r1 = y - M1(x). - Раунд 2: Модель M2 предсказывает r1. Ансамбль = M1(x) + M2(x). - Раунд 3: Модель M3 предсказывает r2 = y - M1(x) - M2(x). - ... Это эквивалентно **градиентному спуску в функциональном пространстве** - каждая модель делает шаг в направлении, уменьшающем функцию потерь. Отсюда название.

Boosting уменьшает **bias** ансамбля: даже если каждая отдельная модель слабая (stump - дерево с одним разбиением), их последовательная комбинация может аппроксимировать сколь угодно сложную функцию. Однако boosting может **увеличить variance** и привести к overfitting, особенно при большом числе раундов или шуме в данных. Поэтому learning rate (скорость обучения) и ранняя остановка - критически важные гиперпараметры.

**Boosting и шум в данных:** Boosting целенаправленно фокусируется на «трудных» примерах. Но если трудный пример - это **выброс или ошибка разметки**, boosting будет упорно пытаться его выучить, жертвуя качеством на нормальных данных. Это главная уязвимость boosting: он **чувствителен к шуму**. В зашумлённых данных bagging часто работает лучше.

Сравнение и выбор

Теперь, когда мы разобрали оба подхода, пора их поставить рядом и понять, когда какой выбирать. Bagging и Boosting - не конкуренты, а **инструменты для разных ситуаций**. Выбор зависит от характера ошибок вашей модели (bias vs variance), качества данных и вычислительных ресурсов.

На практике **Gradient Boosting** (и его реализации XGBoost, LightGBM, CatBoost) чаще побеждает на табличных данных. Исследование 2022 года на 176 datasets из OpenML показало, что gradient boosting уступает только в задачах с очень малым количеством данных или сильным шумом. Kaggle-соревнования подтверждают: XGBoost/LightGBM - самый частый «winning algorithm» на табличных данных. Но Random Forest остаётся отличным выбором как **baseline**: он быстро обучается, не требует сложной настройки гиперпараметров, и даёт надёжный результат «из коробки».

**Современные реализации Gradient Boosting:** - **XGBoost** (2014, Тянь Ци Чэнь) - первый production-ready GB с регуляризацией, обработкой пропусков и параллельным построением деревьев. Доминировал на Kaggle 2015-2018. - **LightGBM** (2017, Microsoft) - leaf-wise рост дерева вместо level-wise, гистограммный подход. В 10-20x быстрее XGBoost на больших данных. - **CatBoost** (2017, Яндекс) - нативная поддержка категориальных признаков через ordered target encoding. Лучше других работает без feature engineering.

Bagging и Boosting - не единственные ансамблевые методы. **Stacking** (stacked generalization) идёт ещё дальше: он обучает мета-модель, которая учится **оптимально комбинировать** предсказания нескольких базовых моделей. Вместо простого голосования или усреднения, stacking может давать разным моделям разный вес в зависимости от контекста. Но это тема отдельного урока.

Ключевые идеи

• **Bootstrap** - выборка с возвращением, каждая содержит ~63.2% уникальных объектов; оставшиеся 36.8% (OOB) служат бесплатным validation set
• **Bagging** (Bootstrap Aggregating) обучает модели параллельно и независимо на bootstrap-выборках, снижает variance, но не bias; наиболее эффективен с нестабильными моделями (деревья решений)
• **Boosting** обучает модели последовательно, каждая исправляет ошибки предыдущих: AdaBoost перевзвешивает примеры, Gradient Boosting обучается на остатках; снижает bias, но может переобучиться на шуме
• **Выбор зависит от ситуации:** Bagging (Random Forest) - надёжный baseline, устойчивый к шуму; Boosting (XGBoost, LightGBM, CatBoost) - часто точнее на чистых данных, но требует настройки - как консилиум врачей из нашего примера, где важен не только метод объединения мнений, но и качество исходных данных

Связанные темы

Bagging и Boosting - фундамент ансамблевых методов. Дальше мы углубимся в конкретные алгоритмы и продвинутые способы комбинирования моделей:

• Random Forest — Bagging + случайный выбор признаков - самая популярная реализация bagging, изученная ранее как отдельный алгоритм
• Gradient Boosting в деталях — Глубокое погружение в механику Gradient Boosting: XGBoost, LightGBM, CatBoost, настройка гиперпараметров и регуляризация
• Stacking — Третий ансамблевый подход: мета-модель учится оптимально комбинировать предсказания нескольких базовых моделей вместо простого голосования
• Деревья решений — Базовый алгоритм, лежащий в основе и Random Forest (bagging), и всех Gradient Boosting реализаций - понимание деревьев критично для понимания ансамблей

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

• Если Bagging снижает variance, а Boosting - bias, можно ли придумать метод, который снижает оба одновременно? Какие компромиссы это потребует?
• Почему Gradient Boosting доминирует на Kaggle-соревнованиях с табличными данными, но нейронные сети побеждают в компьютерном зрении и NLP? Что определяет границу применимости?
• Компания получила dataset с 30% ошибок в метках (crowdsourcing-разметка). Какой ансамблевый подход вы бы выбрали и почему? Как бы вы адаптировали стандартный pipeline?

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

• ml-12-random-forest — Случайный лес - канонический пример бэггинга
• ml-22-gradient-boosting — Интуиция бустинга ведёт к градиентному бустингу
• ml-23-stacking — Стекинг - третий способ комбинировать много моделей
• prob-08-variance — Компромисс смещение-дисперсия объясняет пользу ансамблей
• stat-18-bootstrap — Бэггинг - бутстрэп-выборка, применённая к моделям
• prob-02-combinatorics