Бустинг
Материал из MachineLearning.
(Новая: {{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}}) |
|||
| (7 промежуточных версий не показаны.) | |||
| Строка 1: | Строка 1: | ||
| - | + | Бустинг (англ. boosting — улучшение) — это процедура последовательного построения [[Композиция алгоритмов|композиции алгоритмов]] [[Машинное обучение|машинного обучения]], когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения [[Композиция алгоритмов|композиции алгоритмов]]. Изначально понятие бустинга возникло в работах по [[Теория Валианта|вероятно почти корректному обучению]] в связи с вопросом: возможно ли, имея множество плохих (незначительно отличающихся от случайных) алгоритмов обучения, получить хороший<ref>Michael Kearns. Thoughts on hypothesis boosting. Unpublished manuscript. 1988</ref>. | |
| + | |||
| + | В течение последних 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]] | ||
| + | * [[AnyBoost]] — бустинг как процесс градиентного спуска. | ||
| + | * [[GentleBoost]] | ||
| + | * [[LogitBoost]] | ||
| + | * [[BrownBoost]] | ||
| + | * [[LPBoost]] | ||
| + | * [[TotalBoost]] | ||
| + | * [[MadaBoost]] | ||
| + | |||
| + | == Ссылки == | ||
| + | <references/> | ||
| + | |||
| + | == См. также == | ||
| + | * [[Машинное обучение (курс лекций, К.В.Воронцов)]] | ||
| + | * [http://www.cs.princeton.edu/~schapire/boost.html Подборка материалов по бустингу Роберта Шапира] | ||
| + | |||
| + | [[Категория:Методы голосования]] | ||
Текущая версия
Бустинг (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов. Изначально понятие бустинга возникло в работах по вероятно почти корректному обучению в связи с вопросом: возможно ли, имея множество плохих (незначительно отличающихся от случайных) алгоритмов обучения, получить хороший[1].
В течение последних 10 лет бустинг остаётся одним из наиболее популярных методов машинного обучения, наряду с нейронными сетями и машинами опорных векторов. Основные причины — простота, универсальность, гибкость (возможность построения различных модификаций), и, главное, высокая обобщающая способность.
Бустинг над решающими деревьями считается одним из наиболее эффективных методов с точки зрения качества классификации. Во многих экспериментах наблюдалось практически неограниченное уменьшение частоты ошибок на независимой тестовой выборке по мере наращивания композиции. Более того, качество на тестовой выборке часто продолжало улучшаться даже после достижения безошибочного распознавания всей обучающей выборки [1]. Это перевернуло существовавшие долгое время представления о том, что для повышения обобщающей способности необходимо ограничивать сложность алгоритмов. На примере бустинга стало понятно, что хорошим качеством могут обладать сколь угодно сложные композиции, если их правильно настраивать.
Впоследствии феномен бустинга получил теоретическое обоснование. Оказалось, что взвешенное голосование не увеличивает эффективную сложность алгоритма, а лишь сглаживает ответы базовых алгоритмов. Количественные оценки обобщающей способности бустинга формулируются в терминах отступа [1]. Эффективность бустинга объясняется тем, что по мере добавления базовых алгоритмов увеличиваются отступы обучающих объектов. Причём бустинг продолжает раздвигать классы даже после достижения безошибочной классификации обучающей выборки.
К сожалению, теоретические оценки обобщающей способности [1] дают лишь качественное обоснование феномену бустинга. Хотя они существенно точнее более общих оценок Вапника-Червоненкиса[1], всё же они сильно завышены, и требуемая длина обучающей выборки оценивается величиной порядка . Более основательные эксперименты показали, что иногда бустинг всё же переобучается [1] [1].
Варианты бустинга
Существует большое количество алгоритмов бустинга.
- AdaBoost
- AnyBoost — бустинг как процесс градиентного спуска.
- GentleBoost
- LogitBoost
- BrownBoost
- LPBoost
- TotalBoost
- MadaBoost
Ссылки
