Succinct Explanations with Cascading Decision Trees

Jialu Zhang, Mark Santolucito, Ruzica PiskacOpenReview 2020 · OpenReview

TL;DR

This paper introduces "Cascading Decision Trees" (CDTs), a novel approach to make decision tree explanations more concise without sacrificing predictive accuracy. By breaking down a large decision tree into a sequence of smaller, specialized subtrees, CDTs significantly shorten the explanation paths for positive classifications, making them easier for humans to understand.

What Problem Does This Paper Address?

Traditional decision trees, while interpretable, often grow excessively deep when trained on complex, modern datasets. These deep trees lead to long, convoluted "explanation paths" that are difficult for humans to follow, hindering true comprehensibility. This depth can also contribute to overfitting and make models less robust, especially when dealing with missing data. The paper aims to bridge the gap between high accuracy (often found in "black-box" models) and the need for understandable explanations, a critical requirement in fields like medicine and scientific research.

Methods

The core innovation is the "Cascading Decision Trees" (CDTs) model. Instead of a single, deep decision tree, CDT constructs a sequence of smaller decision subtrees. The key idea is to separate the decision path from the explanation path. Each subtree is trained to classify positive samples efficiently, and if a positive classification is made, the process stops, and the explanation path from that specific subtree is reported. This sequential approach ensures that explanations are generated by the earliest possible subtree, thus keeping them short. The training process iteratively removes correctly classified positive samples to train subsequent subtrees, focusing on the remaining challenging cases.

Datasets

The authors evaluated their approach on ten standard UCI Machine Learning Repository datasets. They also applied it to a real-world application: continuous integration (CI) build status prediction. The specific UCI datasets mentioned include:

  • Breast Cancer
  • Heart Disease
  • Wisc Breast Cancer
  • Cervical Cancer
  • Credit Card
  • German Credit
  • Climate
  • Happiness
  • Ionosphere
  • Sonar

Key Insights and Ideas

  • Separating Decision and Explanation Paths: This is the fundamental insight. By allowing a shorter "explanation path" to be found in an earlier subtree, even if the full "decision path" in a monolithic tree would be longer, the model achieves succinctness.
  • Targeting Positive Classifications: The cascading approach is specifically optimized for generating explanations for positive predictions. This is motivated by real-world scenarios where understanding why something is classified as "positive" (e.g., a disease) is paramount.
  • Iterative Refinement: The sequential nature of training subtrees, where correctly classified positive samples are removed, allows each subsequent subtree to focus on harder-to-classify instances, leading to more efficient and targeted explanations.
  • Overfitting Mitigation: The paper suggests that shorter explanation paths, by limiting tree depth, inherently help in avoiding overfitting, which is linked to the VC dimension of decision trees.

Key Results

  • Shorter Explanations: On average, Cascading Decision Trees generated explanation paths that were 63.38% shorter than those from classic decision trees with PI-explanation (Prime Implicant explanation).
  • Competitive Accuracy: Despite generating shorter explanations, CDTs maintained or even improved prediction accuracy compared to baselines on most datasets. For instance, on the German Credit dataset, CDT achieved a 5.0% higher average prediction accuracy than PI-explanation.
  • Robustness to Missing Data: CDTs demonstrated significantly better robustness against missing data. While PI-explanation models often failed when encountering missing values along their longer paths, CDTs were less affected.
  • Efficiency: The training process for CDTs was remarkably fast, completing ten UCI datasets in seconds, compared to minutes or even hours for some state-of-the-art methods.

Limitations and Future Work

  • Focus on Positive Classifications: The current CDT algorithm is primarily designed for generating succinct explanations for positive classifications. While the paper mentions symmetry for negative classifications, the core development and evaluation focus on the positive case.
  • Computational Cost of Base Trees: While the overall CDT training is fast, the efficiency of building each individual subtree depends on the underlying classic decision tree algorithm. The paper notes that optimal decision tree learners could be used as base trees for potentially better accuracy, but at a higher training cost.
  • Future Work: The authors suggest combining their CDT approach with pruning techniques and exploring different goodness measures for decision node splits. They also highlight the potential for CDT to be combined with optimal decision tree learners for further improvements.

Summary updated

Abstract

Classic decision tree learning is a binary classification algorithm that constructs models with first-class transparency - every classification has a directly derivable explanation. However, learning decision trees on modern datasets generates large trees, which in turn generate decision paths of excessive depth, obscuring the explanation of classifications. To improve the comprehensibility of classifications, we propose a new decision tree model that we call Cascading Decision Trees. Cascading Decision Trees shorten the size of explanations of classifications, without sacrificing model performance overall. Our key insight is to separate the notion of a decision path and an explanation path. Utilizing this insight, instead of having one monolithic decision tree, we build several smaller decision subtrees and cascade them in sequence. Our cascading decision subtrees are designed to specifically target explanations for positive classifications. This way each subtree identifies the smallest set of features that can classify as many positive samples as possible, without misclassifying any negative samples. Applying cascading decision trees to new samples results in a significantly shorter and succinct explanation, if one of the subtrees detects a positive classification. In that case, we immediately stop and report the decision path of only the current subtree to the user as an explanation for the classification. We evaluate our algorithm on standard datasets, as well as new real-world applications and find that our model shortens the explanation depth by over 40.8\% for positive classifications compared to the classic decision tree model.
BibTeX
@misc{zhang2020succinct,
  author = {JIALU ZHANG and Mark Santolucito and Ruzica Piskac},
  title = {{Succinct Explanations with Cascading Decision Trees}},
  year = {2020},
  eprint = {2010.06631},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.06631},
  howpublished = {OpenReview},
}
Figure