Повышение (машинное обучение)

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

Концепция повышения основана на вопросе, поставленном Кернсом и Валиантом (1988, 1989): «Может ли группа слабых учеников создать одного сильного ученика?» Слабый обучающийся определяется как классификатор , который лишь незначительно коррелирует с истинной классификацией (он может маркировать примеры лучше, чем случайное угадывание). Напротив, сильный обучающийся — это классификатор, который сколь угодно хорошо коррелирует с истинной классификацией.

Роберт Шапир утвердительно ответил на вопрос, заданный Кирнсом и Валиантом, в статье, опубликованной в 1990 году. Это имело серьезные последствия для машинного обучения и статистики , в первую очередь приведя к развитию бустинга.

впервые была представлена, Когда проблема повышения гипотез она просто относилась к процессу превращения слабого ученика в сильного ученика. «Неофициально, проблема [подтверждения гипотезы] заключается в том, предполагает ли эффективный алгоритм обучения […], который выводит гипотезу, производительность которой лишь немного лучше, чем случайное предположение [т.е. слабый обучающийся], подразумевает ли существование эффективного алгоритма, который выводит гипотезу произвольного точность [т.е. сильная обучаемость]». Алгоритмы, обеспечивающие усиление гипотез, быстро стали известны как «повышение гипотезы». Дуга Фрейнда и Шапире (Адаптивная [ат]ивная передискретизация и объединение), как общий метод, является более или менее синонимом повышения.

Алгоритмы повышения

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

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

Существует множество алгоритмов повышения. Оригинальные, предложенные Робертом Шапиром ( рекурсивная формулировка мажоритарного вентиля), и Йоав Фройнд (поддержка большинством голосов), не были адаптивными и не могли в полной мере использовать преимущества слабых учащихся. Затем Шапир и Фройнд разработали AdaBoost , алгоритм адаптивного повышения, получивший престижную премию Гёделя .

Только алгоритмы, которые являются доказуемыми алгоритмами повышения в вероятно приблизительно правильной формулировке обучения, могут быть точно названы алгоритмами повышения . Другие алгоритмы, близкие по духу Алгоритмы повышения иногда называют «алгоритмами использования», хотя их также иногда неправильно называют алгоритмами повышения.

Основным отличием многих алгоритмов повышения является их метод взвешивания обучения точек данных и гипотез . AdaBoost очень популярен и наиболее значим в истории, поскольку это был первый алгоритм, который мог адаптироваться к слабым ученикам. Это часто является основой вводного курса повышения квалификации на университетских курсах машинного обучения. Существует множество более свежих алгоритмов, таких как LPBoost , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost и другие. Многие алгоритмы повышения вписываются в структуру AnyBoost. который показывает, что повышение выполняет градиентный спуск в функциональном пространстве с использованием выпуклой функции стоимости .

Категоризация объектов в компьютерном зрении

Основная статья: Категоризация объектов при поиске изображений

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

Проблема категоризации объектов

Категоризация объектов — типичная задача компьютерного зрения , которая включает в себя определение того, содержит ли изображение определенную категорию объектов. Эта идея тесно связана с распознаванием, идентификацией и обнаружением. Категоризация объектов на основе внешнего вида обычно включает признаков , изучение классификатора извлечение и применение классификатора к новым примерам. Существует множество способов представления категории объектов, например, с помощью анализа формы , моделей «мешков слов» или локальных дескрипторов, таких как SIFT и т. д. Примерами контролируемых классификаторов являются наивные классификаторы Байеса , машины опорных векторов , смеси гауссиан и нейронные сети. . Однако исследования показал, что категории объектов и их расположение на изображениях могут быть обнаружены без присмотра . также

Статус-кво для категоризации объектов

Распознавание категорий объектов на изображениях является сложной проблемой компьютерного зрения , особенно когда количество категорий велико. Это связано с высокой внутриклассовой изменчивостью и необходимостью обобщения вариаций объектов внутри одной категории. Объекты одной категории могут выглядеть совершенно по-разному. Даже один и тот же объект может выглядеть непохожим под разной точкой зрения, масштабом и освещением . Беспорядок на заднем плане и частичная окклюзия также усложняют распознавание. Люди способны распознавать тысячи типов объектов, тогда как большинство существующих систем распознавания объектов обучены распознавать лишь некоторые из них. например, человеческие лица , автомобили , простые предметы и т. д. Исследования были очень активными, направленными на работу с большим количеством категорий и обеспечение возможности постепенного добавления новых категорий, и, хотя общая проблема остается нерешенной, несколько детекторов объектов с несколькими категориями (до сотен или тысяч категорий) ) были разработаны. Одним из способов является совместное использование функций и их повышение.

