АдаБуст

AdaBoost , сокращение от Adaptive Boosting , — это статистической классификации мета-алгоритм , сформулированный Йоавом Фройндом и Робертом Шапиром в 1995 году, получившими за свою работу премию Гёделя в 2003 году . Его можно использовать в сочетании со многими другими типами алгоритмов обучения для повышения производительности. Выходные данные других алгоритмов обучения («слабые ученики») объединяются во взвешенную сумму, которая представляет собой конечный результат усиленного классификатора. Обычно AdaBoost представлен для бинарной классификации , хотя его можно обобщить на несколько классов или ограниченные интервалы в реальной строке.

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

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

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

Обучение

AdaBoost относится к конкретному методу обучения усиленного классификатора. Усиленный классификатор — это классификатор вида $$F_{T}(x)=\sum _{t=1}^{T}f_{t}(x)$$где каждый $f_{t}$ слабый ученик, который берет предмет $x$ в качестве входных данных и возвращает значение, указывающее класс объекта. Например, в задаче с двумя классами знак результатов слабого учащегося определяет прогнозируемый класс объекта, а абсолютное значение дает уверенность в этой классификации. Аналогичным образом, $t$-й классификатор является положительным, если образец относится к положительному классу, и отрицательным в противном случае.

Каждый слабый ученик выдвигает выходную гипотезу $h$ который фиксирует прогноз $h(x_{i})$ для каждого образца в обучающем наборе. На каждой итерации $t$, выбирается слабый ученик и ему присваивается коэффициент $\alpha _{t}$ такая, что общая ошибка обучения $E_{t}$ полученного $t$Усиленный классификатор -этапа сведен к минимуму.

$$E_{t}=\sum _{i}E[F_{t-1}(x_{i})+\alpha _{t}h(x_{i})]$$

Здесь $F_{t-1}(x)$ — это усиленный классификатор, построенный на предыдущем этапе обучения и $f_{t}(x)=\alpha _{t}h(x)$ — это слабый ученик, которого рассматривают для добавления в окончательный классификатор.

Взвешивание

На каждой итерации тренировочного процесса вес $w_{i,t}$ присваивается каждой выборке в обучающем наборе, равной текущей ошибке $E(F_{t-1}(x_{i}))$ на этом образце. Эти веса можно использовать при обучении слабых учеников. Например, можно вырастить деревья решений, способствующие разделению наборов выборок с большими весами.

Вывод

Этот вывод следует из Рохаса (2009):

Предположим, у нас есть набор данных $\{(x_{1},y_{1}),\ldots ,(x_{N},y_{N})\}$ где каждый предмет $x_{i}$ имеет связанный класс $y_{i}\in \{-1,1\}$и набор слабых классификаторов $\{k_{1},\ldots ,k_{L}\}$ каждый из которых выводит классификацию $k_{j}(x_{i})\in \{-1,1\}$ для каждого предмета. После $(m-1)$-th итерации наш усиленный классификатор представляет собой линейную комбинацию слабых классификаторов вида: $$C_{(m-1)}(x_{i})=\alpha _{1}k_{1}(x_{i})+\cdots +\alpha _{m-1}k_{m-1}(x_{i}),$$где класс будет признаком $C_{(m-1)}(x_{i})$. На $m$-th итерации мы хотим расширить это до более мощного классификатора, добавив еще один слабый классификатор. $k_{m}$, с другим весом $\alpha _{m}$: $$C_{m}(x_{i})=C_{(m-1)}(x_{i})+\alpha _{m}k_{m}(x_{i})$$

Итак, осталось определить, какой слабый классификатор является лучшим выбором для $k_{m}$и какой у него вес $\alpha _{m}$ должно быть. Определим суммарную ошибку $E$ из $C_{m}$ как сумма экспоненциальных потерь в каждой точке данных, определяемая следующим образом: $$E=\sum _{i=1}^{N}e^{-y_{i}C_{m}(x_{i})}=\sum _{i=1}^{N}e^{-y_{i}C_{(m-1)}(x_{i})}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}$$

Сдача в аренду $w_{i}^{(1)}=1$ и $w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}$ для $m>1$, у нас есть: $$E=\sum _{i=1}^{N}w_{i}^{(m)}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}$$

Мы можем разделить это суммирование между теми точками данных, которые правильно классифицированы по $k_{m}$ (так $y_{i}k_{m}(x_{i})=1$) и те, которые неправильно классифицированы (поэтому $y_{i}k_{m}(x_{i})=-1$): $${\begin{aligned}E&=\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}}\\&=\sum _{i=1}^{N}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}\left(e^{\alpha _{m}}-e^{-\alpha _{m}}\right)\end{aligned}}$$

Поскольку единственная часть правой части этого уравнения, зависящая от $k_{m}$ является ${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$, мы видим, что $k_{m}$ что сводит к минимуму $E$ это тот, что в наборе $\{k_{1},\ldots ,k_{L}\}$ что сводит к минимуму ${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$ [предполагая, что $\alpha _{m}>0$], т.е. слабый классификатор с наименьшей взвешенной ошибкой (с весами $w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}$).

Чтобы определить желаемый вес $\alpha _{m}$ что сводит к минимуму $E$ с $k_{m}$ что мы только что определили, дифференцируем: $${\frac {dE}{d\alpha _{m}}}={\frac {d(\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}})}{d\alpha _{m}}}$$

К счастью, минимум достигается при установке этого значения на ноль, а затем при определении $\alpha _{m}$ дает: $$\alpha _{m}={\frac {1}{2}}\ln \left({\frac {\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}}\right)$$

Доказательство

$${\frac {dE}{d\alpha _{m}}}=-\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}}=0$$потому что $e^{-\alpha _{m}}$ не зависит от $i$$$e^{-\alpha _{m}}\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}=e^{\alpha _{m}}\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}$$$$-\alpha _{m}+\ln \left(\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}\right)=\alpha _{m}+\ln \left(\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}\right)$$$$-2\alpha _{m}=\ln \left({\dfrac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}}\right)$$$$\alpha _{m}=-{\dfrac {1}{2}}\ln \left({\dfrac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}}\right)$$$$\alpha _{m}={\dfrac {1}{2}}\ln \left({\dfrac {\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}}\right)$$

Мы рассчитываем взвешенную частоту ошибок слабого классификатора как $\epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}$, поэтому следует, что: $$\alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{m}}{\epsilon _{m}}}\right)$$что представляет собой отрицательную логит-функцию, умноженную на 0,5. Из-за выпуклости $E$ как функция $\alpha _{m}$, это новое выражение для $\alpha _{m}$ дает глобальный минимум функции потерь.

Примечание. Этот вывод применяется только тогда, когда $k_{m}(x_{i})\in \{-1,1\}$, хотя в других случаях это может быть хорошей отправной точкой, например, когда слабый обучающийся предвзят ( $k_{m}(x)\in \{a,b\},a\neq -b$), имеет несколько листьев ( $k_{m}(x)\in \{a,b,\dots ,n\}$) или какая-то другая функция $k_{m}(x)\in \mathbb {R}$.

Таким образом мы получили алгоритм AdaBoost: на каждой итерации выбираем классификатор $k_{m}$, что минимизирует общую взвешенную ошибку ${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$, используйте это для расчета частоты ошибок $\epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}$, используйте это для расчета веса $\alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{m}}{\epsilon _{m}}}\right)$и, наконец, используйте это для улучшения усиленного классификатора $C_{m-1}$ к $C_{m}=C_{(m-1)}+\alpha _{m}k_{m}$.

Статистическое понимание бустинга

Бустинг — это форма линейной регрессии , в которой особенности каждой выборки $x_{i}$ это результаты какого-то слабого ученика $h$ применяется к $x_{i}$.

