Бустинг

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

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

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

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

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

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

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

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

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

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

Основная статья: Классификация признаков по изображениям из поисковиков

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация

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

Литература

• Leo Breiman. Bias, Variance, And Arcing Classifiers // Technical Report. — 1996. Архивировано 19 января 2015 года. Выдержка: «Arcing [Boosting] is more successful than bagging in variance reduction»
• Zhou Zhi-Hua. Ensemble Methods: Foundations and Algorithms. — Chapman and Hall/CRC, 2012. — ISBN 978-1439830031. Выдержка: «The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners»
• Michael Kearns. Thoughts on Hypothesis Boosting. — 1988. — (Unpublished manuscript (Machine Learning class project)).
• Leo Breiman. Arcing Classifier (with Discussion and a Rejoinder by the Author) // Annals of Statistics. — 1998. — Т. 26, № 3. — С. 801—849:.
• Michael Kearns, Leslie Valiant. Crytographic limitations on learning Boolean formulae and finite automata // Symposium on Theory of computing. — ACM, 1989. — Т. 21. — doi:10.1145/73007.73049.
• Michael Kearns, Leslie Valiant. Learning Boolean Formulae or Finite Automata is as Hard as Factoring. Technical Report TR-14-88. — Harvard University Aiken Computation Laboratory, 1988.
  • Статья была позднее перепечатана в журнале «Journal of the Association for Computing Machinery», 41(1):67-95, January 1994
• Robert E. Schapire. The Strength of Weak Learnability // Machine Learning. — Boston, MA: Kluwer Academic Publishers, 1990. — Т. 5, вып. 2. — doi:10.1007/bf00116037. Архивировано 10 октября 2012 года.
• Leo Breiman. Arcing classifier (with discussion and a rejoinder by the author) // Ann. Stat.. — 1998. — Т. 26, вып. 3. — doi:10.1214/aos/1024691079. Выдержка: «Schapire (1990) proved that boosting is possible» (Page 823)
• Yoav Freund, Robert E. Schapire. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. — 1997. — Т. 55, вып. 1.
• Andreas Opelt, Axel Pinz, Michael Fussenegger, Peter Auer. Generic Object Recognition with Boosting // IEEE Trans Pattern Anal Mach Intell. — 2006. — Т. 28. — С. 416—31. — ISSN 0162-8828.
• Marszalek M., Schmid C. Semantic Hierarchies for Visual Object Recognition. — 2007.
• Viola P., Jones M., Snow D. Detecting Pedestrians Using Patterns of Motion and Appearance // ICCV. — 2003.
• Torralba A., Murphy K. P., Freeman W. T. Sharing visual features for multiclass and multiview object detection // IEEE Transactions on PAMI. — 2007. — Т. 29, вып. 5. — doi:10.1109/TPAMI.2007.1055.
• Andreas Opelt, Axel Pinz, Andrew Zisserma. Incremental learning of object detectors using a visual shape alphabet // CVPR. — 2006. — С. 3—10.
• Long P., Servedio R. Random classification noise defeats all convex potential boosters // 25th International Conference on Machine Learning (ICML). — 2008. — С. 608—615.
• Philip M. Long, Rocco A. Servedio. Random classification noise defeats all convex potential boosters // Machine Learning. — Springer US, 2010. — Март (т. 78, вып. 3). — С. 287–304. — doi:10.1007/s10994-009-5165-z.
• Llew Mason, Jonathan Baxter, Peter Bartlett, Marcus Frean. Boosting Algorithms as Gradient Descent // Advances in Neural Information Processing Systems / S. A. Solla, T. K. Leen, K.-R. Muller. — MIT Press, 2000. — Т. 12.
• Josef Sivic, Bryan C. Russell, Alexei A. Efros, Andrew Zisserman, William T. Freeman. Discovering objects and their location in images // ICCV 2005. Tenth IEEE International Conference on Computer Vision. — IEEE, 2005. — Т. 1.
• Paul Viola, Michael Jeffrey Jones. Robust Real-time Object Detection // International Journal of Computer Vision. — 2001. — Т. 57, вып. 2.
• Yoav Freund and Robert E. Schapire (1997); A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting Архивная копия от 12 октября 2008 на Wayback Machine, Journal of Computer and System Sciences, 55(1):119-139
• Robert E. Schapire and Yoram Singer (1999); Improved Boosting Algorithms Using Confidence-Rated Predictors Архивная копия от 20 августа 2008 на Wayback Machine, Machine Learning, 37(3):297-336

Ссылки

• Robert E. Schapire (2003); The Boosting Approach to Machine Learning: An Overview Архивная копия от 20 сентября 2020 на Wayback Machine, MSRI (Mathematical Sciences Research Institute) Workshop on Nonlinear Estimation and Classification
• Zhou Zhi-Hua (2014) Boosting 25 years Архивная копия от 20 августа 2016 на Wayback Machine, CCL 2014 Keynote.
• Zhihua Zhou. On the margin explanation of boosting algorithm. // Proceedings of the 21st Annual Conference on Learning Theory (COLT'08). — 2008. — С. 479–490.
• Zhihua Zhou. On the doubt about margin explanation of boosting. // Artificial Intelligence. — 2013. — Т. 203. — С. 1–18. — doi:10.1016/j.artint.2013.07.002. — arXiv:1009.3613.
• http://www.machinelearning.ru/wiki/index.php?title=%D0%91%D1%83%D1%81%D1%82%D0%B8%D0%BD%D0%B3 Архивная копия от 24 февраля 2020 на Wayback Machine