Повышение бинарной категоризации

AdaBoost можно использовать для распознавания лиц в качестве примера двоичной категоризации . Две категории — это лица и фон. Общий алгоритм следующий:

1. Сформируйте большой набор простых функций
2. Инициализируйте веса для обучающих изображений
3. Для Т-раундов
   1. Нормализовать веса
   2. Для доступных функций из набора обучите классификатор, используя одну функцию, и оцените ошибку обучения.
   3. Выберите классификатор с наименьшей ошибкой
   4. Обновите веса обучающих изображений: увеличьте, если этот классификатор классифицирует их неправильно, уменьшите, если правильно.
4. Сформируйте окончательный сильный классификатор как линейную комбинацию T-классификаторов (коэффициент больше, если ошибка обучения невелика)

После повышения классификатор, построенный из 200 признаков, может обеспечить уровень обнаружения 95 % при $10^{-5}$ ложноположительный уровень .

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

Повышение категоризации по нескольким классам

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

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

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

Выпуклые и невыпуклые алгоритмы повышения

Алгоритмы повышения могут быть основаны на алгоритмах выпуклой или невыпуклой оптимизации. Выпуклые алгоритмы, такие как AdaBoost и LogitBoost , могут быть «побеждены» случайным шумом, так что они не смогут изучить базовые и обучаемые комбинации слабых гипотез. На это ограничение указали Long & Servedio в 2008 году. Однако к 2009 году несколько авторов продемонстрировали, что алгоритмы повышения, основанные на невыпуклой оптимизации, такие как BrownBoost , могут учиться на зашумленных наборах данных и, в частности, могут изучать базовый классификатор Long- Набор данных Серведио.

См. также

• Случайный лес
• Альтернативное дерево решений
• Бутстрап-агрегирование (пакетирование)
• Каскадный
• Совместное усиление
• Логистическая регрессия
• Методы максимальной энтропии
• Повышение градиента
• Классификаторы маржи
• Перекрестная проверка
• Список наборов данных для исследований в области машинного обучения

Реализации

• scikit-learn — библиотека машинного обучения с открытым исходным кодом для Python.
• Orange — бесплатный пакет программного обеспечения для интеллектуального анализа данных, модуль Orange.ensemble.
• Weka — это набор инструментов машинного обучения, который предлагает различные реализации алгоритмов повышения, таких как AdaBoost и LogitBoost.
• R Пакет GBM (Обобщенные модели регрессии с усилением) реализует расширения алгоритма AdaBoost Фрейнда и Шапире и машины повышения градиента Фридмана.
• jboost ; AdaBoost, LogitBoost, RobustBoost, Boostexter и альтернативные деревья решений
• Пакет R adabag : применяет мультикласс AdaBoost.M1, AdaBoost-SAMME и пакетирование.
• Пакет R xgboost : реализация повышения градиента для линейных и древовидных моделей.

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

• Фройнд, Йоав; Шапире, Роберт Э. (1997). «Обобщение онлайн-обучения с точки зрения принятия решений и применение к повышению» (PDF) . Журнал компьютерных и системных наук . 55 (1): 119–139. дои : 10.1006/jcss.1997.1504 .
• Шапире, Роберт Э. (1990). «Сила слабой обучаемости» . Машинное обучение . 5 (2): 197–227. дои : 10.1007/BF00116037 . S2CID   6207294 .
• Шапире, Роберт Э.; Певец Йорам (1999). «Улучшенные алгоритмы повышения с использованием предикторов с рейтингом достоверности» . Машинное обучение . 37 (3): 297–336. дои : 10.1023/А:1007614523901 . S2CID   2329907 .
• Чжоу, Чжихуа (2008). «Политическое объяснение алгоритма повышения» (PDF) . В: Материалы 21-й ежегодной конференции по теории обучения (COLT'08) : 479–490.
• Чжоу, Чжихуа (2013). «О сомнениях в маржинальном объяснении повышения» (PDF) . Искусственный интеллект . 203 : 1–18. arXiv : 1009.3613 . дои : 10.1016/j.artint.2013.07.002 . S2CID   2828847 .

Внешние ссылки

• Роберт Э. Шапир (2003); Усиливающий подход к машинному обучению: обзор , Семинар MSRI (Научно-исследовательский институт математических наук) по нелинейному оцениванию и классификации
• Чжоу Чжи-Хуа (2014). Продление 25 лет. Архивировано 20 августа 2016 г. в Wayback Machine , основной доклад CCL 2014.