алгоритм буст что такое

Бустинг, 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 в качестве базы:

Источник

Бустинг — ещё один способ машинного обучения

Как с помощью слабых алгоритмов сделать сильный.

Мы уже говорили об общем принципе работы нейросетей для машинного обучения. Разберём другой — бустинг. Кто кого бустит и зачем?

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

Дерево решений

Чтобы понять бустинг, нужно сначала понять дерево решений. Вот это — очень простое дерево:

Сейчас это дерево решений, но может быть деревом предсказаний. Представьте, что в заголовке дерева написано «Выйдет ли Юзернейм гулять?» — и вы получите машину предсказаний, которая на основе данных о Юзернейме и погоде будет строить точные предсказания о Юзернейме — при условии, что мы задаём правильные вопросы.

Машина предсказания

Теперь пример сложнее. Допустим, у нас есть данные по миллиону музыкальных клипов на Ютубе. По каждому есть 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%».

Почитайте полное интервью с Романом, там много про аналитику и машинное обучение на практике →

Источник

XGBoost

XGBoost [1] — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.

Содержание

История [ править ]

Описание алгоритма [ править ]

В основе XGBoost лежит алгоритм градиентного бустинга деревьев решений. Градиентный бустинг — это техника машинного обучения для задач классификации и регрессии, которая строит модель предсказания в форме ансамбля слабых предсказывающих моделей, обычно деревьев решений. Обучение ансамбля проводится последовательно в отличие, например от бэггинга. На каждой итерации вычисляются отклонения предсказаний уже обученного ансамбля на обучающей выборке. Следующая модель, которая будет добавлена в ансамбль будет предсказывать эти отклонения. Таким образом, добавив предсказания нового дерева к предсказаниям обученного ансамбля мы можем уменьшить среднее отклонение модели, которое является таргетом оптимизационной задачи. Новые деревья добавляются в ансамбль до тех пор, пока ошибка уменьшается, либо пока не выполняется одно из правил «ранней остановки».

Математика за алгоритмом [ править ]

[math]\mathcal^ <(t)>= \sum_^n l(y_i,\hat^<(t-1)>+f_t(x_i))+\Omega(f_t)[/math] — функция для оптимизации градиентного бустинга, где:

[math]l[/math] — функция потерь, см. Общие понятия.

[math]y_i, \hat^[/math] — значение i-го элемента обучающей выборки и сумма предсказаний первых t деревьев соответственно.

[math]x_i[/math] — набор признаков i-го элемента обучающей выборки.

[math]f_t[/math] — функция (в нашем случае дерево), которую мы хотим обучить на шаге t. [math]f_t(x_i)[/math] — предсказание на i-ом элементе обучающей выборки.

Дальше с помощью разложения Тейлора до второго члена можем приблизить оптимизируемую функцию [math]\mathcal^<(t)>[/math] следующим выражением:

Поскольку мы хотим минимизировать ошибку модели на обучающей выборке, нам нужно найти минимум [math]\mathcal^<(t)>[/math] для каждого t.

Каждое отдельное дерево ансамбля [math]f_t(x_i)[/math] обучается стандартным алгоритмом. Для более полного описания см. Дерево решений и случайный лес.

Возможности XGBoost [ править ]

XGBoost поддерживает все возможности таких библиотек как scikit-learn с возможностью добавлять регуляризацию. Поддержаны три главные формы градиетного бустинга:

Библиотека предоставляет систему для использования в различных вычислительных средах:

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

Основные параметры [ править ]

Поддерживаемые интерфейсы [ править ]

Пример использования с помощью библиотеки xgboost [ править ]

Разделение датасета на обучающую/тестовую выборку.

Импорт XGBoost и создание необходимых объектов.

Задание параметров модели.

Определение качества модели на тестовой выборке.

Источник

🤖 Решаем задачи машинного обучения с помощью алгоритма градиентного бустинга

Alex Maszański

Предположим, что вы играете в гольф. Чтобы загнать мяч в лунĸу, вам необходимо замахиваться клюшкой, каждый раз исходя из предыдущего удара. То есть перед новым ударом гольфист в первую очередь смотрит на расстояние между мячом и лунĸой после предыдущего удара, так как наша основная задача – при следующем ударе уменьшить это расстояние.

Стоит отметить, что для задач классификации и регрессии реализация алгоритма в программировании будет различаться.

Параметры алгоритма

Реализация на языке python (библиотека sklearn)

Результат работы кода:

Базовая модель градиентного бустинга с несложной простой настройкой дает нам точность более чем в 95% на задаче регрессии.

Какие библиотеки использовать?

Вы можете установить XGBoost следующим образом:

