AdaBoost - AdaBoost

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

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

Обзор

Проблемы в машинном обучении часто страдают от проклятие размерности - каждый образец может состоять из огромного количества потенциальных признаков (например, их может быть 162 336 Особенности Хаара, как используется Среда обнаружения объектов Виолы – Джонса, в окне изображения 24 × 24 пикселя), а оценка каждой функции может снизить не только скорость обучения и выполнения классификатора, но и фактически уменьшить предсказательную силу.^[4] в отличие нейронные сети и SVM, процесс обучения AdaBoost выбирает только те функции, которые, как известно, улучшают прогнозирующую способность модели, уменьшая размерность и потенциально улучшая время выполнения, поскольку нерелевантные функции не нужно вычислять.

Подготовка

AdaBoost относится к определенному методу обучения усиленного классификатора. Классификатор повышения - это классификатор в форме

{ Displaystyle F_ {T} (x) = sum _ {t = 1} ^ {T} f_ {t} (x) , !}

где каждый ${ displaystyle f_ {t}}$ слабый ученик, который берет предмет ${ displaystyle x}$ в качестве ввода и возвращает значение, указывающее класс объекта. Например, в задаче с двумя классами знак выходных данных слабого обучаемого идентифицирует предсказанный класс объекта, а абсолютное значение дает уверенность в этой классификации. Точно так же ${ displaystyle T}$ th классификатор положительный, если образец находится в положительном классе, и отрицательный в противном случае.

Каждый слабый ученик выдвигает гипотезу вывода, ${ 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_ {т-1} (х)}$ - это усиленный классификатор, который был построен на предыдущем этапе обучения, ${ Displaystyle E (F)}$ это некоторая функция ошибки и ${ displaystyle f_ {t} (x) = alpha _ {t} h (x)}$ является слабым учеником, которого рассматривают для добавления в окончательный классификатор.

Взвешивание

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

Вывод

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

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

{ Displaystyle C _ {(м-1)} (x_ {i}) = alpha _ {1} k_ {1} (x_ {i}) + cdots + alpha _ {m-1} k_ {m- 1} (x_ {i})}

Где класс будет знаком ${ Displaystyle С _ {(м-1)} (х_ {я})}$ . На ${ 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 ш_ {я} ^ {(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} )}}

Мы можем разделить это суммирование между теми точками данных, которые правильно классифицированы по ${ displaystyle k_ {m}}$ (так ${ Displaystyle у_ {я} к_ {м} (х_ {я}) = 1}$ ) и ошибочно классифицированные (так ${ displaystyle y_ {i} k_ {m} (x_ {i}) = - 1}$ ):

{ displaystyle 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}}}

{ displaystyle = sum _ {i = 1} ^ {N} w_ {i} ^ {(m)} e ^ {- alpha _ {m}} + sum _ {y_ {i} neq k_ { m} (x_ {i})} w_ {i} ^ {(m)} (e ^ { alpha _ {m}} - e ^ {- alpha _ {m}})}

Поскольку единственная часть правой части этого уравнения, которая зависит от ${ displaystyle k_ {m}}$ является ${ displaystyle sum _ {y_ {i} neq k_ {m} (x_ {i})} w_ {i} ^ {(m)}}$ , мы видим, что ${ displaystyle k_ {m}}$ что сводит к минимуму ${ displaystyle E}$ тот, который сводит к минимуму ${ displaystyle 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 - альфа _ {m} + log left ( sum _ {y_ {i} = k_ {m} (x_ {i})} w_ {i} ^ {(m)} right) = alpha _ {m} + log left ( sum _ {y_ {i} neq k_ {m} (x_ {i})} w_ {i} ^ {(m)} right)}

{ displaystyle -2 alpha _ {m} = log 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 альфа _ {m} = - { dfrac {1} {2}} log 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}} log left ({ dfrac { sum _ {y_ {i} = k_ {m} (x_ {i})} w_ {i} ^ {(m)}} { sum _ {y_ {i} neq k_ {m} (x_ {i})} w_ {i} ^ {(m)}}} right)}

