Алгоритм AdaBoost

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (17:40, 24 октября 2016) (править) (отменить)
 
(7 промежуточных версий не показаны.)
Строка 25: Строка 25:
<tex>\alpha_t = \frac{1}{2} \ln\frac{1 - Q(b,W^l)}{Q(b,W^l)}</tex>;
<tex>\alpha_t = \frac{1}{2} \ln\frac{1 - Q(b,W^l)}{Q(b,W^l)}</tex>;
-
2.3 Пересчет весов объектов: <tex>w_i = w_i \exp{(-\alpha_t y_t b_t(x_i))}</tex>, <tex>i = 1,\dots, l</tex>;
+
2.3 Пересчет весов объектов: <tex>w_i = w_i \exp{(-\alpha_t y_i b_t(x_i))}</tex>, <tex>i = 1,\dots, l</tex>;
2.4 Нормировка весов объектов: <tex>w_0 = \sum_{j=1}^{l}w_j</tex>; <tex>w_i = w_i/w_0</tex>, <tex>i = 1,\dots, l</tex>;
2.4 Нормировка весов объектов: <tex>w_0 = \sum_{j=1}^{l}w_j</tex>; <tex>w_i = w_i/w_0</tex>, <tex>i = 1,\dots, l</tex>;
-
4. Возвращаем: <tex>a(x) = sign \left(\sum_{i=1}^{T} \alpha_i b(x)\right)</tex>
+
4. Возвращаем: <tex>a(x) = sign \left(\sum_{i=1}^{T} \alpha_i b_i(x)\right)</tex>
'''Замечание:''' После построения некоторого количества базовых алгоритмов(скажем, пары десятков) имеет смысл проанализировать распределение весов объектов. Объекты с наибольшими весами, скорее всего, являются шумовыми выбросами, которые стоит исключить из выборки, после чего начать построение композиции заново. Вообще, бустинг можно использовать как универсальный метод фильтрации выбросов перед применением любого другого метода классификации.
'''Замечание:''' После построения некоторого количества базовых алгоритмов(скажем, пары десятков) имеет смысл проанализировать распределение весов объектов. Объекты с наибольшими весами, скорее всего, являются шумовыми выбросами, которые стоит исключить из выборки, после чего начать построение композиции заново. Вообще, бустинг можно использовать как универсальный метод фильтрации выбросов перед применением любого другого метода классификации.
 +
=== Достоинства ===
=== Достоинства ===
* Хорошая обобщающая способность. В реальных задачах (не всегда, но часто) удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться (в некоторых задачах) по мере увеличения числа базовых алгоритмов.
* Хорошая обобщающая способность. В реальных задачах (не всегда, но часто) удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться (в некоторых задачах) по мере увеличения числа базовых алгоритмов.
Строка 39: Строка 40:
* Жадная стратегия последовательного добавления приводит к построению неоптимального набора базовых алгоритмов. Для улучшения композиции можно периодически возвращаться к ранее построенным алгоритмам и обучать их заново. Для улучшения коэффициентов можно оптимизировать их ещё раз по окончании процесса бустинга с помощью какого-нибудь стандартного метода построения линейной разделяющей поверхности. Рекомендуется использовать для этой цели [[Машина опорных векторов | SVM (машины опорных векторов)]].
* Жадная стратегия последовательного добавления приводит к построению неоптимального набора базовых алгоритмов. Для улучшения композиции можно периодически возвращаться к ранее построенным алгоритмам и обучать их заново. Для улучшения коэффициентов можно оптимизировать их ещё раз по окончании процесса бустинга с помощью какого-нибудь стандартного метода построения линейной разделяющей поверхности. Рекомендуется использовать для этой цели [[Машина опорных векторов | SVM (машины опорных векторов)]].
* Бустинг может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.
* Бустинг может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.
 +
 +
=== Софт ===
 +
Среда для статистических вычислений и графики R содержит пакет ada.
 +
 +
Основные функции пакета.
 +
 +
1. Подгонка модели
 +
 +
Использование
 +
 +
''ada(x,...)
 +
 +
## Метод по умолчанию:
 +
ada(x, y,
 +
 +
test.x ,test.y=NULL,
 +
 +
loss=c(“exponential”, “logistic”),
 +
 +
type=c(“discrete”,”real”, “gentle”), iter=50, nu=0.1, bag.frac=0.5,
 +
 +
model.coef=TRUE,
 +
 +
bag.shift=FALSE,
 +
 +
max.iter=20,
 +
 +
delta=10^(-10),
 +
 +
verbose=FALSE,
 +
 +
control = cont,
 +
 +
...,na.action=na.rpart)
 +
 +
 +
## Метод для класса «formula»
 +
ada(formula, data, ..., subset, na.action=na.rpart)''
 +
 +
Параметры
 +
x матрица наблюдений.
 +
 +
y вектор ответов. «y» может иметь только два уникальных значения.
 +
 +
test.x матрица наблюдений для обучения (дополнительно).
 +
 +
test.y вектор ответов обучения (дополнительно).
 +
 +
loss loss=«exponential», «ada», «e» или любые вариации, соответствующие увеличению по умолчанию при экспоненциальных потерях. loss=«logistic», «l2», «l» предоставляет увеличение (boosting) при логистических потерях, которые, как считается, ведет к меньшей вероятности переобучения.
 +
 +
type тип выполняемого алгоритма увеличения (boosting). “discrete” выполняет дискретное увеличение (по умолчанию). “real” выполняет числовое увеличение. “gentle” выполняет мягкое увеличение. Из теории известно, что все три алгоритма должны рассматриваться, как экспоненциальные алгоритмы оптимизации.
 +
iter количество выполняемых итераций усиления. Умолчание = 50. Считается, что увеличение итераций может привести к переобучению. Особенно этот эффект возможен при слабом учителе.
 +
nu параметр сжатия для усиления, по умолчанию принимается равным 1.
 +
 +
bag.frac доля сэмплирования для наблюдений, взятых вне выборки. Это позволяет использовать случайную перестановку, которая улучшает результативность.
 +
 +
model.coef флаг, используемый для взвешивания этапа усиления. Если FALSE, то процедура соответствует усилению эпсилона.
 +
 +
bag.shift флаг для определения должны ли веса этапа сходиться к единице как ню, или сходиться к нулю. Это делается лишь в случае, если bag.frac небольшой.
 +
 +
max.iter количество итераций для выполнения ньютоновских шагов для определения коэффициентов.
 +
 +
delta устойчивость для сходимости при выполнения ньютоновских шагов по определению коэффициентов.
 +
 +
verbose печать числа итераций, необходимых для сходимости коэффициентов.
 +
 +
formula символическое описание подгоняемой модели.
 +
 +
data дополнительный фрейм данных, содержащий переменные для модели.
 +
 +
subset дополнительный вектор, указывающий подмножество наблюдений, подлежащих использованию в процессе подгонки.
 +
 +
na.action функция, которая указывает как обрабатывать значения «NA». Умолчание na.rpart.
 +
 +
... параметры, передаваемые rpart.control. Для корня дерева использование rpart.control(maxdepth=1, cp=-1, minsplit=0 maxdepth) управляет глубиной дерева, а cp управляет сложностью дерева. Предыдущее также должно фиксироваться так, как показано при обсуждении параметра parms во второй ссылке.
 +
 +
Детали
 +
 +
Эта функция непосредственно реализует алгоритмы, перечисленные в “Additive Logistic Regression: A Statistical View of Boosting”.
 +
 +
При использовании «ada (x, y)»:
 +
 +
x данные могут иметь вид data.frame или as.matrix.
 +
 +
y данные могут иметь вид data.frame, as.factor, as.matrix, as.array или as.table.
 +
 +
NA отсутствующие значения следует удалить из данных до выполнения.
 +
 +
При использовании «ada (y ~.)»: данные должны быть в data.frame. Отклик может быть или фактором, или числовым значением. Отсутствующие значения могут всегда присутствовать в данных предиктора при установке na.action в любую опцию кроме na.pass.
 +
 +
