что такое бэггинг в машинном обучении
Бэггинг
Материал из MachineLearning.
Содержание
Идея метода
Бэггинг – технология классификации, где в отличие от бустинга все элементарные классификаторы обучаются и работают параллельно (независимо друг от друга). Идея заключается в том, что классификаторы не исправляют ошибки друг друга, а компенсируют их при голосовании. Базовые классификаторы должны быть независимыми, это могут быть классификаторы основанные на разных группах методов или же обученные на независимых наборах данных. Во втором случае можно использовать один и тот же метод.
Бэггинг на подпространствах
Этот алгоритм применяется для классификации многомерных объектов. Рассматриваемый алгоритм помогает добиться качественной классификации в условиях, когда разделить объекты на группы на всем пространстве параметров не представляется возможным. Предлагается разделить пространство характеристик на подмножества объединенных по смыслу параметров. Классификация на каждом подпространстве производится отдельно, затем результаты учитываются в голосовании. В этом случае будет учтен вклад каждой смысловой группы и много повысится вероятность того, что итоговые результаты классификации окажутся более качественными нежели без деления на подпространства, так как параметры, по которым представители разных классов неотличимы, попадут, почти наверняка, не во все группы.
Постановка задачи
Существует матрица характеристик объекта мерные столбцы с характеристиками объектов. Необходимо сопоставить каждому вектору параметров метку класса (т.е. существует некоторое отображение Y» alt= «X->Y» />, где метки классов), на основании известных пар для объектов обучающей выборки.
Алгоритм классификации в технологии бэггинг на подпространствах
Методы принятия решений
Окончательное решение о принадлежности объекта классу может приниматься, например, одним из следующих методов:
Бэггинг на подпространствах с классификаторами на основе метода потенциальных функций
Объединение метода Бравермана потенциальных функций и технологии Бэггинг позволяет работать с небольшими выборками многомерных объектов. Подход успешно справляется с неравномерным распределением объектов внутри классов, однако выбросы в данных (особенно при небольших выборках) оказывают очень большое влияние на результаты итоговой классификации.
Семь основных понятий машинного обучения
Невозможно не восхищаться машинным обучением. Машины невероятно мощны. Даже Стив Балмер считает, что машинное обучение станет новой эрой вычислительной техники. В наши дни этот феномен окружён многочисленными слухами. Ману Дживан (Manu Jeevan) предлагает обзор основных концепций машинного обучения. dev.by публикует перевод его статьи.
Методы ансамблей (коллективные методы)
Классно, когда владеешь этими методами. Дерево принятия решений работает не очень хорошо, но очень быстро.
Методы ансамблей — это алгоритмы обучения, которые строят ряд классификаторов и затем классифицируют новые точки данных, суммируя результаты их предсказаний. В этой статье я буду говорить о некоторых популярных методах, например, бэггинге, бустинге и случайных лесах.
Если бы меня попросили рассказать про методы ансамблей одним предложением, я сформулировал бы это так: «Агрегация предсказаний нескольких классификаторов с целью повышения точности».
Но если вы хотите обучать множественные классификаторы, вам нужно больше данных. Чем больше степеней свободы имеет ваша модель, тем больший объём данных модель старается вместить и тем больше точек данных вам понадобится. Здесь и пригодится бутстрэп.
Бутстрэп
Вы используете имеющиеся данные и пытаетесь их приумножить — в этом суть бутстрэпинга. Возьмите N точек данных и введите N раз с заменой — в результате вы получите несколько наборов одного размера. Поскольку вы используете замену, каждый из этих образцов будет немного отличаться. Вы можете использовать каждый из наборов данных отдельно.
Помните, что вы не можете делать перекрёстную проверку в этом случае, потому что у вас есть бутстрэп образцы х1 и х2 и некоторые точки присутствуют как в х1, так и в х2.
Для лучшего понимания бутстрэпинга читайте эту ветку на Stack Exchange.
Бэггинг
Первый из методов ансамблей, о котором мы поговорим, называется бэггинг (bagging — сокр. от bootstrap aggregation).
Один из недостатков деревьев принятия решений в том, что они выглядят по-разному при наличии небольшой разницы в данных. Ансамбли превращают этот недостаток в преимущество.
Бэггинг состоит из следующих шагов:
Когда каждый бутстрэп-образец выглядит немного иначе, вы получаете разные деревья принятия решений. Вы можете усреднить их и получить хорошую классификацию. Бэггинг значительно снижает переобучение.
Основная идея бэггинга — усреднить «шумные» и несмещённые модели для создания модели с низким расхождением в рамках классификации. Посмотрите это видео, чтобы лучше понять, что такое бэггинг.
Случайный лес
Случайный лес использует много деревьев принятия решений для создания классификации. В качестве параметров используется число признаков и число деревьев. Случайный лес — это готовый классификатор, большую часть времени вам не придётся думать об этих параметрах.
Если вы разобрались с концепцией деревьев принятия решений, понять случайные леса вам будет нетрудно. Я бы порекомендовал вам прочесть введение в случайные леса для дилетантов от Эдвина Чена и посмотреть это видео.
Вероятность ошибки случайного леса зависит от корреляции между деревьями и от силы отдельных деревьев.
Но если вы увеличите количество признаков при каждом разделении, увеличится и корреляция между деревьями, и сила отдельных деревьев. Если ваши деревья не очень отличаются, усреднение не даст улучшений, на которые вы рассчитываете. Отдельные деревья должны быть действительно сильными, если вы хотите, чтобы каждое дерево чему-то научилось. Здесь нужен компромисс.
а) Out-Of-Bag-ошибка
OOB-ошибка — это встроенная версия расчёта ошибки теста. Это очень удобно, потому что вам не нужно откладывать набор данных в самом начале. Вы берёте бутстрэп-сэмпл, который покрывает 60% оригинальных точек данных, и у вас есть 30% неиспользованных. Суть в том, что вы можете использовать эти 30% как точки для оценки ошибки теста. Если я делаю бутстрэп-сэмплы и в конце получаю 500 штук — это для каждого отдельного дерева, не для всего леса — у меня есть бутстрэп-сэмпл и оставшиеся точки, которые в него не вошли. Я могу использовать их для оценки результатов теста для каждого отдельного дерева (не всего леса). Суть в том, что вы можете сделать это для каждого дерева, и это даст характеристику случайного леса, потому что вы знаете, насколько сильны отдельные деревья.
И всё же, я не считал бы OOB-ошибку ошибкой теста. Если вы изобразите их зависимость друг от друга, в большинстве случаев вы увидите возрастание, потому что это ненастоящая ошибка теста.
Можно использовать OOB-ошибку для валидации — таким образом вы можете подбирать оптимальное количество деревьев. Прочтите эту статью, чтобы узнать больше о OOB-ошибке.
b) Значимость переменной
Случайные леса позволяют вычислить эвристику для определения «значимости» параметра в предсказании цели. Она замеряет изменения в точности предсказаний, если вы возьмёте и перемешаете значения данного параметра между точками данных в тестовом наборе. Чем больше при этом снижается точность, тем более значимым считается параметр.
Допустим, есть 1000 мужчин и 1000 женщин. Измерим рост каждого человека и смоделируем предсказание роста по полу. В контексте случайного леса вы можете оценить точность предсказания out-of-bag.
Если пол не влияет на рост, вы должны получить примерно ту же точность предсказания при случайном переставлении значений М/Ж.
Так и работает значимость переменной случайных лесов: перемешайте наблюдаемые значения в рамках одной переменной, пересчитайте точности предсказаний и сравните полученные результаты с изначальными данными. Если перемешанные данные дают такие же предсказания, как и исходные, переменная, очевидно, не так важна для предсказания. Если же с перемешанными значениями точность предсказаний падает, переменная значима.
Несбалансированные классы
Несбалансированные классы означают, что у вас есть 8000 точек класса А и 2000 точек класса В. Ваша задача сделать так, чтобы классификатор понимал важность точек класса В. Один из вариантов — использовать сэмплы (продолжайте делать сэмплы, пока не получите два набора данных одинакового размера). Другой вариант — разбить на сэмплы большой класс. Случайный лес предоставляет хорошее решение для этого: вы можете создавать подсэмплы для каждого дерева. Таким образом, все деревья теперь сбалансированы, в итоге алгоритм получит все значения из большого класса.
Точность и полнота
Точность и полнота — оценочная метрика проблем классификации с асимметричными классами. Во многих приложениях необходимо контролировать соотношение точности и полноты.
Рассмотрим пример прогнозирования рака. Если вы модифицируете свою гипотезу (h(x)) до 0.7, чтобы уверенно прогнозировать рак, вы получите классификатор с высокой точностью и низкой полнотой. Иными словами, у пациента рак, но вы ошиблись, сообщив ему, что рака нет. Если вы установите (h(x)) на 0.3, вы получите высокую полноту и низкую точность. В этом случае классификатор может предсказать, что у большинства из них есть рак. Для большинства классификаторов это будет компромиссом между точностью и полнотой.
Есть ли способ определить порог автоматически? Как решить, какой из них лучше? И тут наступает очередь F-метрик. F-метрика — средство гармонизации точности и полноты.
Чтобы лучше понять, что такое точность и полнота, посмотрите эти видео-лекции (неделя 6) или прочитайте этот текст.
Бустинг
Это один из методов ансамблей, но он делает больше, чем просто усреднение. Вы обучаете один классификатор, смотрите на результаты и вносите коррективы. Вы обучаете второй, смотрите на результаты, вносите коррективы и усредняете их при помощи весов. Классификатору, который показал хороший результат, я хочу присвоить больший вес, второй получает меньший вес.
Для многих приложений бустинг подходит лучше, чем бэггинг. Читайте больше о бустинге здесь.
AdaBoost
В AdaBoost вы рисуете одну границу решений и смотрите на классификации — несколько точек будут ошибочными. Я присвою этим точкам большой вес (они не классифицированы, линия 1 на рисунке). И следующему классификатору, который буду обучать, я скажу обратить больше внимания на эти точки. В итоге получим другую границу решений (линия 2). Вместо того, чтобы вносить неразбериху, я смотрю на работу предыдущего классификатора и пытаюсь исправить совершенные им ошибки.
В большинстве случаев AdaBoost работает даже с «пнями». Пни решений — одноуровневое дерево принятия решений, с одним разветвлением. На практике, линия AdaBoost будет не прямой, а ломанной.
Заключение
Итак, я рассказал о некоторых наиболее важных концептах машинного обучения. Концепцию ансамблей я бы хотел передать этой цитатой Джеймса Суровецки (James Surowiecki):
«Коллективное знание разнообразной и независимой группы людей обычно превышает знания каждого отдельного индивида и может быть учтено путем голосования».
Кстати, метод ансамблей использовали победители Netflix prize — посмотрите видео.
Хотите сообщить важную новость? Пишите в Телеграм-бот.
А также подписывайтесь на наш Телеграм-канал.
😱 Разработчик прошел 3 собеседования в Facebook, Amazon и Google. И рассказал про самую кошмарную часть — behavioral interview. Читайте, как это было.
Ансамблевые методы: бэггинг, бустинг и стекинг
«Единство это сила». Эта старая поговорка довольно хорошо выражает основную идею, за которой стоят очень мощные «ансамблевые методы» в машинном обучении. Ансамблевые методы часто занимают топ рейтингов во многих соревнованиях по машинному обучению, в том числе на 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), который является библиотекой, реализующей методы градиентного бустинга вместе с множеством дополнительных трюков, которые делают обучение намного более эффективным (и пригодным для больших датасетов).
Наконец, мы хотели бы в заключение напомнить, что обучение ансамблей — это объединение некоторых базовых моделей для получения модели ансамбля с лучшими характеристиками. Таким образом, даже если бэггинг, бустинг и стекинг являются наиболее часто используемыми ансамблевыми методами, возможны варианты, которые могут быть разработаны для лучшей адаптации к некоторым конкретным проблемам. В основном это требует двух вещей: полностью понять проблему, с которой мы сталкиваемся и… проявить творческий подход!