Часто суть статей о бэггинге сводится к тому, что вы обучаете множество деревьев решений на различных частях данных и усредняете прогнозы, чтобы получить окончательный прогноз, который улучшается из-за того, что дисперсия случайного леса меньше дисперсии одного дерева решений. Тексты с таким заключением содержат отличные демонстрации, код и много других мыслей. Но криптоаналитику и дата-сайентисту, доктору Роберту Кюблеру, переводом статьи которого мы делимся сегодня, часто не хватает хороших выкладок о причине, почему бэггинг — хорошая идея, а ещё не хватает демонстраций уменьшения дисперсии на реальных данных. Восполняем этот пробел к старту нашего флагманского курса по Data Science.
Я хочу рассмотреть недостатки и дать интуитивное обоснование причины, почему алгоритм случайного леса работает и как увидеть улучшение дисперсии графически. Считайте эту статью исследованием двух тем, которое глубже обычной статьи о дилемме смещения-дисперсии, но она не настолько глубокая, как полноценная исследовательская работа. Тем не менее я буду давать ссылки на ресурсы, которые считаю полезными, чтобы дать вам возможность углубиться в них.
Я стараюсь, чтобы уровень математики оставался достаточно понятным, чтобы люди без математического образования могли читать мои статьи, но даю высокоуровневые идеи и иллюстрации, которые могут понравиться и людям с математическим образованием. Не стану подробно объяснять, как работают деревья решений, случайные леса и все остальные упомянутые модели, вместо этого объясню только очень высокоуровневые идеи.
Деревья решений
Отказ от ответственности: я буду говорить только о ванильных деревьях, не рассматривая обрезку. Также условимся, что деревья могут расти на произвольную глубину.
Выходное описание
Дерево решений с k листьями — модель вида
означает, что дерево решений — это кусочно-постоянная функция с вещественными значением w в области пространства признаков R. Здесь x — метка из пространства признаков X, а y — метка из выходного пространства Y. Ограничения R таковы:
Они представляют собой прямоугольники с границами, параллельными координатным осям пространства признаков;
Множество всех прямоугольников является разбиением пространства признаков, т. е. два прямоугольника не пересекаются, а объединение всех прямоугольников является полным пространством признаков.
Теперь, когда мы это выяснили, разберёмся, почему дерево решений называют алгоритмом с высокой дисперсией, в то время как, например, линейная регрессия считается алгоритмом с низкой дисперсией.
Сравнение с линейной регрессией
Вкратце напомню, что модели линейной регрессии имеют следующий вид:
где веса w — вещественные числа, а d — размерность выборок, т. е. количество функций.
Для сравнения дисперсии этих моделей мы должны сделать один шаг назад и подумать о том, что на самом деле представляет собой задача обучения.
Обычно даётся фиксированное количество образцов (обучающее множество), образцы позволяют алгоритму творить магию и подбирать все необходимые параметры. В результате мы можем предсказать значения данных, которых не было в обучающем наборе. Однако это довольно закостенелый взгляд. В теории обучения мы моделируем обучающее множество как происходящее из распределения D в пространстве X×Y, где X — это пространство признаков, а Y — пространство вывода. Мы выберем обучающий набор L (а также набор для проверки и тестирования) размера n из распределения:
n выборок данных из распределения D. Здесь каждый x — это вектор некоторой размерности d, поступающий из пространства признаков X, а y — это соответствующие метки выходного пространства Y.
Представьте, что распределение представляет собой чёрный ящик с кнопкой; если вы нажмёте кнопку один раз, получите из распределения случайный образец (x₁, y₁). Нажав ещё раз, вы получите ещё один образец (x₂, y₂), который не зависит от предыдцщего. И так до достаточного количества образцов.
Затем мы можем использовать n точек данных из L для обучения нашей модели, получится функция f с f(xᵢ)≈yᵢ для всех (xᵢ, yᵢ) в выборке L (если модель хороша). Такой подход гарантирует хорошую производительность на обучающем наборе.
Но представьте, что мы запрашиваем n новых выборок из распределения D и используем их как обучающее множество L'. Назовём обученную на новом множестве модель g. Эта модель также будет удовлетворять условию g(xᵢ’)≈yᵢ’ для всех (xᵢ’, yᵢ’) в L’.
Поскольку L' состоит из разных точек (xᵢ’, yᵢ’), новая модель g будет иметь отличающуюся от f выходную форму. Модели f и g могут сильно различаться или не различаться, в зависимости от того, насколько отличаются L и L', как создавались модели и какой подход к случайности применялся в алгоритмах.
Если для фиксированного алгоритма, например дерева решений, модели для разных обучающих наборов L и L' имеют тенденцию сильно различаться, то он называется алгоритмом с высокой дисперсией.
Конечно, это не точное определение, но в этой статье точность не нужна. Воспользуемся графиками, чтобы определить, имеет ли алгоритм дисперсию выше, чем у другого алгоритма.
Если вас интересует математика (ура!), могу порекомендовать диссертацию Жиля Луппа[1], а также книгу Шая Шалев-Шварца и Шая Бен-Давида[2], где очень подробно объясняются теоретические основы машинного обучения.
Вернёмся к сравнению деревьев решений и линейной регрессии. Воспользуемся таким рабочим примером: X=[0, 10] и Y=ℝ, т. е. пространством признаков размерности 1. Этот один признак может принимать вещественные значения от 0 до 10, а метки могут принимать любые вещественные значения. В нашем примере D определяется так: признак x выбирается равномерно от 0 до 10, а метка y явно вычисляется через скрытую функцию h(x).
Функция h описывает базовую структуру меток, это истина, которую мы хотим узнать. Она называется скрытой, поскольку информация не предоставляется алгоритмам, которые должны разобраться сами. Согласно этим рассуждениям, если мы запросим распределение D три раза по 10 образцов каждый раз, то получим три обучающих набора данных:
Трёхкратная выборка из распределения даёт три разных результата. Каждый раз генерировалось 10 обучающих выборок. Воспользуемся третьим обучающим набором и построим график результатов после применения деревьев решений и линейной регрессии.
Видно, что дерево решений идеально подходит к обучающим данным, но это не повод для радости: алгоритм захватывает шум, а этого не хотелось бы. Мы заинтересованы только в том, чтобы уловить основную структуру меток, то есть 3sin(x)+x.
Смещение-дисперсия деревьев решений и регрессии
Проведём этот эксперимент 3000 раз для 3000 независимых обучающих наборов с размерами в 10 элементов данных. В левой части видны результаты деревьев, в правой — линейной регрессии. Результаты на графиках накладываются друг на друга.
Каждое испытание даёт одну кривую прозрачного чёрного цвета. Чем больше линий складывается, тем темнее становятся пересечения. Пунктирная синяя линия — это наша функция 3sin(x)+x.
Деревья решений слева в среднем довольно хорошо подходят к данным. Люди также называют это свойство деревьев решений низкой систематической погрешностью (смещением). Модель линейной регрессии, справа, явно не отражает сложную картину в основе структуры меток. Мы говорим, что линейная регрессия имеет высокую систематическую погрешность, в данном случае она не справляется с задачей.
Тем не менее если рассматривать вертикальную ширину чёрных трубок, то трубки деревьев решений шире, чем в случае линейной регрессии. Это означает, что прогнозы дерева решений колеблются сильнее прогнозов линейной регрессии при повторной выборке обучающего набора, это свойство деревьев решений называется высокой дисперсией; получается, что у линейной регрессии низкая дисперсия.
Мы нуждаемся в алгоритмах с низким смещением, которые попадают в истину в среднем, и низкой дисперсией, которые не слишком колеблются вокруг истины. К счастью, есть множество способов уменьшить смещение, один из них называется бустинг, также есть способы снижения дисперсии, например бэггинг. Хорошая черта бэггинга — он не увеличивает смещение; причину этого я объясню ниже.
Вот почему эффект от совместного применения бэггинга и линейной регрессии небольшой: смещение уменьшается бустингом, а не бэггингом. Забавно, но оказалось полезным совместить деревья решений и бустингом. В таком случае применяются обрезанные деревья решений, имеющие низкую погрешность.
Бэггинг
Далее о том, что делает бэггинг, почему он работает и как увидеть уменьшение дисперсии.
Простое объяснение
Представьте, что у нас есть доступ к стандартному нормальному распределению, в частности, среднее значение наблюдаемой величины равно 0, а её дисперсия равна 1. Предположим, что нам нравится наблюдать значения около 0 (так же, как функции предсказания около 3sin(x)+x). Но дисперсия 1 слишком велика, на наш взгляд (как и ширина чёрных трубок), и мы ищем способ уменьшить её. Можно просто выбрать больше значений из стандартного нормального распределения и взять их среднее значение. Следующий результат хорошо известен и легко проверяется:
Среднее значение стандартных нормальных случайных величин также нормально распределено. Новое среднее — это просто сумма средних, а новую дисперсию возможно вычислить через формулу суммы некоррелированных переменных, которая отражает зависимости между случайными величинами. Если все величины независимы, то ρ=0. Если все ковариации между случайными величинами меньше границ K, то ρ также меньше K.
Таким образом, усредняя, мы имитируем выборку из другого нормального распределения с таким же средним значением, но с меньшей дисперсией, если значение ρ не слишком велико. Это здорово, потому что мы получаем значения, близкие к нулю с большей вероятностью, чем раньше! В частном случае независимых случайных величин, когда ρ=0 и b=100, дисперсия падает, например, с 1 до 0,01. И вот результат:
Нормальное распределение с дисперсией 0,01 намного уже стандартного нормального распределения с дисперсией 1. В затенённых областях видно, где лежат 99% вероятности каждого распределения.
Внимание: если все случайные величины X коррелируют со значением 1, то из этого следует, что ρ=(b-1)/b, т. е. дисперсия среднего снова равна 1. Это соответствует случаю, когда каждый образец данных в сущности является одним и тем же числом. Усреднение по множеству одинаковых чисел не даёт нам никакой новой информации, оно не лучше, чем вывод единственного значения.
В лучшем случае возможно усреднить независимые выборки. Чем больше их корреляция, тем они бесполезнее в усреднении.
Основная идея бэггинга
Полезным окажется сделать то же самое с моделями предсказания. Запуск алгоритма Decision Tree на случайном наборе обучающих данных даёт нам модель, которая по сути является выборкой функции из распределения. Усреднение этих моделей даёт нам другую модель (например, случайный лес) с тем же смещением, но меньшей дисперсией. Эта ансамблевая модель в среднем ближе к истине, чем одно дерево.
Но вопрос в другом: насколько коррелируют эти функции? Пример: если попадётся набор данных, мы можем установить на него одно дерево решений. Но если мы сделаем это снова, результат будет (почти) таким же в случае с деревьями решений, то есть выбранные таким образом функции сильно коррелированы (ρ≈1) и не улучшают ни одно дерево.
Именно единица не обязательна, поскольку алгоритмы дерева решений иногда должны разрушать связи, например случайным образом, но, поскольку в этом состоит единственный источник случайности, разрушение связей не приводит к созданию принципиально различных деревьев, которые каким-то образом нужно декоррелировать; об этом — в следующем разделе.
Приближаемся к случайным лесам
Случайные леса изобретены Лео Брейманом[3]. Идея здесь — особым образом подогнать множество деревьев решений к обучающему набору, что даёт одинаково большое количество моделей деревьев, то есть функций. Затем эти деревья объединяются в единую модель, например усреднением их выходов для любого заданного входа x, а такой подход превращает метод в частный случай бэггинга. В результате модель обладает меньшей дисперсией, подобно тому, что мы наблюдали в случае с нормально распределёнными случайными величинами. Идея получения многих максимально некоррелированных деревьев заключается в следующем:
Задействовать случайное подмножество обучающих выборок для каждого дерева.
Использовать случайное подмножество признаков на каждом этапе выращивания каждого дерева.
Два источника рандомизации способствуют снижению корреляции между деревьями даже больше, чем только один. Не стесняйтесь добавлять другие, если вам доведётся разработать новый алгоритм бэггинга! Есть и другие методы объединения отдельных деревьев решений, например, экстремально случайные деревья[4].
Сравнение дисперсии между деревьями решений и случайными лесами в одном измерении
Возьмём 10 образцов из нашего распределения и обучим дерево решений и случайный лес из 100 деревьев. Повторим эту процедуру 1000 раз:
Мы видим, что вертикальная ширина красной образованной случайным лесом трубки меньше ширины трубки дерева решений. Более того, кажется, что средние значения (середина) трубок одинакова, то есть усреднение не повлияло на смещение. Функцию 3sin(x)+x достаточно хорошо видно.
Обратите внимание: случайный лес не показал весь свой потенциал: мы использовали набор данных с единственным признаком, то есть с ним работало каждое дерево решений. Таким образом, 100 деревьев внутри леса различаются только обучающими выборками. В таком случае алгоритм сворачивается в более простой алгоритм бэггинга.
Если хочется увеличить разрыв в вариациях и иметь возможность визуально интерпретировать результаты, мы должны перейти к двумерному пространству признаков. Это позволит алгоритму случайным образом на каждом шаге выбирать единственный из двух имеющихся признаков.
Сравнение дисперсии деревьев решений и случайного леса в двумерном пространстве
Определим распределение обучающих данных, аналогичное распределению для одномерного случая. Выберем X=[0, 10]² и Y=ℝ, где D равномерно выполняет выборку (x, x') из квадрата с вершинами в (0, 0), (0, 10), (10, 0) и (10, 10) и
Подобно тому, что мы видели ранее, y вычисляется детерминированно через 3sin(x+x')+x-x', а затем добавляется стандартный нормально распределённый шум. Случайный набор данных из 50 точек может выглядеть так:
50 случайных точек из распределения. Мы видим, что в правом нижнем углу находятся более высокие значения, а в левом верхнем — низкие. Разделяющая эти углы область заполнена значениями около нуля. Теперь давайте посмотрим, как ведёт себя дисперсия деревьев решений и случайного леса в этой ситуации. Начнём с деревьев решений и используем 9 разных обучающих наборов данных, чтобы получить 9 разных деревьев.
Картинки сильно различаются. Справа внизу — светлее, что указывает на высокие значения, а слева вверху — темнее, что указывает на низкие значения, но размер и форма всех прямоугольников сильно различаются. Выглядит знакомо? Проделаем то же самое со случайными лесами, обучим 100 деревьев на другом подмножестве данных и только на одном из двух заданных признаков, случайно.
Мы не только снова видим высокие значения в правом нижнем углу и низкие значения в левом; изображения очень похожи. На каждом рисунке есть красивый и плавный градиент, подобный другим градиентам.
Заключение
Очевидно, что алгоритмы с высокой дисперсией быстро меняют результат (модель) при изменении обучающего набора. Это плохо: нельзя узнать, насколько конкретная модель далека от истины, даже когда её смещение равно нулю. Но мы узнали, как увеличить шансы на хорошую модель с помощью бэггинга, и получили интуитивное представление о том, почему бэггинг снижает дисперсию, оставляя смещение неизменным; также мы увидели результаты на множестве иллюстраций.
Ссылки
[1] G. Louppe, Understanding Random Forests — From Theory to Practice (2014), Dissertation
[2] S. Shalev-Shwartz and S. Ben-David, Understanding Machine Learning: From Theory to Algorithm (2014), Cambridge University Press
[3] L. Breiman, Random Forests (2001), Machine learning 45.1 (2001): 5–32
[4] P. Geurts, D. Ernst and L. Wehenkel, Extremely Randomized Trees (2005), Machine learning 63.1 (2006): 3–42
Все формулы я написал в LaTeX. Для другой графики я воспользовался библиотекой Python matplotlib вместе с numpy, а для обучения модели применял scikit-learn. И последнее — код лесной мозаики:
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
import numpy as np
# Sample from the distribution with a true function f.
def generate_data_2d(f, n_samples):
x1 = np.random.uniform(0, 10, n_samples)
x2 = np.random.uniform(0, 10, n_samples)
y = f(x1, x2) + np.random.randn(n_samples)
return np.vstack([x1, x2]).transpose(), y
# Parameters to play round with.
f = lambda x1, x2: 3 * np.sin(x1 + x2) + x1 - x2
n_samples = 50
n_rows = 3
n_cols = 3
# Increase numbers to remove white spaces in the pictures.
n_points = 100
size_points = 6
# Prepare the plotting.
fig = plt.figure(constrained_layout=True, figsize=(12, 12))
all_points = np.array([(x1, x2) for x1 in np.linspace(0, 10, n_points) for x2 in np.linspace(0, 10, n_points)])
# Start plotting.
for i in range(1, n_rows * n_cols + 1):
# Get a random training set.
x, y = generate_data_2d(f, n_samples)
# Train a Decision Tree.
dt = DecisionTreeRegressor()
dt.fit(x, y)
predictions = dt.predict(all_points)
# Create one mosaic picture.
ax = fig.add_subplot(n_rows, n_cols, i)
ax.axis('off')
ax.scatter(all_points[:, 0], all_points[:, 1], c=predictions, s=size_points)
Эта статья примечательна тем, что через простые визуализации снимает страх перед математикой, которая иногда может казаться сложной и даже переусложнённой. Но в основе самых сложных идей всегда лежат простые составляющие, поэтому приходите на наши курсы по Data Science, машинному и глубокому обучению или на курс по аналитике данных, чотбы изменить карьеру и стать востребованным специалистом. Добавим, что наши курсы не ограничиваются темами данных и искусственного интеллекта:
Data Science и Machine Learning
Python, веб-разработка
Мобильная разработка
Java и C#
От основ — в глубину
А также: