Случайный лес — модель, которая не может переобучиться

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

Эхо-камера

В шоу “Кто хочет стать миллионером” игрок должен ответить на серию вопросов с четырьмя вариантами ответа. Игрок может использовать подсказки: позвонить другу, который разбирается в теме, или попросить помощь зала. Если игрок выбирает помощь зала, каждый зритель голосует за вариант ответа, а игроку показывают распределение голосов. По статистике шоу за 15 лет помощь зала дает правильный ответ в 91% случаев, а звонок другу — только в 65% случаев.

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

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

В 80-е и 90-е развивалась теория решающих деревьев. Решающие деревья были компромиссом между экспертными системами, в которых решение задачи вводилось вручную, и машинным обучением, где решение определялось по данным. Решающие деревья автоматически извлекали из данных экспертные правила для решения задачи. У одиночных деревьев были проблемы с переобучением, и исследователи обратили внимание на потенциал объединения деревьев в ансамбли. Специалистка по computer science Тин Кам Хо предложила свою версию ансамбля в 1995 году и ввела термин “случайный решающий лес”. Автор одного из алгоритмов обучения решающих деревьев — статистик Лео Бре́йман — предложил свою версию в 2001 году и сократил название до “случайный лес”.

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

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

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

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

Соберем лес из решающих деревьев. Будем предсказывать вероятность диабета по данным медицинского скрининга. Данные 300 пациентов для обучения находятся в файле ↓ train.csv тестовая выборка из 478 пациентов находится в файле ↓ test.csv.

Инициализируем новый проект и установим зависимости — Pandas и Scikit-learn:

uv init
uv add pandas scikit-learn

Импортируем Pandas для работы с данными и загрузим данные из обоих файлов. Выделим матрицу признаков для обучения — все колонки, кроме целевой колонки “диабет”, и вектор целевых значений — оставшаяся колонка. Повторим те же действия для тестовой выборки:

import pandas as pd

train_data = pd.read_csv("data/train.csv")
test_data = pd.read_csv("data/test.csv")

X_train = train_data.drop(columns=["diabetes"])
y_train = train_data["diabetes"]
X_test = test_data.drop(columns=["diabetes"])
y_test = test_data["diabetes"]

Обучим одно дерево. Импортируем из Scikit-learn реализацию решающего дерева для задач классификации — DecisionTreeClassifier. Инициализируем дерево с параметрами по умолчанию — они не ограничивают рост дерева. Обучим дерево на выборке обучения и посчитаем точность на выборке обучения и тестовой выборке. Выведем оба значения в процентах:

import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

train_data = pd.read_csv("data/train.csv")
test_data = pd.read_csv("data/test.csv")

X_train = train_data.drop(columns=["diabetes"])
y_train = train_data["diabetes"]
X_test = test_data.drop(columns=["diabetes"])
y_test = test_data["diabetes"]

model = DecisionTreeClassifier()
model.fit(X_train, y_train)

train_accuracy = accuracy_score(y_train, model.predict(X_train))
test_accuracy = accuracy_score(y_test, model.predict(X_test))

print(f"Точность (обучение): {train_accuracy:.1%}")
print(f"Точность (валидация): {test_accuracy:.1%}")

Запустим обучение с помощью команды:

uv run train.py

Точность (обучение): 100.0%
Точность (валидация): 68.4%

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

Превратим одно решающее дерево в решающий лес. Создадим переменную predict для подсчета вероятности диабета у пациентов из тестовой выборки — инициализируем ее нулями. Обучим 100 деревьев в цикле и добавим предсказание каждого дерева к переменной predict. После цикла в ней будет количество голосов, которые деревья суммарно присвоили каждому пациенту. Для получения вероятности разделим голоса на количество деревьев. Округлим результат, чтобы получить окончательное предсказание леса, и выведем его точность:

import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

train_data = pd.read_csv("data/train.csv")
test_data = pd.read_csv("data/test.csv")

X_train = train_data.drop(columns=["diabetes"])
y_train = train_data["diabetes"]
X_test = test_data.drop(columns=["diabetes"])
y_test = test_data["diabetes"]

predict = pd.Series(0, index=y_test.index)

for _ in range(100):
    model = DecisionTreeClassifier()
    model.fit(X_train, y_train)
    predict += model.predict(X_test)

test_accuracy = accuracy_score(y_test, (predict / 100).round())
print(f"Точность: {test_accuracy:.1%}")

Точность: 68.3%

Наша реализация леса не сработала — точность леса не выросла по сравнению с точностью одного дерева. Если сравнить предсказания деревьев друг с другом, мы увидим, что в 81% случаев все 100 деревьев дают ответ единогласно. Это противоречит идее независимого голосования — большинство деревьев делает одинаковые предсказания и одинаковые ошибки.

Что-то из ничего

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

Добавление одной точки в правом верхнем углу разрешает ничью в пользу деления по горизонтали

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

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

Каждый альтернативный вариант ветвления приводит к новым вариантам ветвления в дочерних узлах. Вложенные варианты выбора создают комбинаторный взрыв: каждое дерево получается уникальным. Но так как деревья отличаются только в глубоких узлах, их предсказания расходятся незначительно — большая часть голосов совпадает. Детерминизм решающего дерева — причина, по которой разные исследователи добавляли в название решающего леса слово “случайный”: случайность леса должна быть искусственной.

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

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

Разделить выборку поровну между сотней деревьев невозможно — части получатся слишком маленькими. Для решения этой проблемы используют бутстрап. Бутстрап позволяет извлечь из одного набора данных сколько угодно наборов того же размера. Этот метод придумал математик Брэдли Эфрон в 1979 году. По задумке Эфрона название метода отсылает к истории с бароном Мюнхгаузеном, в которой он смог вытянуть себя из болота за косичку. Тот же образ закрепился в выражении “вытащить себя за петли ботинок” — bootstraps — то есть, сделать что-то невозможное без чужой помощи.

Рассмотрим бутстрап на примере. Возьмем набор данных x1, который состоит из чисел от 1 до 5. Создадим из него новый набор данных x2 с помощью бутстрапа. Для этого выберем случайный элемент из x1 и переложим его в x2. Повторим это действие по одному разу на каждый элемент в x1 и выведем результат:

import random

x1 = [1, 2, 3, 4, 5]

x2 = []

for i in range(len(x1)):
    x = random.choice(x1)
    x2.append(x)

print(x2)

Запустим код несколько раз:

[1, 1, 2, 2, 4]
[5, 3, 2, 1, 1]
[4, 1, 2, 5, 3]

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

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

P(\text{попал}) = \frac{1}{n}.

Вероятность того, что он не попадет в выборку, равна:

P(\text{не попал}) = - \frac{1}{n}.

Вероятность того, что он не попадет в выборку при каждой из $n$ попыток, равна:

P(\text{ни разу не попал}) = \left( 1 - \frac{1}{n} \right)^n.

Если размер выборки $n$ достаточно большой, мы можем использовать второй замечательный предел:

\lim_{n \rightarrow \infty} \left( 1 - \frac{1}{n}\right )^n = \frac{1}{e} \approx 0.368.

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

В Pandas бутстрап выборку можно получить с помощью метода .sample() объектов Series и DataFrame. Передадим методу размер новой выборки, равный размеру исходной, и параметр replace со значением True — он включает возврат элементов. Выведем три случайные бутстрап выборки:

import pandas as pd

x1 = pd.Series([1, 2, 3, 4, 5])

for _ in range(3):
    x2 = x1.sample(n=len(x1), replace=True)
    print(x2.values)

array([2, 4, 1, 5, 4])
array([5, 4, 4, 3, 1])
array([2, 5, 1, 1, 1])

Обучим лес заново, но создадим бутстрап выборку для каждого дерева. Для этого вызовем метод .sample() набора данных train_data, чтобы получить бутстрап выборку train_data_sample. Выделим из выборки матрицу признаков и вектор целевых значений. Оставшуюся часть обучения оставим без изменений:

import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

train_data = pd.read_csv("data/train.csv")
test_data = pd.read_csv("data/test.csv")

