Алгоритм 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>F,G\in\mathrm{lin}(\mathcal{F})</tex> введено скалярное умножение: <tex> \left \langle F,G\right \rangle =\frac{1}{m}\sum^{m}_{i=1}{F(x_i)G(x_i)}</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>Y=\{-1;1\}</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>X^l =\{(x_i,y_i)\}</tex> - обучающая выборка.
-
Нахождение классификатора на каждом шаге будет равносильно нахождению классификатора <tex>f</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

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

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

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


Алгоритм AnyBoost - класс алгоритмов, представляющих бустинг как процесс градиентного спуска. В основе алгоритма лежит последовательное уточнение функции, представляющей собой линейную комбинацию базовых классификаторов, с тем чтобы минимизировать функцию потерь. В класс AnyBoost входят практически все алгоритмы бустинг как частные случаи.

Содержание

Описание алгоритма

Алгоритм AnyBoost

Рассмотрим задачу классификации, \mathcal{F} - множество базовых классификаторов, все их линейные комбинации содержатся в множестве \mathrm{lin}(\mathcal{F}). На каждом шаге алгоритма к текущему классификатору F прибавляется базовый классификатор так, чтобы значение C(F+\eps f) уменьшилось на некоторое значение \eps. То есть в терминах функционального пространства для функции f ищется направление, в котором функция C(F+\eps 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; ## Если -\left \langle \nabla C(F_t),f_{t+1}\right \rangle \le 0 выходим из цикла и возвращаем F_t;
    2. Выбор веса w_{t+1}
    3. Уточнение классификатора 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, минимизирующего взвешенную ошибку.

См. также

Литература

  1. 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 с.

Ссылки

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_AnyBoost»
Личные инструменты