Композиционные методы

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

Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Д. Жумабеков 21:27, 19 июля 2026 (MSD)

Содержание

1 Введение
2 Смещение и разброс
3 Простое и взвешенное голосование
4 Бэггинг и случайный лес
5 Стэкинг и смесь экспертов
6 Градиентный бустинг с произвольной функцией потерь
7 Алгоритм градиентного бустинга
8 Практическое применение: прогнозирование оттока клиентов
9 Современные реализации
10 Сравнение методов
11 Литература

Введение

Пусть $X^{\ell} = (x_i, y_i)_{i=1}^{\ell}$ — обучающая выборка, $b_1, \dots, b_T: X \to \mathbb{R}$ — семейство базовых алгоритмов (базовых моделей), каждый из которых по отдельности решает задачу прогнозирования с некоторым, как правило невысоким, качеством. Композиционным методом (ансамблем) называется способ построения итогового алгоритма

$a(x) = C\big(b_1(x), \dots, b_T(x)\big)$

где $C: \mathbb{R}^T \to \mathbb{R}$ — корректирующая (агрегирующая) функция, объединяющая ответы базовых алгоритмов в единый прогноз. Мотивация построения композиции — эмпирический и теоретически обоснованный факт: ошибка согласованно скомбинированных базовых алгоритмов может оказаться существенно ниже ошибки любого из них по отдельности, если базовые алгоритмы допускают разнородные, слабо коррелированные ошибки.

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

Параллельное (одновременное) обучение. Базовые алгоритмы $b_1, \dots, b_T$ обучаются независимо друг от друга, как правило, на различных подвыборках или подпространствах признаков, после чего объединяются корректирующей функцией, не зависящей от процесса обучения базовых моделей. К этому классу относится Бэггинг.
Последовательное обучение. Каждый следующий базовый алгоритм $b_{t+1}$ строится с учётом качества работы уже построенной композиции $b_1, \dots, b_t$ , как правило, с целью исправления её текущих ошибок. К этому классу относится Бустинг.

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

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

Пусть ошибка алгоритма $a$ , обученного по случайной выборке $X^{\ell}$ , измеряется квадратичным функционалом. Усредняя по всем возможным обучающим выборкам фиксированного объёма, ожидаемую квадратичную ошибку алгоритма в точке $x$ можно разложить на три неотрицательных слагаемых:

$\mathsf{E}_{X^{\ell}} \big[ (a(x) - y(x))^2 \big] = \mathrm{Bias}^2(x) + \mathrm{Var}(x) + \sigma^2$

где

$\mathrm{Bias}(x) = \mathsf{E}_{X^{\ell}}\, a(x) - y(x)$

— смещение (bias), систематическое отклонение среднего по выборкам ответа алгоритма от истинной зависимости $y(x)$ , и

$\mathrm{Var}(x) = \mathsf{E}_{X^{\ell}} \big[ (a(x) - \mathsf{E}_{X^{\ell}}\, a(x))^2 \big]$

— разброс (variance), чувствительность ответа алгоритма к конкретной реализации обучающей выборки; $\sigma^2$ — неустранимый шум в данных, не зависящий от выбора алгоритма. Высокое смещение типично для слишком простых, негибких моделей (недообучение), высокий разброс — для слишком гибких моделей, чрезмерно подстраивающихся под конкретную выборку (Переобучение).

Ключевое наблюдение, лежащее в основе композиционных методов: усреднение нескольких некоррелированных алгоритмов с одинаковым смещением снижает разброс композиции пропорционально $1/T$ при $T$ независимых базовых алгоритмах, не увеличивая при этом смещения, — на этом принципе строится Бэггинг. Напротив, последовательная коррекция систематических ошибок предыдущих алгоритмов, лежащая в основе бустинга, направлена в первую очередь на снижение смещения, поскольку каждый следующий базовый алгоритм целенаправленно уменьшает ту часть ошибки, которая систематически не устранена предыдущими членами композиции.

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

Простейшая корректирующая функция для задачи классификации — простое голосование: каждый базовый алгоритм $b_t$ голосует за класс, который он предсказывает, и итоговый ответ определяется классом, набравшим больше всего голосов:

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

Если базовые алгоритмы допускают ошибки независимо друг от друга с вероятностью ошибки $p < 1/2$ каждый, простое голосование нечётного числа таких алгоритмов снижает вероятность ошибки композиции экспоненциально по $T$ — это классический результат, объясняющий эффективность усреднения при низкой скоррелированности ошибок базовых моделей.

