Алгоритм AnyBoost
Материал из MachineLearning.
(→Особенности алгоритма) |
|||
Строка 48: | Строка 48: | ||
==Особенности алгоритма== | ==Особенности алгоритма== | ||
*Алгоритм в значительной доле случаев устойчив к переобучению, даже при использовании большого числа классификаторов. | *Алгоритм в значительной доле случаев устойчив к переобучению, даже при использовании большого числа классификаторов. | ||
- | *Проявляет нестойкость к переобучению в случае экспоненциальных функций потерь, но | + | *Проявляет нестойкость к переобучению в случае экспоненциальных функций потерь, но она может быть устранен путем использования близких по значению к функции <tex>C(F)=\frac{1}{m}\sum^{m}_{i=1}{1-\tanh(\lambda y_iF(x_i))}</tex>. В качестве выходного значения будут получаться только выпуклые линейные комбинации классификаторов. |
*Возможно использование модификаций метода - AnyBoost.L<sub>1</sub> (с применением нормализации линейной комбинации) и AnyBoost.L<sub>2</sub> (метод градиентного спуска используется в выборе коэффициента при норме линейной комбинации, входящей в функцию потерь). | *Возможно использование модификаций метода - AnyBoost.L<sub>1</sub> (с применением нормализации линейной комбинации) и AnyBoost.L<sub>2</sub> (метод градиентного спуска используется в выборе коэффициента при норме линейной комбинации, входящей в функцию потерь). | ||
+ | |||
==См. также== | ==См. также== | ||
*[[Алгоритм AdaBoost]] | *[[Алгоритм AdaBoost]] |
Версия 22:08, 9 февраля 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Алгоритм AnyBoost - класс алгоритмов, представляющих бустинг как процесс градиентного спуска. В основе алгоритма лежит последовательное уточнение функции, представляющей собой линейную комбинацию базовых классификаторов, с тем чтобы минимизировать функцию потерь. В класс AnyBoost входят практически все алгоритмы бустинга как частные случаи.
Содержание[убрать] |
Описание алгоритма
Алгоритм AnyBoost
Рассмотрим задачу классификации. Пусть - множество базовых классификаторов, а
- множество всех линейных комбинаций из
.
На каждом шаге алгоритма к текущему классификатору
прибавляется базовый классификатор так, чтобы значение
уменьшилось на некоторое значение
. То есть в терминах функционального пространства для функции
ищется направление, в котором функция
быстрее уменьшается. Наибольшее уменьшение функции потерь наблюдается в случае, когда
максимизирует величину
.
- Инициализация
;
- Для всех
пока не выполнено условие выхода из цикла;
- Получение нового классификатора
, увеличивающего значение
;
- Если
выходим из цикла и возвращаем
;
- Выбор веса
- Уточнение классификатора
- Получение нового классификатора
- Возвращаем
В случае бинарного классификатора .
Пусть
- обучающая выборка.
Функция потерь
определяется через дифференцируемую функцию выброса
.
В этом случае
, и нахождение классификатора на каждом шаге будет равносильно нахождению классификатора
, минимизирующего взвешенную ошибку.
Методы голосования как частный случай AnyBoost
Алгоритм | Функция потерь | Размер шага |
---|---|---|
AdaBoost | Линейный поиск | |
ARC-X4 | ||
ConfidenceBoost | Линейный поиск | |
LogitBoost | Метод Ньютона |
Особенности алгоритма
- Алгоритм в значительной доле случаев устойчив к переобучению, даже при использовании большого числа классификаторов.
- Проявляет нестойкость к переобучению в случае экспоненциальных функций потерь, но она может быть устранен путем использования близких по значению к функции
. В качестве выходного значения будут получаться только выпуклые линейные комбинации классификаторов.
- Возможно использование модификаций метода - AnyBoost.L1 (с применением нормализации линейной комбинации) и AnyBoost.L2 (метод градиентного спуска используется в выборе коэффициента при норме линейной комбинации, входящей в функцию потерь).
См. также
Литература
- К.В. Воронцов, Машинное обучение (курс лекций)
- Mason L., Baxter J., Bartlett P., Frean M. Boosting algorithms as gradient descent. — Advances in Neural Information Processing Systems. — MIT Press, 2000. — T. 12. — 512--518 с.
- Mason L., Baxter J., Bartlett P., Frean M. Functional Gradient Techniques for Combining Hypotheses. — Advances in Large Margin Classifiers. — MIT Press, 1999. — T. 12. — 221--246 с.