Decision trees with short explainable rules

Decision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretability/explainability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters. This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our new measure (which we call the explanation size) and the more classical measures of worst-case and average depth. We also show that from our characterizations it is possible to obtain polynomial algorithms that guarantee O ( ln ⁡ n ) -approximation (hence optimal if P ≠ N P ) for the minimization of both the average/worst-case explanation size and the average/worst-case depth.

Authors

• Victor F.C. Souza
• Ferdinando Cicalese
• Eduardo Sany Laber
• Marco Molinaro

Keywords

• Decision trees
• Interpretable ML
• Exlpainability measures