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

Проблемы

Первая проблема, которую решает бустинг, — это компромисс между смещением и сложностью. Если вы не знаете, что это такое, позвольте мне кратко объяснить вам. С теоретической точки зрения парадигма минимизации эмпирического риска (ERM) представляет собой алгоритм для поиска лучшего предиктора вашего класса гипотез с использованием обучающего набора. Класс Hypothesis — это набор предикторов, которые вы принимаете во внимание, чтобы найти решение вашей задачи. Каждый предиктор hимеет свою эмпирическую ошибку Ls(h),то есть ошибку, которую вы делаете, используя обучающие данные, и тестовую ошибкуLd(h) это ошибка, которую вы делаете с невидимыми данными. Таким образом, парадигма ERM находит предиктор вашего набора гипотез, который минимизирует эмпирическую ошибку. Теперь, взяв предиктор ERM hs, мы можем разложить его тестовую ошибку на две части:

Первый член — это ошибка аппроксимации, и интуитивно понятно, что чем богаче наш класс гипотез, тем меньше эта ошибка. Но, с другой стороны, чем богаче наш класс гипотез, тем выше ошибка оценки, поэтому существует компромисс между сложностью и предвзятостью. Интуитивно, если у нас будет много предикторов в нашем классе гипотез, у нас будет большая вероятность найти лучший предиктор с помощью алгоритма ERM; мы найдем отличный предиктор, который идеально описывает данные обучающей выборки, следовательно, то, что мы делаем, — это переоценка нашей задачи, т.е. мы делаем переобучение. С другой стороны, если мы сильно ограничиваем наш класс гипотез, мы недооцениваем нашу проблему и делаем недообучение, так что это компромисс смещения.

Еще одна проблема, которую решает бустинг, — это вычислительная сложность поиска предиктора ERM. Поскольку найти лучший не так просто, форсирование начинается со слабого ученика и на каждом этапе пытается оптимизировать его, объединяя слабые предикторы, чтобы получить лучший.

АдаБуст

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

Простой алгоритм повышения — AdaBoost (сокращение от Adaptive Boosting). Алгоритм AdaBoost находит предиктор, представляющий собой линейную комбинацию множества простых предикторов. В частности, с помощью AdaBoost мы можем контролировать ошибку аппроксимации и ошибку оценки, изменяя только один параметр.

Математика AdaBoost

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

Были ли y истинными метками каждой точки экземпляра x. На следующем шаге AdaBoost присваивает вес h на итерации t следующим образом:

Как мы видим, вес обратно пропорционален функции потерь, эти веса используются для обновления распределения D, поэтому примеры в обучающем наборе, которые неправильно классифицированы на итерации t, получат более высокую вероятностную массу и примеры, которые правильно классифицированы, получат меньшую вероятностную массу, поэтому интуитивно слабый предсказатель сосредоточится только на неправильных примерах.

Реализация AdaBoost в Python

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

Помните, что мы хотим найти хороший компромисс между ошибкой аппроксимации и ошибкой оценки, и с помощью AdaBoost мы можем регулировать его только с одним параметром, скоростью обучения для правила обновления.

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

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

Но помните, что всегда можно сделать лучше

были разработаны и другие алгоритмы повышения, например алгоритм повышения градиента, но это уже другая история.

Итак, давайте попробуем использовать буст для решения ваших проблем!