Бустинг

Материал из MachineLearning.

Версия 23:01, 9 января 2010

Данная статья является непроверенным учебным заданием. Студент: Участник:DmitryKonstantinov Преподаватель: Участник:Константин Воронцов Срок: 8 января 2010 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

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

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

Бустинг над решающими деревьями считается одним из наиболее эффективных методов с точки зрения качества классификации. Во многих экспериментах наблюдалось практически неограниченное уменьшение частоты ошибок на независимой тестовой выборке по мере наращивания композиции. Более того, качество на тестовой выборке часто продолжало улучшаться даже после достижения безошибочного распознавания всей обучающей выборки ^[1]. Это перевернуло существовавшие долгое время представления о том, что для повышения обобщающей способности необходимо ограничивать сложность алгоритмов. На примере бустинга стало понятно, что хорошим качеством могут обладать сколь угодно сложные композиции, если их правильно настраивать.

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

К сожалению, теоретические оценки обобщающей способности ^[1] дают лишь качественное обоснование феномену бустинга. Хотя они существенно точнее более общих оценок Вапника-Червоненкиса^[1], всё же они сильно завышены, и требуемая длина обучающей выборки оценивается величиной порядка . Более основательные эксперименты показали, что иногда бустинг всё же переобучается ^{[1] [1]} .

Варианты бустинга

Существует большое количество алгоритмов бустинга.

• AdaBoost
• GentleBoost
• LogitBoost
• BrownBoost
• LPBoost
• TotalBoost
• MadaBoost
• AnyBoost — бустинг как процесс градиентного спуска.

Ссылки

Материалы

• Машинное обучение (курс лекций, К.В.Воронцов)
• Подборка материалов по бустингу Роберта Шапира