Мы вычисляем взвешенную частоту ошибок слабого классификатора как ${ displaystyle epsilon _ {m} = 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) }

которая представляет собой функцию отрицательного логита, умноженную на 0,5.

Таким образом, мы получили алгоритм AdaBoost: на каждой итерации выбираем классификатор ${ displaystyle k_ {m}}$ , что минимизирует общую взвешенную ошибку ${ displaystyle sum _ {y_ {i} neq k_ {m} (x_ {i})} w_ {i} ^ {(m)}}$ , используйте это, чтобы вычислить частоту ошибок ${ displaystyle epsilon _ {m} = 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}}$ .

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

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

При выборе функции потерь допускается большая гибкость. Пока функция потерь монотонный и непрерывно дифференцируемый, классификатор всегда стремится к более чистым решениям.^[6] Чжан (2004) предоставляет функцию потерь, основанную на наименьших квадратах, модифицированную Функция потерь Хубера:

{ displaystyle phi (y, f (x)) = { begin {cases} -4yf (x) & { mbox {if}} yf (x) <- 1, (yf (x) -1 ) ^ {2} & { mbox {if}} - 1 leq yf (x) leq 1, 0 & { mbox {if}} yf (x)> 1 end {cases}}}

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

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

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

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

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

С участием:

Образцы ${ displaystyle x_ {1} dots x_ {n}}$
Желаемые результаты ${ displaystyle y_ {1} dots y_ {n}, y in {- 1,1 }}$
Начальные веса ${ Displaystyle ш_ {1,1} точки ш_ {п, 1}}$ установлен в ${ displaystyle { frac {1} {n}}}$
Функция ошибки ${ Displaystyle Е (е (х), у, я) = е ^ {- у_ {я} е (х_ {я})}}$
Слабые ученики ${ displaystyle h двоеточие x rightarrow {- 1,1 }}$

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

выберите ${ displaystyle h_ {t} (x)}$ $h_t (х)$ :
- Найдите слабого ученика ${ 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_ {я, t + 1}}$ такой, что ${ Displaystyle сумма _ {я} w_ {я, т + 1} = 1}$
- (Примечание: можно показать, что ${ displaystyle { frac { sum _ {h_ {t + 1} (x_ {i}) = y_ {i}} w_ {i, t + 1}} { sum _ {h_ {t + 1} ( 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}}}}$ на каждом этапе, что может упростить расчет новых весов.)

Выбор $α т$

${ displaystyle alpha _ {t}}$ выбран, поскольку аналитически показано, что он является минимизатором экспоненциальной функции ошибок для Discrete AdaBoost.^[8]

Свести к минимуму:

${ displaystyle sum _ {i} w_ {i} e ^ {- y_ {i} h_ {i} alpha _ {t}}}$

Используя выпуклость экспоненциальной функции и предполагая, что ${ displaystyle forall i, h_ {i} in [-1,1]}$ у нас есть:

${ displaystyle { begin {align} sum _ {i} w_ {i} e ^ {- y_ {i} h_ {i} alpha _ {t}} & leq sum _ {i} left ( { frac {1-y_ {i} h_ {i}} {2}} right) w_ {i} e ^ { alpha _ {t}} + sum _ {i} left ({ frac { 1 + y_ {i} h_ {i}} {2}} right) w_ {i} e ^ {- alpha _ {t}} & = left ({ frac { epsilon _ {t} } {2}} right) e ^ { alpha _ {t}} + left ({ frac {1- epsilon _ {t}} {2}} right) e ^ {- alpha _ { т}} конец {выровнено}}}$

Затем мы дифференцируем это выражение относительно ${ displaystyle alpha _ {t}}$ и установите его в ноль, чтобы найти минимум верхней границы:

${ displaystyle { begin {align} left ({ frac { epsilon _ {t}} {2}} right) e ^ { alpha _ {t}} - left ({ frac {1- epsilon _ {t}} {2}} right) e ^ {- alpha _ {t}} & = 0 alpha _ {t} & = { frac {1} {2}} ln left ({ frac {1- epsilon _ {t}} { epsilon _ {t}}} right) end {align}}}$

Обратите внимание, что это применимо только когда ${ displaystyle h_ {i} in {- 1,1 }}$ , хотя это может быть хорошей отправной точкой в других случаях, например, когда слабый ученик предвзято ( ${ displaystyle h (x) in {a, b }, a neq -b}$ ), имеет несколько листьев ( ${ Displaystyle ч (х) в {а, б, точки, п }}$ ) или какая-то другая функция ${ Displaystyle ч (х) в mathbb {R}}$ . В таких случаях выбор слабого ученика и коэффициента можно свести к одному шагу, в котором ${ displaystyle f_ {t} = alpha _ {t} h_ {t} (x)}$ выбирается из всех возможных ${ displaystyle alpha, h}$ как минимизатор ${ displaystyle sum _ {i} w_ {i, t} e ^ {- y_ {i} f_ {t} (x_ {i})}}$ с помощью некоторой процедуры числового поиска.

Варианты

Реальный AdaBoost

Результатом деревьев решений является оценка вероятности класса ${ Displaystyle р (х) = п (у = 1 | х)}$ , вероятность того, что ${ displaystyle x}$ находится в положительном классе.^[6] Фридман, Хасти и Тибширани выводят аналитический минимизатор для ${ 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_ { т-1} (х)}}},}

{ Displaystyle ш_ {т} = р_ {т} (х) (1-р_ {т} (х))}

{ displaystyle y ^ {*} = { frac {y + 1} {2}}.}

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

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

Нежный AdaBoost

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

Раннее прекращение

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

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

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

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

Обрезка

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

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

использованная литература

^ «Алгоритмы повышения: AdaBoost, Gradient Boosting и XGBoost». hackernoon.com. 5 мая 2018 г.. Получено 2020-01-04.
^ Кегл, Балаж (20 декабря 2013 г.). «Возвращение AdaBoost.MH: мультиклассовые деревья Хэмминга». arXiv:1312.6086 [cs.LG ].
^ Йоглекар, Сачин. "adaboost - блог Сачина Джоглекара". codeachin.wordpress.com. Получено 3 августа 2016.
^ Хьюз, Г.Ф. (Январь 1968 г.). «О средней точности статистических распознавателей образов». IEEE Transactions по теории информации. 14 (1): 55–63. Дои:10.1109 / TIT.1968.1054102. S2CID 206729491.
^ Рохас, Р. (2009). AdaBoost и супер чаша классификаторов - введение в адаптивное повышение. Свободный университет, Берлин, Tech. Rep.
^ ^а ^б Фридман, Джером; Хасти, Тревор; Тибширани, Роберт (1998). «Аддитивная логистическая регрессия: статистический взгляд на повышение». CiteSeerX 10.1.1.51.9525. Цитировать журнал требует | журнал = (Помогите)
^ Чжан, Т. (2004). «Статистическое поведение и последовательность методов классификации, основанных на минимизации выпуклого риска». Анналы статистики. 32 (1): 56–85. JSTOR 3448494.
^ ^а ^б Шапир, Роберт; Певец, Йорам (1999). «Улучшенные алгоритмы повышения с использованием уверенных прогнозов». CiteSeerX 10.1.1.33.4002. Цитировать журнал требует | журнал = (Помогите)
^ Фройнд; Шапир (1999). «Краткое введение в повышение эффективности» (PDF):
^ Виола, Поль; Джонс, Роберт (2001). «Быстрое обнаружение объектов с использованием усиленного каскада простых функций». CiteSeerX 10.1.1.10.6807. Цитировать журнал требует | журнал = (Помогите)
^ Маккейн, Брендан; Новинс, Кевин; Альберт, Майкл (2005). «Оптимизация каскадных классификаторов». Цитировать журнал требует | журнал = (Помогите)
^ Тревор Хасти; Роберт Тибширани; Джером Фридман (2009). Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование (2-е изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-84858-7.
^ Шохман, Ян; Матас, Иржи (2004). Adaboost с полностью корректирующими обновлениями для быстрого распознавания лиц. ISBN 978-0-7695-2122-0.
^ Марджинеанту, Драгос; Диттерих, Томас (1997). «Адаптивное усиление обрезки». CiteSeerX 10.1.1.38.7017. Цитировать журнал требует | журнал = (Помогите)
^ Тамон, Кристино; Сян, Цзе (2000). «О проблеме ускоренной обрезки». Цитировать журнал требует | журнал = (Помогите)

Фройнд, Йоав; Шапир, Роберт Э (1997). «Теоретико-решающее обобщение онлайн-обучения и приложение для повышения квалификации». Журнал компьютерных и системных наук. 55: 119–139. CiteSeerX 10.1.1.32.8918. Дои: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. Дои:10.1016 / j.artint.2013.07.002. О сомнении в маржинальном объяснении повышения.

[1] «Алгоритмы повышения: AdaBoost, Gradient Boosting и XGBoost». hackernoon.com. 5 мая 2018 г.. Получено 2020-01-04.

[2] Кегл, Балаж (20 декабря 2013 г.). «Возвращение AdaBoost.MH: мультиклассовые деревья Хэмминга». arXiv:1312.6086 [cs.LG ].

[3] Йоглекар, Сачин. "adaboost - блог Сачина Джоглекара". codeachin.wordpress.com. Получено 3 августа 2016.

[4] Хьюз, Г.Ф. (Январь 1968 г.). «О средней точности статистических распознавателей образов». IEEE Transactions по теории информации. 14 (1): 55–63. Дои:10.1109 / TIT.1968.1054102. S2CID 206729491.

[5] Рохас, Р. (2009). AdaBoost и супер чаша классификаторов - введение в адаптивное повышение. Свободный университет, Берлин, Tech. Rep.

[fht-6] а ^б Фридман, Джером; Хасти, Тревор; Тибширани, Роберт (1998). «Аддитивная логистическая регрессия: статистический взгляд на повышение». CiteSeerX 10.1.1.51.9525. Цитировать журнал требует | журнал = (Помогите)

[7] Чжан, Т. (2004). «Статистическое поведение и последовательность методов классификации, основанных на минимизации выпуклого риска». Анналы статистики. 32 (1): 56–85. JSTOR 3448494.

[ss-8] а ^б Шапир, Роберт; Певец, Йорам (1999). «Улучшенные алгоритмы повышения с использованием уверенных прогнозов». CiteSeerX 10.1.1.33.4002. Цитировать журнал требует | журнал = (Помогите)

[fs-9] Фройнд; Шапир (1999). «Краткое введение в повышение эффективности» (PDF):

[10] Виола, Поль; Джонс, Роберт (2001). «Быстрое обнаружение объектов с использованием усиленного каскада простых функций». CiteSeerX 10.1.1.10.6807. Цитировать журнал требует | журнал = (Помогите)

[11] Маккейн, Брендан; Новинс, Кевин; Альберт, Майкл (2005). «Оптимизация каскадных классификаторов». Цитировать журнал требует | журнал = (Помогите)

[12] Тревор Хасти; Роберт Тибширани; Джером Фридман (2009). Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование (2-е изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-84858-7.

[13] Шохман, Ян; Матас, Иржи (2004). Adaboost с полностью корректирующими обновлениями для быстрого распознавания лиц. ISBN 978-0-7695-2122-0.

[14] Марджинеанту, Драгос; Диттерих, Томас (1997). «Адаптивное усиление обрезки». CiteSeerX 10.1.1.38.7017. Цитировать журнал требует | журнал = (Помогите)

[15] Тамон, Кристино; Сян, Цзе (2000). «О проблеме ускоренной обрезки». Цитировать журнал требует | журнал = (Помогите)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]