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

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

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

$$\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 [1]):

$$\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*}$$

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

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

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

Рассмотрим задачу бинарной классификации базовыми моделями $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$$

Это переформулировка теоремы Кондорсе [3] о присяжных в терминах машинного обучения.

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

Рассмотрим случайную величину $\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$. Для бинарного случая это означает, что базовые классификаторы могут быть лишь немного лучше случайного угадывания для получения сколь угодно точного прогноза ансамблем!

В чём проблема этого достичь на практике?

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

Литература

1. Krogh A., Vedelsby J. Neural network ensembles, cross validation, and active learning //Advances in neural information processing systems. – 1994. – Т. 7.

2. Liu Y., Yao X. Ensemble learning via negative correlation //Neural networks. – 1999. – Т. 12. – №. 10. – С. 1399-1404.

3. Викиконспекты ИТМО: виды ансамблей.