Разбираемся в ML без воды: от базы до Attention. Часть 10: Бэггинг и случайный лес

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

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

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

кто скажет, что это девочка, пусть первый бросит в меня камень (с)

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

Бэггинг (Bagging)

Бэггинг — это просто сокращение от двух слов: Bootstrap + Aggregating. Идея крайне проста: если одно дерево решений сильно страдает от малейшего изменения в данных, давайте создадим целую толпу таких деревьев, а потом просто усредним их ответы.

Но есть один нюанс: Если мы дадим сотне деревьев один и тот же датасет, они вырастут абсолютно одинаковыми. Далее они нам выдадут одинаковые ответы и после усреднения мы поймем, что просто потратили вычислительные ресурсы.

Следовательно, нам нужно сделать эти деревья разными. И вот тут включается Bootstrap.

Bootstraping

Bootstraping (бутстрапирование) — это генерация повторной выборки с возвращением.

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

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

Вероятность не выбрать конкретную строку из за одну попытку равна $1-\frac{1}{N}$

Следовательно, вероятность, что конкретная строка не попадет в копию датасета:

$P = \left(1-\frac{1}{N}\right)^N \xrightarrow[N \to \infty]{} \frac{1}{e} \approx 0.368$

Здесь используется второй замечательный предел (точнее его следствие): $\lim_{n\to\infty}\left(1 + \frac{x}{n}\right)^n = e^x$

Сразу заметим, что хоть предельный переход невозможен на практике (у нас нет бесконечного датасета), но даже при скромных 1000 строках значение получается примерно 0.3677.

Следовательно, примерно 37% данных не попадают в обучение каждого конкретного дерева. Говоря иначе, условная строка номер 1 не попала в 37% деревьев. Отсюда возникает идея: Мы можем попросить именно эти деревья предсказать значение для строки №1 и усреднить их ответы.

Повторив это для каждой строки датасета в итоге получим честную метрику качества по имени Out-of-bag score (OOB-score). Она ничем не уступает валидации на отложенной выборке или кросс-валидации, но считается прямо в процессе обучения. Кроме того, нам больше не нужен train_test_split, а значит, модель будет обучаться на большем количестве данных, что, безусловно, хорошо.

Aggregating

С первой частью слова (Bootstrap) мы разобрались: данные размножили, деревья вырастили, они получились разными и даже в качестве бонуса OOB-метрику из этого извлекли. Теперь разберемся со второй частью — Aggregating (агрегирование).

У нас есть много обученных деревьев. Мы подаем им на вход новый объект (например, параметры квартиры) и хотим получить один финальный ответ. Но как нам это сделать?

Здесь всё зависит от того, какую задачу мы решаем:

1. Задача регрессии:
Если мы предсказываем цену квартиры, мы просто опрашиваем каждое дерево, получаем от них конкретные суммы (одно сказало 10 млн, второе — 12 млн, третье — 11 млн). Просто берем обычное среднее арифметическое. Случайные завышения одних деревьев компенсируют случайные занижения других, и на выходе получается стабильный адекватный ценник.

2. Задача классификации:
Если мы хотим узнать, стоит покупать квартиру или нет, у нас есть два пути:

Жесткое голосование (Hard Voting): Каждое дерево выдает свой вердикт. Мы подсчитываем голоса и выбираем победителя большинством. Если 70 деревьев сказали «Да», а 30 сказали «Нет» — ансамбль выдает ответ «Да».
Мягкое голосование (Soft Voting): Мы берем не окончательный ответ дерева, а вероятность. Например, первое дерево говорит: «с вероятностью 80% квартиру стоит покупать». Мы усредняем эти вероятности по всем деревьям. Этот способ на практике работает лучше, потому что учитывает степень уверенности каждого отдельного дерева. С другой стороны, для этого необходимо, чтобы деревья были способны оценивать вероятности классов (predict_proba). В scikit-learn, например, такое есть по дефолту.

Насколько эффективен бэггинг

Идея бэггинга достаточно простая, но давайте посмотрим на его эффективность. Раз мы ввели этот метод, чтобы снизить дисперсию, посмотрим насколько она изменилась.

Включим базовую теорию вероятностей. Представим идеальный мир, где все наши обученные деревья выдают предсказания абсолютно независимо друг от друга. Допустим, у каждого отдельного дерева дисперсия (тот самый разброс и нестабильность) равна $\sigma ^{2}$ .

Когда мы объединяем таких независимых деревьев, мы берем среднее арифметическое их ответов:

$\overline{x}=\frac{1}{n}\sum_{i=1}^{n}x_{i}$

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

$\text{Var}(\overline{x})=\text{Var}\left(\frac{1}{n}\sum_{i=1}^{n}x_{i}\right)=\frac{1}{n^{2}}\sum_{i=1}^{n}\text{Var}(x_{i})=\frac{1}{n^{2}}\cdot n\ \cdot \sigma ^{2}=\frac{\sigma ^{2}}{n}$

Вывод: если базовые модели независимы, то бэггинг снижает дисперсию всей модели ровно в раз (где — количество деревьев в ансамбле). При этом смещение (bias) алгоритма вообще не страдает. Мы буквально бесплатно срезали хаос.