После подгонки модели «ada» печатает итоги: вызов функции, метод, используемый для усиления, число итераций, заключительную матрицу рассогласования (ошибок) (наблюдаемая классификация по сравнению с предсказанной классификацией; метки для классов - то же самое как в отклике), ошибка для набора данных обучения и тестирования, и оценки каппы соответствующего числа итераций.
 +
 +
 +
2. Предсказание
 +
 +
 +
Описание
 +
predict классифицирует новое множество наблюдений, используя ранее созданный классификатор. Эта функция обеспечит или вектор новых классов, оценок вероятности класса, или обоих.
 +
 +
Использование
 +
 +
Метод для класса «ada»
 +
 +
''predict(object, newdata = NULL,
 +
 +
type = c(“vector”, “probs’, “both”, “F”), n.iter=NULL,...)''
 +
 +
Параметры
 +
object объект, генерируемый функцией ada.
 +
 +
newdata новый набор данных для предсказания. Этот набор данных должен иметь тип «data.frame». По умолчанию равно NULL. При NULL predict выполняет предсказание для исходного набора обучения.
 +
 +
type выбор для предсказания. type=“vector” возвращает умалчиваемый класс меток. type=“prob” возвращает оценки вероятности класса. type=“both” возвращает как класс меток по умолчанию, так и оценки вероятности класса. type=“F” возвращает среднее по ансамблю, где класс меток равен sign(F). В основном это полезно для случая многих классов.
 +
 +
n.iter число выполненных итераций для предсказания. По умолчанию iter берется из вызова ada (n.iter< iter).
 +
 +
... другие параметры, не используемые для этой функции.
 +
 +
 +
=== Ссылки ===
=== Ссылки ===
Строка 45: Строка 166:
# [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.9525 Additive logistic regression: a statistical view of boosting. Jerome Friedman, Trevor Hastie, Robert Tibshirani] Обсуждаются вероятностные аспекты AdaBoost, описывается GentleBoost.
# [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.9525 Additive logistic regression: a statistical view of boosting. Jerome Friedman, Trevor Hastie, Robert Tibshirani] Обсуждаются вероятностные аспекты AdaBoost, описывается GentleBoost.
#[http://www.site.uottawa.ca/~stan/csi5387/boost-tut-ppr.pdf A Short Introduction to Boosting] Введение в Adaboost, Freund и Schapire, 1999
#[http://www.site.uottawa.ca/~stan/csi5387/boost-tut-ppr.pdf A Short Introduction to Boosting] Введение в Adaboost, Freund и Schapire, 1999
-
[[Категория:Машинное обучение]]
+
 
 +
[[Категория:Алгоритмические композиции]]
 +
[[Категория:Методы голосования]]

Текущая версия

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

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

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


Алгоритм AdaBoost (сокр. от adaptive boosting) — алгоритм машинного обучения, предложенный Йоавом Фройндом (Yoav Freund) и Робертом Шапиром (Robert Schapire). Является мета-алгоритмом, в процессе обучения строит композицию из базовых алгоритмов обучения для улучшения их эффективности. AdaBoost является алгоритмом адаптивного бустинга в том смысле, что каждый следующий классификатор строится по объектам, которые плохо классифицируются предыдущими классификаторами.

AdaBoost вызывает слабый классификатор в цикле. После каждого вызова обновляется распределение весов, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый классификатор «фокусирует своё внимание» на этих объектах.

Содержание

Описание базового алгоритма для задачи построения бинарного классификатора

Рассмотрим задачу классификации на два класса, Y=\{-1,+1\}. Допустим, что базовые алгоритмы b_1, \dots, b_T также возвращают только два ответа -1 и +1. W^l = (w_1,\dots w_l) — вектор весов объектов.

Q(b,W^l) = \sum_{i=1}^{l}w_i[y_i b(x_i) < 0] — стандартный функционал качества алгоритма классификации b.

Задачу оптимизации параметра \alpha_t решаем аналитически, аппроксимируя пороговую функцию потерь [z < 0] с помощью экспоненты E(z) = \exp(-z). 

Алгоритм AdaBoost — построение линейной комбинации классификаторов.

Дано: X^l - обучающая выборка;

