Ансамбли моделей

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

Ансамблирование моделей

Идея алгоритма

Обучаем несколько базовых моделей, а затем агрегируем их результаты по какому-либо правилу и выдаем окончательный результат.

Зачем это нужно:

• В совокупности получаем более сложную модель, чем каждая в отдельности
• Уменьшение разбора
• Избежание переобучения/недообучения
• Возможность работы с признаками разной природы (использовать разные алгоритмы)

Для простоты рассмотрим задачу бинарной классификации. Пусть всего $N$ базовых моделей и каждая предсказывает класс $c_1$ или $c_2$. Тогда агрегированный алгоритм может выдавать класс $c_1$ по следующим правилам:

• AND-правило: если все базовые модели выдали $c_1$
• OR-правило: если хотя бы одна базовая модель выдала $c_1$
• $k$-out-of-$N$: если хотя бы $k$ базовых моделей из $N$ выдали $c_1$
• majority vote: если большинство базовых моделей выдало $c_1$

Почему ансамблирование улучшает результат описано здесь.

Обобщение с весами

Также, если используются правила $k$-out-of-$N$ или majority vote, можно каждой базовой модели присвоить вес, основываясь на качестве предсказания на валидационной выборке.

Предсказание класса по уровням ранжирования

Пусть теперь рассматривается задачи многоклассовой классификации с $C$ классами. Пусть каждая $k$-ая базовая модель выдает некую отранжированную информацию о классе объекта:

$c_{k_{1}}\succcurlyeq c_{k_{2}}\succcurlyeq \dots \succcurlyeq c_{k_{C}}$

Это означает, что класс $c_{k_{1}}$ наиболее вероятен для рассматриваемого объекта, а класс $c_{k_{C}}$ --- наименее вероятен.

Пусть $B_{k}(i)$ --- сколько классов было отранжировано ниже $i$-го класса $k$-ой базовой моделью. Чем $B_{k}(i)$ выше, тем более вероятен $i$-ый класс. Поэтому, в качестве совокупного рейтинга построим следующую величину:

$g_{i}(x)=\sum \limits _{k}B_{k}(i,x)$

Тогда результирующее предсказание на объекте $x$:

${\hat {y}}(x)={\underset {i\in [1,\dots ,C]}{\operatorname {argmax} }}~~g_{i}(x)$

Предсказание класса по вероятностям

Опять рассмотрим задачу многоклассовой классификации с $C$ классами. Пусть каждая $k$-ая базовая модель выдает вектор вероятностей из принадлежностей к каждому классу:

$[p^{k}(c_{1}),p^{k}(c_{2}),\dots ,p^{k}(c_{C})]$

Тогда ${\hat {y}}(x)=c_{i}$, где $i={\underset {i\in [1,\dots ,C]}{\operatorname {argmax} }}~~F(p^{1}(c_{i}),p^{2}(c_{i}),\dots ,p^{N}(c_{i}))$

$F$ --- среднее арифметическое или медиана.

Стэкинг моделей

Рассмотрим задачу регрессии. Пусть всего $K$ базовых моделей каждая модель --- это $f_k(x)$ алгоритмов регрессии. Результирующую модель строим следующим образом:

$f(x)=\sum \limits _{k=1}^{K}w_{k}f_{k}(x)$

Можно находить веса следующим образом:

${\hat {w}}={\underset {w}{\operatorname {argmin} }}~\sum \limits _{i=1}^{N}{\mathcal {L}}(y_{i},\sum \limits _{k=1}^{K}w_{k}f_{k}(x_{i}))$

Но такой способ приведет к переобучению. Поэтому будем находить веса при помощи кросс-валидации, а именно: разобьем выборке на $M$ частей. Пусть $fold(i)$ --- та часть, которая содержит $i$-ый объект, а $f_{k}^{-fold(i)}$ --- алгоритм, обученный на всех фолдах, кроме $fold(i)$. Тогда:

${\hat {w}}={\underset {w}{\operatorname {argmin} }}~\sum \limits _{i=1}^{N}{\mathcal {L}}(y_{i},\sum \limits _{k=1}^{K}w_{k}f_{k}^{-fold(i)}(x_{i}))$

Для уменьшения переобучения можно добавить условия на неотрицательность весов или добавить к функционалу регуляризатор $\lambda \sum \limits _{k=1}^{K}(w_{k}-{\dfrac {1}{K}})^{2}$

Обобщенный стэкинг

Предполагаем, что

$f(x)=A_{\theta }(f_{1}(x),\dots ,f_{K}(x))$

,где $\theta$ --- вектор параметров:

${\hat {\theta }}={\underset {\theta }{\operatorname {argmin} }}~\sum \limits _{i=1}^{N}{\mathcal {L}}(y_{i},A_{\theta }(f_{1}^{-fold(i)}(x),\dots ,f_{K}^{-fold(i)}(x)))$

$f_i (x)$:

• Номер класса
• Вектор вероятностей классов
• Любой изначальный или сгенерированный признак

Бэггинг (Bagging)

Генерируем $K$ выборок фиксированного размера $M$, выбирая с возвращением из $N$ имеющихся объектов. Доказывается, что каждый объект попадает в выборку с вероятностью $1-e^{-1}$, если $M=N$.

Настраиваем $K$ базовых моделей на этих выборках и агрегируем результат.

Плюсы:

• Уменьшает переобучение, если базовые модели были переобучены (например, решающие деревья)

Минусы:

• Время обучения увеличивается в $K$ раз

Метод случайных подпространств (Random subspace method)

Разбиваем без возвращения признаки случайных образом (причем, не обязательно, чтобы было одинаковое количество признаков)

• Можно объединять два вышеприведенных подхода, то есть, фактически, выбирать подматрицы матрицы $\mathbb{X}$.

Случайный лес (Random Forest)

Базовые алгоритмы --- решающие деревья. Пусть всего $B$ базовых алгоритмов и размер подвыборки признаков --- $m$. Тогда, алгоритм построения случайного леса следующий:

• Генерируем при помощи бэггинга $B$ выборок
• Обучаем каждое решающее дерево на своей выборке, причем в каждом узле признаки рассматриваются из случайно выбранного подмножества размера $m$ из всех признаков.

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

Плюсы:

• Можно осуществить параллельную реализацию
• Не переобучается с ростом $B$

Минусы:

• Менее интерпретируемый, чем решающее дерево
• Деревья не исправляют ошибки друг друга

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

Extra Random Trees

В каждом узле дерева генерируется случайно $m$ пар (признак, порог).

Плюсы:

• Упрощение модели Random Forest
• Более быстрые, чем Random Forest
• Не переобучается с ростом $B$

Минусы:

• Bias выше, чем у Random Forest, а variance --- меньше.

Для обучения должны использоваться глубокие деревья

Ссылки

слайды Китова

семинары Соколова по бэггингу

семинары Соколова по Random Forest