决策树训练加速新方法：效率提升高达99%

梯度提升决策树是一种常用于大规模在线搜索应用的机器学习模型，因为它兼具高精度和高效率。然而，要保持这种效率，通常意味着需要限制决策树模型在做决策时考虑的数据特征数量。如果决策树模型的训练数据有数千个可能的特征，而最终模型只会用到其中一小部分（例如一两百个），那么大部分评估特征的工作将是徒劳的，导致训练效率低下。

在提交给国际人工智能与统计会议的一篇论文中，我们提出了一种新的梯度提升决策树训练方法。在总特征集远大于必要特征集的情况下，该方法比最高效的现有方法（一种称为梯度提升特征选择的技术）要高效得多。

在测试中，我们使用了三个流行的基准数据集，将我们的方法与另外三种梯度提升决策树的实现进行了比较。相对于最高效的前代方法，我们的方法将训练时间减少了 50% 到 99%，同时保持了结果模型的准确性。

我们还发现，我们的方法特别适合多任务训练，即同时训练机器学习模型执行多项任务。在实验中，当系统被同时训练来执行三项任务时，它在每项任务上的表现都比单独训练一项任务时更好。与使用梯度提升决策树进行多任务训练的标准方法相比，我们的方法在所有三项任务上都提高了性能。

决策树是一种二叉树，类似于流程图，呈现一系列二元决策。每个决策点，树都会分成两个分支。最终，树上的每条路径都会到达一个称为叶子的终点。每个叶子都有一个相关联的数字，代表其对某个分类任务的投票结果。

一个使用梯度提升决策树的模型由多棵（可能数百棵）树组成。在训练期间，模型按顺序构建树。每棵新树的设计都旨在最小化前面所有树的残差（这就是梯度提升）。模型的整体输出是所有树输出的聚合。

在每棵树的每个新决策点，模型必须选择一个能最小化整体模型错误率的标准。这意味着需要评估训练数据的每一个可能特征。如果数据有1000个特征，但只有100个最终会被证明是有用的决策标准，那么大部分工作就被浪费了。

集体行动

我们通过改造常见的二分搜索算法来解决这个问题。在训练之前，我们对每个特征的值进行归一化，使它们都落在0到1的范围内。然后，我们随机将特征分成两组，创建两个伪特征，其值就是各个特征归一化值的总和。我们重复这个过程几次，生成几对将特征集均匀划分的伪特征。

在训练期间，在每个决策点，我们使用一对伪特征来评估树，以普通方式为每个伪特征选择一个分裂点。然后，我们取预测效果更好的那个伪特征，将其随机分成两个新的伪特征，并再次测试分裂点。

我们重复这个过程，直到收敛到单个特征作为该决策点的标准。我们评估的伪特征数量等于特征数量的对数，而不是评估每一个特征。

这种方法只是一种近似，但在论文中，我们给出了理论分析，表明只要有足够的训练数据，该近似仍应能收敛到一组最优的决策树。

我们也对这种方法进行了实证测试，使用了三个标准的机器学习研究基准数据集：一个手写数字数据集（目标是识别数字），一个航班信息数据集（目标是预测延误），以及一个图像识别任务。我们将我们系统的性能与另外三种梯度提升决策树的标准实现进行了比较。

在所有情况下，我们系统的性能与表现最佳的基线模型相比相差不到一个百分点（或领先或落后），但其训练时间却短得多。训练时间的差异取决于系统设定的目标准确率，但对于航班数据集，训练时间的加速持续在2倍左右；对于手写数字识别任务，持续在10倍左右；对于图像识别任务，持续在100倍左右。

研究领域

机器学习

搜索与信息检索

标签

人工智能 (AI)

梯度提升决策树

会议

AISTATS 2020

相关出版物

可扩展的（多任务）梯度提升树特征选择