Композиция алгоритмов

Материал из MachineLearning.

Перейти к: навигация, поиск
Статья написана с использованием LLM ChatGPT, GPT-5.6 Thinking и проверена участником Vadim Iamaletdinov 22:19, 19 июля 2026 (MSD)


Содержание

Композиция алгоритмов — алгоритм машинного обучения, объединяющий предсказания нескольких базовых алгоритмов в одно итоговое решение. В англоязычной литературе близкими терминами являются ensemble, ensemble model и combined predictor.

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

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

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

Основное определение

Пусть построены базовые алгоритмы

b_1(x),b_2(x),\ldots,b_T(x).

Композиция имеет вид

a(x)=C(b_1(x),b_2(x),\ldots,b_T(x)),

где C — корректирующая операция, или правило агрегирования.

Правило C может быть:

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

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

Почему композиция может работать лучше

Усреднение случайных ошибок

Пусть регрессионные модели имеют ошибки с одинаковой дисперсией \sigma^2, а попарная корреляция ошибок равна \rho. Для среднего предсказания дисперсия ошибки при упрощающих предположениях равна

{\rm Var}(\overline{b})=\frac{\sigma^2}{T}\left(1+(T-1)\rho\right).

Если ошибки независимы, \rho=0, и дисперсия уменьшается примерно в T раз. Если ошибки полностью совпадают, \rho=1, усреднение не уменьшает дисперсию.

Эта формула показывает два важных свойства хорошего ансамбля:

  • отдельные модели должны быть достаточно точными;
  • их ошибки не должны быть слишком сильно коррелированы.

Снижение нестабильности

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

Именно эта идея лежит в основе бэггинга. Л. Брейман подчёркивал, что бэггинг особенно полезен для методов, предсказания которых значительно меняются при возмущении обучающей выборки.[1]

Исправление систематических ошибок

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

Специализация моделей

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

Простое усреднение

Для регрессии простейшая композиция вычисляет среднее:

a(x)=\frac{1}{T}\sum_{t=1}^{T}b_t(x).

Взвешенное среднее имеет вид

a(x)=\sum_{t=1}^{T}\alpha_tb_t(x),\qquad \sum_{t=1}^{T}\alpha_t=1.

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

Усреднение уменьшает влияние отдельных необычных предсказаний. Однако среднее чувствительно к очень большим ошибкам. В некоторых задачах применяют медиану или усечённое среднее.

Голосование в классификации

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

a(x)=\arg\max_{y\in Y}\sum_{t=1}^{T}[b_t(x)=y].

При взвешенном голосовании:

a(x)=\arg\max_{y\in Y}\sum_{t=1}^{T}\alpha_t[b_t(x)=y].

Голосование по готовым меткам не использует степень уверенности моделей. Если доступны оценки вероятностей, часто лучше усреднять их:

\widehat{P}(y\mid x)=\sum_{t=1}^{T}\alpha_t\widehat{P}_t(y\mid x).

Итоговый класс определяется по максимальной усреднённой вероятности.

Вероятностное усреднение требует согласованного порядка классов и желательно хорошо откалиброванных вероятностей.

Пример голосования

Пусть три классификатора дали ответы:

Алгоритм Предсказанный класс Вероятность класса A
b_1 A 0,90
b_2 B 0,49
b_3 B 0,48

Обычное голосование выбирает класс B, поскольку за него подано два голоса. Средняя вероятность класса A равна

\frac{0.90+0.49+0.48}{3}\approx0.623.

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

Бэггинг

Бэггинг (англ. bootstrap aggregating) строит несколько версий базового алгоритма на бутстрэп-выборках и агрегирует их предсказания.[1]

Для каждого t=1,\ldots,T:

  1. из исходной обучающей выборки создаётся бутстрэп-выборка;
  2. на ней обучается алгоритм b_t;
  3. предсказания всех моделей усредняются или объединяются голосованием.

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

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

Объекты вне бутстрэп-выборки

Для каждого дерева часть обучающих объектов не попадает в его бутстрэп-выборку. Их называют out-of-bag-объектами. Предсказания только тех деревьев, которые не обучались на данном объекте, можно использовать для внутренней оценки качества.

Out-of-bag-оценка не всегда заменяет полноценную внешнюю проверку, особенно если по ней многократно подбирались параметры.

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

Случайный лес объединяет бэггинг деревьев со случайным выбором признаков при построении разбиений.

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

Л. Брейман определил случайный лес как композицию деревьев, зависящих от случайных векторов, одинаково распределённых и независимо сгенерированных для отдельных деревьев.[1]

Качество леса зависит от силы отдельных деревьев и корреляции между ними.[1]

Бустинг

Бустинг строит композицию последовательно. Каждый новый базовый алгоритм добавляется с учётом уже построенной модели:

F_T(x)=\sum_{t=1}^{T}\alpha_tb_t(x).

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

AdaBoost

AdaBoost увеличивает внимание к объектам, на которых текущие базовые классификаторы ошибаются. Для бинарных меток y_i\in\{-1,+1\} веса объектов обновляются по правилу вида

w_i^{(t+1)}=\frac{w_i^{(t)}\exp(-\alpha_ty_ib_t(x_i))}{Z_t},

где Z_t нормирует сумму весов.

Если b_t(x_i) совпадает с y_i, вес объекта уменьшается; при ошибке — увеличивается. Итоговая композиция использует взвешенное голосование.

AdaBoost был выведен Й. Фройндом и Р. Шапиром на основе мультипликативного обновления весов.[1]

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

В градиентном бустинге композиция строится как жадное приближение функции в пространстве базовых алгоритмов. На каждом шаге новый алгоритм приближает направление уменьшения функции потерь.[1]

Для квадратичной ошибки новый базовый алгоритм приближает остатки:

r_i^{(t)}=y_i-F_{t-1}(x_i).

Обновление имеет вид

F_t(x)=F_{t-1}(x)+\eta\alpha_tb_t(x),

где \eta — скорость обучения.

Малые значения \eta обычно требуют большего числа базовых алгоритмов, но позволяют более постепенно строить композицию.

Стекинг

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

Пусть базовые модели создают признаки

z_t(x)=b_t(x),\qquad t=1,\ldots,T.

Модель верхнего уровня получает вектор

z(x)=(z_1(x),\ldots,z_T(x))

и строит итоговое предсказание

a(x)=g(z(x)).

В классификации входами метамодели обычно служат вероятности классов, а не только готовые метки.

Д. Вольперт предложил stacked generalization как способ использовать модель следующего уровня для исправления систематических особенностей базовых алгоритмов.[1]

Предсказания вне обучающей части

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

Правильная схема использует out-of-fold-предсказания:

  1. обучающая выборка делится на части;
  2. для каждой части базовая модель обучается на остальных частях;
  3. сохранённая часть получает предсказания модели, которая её не видела;
  4. все out-of-fold-предсказания объединяются;
  5. по ним обучается метамодель;
  6. для применения базовые модели переобучаются на всей обучающей выборке.

Тестовая выборка не должна использоваться для обучения метамодели.

Блендинг

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

Смесь экспертов

В смеси экспертов веса моделей зависят от объекта:

a(x)=\sum_{t=1}^{T}g_t(x)b_t(x),

где

g_t(x)\geq0,\qquad \sum_{t=1}^{T}g_t(x)=1.

Функции g_t(x) образуют управляющую модель. Она определяет область компетентности каждого эксперта.

Например, один эксперт может специализироваться на коротких временных рядах, другой — на длинных; один — на дневных снимках, другой — на ночных.

Адаптивная смесь локальных экспертов была предложена как обучаемая система, в которой отдельные сети осваивают разные подзадачи, а управляющая сеть распределяет объекты между ними.[1]

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

Ансамбли нейронных сетей

Несколько нейронных сетей можно обучить:

  • с разными случайными инициализациями;
  • на разных подвыборках;
  • с разными архитектурами;
  • с разными преобразованиями данных;
  • с разными функциями потерь или гиперпараметрами.

Их вероятности или числовые предсказания затем усредняются.

Глубокие ансамбли применяются не только для повышения точности, но и для оценивания неопределённости. Разброс предсказаний между сетями может указывать на области, где модели не согласны. Работа Лакшминараянана, Притцеля и Бланделла показала, что ансамбль независимо обученных нейронных сетей может давать полезные оценки предсказательной неопределённости.[1]

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