Однако реальный мир суров. Наши деревья не могут быть на 100% независимыми, ведь мы собирали их бутстрэпом из одного и того же исходного датасета. Они всё равно немного коррелируют между собой. Из-за этой корреляции (обозначим её как $\rho$ ) реальная формула разброса выглядит чуть сложнее:

$\text{Var}(\overline{x})=\rho \sigma ^{2}+\frac{1-\rho }{N}\sigma ^{2}$

Почему именно так?

Мы ищем дисперсию среднего арифметического одинаково распределенных случайных величин $x_{i}$ , каждая из которых имеет дисперсию $\text{Var}(x_i) = \sigma^2$ , а коэффициент корреляции между любыми двумя разными моделями равен $\rho$ (то есть $\text{Cov}(X_i, X_j) = \rho \sigma^2$ , для $i \neq j$ ).

Формула дисперсии суммы с учетом ковариации:

$\text{Var}\left(\frac{1}{n}\sum_{i=1}^{n}x_{i}\right)=\frac{1}{n^{2}}\text{Var}\left(\sum_{i=1}^{n}x_{i}\right) =\sum_{i=1}^{n}\text{Var}(x_{i})+\sum_{i\ne j}\text{Cov}(x_{i},x_{j})$
Считаем слагаемые:
- Собственных дисперсий ровно штук. Каждая равна $\sigma^{2}$ . Суммарно будет $n\sigma^2$ .
- Попарных ковариаций в квадратной матрице $n \times n$ (без учета главной диагонали) ровно штук. Каждая равна $\rho\sigma^2$ . Суммарно — $n(n-1)\rho\sigma^2$ .
Подставляем это обратно:

$\text{Var}(\overline{x})=\frac{1}{n^{2}}\left[n\sigma ^{2}+n(n-1)\rho \sigma ^{2}\right]$
Раскрываем скобки и делим на $n^{2}$ :

$\text{Var}(\overline{x})=\frac{\sigma^{2}}{n}+\frac{n-1}{n}\rho \sigma^{2}=\frac{\sigma ^{2}}{n}+\left(1-\frac{1}{n}\right)\rho \sigma ^{2}$
Группируем слагаемые, чтобы получить классический вид:

$\text{Var}(\overline{x})=\rho \sigma ^{2}+\frac{1-\rho }{n}\sigma ^{2}$

Формула наглядно показывает потолок бэггинга: сколько бы деревьев () мы ни добавляли, даже если второе слагаемое обнулится, мы всё равно получим остаток $\rho\sigma^2$ . А базовые деревья обычно сильно коррелируют ( $\rho$ высокое) из-за наличия доминантных признаков в данных.

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

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

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

Что произойдет в бэггинге? Мы запускаем обучение 100500 деревьев. Безусловно, бутстрэп подсунул каждому дереву свою уникальную выборку строк. Но признак «общая площадь» настолько силен, что он будет доминировать в любой случайной подвыборке.

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

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

Чтобы спасти ситуацию, нужно придумать, как запретить деревьям быть почти одинаковыми.

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

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

Работает это так: когда дерево собирается сделать очередной сплит, мы запрещаем ему смотреть на весь список признаков. В каждом конкретном узле при каждом делении мы даем ему доступ к части признаков (например, 2 из 5) и заставляем работать при таком ограничении. В этом и есть суть случайного леса.

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

Естественно, возникает вопрос: а сколько конкретно признаков нужно выдавать дереву на каждом шаге? Если дать слишком мало (например, всего 1 признак из 100), деревья станут совсем слепыми и бесполезными. Если дать слишком много — мы вернемся к проблеме бэггинга.

Здесь есть золотой стандарт. Пусть — это общее количество признаков в нашем датасете. Для классификации обычну берут $\sqrt{d}$ признаков, а для регрессии — .

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

Также, грех не упомянуть, что в бэггинге и случайном лесе базовые деревья всегда обучаются максимально глубокими (пока в листах не останется по 1 объекту). У них должно быть низкое смещение (low bias) и огромный разброс (high variance). Это принципиально отличает лес от бустинга (о котором поговорим уже в следующей статье).

К слову, наравне с бэггингом, у случайного леса тоже есть приятный бонус: случайный лес попутно решает еще одну важную задачу — он вычисляет важность признаков (Feature Importance).

Нам больше не нужно гадать, что сильнее влияет на цену квартиры: район или год постройки. Лес сам посчитает, насколько сильно каждый признак снижает хаос и неопределенность (критерий Джини или MSE) при разделении узлов. Чем чаще признак помогал деревьям делать точные сплиты, тем выше будет его финальный рейтинг важности.

Однако, случайный лес, несмотря на всю свою мощь, далеко не идеален. У него есть два основных минуса:

Проблема экстраполяции

Об этом мы говорили еще при обсуждении деревьев. Математика деревьев устроена так, что они не умеют строить тренды и экстраполировать зависимости (в отличие от линейной регрессии). Дерево просто делит данные на части и усредняет ответы внутри них. Оно физически не способно выдать число больше, чем максимальный ответ из обучающей выборки.
Память и скорость

