May, 2024

决策树算法的超快速选择

PDF
TL;DR我们提出了一种名为 Superfast Selection 的新颖系统方法，用于在表格数据上选择决策树和特征选择算法的 “最优分裂”。该方法通过降低时间复杂度（从 O（MN）降至 O（M））来加快在单个特征上的分裂选择，M 表示输入示例的数量，N 表示唯一值的数量。此外，消除了特征值异质性的预编码需求，例如独热或整数编码。为了展示 Superfast Selection 的高效性，我们将其集成到 CART 算法中，创造了我们所称的 Ultrafast Decision Tree (UDT)。这种改进使 UDT 能够在时间复杂度为 O（KMlogM）（其中 K 是特征的数量）的情况下完成训练过程。此外，Training Only Once Tuning 使得 UDT 可以避免寻找最优超参数所需的重复训练过程。实验证明，在笔记本电脑上，UDT 可以在 1 秒内完成对 KDD99-10％数据集（494K 个示例，41 个特征）的单次训练，并在 0.25 秒内使用 214.8 个超参数集进行调优。
发现论文，激发创造
  • （多任务）梯度提升树的可扩展特征选择

    本文提出了一种可伸缩的基于前向特征选择的梯度提升决策树方法，通过一种新颖的群体测试过程，在高维度下工作良好，并具有较好的理论性能和计算保证，可用于搜索和推荐中的排名和相关模型的构建。同时，该方法扩展到多任务设置，允许从多个任务中选择通用特征和选择任务特定特征，与现有的梯度提升决策树方法相比，在模型性能度量方面表现相当，但训练时间有显著提升。

    Sep, 2021

  • 一种可扩展的基于 MIP 的学习最优多变量决策树方法

    本文提出了一种新的基于支持向量机和 1 - 范数分多元决策树（ODT）训练的混合整数规划（MIP）公式，利用线性规划（LP）数据选择方法选择数据样本，实现了对大数据集的有效训练，并在包含 245,000 个样本的数据集上验证了该方法优于现有的启发式方法和其他基于 MIP 的技术的效果。

    Nov, 2020

  • 决策树学习中选择的力量

    我们提出了一种简单的决策树学习算法的泛化方法，称为 Top-k，它考虑了 k 个最佳属性作为可能的分割点，相较于贪婪算法和最优决策树算法，在准确率和可扩展性方面都取得了显著的优势。

    Oct, 2023

  • BUFF：基于提升决策树的超快速流匹配

    基于树模型优于深度学习模型在处理表格数据任务方面的表现，我们采用条件流匹配生成模型并使用不同技术融合了 Gradient Boosted Trees 的使用，通过在多个公共数据集上进行多个分析任务的评估，展示了大多数高级仿真任务的训练和推理时间能够加速数个数量级。该应用还可以扩展至低级特征模拟和具备竞争性性能的条件生成。

    Apr, 2024

  • 通用和可扩展的最优稀疏决策树

    通过提出一种决策树优化框架，解决了当前领域中两个开放性问题：不平衡数据处理和连续变量完全优化。此外，我们还介绍了一种可扩展的算法，可以在存在连续变量的情况下产生可证明的最优结果，并相对于现有技术将决策树构建速度提高了数个数量级。

    Jun, 2020

  • 面向大数据的超高维特征选择

    本文提出了一种新的自适应特征缩放方案用于大数据上的超高维特征选择，解决了激活大量特征时优化速度缓慢的问题，采用特征生成方法迭代激活一组特征并通过多重核学习子问题得到最优解，通过加速近端梯度算法在原始形式中求解多重核学习子问题并采用缓存技巧加速训练，通过大量论文实验验证了方法的竞争性能。

    Sep, 2012

  • 一种用于学习瘦树的端到端特征选择方法

    通过同时进行特征选择和树集成学习的方法，我们提出了 Skinny Trees 工具包，利用 Group l0-l2 正则化及变分树的不断优化方法，实现了高效的特征选择和树集成学习，并在性能上超越了现有工具包 LightGBM 和 Random Forests。

    Oct, 2023

  • 利用决策树进行高维数据的快速监督哈希

    本文利用增强决策树来实现哈希中的非线性，提出了基于次模形式的哈希二进制码推断问题和用于解决大规模哈希推断的高效 GraphCut 块搜索方法。实验证明，该方法在检索准确性和训练时间方面显著优于大多数最先进的方法，尤其是对于高维数据，该方法的训练时间比许多方法快数个数量级。

    Apr, 2014

  • 最优决策桩的非参数变量筛选

    通过使用决策树，我们推导出了非参数模型中变量选择的有限样本性能保证，并发现决策树可以用于实现一致的模型选择，即使用于估计目的时高度不准确。

    Nov, 2020

  • 无模型特征选择以促进表格数据中发现不同子组

    该论文提出了一个面向数据的 AI 框架，可以自动选择重要特征，实现自动发现不同的数据子组并提高检测性能。通过在 MIMIC-III 和 Allstate Claims 公开数据集上的验证，该框架比现有的六种特征选择方法减少了 81 倍和 104 倍的特征选择时间，并实现了有竞争力的检测性能。

    Mar, 2022