X_test = test_data.drop(columns=["diabetes"])
y_test = test_data["diabetes"]

predict = pd.Series(0, index=y_test.index)

for _ in range(100):
    train_data_sample = train_data.sample(n=len(train_data), replace=True)
    X_train = train_data_sample.drop(columns=["diabetes"])
    y_train = train_data_sample["diabetes"]

    model = DecisionTreeClassifier()
    model.fit(X_train, y_train)
    predict += model.predict(X_test)

test_accuracy = accuracy_score(y_test, (predict / 100).round())
print(f"Точность: {100 * test_accuracy:.1f}%")

Точность: 74.5%

Точность леса увеличилась на 6 процентных пунктов по сравнению с одиночным решающим деревом.

Структура деревьев изменилась — глюкоза осталась в корне у 92 деревьев из 100, в остальных случаях ее место заняли другие сильные признаки: индекс массы тела, возраст, уровень инсулина и количество беременностей. Устойчивые правила в других узлах тоже изменились. Идея независимого голосования начала работать: доля пациентов, для которых все 100 деревьев предсказывают одинаковый диагноз единогласно, упала с 81% до 0%.

Равные шансы

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

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

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

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

Алгоритм обучения дерева с механикой жребия разработали математики Я́ли Ами́т и Дональд Ге́ман в 1997 году. Они предложили сбрасывать большую часть признаков перед каждым ветвлением. Обычно сбрасывают корень из количества признаков — если всего признаков 9, сбрасывают 6 и оставляют 3. Дерево выбирает лучший признак и лучшее плечо из оставшихся признаков как обычно. На следующем делении жребий повторяется — снова сбрасываются 6 признаков, и дерево выбирает из оставшихся:

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

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

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

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

Алгоритм Амита-Гемана встроен в решающие деревья в Scikit-learn. Чтобы использовать его, передадим конструктору дерева параметр max_features равный 3 — это ограничит выбор признаков с 8 до случайных 3 на каждом узле. Обучим все деревья на одной и той же выборке без бутстрапа, чтобы изолировать эффект выбора признаков:

import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

train_data = pd.read_csv("data/train.csv")
test_data = pd.read_csv("data/test.csv")

X_train = train_data.drop(columns=["diabetes"])
y_train = train_data["diabetes"]
X_test = test_data.drop(columns=["diabetes"])
y_test = test_data["diabetes"]

predict = pd.Series(0, index=y_test.index)

for _ in range(100):
    model = DecisionTreeClassifier(max_features=3)
    model.fit(X_train, y_train)
    predict += model.predict(X_test)

test_accuracy = accuracy_score(y_test, (predict / 100).round())
print(f"Точность: {100 * test_accuracy:.1f}%")

Точность: 74.3%

Результат близок к результату леса на бутстрапе, но структура деревьев отличается. В бутстрап деревьях глюкоза занимала положение в корне 92 деревьев из 100. С выбором признаков глюкоза осталась в корне только 38 деревьев. Частота использования признаков в узлах дерева стала ближе к равномерной — деревья находят разные решения.

Бесконечный лес

В 2001 году статистик Лео Брейман опубликовал статью “Random Forests” со своей реализацией случайного леса. Она включала и бутстрап Эфрона, и случайный выбор признаков Амита-Гемана.

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

Эта версия случайного леса считается каноничной. Она доступна в Scikit-learn в двух видах: RandomForestClassifier для задач классификации и RandomForestRegressor для задач регрессии. Обучим эту версию леса на данных задачи. По умолчанию лес состоит из 100 деревьев. Деревья обучаются на бутстрап выборках и получают количество признаков, ограниченное до квадратного корня из их числа, на каждом ветвлении:

import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score

train_data = pd.read_csv("data/train.csv")
test_data = pd.read_csv("data/test.csv")

X_train = train_data.drop(columns=["diabetes"])
y_train = train_data["diabetes"]
X_test = test_data.drop(columns=["diabetes"])
y_test = test_data["diabetes"]

model = RandomForestClassifier()
model.fit(X_train, y_train)

train_accuracy = accuracy_score(y_train, model.predict(X_train))
test_accuracy = accuracy_score(y_test, model.predict(X_test))

