Математическое обоснование ансамблей

Уточнение прогнозов при равномерном усреднении

Рассмотрим задачу регрессии с усредняющим ансамблем:

$$\widehat{y}(\mathbf{x})=\frac{1}{M}\sum_{m=1}^{M}f_{m}(\mathbf{x})$$

Пусть $\varepsilon_{1},...\varepsilon_{M}$ - ошибки прогнозирования базовыми моделями $f_{1}(\mathbf{x}),...f_{M}(\mathbf{x})$ со средним ноль, дисперсией $\mathbb{D}\varepsilon_{i}=\sigma^{2}$, и пусть эти ошибки имеют попарную корреляцию $\rho$. Тогда ковариация ошибок будет будет

$$\mathbb{E}\varepsilon_{i}\varepsilon_{j}=\rho\sigma^{2}$$

Тогда ожидаемый квадрат ошибки отдельной базовой модели будет

$$\mathbb{E}\left\{ \left(f_{i}(\mathbf{x})-y(\mathbf{x})\right)^{2}\right\} =\mathbb{E}\varepsilon_{i}^{2}=\sigma^{2}, \quad i=1,2,...M.$$

А ожидаемый квадрат ошибки усредняющего ансамбля будет:

$$\mathbb{E}\left\{ \left(\widehat{y}(\mathbf{x})-y(\mathbf{x})\right)^{2}\right\} = \frac{\sigma^{2}}{M}+\left(1-\frac{1}{M}\right)\rho\sigma^{2}$$

Доказательство

$$\begin{aligned}\mathbb{E}\left\{ \left(\widehat{y}(\mathbf{x})-y(\mathbf{x})\right)^{2}\right\} & =\mathbb{E}\left\{ \left(\frac{\sum_{m=1}^{M}\left(f_{m}(\mathbf{x})-y(\mathbf{x})\right)}{M}\right)^{2}\right\} \\ & =\frac{1}{M^{2}}\mathbb{E}\left\{ \left(\sum_{m=1}^{M}\varepsilon_{m}\right)^{2}\right\} \\ & =\frac{1}{M^{2}}\mathbb{E}\left\{ \sum_{m=1}^{M}\varepsilon_{m}^{2}+\sum_{i\ne j}\varepsilon_{i}\varepsilon_{j}\right\} \\ & =\frac{M}{M^{2}}\sigma^{2}+\frac{M^{2}-M}{M^{2}}\rho\sigma^{2}\\ & =\frac{\sigma^{2}}{M}+\left(1-\frac{1}{M}\right)\rho\sigma^{2} \end{aligned}$$

При $\rho=0$ ожидаемый квадрат ошибки ансамбля будет в $M$ раз меньше, чем квадрат ошибки отдельной базовой модели, а при $\rho<0$ он может быть даже меньше за счёт рассогласованности прогнозов и взаимной компенсации ошибок разных моделей.

При максимальной скоррелированности ошибок ($\rho=1$) ожидаемо получим, что квадрат ошибки анасмбля совпадёт с квадратом ошибки отдельной базовой модели, и использование ансамбля преимущества не даёт.

На практике базовые модели будут различными и, скорее всего, будут обладать некоторой положительной корреляцией $\rho\in (0,1)$, поэтому квадрат ошибки ансамбля будет меньше, чем квадрат ошибки одной базовой модели. Положительная скоррелированность вызвана тем, что эти базовые модели будут обучаться предсказывать одну и ту же целевую переменную на одной и той же обучающей выборке. Чтобы уменьшить корреляцию, рекомендуется выбирать базовые модели из разных классов (линейные, метрические, решающие деревья).

Уточнение прогнозов при неравномерном усреднении

Рассмотрим задачу регрессии, решаемую ансамблем

$$G(\mathbf{x})=\sum_{m=1}^{M}w_{m}f_{m}(\mathbf{x})$$

где $w_{m}\ge 0, \sum_{m=1}^M w_{m}=1$ - веса, с которыми мы учитываем базовые модели.

В простейшем случае можно взять равномерное усреднение:

$$w_1=w_2=...=w_M=\frac{1}{M},$$

однако взвешенный учёт позволяет более точным базовым моделям назначать больший вес.