b_1, \dots, b_T - базовые алгоритмы классификации;

1. Инициализация весов объектов: \w_i = 1/l, i = 1,\dots, l;
2. Для всех t=1,\dots, T, пока не выполнен критерий останова.
    2.1 Находим классификатор b_{t}: X \to \{-1,+1\} который минимизирует взвешенную ошибку классификации;

        b_t = \arg \min_b Q(b,W^l);
    2.2 Пересчитываем кооэффициент взвешенного голосования для алгоритма классификации b_t:

        \alpha_t = \frac{1}{2} \ln\frac{1 - Q(b,W^l)}{Q(b,W^l)};
    2.3 Пересчет весов объектов: w_i = w_i \exp{(-\alpha_t y_i b_t(x_i))}, i = 1,\dots, l;
    2.4 Нормировка весов объектов: w_0 = \sum_{j=1}^{l}w_j; w_i = w_i/w_0, i = 1,\dots, l;
4. Возвращаем: a(x) = sign \left(\sum_{i=1}^{T} \alpha_i b_i(x)\right)

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

Достоинства

  • Хорошая обобщающая способность. В реальных задачах (не всегда, но часто) удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться (в некоторых задачах) по мере увеличения числа базовых алгоритмов.
  • Простота реализации.
  • Собственные накладные расходы бустинга невелики. Время построения композиции практически полностью определяется временем обучения базовых алгоритмов.
  • Возможность идентифицировать объекты, являющиеся шумовыми выбросами.

Недостатки

  • AdaBoost склонен к переобучению при наличии значительного уровня шума в данных. Экспоненциальная функция потерь слишком сильно увеличивает веса наиболее трудных объектов, на которых ошибаются многие базовые алгоритмы. Однако именно эти объекты чаще всего оказываются шумовыми выбросами. В результате AdaBoost начинает настраиваться на шум, что ведёт к переобучению. Проблема решается путём удаления выбросов или применения менее агрессивных функций потерь.
  • AdaBoost требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
  • Жадная стратегия последовательного добавления приводит к построению неоптимального набора базовых алгоритмов. Для улучшения композиции можно периодически возвращаться к ранее построенным алгоритмам и обучать их заново. Для улучшения коэффициентов можно оптимизировать их ещё раз по окончании процесса бустинга с помощью какого-нибудь стандартного метода построения линейной разделяющей поверхности. Рекомендуется использовать для этой цели SVM (машины опорных векторов).
  • Бустинг может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.

Софт

Среда для статистических вычислений и графики R содержит пакет ada.

Основные функции пакета.

1. Подгонка модели

Использование

ada(x,...)

    1. Метод по умолчанию:

ada(x, y,

test.x ,test.y=NULL,

loss=c(“exponential”, “logistic”),

type=c(“discrete”,”real”, “gentle”), iter=50, nu=0.1, bag.frac=0.5,

model.coef=TRUE,

bag.shift=FALSE,

max.iter=20,

delta=10^(-10),

verbose=FALSE,

control = cont,

...,na.action=na.rpart)


    1. Метод для класса «formula»

ada(formula, data, ..., subset, na.action=na.rpart)

Параметры x матрица наблюдений.

y вектор ответов. «y» может иметь только два уникальных значения.

test.x матрица наблюдений для обучения (дополнительно).

test.y вектор ответов обучения (дополнительно).

loss loss=«exponential», «ada», «e» или любые вариации, соответствующие увеличению по умолчанию при экспоненциальных потерях. loss=«logistic», «l2», «l» предоставляет увеличение (boosting) при логистических потерях, которые, как считается, ведет к меньшей вероятности переобучения.

type тип выполняемого алгоритма увеличения (boosting). “discrete” выполняет дискретное увеличение (по умолчанию). “real” выполняет числовое увеличение. “gentle” выполняет мягкое увеличение. Из теории известно, что все три алгоритма должны рассматриваться, как экспоненциальные алгоритмы оптимизации. iter количество выполняемых итераций усиления. Умолчание = 50. Считается, что увеличение итераций может привести к переобучению. Особенно этот эффект возможен при слабом учителе. nu параметр сжатия для усиления, по умолчанию принимается равным 1.

