АдаБуст
AdaBoost , сокращение от Adaptive Boosting , — это статистической классификации мета-алгоритм , сформулированный Йоавом Фройндом и Робертом Шапиром в 1995 году, получившими за свою работу премию Гёделя в 2003 году . Его можно использовать в сочетании со многими другими типами алгоритмов обучения для повышения производительности. Выходные данные других алгоритмов обучения («слабые ученики») объединяются во взвешенную сумму, которая представляет собой конечный результат усиленного классификатора. Обычно AdaBoost представлен для двоичной классификации , хотя его можно обобщить на несколько классов или ограниченные интервалы в реальной строке. [1] [2]
AdaBoost является адаптивным в том смысле, что последующие слабые ученики настраиваются в пользу тех экземпляров, которые были неправильно классифицированы предыдущими классификаторами. В некоторых задачах он может быть менее подвержен проблеме переобучения , чем другие алгоритмы обучения. Отдельные учащиеся могут быть слабыми, но пока производительность каждого из них немного лучше, чем случайное угадывание, можно доказать, что окончательная модель сходится к сильному учащемуся.
Хотя AdaBoost обычно используется для объединения слабых базовых обучающихся (например, пней решений ), было показано, что он также может эффективно объединять сильные базовые обучающиеся (например, глубокие деревья решений ), создавая еще более точную модель. [3]
Каждый алгоритм обучения имеет тенденцию лучше подходить к одним типам задач, чем к другим, и обычно имеет множество различных параметров и конфигураций, которые необходимо настроить, прежде чем он достигнет оптимальной производительности в наборе данных. AdaBoost (с деревьями решений в качестве слабых обучающихся) часто называют лучшим готовым классификатором. [4] [5] При использовании с обучением дерева решений информация, собранная на каждом этапе алгоритма AdaBoost об относительной «твердости» каждой обучающей выборки, передается в алгоритм выращивания дерева, так что последующие деревья имеют тенденцию сосредотачиваться на примерах, которые труднее классифицировать.
Обучение
[ редактировать ]AdaBoost относится к конкретному методу обучения усиленного классификатора. Усиленный классификатор — это классификатор вида где каждый слабый ученик, который берет предмет в качестве входных данных и возвращает значение, указывающее класс объекта. Например, в задаче с двумя классами знак результатов слабого учащегося определяет прогнозируемый класс объекта, а абсолютное значение дает уверенность в этой классификации. Аналогичным образом, -й классификатор является положительным, если образец относится к положительному классу, и отрицательным в противном случае.
Каждый слабый ученик выдвигает выходную гипотезу который фиксирует прогноз для каждого образца в обучающем наборе. На каждой итерации , выбирается слабый ученик и ему присваивается коэффициент такая, что общая ошибка обучения полученного Усиленный классификатор -этапа сведен к минимуму.
Здесь — это усиленный классификатор, построенный на предыдущем этапе обучения и — это слабый ученик, которого рассматривают для добавления в окончательный классификатор.
Взвешивание
[ редактировать ]На каждой итерации тренировочного процесса вес присваивается каждой выборке в обучающем наборе, равной текущей ошибке на этом образце. Эти веса можно использовать при обучении слабых учеников. Например, можно вырастить деревья решений, способствующие разделению наборов выборок с большими весами.
Вывод
[ редактировать ]Этот вывод следует из Рохаса (2009): [6]
Предположим, у нас есть набор данных где каждый предмет имеет связанный класс и набор слабых классификаторов каждый из которых выводит классификацию для каждого предмета. После -th итерации наш усиленный классификатор представляет собой линейную комбинацию слабых классификаторов вида: где класс будет признаком . На -th итерации мы хотим расширить это до более мощного классификатора, добавив еще один слабый классификатор. , с другим весом :
Итак, осталось определить, какой слабый классификатор является лучшим выбором для и какой у него вес должно быть. Определим суммарную ошибку из как сумма экспоненциальных потерь в каждой точке данных, определяемая следующим образом:
Сдача в аренду и для , у нас есть:
Мы можем разделить это суммирование между теми точками данных, которые правильно классифицированы по (так ) и те, которые неправильно классифицированы (поэтому ):
Поскольку единственная часть правой части этого уравнения, зависящая от является , мы видим, что что сводит к минимуму это тот, что в наборе что сводит к минимуму [предполагая, что ], т.е. слабый классификатор с наименьшей взвешенной ошибкой (с весами ).
Чтобы определить желаемый вес что сводит к минимуму с что мы только что определили, дифференцируем:
К счастью, минимум достигается при установке этого значения на ноль, а затем при определении дает:
потому что не зависит от
Мы рассчитываем взвешенную частоту ошибок слабого классификатора как , поэтому следует, что: что представляет собой отрицательную логит-функцию, умноженную на 0,5. Из-за выпуклости как функция , это новое выражение для дает глобальный минимум функции потерь.
Примечание. Этот вывод применяется только тогда, когда , хотя в других случаях это может быть хорошей отправной точкой, например, когда слабый ученик предвзято ( ), имеет несколько листьев ( ) или какая-то другая функция .
Таким образом мы получили алгоритм AdaBoost: на каждой итерации выбираем классификатор , что минимизирует общую взвешенную ошибку , используйте это для расчета частоты ошибок , используйте это для расчета веса и, наконец, используйте это для улучшения усиленного классификатора к .
Статистическое понимание бустинга
[ редактировать ]Этот раздел нуждается в дополнительных цитатах для проверки . ( Май 2016 г. ) |
Бустинг — это форма линейной регрессии , в которой особенности каждой выборки это результаты какого-то слабого ученика применяется к .
Хотя регрессия пытается соответствовать к как можно точнее, без потери обобщения, обычно с использованием наименьших квадратов ошибки , тогда как функция ошибок AdaBoost учитывает тот факт, что используется только знак конечного результата, таким образом может быть намного больше 1 без увеличения ошибки. Однако экспоненциальный рост ошибки для выборки как увеличивается, что приводит к тому, что выбросам присваиваются чрезмерные веса.
Одной из особенностей выбора экспоненциальной функции ошибок является то, что ошибка итоговой аддитивной модели является произведением ошибок каждого этапа, т.е. . Таким образом, можно видеть, что обновление веса в алгоритме AdaBoost эквивалентно пересчету ошибки на после каждого этапа.
При выборе функции потерь допускается большая гибкость. Пока функция потерь монотонна и непрерывно дифференцируема , классификатор всегда стремится к более чистым решениям. [7] Чжан (2004) предоставляет функцию потерь, основанную на методе наименьших квадратов, модифицированную функцию потерь Хубера :
Эта функция работает лучше, чем LogitBoost, для близкое к 1 или -1, не наказывает «чрезмерно самоуверенные» прогнозы ( ), в отличие от немодифицированного метода наименьших квадратов, и штрафует только выборки, неправильно классифицированные с достоверностью более 1, линейно, а не квадратично или экспоненциально, и, таким образом, менее восприимчив к эффектам выбросов.
Повышение как градиентный спуск
[ редактировать ]Повышение можно рассматривать как минимизацию выпуклой функции потерь над выпуклым набором функций. [8] В частности, потери, минимизируемые AdaBoost, представляют собой экспоненциальные потери. тогда как LogitBoost выполняет логистическую регрессию, минимизируя
В аналогии с градиентным спуском выходные данные классификатора для каждой обучающей точки считаются точкой. в n-мерном пространстве, где каждая ось соответствует обучающей выборке, каждый слабый обучаемый соответствует вектору фиксированной ориентации и длины, и цель состоит в том, чтобы достичь целевой точки (или любой регион, где значение функции потерь меньше значения в этой точке) за наименьшее количество шагов. Таким образом, алгоритмы AdaBoost выполняют либо Коши (найти с самым крутым уклоном выберите чтобы минимизировать ошибку теста) или Ньютона (выберите какую-нибудь целевую точку, найдите это приносит ближайший к этой точке) оптимизация ошибки обучения.
Пример алгоритма (Дискретный AdaBoost)
[ редактировать ]С:
- Образцы
- Желаемые результаты
- Начальный вес установлен на
- Функция ошибки
- Слабые ученики
Для в :
- Выбирать :
- Найдите слабого ученика что сводит к минимуму , ошибка взвешенной суммы для неправильно классифицированных точек
- Выбирать
- Добавить в ансамбль:
- Обновление весов:
- для в
- Перенормировать такой, что
- (Примечание: можно показать, что на каждом шаге, что может упростить расчет новых весов.)
Варианты
[ редактировать ]Настоящая АдаБуст
[ редактировать ]Результатом работы деревьев решений является оценка вероятности класса. , вероятность того, что находится в положительном классе. [7] Фридман, Хасти и Тибширани вывели аналитический минимизатор для для некоторых фиксированных (обычно выбирается с использованием взвешенной ошибки наименьших квадратов):
- .
Таким образом, вместо того, чтобы умножать выходные данные всего дерева на некоторое фиксированное значение, каждый листовой узел изменяется так, чтобы выводить половину логит - преобразования его предыдущего значения.
ЛогитБуст
[ редактировать ]LogitBoost представляет собой применение известных методов логистической регрессии к методу AdaBoost. Вместо того, чтобы минимизировать ошибку по отношению к y, слабые ученики выбираются так, чтобы минимизировать ошибку (взвешенного метода наименьших квадратов) относительно где
То есть — аппроксимация Ньютона–Рафсона минимизатора логарифмической ошибки на этапе и слабый ученик выбирается в качестве учащегося, который лучше всего приближается по взвешенным наименьшим квадратам.
Когда p приближается к 1 или 0, значение становится очень маленьким, и член z , который велик для неправильно классифицированных образцов, может стать численно нестабильным из-за ошибок машинного округления. Этого можно избежать, установив некоторые ограничения на абсолютное значение z и минимальное значение w.
Нежный AdaBoost
[ редактировать ]В то время как предыдущие алгоритмы повышения выбирают GentleBoost жадно минимизирует общую ошибку теста на каждом этапе, насколько это возможно, и имеет ограниченный размер шага. выбран для минимизации , и дополнительный коэффициент не применяется. Таким образом, в случае, когда слабый обучающийся демонстрирует отличные результаты классификации, GentleBoost выбирает точно равен , в то время как алгоритмы наискорейшего спуска пытаются установить . Эмпирические наблюдения о хороших характеристиках GentleBoost, по-видимому, подтверждают замечание Шапире и Сингера о том, что допускаются чрезмерно большие значения может привести к плохой эффективности обобщения. [9] [10]
Досрочное прекращение
[ редактировать ]Метод ускорения обработки усиленных классификаторов, раннее завершение означает тестирование каждого потенциального объекта только с таким количеством слоев окончательного классификатора, которое необходимо для достижения некоторого порога достоверности, что ускоряет вычисления в тех случаях, когда класс объекта может быть легко определен. Одной из таких схем является система обнаружения объектов, предложенная Виолой и Джонсом: [11] В приложении со значительно большим количеством отрицательных образцов, чем положительных, обучается каскад отдельных буст-классификаторов, выходные данные каждого этапа смещаются так, что некоторая приемлемо малая часть положительных образцов ошибочно помечается как отрицательные, а все образцы, помеченные как отрицательные после каждого этапа, отброшено. Если на каждом этапе отфильтровывается 50% отрицательных выборок, через весь классификатор пройдет лишь очень небольшое количество объектов, что снижает трудоемкость вычислений. С тех пор этот метод был обобщен, и появилась формула для выбора оптимальных порогов на каждом этапе для достижения желаемого уровня ложноположительных и ложноотрицательных результатов. [12]
В области статистики, где AdaBoost чаще применяется для решения задач умеренной размерности, ранняя остановка используется как стратегия уменьшения переобучения . [13] Проверочный набор образцов отделяется от обучающего набора, производительность классификатора на образцах, используемых для обучения, сравнивается с производительностью на проверочных образцах, и обучение прекращается, если производительность на проверочной выборке снижается, даже если производительность на проверочной выборке снижается. обучающий набор продолжает улучшаться.
Полностью корректирующие алгоритмы
[ редактировать ]Для версий AdaBoost с самым крутым спуском, где выбирается на каждом слое t , чтобы минимизировать ошибку теста, следующий добавляемый слой считается максимально независимым от слоя t : [14] маловероятно, что вы выберете слабого ученика t+1 , похожего на ученика t . Однако остается вероятность того, что t+1 выдает информацию, аналогичную некоторому другому более раннему уровню. Полностью корректирующие алгоритмы, такие как LPBoost , оптимизируют значение каждого коэффициента после каждого шага, так что новые добавляемые слои всегда максимально независимы от каждого предыдущего слоя. Это может быть достигнуто путем обратной установки, линейного программирования или каким-либо другим методом.
Обрезка
[ редактировать ]Сокращение — это процесс удаления плохо работающих слабых классификаторов для улучшения памяти и затрат времени на выполнение усиленного классификатора. Простейшими методами, которые могут быть особенно эффективными в сочетании с полностью корректирующим обучением, являются обрезка веса или предела: когда коэффициент или вклад в общую ошибку теста какого-либо слабого классификатора падает ниже определенного порога, этот классификатор упавший. Марджинанту и Дитерих [15] предложил альтернативный критерий обрезки: слабые классификаторы следует выбирать так, чтобы разнообразие ансамбля было максимальным. Если два слабых ученика дают очень похожие результаты, эффективность можно повысить, удалив одного из них и увеличив коэффициент оставшегося слабого ученика. [16]
См. также
[ редактировать ]- Бутстрап-агрегирование
- Совместное усиление
- БраунBoost
- Повышение градиента
- Мультипликативный метод обновления веса § Алгоритм AdaBoost
Ссылки
[ редактировать ]- ^ Фройнд, Йоав; Шапире, Роберт Э. (1995), Теоретико-решающее [так в оригинале] обобщение онлайн-обучения и приложение к повышению , Конспекты лекций по информатике, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 23–37, doi : 10.1007/3-540-59119-2_166 , ISBN 978-3-540-59119-1 , получено 24 июня 2022 г.
- ^ Хасти, Тревор; Россе, Сахарон; Чжу, Цзи; Цзоу, Хуэй (2009). «Мультиклассовый AdaBoost» . Статистика и ее интерфейс . 2 (3): 349–360. дои : 10.4310/sii.2009.v2.n3.a8 . ISSN 1938-7989 .
- ^ Винер, Авраам Дж.; Олсон, Мэтью; Блайх, Джастин; Миз, Дэвид (2017). «Объяснение успеха AdaBoost и случайных лесов в качестве интерполирующих классификаторов» . Журнал исследований машинного обучения . 18 (48): 1–33 . Проверено 17 марта 2022 г.
- ^ Кегль, Балаж (20 декабря 2013 г.). «Возвращение AdaBoost.MH: многоклассовые деревья Хэмминга». arXiv : 1312.6086 [ cs.LG ].
- ^ Йоглекар, Сачин. «adaboost — блог Сачина Джоглекара» . codeachin.wordpress.com . Проверено 3 августа 2016 г.
- ^ Рохас, Рауль (2009). «AdaBoost и суперкубок классификаторов — учебное введение в адаптивное повышение» (Tech. Rep.) . Свободный университет, Берлин.
- ^ Перейти обратно: а б Фридман, Джером; Хасти, Тревор; Тибширани, Роберт (1998). «Аддитивная логистическая регрессия: статистический взгляд на повышение». Анналы статистики . 28 : 2000. CiteSeerX 10.1.1.51.9525 .
- ^ Чжан, Т. (2004). «Статистическое поведение и непротиворечивость методов классификации, основанных на выпуклой минимизации риска» . Анналы статистики . 32 (1): 56–85. дои : 10.1214/aos/1079120130 . JSTOR 3448494 .
- ^ Шапире, Роберт; Певец, Йорам (1999). «Улучшенные алгоритмы повышения с использованием прогнозов с достоверностью»: 80–91. CiteSeerX 10.1.1.33.4002 .
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь ) - ^ Фрейнд; Шапире (1999). «Краткое введение в повышение» (PDF) :
- ^ Виола, Пол; Джонс, Роберт (2001). «Быстрое обнаружение объектов с использованием расширенного каскада простых функций». CiteSeerX 10.1.1.10.6807 .
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь ) - ^ Маккейн, Брендан; Новинс, Кевин; Альберт, Майкл (2005). «Оптимизация каскадных классификаторов».
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь ) - ^ Тревор Хэсти; Роберт Тибширани; Джером Фридман (2009). Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование (2-е изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-84858-7 .
- ^ Шохман, Ян; Матас, Иржи (2004). Adaboost с полностью корректирующими обновлениями для быстрого распознавания лиц . ISBN 978-0-7695-2122-0 .
- ^ Маргинеанту, Драгош; Диттерих, Томас (1997). «Обрезка адаптивного повышения». CiteSeerX 10.1.1.38.7017 .
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь ) - ^ Тамон, Кристино; Сян, Цзе (2000). «О проблеме ускорения обрезки».
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь )
Дальнейшее чтение
[ редактировать ]- Фройнд, Йоав; Шапире, Роберт Э (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 . По поводу сомнений в маржинальном объяснении повышения.