print(f"Точность (обучение): {100 * train_accuracy:.1f}%")
print(f"Точность (валидация): {100 * test_accuracy:.1f}%")

Точность (обучение): 100.0%
Точность (валидация): 75.3%

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

Лес вводит новый гиперпараметр — количество деревьев. Оценить его влияние можно с помощью метода Монте-Карло.

В 1946 году математик Станислав Улам восстанавливался после операции на мозге и раскладывал пасьянс. Пасьянс — одиночная игра, в которой выигрыш зависит и от стратегии игрока, и от случайности. Улам захотел посчитать вероятность выигрыша. Несмотря на простые правила игры, вывести вероятность теоретически оказалось трудно. Уламу пришла в голову другая идея: если сыграть в пасьянс много раз подряд, доля успешных партий будет приближением истинной вероятности выигрыша. Чем больше пасьянсов разыграно, тем точнее приближение.

Позже Улам передал свою идею математику Джону фон Нейману, который работал с ним в секретной ядерной программе США над созданием водородной бомбы. Фон Нейман написал программу и провел первые промышленные расчеты по методу Улама в 1948 году. Так как метод Улама полагался на случайность, позже его назвали в честь казино — Монте-Карло.

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

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

import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score

train_data = pd.read_csv("data/train.csv")
test_data = pd.read_csv("data/test.csv")

X_train = train_data.drop(columns=["diabetes"])
y_train = train_data["diabetes"]
X_test = test_data.drop(columns=["diabetes"])
y_test = test_data["diabetes"]

scores = []
for _ in range(100):
    model = RandomForestClassifier(n_estimators=5)
    model.fit(X_train, y_train)
    score = 100 * accuracy_score(y_test, model.predict(X_test))
    scores.append(score)

print(f"Точность: {np.mean(scores):.1f}% ± {np.std(scores):.1f}%")

Точность: 70.2% ± 1.8%

Запустим программу еще несколько раз с другим количеством деревьев и сравним результаты друг с другом:

Количество деревьев	Точность	Отклонение
5	70.2%	±1.8%
10	72.7%	±1.5%
50	74.9%	±0.9%
100	75.3%	±0.8%
500	75.8%	±0.5%
1,000	75.9%	±0.5%
5,000	75.9%	±0.4%
10,000	75.9%	±0.3%

Точность леса приближается к 76%, добавление деревьев стягивает результат к истинному значению и не приводит к переобучению. Такое поведение леса с ростом числа деревьев соответствует идее Монте-Карло — оно универсально и не зависит от задачи. На конкретное значение предела (76%) влияют другие факторы. Брейман оценил верхнюю границу этого предела в своей работе:

\text{Ошибка} \le \overline{\rho} \frac{\left( 1 - s^2 \right)}{s^2}.

Если лес бесконечен, его ошибка зависит от двух параметров: предсказательной силы дерева $s$ и корреляции между деревьями $\overline{\rho}$ .

Корреляция деревьев принимает значение от 0 до 1 и зависит от разницы в предсказаниях деревьев, а не в их структуре. В первом примере структура каждого дерева была уникальной даже при обучении без бутстрапа и случайного выбора признаков. Расхождение в структуре достигалось только за счет узлов на большой глубине, которые меньше всего влияют на предсказание — в 81% случаев деревья принимали решение единогласно. Корреляция деревьев в этом случае близка к единице, а ошибка леса близка к ошибке одного дерева, которая задается дробью в правой части выражения.

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

Со снижением корреляции падает и сила деревьев. Бутстрап снизил точность отдельного дерева с 68% до 66%, случайный выбор признаков — до 65%. Лес покрывает эту потерю, пока выигрыш от независимости деревьев ее перевешивает. Если оставить на каждом делении один случайный признак вместо трех, корреляция упадет еще сильнее, но рост ошибок деревьев уже не окупится — точность леса снизится на 0.7 процентного пункта. Лучший баланс между силой и корреляцией зависит от задачи. Его определяют перебором: меняют число доступных признаков с максимума до единицы и смотрят на метрики леса.

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