Взвешенное голосование обобщает эту схему, приписывая каждому базовому алгоритму вес $w_t \geq 0$ , отражающий степень доверия к нему:

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

Эта конструкция в точности совпадает со схемой агрегирования логических закономерностей в классификаторе на основе набора правил: каждое правило $\varphi_k$ , будучи интерпретируемым бинарным классификатором одного класса, естественно рассматривается как частный случай базового алгоритма $b_t$ , а его вес $w_t$ — как мера информативности правила относительно своего класса. Таким образом, взвешенное голосование правил — частный случай общей схемы композиционных методов, в котором базовые алгоритмы обладают дополнительным свойством интерпретируемости.

Бэггинг и случайный лес

Бэггинг (bagging, bootstrap aggregating) реализует параллельную схему обучения композиции за счёт следующей идеи: вместо обучения единственного алгоритма по всей выборке $X^{\ell}$ строится $T$ независимых алгоритмов $b_1, \dots, b_T$ , каждый из которых обучается по собственной бутстреп-выборке $\widetilde{X}^{\ell}_t$ — выборке объёма $\ell$ , полученной случайным выбором объектов из $X^{\ell}$ с возвращением. Итоговый алгоритм — простое (для регрессии — усреднение, для классификации — голосование) объединение ответов:

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

Поскольку бутстреп-выборки $\widetilde{X}^{\ell}_t$ получены из одного и того же распределения, все $b_t$ имеют приблизительно одинаковое смещение, совпадающее со смещением базового алгоритма, обученного по всей выборке; усреднение при этом снижает разброс композиции без существенного изменения смещения — в полном соответствии с разложением, приведённым в разделе «Смещение и разброс». Бэггинг наиболее эффективен для базовых алгоритмов с высоким разбросом и низким смещением — в первую очередь для глубоких решающих деревьев, не подвергнутых стрижке.

Случайный лес дополняет схему бэггинга решающих деревьев ещё одним источником случайности: при построении каждой вершины дерева оптимальный признак для разбиения ищется не среди всех $n$ признаков, а среди случайно выбранного подмножества из $m \ll n$ признаков (типичный выбор — $m = \sqrt{n}$ для классификации и $m = n/3$ для регрессии). Такое случайное подпространство признаков дополнительно снижает корреляцию между деревьями композиции, что усиливает эффект снижения разброса при усреднении, поскольку эффективность усреднения тем выше, чем слабее коррелированы усредняемые алгоритмы.

Специфическая особенность бэггинга, отсутствующая у последовательных методов, — возможность получить несмещённую оценку ошибки композиции без отдельной контрольной выборки. Поскольку каждая бутстреп-выборка $\widetilde{X}^{\ell}_t$ в среднем содержит около $1 - e^{-1} \approx 63{,}2\%$ исходных объектов, оставшиеся приблизительно $36{,}8\%$ объектов — out-of-bag (OOB) объекты — не участвовали в обучении дерева $b_t$ и могут быть использованы для его тестирования. Усредняя ошибку каждого объекта $x_i$ только по тем деревьям, для которых он был out-of-bag, получают OOB-оценку ошибки композиции:

$Q_{\mathrm{OOB}} = \frac{1}{\ell} \sum_{i=1}^{\ell} L\Big( y_i,\, \frac{1}{|T_i|} \sum_{t \in T_i} b_t(x_i) \Big)$

где $T_i$ — множество индексов деревьев, для которых объект $x_i$ был out-of-bag, а $L$ — функция потерь. OOB-оценка асимптотически эквивалентна оценке по скользящему контролю, но вычисляется за один проход обучения без дополнительных вычислительных затрат.

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

Обобщающий стэкинг (stacking) отказывается от заранее фиксированной корректирующей функции в пользу обучаемой: помимо базовых алгоритмов $b_1, \dots, b_T$ обучается мета-алгоритм $C$ , принимающий на вход вектор ответов базовых алгоритмов $(b_1(x), \dots, b_T(x))$ и обученный предсказывать по нему целевую переменную $y$ :

$a(x) = C\big(b_1(x), \dots, b_T(x)\big), \qquad C = \arg\min_{C} \sum_{i=1}^{\ell} L\big(y_i,\, C(b_1(x_i), \dots, b_T(x_i))\big)$

