Ансамблевые методы и бустинг

Один классификатор почти всегда хуже коллектива: разные модели делают разные ошибки, и их объединение снижает суммарную ошибку. Ансамблевые методы — фундамент победных решений в машинном обучении на реальных данных.

Разложение ошибки: смещение и дисперсия

Ошибка любого алгоритма раскладывается: Err = Bias² + Variance + Irreducible noise. Смещение (Bias) — систематическая ошибка из-за неправильных предположений модели: слишком простая модель «не попадает» в правильный ответ даже на бесконечных данных. Дисперсия (Variance) — чувствительность модели к случайным флуктуациям обучающей выборки: сложная модель переподстраивается под каждую обучающую выборку.

Интуиция: стрелок с высоким смещением целится в сторону от мишени; стрелок с высокой дисперсией — метко, но непоследовательно. Хочется ни того ни другого.

Бэггинг: снижение дисперсии

Бэггинг (Bootstrap Aggregation, Breiman, 1994): обучаем B моделей на B бутстрэп-выборках (каждая — случайная выборка с возвращением из исходных n объектов), затем усредняем предсказания. Для регрессии: F̂ = (1/B)ΣF_b(x). Для классификации — большинство голосов.

Почему это работает: если модели независимы и каждая имеет дисперсию σ², то среднее B независимых моделей имеет дисперсию σ²/B. Смещение не меняется, дисперсия уменьшается в B раз.

Случайный лес (Breiman, 2001): бэггинг деревьев с дополнительной рандомизацией. На каждом разбиении узла используется случайное подмножество признаков — √p для классификации, p/3 для регрессии (p — общее число признаков). Дополнительная случайность снижает корреляцию между деревьями → больший прирост от усреднения.

Out-of-bag оценка: каждый объект попадает в бутстрэп-выборку ≈63% раз, значит ≈37% деревьев не видели его при обучении. Их средний прогноз — честная оценка generalization error без отдельной валидации.

Бустинг: снижение смещения

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

Gradient Boosting (Friedman, 2001): Аддитивная модель F_M(x) = F₀(x) + Σ_{m=1}^M hₘ(x). На каждом шаге m новое слабое дерево hₘ аппроксимирует «псевдоостатки» — отрицательный градиент функции потерь по предсказанию:

rᵢₘ = −[∂L(yᵢ, F(xᵢ))/∂F(xᵢ)]|{F=F{m−1}}

Здесь L(y, F) — функция потерь (квадратическая, logloss, Huber и др.), yᵢ — истинное значение, F_{m−1}(xᵢ) — текущее предсказание. Для квадратичной потери rᵢ = yᵢ − F_{m−1}(xᵢ) — обычные остатки. Для logloss — взвешенные остатки. Шаг обучения η ∈ (0,1] контролирует «размер шага» в пространстве функций.

Современные реализации

XGBoost (Chen, Guestrin, 2016): использует разложение Тейлора второго порядка (gᵢ = первый градиент, hᵢ = второй). Структурный счёт листа wⱼ* = −(Σgᵢ)/(Σhᵢ + λ). Регуляризация листьев (λ, γ) предотвращает переобучение. Параллелизм по признакам ускоряет поиск разбиений. Доминировал соревнования Kaggle 2015–2018.

LightGBM: Гистограммный трюк (дискретизация непрерывных признаков в 255 корзин) ускоряет поиск разбиений в 10–20 раз. GOSS (Gradient-based One-Side Sampling): сохраняем все объекты с большим градиентом, случайно семплируем объекты с малым. EFB (Exclusive Feature Bundling): объединяем взаимоисключающие признаки.

CatBoost: Упорядоченный бустинг (ordered boosting) вычисляет остатки для объекта i только по моделям, обученным на подмножестве без i — устраняет data leakage при категориальных признаках. Автоматическое кодирование категориальных признаков через TS (Target Statistics).

Численный пример

Данные: предсказываем цену дома. После двух шагов бустинга F₂(x) = 200 тыс. руб. Истинная цена y = 250 тыс. Остаток r = 50 тыс. Третье дерево h₃ предсказывает 50 тыс., η = 0.1: F₃ = 200 + 0.1·50 = 205 тыс. Процесс медленный, но точный — «черепаха», которая придёт к цели.

Применения в реальном мире

Кредитный скоринг (банки: LightGBM на 500+ признаков), предсказание оттока клиентов (телеком), медицинская диагностика (риск заболевания), рекомендательные системы (ранжирование), предсказание стоимости недвижимости. В 2023 году XGBoost/LightGBM составляли основу решений во всех топ-10 позициях 7 из 10 крупнейших табличных соревнований Kaggle.

Задание: Обучите XGBoost и LightGBM на датасете Boston Housing. Подберите гиперпараметры (n_estimators, max_depth, learning_rate, subsample) через 5-fold CV. Постройте кривые обучения (train/val RMSE vs число деревьев). Сравните OOB-оценку случайного леса с CV-оценкой XGBoost. Какой метод быстрее сходится и даёт лучший результат?