Алгоритм AdaBoost

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (17:40, 24 октября 2016) (править) (отменить)
 
(1 промежуточная версия не показана)
Строка 43: Строка 43:
=== Софт ===
=== Софт ===
Среда для статистических вычислений и графики R содержит пакет ada.
Среда для статистических вычислений и графики R содержит пакет ada.
 +
Основные функции пакета.
Основные функции пакета.
 +
1. Подгонка модели
1. Подгонка модели
 +
Использование
Использование
-
ada(x,...)
+
 
 +
''ada(x,...)
 +
 
## Метод по умолчанию:
## Метод по умолчанию:
ada(x, y,
ada(x, y,
 +
test.x ,test.y=NULL,
test.x ,test.y=NULL,
 +
loss=c(“exponential”, “logistic”),
loss=c(“exponential”, “logistic”),
 +
type=c(“discrete”,”real”, “gentle”), iter=50, nu=0.1, bag.frac=0.5,
type=c(“discrete”,”real”, “gentle”), iter=50, nu=0.1, bag.frac=0.5,
 +
model.coef=TRUE,
model.coef=TRUE,
 +
bag.shift=FALSE,
bag.shift=FALSE,
 +
max.iter=20,
max.iter=20,
 +
delta=10^(-10),
delta=10^(-10),
 +
verbose=FALSE,
verbose=FALSE,
 +
control = cont,
control = cont,
 +
...,na.action=na.rpart)
...,na.action=na.rpart)
 +
## Метод для класса «formula»
## Метод для класса «formula»
-
ada(formula, data, ..., subset, na.action=na.rpart)
+
ada(formula, data, ..., subset, na.action=na.rpart)''
 +
 
Параметры
Параметры
x матрица наблюдений.
x матрица наблюдений.
 +
y вектор ответов. «y» может иметь только два уникальных значения.
y вектор ответов. «y» может иметь только два уникальных значения.
 +
test.x матрица наблюдений для обучения (дополнительно).
test.x матрица наблюдений для обучения (дополнительно).
 +
test.y вектор ответов обучения (дополнительно).
test.y вектор ответов обучения (дополнительно).
 +
loss loss=«exponential», «ada», «e» или любые вариации, соответствующие увеличению по умолчанию при экспоненциальных потерях. loss=«logistic», «l2», «l» предоставляет увеличение (boosting) при логистических потерях, которые, как считается, ведет к меньшей вероятности переобучения.
loss loss=«exponential», «ada», «e» или любые вариации, соответствующие увеличению по умолчанию при экспоненциальных потерях. loss=«logistic», «l2», «l» предоставляет увеличение (boosting) при логистических потерях, которые, как считается, ведет к меньшей вероятности переобучения.
 +
type тип выполняемого алгоритма увеличения (boosting). “discrete” выполняет дискретное увеличение (по умолчанию). “real” выполняет числовое увеличение. “gentle” выполняет мягкое увеличение. Из теории известно, что все три алгоритма должны рассматриваться, как экспоненциальные алгоритмы оптимизации.
type тип выполняемого алгоритма увеличения (boosting). “discrete” выполняет дискретное увеличение (по умолчанию). “real” выполняет числовое увеличение. “gentle” выполняет мягкое увеличение. Из теории известно, что все три алгоритма должны рассматриваться, как экспоненциальные алгоритмы оптимизации.
iter количество выполняемых итераций усиления. Умолчание = 50. Считается, что увеличение итераций может привести к переобучению. Особенно этот эффект возможен при слабом учителе.
iter количество выполняемых итераций усиления. Умолчание = 50. Считается, что увеличение итераций может привести к переобучению. Особенно этот эффект возможен при слабом учителе.
nu параметр сжатия для усиления, по умолчанию принимается равным 1.
nu параметр сжатия для усиления, по умолчанию принимается равным 1.
 +
bag.frac доля сэмплирования для наблюдений, взятых вне выборки. Это позволяет использовать случайную перестановку, которая улучшает результативность.
bag.frac доля сэмплирования для наблюдений, взятых вне выборки. Это позволяет использовать случайную перестановку, которая улучшает результативность.
 +
model.coef флаг, используемый для взвешивания этапа усиления. Если FALSE, то процедура соответствует усилению эпсилона.
model.coef флаг, используемый для взвешивания этапа усиления. Если FALSE, то процедура соответствует усилению эпсилона.
 +
bag.shift флаг для определения должны ли веса этапа сходиться к единице как ню, или сходиться к нулю. Это делается лишь в случае, если bag.frac небольшой.
bag.shift флаг для определения должны ли веса этапа сходиться к единице как ню, или сходиться к нулю. Это делается лишь в случае, если bag.frac небольшой.
 +
max.iter количество итераций для выполнения ньютоновских шагов для определения коэффициентов.
max.iter количество итераций для выполнения ньютоновских шагов для определения коэффициентов.
 +
delta устойчивость для сходимости при выполнения ньютоновских шагов по определению коэффициентов.
delta устойчивость для сходимости при выполнения ньютоновских шагов по определению коэффициентов.
 +
verbose печать числа итераций, необходимых для сходимости коэффициентов.
verbose печать числа итераций, необходимых для сходимости коэффициентов.
 +
formula символическое описание подгоняемой модели.
formula символическое описание подгоняемой модели.
 +
data дополнительный фрейм данных, содержащий переменные для модели.
data дополнительный фрейм данных, содержащий переменные для модели.
 +
subset дополнительный вектор, указывающий подмножество наблюдений, подлежащих использованию в процессе подгонки.
subset дополнительный вектор, указывающий подмножество наблюдений, подлежащих использованию в процессе подгонки.
 +
na.action функция, которая указывает как обрабатывать значения «NA». Умолчание na.rpart.
na.action функция, которая указывает как обрабатывать значения «NA». Умолчание na.rpart.
 +
... параметры, передаваемые rpart.control. Для корня дерева использование rpart.control(maxdepth=1, cp=-1, minsplit=0 maxdepth) управляет глубиной дерева, а cp управляет сложностью дерева. Предыдущее также должно фиксироваться так, как показано при обсуждении параметра parms во второй ссылке.
... параметры, передаваемые rpart.control. Для корня дерева использование rpart.control(maxdepth=1, cp=-1, minsplit=0 maxdepth) управляет глубиной дерева, а cp управляет сложностью дерева. Предыдущее также должно фиксироваться так, как показано при обсуждении параметра parms во второй ссылке.
 +
Детали
Детали
 +
Эта функция непосредственно реализует алгоритмы, перечисленные в “Additive Logistic Regression: A Statistical View of Boosting”.
Эта функция непосредственно реализует алгоритмы, перечисленные в “Additive Logistic Regression: A Statistical View of Boosting”.
 +
При использовании «ada (x, y)»:
При использовании «ada (x, y)»:
 +
x данные могут иметь вид data.frame или as.matrix.
x данные могут иметь вид data.frame или as.matrix.
 +
y данные могут иметь вид data.frame, as.factor, as.matrix, as.array или as.table.
y данные могут иметь вид data.frame, as.factor, as.matrix, as.array или as.table.
 +
NA отсутствующие значения следует удалить из данных до выполнения.
NA отсутствующие значения следует удалить из данных до выполнения.
 +
При использовании «ada (y ~.)»: данные должны быть в data.frame. Отклик может быть или фактором, или числовым значением. Отсутствующие значения могут всегда присутствовать в данных предиктора при установке na.action в любую опцию кроме na.pass.
При использовании «ada (y ~.)»: данные должны быть в data.frame. Отклик может быть или фактором, или числовым значением. Отсутствующие значения могут всегда присутствовать в данных предиктора при установке na.action в любую опцию кроме na.pass.
 +