Библиотека XGBoost предоставляем нам разные классы для разных задач: XGBClassifier для классификации и XGBregressor для регрессии.

Вы можете установить LightGBM также при помощи pip:

Более того, главным преимуществом CatBoost (помимо улучшения скорости вычислений) является поддержка категориальных входных переменных. Из-за этого библиотека получила свое название CatBoost, от «Category Gradient Boosting» (Категориальный Градиентный Бустинг).

Вы можете установить CatBoost проверенным ранее путем:

Когда использовать?

Вы можете использовать алгоритм градиентного бустинга при следующих условиях:

Когда НЕ следует использовать XGBoost:

Плюсы и минусы

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

Источник

Ансамблевые методы: бэггинг, бустинг и стекинг

«Единство это сила». Эта старая поговорка довольно хорошо выражает основную идею, за которой стоят очень мощные «ансамблевые методы» в машинном обучении. Ансамблевые методы часто занимают топ рейтингов во многих соревнованиях по машинному обучению, в том числе на Kaggle. Если говорить грубо, они основаны на гипотезе о том, что объединение нескольких моделей воедино часто может привести к созданию гораздо более мощной модели.

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

План

В первом разделе этой статьи мы представим понятия слабых и сильных учеников и представим три основных метода обучения в ансамбле: бэггинг, бустинг и стекинг. Затем во втором разделе мы сфокусируем внимание на бэггинге и обсудим такие понятия, как бутстрэп, бэггинг и случайный лес. В третьем разделе мы представим бустинг и, в частности, два его самых популярных варианта: адаптивный бустинг (adaboost) и градиентный бустинг. Наконец, в четвертом разделе мы дадим обзор стекинга.

Что такое ансамблевые методы?

Ансамблевые методы — это парадигма машинного обучения, где несколько моделей (часто называемых «слабыми учениками») обучаются для решения одной и той же проблемы и объединяются для получения лучших результатов. Основная гипотеза состоит в том, что при правильном сочетании слабых моделей мы можем получить более точные и/или надежные модели.

Один слабый ученик

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

Слабое смещение (bias) и разброс (variance) модели, хотя они чаще всего изменяются в противоположных направлениях, являются двумя наиболее фундаментальными особенностями, ожидаемыми для модели. Действительно, чтобы иметь возможность «решить» проблему, мы хотим, чтобы в нашей модели было достаточно степеней свободы для разрешения базовой сложности данных, с которыми мы работаем, но мы также хотим, чтобы у нее было не слишком много степеней свободы, чтобы избежать ее высокого разброса и быть более устойчивой. Это хорошо известный компромисс между смещением и разбросом.

Иллюстрация компромисса между смещением и разбросом

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

Объединение слабых учеников

Чтобы реализовать ансамблевый метод, нам сначала нужно отобрать наших слабых учеников для агрегирования. В основном (в том числе в хорошо известных методах бэггинга и бустинга) используется единственный базовый алгоритм обучения, так что у нас есть однородные слабые ученики, которые обучаются по-разному. Получаемая нами модель ансамбля называется «однородной». Тем не менее, существуют также некоторые методы, которые используют различные типы базовых алгоритмов обучения: некоторые разнородные слабые ученики затем объединяются в «разнородную ансамблевую модель».

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

Это подводит нас к вопросу о том, как комбинировать эти модели. Мы можем упомянуть три основных типа мета-алгоритмов, которые направлены на объединение слабых учеников:

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

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

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

Сфокусируем внимание на бэггинге

В параллельных методах мы рассматриваем разных учеников независимо друг от друга друга и, таким образом, можно обучать их одновременно. Наиболее известным из таких подходом является «бэггинг» (от «bootstrap aggregation»), целью которого является создание ансамблевой модели, которая является более надежной, чем отдельные модели, ее составляющие.

Бутстрэп

Давайте начнем с определения бутстрэпа. Этот статистический метод заключается в генерации выборок размера B (так называемых бутстрэп выборок) из исходного датасета размера N путем случайного выбора элементов с повторениями в каждом из наблюдений B.

Иллюстрация процесса бустрэпа

При некоторых допущениях эти выборки имеют довольно хорошие статистические свойства: в первом приближении их можно рассматривать как взятые непосредственно из истинного базового (и часто неизвестного) распределения данных, так и независимо друг от друга. Таким образом, их можно рассматривать как репрезентативные и независимые выборки истинного распределения данных (почти идентичные выборки). Гипотеза, которая должна быть проверена, чтобы сделать это приближение действительным, имеет две стороны. Во-первых, размер N исходного датасета должен быть достаточно большим, чтобы охватить большую часть сложности базового распределения, чтобы выборка из датасета была хорошим приближением к выборке из реального распределения (репрезентативность). Во-вторых, размер датасета N должен быть достаточно большим по сравнению с размером бутстрэп выборок B, чтобы выборки не слишком сильно коррелировали (независимость). Обратите внимание, что в дальнейшем мы иногда будем ссылаться на эти свойства (репрезентативность и независимость) бутстрэп выборок: читатель всегда должен помнить, что это только приближение.

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