Случайный лес — это огромная сущность. Чтобы получить один ответ, нам нужно прогнать объект через сотни глубоких разветвленных деревьев. Если датасет был большим, готовая модель в сохраненном виде (.pkl файл) может весить несколько гигабайт и безбожно жрать оперативную память на сервере. Для систем, где ответ нужно отдавать за миллисекунды (например, высоконагруженный веб или баннеры в реальном времени), он часто оказывается слишком медленным.

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

Идеальная параллелизация:

Поскольку все наши 100500 деревьев строятся на своих бутстрэп-выборках абсолютно независимо друг от друга, им не нужно ждать результатов других. Алгоритм можно сходу запустить на полную мощность на всех ядрах процессора (в scikit-learn за это отвечает один параметр n_jobs=-1). Модель обучается невероятно быстро.

Иммунитет к количеству деревьев:

Случайный лес физически не способен переобучиться из-за того, что мы добавили в него слишком много деревьев. Мы можем посадить хоть 500, хоть 100500 деревьев — в какой-то момент ошибка модели просто замрет. Единственное, что можно потерять при бесконечном увеличении ансамбля — это время на обучение и место на диске.

Последнее утверждение имеет название — Теорема о сходимости случайного леса, которую Лео Брейман сформулировал и доказал в своей основополагающей статье «Random Forests» (2001). Посмотрим, как она работает.

Теорема о сходимости случайного леса

Каждое дерево в ансамбле полностью определяется вектором признаков объекта и случайным вектором $\Theta_{k}$ , который задает весь рандом (какие строки попали в бутстрэп и какие признаки выбраны в узлах). Случайные векторы $\Theta_1, \Theta_2, \dots, \Theta_n$ независимы и одинаково распределены.

Пусть классификатор (дерево) выдает ответ $h(X, \Theta_k)$ . Финальное предсказание леса из деревьев для объекта определяется голосованием большинства.

Введем функцию отрыва (margin function), которая измеряет, насколько среднее число голосов за правильный класс превосходит максимальное число голосов за любой другой неверный класс :

$mr(X,Y)=\frac{1}{n}\sum_{i=1}^{n}I\big[h(X,\Theta {i})=Y\big]-\max_{V\ne Y}\frac{1}{n}\sum_{i=1}^{n}I\big[h(X,\Theta _{i})=V\big]$

(Здесь $I[\cdot]$ — индикаторная функция, равная 1, если условие верно, и 0, если неверно).

Ансамбль ошибается тогда и только тогда, когда большинство деревьев проголосовало за неверный класс. Это эквивалентно ситуации, когда функция отрыва становится меньше нуля — $\text{mr}(X, Y) < 0$ . Соответственно, ошибка обобщения леса (generalization error) — это вероятность такого события по всему распределению данных :

$PE^{*}=P_{X,Y}\Big(mr(X,Y)<0\Big)$

Теперь применим к обоим слагаемым внутри функции отрыва Усиленный закон больших чисел (УЗБЧ). Так как векторы $\Theta _{i}$ независимы и одинаково распределены, то при фиксированных и устремлении количества деревьев к бесконечности ( $n \to \infty$ ) среднее арифметическое индикаторов почти наверняка (a.s.) сходится к их математическому ожиданию по распределению вектора $\Theta$ :

$\frac{1}{n}\sum_{i=1}^{n}I\big(h(X,\Theta_{i})=Y\big) \xrightarrow[n\rightarrow \infty]{a.s.}\mathbb{E}_{\Theta }\Big[I\big(h(X,\Theta )=Y\big)\Big]=P_{\Theta }\big(h(X,\Theta )=Y\big)$

Аналогично для любого неверного класса :

$\frac{1}{n}\sum_{i=1}^{n}I\big(h(X,\Theta_{i})=V\big)\xrightarrow[n\rightarrow \infty]{a.s.}P_{\Theta }\big(h(X,\Theta )=V\big)$

Следовательно, при $n \to \infty$ функция отрыва всего леса почти наверняка сходится к предельной функции отрыва:

$mr(X,Y)\xrightarrow[n\rightarrow \infty]{a.s.} P_{\Theta }\big(h(X,\Theta )=Y\big)-\max_{V\ne Y}P{\Theta }\big(h(X,\Theta )=V\big)$

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

$PE^{*}\xrightarrow[n\rightarrow \infty]{a.s.} P_{X,Y}\left(P_{\Theta }\big(h(X,\Theta )=Y\big)-\max_{V\ne Y}P_{\Theta }\big(h(X,\Theta )=V\big)<0\right)$

Что это значит простыми словами? При бесконечном увеличении количества деревьев хаос и случайность самого алгоритма исчезают, а доля проголосовавших деревьев превращается в фиксированную константу (чистую вероятность). Общая ошибка cлучайного леса не улетает в космос։ она остановится на своем теоретическом пределе.

Заключение

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

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

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

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

ссылка на оригинал статьи https://habr.com/ru/articles/1045016/