Бустинг

Алгоритм бустинга (boosting [1]) строит прогноз в виде ансамбля (композиции) базовых моделей:

$$f_0(\mathbf{x}),f_1(\mathbf{x}),f_2(\mathbf{x}),...f_M(\mathbf{x})$$

Агрегирующая модель, на базе которой строится итоговый прогноз, представляет собой линейную комбинацию базовых моделей с настраиваемыми весами:

$$G_M(\mathbf{x})=f_0(\mathbf{x})+c_1 f_1(\mathbf{x})+c_2 f_2(\mathbf{x})+...+c_M f_M(\mathbf{x})$$

Все базовые модели, кроме начального приближения $f_0(\mathbf{x})$, берутся из одного семейства.

Как правило, начальное приближение выбирается тождественным нулём или настраиваемой константой, а остальные модели - решающими деревьями небольшой глубины.

Типы решаемых задач

Смысл $G_M(\mathbf{x})$ меняется в зависимости от решаемой задачи:

• для регрессии $G_M(\mathbf{x})$ предсказывает регрессионный прогноз:

  $$\widehat{y}(\mathbf{x})=G_{M}(\mathbf{x})$$

• для бинарной классификации $G_M(\mathbf{x})$ представляет собой рейтинг положительного класса по сравнению с отрицательным. Итоговый прогноз $y\in\{-1,+1\}$ строится как функция взятия знака $G_M(\mathbf{x})$ (+1 для положительных и -1 для отрицательных аргументов):

  $$\widehat{y}(\mathbf{x})=\text{sign}( G_{M}(\mathbf{x}) )$$

• в многоклассовой классификации на $C$ классов $G_M(\mathbf{x})=[G_M^1(\mathbf{x}),...G_M^C(\mathbf{x})]$ представляет собой вектор рейтингов для каждого класса, а прогноз строится по принципу назначения класса, обладающего максимальным рейтингом:

  $$\hat{y}=\arg\max_c \{G_{M}^1(\mathbf{x}),...G_{M}^C(\mathbf{x})\}$$

Принцип построения ансамбля

Базовые модели, кроме начального приближения $f_0(\mathbf{x})$, выбираются из одного класса, но неравнозначны между собой, поскольку настраиваются последовательно одна за другой:

1. $f_0(\mathbf{x})$ настраивается приближать целевую величину $y$;

2. $c_1 f_1(\mathbf{x})$ учится исправлять ошибки $G_0(\mathbf{x})=f_0(\mathbf{x})$;

3. $c_2 f_2(\mathbf{x})$ учится исправлять ошибки $G_1(\mathbf{x})=f_0(\mathbf{x})+c_1 f_1(\mathbf{x})$;

4. $\cdots$

5. $c_M f_M(\mathbf{x})$ учится исправлять ошибки $G_{M-1}(\mathbf{x})=f_0(\mathbf{x})+c_1 f_1(\mathbf{x})+...+c_{M-1}f_{M-1}(\mathbf{x})$.

Более формально, решаются следующие задачи:

1. Настраиваем начальное приближение

   $$f_{0}(\mathbf{x})=\arg\min_{f}\sum_{n=1}^{N}\mathcal{L}(f(\mathbf{x}_{n}),y_{n})$$

2. Для $m=1,2,...M$:

   находим коррекцию:

   $$(c_{m},f_{m}):=\arg\min_{f,c}\sum_{n=1}^{N}\mathcal{L}(G_{m-1}(\mathbf{x}_{n})+cf(\mathbf{x}_{n}),\,y_{n})$$

   обновляем ансамбль:

   $$G_{m}(\mathbf{x}):=G_{m-1}(\mathbf{x})+c_{m}f_{m}(\mathbf{x})$$

3. Возвращаем $G_M(\mathbf{x})$.

Описанная процедура также известна как forward stagewise additive modeling [2].

На шаге 2 часто коэффициент $c_m$ не настраивается, а берётся малой константой, называемой шаг обучения (learning rate).

Особенности реализации

Для эффективности применения ансамбля усреднение должно происходить по многим базовым моделям, поэтому в бустинге их число измеряется сотнями и даже тысячами.

Для того, чтобы строить ансамбль из большого числа моделей, базовые модели не должны быть слишком точными, чтобы оставлять пространство для дальнейших уточнений последующими уточняющими моделями. Для этого, в частности, используются следующие принципы:

• Начальное приближение полагается тождественному нулю $f_0(\mathbf{x})\equiv 0$ либо находится как наилучший константный прогноз $f_0(\mathbf{x})\equiv c\in \mathbb{R}$.

• Последующие базовые модели $f_1(\mathbf{x}),...f_M(\mathbf{x})$ берутся простыми и неточными. Чаще всего это решающие деревья небольшой глубины (~1-5) или с ограничением на максимальное число листьев (~2-32).

  Какую модель получим, если будем строить бустинг над линейными моделями?

  Комбинируя с весами линейные модели, мы снова получим линейную модель! Поэтому бустинг над линейными моделями не используется. Хотя можно взять линейную модель в качестве начального приближения, а последующие базовые модели брать уже из другого семейства.

• На каждой итерации настраивать модель $f_m(\mathbf{x})$ и коэффициент $c_m$ при ней можно неточно. Часто $c_m$ просто берут малой константой, так как настройка $f_m(\mathbf{x})$ уже настраивает общий масштаб изменения.

Литература

1. Wikipedia: boosting (machine learning).

2. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. – Springer Science & Business Media, 2009.