Featurestream.io - Случайные леса++

Наряду с глубоким обучением, Случайные леса являются одной из рабочих лошадок современной науки о данных. Они популярны, потому что с ними часто легко получить хорошие результаты, и они хорошо работают с низко- и среднеразмерными структурированными табличными данными (в отличие от многомерных неструктурированных данных, таких как текст, аудио, изображения), и особенно когда объем данных не велик.

Этот пост посвящен некоторым улучшениям случайных лесов, которые мы разработали в рамках стартапа под названием featurestream.io. Мы хотели разработать инструменты для машинного обучения потоковых данных. Единственными существующими инструментами, доступными в то время для обработки потоковых данных, была логистическая регрессия, тогда как случайные леса были современными, например, для соревнований Kaggle. В частности, мы хотели иметь инструменты, которые позволяли бы обучаться в потоках, а не просто прогнозировать.

Featurestream улучшает доступные реализации Random forest несколькими полезными способами:

Инкрементальное (онлайн) обучение (и более быстрое пакетное обучение за один проход)
Обработка отсутствующих/зашумленных данных
Интерпретируемость
Распределенное обучение

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

Часть кода доступна по адресу https://github.com/featurestream.

Инкрементальное обучение

Случайные леса — широко реализованные в Spark или scikit-learn — представляют собой пакетные методы, рабочий процесс которых обычно выглядит следующим образом:

df = load_input_data()
X,y = preprocess_data()
rf = RandomForestClassifier().fit(X,y)
...
deploy_model(rf)

Во многих приложениях обучающие данные не являются статическими; он может периодически обновляться или даже транслироваться через что-то вроде Kafka. Типичный подход к решению этой проблемы заключается в периодическом выполнении описанных выше шагов — например, в потоковой передаче Spark это можно сделать, отслеживая папку HDFS на наличие обновлений, которые могут поступать из приложения. У этого есть 2 очевидные проблемы: 1) модель не актуальна; 2) если мы не выбрасываем данные, каждая перестройка последовательно занимает больше времени, что усугубляет проблему.

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

Деревья Хёффдинга

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

Граница Хёффдинга состоит в следующем. Учитывая n независимых наблюдений x_1,…,x_n случайной величины X с диапазоном R, тогда с вероятностью 1-delta среднее значение X равно как минимум mean(x_1,..,x_n) — epsilon, где

Хотя это не убывает экспоненциально быстро в n (в отличие, скажем, от границы Чернова), у него есть то преимущество, что оно работает для всех входных распределений. Мы применяем границу Хёффдинга, чтобы решить, можно ли разделить узел раньше, точнее, если наибольший выигрыш max_a G(a) как минимум в epsilon больше, чем второй по величине выигрыш. В этом случае атрибут a является лучшим w.p. не менее 1-delta.

Вот некоторый псевдокод для случая, когда все функции являются бинарными:

class node:
  isleaf = True
  feat_ix = None
  children = []
  counts = np.zeros(n_labels)
  data = np.zeros(n_feats, 2, n_labels) # features are[0,1]
root = node() # an empty tree
# update from node with example (x,y)
def update(node, x, y):
  while !node.isleaf:
    node = node.children[x[node.feat_ix]]
  node.counts[y] += 1
  for i,j in enumerate(x):
    node.data[i,j,y] += 1
  # compute entropy for each feature
  for i in range(n_feats):
    weights = np.sum(node.data[i], axis=0)
    ent = weights[0]*entropy(node.data[i,0,:]) \
          + weights[1]*entropy(node.data[i,1,:])
    ig[i] = (ent, i)
  ig.sort(ascending=False)
  eps = np.sqrt(R**2 * np.log(1./delta) / (2*n))
  delta = ig[0][0] - ig[1][0]
  if delta > eps:
    # split node
    node.isleaf = False
    node.feat_ix = ig[0][1]
    node.children = [Node(counts=node.data[i,:]) \
                       for i in range(n_labels)]

Есть еще несколько приемов — например, разрыв связей там, где граница никогда не достигается (поскольку два признака одинаково полезны или, что еще хуже, коллинеарны). Мы также хотим иметь дело отдельно со случаями, когда у нас есть числовые/категориальные признаки и числовые/категориальные цели (классификация/регрессия). Некоторые из этих вопросов подробно обсуждаются в оригинальной документе VFDT Domingos et al.

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

Дрейф концепции: нестационарные источники

Приведенное выше описание предполагает, что нижележащий источник является стационарным. Другими словами, примеры были взяты из источника с таким же поведением, или (если хотите) информация о порядке примеров отсутствует. На практике это часто не так — например, меняется поведение клиентов, меняются базовые процессы, меняются фондовые рынки по мере того, как участники меняют стратегию, и так далее. Это известно как дрейф концепций. В этом случае описанные выше алгоритмы будут по-прежнему работать, но допущения Хёффдинга будут нарушаться, поэтому мы можем слишком рано разделиться и построить плохую модель. В случае с потоком наша модель может со временем ухудшиться, и нам, возможно, придется ее выбросить.

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

Онлайн-бэггинг — ансамбли деревьев

В то время как единое дерево решений может быть построено постепенно с использованием описанного выше подхода Хёффдинга, случайный лес представляет собой пакетный ансамбль деревьев решений. Бэггинг («самозагружаемое усреднение») работает следующим образом:

trees=[]
X, y = original data
n = len(X)
for i in range(n_trees):
  X_i, y_i = sample_with_replacement(X, y, n)
  T = build_tree(X_i, y_i)
  trees.append(T)

Сделать прогноз с использованием ансамбля можно путем простого усреднения прогнозов по каждому дереву.

Теперь, имея поток точек данных (x1,y1), (x2,y2), ..., мы хотели бы вычислить пакетированный ансамбль. Получается, что выборка с заменой эквивалентна выборке каждого элемента k раз, где k ~ Poisson(1) (пояснение см. ниже). Следовательно, у нас есть следующий простой алгоритм онлайн-построения случайного леса (подробнее см. [Oza et al]).

# build empty trees
trees=[Tree() for i in range(n_trees)]
def update(x,y):
  for t in trees: # in parallel
    k = np.random.Poisson(1.0)
    t.update([x]*k, [y]*k) # replicate k times

Аппроксимация Пуассона работает, потому что количество раз, когда каждый элемент присутствует в исходном пакетированном выводе, определяется как Binomial(n,1/n), а PDF этого может быть аппроксимирован как Poisson(1).

Отсутствующие/зашумленные данные

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

При обходе дерева в рамках обновления мы поддерживаем массивы count для внутренних узлов в дополнение к листовым узлам. Во время прогнозирования для экземпляра x мы проходим по дереву до тех пор, пока не наткнемся на конечный узел или узел n, где x[n.feat_ix] is None. В последнем случае мы делаем прогноз, используя массивы, хранящиеся в узле n. Это можно рассматривать как «интеграцию» отсутствующей функции. Если узел находится высоко в дереве, предсказание, вероятно, будет одинаковым для разных классов и не будет слишком сильно влиять на конечный результат, который вычисляется путем суммирования предсказаний классов по всем деревьям в ансамбле. Благодаря бэггингу маловероятно, что этот узел будет присутствовать высоко на пути на многих других деревьях.

Интерпретируемость и распределенное обучение

Созданные структуры данных также позволяют интерпретировать как на уровне модели (какие функции важны для модели), так и интерпретируемо на уровне экземпляра (какие функции способствуют этому прогнозу и как).

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

Я расскажу об этих двух проблемах в другом посте.