Результат выше (для ожидаемого квадрата ошибки) можно обобщить и на случай взвешенного учёта базовых моделей (выведите!) с обоснованием эффективности ансамблей. Однако здесь мы продемонстрируем другое иллюстративное разложение квадрата ошибки, справедливое даже не для мат. ожидания, для для отдельного объекта $(\mathbf{x},y)$, называемое разложением неоднозначности (ambiguity decomposition):

$$\underset{\text{ошибка ансамбля}}{\underbrace{\left(G(\mathbf{x})-y\right)^{2}}}=\underset{\text{ошибка базовой модели}}{\underbrace{\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y\right)^{2}}}-\underset{\text{неоднозначность}}{\underbrace{\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-G(\mathbf{x})\right)^{2}}}$$

Доказательство

$$\begin{gather*} \sum_{m}w_{m}\left(f_{m}(\mathbf{x})-G(\mathbf{x})\right)^{2}=\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y+y-G(\mathbf{x})\right)^{2}\\ =\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y\right)^{2}+\sum_{m}w_{m}\left(y-G(\mathbf{x})\right)^{2}+2\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y\right)\left(y-G(\mathbf{x})\right) \\ =\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y\right)^{2}+\left(G(\mathbf{x})-y\right)^{2}+2\left(y-G(\mathbf{x})\right)\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y\right)\\ =\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y\right)^{2}+\left(G(\mathbf{x})-y\right)^{2}+2\left(y-G(\mathbf{x})\right)\left(G(\mathbf{x})-y\right)\\ =\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y\right)^{2}+\left(G(\mathbf{x})-y\right)^{2}-2\left(G(\mathbf{x})-y\right)^{2}\\ =\sum_{m}w_{m}\left(f_{m}(\mathbf{x})-y\right)^{2}-\left(G(\mathbf{x})-y\right)^{2} \end{gather*}$$

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

Практический вывод

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

Классификация

Рассмотрим задачу бинарной классификации базовыми моделями $f_{1}(\mathbf{x}),...f_{M}(\mathbf{x})$. Пусть для каждой базовой модели вероятность предсказать правильный класс равна $p>0.5$. Предположим, что модели ошибаются независимо друг от друга, а агрегирующая модель $G(\cdot)$ - голосование по большинству (majority voting), в котором итоговым классом назначается тот класс, за который проголосовало большинство базовых моделей.

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

$$p(G(\mathbf{x})\ne y)\to 0 \text{ при } M\to\infty$$

Доказательство

Рассмотрим случайную величину $\xi_m\in \{0,1\}$, принимающую значение 1, если m-й классификатор верно угадал класс, и значение 0, если неверно. Тогда среднее этих случайных величин $\eta=\frac{\xi_{1}+...+\xi_{M}}{M}$ будет больше 0.5 тогда и только тогда, когда прогноз всего ансамбля будет верным, поскольку это условие характеризует ситуацию, когда большинство базовых классификаторов не ошиблись и назначили верный класс. Вероятность верного прогноза для всего ансамбля будет $P(\eta>0.5)$.

По центральной предельной теореме

$$\begin{gather*} \frac{\sum_{i=1}^{M}\left[\xi_{i}-\mathbb{E}\xi_{i}\right]}{\sqrt{M\mathbb{D}(\xi_{1})}}=\frac{\sum_{i=1}^{M}\left[\xi_{i}-p\right]}{\sqrt{Mp(1-p)}}=\\ \frac{\sqrt{M}}{\sqrt{p(1-p)}}\frac{\sum_{i=1}^{M}\xi_{i}-Mp}{M}=\frac{\sqrt{M}}{\sqrt{p(1-p)}}(\eta-p)\to\mathcal{N}(0,1) \end{gather*}$$

Поэтому $\eta\to\mathcal{N}(p,\frac{p(1-p)}{M})$ при $M\to\infty$.

Обратим внимание, что $\mathbb{E}\eta=p$ и $\mathbb{D}[\eta]=\frac{p(1-p)}{M}\to0 \text{ при } M\to\infty$, откуда следует, что $P(\eta>0.5)\to 1 \text{ при } M\to\infty$ по неравенству Чебышева.

Задача

Сформулируйте и докажите это утверждения для многоклассового случая.

Отметим, что мы потребовали, чтобы базовые модели угадывали верный класс при $p>0.5$. Например, $p=0.51$. Для бинарного случая это означает, что классификаторы могут быть всего лишь немного лучше случайного угадывания. Однако этого всё равно достаточно для построения сколь угодно точного прогноза, если устроить голосование по достаточному числу подобных классификаторов!

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