Введение

Метод в машинном обучении

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

Алгоритмы усиления

Хотя усиление (boosting) не ограничено алгоритмически, большинство алгоритмов усиления состоят из итеративного обучения слабых классификаторов относительно некоторого распределения и добавления их к финальному сильному классификатору. При добавлении они взвешиваются в соответствии с точностью слабых классификаторов. После добавления слабого классификатора веса данных пересчитываются, что известно как "перевзвешивание" (reweighting). Неправильно классифицированные входные данные получают больший вес, а правильно классифицированные примеры – меньший. Некоторые алгоритмы классификации, основанные на усилении, фактически уменьшают вес примеров, которые неоднократно классифицируются неверно, например, Boost by Majority и BrownBoost. Таким образом, последующие слабые классификаторы сосредотачиваются в большей степени на примерах, которые предыдущие слабые классификаторы классифицировали неверно. Существует множество алгоритмов усиления. Первоначальные, предложенные Робертом Шапиром (в виде рекурсивной формулировки логического элемента большинства), не были адаптивными и не могли в полной мере использовать слабые классификаторы. Шапир и Фрёнд затем разработали AdaBoost – адаптивный алгоритм усиления, удостоенный престижной премии Гёделя. Только алгоритмы, которые являются доказанными алгоритмами усиления в рамках концепции вероятно приблизительно корректного обучения (PAC learning), могут быть точно названы алгоритмами усиления. Другие алгоритмы, схожие по принципу работы с алгоритмами усиления, иногда называют "алгоритмами использования" (leveraging algorithms), хотя их также иногда ошибочно называют алгоритмами усиления. Существует множество более современных алгоритмов, таких как LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost и другие. Многие алгоритмы усиления вписываются в структуру AnyBoost.

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

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

Усиление для многоклассной категоризации

По сравнению с бинарной категоризацией, многоклассовая категоризация ищет общие признаки, которые могут одновременно использоваться для разных категорий. Эти признаки оказываются более общими, похожими на граничные. В процессе обучения детекторы для каждой категории могут обучаться совместно. По сравнению с отдельным обучением, это обеспечивает лучшую обобщающую способность, требует меньше обучающих данных и меньшего количества признаков для достижения той же производительности. Основной ход алгоритма аналогичен бинарному случаю. Отличие состоит в том, что мера совместной ошибки обучения должна быть определена заранее. На каждой итерации алгоритм выбирает классификатор на основе одного признака (при этом приветствуются признаки, которые могут быть общими для нескольких категорий). Это можно сделать, преобразовав многоклассовую классификацию в бинарную (набор категорий против остальных), или путем введения штрафной ошибки от категорий, не обладающих признаком данного классификатора. В статье "Sharing visual features for multiclass and multiview object detection" А. Торралба и др. использовали GentleBoost для бустинга и показали, что при ограниченном объеме обучающих данных обучение с использованием общих признаков работает значительно лучше, чем без их использования, при одинаковом количестве раундов бустинга. Кроме того, для заданного уровня производительности общее количество необходимых признаков (и, следовательно, вычислительная стоимость классификатора) для детекторов, использующих общие признаки, масштабируется приблизительно логарифмически с количеством классов, то есть медленнее, чем линейный рост в случае, когда признаки не используются совместно. Аналогичные результаты представлены в статье "Incremental learning of object detectors using a visual shape alphabet", однако авторы использовали AdaBoost для бустинга.

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

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