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

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

Версия от 18:09, 19 июня 2013; Djulustan (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

Содержание

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

Идея метода

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

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

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

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

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

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

Пусть $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.   

2. Для  

    a. exp(_t-1) 

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

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

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

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