Хотя регрессия пытается соответствовать $F(x)$ к $y(x)$ как можно точнее, без потери обобщения, обычно с использованием наименьших квадратов ошибки $E(f)=(y(x)-f(x))^{2}$, тогда как функция ошибок AdaBoost $E(f)=e^{-y(x)f(x)}$ учитывает тот факт, что используется только знак конечного результата, таким образом $|F(x)|$ может быть намного больше 1 без увеличения ошибки. Однако экспоненциальный рост ошибки для выборки $x_{i}$ как $-y(x_{i})f(x_{i})$ увеличивается, что приводит к тому, что выбросам присваиваются чрезмерные веса.

Одной из особенностей выбора экспоненциальной функции ошибок является то, что ошибка итоговой аддитивной модели является произведением ошибок каждого этапа, т.е. $e^{\sum _{i}-y_{i}f(x_{i})}=\prod _{i}e^{-y_{i}f(x_{i})}$. Таким образом, можно видеть, что обновление веса в алгоритме AdaBoost эквивалентно пересчету ошибки на $F_{t}(x)$ после каждого этапа.

При выборе функции потерь допускается большая гибкость. Пока функция потерь монотонна и непрерывно дифференцируема , классификатор всегда стремится к более чистым решениям. Чжан (2004) предоставляет функцию потерь, основанную на методе наименьших квадратов, модифицированную функцию потерь Хубера : $$\phi (y,f(x))={\begin{cases}-4yf(x)&{\text{if }}yf(x)<-1,\\(yf(x)-1)^{2}&{\text{if }}-1\leq yf(x)\leq 1.\\0&{\text{if }}yf(x)>1\end{cases}}$$

Эта функция работает лучше, чем LogitBoost, для $f(x)$ близкое к 1 или -1, не наказывает «чрезмерно самоуверенные» прогнозы ( $yf(x)>1$), в отличие от немодифицированного метода наименьших квадратов, и штрафует только выборки, неправильно классифицированные с достоверностью более 1, линейно, а не квадратично или экспоненциально, и, таким образом, менее восприимчив к эффектам выбросов.

Повышение как градиентный спуск

Основная статья: Повышение градиента

Повышение можно рассматривать как минимизацию выпуклой функции потерь над выпуклым набором функций. В частности, потери, минимизируемые AdaBoost, представляют собой экспоненциальные потери. $$\sum _{i}\phi (i,y,f)=\sum _{i}e^{-y_{i}f(x_{i})},$$тогда как LogitBoost выполняет логистическую регрессию, минимизируя $$\sum _{i}\phi (i,y,f)=\sum _{i}\ln \left(1+e^{-y_{i}f(x_{i})}\right).$$

В аналогии с градиентным спуском выходные данные классификатора для каждой обучающей точки считаются точкой. $\left(F_{t}(x_{1}),\dots ,F_{t}(x_{n})\right)$ в n-мерном пространстве, где каждая ось соответствует обучающей выборке, каждый слабый обучающийся $h(x)$ соответствует вектору фиксированной ориентации и длины, и цель состоит в том, чтобы достичь целевой точки $(y_{1},\dots ,y_{n})$ (или любой регион, где значение функции потерь $E_{T}(x_{1},\dots ,x_{n})$ меньше значения в этой точке) за наименьшее количество шагов. Таким образом, алгоритмы AdaBoost выполняют либо Коши (найти $h(x)$ с самым крутым уклоном выберите $\alpha$ чтобы минимизировать ошибку теста) или Ньютона (выберите какую-нибудь целевую точку, найдите $\alpha h(x)$ это приносит $F_{t}$ ближайший к этой точке) оптимизация ошибки обучения.

Пример алгоритма (Дискретный AdaBoost)

С:

• Образцы $x_{1}\dots x_{n}$
• Желаемые результаты $y_{1}\dots y_{n},y\in \{-1,1\}$
• Начальный вес $w_{1,1}\dots w_{n,1}$ установлен на ${\frac {1}{n}}$
• Функция ошибки $E(f(x),y_{i})=e^{-y_{i}f(x_{i})}$
• Слабые ученики $h\colon x\rightarrow \{-1,1\}$

Для $t$ в $1\dots T$:

• Выбирать $h_{t}(x)$:
  • Найдите слабого ученика $h_{t}(x)$ что сводит к минимуму $\epsilon _{t}$, ошибка взвешенной суммы для неправильно классифицированных точек $\epsilon _{t}=\sum _{\stackrel {i=1}{h_{t}(x_{i})\neq y_{i}}}^{n}w_{i,t}$
  • Выбирать $\alpha _{t}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{t}}{\epsilon _{t}}}\right)$
• Добавить в ансамбль:
  • $F_{t}(x)=F_{t-1}(x)+\alpha _{t}h_{t}(x)$
• Обновление весов:
  • $w_{i,t+1}=w_{i,t}e^{-y_{i}\alpha _{t}h_{t}(x_{i})}$ для $i$ в $1\dots n$
  • Перенормировать $w_{i,t+1}$ такой, что $\sum _{i}w_{i,t+1}=1$
  • (Примечание: можно показать, что ${\frac {\sum _{h_{t}(x_{i})=y_{i}}w_{i,t+1}}{\sum _{h_{t}(x_{i})\neq y_{i}}w_{i,t+1}}}={\frac {\sum _{h_{t}(x_{i})=y_{i}}w_{i,t}}{\sum _{h_{t}(x_{i})\neq y_{i}}w_{i,t}}}$ на каждом шаге, что может упростить расчет новых весов.)

Варианты

Настоящая АдаБуст

Результатом работы деревьев решений является оценка вероятности класса. $p(x)=P(y=1|x)$, вероятность того, что $x$ находится в положительном классе. Фридман, Хасти и Тибширани вывели аналитический минимизатор для $e^{-y\left(F_{t-1}(x)+f_{t}(p(x))\right)}$ для некоторых фиксированных $p(x)$ (обычно выбирается с использованием взвешенной ошибки наименьших квадратов):

$f_{t}(x)={\frac {1}{2}}\ln \left({\frac {x}{1-x}}\right)$.

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

ЛогитБуст

Основная статья: LogitBoost

LogitBoost представляет собой применение известных методов логистической регрессии к методу AdaBoost. Вместо того, чтобы минимизировать ошибку по отношению к y, слабые ученики выбираются так, чтобы минимизировать ошибку (взвешенного метода наименьших квадратов) $f_{t}(x)$ относительно $$z_{t}={\frac {y^{*}-p_{t}(x)}{2p_{t}(x)(1-p_{t}(x))}},$$где $$p_{t}(x)={\frac {e^{F_{t-1}(x)}}{e^{F_{t-1}(x)}+e^{-F_{t-1}(x)}}},$$$$w_{t}=p_{t}(x)(1-p_{t}(x))$$$$y^{*}={\frac {y+1}{2}}.$$

То есть $z_{t}$ — аппроксимация Ньютона–Рафсона минимизатора логарифмической ошибки на этапе $t$и слабый ученик $f_{t}$ выбирается в качестве учащегося, который лучше всего приближается $z_{t}$ по взвешенным наименьшим квадратам.

Когда p приближается к 1 или 0, значение $p_{t}(x_{i})(1-p_{t}(x_{i}))$ становится очень маленьким, и член z , который велик для неправильно классифицированных образцов, может стать численно нестабильным из-за ошибок машинного округления. Этого можно избежать, установив некоторые ограничения на абсолютное значение z и минимальное значение w.

Нежный AdaBoost

В то время как предыдущие алгоритмы повышения выбирают $f_{t}$ GentleBoost жадно минимизирует общую ошибку теста на каждом этапе, насколько это возможно, и имеет ограниченный размер шага. $f_{t}$ выбран для минимизации ${\textstyle \sum _{i}w_{t,i}(y_{i}-f_{t}(x_{i}))^{2}}$, и дополнительный коэффициент не применяется. Таким образом, в случае, когда слабый обучающийся демонстрирует отличные результаты классификации, GentleBoost выбирает $f_{t}(x)=\alpha _{t}h_{t}(x)$ точно равен $y$, в то время как алгоритмы наискорейшего спуска пытаются установить $\alpha _{t}=\infty$. Эмпирические наблюдения о хороших характеристиках GentleBoost, по-видимому, подтверждают замечание Шапире и Сингера о том, что допускаются чрезмерно большие значения $\alpha$ может привести к плохой эффективности обобщения.

