Онлайн деревья решений

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

То есть в каком-то смысле задача состоит в том, чтобы уменьшить наше удивление и сделать модель, соответсвующую реальности максимально. Собственно, первый же вопрос, который возникает “а как это удивление мерить?”. Этим занимается отдельная наука - теория информации. Она рассматривает информацию, связанную с исходом случайной величины и отвечает на вопросы вида “сколько информации несет нам знание того, что на кубике выпала “6”. Интуитивно информация соответствует мере удивления при появлении какого-то исхода. Чем больше мы удивлемся, тем больше информации получаем. Выбираются следущие аксиомы:

  1. $I(p)$ непрерывная монотонно уменьшающаяся функция от $p$. $p$ - вероятность рассматриваемого исхода
  2. Если A и B независимые события. $P(A) = p_1, P(B) = p_2, P(AB)=p_1p_2$. Тогда $I(p_1p_2) = I(p_1) + I(p_2)$.

1-ая аксима по сути означает, что менее вероятному событию мы удивляемся больше. Например, выпадению 6x6 на двух кубиках мы удивимся больше, чем выпадению орла при бросании монеты.

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

Можно показать, что единственное семейство функций, которое удовлетворяет этим аксиомам, это

Теперь нам нужна некая единица измерения информации. Возьмем за 1 бит неопределенность, связанную с исходом случайной величины, которая может быть в двух состояниях с вероятностью = 1/2. По сути это удивления от исхода после броска монеты. Тогда база логарифма будет 2, а мера изменения будет называться “бит”. Важно, что это не тот же бит что в компьютерах (принимающий только значения 0 и 1). Информация может измеряться и в дробных значениях. Это просто мера удивления, например, 1.5 бита значит, что мы в полтора раза больше удивляемся данному исходу по сравнению с результатом броска монеты.

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

  • $I$ - это мера удивления от одного исхода;
  • $H$ - мера удивления всей случайной величины. Она называется entropy.

Переходим непосредственно к деревьям решений

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

  • Бинарная классификация
  • Все аттрибуты categorical с двумя возможными значениями

Иформация до разделения считается просто как энтропия:

Здесь $p$ - пропорции положительных и отрицательных примеров соответственно во всей совокупности S

Информация после разделения по аттрибуту $A$ складывается из двух частей (так как у каждого аттрибута только два значения $v_1$ и $v_2$)

Здесь $p$ - пропорции положительных и отрицательных в части примеров S, у которых $a = v_1$. Аналогично для $v_2$ имеем $H(S_2)$.

Чтобы получить среднюю информацию после разделения, берём взвешенное среднее от $H(S_1)$ и $H(S_2)$. Получаем сколько информации взяло на себя разделение по этому атрибуту. Называется эта величина information gain

$p_1$ и $p_2$ - пропорции примеров, у которых $A = v_1$ и $A = v_2$ соответственно.

Для ситуации, когда $S$ известна нам целиком (batch setting, не онлайн) все просто - выбираем лучший атрибут по значению gain’а, разделяем, выбираем следущий и т.д. Все интереснее в онлайне.

Добавляем онлайн

Тут нам в помощь приходит следущее соотношение, называемое Hoeffding bound. Согласно ему, с вероятностью $1 - \delta$ истинное среднее случайной переменной с диапазоном значений $R$ не будет отличаться от оцененного среднего после $n$ независимых наблюдений больше, чем на

В нашем случае за случайную величину берется разница в gain’е между лучшим и вторым лучшим атрибутом. Например, если границу $\epsilon$ мы оценили в 0.2, а посчитанная разница у нас 0.3, мы можем с увернностью сказать, что первый атрибут лучше второго как минимум на 0.1.

В нашем случае, когда оценивается разница в gain’ах, за $R$ берется логарифм степени 2 от числа классов. $\delta$ - это точность оценки - параметр алгоритма, который можно изменять.

Дальше все просто: копим статистику достаточную для того, чтобы делать значимые выводы о значениях gain’ов, затем выбираем 2 лучших атрибута и считаем Hoeffding bound между ними.

Какие есть проблемы с таким подходом:

  1. Дерево начинает сильно ветвиться без особого толку. Решение этой проблемы называется Pre-pruning. Вводится дополнительный атрибут $A_0$, который значит “не разделять”. Тогда разделение призойдет, только если выбрали за лучший атрибут не $A_0$.
  2. Два атрибута не сильно отличаются друг от друга в плане гейнов. Дерево будет очень долго ждать, чтобы хоть как-то разделиться. В критичном случае разделения вообще может не произойти. Решение Tie-breaking. Если разница меньше определенного значения - брать лучший атрибут и не заморачиваться с тем, насколько близок к нему второй.
  3. Атрибут дает разделение по gain’ам хорошее, но по факту большинство примеров попадают всегда в одну ветку. Решение Skewed Split prevention - не разрешать такие сплиты.
  4. Дерево постоянно растет и когда-нибудь упрется в память. Нужно уметь отключать разделение на “малообещающих” узлах. Те, до которых мы вряд ли дойдем, и которые и так не ошибаются. Делается регулярно, узлы включаются/отключаются.

Числовые аттрибуты

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

  1. Equal width. Если известны границы, в которых атрибут меняется, он делится на k равных частей и преобразуется в значения от 0 до k в зависимости от части, в которую попадает его значение. В онлайне способ применим, если границы известны заранее.
  2. Equal frequency. Если известны границы, в которых атрибут меняется, он делится на k частей. Части не равные, выбираются таким образом, чтобы каждая содержала одинаковое число элементов. В таком простом виде в онлайне не применим (нужно заранее знать все значения).
  3. K-mean clustering. Значения кластеризуются на k кластеров. Атрибут преобразуется в значения от 0 до k в зависимости от кластера, в который попадает. В таком простом виде в онлайне не применим.
  4. Quantile Summaries. Описан тут
  5. Gaussian Approximation. Считаем, что для каждого класса значения атрибута будут представляться в виде нормального распределения (если у нас n классов, получим n распределений). Параметры распределения оцениваются по статистикам, которые накоплены в текущем узле. Дальше за разделение берется точка пересечений этих распределений.

Дальше

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

Rodion's blog

put it on the cloud and kill it with fire
Tags
Connect