Алгоритм AnyBoost
Материал из MachineLearning.
(Новая: {{Задание|Mordasova|Константин Воронцов|10 февраля 2010}) |
м (→См. также) |
||
(23 промежуточные версии не показаны) | |||
Строка 1: | Строка 1: | ||
- | {{Задание|Mordasova|Константин Воронцов|10 февраля 2010} | + | {{Задание|Mordasova|Константин Воронцов|10 февраля 2010}} |
+ | '''Алгоритм AnyBoost''' - класс алгоритмов, представляющих [[бустинг]] как процесс градиентного спуска. В основе алгоритма лежит последовательное уточнение функции, представляющей собой линейную комбинацию базовых классификаторов, с тем чтобы минимизировать функцию потерь. В класс AnyBoost входят практически все алгоритмы [[бустинг|бустинга]] как частные случаи. | ||
+ | |||
+ | ==Описание алгоритма== | ||
+ | '''Алгоритм AnyBoost''' | ||
+ | |||
+ | Рассмотрим задачу [[классификация|классификации]]. Пусть <tex>\mathcal{F}</tex> - множество базовых классификаторов, а <tex>\mathrm{lin}(\mathcal{F})</tex> - множество всех линейных комбинаций из <tex>\mathcal{F}</tex>. | ||
+ | На каждом шаге алгоритма к текущему классификатору <tex>F\in \mathrm{lin}(\mathcal{F})</tex> прибавляется базовый классификатор так, чтобы значение <tex>C(F+\varepsilon f)</tex> уменьшилось на некоторое значение <tex>\varepsilon</tex>. То есть в терминах функционального пространства для функции <tex>f</tex> ищется направление, в котором функция <tex>C(F+\varepsilon f)</tex> быстрее уменьшается. Наибольшее уменьшение функции потерь наблюдается в случае, когда <tex>f</tex> максимизирует величину <tex>-\left \langle \nabla C(F),f \right \rangle </tex>. | ||
+ | |||
+ | # Инициализация <tex>F_0=0</tex>; | ||
+ | # Для всех <tex>t=0,..,T</tex> пока не выполнено условие выхода из цикла; | ||
+ | ## Получение нового классификатора <tex>f_{t+1}</tex>, увеличивающего значение <tex>-\left \langle \nabla C(F_t), f_{t+1}\right \rangle</tex>; | ||
+ | ## Если <tex>-\left \langle \nabla C(F_t),f_{t+1}\right \rangle \le 0</tex> выходим из цикла и возвращаем <tex>F_t</tex>; | ||
+ | ## Выбор веса <tex>w_{t+1}</tex> | ||
+ | ## Уточнение классификатора <tex>F_{t+1}=F_{t}+w_{t+1}f_{t+1}</tex> | ||
+ | # Возвращаем <tex>F_{T+1}</tex> | ||
+ | |||
+ | |||
+ | В случае бинарного классификатора <tex>Y=\{-1;1\}</tex>. | ||
+ | Пусть <tex>X^l =\{(x_i,y_i)\}</tex> - обучающая выборка. | ||
+ | Функция потерь <tex> C=\frac{1}{m}\sum^{m}_{i=1}{c(y_iF(x_i))}</tex> определяется через дифференцируемую функцию выброса <tex>c: \mathbb{R} \to \mathbb{R}</tex>. | ||
+ | В этом случае <tex>-\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))} </tex>, и нахождение классификатора на каждом шаге будет равносильно нахождению классификатора <tex>f</tex>, минимизирующего взвешенную ошибку. | ||
+ | |||
+ | ==Методы голосования как частный случай AnyBoost== | ||
+ | |||
+ | {| class="standard" | ||
+ | !Алгоритм | ||
+ | !Функция потерь | ||
+ | !Размер шага | ||
+ | |- | ||
+ | |AdaBoost | ||
+ | |<tex>e^{-yF(x)}</tex> | ||
+ | |Линейный поиск | ||
+ | |- | ||
+ | |ARC-X4 | ||
+ | |<tex>{(1-yF(x))}^5</tex> | ||
+ | |<tex>1/t</tex> | ||
+ | |- | ||
+ | |ConfidenceBoost | ||
+ | |<tex>e^{-yF(x)}</tex> | ||
+ | |Линейный поиск | ||
+ | |- | ||
+ | |LogitBoost | ||
+ | |<tex>{\ln(1+e^{-yF(x)})</tex> | ||
+ | |Метод Ньютона | ||
+ | |} | ||
+ | |||
+ | ==Особенности алгоритма== | ||
+ | *Алгоритм в значительной доле случаев устойчив к переобучению, даже при использовании большого числа классификаторов. | ||
+ | *Проявляет нестойкость к переобучению в случае экспоненциальных функций потерь, но она может быть устранен путем использования близких по значению к функции <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> (метод градиентного спуска используется в выборе коэффициента при норме линейной комбинации, входящей в функцию потерь). | ||
+ | |||
+ | ==См. также== | ||
+ | *[[Алгоритм AdaBoost]] | ||
+ | *[[BrownBoost]] | ||
+ | *[[LogitBoost]] | ||
+ | * [[Метод потенциального бустинга]] | ||
+ | |||
+ | ==Литература== | ||
+ | #''К.В. Воронцов'', [[Машинное обучение (курс лекций, К.В.Воронцов)|Машинное обучение (курс лекций)]] | ||
+ | #{{книга | ||
+ | |автор = Mason L., Baxter J., Bartlett P., Frean M. | ||
+ | |заглавие = Boosting algorithms as gradient descent | ||
+ | |ссылка = http://www.cs.cmu.edu/Groups/NIPS/NIPS99/99papers-pub-on-web/Named/MasonBaxterBartlettFrean.ps | ||
+ | |издание = Advances in Neural Information Processing Systems | ||
+ | |издательство = MIT Press | ||
+ | |год = 2000 | ||
+ | |том = 12 | ||
+ | |страниц = 512--518 | ||
+ | }} | ||
+ | #{{книга | ||
+ | |автор = Mason L., Baxter J., Bartlett P., Frean M. | ||
+ | |заглавие = Functional Gradient Techniques for Combining Hypotheses | ||
+ | |ссылка = http://homepages.ecs.vuw.ac.nz/~marcus/manuscripts/Mason_etal99B.ps.gz | ||
+ | |издание = Advances in Large Margin Classifiers | ||
+ | |издательство = MIT Press | ||
+ | |год = 1999 | ||
+ | |том = 12 | ||
+ | |страниц = 221--246 | ||
+ | }} | ||
+ | |||
+ | ==Ссылки== | ||
+ | [[Категория:Алгоритмические композиции]] | ||
+ | [[Категория:Методы голосования]] |
Текущая версия
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта 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 с.