Ансамбли в машинном обучении

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

Ансамблем (Ensemble, Multiple Classifier System) называется алгоритм, который состоит из нескольких алгоритмов машинного обучения, а процесс построения ансамбля называется ансамблированием (ensemble learning). Простейший пример ансамбля в регрессии – усреднение нескольких алгоритмов:

f-1

Алгоритмы из которых состоит ансамбль (в (1) – b_t) называются базовыми алгоритмами (base learners). Если рассматривать значения базовых алгоритмов на объекте как независимые случайные величины с одинаковым матожиданием и одинаковой конечной дисперсией, то понятно, что случайная величина (1) имеет такое же матожидание, но меньшую дисперсию:

Замечание. Требование равенства матожиданий ответов базовых алгоритмов вполне естественное: если мы берём алгоритмы из несмещённой модели, то их матожидания не только совпадают, но и равны значению истинной метки. А вот у требования равенства дисперсий уже нет приемлемого оправдания, но для обоснования эффективности ансамбля можно потребовать меньше… вопрос: что именно?

В задачах классификации простейший пример ансамбля – комитет большинства:

где mode – мода (значение, которое встречается чаще других среди аргументов функции). Если рассмотреть задачу классификации с двумя классами {0, 1} и три алгоритма, каждый из которых ошибается с вероятностью p, то в предположении, что их ответы – независимые случайные величины, получаем, что комитет большинства этих трёх алгоритмов ошибается с вероятностью pp(3-2p). Как видно на рис. 1, это выражение может быть существенно меньше p (при p=0.1 почти в два раза), т.е. использование такого ансамбля уменьшает ошибку базовых алгоритмов.

pic_ens_01 — Рис 1. График вероятности ошибки комитета большинства.

Замечание. Если рассмотреть большее число алгоритмов, то по неравенству Хёфдинга ошибка комитета большинства

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

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

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

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

повышают качество базовых алгоритмов,
повышают разнообразие (diversity) базовых алгоритмов.

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

«варьирования» обучающей выборки (бэгинг),
«варьирования» признаков (Random Subspaces),
«варьирования» целевого вектора (ECOC, деформации целевого признака),
«варьирования» моделей (использование разных моделей, стэкинг),
«варьирование» в модели (использование разных алгоритмов в рамках одной, рандомизация в алгоритме – случайный лес).

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

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

алгоритм 1: 1111110000 качество = 0.6
алгоритм 2: 1111110000 качество = 0.6
алгоритм 3: 1111110000 качество = 0.6
ансамбль  : 1111110000 качество = 0.6

Теперь построим похожие алгоритмы:

алгоритм 1: 1111110000 качество = 0.6
алгоритм 2: 1111101000 качество = 0.6
алгоритм 3: 1111100100 качество = 0.6
ансамбль  : 1111100000 качество = 0.5

Теперь построим совершенно разные алгоритмы:

алгоритм 1: 1010010111 качество = 0.6
алгоритм 2: 1100110011 качество = 0.6
алгоритм 3: 1111110000 качество = 0.6
ансамбль  : 1110110011 качество = 0.7

Как видно, ансамбль «совсем разнообразных» алгоритмов показал лучшее качество. Вопрос: нет ли подвоха в этом примере?

В общем случае ансамбль записывается как

где b – некоторый алгоритм (т.е. функция), который принято называть мета-алгоритмом (meta-estimator). Как видим, выражения (1) и (2) являются частным случаем этой записи.

Обоснования использования ансамблей в машинном обучении обычно бывают статистическими (statistical) – приведены выше, когда мы оценивали ошибку ансамбля исходя из вероятностной природы ответов алгоритмов, вычислительными (computational) – поскольку обучение это решение задачи оптимизации, то ансамбль распараллеливает процесс: мы параллельно обучаем несколько базовых алгоритмов, а метаалгоритм «комбинирует» полученные ответы, функциональными (representational) – часто ансамблем можно представить существенно более сложную функцию, чем любым базовым алгоритмом. Последнее можно проиллюстрировать следующим рис. 2: показана задача бинарной классификации, в которой нельзя настроить на 100%-е качество линейный алгоритм, но можно настроить простейший ансамбль линейных алгоритмов. Кстати, какой? Таким образом, ансамбли позволяют решать сложные задачи простыми моделями, усложнение решения для возможности хорошей настройки на данные происходит на уровне мета-алгоритма.

Рис. 2. Линейные классификаторы в задаче с нелинейной природой данных.

Существуют следующие основные модели ансамблирования:

