Бустинг

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

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

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

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

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

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

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

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

Источник

comments powered by HyperComments

Посмотрите также

Японскую нейросеть научили «читать мысли»

Похоже на то, что компьютеры уже могут читать наши мысли. Автозаполнение Google, возможные друзья в Facebook и таргетированная реклама, которая всплывает у вас в браузере, иногда заставляют вас задуматься: как это работает? Мы медленно, но уверенно движемся в направлении компьютеров, читающих наши мысли, и новое исследование из Киото, Япония, стало недвусмысленным шагом в этом направлении. [...]