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

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

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

Содержание [убрать] 1 Идея метода 2 Описание алгоритма 2.1 Постановка проблемы 2.1.1 Задача классификации 2.1.2 Задача потенциального бустинга 2.2 Схема алгоритма 3 См. также

Идея метода

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

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

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

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

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

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

Пусть — множество описаний объектов (все описания - m-мерные числовые векторы), ={1,-1} — множество номеров классов. Существует неизвестная целевая зависимость — отображение , значения которой известны только на объектах конечной обучающей выборки . Требуется построить алгоритм , способный классифицировать произвольный объект .

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

Введем функцию вида:
= exp( - потенциальная функция с центром в нуле и вектором ширины , где - характеризует ширину потенциала по i-ой координате. Введем семейство базовых вещественнозначных классификаторов:
, где = ±1 - тип t-го потенциала, - координаты центра t-го потенциала, - ширина t-го потенциала. Потенциалы типа +1 имеют только положительные значения, потенциалы типа -1 имеют только отрицательные значения.
Задача потенциального бустинга состоит в обучении композиции базовых классификаторов как их линейной комбинации:
=sign() , где - число базовых классификаторов, - коэффициенты этих классификаторов.
Если = 1 , то объект причисляется к классу 1, иначе - к классу -1.
Введем отступ композиции на объекте  :

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

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

1.   

2. Для  

    a. exp(t-1) 

    b. Решается задача оптимизации:  по ≥0, . 

    c. Рещается задача одномерной оптимизации:  по >0  

    d. Значения отступов композиции обновляются:   t-1()  

3. Строится конечная композиция:  =sign()  

См. также

• Метод потенциальных функций
• Метрический классификатор
• Бустинг
• Алгоритм AdaBoost

Данная статья является непроверенным учебным заданием. Студент: Участник:Djulustan Преподаватель: Участник:Константин Воронцов Срок: 30 июня 2013 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.