модель или общая идея	описание и примеры
комитеты (голосование) / усреднение	Построение независимых алгоритмов и их усреднение / голосование по ним, в том числе с помощью бэгинга и предварительной деформации ответов. Здесь же и обобщения бэгинга – случайные леса.
кодировки / перекодировки ответов	Специальные кодировки целевых значений и сведение решения задачи к решению нескольких задач. Один из самых популярных приёмов – ECOC (error-correcting output coding). Другой – настройка на разные деформации целевого признака.
стекинг (stacking)	построение метапризнаков – ответов базовых алгоритмов на объектах выборки, обучение на них мета- алгоритма
бустинг (boosting)	Построение суммы нескольких алгоритмов. Каждое следующее слагаемое строится с учётом ошибок предыдущих: AdaBoost, градиентный бустинг.
«ручные методы»	Эвристические способы комбинирования ответов базовых алгоритмов (с помощью визуализаций, обучения в специальных подпространствах и т.п.)
однородные ансамбли	Пример – нейронные сети. Формула мета-алгоритм – базовые алгоритмы разворачивается рекурсивно, применяется общая схема оптимизации полученной конструкции.

Комитеты (голосование, Voting Ensembles) / усреднение

С этим самым простым способом построения ансамблей мы познакомились на примерах выше. Отметим, что в общем случае может использоваться любое усреднение по Коши. Например, в задачах обнаружения аномалий в качестве мета-классификатора может использоваться максимум: каждый базовый алгоритм выдаёт свою оценку вероятности того, что конкретный объект является аномалией (не похож на обучающую выборку), мы полагаемся на максимальную оценку. Поскольку такие задачи возникают в областях, где нельзя пропустить аномалию (обнаружение поломок, хакерских атак, инсайдеров на бирже и т.п.), действуют по логике «поднимать тревогу при малейшем подозрении».

Часто при использовании функции ошибки MAE в задаче регрессии медиана базовых алгоритмов показывает качество выше, чем среднее арифметическое. В задачах бинарной классификации при использовании AUC ROC – часто усредняют не оценки принадлежности классу 1, а ранги:

f-6

Можно это попробовать объяснить тем, что для функционала AUC ROC важно «правильное упорядочивание» объектов в задаче бинарной классификации, а не конкретные значения оценок. Функция rank позволяет в меньшей степени учитывать сами значения, которые выдают алгоритмы, а в большей, порядок на объектах контрольной выборки.

Вместо обычного усреднения/голосования часто используют усреднение с весами (weighted averaging) / голосование с весами, когда есть основания по-разному доверять разным алгоритмам, участвующим в ансамбле. Feature-Weighted Linear Stacking – это естественная идея обобщения усреднения с весами: сделать веса алгоритмами, т.е. зависимыми от описания объектов

f-7

Здесь веса ищутся в виде линейных регрессий над исходными признаками. Видно, что задача построения такого ансамбля сводится к настройке линейной регрессии в пространстве признаков, которые являются всевозможными произведениями исходных признаков на ответы базовых алгоритмов. Этот метод использовался Top2 командой соревнования Netflix Prize.

Бэгинг (Bagging)

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

Метод	Описание
Бэгинг	Подвыборка обучающей выборки берётся с помощью бутстрепа
Пэстинг (Pasting)	Случайная обучающая подвыборка
Случайные подпространства (Random Subspaces)	Случайное подмножество признаков
Случайные патчи (Random Patches)	Одновременно берём случайное подмножество объектов и признаков
cross-validated committees	k обучений на (k-1)-м фолде

Вероятность быть отобранным при бутстрепе (подвыборке объёма m из основной выборки такого же объёма «с возвращением») для достаточно больших выборок равна примерно 0.632, т.е. примерно 36.8% объектов оказываются «за бортом».

Важно понимать, что подвыборки обучающей выборки берутся в бэгинге для того, чтобы базовые алгоритмы получались непохожими. Есть модели алгоритмов, которые устойчивы (stable learners) относительно взятия подвыборок (kNN при k>3, SVM), их не следует использовать в бэгинге. На рис. 3 показано попытка использование бэгинга для стабильного алгоритма – логистической регрессии (верхний ряд — соответствующие бутстреп-подвыборки и настроенные на них базовые алгоритмы, нижний — результат бэгинга 10 таких базовых алгоритмов).

pic_ens_03

Рис. 3. Три первых алгоритма бэгинга (вверху) и результат бэгинга (внизу).

Ясно, что неустойчивость связана с большим разбросом (high variance), при этом следует использовать несмещённые алгоритмы (small bias), это гарантирует несмещённость усреднения.

Бэгинг позволяет получать т.н. out-of-bag(OOB)-ответы модели. Идея очень простая: каждый алгоритм обучается на подвыборке, в неё, вообще говоря, попадают не все объекты их обучения, поэтому на остальных объектах можно узнать ответы алгоритма. Все построенные алгоритмы усредняются, по аналогии можно для каждого объекта обучения усреднить ответы алгоритмов, в обучающие выборки которых этот объект не попал:

При достаточном числе базовых алгоритмов мы таким образом оцениваем ответ почти на всех объектах обучения. При этом это «честный» ответ: те алгоритмы, которые участвовали в его формировании «не видели» истинной метки соответствующего объекта.