Бутстрэп часто используется для оценки разброса или доверительного интервала некоторых статистических оценок

Бэггинг

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

Идея бэггинга в таком случае проста: мы хотим подобрать несколько независимых моделей и «усреднить» их прогнозы, чтобы получить модель с меньшим разбросом. Однако на практике мы не можем подобрать полностью независимые модели, потому что для этого потребуется слишком много данных. Таким образом, мы полагаемся на хорошие «приблизительные свойства» бутстрэп выборок (репрезентативность и независимость) для подбора моделей, которые практически независимы.

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

Итак, предположим, что у нас есть L бутстрап выборок (аппроксимации L независимых датасетов) размера B. Это обозначается:

Мы можем обучить L почти независимых слабых учеников (по одному на каждый датасет):

А затем объединим их некоторым процессом усреднения, чтобы получить модель ансамбля с меньшим разбросом. Например, мы можем определить нашу сильную модель так, чтобы

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

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

Бэггинг состоит из нескольких базовых моделей, обученных на разных бутстрэп выборках и построения ансамблевой модели, которая «усредняет» результаты этих слабых учеников

Случайные леса

Деревья решений являются очень популярными базовыми моделями для ансамблевых методов. Сильные ученики, состоящие из нескольких деревьев решений, можно назвать «лесами». Деревья, составляющие лес, могут быть выбраны либо неглубокими (глубиной в несколько узлов), либо глубокими (глубиной в множество узлов, если не в полную глубину со всеми листьями). Неглубокие деревья имеют меньший разброс, но более высокое смещение, и тогда для них лучшим выбором станут последовательные методы, которые мы опишем позже. Глубокие деревья, с другой стороны, имеют низкое смещение, но высокий разброс и, таким образом, являются подходящим выбором для бэггинга, который в основном направлен на уменьшение разброса.

Случайный лес представляет собой метод бэггинга, где глубокие деревья, обученные на бутстрап выборках, объединяются для получения результата с более низким разбросом. Тем не менее, случайные леса также используют другой прием, чтобы несколько обученных деревьев были менее коррелированными друг с другом: при построении каждого дерева вместо выбора всех признаков из датасета для генерации бутстрэпа мы выбираем и сохраняем только случайное их подмножество для построения дерева (обычно одинаковое для всех бутстрэп выборок).

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

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

Сфокусируем внимание на бустинге

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

Бустинг

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

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

После того, как слабые ученики выбраны, нам все еще нужно определить, как они будут последовательно подгоняться (какую информацию из предыдущих моделей мы учитываем при подборе текущей модели?) И как они будут агрегироваться (как мы агрегируем текущую модель к предыдущим?). Мы обсудим эти вопросы в двух следующих подразделах, более подробно описывающих два важных алгоритма бустинга: adaboost (адаптивный бустинг) и градиентный бустинг.

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

Бустинг состоит в итеративном подборе слабого ученика, агрегировании его в модель ансамбля и «обновлении» обучающего датасета для лучшего учета сильных и слабых сторон текущей модели ансамбля при подборе следующей базовой модели.

Адаптивный бустинг

При адаптивном бустинге («adaboost») мы пытаемся определить нашу ансамблевую модель как взвешенную сумму L слабых учеников.

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

где c_l и w_l выбраны так, что s_l — это модель, которая наилучшим образом соответствует обучающим данным, и, таким образом, это наилучшее возможное улучшение по сравнению с s_(l-1). Затем мы можем определить

где E(.) — ошибка подгонки данной модели, а e(. ) — функция потерь/ошибок. Таким образом, вместо глобальной оптимизации по всем L-моделям в сумме, мы приближаем оптимум локальной оптимизацией путем построения и добавления слабых учеников к сильной модели по одному.

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

Итак, предположим, что мы сталкиваемся с задачей бинарной классификации с N объектами в нашем датасете, и мы хотим использовать алгоритм adaboost с данным семейством слабых моделей. В самом начале алгоритма (первая модель последовательности) все объекты имеют одинаковые веса 1 / N. Затем мы повторяем L раз (для L учеников в последовательности) следующие шаги:

Повторяя эти шаги, мы затем последовательно строим наши L моделей и объединяем их в простую линейную комбинацию, взвешенную по коэффициентам, выражающим эффективность каждого ученика. Обратите внимание, что существуют варианты исходного алгоритма adaboost, такие как LogitBoost (классификация) или L2Boost (регрессия), которые в основном различаются по своему выбору функции потерь.

Adaboost обновляет веса объектов на каждой итерации. Веса хорошо классифицированных объектов уменьшаются относительно весов неправильно классифицированных объектов. Модели, которые работают лучше, имеют больший вес в окончательной модели ансамбля.

Градиентный бустинг

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

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

где E (.) — ошибка подгонки данной модели, c_l — коэффициент, соответствующий размеру шага, и

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

Итак, предположим, что мы хотим использовать градиентный бустинг с семейством слабых моделей. В самом начале алгоритма (первая модель последовательности) псевдо-остатки устанавливаются равными значениям объектов. Затем мы повторяем L раз (для L моделей последовательности) следующие шаги:

Повторяя эти шаги, мы последовательно строим наши L моделей и агрегируем их в соответствии с подходом градиентного спуска. Обратите внимание на то, что, хотя адаптивный бустинг пытается решить на каждой итерации именно «локальную» задачу оптимизации (найти лучшего слабого ученика и его коэффициент, который нужно добавить к сильной модели), градиентный бустинг использует вместо этого подход с градиентным спуском и его легче адаптировать к большому количеству функций потерь. Таким образом, градиентный бустинг можно рассматривать как обобщение adaboost для произвольных дифференцируемых функций потерь.

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

Обзор стекинга

Стекинг имеет два основных отличия от бэггинга и бустинга. Во-первых, стекинг часто учитывает разнородных слабых учеников (комбинируются разные алгоритмы обучения), тогда как бэггинг и бустинг учитывают в основном однородных слабых учеников. Во-вторых, стекинг учит объединять базовые модели с использованием метамодели, тогда как бэггинг и бустинг объединяют слабых учеников с помощью детерминистическим алгоритмам.

Стекинг

Как мы уже упоминали, идея стекинга состоит в том, чтобы выучить нескольких разных слабых учеников и объединить их, обучив метамодель для вывода предсказаний, основанных на множественных предсказаниях, возвращаемых этими слабыми моделями. Итак, нам нужно определить две вещи для построения нашей модели стека: L учеников, которых мы хотим обучить, и метамодель, которая их объединяет.

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

Итак, предположим, что мы хотим обучить стековый ансамбль, составленный из L слабых учеников. Затем мы должны выполнить следующие шаги:

На предыдущих этапах мы разбили датасет на две части, потому что прогнозы данных, которые использовались для обучения слабых учеников, не имеют отношения к обучению метамодели. Таким образом, очевидным недостатком этого разделения нашего датасета на две части является то, что у нас есть только половина данных для обучения базовых моделей и половина данных для обучения метамодели. Чтобы преодолеть это ограничение, мы можем, однако, следовать некоторому подходу «k-fold кросс-обучение» (аналогичному тому, что делается в k-fold кросс-валидации), таким образом все объекты могут быть использованы для обучения мета-модели: для любого объекта предсказание слабых учеников делается на примерах этих слабых учеников, обученных на k-1 фолдах, которые не содержат рассматриваемого объекта. Другими словами, он обучается по k-1 фолдам, чтобы делать прогнозы для оставшегося фолда для объектов в любых фолдах. Таким образом, мы можем создать соответствующие прогнозы для каждого объекта нашего датасета, а затем обучить нашу метамодель всем этим прогнозам.

Стекинг состоит в обучении метамодели для получения результатов, основанных на результатах, полученных несколькими слабыми учениками нижнего уровня

Многоуровневый стекинг

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

Многоуровневый стекинг предполагает несколько уровней стекинга: некоторые метамодели обучаются на выходных данных, возвращаемых метамоделями более низкого уровня, и так далее. Здесь мы представили 3-х слойную модель стекинга.

Итоги

Основные выводы этой статьи следующие:

В этой статье мы дали базовый обзор ансамблевых методов и, в частности, некоторых основных понятий в этой области: бутстрэп, бэггинг, случайный лес, бустинг (adaboost, градиентный бустинг) и стекинг. Среди оставленных в стороне понятий можно упомянуть, например, метод оценки Out-Of-Bag для бэггинга или также очень популярный «XGBoost» (что означает eXtrem Gradient Boosting), который является библиотекой, реализующей методы градиентного бустинга вместе с множеством дополнительных трюков, которые делают обучение намного более эффективным (и пригодным для больших датасетов).

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

Источник