Досрочное прекращение

Метод ускорения обработки усиленных классификаторов, раннее завершение означает тестирование каждого потенциального объекта только с таким количеством слоев окончательного классификатора, которое необходимо для достижения некоторого порога достоверности, что ускоряет вычисления в тех случаях, когда класс объекта может быть легко определен. Одной из таких схем является система обнаружения объектов, предложенная Виолой и Джонсом: В приложении со значительно большим количеством отрицательных образцов, чем положительных, обучается каскад отдельных буст-классификаторов, выходные данные каждого этапа смещаются так, что некоторая приемлемо малая часть положительных образцов ошибочно помечается как отрицательные, а все образцы, помеченные как отрицательные после каждого этапа, отброшено. Если на каждом этапе отфильтровывается 50% отрицательных выборок, через весь классификатор пройдет лишь очень небольшое количество объектов, что снижает трудоемкость вычислений. С тех пор этот метод был обобщен, и появилась формула для выбора оптимальных порогов на каждом этапе для достижения желаемого уровня ложноположительных и ложноотрицательных результатов.

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

Полностью корректирующие алгоритмы

Для версий AdaBoost с самым крутым спуском, где $\alpha _{t}$ выбирается на каждом слое t , чтобы минимизировать ошибку теста, следующий добавляемый слой считается максимально независимым от слоя t : маловероятно, что вы выберете слабого ученика t+1 , похожего на ученика t . Однако остается вероятность того, что t+1 выдает информацию, аналогичную некоторому другому более раннему уровню. Полностью корректирующие алгоритмы, такие как LPBoost , оптимизируют значение каждого коэффициента после каждого шага, так что новые добавляемые слои всегда максимально независимы от каждого предыдущего слоя. Это может быть достигнуто путем обратной установки, линейного программирования или каким-либо другим методом.

Обрезка

Сокращение — это процесс удаления плохо работающих слабых классификаторов для улучшения памяти и затрат времени на выполнение усиленного классификатора. Простейшими методами, которые могут быть особенно эффективными в сочетании с полностью корректирующим обучением, являются обрезка веса или предела: когда коэффициент или вклад в общую ошибку теста какого-либо слабого классификатора падает ниже определенного порога, этот классификатор упавший. Марджинанту и Дитерих предложил альтернативный критерий обрезки: слабые классификаторы следует выбирать так, чтобы разнообразие ансамбля было максимальным. Если два слабых ученика дают очень похожие результаты, эффективность можно повысить, удалив одного из них и увеличив коэффициент оставшегося слабого ученика.

См. также

• Бутстрап-агрегирование
• Совместное усиление
• БраунBoost
• Повышение градиента
• Метод мультипликативного обновления веса § Алгоритм AdaBoost

Дальнейшее чтение

• Фройнд, Йоав; Шапире, Роберт Э (1997). «Теоретико-решающее обобщение онлайн-обучения и его применение к повышению эффективности». Журнал компьютерных и системных наук . 55 : 119–139. CiteSeerX   10.1.1.32.8918 . doi : 10.1006/jcss.1997.1504 : оригинальная статья Йоава Фройнда и Роберта Э. Шапире, в которой впервые представлен AdaBoost.
• Чжоу, Чжихуа (2008). «Политическое объяснение алгоритма повышения» (PDF) . В: Материалы 21-й ежегодной конференции по теории обучения (COLT'08) : 479–490. На полях объяснение алгоритма повышения.
• Чжоу, Чжихуа (2013). «О сомнениях в маржинальном объяснении повышения» (PDF) . Искусственный интеллект . 203 (2013): 1–18. arXiv : 1009.3613 . Бибкод : 2010arXiv1009.3613G . дои : 10.1016/j.artint.2013.07.002 . S2CID   2828847 . По поводу сомнений в маржинальном объяснении повышения.