Counterfactual Explanations for Oblique Decision Trees: Exact, Efficient Algorithms

Miguel Á. Carreira-Perpiñán, Suryabhan Singh Hada

This paper, "Counterfactual Explanations for Oblique Decision Trees: Exact, Efficient Algorithms," by Miguel A. Carreira-Perpiñán and Suryabhan Singh Hada, presents a robust solution for a growing need in AI: explainability. As machine learning models increasingly influence decisions in finance, medicine, and law, the ability to ask "What would I need to change to get a different result?" becomes essential.

TL;DR

The authors provide the first exact and highly efficient algorithm for generating counterfactual explanations for both standard and oblique (hyperplane-split) decision trees. By decomposing a complex, non-differentiable global problem into simple leaf-level convex optimizations, they achieve optimal results in milliseconds, even for high-dimensional data with mixed continuous and categorical features.

What Problem Does This Paper Address?

A counterfactual explanation (CFE) is a statement like: "You were denied a loan because your income was $30,000; if it had been $45,000, you would have been approved." Formally, it is the minimal change to an input feature vector that flips a classifier's decision to a desired target class.

While CFEs are well-studied for differentiable models like neural networks (where we can use gradients), they are notoriously difficult for decision trees. Trees are non-differentiable and non-convex. Existing methods for trees were often limited to binary classification, restricted to categorical features, or relied on slow, approximate searches that didn't guarantee the "minimal" change.

This paper bridges that gap, specifically targeting oblique decision trees. Unlike standard trees that split on one feature at a time (axis-aligned), oblique trees use linear combinations of features (hyperplanes), making them much more powerful but harder to analyze.

Methods

The authors' core "aha moment" is realizing that while the tree's global decision function is a mess to optimize, the region leading to any specific leaf is just a simple geometric shape (a box for axis-aligned trees or a polytope for oblique trees).

  1. Divide and Conquer: To find the best CFE for a target class, the algorithm simply iterates through every leaf labeled with that target class.
  2. Leaf-Level Optimization: Within a single leaf, the problem becomes: "Find the point in this polytope closest to my original input."
    • For oblique trees, this is a standard convex optimization problem. If using the $L_1$ distance (changing few features), it’s a Linear Program (LP). If using $L_2$ (squared distance), it’s a Quadratic Program (QP).
  3. For axis-aligned trees, the authors prove the solution is even simpler: a "median" formula that can be calculated almost instantly without a solver.
  4. Handling Categorical Data: They treat categorical features via one-hot encoding and solve the resulting mixed-integer problem exactly through enumeration or specialized solvers like CPLEX/Gurobi.
  5. Constraints: The framework easily incorporates user constraints, such as "don't change my race" or "age can only increase."
Figure 2: An oblique tree (left) and its corresponding partition of the input space into polytopes (right). The CFE $x^*$ is the closest point in a target-class region to the source instance $\bar{x}$.

Datasets

The algorithm was evaluated on several standard UCI repository datasets and MNIST:

  • MNIST: Handwritten digits (784 continuous features).
  • Adult: Predicting income levels (mixed continuous and categorical).
  • German Credit: Credit risk assessment (mixed).
  • Breast-Cancer, Spambase, Letter: Various classification tasks with continuous features.

Key Insights and Ideas

  • Exactness is Feasible: Contrary to the belief that non-differentiable models require heuristic search, the authors show that for trees, we can find the mathematically perfect minimal change efficiently.
  • Oblique Trees are "Explainable": Oblique trees trained with modern algorithms like TAO (Tree Alternating Optimization) reach accuracies comparable to neural nets. This paper proves they can be just as interpretable through CFEs.
  • Diversity of Explanations: Because the algorithm checks multiple leaves, it can naturally provide a set of different ways to change a decision (e.g., "either increase your income OR decrease your debt"), rather than just one.

Key Results

  • Speed: The algorithm typically runs in milliseconds. Even for the high-dimensional MNIST dataset, it finds exact solutions in about 40-110ms.
  • Optimality: Compared to the "Feature Tweaking" heuristic (a popular existing method), this algorithm consistently found counterfactuals with significantly smaller distances (lower "cost" to the user) and never failed to find a solution when one existed.
  • Visualizing Change: On MNIST, the authors demonstrated how different distance metrics affect the explanation. $L_1$ changes a few pixels by a lot, while $L_2$ changes many pixels by a tiny, almost invisible amount.
Figure 4: MNIST counterfactuals. Each row shows a source digit (e.g., a '2') and the minimal changes needed to make the tree see it as a different digit (e.g., a '0').

Limitations and Future Work

  • The "Adversarial" Problem: For images (like MNIST), the "minimal" change often looks like random noise that tricks the model rather than a semantically meaningful change. The authors suggest that finding "realistic" counterfactuals for images remains a difficult, open problem.
  • Forests: While this works perfectly for a single tree, finding exact CFEs for a Random Forest is NP-hard. The authors suggest this method could potentially be adapted as a building block for forest-based explanations.
  • Extension: Future work could extend this to regression trees or trees with more complex "softmax" leaves.

Summary updated

Abstract

We consider counterfactual explanations, the problem of minimally adjusting features in a source input instance so that it is classified as a target class under a given classifier. This has become a topic of recent interest as a way to query a trained model and suggest possible actions to overturn its decision. Mathematically, the problem is formally equivalent to that of finding adversarial examples, which also has attracted significant attention recently. Most work on either counterfactual explanations or adversarial examples has focused on differentiable classifiers, such as neural nets. We focus on classification trees, both axis-aligned and oblique (having hyperplane splits). Although here the counterfactual optimization problem is nonconvex and nondifferentiable, we show that an exact solution can be computed very efficiently, even with high-dimensional feature vectors and with both continuous and categorical features, and demonstrate it in different datasets and settings. The results are particularly relevant for finance, medicine or legal applications, where interpretability and counterfactual explanations are particularly important.
BibTeX
@inproceedings{carreiraperpinan2021counterfactual,
  author = {Miguel Á. Carreira-Perpiñán and Suryabhan Singh Hada},
  title = {{Counterfactual Explanations for Oblique Decision Trees: Exact, Efficient Algorithms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=k3gjiqKx-m},
}
Figure