WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте
Машинное обучение и
data mining

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

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

Впервые появившись, гипотеза о бустинге относилась к процессу настройки алгоритма слабого обучения для получения строгого обучения. «Неформально, спрашивается, вытекает ли из существования эффективного алгоритма обучения, выходом которого служит гипотеза, эффективность которой лишь слегка лучше случайного гадания (т.е. слабое обучение), существование эффективного алгоритма, который даёт гипотезу произвольной точности (т.е. сильное обучение)[3]. Алгоритмы, которые получают быстро такую гипотезу, становятся известны просто как «бустинг». Алгоритм «arcing» Фройнда и Шапире (Adaptive Resampling and Combining)[7], как общая техника, является более-менее синонимом бустингу[8]

Алгоритмы бустинга

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

Есть много алгоритмов бустинга. Исходные алгоритмы, предложенные Робертом Шапире (рекурсивное доминирование, англ. recursive majority gate formulation) [5] и Йоавом Фройндом (бустинг по доминированию)[9], не были адаптивными[en] и не могли дать полного преимущества слабых обучений. Шапире и Фройнд затем разработали AdaBoost (Adaptive Boosting) – адаптивный алгоритм бустинга, который выиграл престижную премию Гёделя.

Только алгоритмы, для которых можно доказать, что они являются алгоритмами бустинга в формулировке приближённо правильного обучения[en], могут быть точно названы алгоритмами бустинга. Другие алгоритмы, близкие по духу алгоритмам бустинга, иногда называются «алгоритмами максимального использования» (англ. leveraging algorythms), хотя они иногда также неверно называются алгоритмами бустинга[9].

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

Классификация признаков в компьютерном зрении

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

Задача классификации объектов

Классификация признаков[en] является типичной задачей компьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, идентификацией и обнаружением. Классификация по обнаружению объекта обычно содержит выделение признаков, обучение классификатора и применение классификатора к новым данным. Есть много способов представления категории объектов, например по анализу формы[en], с помощью модели «мешок слов»[en], с помощью локальных описателей, таких как SIFT[en], и так далее. Примерами классификаторов с учителем служат наивные байесовские классификаторы, методы опорных векторов, смесь гауссиан[en] и нейронные сети. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя[11].

Статус кво для классификации объектов

Распознавание категорий объектов в изображениях является сложной задачей в компьютерном зрении, особенно если число категорий велико. Это является следствием высокой внутренней изменчивости классов и необходимости обобщения различных понятий внутри класса. Объекты в одной категории могут выглядеть совершенно различными. Даже один и тот же предмет может выглядеть непохожим с различных точек обзора, при другом мастшабе[en] или освещении[en]. Шум заднего плана и частичные наложения также добавляют сложности в распознавание[12]. Люди способны распознавать тысячи типов объектов, в то время как большинство существующих систем распознавания объектов тренируются для распознавания лишь нескольких, например человеческих лиц, автомобилей, простых объектов и т.д.[13]. Исследования по увеличению числа категорий и возможности добавления новых категорий ведутся активно и, хотя общая проблема пока не решена, разработаны детекторы большого числа категорий (до сотен и тысяч [14]). Достигается это, в частности, с помощью совместного использования признаков[en] и бустинга.

Бустинг для двоичной классификации

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

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

После бустинга классификатор, построенный из 200 признаков, может достигать 95 % успешных распознаний при ошибок положительного распознавания[15].

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

Бустинг мультиклассовой классификации

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

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

В статье «Sharing visual features for multiclass and multiview object detection» (Совместное использование визуальных признаков для мультиклассового обнаружения объектов в нескольких проекциях), А. Торральба с соавторами использовали GentleBoost для бустинга и показали, что, если тренировочные данные ограничены, обучение с помощью совместно используемых признаков делает работу много лучше, чем без совместного использования. Также для заданного уровня производительности общее число признаков, требующихся (а потому и время работы классификатора) для обнаружения совместного использования признаков, растёт примерно логарифмически от числа классов, т.е. медленнее, чем линейно[en], что наблюдается в случае отсутствия совместного использования. Похожие результаты показаны в статье «Инкременальное обучение обнаружения объектов, используя алфавит визуальных образов», впрочем, для бустинга авторы использовали AdaBoost.

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

