АдаБуст

Алгоритм классификации на основе адаптивного усиления

AdaBoost (сокращение от Ada ptive Boosting ) — это статистический метаалгоритм классификации , сформулированный Йоавом Фройндом и Робертом Шапиром в 1995 году, которые в 2003 году получили премию Гёделя за свою работу. Его можно использовать в сочетании со многими типами алгоритмов обучения для повышения производительности. Выходные данные нескольких слабых учеников объединяются во взвешенную сумму, которая представляет собой конечный выход усиленного классификатора. Обычно AdaBoost представлен для бинарной классификации , хотя его можно обобщить на несколько классов или ограниченные интервалы действительных значений. ^{[1] [2]}

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

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

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

Обучение

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

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

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

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

Взвешивание

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

Вывод

Этот вывод следует за Рохасом (2009): ^[6]

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

Итак, остается определить, какой слабый классификатор является лучшим выбором для , и каким должен быть его вес. Мы определяем общую ошибку как сумму ее экспоненциальных потерь на каждой точке данных, заданную следующим образом: ${\displaystyle k_{m}}$ ${\displaystyle \alpha _{m}}$ ${\displaystyle E}$ ${\displaystyle C_{m}}$ $${\displaystyle 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})}}$$

Полагая и для , имеем: ${\displaystyle w_{i}^{(1)}=1}$ ${\displaystyle w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}}$ ${\displaystyle m>1}$ $${\displaystyle E=\sum _{i=1}^{N}w_{i}^{(m)}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}}$$

Мы можем разделить это суммирование между теми точками данных, которые правильно классифицированы (so ), и теми, которые классифицированы неправильно (so ): ${\displaystyle k_{m}}$ ${\displaystyle y_{i}k_{m}(x_{i})=1}$ ${\displaystyle y_{i}k_{m}(x_{i})=-1}$ $${\displaystyle {\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}}}$$

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

Чтобы определить желаемый вес , который минимизируется с тем , который мы только что определили, мы дифференцируем: ${\displaystyle \alpha _{m}}$ ${\displaystyle E}$ ${\displaystyle k_{m}}$ $${\displaystyle {\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}}}}$$

К счастью, минимум достигается при установке этого значения в ноль, а затем решение дает : ${\displaystyle \alpha _{m}}$ $${\displaystyle \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)}$$

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

$${\displaystyle {\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}$$потому что не зависит от ${\displaystyle e^{-\alpha _{m}}}$ ${\displaystyle i}$ $${\displaystyle 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)}}$$ $${\displaystyle -\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)}$$ $${\displaystyle -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)}$$ $${\displaystyle \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)}$$ $${\displaystyle \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)}$$

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

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

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

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

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

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

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

При выборе функции потерь допускается большая гибкость. Пока функция потерь монотонна и непрерывно дифференцируема , классификатор всегда стремится к более чистым решениям. ^[7] Чжан (2004) предлагает функцию потерь, основанную на наименьших квадратах, модифицированную функцию потерь Хьюбера : $${\displaystyle \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, для значений, близких к 1 или -1, не штрафует «слишком уверенные» прогнозы ( ), в отличие от немодифицированного метода наименьших квадратов, и штрафует только образцы, неправильно классифицированные с уверенностью больше 1, линейно, а не квадратично или экспоненциально, и, таким образом, менее восприимчива к эффектам выбросов. ${\displaystyle f(x)}$ ${\displaystyle yf(x)>1}$

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

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

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

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

С:

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

Для : ​ ${\displaystyle t}$ ${\displaystyle 1\dots T}$

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

Варианты

Настоящий AdaBoost

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

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

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

LogitBoost

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

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

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

Нежный AdaBoost

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

Досрочное расторжение

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

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

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

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

Обрезка

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

Смотрите также

• Агрегирование Bootstrap
• CoBoosting
• BrownBoost
• Повышение градиента
• Метод обновления мультипликативного веса § Алгоритм AdaBoost

Ссылки

1. Фройнд, Йоав; Шапир, Роберт Э. (1995), Обобщение теории решений онлайн-обучения и его применение к повышению эффективности, Lecture Notes in Computer Science, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 23–37, doi :10.1007/3-540-59119-2_166, ISBN 978-3-540-59119-1, получено 2022-06-24
2. Хасти, Тревор; Россет, Сахарон; Чжу, Цзи; Цзоу, Хуэй (2009). «Мультиклассовый AdaBoost». Статистика и ее интерфейс . 2 (3): 349–360. doi : 10.4310/sii.2009.v2.n3.a8 . ISSN  1938-7989.
3. Уайнер, Абрахам Дж.; Олсон, Мэтью; Блейх, Джастин; Миз, Дэвид (2017). «Объяснение успеха AdaBoost и случайных лесов как интерполирующих классификаторов». Журнал исследований машинного обучения . 18 (48): 1–33 . Получено 17 марта 2022 г.
4. Кегль, Балаж (20 декабря 2013 г.). «Возвращение AdaBoost.MH: многоклассовые деревья Хэмминга». arXiv : 1312.6086 [cs.LG].
5. Джоглекар, Сачин. "adaboost – блог Сачина Джоглекара". codesachin.wordpress.com . Получено 3 августа 2016 г. .
6. Рохас, Рауль (2009). «AdaBoost и суперкубок классификаторов: введение в адаптивный бустинг» (Технический представитель) . Свободный университет, Берлин.
7. Фридман, Джером; Хасти, Тревор; Тибширани, Роберт (1998). «Аддитивная логистическая регрессия: статистический взгляд на усиление». Annals of Statistics . 28 : 2000. CiteSeerX 10.1.1.51.9525 . 
8. Чжан, Т. (2004). «Статистическое поведение и согласованность методов классификации, основанных на минимизации выпуклого риска». Annals of Statistics . 32 (1): 56–85. doi : 10.1214/aos/1079120130 . JSTOR  3448494.
9. Шапир, Роберт; Сингер, Йорам (1999). «Улучшенные алгоритмы повышения эффективности с использованием прогнозов с рейтингом достоверности»: 80–91. CiteSeerX 10.1.1.33.4002 .  {{cite journal}}: Цитировать журнал требует |journal=( помощь )
10. Фройнд; Шапир (1999). «Краткое введение в бустинг» (PDF) :
11. Виола, Пол; Джонс, Роберт (2001). «Быстрое обнаружение объектов с использованием усиленного каскада простых признаков». CiteSeerX 10.1.1.10.6807 .  {{cite journal}}: Цитировать журнал требует |journal=( помощь )
12. Маккейн, Брендан; Новинс, Кевин; Альберт, Майкл (2005). «Оптимизация каскадных классификаторов». {{cite journal}}: Цитировать журнал требует |journal=( помощь )
13. Тревор Хасти; Роберт Тибширани; Джером Фридман (2009). Элементы статистического обучения: добыча данных, вывод и прогнозирование (2-е изд.). Нью-Йорк: Springer. ISBN 978-0-387-84858-7.
14. Шохман, Ян; Матас, Йиржи (2004). Adaboost с полностью корректирующими обновлениями для быстрого обнаружения лиц . ISBN 978-0-7695-2122-0.
15. Маргинеанту, Драгос; Дитерих, Томас (1997). "Обрезка адаптивного усиления". CiteSeerX 10.1.1.38.7017 .  {{cite journal}}: Цитировать журнал требует |journal=( помощь )
16. Тамон, Кристино; Сян, Цзе (2000). «О проблеме усиливающей обрезки». {{cite journal}}: Цитировать журнал требует |journal=( помощь )

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

• Freund, Yoav; Schapire, Robert E (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 . Bibcode :2010arXiv1009.3613G. doi :10.1016/j.artint.2013.07.002. S2CID  2828847.О сомнении относительно маржинального объяснения повышения.