Advertisement

Jurassic World: Dominion Dominates Fandom Wikis - The Loop

01:25

Бустинг

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

Процедура последовательного построения линейного ансамбля (Forward stagewise additive modeling (FSAM))

Рассматривается задача классификации или регрессии. Пусть — базовые алгоритмы, — числовые коэффициенты. Тогда — линейный ансамбль. Для задачи регрессии представляет собой значение целевой переменной. Для задачи классификации представляет собой уверенность в принадлежности объекта к определённому классу.

Совместная оптимизация , затратна по времени для больших . Основная идея FSAM состоит в жадной оптимизации . После жадной процедуры можно дополнительно настроить , решив задачу линейной регрессии/классификации с признаками .

Алгоритм жадной оптимизации

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

Комментарии:

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

AdaBoost

Рассмотрим задачу бинарной классификации с метками . Общий вид базового алгоритма , классификатор , функция потерь . Для построения ансамбля AdaBoost используем модификацию FSAM.

Алгоритм (дискретная версия)

  • Вход: обучающая выборка ; базовый алгоритм , обучаемый на взвешенных выборках; — число итераций
  • Инициализация весов
  • Для :
    • Обучить на обучающей выборке, используя веса
    • Вычислить взвешенную ошибку классификации
    • Если или : остановить процедуру
    • Вычислить
    • Увеличить все веса, где базовый алгоритм ошибся:
  • Выход: результирующий ансамбль

Детали нахождения () в дискретном AdaBoost

Начальное приближение

Рассмотрим -ую итерацию процедуры FSAM:

Так как в алгоритме , то следует искать следующим образом (первое слагаемое условно является константой, тогда уменьшаем второе неотрицательное слагаемое):

Дифференцирование оптимизируемого функционала

Обозначим . — выпуклый, значит, необходимое условие экстремума является ещё и достаточным:

Комментарии к вычислению весов ()

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

Материалы сообщества доступны в соответствии с условиями лицензии CC-BY-SA, если не указано иное.