Решающие деревья и их композиции

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

Решающее дерево

Грубо говоря, алгоритм решающих деревьев был заимствован у людей, так как деревья похожи на то, как человек принимает решение. Например, кто то хочет купить новый телефон. Если сбережений на новый телефон больше, например, 50к рублей, то это новый iPhone. Если денег меньше, то можно спросить, хочет ли человек отдохнуть в Тайланде? Ели хочет, то новый телефон Xiaomi, если не хочет, то это будет Samsung. На картинке видно такое простое дерево решения.

dt_example

Оно показывает логику, благодаря которой мы принимаем решения. Давайте попробуем эту логику как то формализировать, что бы, по возможности, научить машину делать подобное. В общем случае ограничимся бинарными деревьями (т.е. всего два ветвления будут - левое и правое). Начинать будем с самого верха (корня дерева) и идти в низ к листьям. Заметим, что в корне дерева мы сравниваем сумму наших сбережений с неким порогом - 50к рублей. Если сумма сбережений меньше порога, тогда мы идем в правую ветку, если больше то идем в левую. Если же мы пошли в право, то тут тоже можно сравнить значение с неким порогом. Действительно, хочет человек слетать в Тайланд можно описать бинарным признаком: 0 - не хочет, 1 - хочет. И тогда, наш порог будет выглядеть следующем образом: “хотелка” слетать в Тайланд <= 0. Таким образом можно сделать некий обобщающий вывод построения дерева решений :

  1. Начинаем строить дерево от корня к листьям
  2. В каждой вершине сравниваем значение некоторого признака с неким порогом $[x_i \leq t]$, получаем ветвление влево и вправо.
  3. Повторяем процедуру номер 2

Алгоритм построения дерева машиной уже виднеется на горизонте, но пока остаются вопросы. Как именно выбирать признак и порог? Когда останавливать построение дерева? Попробуем сначала ответить на первый вопрос. Пусть у нас в какую то вершину $m$ попала подвыборка $X_m$. Нам нужно найти некий признак $j$ и порог этого признака $t$ , чтобы разбить $X_m \to X_l, X_r$. Как это можно сделать. Первое, что приходит в голову, надо мерить качество разбиения, т.е. нужна некоторая метрика, которая характеризовала объекты в $X_l, X_r$. Рассмотрим для определенности задачу классификации на два класса. Самая хорошая метрика разбивки $X_m \to X_l, X_r$ это когда в каждом подмножестве содержатся объекты только одного класса. Но это идеальный случай. В реальной задаче можно мерить разброс ответов в каждом подмножестве $X_l, X_r$ с помощью критерия информативности:

\[Q(X_m, j, t) = \frac{|X_l|}{|X_m|}\cdot H(X_l) + \frac{|X_r|}{|X_m|}\cdot H(X_r) \to \min_{j, t} \\ \\ Q, |X_i|, H(X_i)\]

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

Как же можно мерить разброс ответов? Рассмотрим сначала задачу классификации и так называемый критерий Джини для разброса ответов. Пусть у нас $k$ классов всего. Тогда мы можем посчитать долю объектов $k$-го класса в разбиении:

\[p^i_k = \frac{\sum_j \left[ x_j \equiv k \right]}{|X_i|}\]

$p^i_k$- доля объектов $k$-го класса в разбиении $i$. Тогда критерий Джини для метрики разброса ответов выглядит следующим образом:

\[H(X_i) = \sum^{\mathbb{K}}_{k=1} p_k^i\cdot(1-p_k^i).\]

Если в подвыборку $X_i$ попали объекты только класса $k$, то $p_k^i \equiv 1$ и $p_k^i\cdot(1-p_k^i) \equiv 0$, тем самым уменьшая $Q$. Если распределение кассов равновероятно ($p_k^i = 0.5$) то критерий Джини будет максимальным. Вроде неплохая метрика качества разбиения. Есть еще энтропийная метрика разброса ответов:

\[H(X_i) = - \sum_{k=1}^{\mathbb{K}} p^i_k\cdot \ln p^i_k.\]

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

\[H(X_i) = D[X_i] = \frac{1}{|X_i|} \sum_i (y_i - \bar{y})^2\]

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