Аналогично оценивается out-of-bag(OOB)-ошибка бэгинга. Можно оценить ошибку с помощью полученных OOB-ответов, но чаще делают проще: для каждого базового алгоритма ошибку оценивают на объектах, не попавших в его обучение, а затем ошибки усредняют.

Рис. 4. Пример бэгинга для двух нестабильных алгоритмов: решающего дерева и ближайшего соседа.

Случайные леса (Random Forests)

Про это подробно смотрите здесь. Сам алгоритм совмещает идеи бутстрепа и случайных подпространств (Random Subspaces).

ens — Рис. 4. Пример разделения выборки с помощью отдельных деревьев (показаны соответствующие бутстреп-подвыборки) и случайного леса с разным числом деревьев.

Бустинг (Boosting)

Главная идея бустинга – базовые алгоритмы строятся не независимо, каждый следующий мы строим так, чтобы он исправлял ошибки предыдущих и повышал качество всего ансамбля. Первый успешный вариант бустинга – AdaBoost (Adaptive Boosting), сейчас практически не используется, поскольку его вытеснил градиентный аналог. На рис. 5 показано (верхний ряд), как меняются веса объектов при построении очередного базового алгоритма в AdaBoost: объекты, которые классифицировались неправильно первыми двумя алгоритмами при построении третьего имеют большой вес. Основной принцип реализации бустинга – Forward stagewise additive modeling (FSAM). Пусть, например, решается задача регрессии с функцией ошибки L(y, a). Предположим, мы уже построили алгоритм a(x), теперь строим b(x) таким образом, чтобы

Если эту идею применить рекурсивно, получится следующий алгоритм:

f-12

Особенность терминологии, когда говорят о бустинге следующая. Базовые алгоритмы называются «слабыми» (weak learners), а ансамбль – «сильным» алгоритмом (strong learner). Это пошло из теории обучения (learning theory).

boosting — Рис. 5. Базовые алгоритмы AdaBoost (сверху) — размером показан вес объекта при настройке и полученный после 10 итераций бустинг (внизу).

Про градиентый бустинг подробно смотрите здесь. Скорее всего, в этом блоге я ещё отдельно расскажу про AdaBoost.

Cтекинг (Stacking) и блендинг (Blending)

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

ECOC-ансамбли

Про это подробно смотрите здесь. Основная идея — в задаче с l классами сделать специальную кодировку с помощью кода, исправляющего ошибки (Error-Correcting Output Code), например, при l = 4

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

Пусть нам надо классифицировать объект, мы запускаем 6 построенных классификаторов, их ответы записываем в виде бинарного вектора, например, (1,0,1,0,0,0), смотрим по расстоянию Хэмминга, к какой строке матрицы кодировки он ближе. В данном случае — к строке, соответствующей классу 2. Если наш код исправляет одну ошибку, то в случае, если один из классификаторов ошибается, мы всё равно выдаём правильный ответ.

Однородные ансамбли

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

«Советские» ансамбли

Когда-то в блоге меня спрашивали про развитие машинного обучения в СССР и России 90х: развиваемые методы и техники были ортогональны всему, что делалось на Западе (во многом из-за ограничения в коммуникации). В частности, была разработана своя теория ансамблирования, которая получила название алгебраический подход к решению задач распознавания образов. Для её описания нужно делать отдельную заметку в блоге, сейчас — идея.

Рассматривается задача классификации с l классами (их может быть довольно много и они пересекаются), замечается, что каждый алгоритм классификации может быть представлен в виде a(x)=c(b(x)), где b — регрессор, а с — т.н. решающее правило — превращает ответы регрессора в ответы задачи классификации. Например, в байесовском алгоритме мы вычисляем вероятности принадлежности к классам, а потом относим объект к классу с максимальной вероятностью (в задаче с непересекающимися классами) или к классам, вероятность принадлежности к которым выше некоторого порога. Ансамбль строится в виде

т.е. базовые алгоритмы — регрессионные части некоторых разных алгоритмов (из одной модели), b — регрессионная часть мета-алгоритма, с — решающее правило. Ещё в 1977 году (!) в серии работ под названием Корректные алгебры над множествами некорректных (эвристических) алгоритмов Ю.И. Журавлёв доказал, что если брать базовые алгоритмы из достаточно универсальной модели и мета-алгоритм из модели полиномиальной регрессии, а решающее правило зафиксировать пороговым, то в любой разумной задаче (нет противоречивой информации в описаниях объектов и классов) предложенный ансамбль может со 100%-ой точностью классифицировать любую выборку (при соответствующем выборе параметров). Для любопытных лучше сначала прочитать эту статью.

Видео

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

Ссылки

Kaggle ensembling guide (пост в другом блоге на аналогичную тему)
Композиции: бэггинг, случайный лес лекция курса mlcourse.ai
История развития ансамблевых методов классификации в машинном обучении (работа Ю. Кашницкого)
Случайный лес (пост в этом блоге)
Стекинг и блендинг (пост в этом блоге)
Градиентный бустинг (пост в этом блоге)