Что такое бустинг в машинном обучении
Бустинг — ещё один способ машинного обучения
Как с помощью слабых алгоритмов сделать сильный.
Мы уже говорили об общем принципе работы нейросетей для машинного обучения. Разберём другой — бустинг. Кто кого бустит и зачем?
Ноги бустинга растут из вопроса «можно ли с помощью нескольких слабых алгоритмов сделать один сильный?». Оказывается, что да. В этом и есть суть метода: строим серию не особо точных алгоритмов и обучаем их на ошибках друг друга.
Дерево решений
Чтобы понять бустинг, нужно сначала понять дерево решений. Вот это — очень простое дерево:
Сейчас это дерево решений, но может быть деревом предсказаний. Представьте, что в заголовке дерева написано «Выйдет ли Юзернейм гулять?» — и вы получите машину предсказаний, которая на основе данных о Юзернейме и погоде будет строить точные предсказания о Юзернейме — при условии, что мы задаём правильные вопросы.
Машина предсказания
Теперь пример сложнее. Допустим, у нас есть данные по миллиону музыкальных клипов на Ютубе. По каждому есть 100 критериев, например:
Также у нас есть данные о том, набрал ли клип больше миллиона просмотров. Мы хотим научиться предсказывать этот критерий — назовём его популярностью. То есть мы хотим получить некий алгоритм, которому на вход подаёшь 100 критериев клипа в формате да/нет, а на выходе он тебе говорит: «Этому клипу суждено стать популярным».
Миллион клипов, сто критериев — обучающая выборка для алгоритма
Первая проблема
Если мы захотим построить дерево предсказаний для этой задачи, мы столкнёмся с проблемой: мы не знаем, какие критерии ставить в начало, а какие в конец, какие запихивать в какие ветки, а какие вообще не нужны и потому не влияют.
Первый шаг решения
Чтобы построить дерево для такой задачи, мы должны будем сначала посчитать, насколько каждый критерий связан с желаемым результатом:
Среди миллиона клипов в обучающей выборке 300 000 выпустили известные лейблы. 120 000 из них стали популярны. Этот критерий лучше других предсказывает популярность
В итоге мы видим, что самая сильная связь с итоговой популярностью у критерия «Выпустил ли клип популярный лейбл». Получается, если клип выпустил лейбл, это влияет на успех сильнее, чем бочка или автотюн. Этот критерий встаёт на вершину дерева.
Затем мы смотрим, какой критерий поставить следующим. Берём те 300 000 клипов, которые выпустили лейблы, и прогоняем их по остальным критериям. Ищем тот, который даёт самую высокую итоговую точность предсказания.
Среди 300 000 клипов, которые выпустили лейблы, 250 000 клипов идут дольше 3 минут и 90 000 из них набрали больше миллиона просмотров. Этот критерий лучше других предсказывает популярность клипов лейбла
Ставим его на второе место.
То же самое делаем для другой ветки. И так строим последовательность из остальных критериев. На практике вручную этим не занимаются: есть специальные алгоритмы, которые делают это автоматически.
Оп, у нас появилось дерево решений:
Большинство клипов не взлетит, но какие-то станут популярными
Случайный лес
Есть проблема: построенное таким образом дерево очень сложное и, вероятно, не очень точное. Попробуем сделать не одно огромное дерево, а несколько небольших.
Возьмём случайную выборку из наших исходных данных. Не миллион клипов, а 10 000. К ним — случайный набор критериев, не все 100, а 5:
И построим дерево попроще:
Было много уровней, стало меньше
Так построим ещё несколько деревьев, каждое — на своём наборе данных и своём наборе критериев:
Лес алгоритмов
У нас появился случайный лес. Случайный — потому что мы каждый раз брали рандомный набор данных и критериев. Лес — потому что много деревьев.
Теперь запустим клип, которого не было в обучающей выборке. Каждое дерево выдаст свой вердикт, станет ли он популярным — «да» или «нет». Как голосование на выборах. Выбираем вариант, который получит больше всего голосов.
Три за, один против — клип ждёт успех. Наверное
Неслучайный лес — бустинг
Теперь построим похожий лес, но набор данных будет неслучайным. Первое дерево мы построим так же, как и раньше, на случайных данных и случайных критериях. А потом прогоним через это дерево контрольную выборку: другие клипы, по которым у нас есть все данные, но которые не участвуют в обучении. Посмотрим, где дерево ошиблось:
Первое дерево может давать много ошибок
Теперь делаем следующее дерево. Обратим внимание на места, где первое дерево ошиблось. Дадим этим ошибкам больший вес при подборе данных и критериев для обучения. Задача — сделать дерево, которое исправит ошибки предыдущего.
Учим дерево исправлять ошибки предшественника
Но второе дерево наделает своих ошибок. Делаем третье, которое их исправит. Потом четвёртое. Потом пятое. Вы поняли принцип.
Делаем такие деревья, пока не достигнем желаемой точности или пока точность не начнёт падать из-за переобучения. Получается, у нас много деревьев, каждое из которых не очень сильное. Но вместе они складываются в лес, который даёт хорошую точность. Бустинг!
И где это используют?
Бустинг часто используют в задачах, когда нейронные сети не очень подходят.
Нейросети хорошо справляются с однородными данными, например изображениями или голосом. А вот если данные разного характера и с разной структурой, то бустинг справляется лучше. Например, чтобы предсказать погоду, надо учесть температуру и влажность, данные с радаров, наблюдения пользователей и другие параметры. Бустинг с этим справляется отлично.
Вот что про бустинг рассказывает Роман Халкечев, руководитель отдела аналитики в Яндекс.Еде:
«В Яндексе повсеместно используем библиотеку CatBoost. Это внутренняя разработка, которую в 2017 году выложили в open source. Она помогает решать много задач, например, ранжирование в Поиске, предсказание в Погоде, рекомендации в Музыке.
Когда я работал в Такси, с помощью CatBoost мы решали такую задачу: когда пользователь только заказывает машину, в округе может не быть свободных водителей. Мы в таком случае выводим сообщение: «Нет свободных машин». Но при этом уже через несколько секунд может появиться доступный водитель.
С одной стороны, мы не хотим терять заказ. С другой — не хотим разочаровывать пользователя, который начал поиск такси, но так и не смог уехать, потому что никогда не нашлось.
С помощью CatBoost мы решили научиться предсказывать, сможем ли найти для конкретного пользователя машину после вызова. Это задача классификации — нужно отнести пользователя к одной из двух групп: «Сможем найти машину» или «Не сможем найти машину». Мы ориентировались на метрики precision и recall. Они позволяют найти баланс надёжности: не наобещать лишнего, но и не потерять заказы.
В итоге благодаря новому механизму совершается около 1% от всех поездок, а в некоторых городах и районах — до 15%».
Почитайте полное интервью с Романом, там много про аналитику и машинное обучение на практике →
Методы сбора ансамблей алгоритмов машинного обучения: стекинг, бэггинг, бустинг
Что такое ансамбли моделей?
Стекинг. Могут рассматриваться разнородные отдельно взятые модели. Существует мета-модель, которой на вход подаются базовые модели, а выходом является итоговый прогноз.
Бэггинг. Рассматриваются однородные модели, которые обучаются независимо и параллельно, а затем их результаты просто усредняются. Ярким представителем данного метода является случайный лес.
Бустинг. Рассматриваются однородные модели, которые обучаются последовательно, причем последующая модель должна исправлять ошибки предыдущей. Конечно, в качестве примера здесь сразу приходит на ум градиентный бустинг.
Рисунок 1
Три этих способа и будут детальнее рассмотрены далее.
Стекинг
Из трех вариантов стекинг является наименее популярным. Это можно проследить и по числу готовых реализаций данного метода в программных библиотеках. В том же sklearn.ensemble в python куда чаше используют AdaBoost, Bagging, GradientBoosting, чем тот же самый Stacking (хотя его реализация там тоже есть).
Стекинг выделяется двумя основными чертами: он может объединить в себе алгоритмы разной природы в качестве базовых. Например, взять метод опорных векторов (SVM), k-ближайших соседей (KNN) в качестве базовых и на основе их результатов обучить логистическую регрессию для классификации. Также стоит отметить непредсказуемость работы метамодели. Если в случае бэггинга и бустинга существует достаточно четкий и конкретный ансамблевый алгоритм (увидим далее), то здесь метамодель может с течением времени по-разному обучаться на входных данных.
Алгоритм обучения выглядит следующим образом (рис. 2):
Делим выборку на k фолдов (тот же смысл, что и в кросс-валидации).
Для объекта из выборки, который находится в k-ом фолде, делается предсказание слабыми алгоритмами, которые были обучены на k-1 фолдах. Этот процесс итеративен и происходит для каждого фолда.
Создается набор прогнозов слабых алгоритмов для каждого объекта выборки.
На сформированных низкоуровневыми алгоритмами прогнозах в итоге обучается метамодель.
Рисунок 2
Ссылки на библиотеки для использования метода приведены ниже:
Бэггинг
Бэггинг является уже более популярным подходом и зачастую при упоминании этого термина вспоминается алгоритм построения случайного леса, как наиболее типичного его представителя.
При данном методе базовые алгоритмы являются представителями одного и того же семейства, они обучаются параллельно и почти независимо друг от друга, а финальные результаты лишь агрегируются. Нам необходимо, чтобы на вход слабым алгоритмам подавались разные данные, а не один и тот же набор, ведь тогда результат базовых моделей будет идентичен и смысла в них не будет.
0.632*n разных объектов. Таким образом, должны сформироваться m обучающих выборок для m слабых алгоритмов.
Бутстрэп выборки являются в значительной степени независимыми. Отчасти поэтому и говорят, что базовые алгоритмы обучаются на выборках независимо.
Что касается агрегации выходов базовых алгоритмов, то в случае задачи классификации зачастую просто выбирается наиболее часто встречающийся класс, а в случае задачи регрессии выходы алгоритмов усредняются (рис. 3). В формуле под ai подразумеваются выходы базовых алгоритмов.
Рисунок 3
Общий процесс приведен на рисунке ниже (рис. 4):
Рисунок 4
Случайный лес
Рисунок 5
Ссылки на библиотеки для использования метода приведены ниже:
Бустинг
В данном случае, модели уже не обучаются отдельно друг от друга, а каждая следующая правит ошибки предыдущей. То есть можно сказать, что если один слабый алгоритм не смог выявить какую-либо закономерность в данных, так как это было для него сложно, то следующая модель должна сделать это. Но из данного подхода вытекает недостаток: работу алгоритма трудно распараллелить из-за зависимости предыдущего и последующего шагов.
Бустинг направлен скорее на уменьшение смещения в данных, чем на снижение разброса в них. Поэтому в качестве базовых алгоритмов могут браться модели с достаточно высоким смещением, например, неглубокие случайные деревья.
Рисунок 6
Типичными представителями бустинга являются две модели: градиентный бустинг и AdaBoost. Обе по-разному решают одну и ту же оптимизационную задачу по поиску итоговой модели, представляющей собой взвешенную сумму слабых алгоритмов (рис. 6).
Градиентный бустинг использует типичный алгоритм градиентного спуска для решения задачи. Когда приходит время добавить новый слабый алгоритм в ансамбль делается следующее:
Находится оптимальный вектор сдвига, улучшающий предыдущий ансамбль алгоритмов.
Этот вектор сдвига является антиградиентом от функции ошибок работы предыдущего ансамбля моделей
Благодаря вектору сдвигов мы знаем, какие значения должны принимать объекты обучающей выборки
А поскольку нам надо найти очередной алгоритм в композиции, то находим тот, при использовании которого минимизируется отклонение ответов от истинных
Ссылки на библиотеки для использования метода приведены ниже:
Заключение
Таким образом, мы увидели, что для того, чтобы улучшить качество функционирования отдельно взятых моделей машинного обучения, существует ряд техник их объединения в ансамбли. Эти техники уже заложены в программные продукты и ими можно пользоваться, улучшая свое решение. Однако, с моей точки зрения, при решении задачи не стоит сразу же браться за них. Лучше сначала попробовать одну простую, отдельную модель, понять, как она функционирует на конкретных данных, а уже дальше использовать ансамбли.
Ансамблевые методы машинного обучения
Поэтому я решил осветить эту тему в данной статье и показать реализацию ансамблей с помощью scikit-learn.
Что такое ансамбль?
Метод машинного обучения, где несколько моделей обучаются для решения одной и той же проблемы и объединяются для получения лучших результатов называется ансамблевым методом. Основная предпосылка заключается в том, что результат работы нескольких моделей будет более точен, чем результат только одной модели.
Когда говорится об ансамблях, то вводится понятие слабого ученика(обычные модели вроде линейной регрессии или дерева решений). Множество слабых учеников являются строительными блоками для более сложных моделей. Объединение слабых учеников для улучшения качества модели, уменьшения смещения или разброса, называется сильным учеником.
Виды ансамблевых методов
Наиболее популярными ансамблевыми методами являются: стекинг, бэггинг, бустинг.
Стекинг. Используется несколько разнородных слабых учеников. Их обучают и объединяют для построения прогноза, основанного на результатах различных слабых моделей.
Бэггинг. В этом случае однородные модели обучают на разных наборах данных и объединяют. Получают прогноз путём усреднения. Если использовать в качестве слабого ученика деревья решений, то получится случайный лес RandomForestClassifier / RandomForestRegressor.
Бустинг. При использовании данного метода несколько однородных моделей последовательно обучаются, исправляя ошибки друг друга.
Стекинг
Работа этого типа ансамблей довольно проста. На вход всех слабых прогнозаторов подаётся обучающий набор, каждый прогноз идёт к финальной модели, которая называется смеситель, мета-ученик или мета-модель, после чего та вырабатывает финальный прогноз.
Обучение мета-модели
При обучении мета-модели используется приём удерживаемого набора. Сначала набор разделяется на 2 части. Слабые ученики обучаются на первой половине обучающего набора, затем на второй. Затем создаётся новый обучающий набор на основе прогнозов, сделанных на прогнозах первой и второй части набора. Таким образом, на каждый образец из входного набора приходится столько прогнозов, сколько слабых учеников в ансамбле (в примере на картинке три). Мета-модель учится прогнозировать значения на основе нового набора.
Бэггинг
Основная идея бэггинга заключается в том, чтобы обучить несколько одинаковых моделей на разных образцах. Распределение выборки неизвестно, поэтому модели получатся разными.
Если класс предсказывает большинство слабых моделей, то он получает больше голосов и данный класс является результатом предсказывания ансамбля. Это пример жёсткого голосования. При мягком голосовании рассматриваются вероятности предсказывания каждого класса, затем вероятности усредняются и результатом является класс с большой вероятностью.
Бустинг
Метод бустинга в чём то схож с методом бэггинга: берётся множество одинаковых моделей и объединяется, чтобы получить сильного ученика. Но разница заключается в том, что модели приспосабливаются к данным последовательно, то есть каждая модель будет исправлять ошибки предыдущей.
Адаптивный бустинг (AdaBoost)
Данный алгоритм сначала обучает первую базовую модель(допустим деревья решений) на тренировочном наборе. Относительный вес некорректно предсказанных значений увеличивается. На вход второй базовой модели подаются обновлённые веса и модель обучается, после чего вырабатываются прогнозы и цикл повторяется.
Adaboost обновляет веса объектов на каждой итерации. Веса хорошо классифицированных объектов уменьшаются относительно весов неправильно классифицированных объектов. Модели, которые работают лучше, имеют больший вес в окончательной модели ансамбля.
При адаптивном бустинге используется итеративный метод (добавляем слабых учеников одного за другим, просматривая каждую итерацию, чтобы найти наилучшую возможную пару (коэффициент, слабый ученик) для добавления к текущей модели ансамбля) изменения весов. Он работает быстрее, чем аналитический метод.
Градиентный бустинг
Градиентный бустинг обучает слабые модели последовательно, исправляя ошибки предыдущих. Результатом градиентного бустинга также является средневзвешенная сумма результатов моделей. Принципиальное отличие от Adaboost это способ изменения весов. Адаптивный бустинг использует итеративный метод оптимизации. Градиентный бустинг оптимизируется с помощью градиентного спуска.
Вывод
Ансамблевые модели являются мощным инструментом для анализа данных. Идея об объединении простых моделей, позволила делать лучшие прогнозы. Но всё же для построения прогнозов сначала необходимо применять более простые модели, потому что используя их можно добиться нужной точности. Если же результаты вас не устраивают, то можно применять ансамбли.
Помимо библиотеки scikit-learn в python есть библиотека XGBoost, которая предоставляет более обширный набор ансамблевых моделей с более точной реализацией.
Бустинг, AdaBoost
Содержание
Описание [ править ]
Бустинг (англ. boosting) — мета-алгоритм машинного обучения. Основной идеей бустинга является комбинирование слабых функций, которые строятся в ходе итеративного процесса, где на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. Сильный обучающий алгоритм является классификатором, хорошо коррелирующим с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении также рассматривают такие понятия, как бэггинг (англ. bagging) и стэкинг [1] (англ. stacking). Бэггинг, в отличии от бустинга, использует параллельное обучение базовых классификаторов. Стэкинг же комбинирует результаты различных алгоритмов, получая тем самым более точный ответ.
Одним из недостатков бустинга является то, что он может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.
Алгоритмы бустинга [ править ]
Большая часть алгоритмов бустинга основывается на итеративном обучении слабых классификаторов с дальнейшей сборкой их в сильный классификатор. Когда они добавляются, им обычно приписываются веса, обычно связанные с точностью обучения. После добавления слабого классификатора, веса пересчитываются («пересчёт весовых коэффициентов»). Неверно классифицированные входные данные получают больший вес, а правильно классифицированные экземпляры теряют вес. Таким образом, дальнейшее слабое обучение фокусируется на примерах, где предыдущие слабые обучения дали ошибочную классификацию.
Основное расхождение между многими алгоритмами бустинга заключается в методах определения весовых коэффициентов точек тренировочных данных и гипотез. Первым алгоритмом, который смог адаптироваться к слабому обучению был AdaBoost [2] (сокр. Adaptive Boosting), предложенный Шапире и Фройндом.
Прикладное использование алгоритмов бустинга [ править ]
Задача классификации объектов [ править ]
Если даны изображения, содержащие различные известные в мире объекты, классификатор может быть обучен на основе них для автоматической классификации объектов в будущих неизвестных изображениях. Простые классификаторы, построенные на основе некоторых признаков изображения объекта, обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов — путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификации.
Задача ранжирования выдачи поисковых систем [ править ]
Благодаря AdaBoost в мире появился градиентный бустинг (англ. gradient boosting) или GBM. Задачу ранжирования выдачи поисковых запросов рассмотрели с точки зрения функции потерь, которая штрафует за ошибки в порядке выдачи, поэтому было удобно внедрить GBM в ранжирование.
AdaBoost [ править ]
Описание [ править ]
Алгоритм может использоваться в сочетании с несколькими алгоритмами классификации для улучшения их эффективности. Алгоритм усиливает классификаторы, объединяя их в «комитет». AdaBoost является адаптивным в том смысле, что каждый следующий комитет классификаторов строится по объектам, неверно классифицированным предыдущими комитетами. AdaBoost чувствителен к шуму в данных и выбросам. Однако он менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения.
Описание алгоритма [ править ]
Выражение для обновления распределения [math]D^t[/math] должно быть сконструировано таким образом, чтобы выполнялось условие:
Пример работы [ править ]
Для всех ошибочно классифицированных объектов увеличим веса, а для верно классифицированных уменьшим
Теперь у нас все объекты классифицируются верно и число ошибок на выборке равно нулю.
Достоинства и недостатки [ править ]
Пример кода [ править ]
Пример кода на python для scikit-learn [ править ]
Классификатор sklearn.ensemble.AdaBoostClassifier [6] имеет 5 параметров: base_estimator, n_estimators, learning_rate, algorithm, random_state. Наиболее важными являются:
Теперь рассмотрим алгоритм с SVC в качестве базы: