Алгоритм AnyBoost

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
м (→См. также)
 
(20 промежуточных версий не показаны.)
Строка 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
 +
}}
 +
 
 +
==Ссылки==
[[Категория:Алгоритмические композиции]]
[[Категория:Алгоритмические композиции]]
[[Категория:Методы голосования]]
[[Категория:Методы голосования]]

Текущая версия

Данная статья является непроверенным учебным заданием.
Студент: Участник:Mordasova
Преподаватель: Участник:Константин Воронцов
Срок: 10 февраля 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Алгоритм 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 (метод градиентного спуска используется в выборе коэффициента при норме линейной комбинации, входящей в функцию потерь).

См. также

Литература

  1. К.В. Воронцов, Машинное обучение (курс лекций)
  2. 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 с.
  3. 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 с.

Ссылки

Источник — «http://recognition.su/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_AnyBoost»