Однородные и неоднородные композиции

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

Неоднородная композиция объединяет разные семейства моделей, например:

  • логистическую регрессию;
  • градиентный бустинг;
  • нейронную сеть;
  • метод ближайших соседей.

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

Разнообразие базовых алгоритмов

Композиции полезны не из-за количества моделей само по себе, а из-за сочетания качества и разнообразия.

Разнообразие создаётся с помощью:

  • различных обучающих подвыборок;
  • различных наборов признаков;
  • случайной инициализации;
  • разных архитектур;
  • разных функций потерь;
  • разных параметров регуляризации;
  • разных преобразований данных;
  • последовательного обучения на ошибках;
  • специализации по областям пространства объектов.

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

Смещение и разброс

Ошибка модели часто рассматривается через компромисс между смещением и разбросом.

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

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

Калибровка вероятностей

Средняя вероятность ансамбля нередко оказывается стабильнее вероятности одной модели, но калибровка не гарантирована.

Для проверки применяются:

  • калибровочные кривые;
  • логарифмическая функция потерь;
  • мера Брайера;
  • показатели ожидаемой ошибки калибровки.

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

Выбор весов

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

  • одинаковыми;
  • пропорционально качеству;
  • оптимизацией функции потерь;
  • с ограничением неотрицательности;
  • с регуляризацией;
  • с зависимостью от объекта.

Для регрессии веса могут подбираться по задаче

\min_{\alpha}\sum_{i=1}^{\ell}L\left(y_i,\sum_{t=1}^{T}\alpha_tb_t(x_i)\right).

Чтобы уменьшить риск нестабильных компенсаций, можно потребовать

\alpha_t\geq0,\qquad \sum_{t=1}^{T}\alpha_t=1.

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

Выбор порога

В бинарной классификации композиция может выдавать вероятность положительного класса. Решение принимается по порогу \tau:

a(x)=[\widehat{P}(y=1\mid x)\geq\tau].

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

Порог подбирается на проверочных данных после построения композиции.

Корректный эксперимент

Для честной проверки композиции необходимо:

  • использовать одинаковые разбиения для всех базовых моделей;
  • отделять обучение базовых моделей от обучения правила объединения;
  • строить out-of-fold-признаки для стекинга;
  • не использовать тестовые ответы при выборе состава ансамбля;
  • сравнивать с лучшей одиночной моделью;
  • учитывать время, память и задержку;
  • повторять эксперимент при нескольких случайных разбиениях;
  • проверять качество на значимых подгруппах.

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

Пример корректного стекинга

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

  1. Для каждой из пяти частей модели обучаются на остальных четырёх.
  2. На отложенной части сохраняются три предсказания.
  3. После пяти проходов каждый обучающий объект имеет три out-of-fold-признака.
  4. По этим признакам обучается метамодель.
  5. Каждая базовая модель переобучается на всей обучающей выборке.
  6. Для тестового объекта вычисляются три базовых предсказания.
  7. Метамодель объединяет их в итоговый ответ.

Если вместо out-of-fold-признаков использовать предсказания на обучающих объектах, сложная базовая модель может почти идеально запомнить выборку, и метамодель получит нереалистичные входы.

Типичные ошибки

Простое добавление большого числа похожих моделей

Если модели почти одинаковы, выигрыш быстро насыщается.

Выбор весов по тестовой выборке

Тестовая выборка становится частью обучения, а итоговая оценка завышается.

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

Метамодель учится на слишком оптимистичных результатах и плохо переносится на новые данные.

Усреднение несопоставимых выходов

Одна модель может выдавать вероятности, другая — необработанные оценки. Перед объединением необходимо привести выходы к согласованному смыслу.

Разный порядок классов

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

Отсутствие базового сравнения

Без оценки отдельных моделей неизвестно, принесла ли композиция пользу.

Игнорирование стоимости

Композиция из десятков моделей может быть непригодна для системы реального времени.

Усреднение моделей с общей систематической ошибкой

Ансамбль не исправит проблему, если все модели используют один ошибочный признак или одинаково смещённые данные.

