A Uniform Language to Explain Decision Trees

Decision trees are harder to explain than we thought: While decision trees are traditionally considered "easily interpretable," the paper reveals that existing frameworks for explaining them are incomplete. Previous logic-based approaches (FOIL) couldn't capture all the important questions users need answered about why a tree made a specific decision.

A new unified language for asking questions about AI decisions: The researchers developed Q-DT-FOIL and OPT-DT-FOIL—formal languages that can express many different types of explanations people might want from decision trees, from simple "why did you classify this as X?" to more complex questions about what would need to change for a different outcome.

Explanations can be optimized for different goals: The framework allows users to specify what matters most in an explanation—whether that's finding the shortest explanation, the most likely scenario, or explanations that satisfy other fairness or transparency objectives. This flexibility is important because different stakeholders may need different types of explanations.

Efficiency is achievable without sacrificing completeness: Despite the added complexity of handling decision trees specifically (rather than generic AI models), the researchers proved that explanations can be computed in polynomial time using standard computational tools (SAT solvers), making the approach practical for real-world use.

Formal rigor matters for responsible AI: By using mathematical logic to precisely define what "explanation" means, this work helps ensure that when organizations claim their AI systems are interpretable, they're actually meeting rigorous standards rather than relying on vague notions of transparency.