Алгоритм AnyBoost
Материал из MachineLearning.
(→Особенности алгоритма) |
м (→См. также) |
||
Строка 55: | Строка 55: | ||
*[[BrownBoost]] | *[[BrownBoost]] | ||
*[[LogitBoost]] | *[[LogitBoost]] | ||
+ | * [[Метод потенциального бустинга]] | ||
==Литература== | ==Литература== |
Текущая версия
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта 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 с.