Хорошо, мы определились с метрикой качества разбиения, $Q(X_m, j, t)$, теперь надо понять, как выбирать $j, t$. Благо всего признаков в выборке не так много и можно делать перебор по всем $j$, что бы найти минимальное значение $Q$. С порогом такая же история. Зная как померить получившееся разбиение, перебираем все признаки $j$ и пороги $t$, оставляя только те $j, t$ для которых критерий информативности минимален. Тут стоит отметить, что порог $t$ для бинарных (и категориальных) признаков легко перебирается (все возможные значения) , а для вещественных можно брать точки между значениями признака в $X_m$.

Мы разобрались, как делать разбиение, теперь рассмотрим простой вопрос - когда нам остановится? Когда хватит ветвить дерево. Тут есть два варианта: (i) ограничить дерево по глубине (ii) разбивать до тех пор, пока в листе не останется $n$ объектов. Второй пункт понятен, нужно выбрать $n$ таким образом, что бы мы смогли сказать о распределении данных в листе. Как правило $n =5$. Первый же пункт как правило используется в композиции деревьев, о чем будет сказано ниже. Когда дерево остановить мы знаем, но как же предсказать результат теперь? На самом деле все по тупому просто. Если это задача регрессии, то мы предсказываем среднее по объектам в листе. Если это задача классификации, то предсказываем самый популярный класс в листе. Более того, частота этого класса и будет вероятностью, что очень неплохо.

Таким образом, мы знаем все, что бы запрогать решающее дерево для задачи. Начинаем строить с корня до листьев (жадный алгоритм), перебираем признаки и пороги, что бы найти лучшее разбиение, останавливаемся по критерию останова и считаем ответ. Казало бы, что еще нужно? Оказывается, что решающие деревья очень сильно переучиваются. И это очень большой минус. Рассмотрим подробнее, что происходит и как с этим можно бороться.

Композиции деревьев. Случайный лес.

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

dt_overfit

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

dt_overfit2

Видно, что разделяющая поверхность изменилась. Т.е. решающее дерево достаточно сильно меняется при сравнительно небольшом изменении подвыборки. А что, если попробовать обратить эту особенность в преимущество?

Я пропущу некие математические основания объединения алгоритмов в композиции. Лишь хочу упомянуть важные выводы. Ошибка предсказания алгоритма складывается из трех величин: (i) шум (ii) смещение (iii) разброс. Шум это то, на что мы повлиять не сможем, это особенность данных. Смещение это матожидание ошибок, а разброс это дисперсия ошибок. Так вот оказывается, что для деревьев смещение очень мало, так как они сильно переучиваются на данных аппроксимируют сложные зависимости. А разброс ошибок композиции тем ниже, чем меньше коррелированы предсказания различных деревьев. Таким образом, если мы обьеденим несколько деревьев в композицию, то смещение мало изменится, а разброс может стать существенно меньше. Рассмотрим, как можно это сделать.

Так как дерево сильно меняется при изменении выборки, то что если начать генерить различные выборки из исходной и строить деревья на них? Из выборки длинной $M$ генерим подмножество длины $M$ c возвращением. Такой подход называется Бутстрэп. Например, для множества

\[\{a_1, a_2, a_3, a_4, a_5\} \to \{a_1, a_1, a_3, a_4, a_4\}\]

И прочее похожие варианты. Для каждой такой выборки строим наше дерево $T_i(x)$ где $i$ номер выборки и тогда суммарный алгоритм будет иметь вид

\[a(x) = \frac{1}{M}\sum_i^{M} T_i(x).\]

Где $M$ число наших новых выборок. В случае классификации мы выбираем тот класс, за который больше всего проголосовало алгоритмов. Вот оказывается, что такой подход позволяет уменьшить разброс ошибки в $M$ раз! Это называется Бэггинг. Достигается это благодаря малой корреляции деревьев $T_i$.

Супер, мы знаем один способ обьединить деревья в композиции - это беггинг (на самом деле это будет работать не только с деревьями). Но, на самом деле можно еще уменьшить коррелированность деревьев, что бы уменьшить разброс. Что если при построении дерева мы будем не перебирать все признаки, а выбирать из некого случайного подмножества признаков $q$? Т.е. используем тот-же самый беггинг, только добавляем элемент случайности в построение дерева. Построенный таким образом алгоритм называют случайным лесом или random forest. В задачах классификации обычно берут $q=\sqrt{d}$, где $d$ - кол-во признаков, а в задачах регрессии $q=d/3$. Это наверно самый популярный алгоритм в машинном обучении (разные люди пишут, что порядка 70% задач решается с помощью лесов). У RF практически отсутствуют гиперпараметры - как правило это кол-во деревьев и кол-во случайных признаков. Да, это очевидно, что деревья можно строить параллельно, так как построения вообще не связаны друг с другом. Это вообще потрясающе. Можно брать и пользоваться, но что нам мешает остановиться? Но есть еще один подход построения композиции.

