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

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

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

Версия 17:16, 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)}

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

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

Источник — «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»
Личные инструменты