Метод потенциального бустинга

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Описание алгоритма)
(→Описание алгоритма)
Строка 35: Строка 35:
Отрицательное значение отступа показывает ошибку предсказания композиции на объекте : чем больше по абсолютному значению – тем сильнее композиция ошибается. Положительное значение отступа показывает, что композиция правильно распознает объект: чем больше значение - тем увереннее композиция распознает его. <br />
Отрицательное значение отступа показывает ошибку предсказания композиции на объекте : чем больше по абсолютному значению – тем сильнее композиция ошибается. Положительное значение отступа показывает, что композиция правильно распознает объект: чем больше значение - тем увереннее композиция распознает его. <br />
 +
===Схема алгоритма===
===Схема алгоритма===
 +
1. <tex>M_0(x_i):=0</tex> <br />
 +
2. Для <tex> t = 1,...,T: </tex> <br />
 +
a. <tex>w_i:=</tex>exp(<tex>-M</tex><sub>t-1</sub><tex>(x_i)</tex>) <br />
 +
b. Решается задача оптимизации: <tex>\sum^{n}_{i=1}{w_iy_ib_t(x_i)} \rightarrow max </tex> по <tex> a_t\in X , h_t</tex>≥0, <tex> s_t = 1,-1</tex>. <br />
 +
c. Рещается задача одномерной оптимизации: <tex>\sum^{n}_{i=1}{w_i exp(-\alpha_t b_t(x_i)y_i)} \rightarrow min </tex> по <tex>alpha_t</tex>>0 <br />
 +
d. Значения отступов композиции обновляются: <tex>M_t(x_i):=M</tex><sub>t-1</sub>(<tex>x_i</tex>)<tex>+\alpha_t b_t(x_i)y_i</tex> <br />
 +
3. Строится конечная композиция: <tex>B(x)</tex>=sign(<tex>\sum^{T}_{t=1}{\alpha_tb_t(x)}</tex>) <br />

Версия 17:59, 19 июня 2013

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

Содержание

Идея метода

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

Идея метода потенциальных функций состоит в том, чтобы в пространстве объектов каждый объект создавал потенциальное поле со своим зарядом, соответствующим его классу (по аналогии с электростатикой). В качестве функции потенциалов можно брать любую функцию, достигающую в центре своего максимума и убывающую при отдалении от центра. Классификатором становится совокупность всех потенциалов - объект причисляется к тому классу, представители которого дают наибольший суммарный потенциал в этом объекте.

Главной идеей метода потенциального бустинга является построение классификатора, которое является композицией базовых классификаторов - потенциальных функций. Построение композиции методом бустинга позволяет устранить типичные недостатки метода потенциальных функций: медленная сходимость алгоритма, отсутствие настройки или очень грубая настройка параметров потенциалов, зависимость результата от порядка выбора объектов обучающей выборки.

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

Постановка проблемы

Задача классификации

Пусть X — множество описаний объектов (все описания - m-мерные числовые векторы), Y={1,-1} — множество номеров классов. Существует неизвестная целевая зависимость — отображение y^{*}:\; X\to Y, значения которой известны только на объектах конечной обучающей выборки X^l = \{(x_1,y_1),\dots,(x_n,y_n)\}. Требуется построить алгоритм B:\; X\to Y, способный классифицировать произвольный объект x \in X.

Задача потенциального бустинга

Введем функцию вида:
f(x,h) = exp(-\sum^{m}_{i=1}{(\frac{x_j}{h_j})^2}) - потенциальная функция с центром в нуле и вектором ширины h=(h_1,...,h_m), где h_i - характеризует ширину потенциала по i-ой координате. Введем семейство базовых вещественнозначных классификаторов:
b_t(x) = s_tf(x-a_t,h_t) , где s_t = ±1 - тип t-го потенциала, a_t=(a_1,...,a_m) - координаты центра t-го потенциала, h_t - ширина t-го потенциала. Потенциалы типа +1 имеют только положительные значения, потенциалы типа -1 имеют только отрицательные значения.
Задача потенциального бустинга состоит в обучении композиции базовых классификаторов как их линейной комбинации:
B(x)=sign(\sum^{T}_{t=1}{\alpha_tb_t(x)}) , где T - число базовых классификаторов, \alpha_1,...,\alpha_T - коэффициенты этих классификаторов.
Если B(x) = 1 , то объект причисляется к классу 1, иначе - к классу -1.
Введем отступ композиции на объекте x_i :
M_T(x_i) = y_i\sum^{T}_{t=1}{\alpha_tb_t(x_i)}

Отрицательное значение отступа показывает ошибку предсказания композиции на объекте : чем больше по абсолютному значению – тем сильнее композиция ошибается. Положительное значение отступа показывает, что композиция правильно распознает объект: чем больше значение - тем увереннее композиция распознает его.


Схема алгоритма

1. M_0(x_i):=0  

2. Для  t = 1,...,T:  

    a. w_i:=exp(-Mt-1(x_i)) 

    b. Решается задача оптимизации: \sum^{n}_{i=1}{w_iy_ib_t(x_i)} \rightarrow max  по  a_t\in X , h_t≥0,  s_t = 1,-1. 

    c. Рещается задача одномерной оптимизации: \sum^{n}_{i=1}{w_i exp(-\alpha_t b_t(x_i)y_i)} \rightarrow min  по alpha_t>0  

    d. Значения отступов композиции обновляются:   M_t(x_i):=Mt-1(x_i)+\alpha_t b_t(x_i)y_i  

3. Строится конечная композиция:  B(x)=sign(\sum^{T}_{t=1}{\alpha_tb_t(x)})
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D0%BE%D1%82%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B1%D1%83%D1%81%D1%82%D0%B8%D0%BD%D0%B3%D0%B0»
Личные инструменты