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

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

Идея метода

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

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

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

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

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

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

Пусть 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)}

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

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

<

ol>

  •  M_0(x_i):=0
  •  Для  t = 1,...,T:

    <

    ol>

  • w_i:=exp(-Mt-1(x_i))
  • Решается задача оптимизации: \sum^{n}_{i=1}{w_iy_ib_t(x_i)} \rightarrow max по  a_t\in X , h_t≥0,  s_t = 1,-1.
  • Решается задача одномерной оптимизации: \sum^{n}_{i=1}{w_i exp(-\alpha_t b_t(x_i)y_i)} \rightarrow min по <img src=”http://www.machinelearning.ru/mimetex/?alpha_t” alt=”alpha_t[/latex]>0</li> <li>Значения отступов композиции обновляются: M_t(x_i):=M" /><sub>t-1</sub>([latex]x_i)+\alpha_t b_t(x_i)y_i
  • Строится конечная композиция: B(x)=sign(\sum^{T}_{t=1}{\alpha_tb_t(x)})
  • Источник

    comments powered by HyperComments

    Посмотрите также

    Адаптивный линейный элемент

    Адаптивный линейный элемент(Адаптивный линейный нейрон или ADALINE) - частный случай линейного классификатора или искусственной нейронной сети с одним слоем. Был предложен Видроу и Хоффом в 1960 году, развивая математическую модель нейрона МакКаллока–Питтса. Общая схема работы ADALINE Схема работы ADALINE несколько напоминает работу биологического нейрона: модель работы нейрона На вход подаётся вектор импульсов xn ,состоящий из n числовых [...]