Принципиальная методологическая трудность стэкинга — необходимость избежать переобучения мета-алгоритма на ответах базовых моделей, вычисленных на тех же объектах, на которых эти модели обучались (в этом случае ответы $b_t(x_i)$ искусственно завышают качество, недостижимое на новых данных). Стандартное решение — вычислять признаки для мета-алгоритма по схеме скользящего контроля: выборка делится на $K$ блоков, для каждого блока базовые алгоритмы обучаются на остальных $K-1$ блоках, а их ответы на отложенном блоке используются как обучающие признаки мета-алгоритма.

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

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

где $c_t(x) \geq 0$ , $\sum_t c_t(x) = 1$ — функции компетентности, показывающие, насколько базовому алгоритму $b_t$ стоит доверять именно в точке $x$ . В отличие от простого взвешенного голосования, где веса $w_t$ постоянны по всему пространству $X$ , здесь вес каждого базового алгоритма может меняться от объекта к объекту.

Смесь экспертов (mixture of experts) формализует эту идею, вводя явную функцию компетентности (gating function) $g_t(x)$ , которая сама является обучаемой моделью, предсказывающей вероятность того, что эксперт $b_t$ компетентен на объекте $x$ :

$a(x) = \sum_{t=1}^{T} g_t(x)\, b_t(x), \qquad g_t(x) = \frac{\exp(v_t(x))}{\sum_{s=1}^{T} \exp(v_s(x))}$

где $v_t(x)$ — некоторая параметрическая функция (как правило, линейная по признакам), обучаемая совместно с экспертами $b_t$ максимизацией правдоподобия композиции. В качестве иллюстрации: пусть имеются два эксперта — $b_1$ , специализирующийся на объектах с малым значением некоторого признака, и $b_2$ , специализирующийся на объектах с большим значением того же признака; тогда обученная функция компетентности $g_1(x)$ будет близка к единице в области малых значений признака и близка к нулю в области больших значений, плавно передавая ответственность за прогноз от одного эксперта к другому в переходной зоне. В отличие от бэггинга и бустинга, смесь экспертов явно моделирует неоднородность признакового пространства, в разных областях которого целесообразны структурно различные модели.

Градиентный бустинг с произвольной функцией потерь

Пусть $L(y, z)$ — произвольная дифференцируемая по $z$ функция потерь (квадратичная для регрессии, логистическая для классификации и так далее), и композиция строится аддитивно:

$a_T(x) = \sum_{t=1}^{T} \alpha_t\, b_t(x)$

Задача обучения композиции состоит в минимизации эмпирического риска

$Q(a) = \sum_{i=1}^{\ell} L\big(y_i, a(x_i)\big) \to \min$

по всем функциям $a$ вида, допускаемого композицией. Прямая минимизация по параметрам сразу всех $T$ базовых алгоритмов, как правило, вычислительно неосуществима; градиентный бустинг решает эту задачу приближённо — как функциональный градиентный спуск в пространстве значений алгоритма на обучающей выборке.

Формально рассмотрим вектор текущего приближения на обучающих объектах

$u = \big( a(x_1), \dots, a(x_\ell) \big) \in \mathbb{R}^{\ell}$

как единственный аргумент функционала $Q(u) = \sum_{i=1}^{\ell} L(y_i, u_i)$ , определённого уже не на пространстве функций, а на конечномерном пространстве $\mathbb{R}^{\ell}$ . Направление наискорейшего убывания $Q(u)$ в точке $u$ задаётся антиградиентом:

$s_i = -\frac{\partial L(y_i, z)}{\partial z}\bigg|_{z = a(x_i)}, \qquad i = 1, \dots, \ell$

Величины $s_1, \dots, s_\ell$ называются псевдо-остатками: это координаты направления, в котором нужно сдвинуть вектор ответов композиции $u$ на обучающих объектах, чтобы наискорейшим образом уменьшить суммарные потери. Если бы значения $a(x)$ в точках $x_1, \dots, x_\ell$ можно было менять независимо друг от друга, оптимальным шагом был бы в точности сдвиг $u \to u + s$ . Однако $a(x)$ должна быть определена не только на обучающих объектах, но и на всём пространстве $X$ , поэтому истинный антиградиент $s$ заменяется его параметрической аппроксимацией — новый базовый алгоритм $b_{T+1}$ обучается решать задачу регрессии на псевдо-остатки:

$b_{T+1} = \arg\min_{b} \sum_{i=1}^{\ell} \big( b(x_i) - s_i \big)^2$

то есть приближает направление антиградиента функцией, обобщающейся на весь $X$ , а не только на обучающие точки. После того как направление $b_{T+1}$ найдено, вдоль него производится одномерный поиск оптимального шага — коэффициента $\alpha_{T+1}$ , минимизирующего исходный функционал потерь вдоль выбранного направления:

$\alpha_{T+1} = \arg\min_{\alpha \in \mathbb{R}} \sum_{i=1}^{\ell} L\big( y_i,\, a_T(x_i) + \alpha\, b_{T+1}(x_i) \big)$

после чего композиция обновляется: $a_{T+1}(x) = a_T(x) + \alpha_{T+1}\, b_{T+1}(x)$ . В отличие от бэггинга, где базовые алгоритмы независимы и минимизация происходит по разбросу, здесь каждый следующий базовый алгоритм целенаправленно устраняет ту часть ошибки, которую не устранили предыдущие, — механизм, последовательно уменьшающий смещение композиции^[1].

Для квадратичной функции потерь $L(y, z) = (y - z)^2$ антиградиент в точке $z = a(x_i)$ равен $s_i = 2(y_i - a(x_i))$ , то есть с точностью до постоянного множителя совпадает с обычными остатками регрессии — отсюда и происходит название «псевдо-остатки» для общего случая произвольной функции потерь.

Алгоритм градиентного бустинга

Вход: обучающая выборка $X^{\ell}$ ; функция потерь $L(y, z)$ ; число итераций $T$ ; темп обучения (learning rate) $\eta \in (0, 1]$ .

Выход: композиция $a_T(x) = \sum_{t=1}^{T} \eta\, \alpha_t\, b_t(x)$ .

Инициализировать начальное приближение константой: $a_0(x) \equiv \arg\min_{z} \sum_{i=1}^{\ell} L(y_i, z)$ .
Для :
1. Вычислить псевдо-остатки на текущем приближении: $s_i = -\partial L(y_i, z) / \partial z \big|_{z=a_{t-1}(x_i)}$ для всех $i = 1, \dots, \ell$ .
2. Обучить базовый алгоритм $b_t$ на задаче регрессии, приближающей псевдо-остатки: $b_t = \arg\min_{b} \sum_{i} (b(x_i) - s_i)^2$ .
3. Найти оптимальный шаг вдоль направления $b_t$ : $\alpha_t = \arg\min_{\alpha} \sum_{i} L(y_i, a_{t-1}(x_i) + \alpha\, b_t(x_i))$ .
4. Обновить композицию с учётом темпа обучения: $a_t(x) = a_{t-1}(x) + \eta\, \alpha_t\, b_t(x)$ .
Вернуть $a_T$ .

Темп обучения $\eta$ , уменьшающий вклад каждого отдельного базового алгоритма, — стандартный инструмент регуляризации градиентного бустинга: меньшие значения $\eta$ требуют большего числа итераций $T$ , но снижают риск переобучения композиции на обучающей выборке. Дополнительными средствами регуляризации служат ограничение глубины базовых деревьев $b_t$ и стохастический вариант алгоритма, в котором на каждой итерации базовый алгоритм обучается по случайной подвыборке объектов и/или признаков — по аналогии с идеей стохастического градиентного спуска, перенесённой из пространства параметров в пространство функций.

Практическое применение: прогнозирование оттока клиентов

Рассмотрим задачу бинарной классификации: по табличным признакам клиента — длительность обслуживания в компании (мес.), число обращений в поддержку за последний квартал, среднемесячный платёж — требуется предсказать, расторгнет ли клиент договор в следующем периоде. Метка класса $y \in \{-1, +1\}$ , где $y=+1$ — отток. В качестве функции потерь используется логистическая функция:

$L(y, z) = \ln\big(1 + e^{-yz}\big)$

для которой антиградиент имеет вид

$s_i = \frac{y_i}{1 + e^{y_i\, a(x_i)}}$

Пусть на первой итерации начальное приближение — константа $a_0(x) \equiv \ln(P_1/P_{-1})$ , где $P_1, P_{-1}$ — доли клиентов с оттоком и без оттока в обучающей выборке (логарифм отношения шансов, минимизирующий логистические потери на константе). Пусть, например, отток наблюдается у 20% клиентов, тогда $a_0(x) \equiv \ln(0{,}2/0{,}8) = \ln 0{,}25 \approx -1{,}386$ для всех клиентов.

