$\newcommand{\Var}{\operatorname{\mathbb{V}\text{ar}}}$ $\newcommand{\Exp}{\operatorname{\mathbb{E}}}$ $\newcommand{\eps}{\varepsilon}$
Представим, что у вас есть несколько моделей, обученных на ваших данных. Можно ли придумать процедуру, которая позволит использовать все имеющиеся модели и при этом получить на тестовых данных качество выше, чем могла показать каждая из этих моделей в отдельности?
Некоторые картинки в тексте кликабельны. Это означает, что они были заимствованы из какого-то источника, и при клике вы сможете перейти к этому источнику.
Предположим, что мы решаем задачу регрессии с квадратичной функцией потерь. При использовании квадратичной функции потерь для оценки качества работы алгоритма $a$ можно использовать следующий функционал:
\[Q(a) = \Exp_x \Exp_{X, \eps} [y(x, \eps) - a(x, X)]^2,\]где
Для $Q(a)$ существует разложение на три компоненты – шум, смещение и разброс. Это разложение называется bias-variance decomposition, и оно является одним из мощных средств для анализа работы ансамблей. О том, как его вывести, вы узнаете в соответствующей главе, а здесь мы приведём его формулировку.
Bias-variance decomposition . Существует представление $Q(a)$ в виде трёх компонент:
\[Q(a) = \Exp_x \text{bias}_X^2 a(x, X) + \Exp_x \Var_X[a(x, X)] + \sigma^2,\]где
\[\text{bias}_X a(x, X) = f(x) - \Exp_X[a(x, X)]\]– смещение предсказания алгоритма в точке $x$, усреднённого по всем возможным обучающим выборкам, относительно истинной зависимости $f$,
\[\Var_X[a(x, X)] = \Exp_X \left[ a(x, X) - \Exp_X[a(x, X)] \right]^2\]– дисперсия (разброс) предсказаний алгоритма в зависимости от обучающей выборки $X$,
\[\sigma^2 = \Exp_x \Exp_\eps[y(x, \eps) - f(x)]^2\]– неустранимый шум в данных.
Раз нам известно, что ошибка алгоритма раскладывается на шум, смещение и разброс, можно подумать над способом сократить ошибку. Будет разумно попытаться сначала уменьшить одну из составляющих. Понятно, что с шумом уже ничего не сделать – это минимально возможная ошибка. Какую можно придумать процедуру, чтобы, например, сократить разброс, не увеличивая смещение?
Пример приходит из жизни древних греков. Если много древних греков соберутся на одном холме и проголосуют независимо друг от друга, то вместе они придут к разумному решению несмотря на то, что опыт каждого из них субъективен. Аналогом голосования в мире машинного обучения является бэггинг.
Идея бэггинга (bagging, bootstrap aggregation) заключается в следующем. Выберем из обучающей выборки $n$ примеров. Будем выбирать примеры равновероятно, с повторением. Получим новую выборку $X^1$, в которой некоторых элементов исходной выборки не будет, а какие-то могут войти несколько раз. С помощью некоторого алгоритма $b$ обучим на этой выборке модель $b_1(x) = b(x, X^1)$. Повторим процедуру: сформируем вторую выборку $X^2$ из $n$ элементов с возвращением и с помощью того же алгоритма обучим на ней модель $b_2(x) = b(x, X^2)$. Повторив процедуру $k$ раз, получим $k$ моделей, обученных на $k$ выборках. Чтобы получить одно предсказание, усредним предсказания всех моделей:
\[a(x) = \frac{1}{k}(b_1(x) + \dots + b_k(x)).\]Процесс генерации подвыборок с помощью семплирования с возвращением называется бутстрепом (bootstrap), а модели $b_1(x), \ldots, b_k(x)$ часто называют базовыми алгоритмами (хотя, наверное, лучше было бы назвать их базовыми моделями). Модель $a(x)$ называется ансамблем этих моделей.
Посмотрим, что происходит с качеством предсказания при переходе от одной модели к ансамблю. Сначала убедимся, что смещение ансамбля не изменилось по сравнению со средним смещением отдельных моделей. Будем считать, что когда мы берём матожидание по всем обучающим выборкам $X$, то в эти выборки включены также все подвыборки, полученные бутстрепом.
\[\color{#348FEA}{\text{bias}_X a(x, X) =} f(x) - \Exp_X[a(x, X)] = f(x) - \Exp_X \left[ \frac{1}{k} \sum_{i = 1}^k b(x, X^i) \right] =\] \[= f(x) - \frac{1}{k} \sum_{i = 1}^k \Exp_X \left[ b(x, X^i) \right] = f(x) - \frac{1}{k} \sum_{i = 1}^k \Exp_X \left[ b(x, X) \right] = f(x) - \Exp_X b(x, X)\] \[= f(x) - \Exp_X b(x, X) \color{#348FEA}{= \text{bias}_X b(x, X)}\]Получили, что смещение композиции равно смещению одного алгоритма. Теперь посмотрим, что происходит с разбросом.
\[\Var_X[a(x, X)] = \Exp_X \left[ a(x, X) - \Exp_X[a(x, X)] \right]^2 = \\ = \Exp_X \left[ \frac{1}{k} \sum_{i = 1}^k b(x, X^i)- \Exp_X \left[ \frac{1}{k} \sum_{i = 1}^k b(x, X^i) \right] \right]^2 = \\ = \frac{1}{k^2} \Exp_X \left[ \sum_{i = 1}^k \left( b(x, X^i) - \Exp_X b(x, X^i) \right) \right]^2 = \\ = \frac{1}{k^2} \sum_{i = 1}^k \Exp_X (b(x, X^i) - \Exp_X b(x, X^i))^2 + \\ + \frac{1}{k^2} \sum_{k_1 \ne k_2} \Exp_X \left[ \left( b(x, X^{k_1}) - \Exp_X b(x, X^{k_1}) \right) \left( b(x, X^{k_2}) - \Exp_X b(x, X^{k_2}) \right) \right] = \\ = \frac{1}{k^2} \sum_{i = 1}^k \Var_X b(x, X^i) + \frac{1}{k^2} \sum_{k_1 \ne k_2} \text{cov} \left( b(x, X^{k_1}), b(x, X^{k_2}) \right)\]Если предположить, что базовые алгоритмы некоррелированы, то:
\[\color{#348FEA}{\Var_X[a(x, X)] =} \frac{1}{k^2} \sum_{i = 1}^k \Var_X b(x, X^i) = \\ = \frac{1}{k^2} \sum_{i = 1}^k \Var_X b(x, X) \color{#348FEA}{= \frac{1}{k} \Var_X b(x, X)}\]Получилось, что в этом случае дисперсия композиции в $k$ раз меньше дисперсии отдельного алгоритма.
Пусть наша целевая зависимость $f(x)$ задаётся как
\[f(x) = x \sin x,\]и к ней добавляется нормальный шум $\eps \sim \mathcal{N}(0, 9)$. Пример семпла из таких данных:
Попробуем посмотреть, как выглядят предсказания решающих деревьев глубины 7 и бэггинга над такими деревьями в зависимости от обучающей выборки. Обучим решающие деревья 100 раз на различных случайных семплах размера 20. Возьмём также бэггинг над 10 решающими деревьями глубины 7 в качестве базовых классификаторов и тоже 100 раз обучим его на случайных выборках размера 20. Если изобразить предсказания обученных моделей на каждой из 100 итераций, то можно увидеть примерно такую картину:
По этому рисунку видно, что общая дисперсия предсказаний в зависимости от обучающего множества у бэггинга значительно ниже, чем у отдельных деревьев, а в среднем предсказания деревьев и бэггинга не отличаются.
Чтобы подтвердить это наблюдение, мы можем изобразить смещение и разброс случайных деревьев и бэггинга в зависимости от максимальной глубины:
На графике видно, как значительно бэггинг сократил дисперсию. На самом деле, дисперсия уменьшилась практически в 10 раз, что равняется числу базовых алгоритмов ($k$), которые бэггинг использовал для предсказания:
Код для отрисовки картинок и подсчёта смещения и разброса можно найти в этом ноутбуке.
В предыдущем разделе мы сделали предположение, что базовые алгоритмы некоррелированы, и за счёт этого получили очень сильное уменьшение дисперсии у ансамбля относительно входящих в него базовых алгоритмов. Однако в реальной жизни добиться этого сложно: ведь базовые алгоритмы учили одну и ту же зависимость на пересекающихся выборках. Поэтому будет странно, если корреляция на самом деле нулевая. Но на практике оказывается, что строгое выполнение этого предположения не обязательно. Достаточно, чтобы алгоритмы были в некоторой степени не похожи друг на друга. На этом строится развитие идеи бэггинга для решающих деревьев — случайный лес.
Построим ансамбль алгоритмов, где базовый алгоритм — это решающее дерево. Будем строить по следующей схеме:
Построение леса:
Применение леса:
Внимательный читатель мог заметить, что при построении случайного леса у специалиста по машинному обучению есть несколько степеней свободы.
Ошибка модели (на которую мы можем повлиять) состоит из смещения и разброса. Разброс мы уменьшаем с помощью процедуры бэггинга. На смещение бэггинг не влияет, а хочется, чтобы у леса оно было небольшим. Поэтому смещение должно быть небольшим у самих деревьев, из которых строится ансамбль. У неглубоких деревьев малое число параметров, то есть дерево способно запомнить только верхнеуровневые статистики обучающей подвыборки. Они во всех подвыборках будут похожи, но будут не очень подробно описывать целевую зависимость. Поэтому при изменении обучающей подвыборки предсказание на тестовом объекте будет стабильным, но не точным (низкая дисперсия, высокое смещение). Наоборот, у глубоких деревьев нет проблем запомнить подвыборку подробно. Поэтому предсказание на тестовом объекте будет сильнее меняться в зависимости от обучающей подвыборки, зато в среднем будет близко к истине (высокая дисперсия, низкое смещение). Вывод: используем глубокие деревья.
Ограничивая число признаков, которые используются в обучении одного дерева, мы также управляем качеством случайного леса. Чем больше признаков, тем больше корреляция между деревьями и тем меньше чувствуется эффект от ансамблирования. Чем меньше признаков, тем слабее сами деревья. Практическая рекомендация – брать корень из числа всех признаков для классификации и треть признаков для регрессии.
Выше было показано, что увеличение числа элементарных алгоритмов в ансамбле не меняет смещения и уменьшает разброс. Так как число признаков и варианты подвыборок, на которых строятся деревья в случайном лесе, ограничены, уменьшать разброс до бесконечности не получится. Поэтому имеет смысл построить график ошибки от числа деревьев и ограничить размер леса в тот момент, когда ошибка перестанет значимо уменьшаться.
Вторым практическим ограничением на количество деревьев может быть время работы ансамбля. Однако есть положительное свойство случайного леса: случайный лес можно строить и применять параллельно, что сокращает время работы, если у нас есть несколько процессоров. Но процессоров, скорее всего, всё же сильно меньше числа деревьев, а сами деревья обычно глубокие. Поэтому на большом числе деревьев Random Forest может работать дольше желаемого и количество деревьев можно сократить, немного пожертвовав качеством.
Бустинг (boosting) – это ансамблевый метод, в котором так же, как и в методах выше, строится множество базовых алгоритмов из одного семейства, объединяющихся затем в более сильную модель. Отличие состоит в том, что в бэггинге и случайном лесе базовые алгоритмы учатся независимо и параллельно, а в бустинге – последовательно:
Каждый следующий базовый алгоритм в бустинге обучается так, чтобы уменьшить общую ошибку всех своих предшественников. Как следствие, итоговая композиция будет иметь меньшее смещение, чем каждый отдельный базовый алгоритм (хотя уменьшение разброса также может происходить). Поскольку основная цель бустинга – уменьшение смещения, в качестве базовых алгоритмов часто выбирают алгоритмы с высоким смещением и небольшим разбросом. Например, если в качестве базовых классификаторов выступают деревья, то их глубина должна быть небольшой – обычно не больше 2-3 уровней. Ещё одной важной причиной для выбора моделей с высоким смещением в качестве базовых является то, что такие модели, как правило, быстрее учатся. Это важно для их последовательного обучения, которое может стать очень дорогим по времени, если на каждой итерации будет учиться сложная модель. На текущий момент основным видом бустинга с точки зрения применения на практике является градиентный бустинг, о котором подробно рассказывается в соответствующей главе. Хотя случайный лес – мощный и достаточно простой для понимания и реализации алгоритм, на практике он чаще всего уступает градиентному бустингу. Поэтому градиентный бустинг сейчас – основное продакшн-решение, если работа происходит с табличными данными (в работе с однородными данными – картинками, текстами – доминируют нейросети).
Стекинг (stacking) – алгоритм ансамблирования, основные отличия которого от предыдущих состоят в следующем:
Обучение стекинга проходит в несколько этапов:
Для получения мета-факторов на тестовом множестве базовые алгоритмы можно обучить на всём тренировочном множестве – переобучения в данном случае возникнуть не должно.
Если данных достаточно много, то можно просто разделить обучающие данные на две непересекающиеся части: ту, на которой учатся базовые алгортимы, и ту, на которой они делают свои предсказания и обучается мета-модель. Использование такого простого разбиения вместо кросс-валидации на тренировочных данных иногда называют блендингом (blending). Если данных совсем много, то тестовое множество тоже можно разделить на две части: тестовую и валидационную, и использовать последнюю для подбора гиперпараметров моделей-участников :)
С точки зрения смещения и разброса стекинг не имеет прямой интерпретации, так как не минимизирует напрямую ни ту, ни другую компоненту ошибки. Удачно работающий стекинг просто уменьшает ошибку, и, как следствие, её компоненты тоже будут убывать.