Градиентный бустинг.

Хотя RF строится параллельно, но на больших данных и при большом кол-ве признаков строить глубокие деревья не очень эффективно. Процесс получается долгим. Мы можем ускорить построение деревьев, ограничив глубину, но тогда ты теряем в точности, так как смещение композиции алгоритмов уже не обязано быть маленьким. Кроме того, для решения сложных задач может потребоваться больше деревьев, чем хотелось бы. Как именно определять необходимое количество деревьев? На самом деле, если мы откажемся от позиции, где каждое дерево строится независимо от всех остальных и попытаемся учитывать “опыт” прошлых деревьев, то можно более эффективно объединять деревья в композицию. Давайте попробуем строить каждое следующее дерево таким образом, что бы оно минимизировало ошибку всех предыдущих деревьев, другими словами будем строить композицию по индукции. Итак, пусть наш суммарный алгоритм выглядит следующим образом:

\[a_N(x_i) = \sum_{j=0}^{N}T_j(x_i)\]

Где, $x_i$- элементы выборки, а суммирование происходит по всем алгоритмам. Заметим, что это уже не среднее значение а именно сумма алгоритмов. Пусть у нас есть самый первый алгоритм - $T_0(x_i)$ (это может быть самый простой алгоритм, например константа). Пусть мы каким-то образом построили $N-1$ алгоритм $a_{N-1}(x_i)$ и теперь нужно построить новый $T_N(x_i)$ алгоритм. Строить мы его хотим таким образом, что бы некая функция потерь $\mathbb{L}(y, \hat{y})$ была минимальной на всей выборке, т.е.

\[\sum_{i=0}^{l} \mathbb{L}(y_i, \hat{y}_i) = \sum_{i=0}^{l} \mathbb{L}(y_i, a_{N-1}(x_i) + T_N(x_i)) \to \min_{T}.\]

Таким образом, каждый новый алгоритм $T_N$ будет выбираться, чтобы суммарная ошибка на всей выборке имела локальный минимум. Эту задачу можно переформулировать другим образом, найти такой вектор смещения $\bar{\xi} = (\xi_1, …, \xi_l)$, чтобы он минимизировал функционал

\[\sum_{i=0}^{l} \mathbb{L}(y_i, a_{N-1}(x_i) + \xi_i) \to \min_{\xi}.\]

Найти такой вектор можно с помощью градиентного спуска:

\[\bar{\xi} = - \begin{pmatrix} \nabla \mathbb{L}(y_1, a_{N-1}(x_1) ) \\\ ... \\\ \nabla \mathbb{L}(y_l, a_{N-1}(x_l) ) \end{pmatrix}\]

Зная этот вектор $\bar{\xi}$, которой даст локальный минимум функционала, мы можем обучать наш новый алгоритм $T_N$, чтобы его ответы были максимально похожи на вектор смещения $\bar{\xi}$, т.е.

\[T_N(x) = arg\min_{T} \frac{1}{l}\sum_{i=0}^{l} (T(x_i) - \xi_i)^2.\]

В итоге мы получили процесс построения нового дерева, что бы оно приближало лучше целевую переменную.

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

На самом деле бустинг над деревьями не решает проблемы, озвученный выше. В отличии от случайного леса он легко переобучается на данных, и для этого вводят гиперпараметры для борьбы с переобучением. Эффективность бустинга в том, чтобы использовать простые алгоритмы (не обучать долго каждый алгоритм, деревья глубины порядка 5-8) и каждый следующий выбирать так, чтобы минимизировать ошибку. И это действительно приводит к улучшению результатов и на больших объемах данных работает быстрее случайного леса (proof, тут можно долго спекулировать и все зависит от задачи).

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

  1. https://habrahabr.ru/company/ods/blog/324402/
  2. https://www.coursera.org/learn/supervised-learning/
  3. http://www.machinelearning.ru/wiki/images/1/1f/Sem05_ensembles.pdf