Research map / Learning theory and algorithms / Prediction and decision losses
Leveraging Predictive Equivalence in Decision Trees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a minimal DNF/Blake canonical boolean representation of decision trees that removes predictive equivalence, and applies it to Rashomon set counting, RID variable importance, test-time missing data, and cost-efficient Q-learning evaluation.
Problem
Decision trees with identical decision boundaries can have different evaluation orders, which makes model selection, variable importance, missing-value handling, and test-time cost evaluation ambiguous.
Approach
Convert each tree's positive and negative leaves into a minimal DNF via a modified Quine-McCluskey procedure (plus Blake canonical form for all sufficient conditions), yielding a canonical representation that is identical for predictively equivalent trees and can predict under missing features whenever the boundary is determined.
Key results
- Across Rashomon sets on COMPAS, Coupon, Wine, and Wisconsin, predictively distinct trees are substantially fewer than total trees (e.g., COMPAS 12785 total vs 2135 ours, Coupon 666 vs 55).
- Correcting for predictive equivalence shifts RID on a synthetic DGP, reducing 1-Wasserstein distance to ground truth from 0.232 to 0.182 for X3.
- Optimized Q-learning purchase policy reduces average feature acquisition cost relative to path-based and naive purchasing on every main dataset without changing the decision boundary.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| control for predictively equivalent trees | RID · Synthetic DGP, X1 importance | 1-Wasserstein distance to ground truth: 0.120 -> 0.092 | Helped |
| control for predictively equivalent trees | RID · Synthetic DGP, X2 importance | 1-Wasserstein distance to ground truth: 0.136 -> 0.105 | Helped |
| control for predictively equivalent trees | RID · Synthetic DGP, X3 importance | 1-Wasserstein distance to ground truth: 0.232 -> 0.182 | Helped |
| use DNF prediction instead of path-based tree traversal | decision trees under test-time missingness · real-world datasets with synthetic missingness | prediction coverage | Helped |
| use BCF/Q-learning to choose feature acquisition order | decision trees · COMPAS, Wine Quality, Wisconsin, and Coupon | average evaluation cost | Helped |
| use BCF/Q-learning to choose feature acquisition order | decision trees · Iris Setosa | average evaluation cost | No clear effect |
Surprising findings
- Many single trees in a Rashomon set are predictively equivalent, so standard Rashomon sets over-represent some decision logic.
- A majority of samples can be predicted by decision trees even with test-time missingness above 50% per feature.
Limitations
- Minimal DNF computation is NP-hard in general and relies on small trees with few leaves.
- Cannot handle informative (MNAR) missingness that appears only at training time; test-time-only missingness assumed.
- Results focus on single trees with max depth 3 and binary classification.
Experimental setup
Datasets: COMPAS Coupon Wine Quality Wisconsin Netherlands Broward FICO Spiral Tic-Tac-Toe Iris Higgs
Benchmarks: COMPAS Coupon Wine Quality Wisconsin Netherlands Broward FICO Spiral Tic-Tac-Toe Iris
Metrics: Rashomon set size Kolmogorov-Smirnov distance 1-Wasserstein distance fraction of predictable samples under missingness average acquisition cost
Baselines: CART path-based missingness handling naive purchase policy original RID
Builds on: TreeFARMS Rashomon Importance Distribution Quine-McCluskey algorithm Q-learning MINTY
Closest papers by meaning
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.87)
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.87)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.87)
- Generative Model for Decision Trees (AAAI 2024 · similarity 0.87)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.87)
- Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.