基于多变量布尔规则的最优分类树 (BooleanOCT)
内容提要
该文综述基于混合整数规划（MIP/MIO）的最优决策树研究进展，涵盖流式MIO表达式、支持向量机与1-范数多元决策树、逻辑损失分段逼近、Benders分解加速、鲁棒分类树、公平性约束及可解释性度量等方向。实验表明，这些方法在性能、速度和精度上优于传统启发式方法。
延伸解读
MIP方法在决策树优化中的演进
文章梳理了基于混合整数规划（MIP）的最优决策树研究进展，从2016年的基础MIP公式到2023年的逻辑损失分段逼近，方法不断丰富。这些工作致力于解决传统启发式方法可能陷入局部最优的问题，通过精确优化提升树模型的性能。读者可以关注不同年份提出的技术如何逐步改进计算效率和模型质量。
性能提升与可扩展性突破
多项研究在实验对比中展示了MIP方法的优势。例如，基于Benders分解的流式MIP公式比现有技术快50倍，预测精度提升达13.8%；支持向量机与1-范数多元决策树在包含24.5万样本的数据集上优于启发式方法。这些结果表明，MIP方法在大规模数据集上具有实际应用潜力。
公平性与可解释性的兼顾
文章提到，MIP框架可以容纳边际约束和公平性约束，并提出了决策复杂度作为可解释性度量。在流行数据集上的实验显示，方法能在几乎完全平等的情况下保持精度。这为需要兼顾公平与透明的应用场景提供了新的可能性，但读者也需注意公平性约束可能带来的精度权衡。
鲁棒性与连续变量优化
针对数据中的不确定性，有研究提出学习鲁棒分类树的方法，在最差情况准确率上提高了12.48%。同时，有工作解决了连续变量完全优化和不平衡数据处理等开放问题，并实现了可证明的最优结果。这些进展扩展了MIP决策树的适用边界，但实际部署时仍需考虑计算成本。
Q&A
基于混合整数规划的最优决策树方法相比传统启发式方法有哪些优势？
实验表明，这些方法在性能、速度和精度上优于传统启发式方法。例如，基于流的MIP公式利用Benders分解比现有MIP技术快50倍，预测精度提高多达13.8%；支持向量机和1-范数多元决策树方法在包含245,000个样本的数据集上优于现有启发式方法和其他基于MIP的技术。
如何利用混合整数规划构建具有公平性约束的最优分类树？
通过设计一个MIO框架来学习最优分类树，并扩展以支持任意公平性约束。该框架还提出了新的模型可解释性度量标准——决策复杂度，并在流行数据集上对公平性、可解释性及预测准确性之间的权衡进行了综合分析，证明在几乎完全平等的情况下仍能保持精度。
有哪些加速最优决策树训练的方法？
包括使用Benders分解的基于流的MIP公式，比现有MIP技术快50倍；利用线性规划数据选择方法选择数据样本，实现对大数据集的有效训练；以及采用分析界限和数据结构等现代技术的实用算法，在可扩展性、速度和最优性方面具有优势。
最优决策树如何处理连续变量和不平衡数据？
通过提出一种决策树优化框架，解决了不平衡数据处理和连续变量完全优化两个开放性问题。该框架还包含一种可扩展算法，可以在存在连续变量的情况下产生可证明的最优结果，并相对于现有技术将决策树构建速度提高了数个数量级。
基于混合整数规划的最优逻辑树模型是如何处理逻辑损失的？
该模型采用线性分段逼近法处理逻辑损失，并与L1正则项耦合，证明其能够诱导出具有更好可解释性和竞争性推广能力的树状模型，相对于现有的基于MIP的方法。
如何构建鲁棒分类树以提高最差情况准确率？
基于混合整数规划技术，提出了一种学习鲁棒分类树的方法，通过问题转化和约束生成的解决方法，在公共可用数据集上展示了最差情况准确率提高了12.48%，平均情况准确率提高了4.85%。
