`xgboost`中的`tree_method = 'exact'`真的意味着精确的贪心算法吗？

Question

tree_method = 'exact'

中的

xgboost

真的意味着使用精确的贪心算法进行分割查找吗？

我问这个问题是因为

xgboost

运行得不合理的快。这是我用于运行测试的脚本

from xgboost import XGBRegressor as rr
import numpy as np
from sklearn.model_selection import train_test_split
import pickle 
import sys
from time import time

t1 = time()
data = sys.argv[1]
with open(data, 'rb') as source:
    data = pickle.load(source)
np.random.shuffle(data)
x = [item[0] for item in data]
y = [item[1] for item in data]
x_train, x_val, y_train, y_val = train_test_split(x, y, test_size = 0.2, random_state = 100)
eval_set = [(x_train, y_train), (x_val, y_val)]

# Exact model
model_exact = rr(max_depth = 5, 
                 n_estimators = 1,
                 slient = False, 
                 min_child_weight = 0, 
                 tree_method = 'exact')
model_exact.fit(x_train, 
                y_train, 
                eval_set=eval_set,
                eval_metric="mae",
                early_stopping_rounds=30)
t2 = time()
print(f"Time used: {t2 - t1}")

用于测试的pickled数据已上传这里。

每个实例中有

96

个特征，总共有

11450

个实例。

xgboost

通过在单核 (

0.9804270267486572s

) 上运行来找到

1.3 GHz Intel Core i5

中的第一个分割。如果

xgboost

实际上对所有可能的分割执行贪婪搜索，则意味着

xgboost

仅在

11450 x 96 = 1099200

!

 中评估 

0.9804270267486572s

分割

xgboost

真的有这么厉害吗？还是我理解错了

tree_method = exact

？

Answer 1

我没有理由怀疑它已经运行了所有分割的完整贪婪搜索。

如果您的特征包含重复值，则可能的拆分数量可能比

11450 x 96 = 1099200

小得多。 对于具有

n_unique - 1

值的特征，只有

n_unique

有用的分割。

并且分割的统计数据不需要从头开始重新计算：将阈值向右移动一个槽意味着只需从右孩子向左移动几行，并且通常可以计算对分割标准的影响，而无需需要从头开始重新计算。