bag.frac доля сэмплирования для наблюдений, взятых вне выборки. Это позволяет использовать случайную перестановку, которая улучшает результативность.

model.coef флаг, используемый для взвешивания этапа усиления. Если FALSE, то процедура соответствует усилению эпсилона.

bag.shift флаг для определения должны ли веса этапа сходиться к единице как ню, или сходиться к нулю. Это делается лишь в случае, если bag.frac небольшой.

max.iter количество итераций для выполнения ньютоновских шагов для определения коэффициентов.

delta устойчивость для сходимости при выполнения ньютоновских шагов по определению коэффициентов.

verbose печать числа итераций, необходимых для сходимости коэффициентов.

formula символическое описание подгоняемой модели.

data дополнительный фрейм данных, содержащий переменные для модели.

subset дополнительный вектор, указывающий подмножество наблюдений, подлежащих использованию в процессе подгонки.

na.action функция, которая указывает как обрабатывать значения «NA». Умолчание na.rpart.

... параметры, передаваемые rpart.control. Для корня дерева использование rpart.control(maxdepth=1, cp=-1, minsplit=0 maxdepth) управляет глубиной дерева, а cp управляет сложностью дерева. Предыдущее также должно фиксироваться так, как показано при обсуждении параметра parms во второй ссылке.

Детали

Эта функция непосредственно реализует алгоритмы, перечисленные в “Additive Logistic Regression: A Statistical View of Boosting”.

При использовании «ada (x, y)»:

x данные могут иметь вид data.frame или as.matrix.

y данные могут иметь вид data.frame, as.factor, as.matrix, as.array или as.table.

NA отсутствующие значения следует удалить из данных до выполнения.

При использовании «ada (y ~.)»: данные должны быть в data.frame. Отклик может быть или фактором, или числовым значением. Отсутствующие значения могут всегда присутствовать в данных предиктора при установке na.action в любую опцию кроме na.pass.

После подгонки модели «ada» печатает итоги: вызов функции, метод, используемый для усиления, число итераций, заключительную матрицу рассогласования (ошибок) (наблюдаемая классификация по сравнению с предсказанной классификацией; метки для классов - то же самое как в отклике), ошибка для набора данных обучения и тестирования, и оценки каппы соответствующего числа итераций.


2. Предсказание


Описание predict классифицирует новое множество наблюдений, используя ранее созданный классификатор. Эта функция обеспечит или вектор новых классов, оценок вероятности класса, или обоих.

Использование 

Метод для класса «ada»

predict(object, newdata = NULL,

type = c(“vector”, “probs’, “both”, “F”), n.iter=NULL,...)

Параметры object объект, генерируемый функцией ada.

newdata новый набор данных для предсказания. Этот набор данных должен иметь тип «data.frame». По умолчанию равно NULL. При NULL predict выполняет предсказание для исходного набора обучения.

type выбор для предсказания. type=“vector” возвращает умалчиваемый класс меток. type=“prob” возвращает оценки вероятности класса. type=“both” возвращает как класс меток по умолчанию, так и оценки вероятности класса. type=“F” возвращает среднее по ансамблю, где класс меток равен sign(F). В основном это полезно для случая многих классов.

n.iter число выполненных итераций для предсказания. По умолчанию iter берется из вызова ada (n.iter< iter).

... другие параметры, не используемые для этой функции.



Ссылки

  1. К.В. Воронцов, Машинное обучение (курс лекций)
  2. A decision-theoretic generalization of on-line learning and an application to boosting Journal of Computer and System Sciences, no. 55. 1997 Оригинальная работа Yoav Freund и Robert E.Schapire, где впервые был предложен Adaboost.
  3. Additive logistic regression: a statistical view of boosting. Jerome Friedman, Trevor Hastie, Robert Tibshirani Обсуждаются вероятностные аспекты AdaBoost, описывается GentleBoost.
  4. A Short Introduction to Boosting Введение в Adaboost, Freund и Schapire, 1999
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_AdaBoost»
Личные инструменты