Метод потенциального бустинга
Материал из MachineLearning.
(→Описание алгоритма) |
|||
| Строка 45: | Строка 45: | ||
d. Значения отступов композиции обновляются: <tex>M_t(x_i):=M</tex><sub>t-1</sub>(<tex>x_i</tex>)<tex>+\alpha_t b_t(x_i)y_i</tex> <br /> | d. Значения отступов композиции обновляются: <tex>M_t(x_i):=M</tex><sub>t-1</sub>(<tex>x_i</tex>)<tex>+\alpha_t b_t(x_i)y_i</tex> <br /> | ||
3. Строится конечная композиция: <tex>B(x)</tex>=sign(<tex>\sum^{T}_{t=1}{\alpha_tb_t(x)}</tex>) <br /> | 3. Строится конечная композиция: <tex>B(x)</tex>=sign(<tex>\sum^{T}_{t=1}{\alpha_tb_t(x)}</tex>) <br /> | ||
| + | |||
| + | |||
| + | |||
| + | [[Категория:Алгоритмические композиции]] | ||
| + | [[Категория:Метрические алгоритмы классификации]] | ||
Версия 18:09, 19 июня 2013
Метод потенциального бустинга - алгоритм классификации, использующий процедуру бустинга для обучения классификатора - метода потенциальных функций.
Содержание |
Идея метода
Бустинг - одна метод построения композиции классификаторов, которая последовательно обучает базовые классификаторы, каждый раз стараясь исправить ошибки, допускаемые всеми предыдущими классификаторами.
Идея метода потенциальных функций состоит в том, чтобы в пространстве объектов каждый объект создавал потенциальное поле со своим зарядом, соответствующим его классу (по аналогии с электростатикой). В качестве функции потенциалов можно брать любую функцию, достигающую в центре своего максимума и убывающую при отдалении от центра. Классификатором становится совокупность всех потенциалов - объект причисляется к тому классу, представители которого дают наибольший суммарный потенциал в этом объекте.
Главной идеей метода потенциального бустинга является построение классификатора, которое является композицией базовых классификаторов - потенциальных функций. Построение композиции методом бустинга позволяет устранить типичные недостатки метода потенциальных функций: медленная сходимость алгоритма, отсутствие настройки или очень грубая настройка параметров потенциалов, зависимость результата от порядка выбора объектов обучающей выборки.
Описание алгоритма
Постановка проблемы
Задача классификации
Пусть — множество описаний объектов (все описания - m-мерные числовые векторы),
={1,-1} — множество номеров классов.
Существует неизвестная целевая зависимость — отображение
,
значения которой известны только на объектах конечной обучающей выборки
.
Требуется построить алгоритм
,
способный классифицировать произвольный объект
.
Задача потенциального бустинга
Введем функцию вида:
= exp(
- потенциальная функция с центром в нуле и вектором ширины
, где
- характеризует ширину потенциала по i-ой координате.
Введем семейство базовых вещественнозначных классификаторов:
, где
= ±1 - тип t-го потенциала,
- координаты центра t-го потенциала,
- ширина t-го потенциала. Потенциалы типа +1 имеют только положительные значения, потенциалы типа -1 имеют только отрицательные значения.
Задача потенциального бустинга состоит в обучении композиции базовых классификаторов как их линейной комбинации:
=sign(
) , где
- число базовых классификаторов,
- коэффициенты этих классификаторов.
Если = 1 , то объект причисляется к классу 1, иначе - к классу -1.
Введем отступ композиции на объекте :
Отрицательное значение отступа показывает ошибку предсказания композиции на объекте : чем больше по абсолютному значению – тем сильнее композиция ошибается. Положительное значение отступа показывает, что композиция правильно распознает объект: чем больше значение - тем увереннее композиция распознает его.
Схема алгоритма
1.:=0)
2. Для
a.exp(
t-1
)
b. Решается задача оптимизации:по
≥0,
.
c. Рещается задача одномерной оптимизации:по
>0
d. Значения отступов композиции обновляются:t-1(
)
y_i)
3. Строится конечная композиция:=sign(
)