После подгонки модели «ada» печатает итоги: вызов функции, метод, используемый для усиления, число итераций, заключительную матрицу рассогласования (ошибок) (наблюдаемая классификация по сравнению с предсказанной классификацией; метки для классов - то же самое как в отклике), ошибка для набора данных обучения и тестирования, и оценки каппы соответствующего числа итераций.
После подгонки модели «ada» печатает итоги: вызов функции, метод, используемый для усиления, число итераций, заключительную матрицу рассогласования (ошибок) (наблюдаемая классификация по сравнению с предсказанной классификацией; метки для классов - то же самое как в отклике), ошибка для набора данных обучения и тестирования, и оценки каппы соответствующего числа итераций.
2. Предсказание
2. Предсказание
 +
 +
Описание
Описание
predict классифицирует новое множество наблюдений, используя ранее созданный классификатор. Эта функция обеспечит или вектор новых классов, оценок вероятности класса, или обоих.
predict классифицирует новое множество наблюдений, используя ранее созданный классификатор. Эта функция обеспечит или вектор новых классов, оценок вероятности класса, или обоих.
 +
Использование
Использование
-
## Метод для класса «ada»
+
 
-
predict(object, newdata = NULL,
+
Метод для класса «ada»
-
type = c(“vector”, “probs’, “both”, “F”), n.iter=NULL,...)
+
 
 +
''predict(object, newdata = NULL,
 +
 
 +
type = c(“vector”, “probs’, “both”, “F”), n.iter=NULL,...)''
 +
 
Параметры
Параметры
object объект, генерируемый функцией ada.
object объект, генерируемый функцией ada.
 +
newdata новый набор данных для предсказания. Этот набор данных должен иметь тип «data.frame». По умолчанию равно NULL. При NULL predict выполняет предсказание для исходного набора обучения.
newdata новый набор данных для предсказания. Этот набор данных должен иметь тип «data.frame». По умолчанию равно NULL. При NULL predict выполняет предсказание для исходного набора обучения.
 +
type выбор для предсказания. type=“vector” возвращает умалчиваемый класс меток. type=“prob” возвращает оценки вероятности класса. type=“both” возвращает как класс меток по умолчанию, так и оценки вероятности класса. type=“F” возвращает среднее по ансамблю, где класс меток равен sign(F). В основном это полезно для случая многих классов.
type выбор для предсказания. type=“vector” возвращает умалчиваемый класс меток. type=“prob” возвращает оценки вероятности класса. type=“both” возвращает как класс меток по умолчанию, так и оценки вероятности класса. type=“F” возвращает среднее по ансамблю, где класс меток равен sign(F). В основном это полезно для случая многих классов.
 +
n.iter число выполненных итераций для предсказания. По умолчанию iter берется из вызова ada (n.iter< iter).
n.iter число выполненных итераций для предсказания. По умолчанию iter берется из вызова ada (n.iter< iter).
 +
... другие параметры, не используемые для этой функции.
... другие параметры, не используемые для этой функции.
-
Детали
+
 
-
Эта функция вызывается после predict.rpart. Более этого, predict.rpart будет вызываться для обработки предсказания для каждого дерева в ансамбле.
+
 
-
Значение
+
-
fit вектор подогнанного ответа. Подгонка будет возвращена, если type=“vector”.
+
-
probs матрица оценок вероятности класса. Первый столбец соответствует первой метке в «уровнях» отклика. Второй столбец соответствует второй метке в «уровнях» отклика. Вероятности возвращаются при type = “probs”.
+
-
both возвращает и вектор подогнанных откликов, и оценки вероятности класса. Первые элементы возвращают подогнанные отклики и будут маркированы как «класс». Вторые элементы возвращают оценки вероятности класса и будут маркированы как «probs»
+
-
F используется в случае многих классов при выполнении пакета один-против-всех.
+
-
Замечание
+
-
Эта функция вызывается summary, pairs, и универсальная plot вызывается с объектом ada. Если ошибка происходит в одной из вышеупомянутых команд, то пытаются использовать эту команду непосредственно, чтобы проследить за возможными ошибками. Кроме того, набор данных newdata должен иметь тип «data.frame» как и при вызове summary, pairs и plot.
+
-
Набор данных newdata должен иметь наблюдения с полностью одинаковыми именами переменных колонок.
+

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

Данная статья является непроверенным учебным заданием.
Студент: Участник: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»
Личные инструменты