Почему модель регрессии, созданная XGBoost, зависит от порядка обучающих данных, когда используется более 8194 точки данных?

Когда я использую XGBRegressor для построения модели бустированного дерева на основе 8194 или меньшего числа точек данных (т.е. n_train $\leq$ 8194, где n_train определен в коде ниже) и случайно перемешиваю точки данных перед обучением, метод fit является независимым от порядка, что означает, что он генерирует одну и ту же предсказательную модель каждый раз, когда он вызывается. Однако, когда я делаю то же самое для 8195 точек данных, fit становится зависимым от порядка — он генерирует разные предсказательные модели для каждого вызова. Почему так?

Я прочитал эту статью о XGBoost и почти всю документацию по XGBoost, и описанные в них алгоритмы без подсэмплинга, похоже, являются независимыми от порядка для всех n_train. Поэтому источник зависимости от порядка для наборов данных с большим n_train остается загадкой.

Ниже приведен минимальный скрипт на Python, который иллюстрирует проблему.

import numpy as np
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split
from xgboost import XGBRegressor

M = 2  # число моделей для сравнения
tree_method = 'approx'  # метод дерева XGBRegressor. Попробуйте также 'hist' и 'exact'.
n_disp = 5  # количество элементов y_test_pred[m], которые нужно отобразить
np.set_printoptions(precision=5, linewidth=1000, suppress=True)

# ------------------------------------------------------------------------------------------
def main_func():

    for n_samples in [10243, 10244]:

        # Конструируем X и y
        X, y = make_regression(n_samples=n_samples)

        # Разделяем X и y на обучающую и тестовую выборки
        X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
        n_train = y_train.shape[0]

        # Обучаем модели и используем их для предсказания y_test
        model = M * [None]
        y_test_pred = M * [None]
        for m in range(M):
            model[m] = train_model(n_train, X_train, y_train, X_test, y_test, m)
            y_test_pred[m] = model[m].predict(X_test)
            print('---')
            print(f'n_train = {n_train}')
            print(f'y_test_pred[m][:{n_disp}] для m = {m}:')
            print(y_test_pred[m][:n_disp])

# ------------------------------------------------------------------------------------------
def train_model(n_train, X_train, y_train, X_test, y_test, m):

    # Перемешиваем X_train и y_train
    p = np.random.permutation(n_train)
    X_train = X_train[p]
    y_train = y_train[p]

    # Конструируем и обучаем модель
    model = XGBRegressor(tree_method=tree_method, random_state=42)
    model.fit(X_train, y_train, eval_set=[(X_train, y_train), (X_test, y_test)], verbose=0)

    return model

# ------------------------------------------------------------------------------------------
main_func()

Один запуск этого кода выдает:

---
n_train = 8194
y_test_pred[m][:5] для m = 0:
[ 138.66483  -20.09365   62.82829 -136.29303 -120.78113]
---
n_train = 8194
y_test_pred[m][:5] для m = 1:
[ 138.66483  -20.09365   62.82829 -136.29303 -120.78113]
---
n_train = 8195
y_test_pred[m][:5] для m = 0:
[  20.70109 -125.59986 -140.2009    84.15887  -39.79109]
---
n_train = 8195
y_test_pred[m][:5] для m = 1:
[ -26.50723 -159.95743  -79.36356  108.11007  -38.723  ]

Обратите внимание, что для n_train = 8194, y_test_pred[m][:n_disp] одинаковы для всех m, но для n_train = 8195 — нет.

Внутри скрипта обратите внимание, что я перемешиваю элементы X_train и y_train перед каждым запуском. Я ожидал бы, что это не повлияет на модель, производимую алгоритмом подгонки, учитывая, что, насколько я понимаю, значения признаков сортируются и группируются в начале алгоритма. Однако, если я закомментирую это перемешивание, высокая n_train зависимость от порядка исчезает. Также обратите внимание, что в вызове XGBRegressor tree_method может быть установлен в 'approx', 'hist' или 'auto', а random_state может быть установлен на фиксированное значение, не устраняя зависимость от порядка для больших n_train.

Наконец, в документации XGBoost есть несколько комментариев, которые могут показаться уместными:

• Онлайн Часто задаваемые вопросы по XGBoost утверждает, что проблема “Немного разные результаты между запусками… могут возникать из-за недетерминированности в порядке суммирования с плавающей запятой и многопоточности. Также изменение разбиения данных распределенной структуры может быть проблемой. Хотя общая точность обычно остается неизменной.”
• А Справочник API Python утверждает, что “Использование gblinear boost с обновлением shotgun является недетерминированным, так как использует алгоритм Hogwild.”

По различным причинам, тем не менее, я подозреваю, что эти заметки либо не относятся к делу, либо недостаточны, чтобы объяснить резкий переход к зависимости от порядка, которую я только что описал.

Частичный ответ.

Устанавливая tree_method="exact", я получаю те же результаты на разных итерациях, так что, должен быть источник случайности внутри взвешенных квантилиных эскизов ("approx" и "hist"). Не указывая tree_method, поведение по умолчанию "auto" выбирает "exact" для малых наборов данных, и я полагаю, что вы нашли порог (хотя он может зависеть от других факторов, таких как количество признаков).

Но я не уверен, почему бинирование должно иметь случайный компонент?? И установка random_state даже не фиксирует это.

Ответ на этот вопрос был предложен на странице GitHub для XGBoost:

“Квантилирование работает на потоке данных и очищает сводку
по мере поступления новых данных. В таком случае результаты очистки могут зависеть
от порядка поступления данных.”

Конкретные детали алгоритма обрезки описаны в дополнительных материалах статьи XGBoost, представленной на KDD ’16.

Кроме того, критическое наблюдение было сделано maxaehle на вышеуказанной странице GitHub: “Когда только первые 8194 строки перемешаны, а последняя строка остается последней, оба вывода для 8195 оказываются одинаковыми.”

Более того, пороговое значение $8194$ довольно близко к $2^{13} = 8192$.

Таким образом, предварительно кажется, что существует жестко закодированный порог n_train $= 8195$, при котором алгоритм обрезки или квантилирование становятся активными или сильно зависят от порядка. Точные детали этого остаются неясными.