Шаг 1. Вычисление псевдо-остатков. Для клиента с меткой $y_i = +1$ (действительно ушёл) псевдо-остаток равен $s_i = 1/(1+e^{-1{,}386}) \approx 0{,}80$ — положительная величина, указывающая, что предсказание нужно сдвинуть в сторону оттока. Для клиента с меткой $y_i = -1$ (остался) псевдо-остаток равен $s_i = -1/(1+e^{-1{,}386}) \approx -0{,}80$ — отрицательная величина, указывающая, что предсказание для такого клиента уже смещено в верном направлении и корректировка должна быть небольшой. Псевдо-остатки вычисляются для каждого клиента обучающей выборки, образуя новую целевую переменную для регрессии.

Шаг 2. Подбор базового алгоритма. На множестве пар (признаки клиента, псевдо-остаток) обучается неглубокое решающее дерево регрессии $b_1(x)$ — например, глубины 2–3, — приближающее псевдо-остатки. Полученное дерево может, к примеру, выделить подгруппу «число обращений в поддержку за квартал больше трёх и длительность обслуживания менее шести месяцев» как область с систематически высоким псевдо-остатком, то есть с высоким риском оттока, не объяснённым текущим (пока константным) приближением.

Шаг 3. Поиск оптимального шага. Для найденного направления $b_1$ решается одномерная задача минимизации логистических потерь по $\alpha_1$ ; поскольку явного решения в замкнутом виде для логистической функции потерь нет, оптимальный шаг находится численно (например, методом Ньютона по одной переменной либо простым одномерным поиском), после чего композиция обновляется: $a_1(x) = a_0(x) + \eta\, \alpha_1\, b_1(x)$ .

Последующие итерации повторяют шаги 1–3, вычисляя псевдо-остатки уже на обновлённом приближении $a_1(x)$ : клиенты, для которых дерево $b_1$ уже дало корректную поправку, получат псевдо-остатки, близкие к нулю, и не будут существенно влиять на обучение $b_2$ , тогда как клиенты со всё ещё неверным прогнозом (например, ушедшие клиенты с низким числом обращений в поддержку, не выделенные деревом $b_1$ ) сформируют псевдо-остатки, на которые нацелится следующее дерево. Итоговый классификатор оттока — знак композиции $a_T(x)$ после $T$ итераций, а величина $1/(1+e^{-a_T(x)})$ интерпретируется как оценка вероятности оттока конкретного клиента.

Современные реализации

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

XGBoost явно включает в критерий построения дерева регуляризационное слагаемое, штрафующее число листьев дерева и величину значений в листьях (аналог $L_1$ / $L_2$ -регуляризации), а также использует приближение вторыми производными функции потерь (аналог метода Ньютона) при выборе структуры дерева, а не только первыми производными (антиградиентом), как в классической схеме Фридмана. Деревья строятся послойно (level-wise) с ограничением максимальной глубины.

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

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

Сравнение методов

Сопоставление бэггинга, бустинга и стэкинга
Критерий	Бэггинг	Бустинг	Стэкинг
Обучение базовых алгоритмов	параллельное, независимое	последовательное, каждый следующий зависит от предыдущих	параллельное для базовых алгоритмов, отдельное для мета-алгоритма
Основной эффект на ошибку	снижает разброс (variance)	снижает смещение (bias)	снижает и смещение, и разброс за счёт обучаемой корректирующей функции
Параллелизуемость обучения	полная	отсутствует (строго последовательная схема)	полная для базовых алгоритмов
Устойчивость к переобучению	высокая при росте $T$	требует регуляризации (темп обучения, глубина деревьев, число итераций)	зависит от корректности схемы скользящего контроля при построении мета-признаков
Типичные базовые алгоритмы	алгоритмы с низким смещением и высоким разбросом (глубокие деревья)	алгоритмы с высоким смещением и низким разбросом (неглубокие деревья)	разнородные по своей природе алгоритмы (деревья, линейные модели, метрические методы)
Интерпретируемость	ниже отдельного дерева, но допускает оценку важности признаков	ниже отдельного дерева, но допускает оценку важности признаков	как правило, наименьшая среди трёх схем из-за дополнительного уровня мета-алгоритма

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B»

Категории: Методы классификации | Энциклопедия анализа данных | Композиционные методы | Ансамблевое обучение