Алгоритмы бустинга могут основываться на выпуклых[en] или невыпуклых алгоритмах оптимизации. Выпуклые алгоритмы, такие как AdaBoost и LogitBoost[en], могут «потерпеть крушение» из-за случайного шума, так как не могут обучить базовым и поддающимся научению комбинациям слабых гипотез[19][20]. На это ограничение указали Лонг и Серведо в 2008. Однако в 2009 несколько авторов продемонстрировали, что алгоритмы бустинга, основанные на невыпуклой оптимизации, такие как BrownBoost, могут быть обучены из данных с шумами и лежащий в основе классификатор Лонг–Серведио для набора данных может быть обучен.

См. также

Реализация

  • Scikit-learn[en], библиотека машинного обучения с открытым кодом для языка Python
  • Orange[en], a свободно распространяемый программный комплекс для анализа данных, модуль Orange.ensemble
  • Weka — это набор средств для машинного обучения, содержащий ряд реализаций алгоритмов бустинга, таких как AdaBoost и LogitBoost
  • Пакет GBM (Generalized Boosted Regression Models = Обобщённые Модели Бустинга Регрессии) на языке R реализует расширение алгоритма Фройнда и Шапире AdaBoost и градиентного бустинга Фридмана.
  • jboost; AdaBoost, LogitBoost, RobustBoost, Boostexter и чередующиеся решающие деревья[en]
  • Пакет adabag на языке R: Применяет мультиклассовые алгоритмы AdaBoost.M1, AdaBoost-SAMME и Bagging
  • Пакет xgboost на языке R: Реализация градиентного бустинга для линейных основанных на деревьях моделей.

Примечания

  1. ↑ . Некоторые основанные на бустинге алгоритмы классификации на самом деле уменьшают веса повторно неверно классифицированных экземпляпров. Например, бустинг по доминированию (англ. boost by majority) и BrownBoost
  1. ↑ Breiman, 1996.
  2. ↑ Zhi-Hua, 2012, с. 23.
  3. 1 2 Kearns, 1988.
  4. ↑ Kearns, Valiant, 1989, с. 433–444.
  5. 1 2 Schapire, 1990, с. 197–227.
  6. ↑ Breiman, 1998, с. 801–849.
  7. ↑ Freund, Schapire, 1997, с. 119-139.
  8. ↑ Лео Брайман (Breiman 1998) пишет: «Понятие слабого обучения ввели Кернс и Валиант (Kearns, Valiant, 1988, Kearns, Valiant, 1989), которые поставили вопрос, эквивалентны ли слабое и сильное обучение. Вопрос был назван задачей бустинга, поскольку решение должно усилить слабую точность слабого обучения до высокой точности сильного обучения. Шапире (1990) доказал, что бустинг возможен. Алгоритм бустинга является методом, который берёт слабый метод обучения и преобразует его в сильный метод. Фройнд и Шапире (1997) доказали, что алгоритм, подобный arc-fs, является бустингом.»
  9. 1 2 3 Mason, Baxter, Bartlett, Frean, 2000, с. 512-518.
  10. ↑ Emer, Eric Boosting (AdaBoost algorithm). MIT.
  11. ↑ Sivic, Russell, Efros, Zisserman, Freeman, 2005, с. 370-377.
  12. ↑ Opelt, Pinz, Fussenegger, Auer, 2006, с. 416-431.
  13. ↑ Marszalek, Schmid, 2007.
  14. ↑ Large Scale Visual Recognition Challenge (December 2017).
  15. ↑ Viola, Jones, 2001.
  16. ↑ Viola, Jones, Snow, 2003.
  17. ↑ Torralba, Murphy, Freeman, 2007, с. 854-869.
  18. ↑ Opelt, Pinz, Zisserma, 2006, с. 3-10.
  19. ↑ Long, Servedio, 2008, с. 608-615.
  20. ↑ Long, Servedio, 2010, с. 287–304.

Литература

Литература для дальнейшего чтения

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии