决策树训练加速技术解析

梯度提升决策树是一种在大型在线搜索应用中常用的机器学习模型，兼具高准确性和高效率。然而，为了保持效率，必须限制梯度提升决策树在决策时考虑的数据特征数量。如果决策树模型的训练数据有许多可能特征（例如数千个），而最终仅使用其中一小部分（例如几百个），训练过程就会变得低效，因为模型评估的大多数特征最终都被证明是无关的。

在一篇被国际人工智能与统计会议接受的论文中，我们提出了一种新的梯度提升树训练方法。在总特征集大于必要特征集的情况下，该方法比最高效的前身技术更加高效。

在测试中，我们使用三个流行的基准数据集将我们的方法与其他三种梯度提升决策树实现进行了比较。相对于最高效的前身技术——梯度提升特征选择，我们的方法将训练时间减少了50%到99%，同时保持了所得模型的准确性。

我们还发现，我们的方法特别适合多任务训练，即机器学习模型被训练同时执行多个任务——例如识别狗、猫和马的图像，而不仅仅是三者之一。在实验中，当我们的系统同时训练三个任务时，它在每个任务上的表现都比单独训练一个任务时更好。我们还将它与使用梯度提升树进行多任务训练的标准方法进行了比较，发现它在所有三个任务上都提高了性能。

决策树是一种二叉树，类似于流程图，呈现一系列二元决策。每个决策都会使树分支出两条路径。最终，通过树的每条路径都会到达称为叶子的终端点。每个叶子都有一个相关数字，代表其对某些分类任务的投票：是，我认为这是一只狗；不，我认为这首歌与查询不匹配。

使用梯度提升决策树的模型包含多个树——可能有数百个。在训练期间，模型按顺序构建树。每个新树都旨在最小化前驱树的残差：这就是梯度提升。模型整体的输出是所有树的聚合输出。

在每个树的每个新决策点，模型必须选择一个决策标准，以最小化模型整体的错误率。这意味着需要评估训练数据的每个可能特征——对于音乐曲目而言，包括艺术家、标题、流派、发行日期、比特率、音轨编号等。

对于每个特征，模型必须找到最佳分割点，即决定路径向左还是向右分支的阈值。如果数据有1000个特征，但最终只有100个被证明可用作决策标准，那么大部分工作都是浪费的。

集体行动

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

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

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

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

我们还在三个机器学习研究的标准基准上实证测试了我们的方法。一个是手写数字数据集，目标是识别数字；另一个是航班信息数据集，目标是预测延误；第三个是图像识别任务。我们将我们系统的性能与其他三种梯度提升树的标准实现进行了比较。

在所有情况下，我们系统的性能与最佳基线的性能相差不到一个百分点——有时领先有时落后——但其训练时间要短得多。训练时间的差异因系统的目标准确率而异，但对于航班数据集，训练时间加速 consistently 约为两倍；对于手写识别任务， consistently 约为10倍；对于图像识别任务， consistently 约为100倍。

研究领域

• 机器学习
• 搜索和信息检索

标签

• 人工智能
• 梯度提升决策树

会议

• AISTATS 2020

相关出版物

• 可扩展的（多任务）梯度提升树特征选择
  更多精彩内容 请关注我的个人公众号 公众号（办公AI智能小助手）或者 我的个人博客 https://blog.qife122.com/
  对网络安全、黑客技术感兴趣的朋友可以关注我的安全公众号（网络安全技术点滴分享）

公众号二维码

公众号二维码