Алгоритм AnyBoost
Материал из MachineLearning.
(→Описание алгоритма) |
(→Описание алгоритма) |
||
Строка 8: | Строка 8: | ||
На каждом шаге алгоритма к текущему классификатору <tex>F</tex> прибавляется базовый классификатор так, чтобы значение <tex>C(F+\eps f)</tex> уменьшилось на некоторое значение <tex>\eps</tex>. То есть в терминах функционального пространства для функции <tex>f</tex> ищется направление, в котором функция <tex>C(F+\eps f)</tex> быстрее уменьшается. Наибольшее уменьшение функции потерь наблюдается в случае, когда <tex>f</tex> максимизирует <tex>-\left \langle \nabla C(F),f \right \rangle </tex>. | На каждом шаге алгоритма к текущему классификатору <tex>F</tex> прибавляется базовый классификатор так, чтобы значение <tex>C(F+\eps f)</tex> уменьшилось на некоторое значение <tex>\eps</tex>. То есть в терминах функционального пространства для функции <tex>f</tex> ищется направление, в котором функция <tex>C(F+\eps f)</tex> быстрее уменьшается. Наибольшее уменьшение функции потерь наблюдается в случае, когда <tex>f</tex> максимизирует <tex>-\left \langle \nabla C(F),f \right \rangle </tex>. | ||
- | #Инициализация <tex>F_0=0</tex>; | + | # Инициализация <tex>F_0=0</tex>; |
- | #Для всех <tex>t=0,..,T</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>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>-\left \langle \nabla C(F_t),f_{t+1}\right \rangle \le 0</tex> выходим из цикла и возвращаем <tex>F_t</tex>; | + | ## Выбор веса <tex>w_{t+1}</tex> |
- | ##Выбор веса <tex>w_{t+1}</tex> | + | ## Уточнение классификатора <tex>F_{t+1}=F_{t}+w_{t+1}f_{t+1}</tex> |
- | ##Уточнение классификатора <tex>F_{t+1}=F_{t}+w_{t+1}f_{t+1}</tex> | + | # Возвращаем <tex>F_{T+1}</tex> |
- | #Возвращаем <tex>F_{T+1}</tex> | + | |
- | В случае бинарного классификатора <tex>Y=\{-1;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>, минимизирующего взвешенную ошибку. | ||
==См. также== | ==См. также== |
Версия 17:32, 7 февраля 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Алгоритм AnyBoost - класс алгоритмов, представляющих бустинг как процесс градиентного спуска. В основе алгоритма лежит последовательное уточнение функции, представляющей собой линейную комбинацию базовых классификаторов, с тем чтобы минимизировать функцию потерь. В класс AnyBoost входят практически все алгоритмы бустинг как частные случаи.
Содержание |
Описание алгоритма
Алгоритм AnyBoost
Рассмотрим задачу классификации, - множество базовых классификаторов, все их линейные комбинации содержатся в множестве
.
На каждом шаге алгоритма к текущему классификатору
прибавляется базовый классификатор так, чтобы значение
уменьшилось на некоторое значение
. То есть в терминах функционального пространства для функции
ищется направление, в котором функция
быстрее уменьшается. Наибольшее уменьшение функции потерь наблюдается в случае, когда
максимизирует
.
- Инициализация
;
- Для всех
пока не выполнено условие выхода из цикла;
- Получение нового классификатора
, увеличивающего значение
; ## Если
выходим из цикла и возвращаем
;
- Выбор веса
- Уточнение классификатора
- Получение нового классификатора
- Возвращаем
В случае бинарного классификатора .
- обучающая выборка.
Функция потерь
определяется через дифференцируемую функцию выброса
.
В этом случае
, и нахождение классификатора на каждом шаге будет равносильно нахождению классификатора
, минимизирующего взвешенную ошибку.
См. также
Литература
- 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 с.