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

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

Перейти к: навигация, поиск

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

Содержание

Идея метода

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

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

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

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

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

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

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


См. также


Данная статья является непроверенным учебным заданием.
Студент: Участник:Djulustan
Преподаватель: Участник:Константин Воронцов
Срок: 30 июня 2013

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

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

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