Преимущества

Композиции алгоритмов позволяют:

  • уменьшать разброс предсказаний;
  • использовать сильные стороны разных моделей;
  • повышать устойчивость к случайным изменениям выборки;
  • строить сложные зависимости из простых компонентов;
  • оценивать неопределённость по расхождению моделей;
  • разделять пространство объектов между экспертами;
  • получать более высокое качество без разработки одного чрезвычайно сложного алгоритма.

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

Ограничения

Вычислительная стоимость

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

Сложность интерпретации

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

Сложность воспроизводимости

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

Уязвимость к утечке

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

Общая систематическая ошибка

Если все модели обучены на одних смещённых данных, ансамбль может уверенно воспроизводить это смещение.

Сложность обновления

При поступлении новых данных может потребоваться переобучать несколько моделей и правило объединения. Необходимо контролировать совместимость их версий.

Практический выбор метода

Условия Возможный подход Причина
Нестабильная модель и достаточный вычислительный бюджет Бэггинг Уменьшение разброса
Табличные данные и деревья Случайный лес или градиентный бустинг Хорошее моделирование нелинейностей и взаимодействий
Несколько сильных разных моделей Усреднение или стекинг Использование различий в ошибках
Разные модели полезны для разных объектов Смесь экспертов Зависимые от объекта веса
Большие нейронные сети Небольшой глубокий ансамбль Точность и оценка неопределённости
Жёсткое ограничение задержки Одна модель или дистилляция композиции Снижение стоимости применения

Таблица задаёт отправные варианты. Окончательный выбор должен определяться экспериментом и ограничениями системы.

Сжатие композиции

Большую композицию иногда заменяют одной более компактной моделью. Такой процесс называют дистилляцией знаний.

Модель-ученик обучается воспроизводить ответы композиции, включая вероятности классов или числовые оценки. Это позволяет уменьшить задержку и память, но ученик может потерять часть качества и неопределённости ансамбля.

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

Применения

Композиции алгоритмов применяются:

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

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

История

Объединение нескольких правил принятия решений появилось задолго до современного машинного обучения. В статистике использовались усреднение оценок и объединение прогнозов, а в распознавании образов — голосование классификаторов.

В 1991 году была описана адаптивная смесь локальных экспертов с обучаемым управляющим механизмом.[1] В 1992 году Д. Вольперт предложил stacked generalization.[1]

В 1996 году Л. Брейман представил бэггинг как построение и агрегирование моделей по бутстрэп-выборкам.[1] В 1997 году Й. Фройнд и Р. Шапир опубликовали алгоритм AdaBoost и его теоретическое обоснование.[1]

В 2001 году были опубликованы работы о случайных лесах и градиентном бустинге, ставших основными ансамблевыми методами для табличных данных.[1][1]

В дальнейшем композиции распространились на глубокие нейронные сети, оценивание неопределённости, мультимодальные модели и крупные системы машинного обучения.[1]

См. также

Примечания


Литература

  • Jacobs R. A., Jordan M. I., Nowlan S. J., Hinton G. E. Adaptive Mixtures of Local Experts // Neural Computation. — 1991. — Т. 3. — № 1. — С. 79—87.
  • Wolpert D. H. Stacked Generalization // Neural Networks. — 1992. — Т. 5. — № 2. — С. 241—259.
  • Breiman L. Bagging Predictors // Machine Learning. — 1996. — Т. 24. — № 2. — С. 123—140.
  • Freund Y., Schapire R. E. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting // Journal of Computer and System Sciences. — 1997. — Т. 55. — № 1. — С. 119—139.
  • Breiman L. Random Forests // Machine Learning. — 2001. — Т. 45. — № 1. — С. 5—32.
  • Friedman J. H. Greedy Function Approximation: A Gradient Boosting Machine // The Annals of Statistics. — 2001. — Т. 29. — № 5. — С. 1189—1232.
  • Lakshminarayanan B., Pritzel A., Blundell C. Simple and Scalable Predictive Uncertainty Estimation Using Deep Ensembles // Advances in Neural Information Processing Systems. — 2017. — Т. 30.
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2»
Личные инструменты