Бустинг

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}})
(дополнение, ссылки)
Строка 1: Строка 1:
{{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}}
{{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}}
 +
Бустинг (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов [[Машинное обучение|машинного обучения]], когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов и является частным случаем алгоритмической композиции.
 +
 +
В течение последних 10 лет бустинг остаётся одним из наиболее популярных методов машинного обучения, наряду с нейронными сетями и машинами опорных векторов. Основные причины простота, универсальность, гибкость (возможность построения различных модификаций), и, главное, высокая обобщающая способность.
 +
 +
Бустинг над [[Решающее дерево | решающими деревьями]] считается одним из наиболее эффективных методов с точки зрения качества [[Классификация|классификации]]. Во многих экспериментах наблюдалось практически неограниченное уменьшение частоты ошибок на независимой тестовой [[Выборка|выборке]] по мере наращивания композиции. Более того, качество на тестовой выборке часто продолжало улучшаться даже после достижения безошибочного распознавания всей обучающей выборки <ref>Freund Y., Schapire R. E. Experiments with a new boosting algorithm //International Conference on Machine Learning, — 1996. — Pp. 148–156.</ref>. Это перевернуло существовавшие долгое время представления о том, что для повышения обобщающей способности необходимо ограничивать сложность алгоритмов. На примере бустинга стало понятно, что хорошим качеством могут обладать сколь угодно сложные композиции, если их правильно настраивать.
 +
 +
Впоследствии феномен бустинга получил теоретическое обоснование. Оказалось, что взвешенное голосование не увеличивает эффективную сложность алгоритма, а лишь сглаживает ответы базовых алгоритмов. Количественные оценки обобщающей способности бустинга формулируются в терминах [[Отступ | отступа]] <ref name="margin">Boosting the margin: a new explanation for the effectiveness of voting methods / R. E. Schapire, Y. Freund, W. S. Lee, P. Bartlett // Annals of Statistics, — 1998.
 +
Vol. 26, no. 5. — Pp. 1651–1686.</ref>. Эффективность бустинга объясняется тем, что по мере добавления базовых алгоритмов увеличиваются отступы обучающих объектов. Причём бустинг продолжает раздвигать классы даже после достижения безошибочной классификации обучающей выборки. Впервые идея
 +
 +
К сожалению, теоретические оценки обобщающей способности <ref name="margin"/> дают лишь качественное обоснование феномену бустинга. Хотя они существенно точнее более общих [[Теория Вапника-Червоненкиса|оценок Вапника-Червоненкиса]]<ref> Vapnik V. Statistical Learning Theory. Wiley, New York, — 1998.
 +
[</ref>, всё же они сильно завышены, и требуемая длина обучающей выборки оценивается величиной порядка <tex>10^4 \dots 10^6</tex>. Более основательные эксперименты показали, что иногда бустинг всё же [[Переобучение|переобучается]] <ref>Ratsch G., Onoda T., Muller K. R. An improvement of adaboost to avoid verfitting // Advances in Neutral Information Processing Systems, Kitakyushu, Japan. — 1998. — Pp. 506–509.</ref> <ref>Ratsch G., Onoda T., Muller K.-R. Soft margins for AdaBoost // Machine Learning. — 2001. Vol. 42, no. 3. — Pp. 287–320.</ref> .
 +
 +
== Варианты бустинга ==
 +
Существует большое количество алгоритмов бустинга.
 +
* [[Алгоритм AdaBoost | AdaBoost]]
 +
* [[GentleBoost]]
 +
* [[LogitBoost]]
 +
* [[BrownBoost]]
 +
* [[LPBoost]]
 +
* [[TotalBoost]]
 +
* [[MadaBoost]]
 +
* [[AnyBoost]] — бустинг как процесс градиентного спуска.
 +
== Ссылки ==
 +
<references/>
 +
=== Дополнительно ===
 +
[http://www.cs.princeton.edu/~schapire/boost.html Подборка материалов по бустингу]

Версия 21:18, 4 января 2010

Данная статья является непроверенным учебным заданием.
Студент: Участник:DmitryKonstantinov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


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

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

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

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

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

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

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

Ссылки

Дополнительно

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

Личные инструменты