В машинном обучении бустинг — это ансамблевый мета-алгоритм, предназначенный в первую очередь для снижения смещения и дисперсии. [1] Он используется в контролируемом обучении и семействе алгоритмов машинного обучения , которые преобразуют слабых учеников в сильных. [2]
Концепция усиления основана на вопросе, поставленном Кернсом и Валиантом (1988, 1989): [3] [4] «Может ли набор слабых учеников создать одного сильного ученика?» Слабый ученик определяется как классификатор , который лишь немного коррелирует с истинной классификацией (он может маркировать примеры лучше, чем случайное угадывание). Сильный ученик — это классификатор, который произвольно хорошо коррелирует с истинной классификацией. Роберт Шапир ответил на этот вопрос утвердительно в статье, опубликованной в 1990 году. [5] Это имело значительные последствия в машинном обучении и статистике , в частности, приведя к разработке усиления. [6]
Первоначально проблема усиления гипотезы просто относилась к процессу превращения слабого ученика в сильного. [3] Алгоритмы, которые достигают этого, быстро стали известны как «усиление». Дуга Фройнда и Шапира (Adapt[at]ive Resampling and Combining), [7] как общая техника, более или менее синонимична усилению. [8]
Хотя усиление алгоритмически не ограничено, большинство алгоритмов усиления состоят из итеративного обучения слабых классификаторов относительно распределения и добавления их к окончательному сильному классификатору. Когда они добавляются, они взвешиваются способом, который связан с точностью слабых учеников. После добавления слабого ученика веса данных перенастраиваются, что известно как «повторное взвешивание ». Неправильно классифицированные входные данные получают более высокий вес, а примеры, которые классифицированы правильно, теряют вес. [примечание 1] Таким образом, будущие слабые ученики больше сосредотачиваются на примерах, которые предыдущие слабые ученики неправильно классифицировали.
Существует множество алгоритмов усиления. Первоначальные, предложенные Робертом Шапиром ( рекурсивная формулировка большинства), [5] и Йоавом Фройндом (усиление большинством), [9] не были адаптивными и не могли в полной мере использовать слабых учеников. Затем Шапир и Фройнд разработали AdaBoost , адаптивный алгоритм усиления, который выиграл престижную премию Гёделя .
Только алгоритмы, которые являются доказуемыми алгоритмами усиления в вероятно приблизительно правильной формулировке обучения, могут быть точно названы алгоритмами усиления . Другие алгоритмы, которые по духу похожи [ необходимо разъяснение ] на алгоритмы усиления, иногда называются «алгоритмами усиления», хотя их также иногда неправильно называют алгоритмами усиления. [9]
Основное различие между многими алгоритмами повышения эффективности заключается в их методе взвешивания точек данных обучения и гипотез . AdaBoost очень популярен и исторически наиболее значим, поскольку это был первый алгоритм, который смог адаптироваться к слабым ученикам. Он часто является основой вводного освещения повышения эффективности в университетских курсах машинного обучения. [10] Существует множество более поздних алгоритмов, таких как LPBoost , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost и другие. Многие алгоритмы повышения эффективности вписываются в структуру AnyBoost, [9] которая показывает, что повышение эффективности выполняет градиентный спуск в функциональном пространстве с использованием выпуклой функции стоимости .
Учитывая изображения, содержащие различные известные объекты в мире, классификатор может быть обучен на их основе для автоматической классификации объектов в будущих изображениях. Простые классификаторы, построенные на основе некоторых особенностей изображения объекта, как правило, слабы в производительности категоризации. Использование методов усиления для категоризации объектов — это способ объединить слабые классификаторы особым образом, чтобы повысить общую способность категоризации. [ необходима цитата ]
Категоризация объектов — типичная задача компьютерного зрения , которая включает определение того, содержит ли изображение определенную категорию объектов. Идея тесно связана с распознаванием, идентификацией и обнаружением. Категоризация объектов на основе внешнего вида обычно включает извлечение признаков , обучение классификатора и применение классификатора к новым примерам. Существует много способов представления категории объектов, например, с помощью анализа формы , моделей мешка слов или локальных дескрипторов , таких как SIFT и т. д. Примерами контролируемых классификаторов являются наивные байесовские классификаторы , машины опорных векторов , смеси гауссианов и нейронные сети . Однако исследования [ which? ] показали, что категории объектов и их расположение на изображениях можно обнаружить и неконтролируемым образом . [11]
Распознавание категорий объектов на изображениях является сложной проблемой в компьютерном зрении , особенно когда количество категорий велико. Это связано с высокой внутриклассовой изменчивостью и необходимостью обобщения между вариациями объектов в пределах одной категории. Объекты в пределах одной категории могут выглядеть совершенно по-разному. Даже один и тот же объект может казаться непохожим при разной точке обзора, масштабе и освещении . Фоновый беспорядок и частичная окклюзия также усложняют распознавание. [12] Люди способны распознавать тысячи типов объектов, тогда как большинство существующих систем распознавания объектов обучены распознавать только несколько, [ количественно определять ], например, человеческие лица , автомобили , простые объекты и т. д. [13] [ требуется обновление? ] Исследования были очень активны в отношении работы с большим количеством категорий и обеспечения возможности постепенного добавления новых категорий, и хотя общая проблема остается нерешенной, было разработано несколько детекторов многокатегорийных объектов (для сотен или тысяч категорий [14] ). Одним из способов является совместное использование и усиление признаков .
AdaBoost может использоваться для обнаружения лиц в качестве примера бинарной категоризации . Две категории — это лица и фон. Общий алгоритм выглядит следующим образом:
После усиления классификатор, созданный на основе 200 признаков, может обеспечить 95%-ный уровень обнаружения при уровне ложных срабатываний . [15]
Другим применением бустинга для бинарной категоризации является система, которая обнаруживает пешеходов, используя шаблоны движения и внешнего вида. [16] Эта работа является первой, которая объединяет как информацию о движении, так и информацию о внешнем виде в качестве признаков для обнаружения идущего человека. Она использует аналогичный подход к фреймворку обнаружения объектов Виолы-Джонса .
По сравнению с бинарной категоризацией, многоклассовая категоризация ищет общие признаки, которые могут быть общими для всех категорий одновременно. Они оказываются более общими признаками, похожими на края . Во время обучения детекторы для каждой категории могут обучаться совместно. По сравнению с обучением по отдельности, она лучше обобщает , требует меньше обучающих данных и требует меньше признаков для достижения той же производительности.
Основной поток алгоритма аналогичен бинарному случаю. Отличие заключается в том, что мера ошибки совместного обучения должна быть определена заранее. Во время каждой итерации алгоритм выбирает классификатор одного признака (признаки, которые могут быть общими для большего количества категорий, должны поощряться). Это можно сделать путем преобразования многоклассовой классификации в бинарную (набор категорий против остальных), [17] или путем введения штрафной ошибки из категорий, которые не имеют признака классификатора. [18]
В статье «Обмен визуальными признаками для обнаружения многоклассовых и многовидовых объектов» А. Торральба и др. использовали GentleBoost для усиления и показали, что при ограниченном объеме обучающих данных обучение посредством обмена признаками дает гораздо лучшие результаты, чем отсутствие обмена при тех же раундах усиления. Кроме того, для заданного уровня производительности общее количество требуемых признаков (и, следовательно, стоимость времени выполнения классификатора) для детекторов совместного использования признаков, как наблюдается, масштабируется приблизительно логарифмически с числом классов, т. е. медленнее, чем линейный рост в случае отсутствия обмена. Аналогичные результаты показаны в статье «Инкрементальное обучение детекторов объектов с использованием визуального алфавита форм», однако авторы использовали AdaBoost для усиления.
Алгоритмы повышения могут быть основаны на выпуклых или невыпуклых алгоритмах оптимизации. Выпуклые алгоритмы, такие как AdaBoost и LogitBoost , могут быть «побеждены» случайным шумом, так что они не смогут изучить базовые и обучаемые комбинации слабых гипотез. [19] [20] Это ограничение было указано Long & Servedio в 2008 году. Однако к 2009 году несколько авторов продемонстрировали, что алгоритмы повышения, основанные на невыпуклой оптимизации, такие как BrownBoost , могут обучаться на зашумленных наборах данных и могут, в частности, изучать базовый классификатор набора данных Long–Servedio.
Дугообразование [усиление] более успешно, чем бэггинг в снижении дисперсии
Термин «усиление» относится к семейству алгоритмов, которые способны преобразовывать слабых учеников в сильных учеников.
Шапир (1990) доказал, что бустинг возможен. (Страница 823)
