Алгоритм AnyBoost

Справочные данные не проверены и ожидают проверку. Если вы заметили какую то ошибку, напишите пожалуйста в комментариях.

Справочник требует, расстановки ссылок на лица.

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

Описание алгоритма

Алгоритм AnyBoost

Рассмотрим задачу классификации. \mathcal{F} – множество базовых классификаторов, а \mathrm{lin}(\mathcal{F}) – множество всех линейных комбинаций из \mathcal{F}. На каждом шаге алгоритма к текущему классификатору F\in \mathrm{lin}(\mathcal{F}) прибавляется базовый классификатор так, чтобы значение C(F+\varepsilon f)уменьшилось на некоторое значение \varepsilon. То есть в терминах функционального пространства для функции f ищется направление, в котором функция C(F+\varepsilon f) быстрее уменьшается. Наибольшее уменьшение функции потерь наблюдается в случае, когда f максимизирует величину -\left \langle \nabla C(F),f \right \rangle .

  1. Инициализация F_0=0;
  2. Для всех t=0,..,T пока не выполнено условие выхода из цикла;
    1. Получение нового классификатора f_{t+1}, увеличивающего значение -\left \langle \nabla C(F_t), f_{t+1}\right \rangle;
    2. Если -\left \langle \nabla C(F_t),f_{t+1}\right \rangle \le 0 выходим из цикла и возвращаем F_t;
    3. Выбор веса w_{t+1}
    4. Уточнение классификатора F_{t+1}=F_{t}+w_{t+1}f_{t+1}
  3. Возвращаем F_{T+1}

В случае бинарного классификатора Y=\{-1;1\}. Пусть X^l =\{(x_i,y_i)\} – обучающая выборка. Функция потерь  C=\frac{1}{m}\sum^{m}_{i=1}{c(y_iF(x_i))} определяется через дифференцируемую функцию выброса c: \mathbb{R} \to \mathbb{R}. В этом случае -\left \langle \nabla C(F),f \right \rangle = -\frac{1}{m^2}\sum^{m}_{i=1}{y_if(x_i)c'(y_iF(x_i))} , и нахождение классификатора на каждом шаге будет равносильно нахождению классификатора f, минимизирующего взвешенную ошибку.

Методы голосования как частный случай AnyBoost

Алгоритм Функция потерь Размер шага
AdaBoost e^{-yF(x)} Линейный поиск
ARC-X4 {(1-yF(x))}^5 1/t
ConfidenceBoost e^{-yF(x)} Линейный поиск
LogitBoost {\ln(1+e^{-yF(x)})} Метод Ньютона

Особенности алгоритма

  • Алгоритм в значительной доле случаев устойчив к переобучению, даже при использовании большого числа классификаторов.
  • Проявляет нестойкость к переобучению в случае экспоненциальных функций потерь, но она может быть устранен путем использования близких по значению к функции C(F)=\frac{1}{m}\sum^{m}_{i=1}{1-\tanh(\lambda y_iF(x_i))}. В качестве выходного значения будут получаться только выпуклые линейные комбинации классификаторов.
  • Возможно использование модификаций метода – AnyBoost.L1 (с применением нормализации линейной комбинации) и AnyBoost.L2 (метод градиентного спуска используется в выборе коэффициента при норме линейной комбинации, входящей в функцию потерь).

Источник

comments powered by HyperComments

Посмотрите также

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

Бустинг

Бустинг (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда …