Boosting: от слабого к сильному классификатору

OpenAI в 2024 опубликовали «weak-to-strong generalization»: GPT-2 обучает GPT-4 лучше, чем человеческие аннотаторы. Это буквально boosting теория 1997 года, применённая к alignment. XGBoost выигрывает Kaggle соревнования. LightGBM - стандарт в промышленности для tabular ML. Boosting - живая теория с прямым применением.

• **XGBoost/LightGBM:** стандарт для fraud detection, click-through rate, ценообразования в Uber/Airbnb/Booking. 2016 KDDCup - 10 из 10 winning solutions использовали XGBoost.
• **OpenAI weak-to-strong:** GPT-2 как «weak supervisor» для GPT-4 через boosting-подобный итеративный процесс. Теоретическое обоснование - margin bounds.
• **Gradient Boosted Trees в Search:** Яндекс MatrixNet (2009), Google BM25+GBDT ranker - ranking в поисковых системах на gradient boosting десятилетиями.

Слабый классификатор + Hedge = сильный обобщающий

**OpenAI использует weak-to-strong generalization для выравнивания GPT-4 через GPT-2.** Это прямое применение boosting теории: слабый учитель (GPT-2) через итеративный процесс обучает сильного ученика (GPT-4). Оригинальный AdaBoost 1997 года предвосхитил этот принцип.

**Слабый классификатор:** h: X → {-1, +1} с accuracy 50% + γ (чуть лучше случайного, γ > 0). **Boosting:** объединить T слабых классификаторов в один сильный H с accuracy → 1. Schapire 1990 доказал: теоретически возможно. Freund-Schapire 1997 (AdaBoost) нашли практический алгоритм.

**AdaBoost протокол:** 1. Инициализация: равномерные веса D₁(i) = 1/n 2. Для t = 1, ..., T: a. Обучить hₜ на взвешенной выборке с весами Dₜ b. Ошибка: εₜ = Σᵢ Dₜ(i)·1[hₜ(xᵢ) ≠ yᵢ] c. αₜ = (1/2)·log((1-εₜ)/εₜ) (вес классификатора) d. Обновить: Dₜ₊₁(i) ∝ Dₜ(i)·exp(-αₜ·yᵢ·hₜ(xᵢ)) 3. H(x) = sign(Σₜ αₜ·hₜ(x)) Training error: E_train ≤ exp(-2·Σₜ γₜ²) → экспоненциально убывает!

Почему boosting обобщает после нулевой training error

AdaBoost достигает нулевого training error за ~20 раундов. Классическая VC теория предсказывает: VC dimension ансамбля растёт с T - значит, generalization должна ухудшаться. На практике test accuracy продолжает расти ещё 1000 раундов. Объяснение: **margin theory**.

**Margin-based bound для boosting:** Margin: ρᵢ = yᵢ · H(xᵢ) / ||α||₁ - насколько «уверенно» H классифицирует xᵢ Schapire-Singer-Bartlett-Lee (1998): E_test ≤ Pr_train[margin ≤ θ] + O(√(d·log²T / (m·θ²))) Ключ: первый член. Пока AdaBoost продолжает работать, margin растёт у большинства примеров. Bound уменьшается, даже если VC dimension ансамбля растёт! **Связь с Hedge:** AdaBoost - это Hedge на training samples. Examples = «эксперты», rounds = «время». Regret → margin увеличивается.

XGBoost и LightGBM - это gradient boosting, не AdaBoost. Они минимизируют произвольную differentiable loss через functional gradient descent. В Kaggle competitions gradient boosting выигрывает на tabular данных - нейросети проигрывают на структурированных таблицах.

Gradient Boosting: функциональный градиентный спуск

AdaBoost минимизирует экспоненциальный loss. **Gradient Boosting** (Friedman 2001) обобщает: на каждом шаге добавить hₜ, лучше всего аппроксимирующую **антиградиент** текущего loss по предсказаниям. Любой differentiable loss, любой базовый классификатор.

**Gradient Boosting алгоритм:** F₀(x) = argmin_c Σᵢ L(yᵢ, c) Для t = 1, ..., T: 1. Pseudo-residuals: rᵢₜ = -∂L(yᵢ, F(xᵢ))/∂F(xᵢ)|F=Fₜ₋₁ 2. Обучить hₜ регрессионное дерево на rᵢₜ 3. γₜ = argmin_γ Σᵢ L(yᵢ, Fₜ₋₁(xᵢ) + γ·hₜ(xᵢ)) 4. Fₜ(x) = Fₜ₋₁(x) + ν·γₜ·hₜ(x) (ν - shrinkage/learning rate) Для MSE: rᵢₜ = yᵢ - F(xᵢ) - обычные residuals! Для log-loss: rᵢₜ = yᵢ - pᵢ - residuals логистической регрессии.

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

• **AdaBoost:** T слабых классификаторов с ошибкой 50%-γ → training error ≤ exp(-2γ²T). Веса обновляются экспоненциально.
• **AdaBoost = Hedge:** weights ∝ exp(-αₜ·yᵢ·hₜ(xᵢ)) - это буквально exponential weights на training samples.
• **Margin theory:** test error ≤ Pr[margin ≤ θ] + O(√log T / θ√n). Margin растёт после нулевого train error - bound продолжает уменьшаться.
• **Gradient Boosting:** hₜ аппроксимирует антиградиент loss по предсказаниям. MSE → residuals, log-loss → logistic residuals.
• **Shrinkage:** lr < 1 требует больше деревьев, но даёт лучшую регуляризацию. Глубина 3-6 + T=100-1000 + lr=0.01-0.1 - стандартные hyperparameters.

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

Boosting теория и практика:

• Margin Bounds — Теоретическое объяснение почему ансамбли обобщают - margin theory
• Kernel Methods — Следующий урок: RKHS, representer theorem, SVM как margin maximizer

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

• lt-11-margin-bounds — Margin theory объясняет почему boosting обобщает
• lt-15-online-learning — AdaBoost - это Hedge algorithm на training samples
• lt-04-vc-dimension — VC dimension ансамбля растёт, но margin bounds остаются хорошими