Learning Optimal Decision Trees with SAT
Learning Optimal Decision Trees with SAT
复制标题
通过 SAT 学习最优决策树
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Joao Marques
中科院分区：
文献类型：
--
作者：
Nina Narodytska;Alexey Ignatiev;Filipe Pereira;Joao Marques
机器学习（ML）预测的解释在不同的环境中具有根本的重要性。此外，解释应简洁明了，使人类易于理解。 决策树是开发可解释的ML模型的常用方法，其动机是决策树路径和规则之间的自然映射。显然，较小的树与较小的规则相关性很好，因此一个挑战是设计解决方案来计算给定训练数据的最小尺寸决策树。虽然简单的公式化，最小尺寸的决策树的计算结果是一个非常具有挑战性的计算问题，没有实际的解决方案是已知的。本文提出了一种基于SAT的模型，用于计算给定训练数据的最小决策树。与过去的工作形成鲜明对比，所提出的SAT模型的规模为公开的数据集的实际利益。
Explanations of machine learning (ML) predictions are of fundamental importance in different settings. Moreover, explanations should be succinct, to enable easy understanding by humans. Decision trees represent an often used approach for developing explainable ML models, motivated by the natural mapping between decision tree paths and rules. Clearly, smaller trees correlate well with smaller rules, and so one challenge is to devise solutions for computing smallest size decision trees given training data. Although simple to formulate, the computation of smallest size decision trees turns out to be an extremely challenging computational problem, for which no practical solutions are known. This paper develops a SAT-based model for computing smallest-size decision trees given training data. In sharp contrast with past work, the proposed SAT model is shown to scale for publicly available datasets of practical interest.