Квантильные случайные леса из сада Скикит очень медленно делают прогнозы

Question

Я начал работать с квантильными случайными лесами (QRF) из scikit-garden пакет. Ранее я создавал регулярные случайные леса, используя RandomForestRegresser от sklearn.ensemble,

Похоже, что скорость QRF сравнима с обычной RF с небольшими размерами набора данных, но по мере увеличения размера данных QRF становится НАМНОГО медленнее делать прогнозы, чем RF.

Это ожидается? Если да, то может кто-нибудь объяснить, почему на эти прогнозы уходит так много времени и / или давать какие-либо предложения относительно того, как я могу получить квантильные прогнозы более своевременно.

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

import matplotlib as mpl
mpl.use('Agg')
from sklearn.ensemble import RandomForestRegressor
from skgarden import RandomForestQuantileRegressor
from sklearn.model_selection import train_test_split
import numpy as np
import time
import matplotlib.pyplot as plt

log_ns = np.arange(0.5, 5, 0.5) # number of observations (log10)
ns = (10 ** (log_ns)).astype(int)
print(ns)
m = 14 # number of covariates
train_rf = []
train_qrf = []
pred_rf = []
pred_qrf = []

for n in ns:
    # create dataset
    print('n = {}'.format(n))
    print('m = {}'.format(m))
    rndms = np.random.normal(size=n)
    X = np.random.uniform(size=[n,m])
    betas = np.random.uniform(size=m)
    y = 3 +  np.sum(betas[None,:] * X, axis=1) + rndms

    # split test/train
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)

    # random forest
    rf = RandomForestRegressor(n_estimators=1000, random_state=0)
    st = time.time()
    rf.fit(X_train, y_train)
    en = time.time()
    print('Fit time RF = {} secs'.format(en - st))
    train_rf.append(en - st)

    # quantile random forest
    qrf = RandomForestQuantileRegressor(random_state=0, min_samples_split=10, n_estimators=1000)
    qrf.set_params(max_features = X.shape[1] // 3)
    st = time.time()
    qrf.fit(X_train, y_train)
    en = time.time()
    print('Fit time QRF = {} secs'.format(en - st))
    train_qrf.append(en - st)


    # predictions
    st = time.time()
    preds_rf = rf.predict(X_test)
    en = time.time()
    print('Prediction time RF = {}'.format(en - st))
    pred_rf.append(en - st)

    st = time.time()
    preds_qrf = qrf.predict(X_test, quantile=50)
    en = time.time()
    print('Prediction time QRF = {}'.format(en - st))
    pred_qrf.append(en - st)

fig, ax = plt.subplots()
ax.plot(np.log10(ns), train_rf, label='RF train', color='blue')
ax.plot(np.log10(ns), train_qrf, label='QRF train', color='red')
ax.plot(np.log10(ns), pred_rf, label='RF predict', color='blue', linestyle=':')
ax.plot(np.log10(ns), pred_qrf, label='QRF predict', color='red', linestyle =':')
ax.legend()
ax.set_xlabel('log(n)')
ax.set_ylabel('time (s)')
fig.savefig('time_comparison.png')

Вот результат: Сравнение времени обучения RFF и QRF и прогнозы

Answer 1

Я не являюсь разработчиком этого или любого другого пакета квантильной регрессии, но я посмотрел исходный код для scikit-garden и quantRegForest/ranger, и у меня есть представление о том, почему версии R намного быстрее:

РЕДАКТИРОВАТЬ: В связанной с github проблеме, lmssdd упоминает, как этот метод работает значительно хуже, чем "стандартная процедура" из статьи. Я не читал газету подробно, поэтому воспринимайте этот ответ как скептицизм.

Объяснение различий в методах скгарден / кванторфорест

Основная идея скгардена predict Функция сохранить все y_train значения, соответствующие всем листьям. Затем, при прогнозировании нового образца, вы собираете соответствующие листья и соответствующие y_train значения и вычислить (взвешенный) квантиль этого массива. Версии R используют ярлык: они сохраняют только один, случайно выбранный y_train значение на листовой узел. Это имеет два преимущества: это делает сбор соответствующих y_train Значения намного проще, поскольку в каждом листовом узле всегда есть ровно одно значение. Во-вторых, это значительно упрощает расчет квантилей, поскольку каждый лист имеет одинаковый вес.

Поскольку вы используете только одно (случайное) значение на лист вместо всех, это метод аппроксимации. По моему опыту, если у вас достаточно деревьев (не менее 50-100 или около того), это очень мало влияет на результат. Тем не менее, я не знаю достаточно о математике, чтобы сказать, насколько точно это приближение.

TL; DR: как заставить скгарден прогнозировать быстрее

Ниже приведена реализация более простого R-метода квантильного предсказания для модели RandomForestQuantileRegressor. Обратите внимание, что первая половина функции - это (единовременный) процесс выбора случайного значения y_train для листа. Если бы автор реализовал этот метод в skgarden, он бы логически переместил эту часть в fit метод, оставляя только последние 6 или около того строк, что делает намного быстрее predict метод. Также в моем примере я использую квантили от 0 до 1 вместо от 0 до 100.

def predict_approx(model, X_test, quantiles=[0.05, 0.5, 0.95]):
    """
    Function to predict quantiles much faster than the default skgarden method
    This is the same method that the ranger and quantRegForest packages in R use
    Output is (n_samples, n_quantiles) or (n_samples, ) if a scalar is given as quantiles
    """
    # Begin one-time calculation of random_values. This only depends on model, so could be saved.
    n_leaves = np.max(model.y_train_leaves_) + 1  # leaves run from 0 to max(leaf_number)
    random_values = np.zeros((model.n_estimators, n_leaves))
    for tree in range(model.n_estimators):
        for leaf in range(n_leaves):
            train_samples = np.argwhere(model.y_train_leaves_[tree, :] == leaf).reshape(-1)
            if len(train_samples) == 0:
                random_values[tree, leaf] = np.nan
            else:
                train_values = model.y_train_[train_samples]
                random_values[tree, leaf] = np.random.choice(train_values)
    # Optionally, save random_values as a model attribute for reuse later

    # For each sample, get the random leaf values from all the leaves they land in
    X_leaves = model.apply(X_test)
    leaf_values = np.zeros((X_test.shape[0], model.n_estimators))
    for i in range(model.n_estimators):
        leaf_values[:, i] = random_values[i, X_leaves[:, i]]

    # For each sample, calculate the quantiles of the leaf_values
    return np.quantile(leaf_values, np.array(quantiles), axis=1).transpose()

Answer 2

Существенные различия между лесом квантильной регрессии и стандартным регрессором случайного леса заключаются в том, что варианты квантилей должны:

1. Сохраните (все) значения ответа на обучение (y) и сопоставьте их с их конечными узлами во время обучения.
2. Получите значения ответа, чтобы вычислить один или несколько квантилей (например, медиану) во время прогнозирования.

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

Для решения этих проблем существует быстрая, оптимизированная для Cython, совместимая с scikit-learn реализация Quantile Regression Forests, доступная здесь: https://github.com/zillow/quantile-forest .