Машинное обучение вики
Метка: rte-source
Метка: rte-source
Строка 77: Строка 77:
 
,где <math>\theta</math> --- вектор параметров:
 
,где <math>\theta</math> --- вектор параметров:
   
<math>\hat \theta = \underset{\theta}{\operatorname{argmin}}~\sum \limits_{i=1}^N \mathcal L(y_i, \sum A_{\theta}(f_1^{-fold(i)}(x), \dots, f_K^{-fold(i)}(x)))</math>
+
<math>\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)))</math>
   
 
<math>f_i(x)</math>:
 
<math>f_i(x)</math>:

Версия 20:20, 25 июня 2017

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

5.png

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

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

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

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

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

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

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

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

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

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

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

Это означает, что класс наиболее вероятен для рассматриваемого объекта, а класс --- наименее вероятен.

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

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

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

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

Тогда , где

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

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

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

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

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

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

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

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

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

:

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

Бэггинг (Bagging)

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

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

Плюсы:

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

Минусы:

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

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

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

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

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

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

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

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

Плюсы:

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

Минусы:

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

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

Extra Random Trees

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

Плюсы:

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

Минусы:

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

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

Ссылки

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

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

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