Содержание
Бустинг
Это процедура с целью построения ансамбля из базовых (иногда говорят, слабых) алгоритмов, имеющего качество, превосходящее качество базового алгоритма. В отличие от бэггинга, это детерминированная процедура, выполняющаяся последовательно, основанная на результатах предыдущей итерации.
Процедура последовательного построения линейного ансамбля (Forward stagewise additive modeling (FSAM))
Рассматривается задача классификации или регрессии. Пусть
— базовые алгоритмы, — числовые коэффициенты. Тогда — линейный ансамбль. Для задачи регрессии представляет собой значение целевой переменной. Для задачи классификации представляет собой уверенность в принадлежности объекта к определённому классу.Совместная оптимизация
, затратна по времени для больших . Основная идея FSAM состоит в жадной оптимизации . После жадной процедуры можно дополнительно настроить , решив задачу линейной регрессии/классификации с признаками .Алгоритм жадной оптимизации
- Вход: обучающая выборка ; функция потерь ; общий вид базового алгоритма — параметр; — число итераций
- Начальное приближение
- Для
- Поиск следующего лучшего алгоритма
- Присвоение
:
- Выход: приближение
Комментарии:
- Значение следует подбирать по валидации.
- Начальное приближение не обязательно решать в пространстве функций , можно или . Ожидается исправление ошибок на последующих итерациях.
- По схожим причинам не требуется высокая точность при нахождении .
- Для некоторых функций потерь FSAM имеет аналитическое решение.
- В общем случае используется схема градиентного бустинга.
AdaBoost
Рассмотрим задачу бинарной классификации с метками
. Общий вид базового алгоритма , классификатор , функция потерь . Для построения ансамбля AdaBoost используем модификацию FSAM.Алгоритм (дискретная версия)
- Вход: обучающая выборка ; базовый алгоритм , обучаемый на взвешенных выборках; — число итераций
- Инициализация весов
- Для
- Обучить на обучающей выборке, используя веса
- Вычислить взвешенную ошибку классификации
- Если или : остановить процедуру
- Вычислить
- Увеличить все веса, где базовый алгоритм ошибся:
:
- Выход: результирующий ансамбль
Детали нахождения ( ) в дискретном AdaBoost
Начальное приближение
Рассмотрим
-ую итерацию процедуры FSAM:
Так как в алгоритме
, то следует искать следующим образом (первое слагаемое условно является константой, тогда уменьшаем второе неотрицательное слагаемое):Дифференцирование оптимизируемого функционала
Обозначим
. — выпуклый, значит, необходимое условие экстремума является ещё и достаточным:
Комментарии к вычислению весов ( )
(избавились от общей константы ). Таким образом, для правильно классифицированных объектов из обучающей выборки с помощью , для неправильно классифицированных объектов с помощью вес на -ой итерации будет равен , значит, классификаторы на последующих итерациях будут считать более важными объекты, неверно классифицированные на предыдущей итерации. Существенно важный недостаток данного ансамбля (комитета) состоит в неустойчивости к выбросам из-за используемой экспоненциальной функции потерь.