Research map / Learning theory and algorithms / Prediction and decision losses
A General Theoretical Framework for Learning Smallest Interpretable Models
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.
Presents a general fixed-parameter tractable branching framework for learning smallest interpretable models (decision sets, decision lists, decision trees, BDDs, and their majority ensembles) parameterized by solution size plus the feature-difference bound δ.
Problem
Finding smallest symbolic ML models (decision trees, decision sets, decision lists, BDDs, and ensembles) that classify given binary data correctly is NP-hard; the goal is to obtain fixed-parameter tractability with respect to natural parameters.
Approach
Defines strong and weak "extendability" properties of model types; if a model type admits an efficient procedure returning a small complete set of strict extensions (guided by annotated examples for strongly extendable types, or via useful feature sets for BDDs), a bounded-depth branching algorithm yields FPT algorithms for minimum models and ensembles.
Key results
- Decision sets, decision lists, and decision trees are strongly extendable, giving FPT algorithms for minimum model size parameterized by s + δ, with O*((δ+s+1)^s) style branching for decision lists.
- BDDs and BDD-ensembles are shown to be extendable, yielding FPT algorithms parameterized by s + δ (BDD-MMS and BDD-MEMS).
- Minimum model size is W[2]-hard parameterized by s alone for all model types, and DS/DL with one term or one literal per term is NP-hard even for δ = 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the framework to decision sets, decision lists, and decision trees | Smallest-model learning · Decision sets, decision lists, and decision trees | Parameterized tractability | Helped |
| Apply the framework to binary decision diagrams | Smallest-model learning · Binary decision diagrams | Parameterized tractability | Helped |
| Apply the framework to ensembles | Decision-set, decision-list, decision-tree, and BDD ensembles · Ensemble minimum model size | Parameterized tractability | Helped |
| Parameterize minimum-model learning by solution size alone | Decision sets, decision lists, decision trees, and binary decision diagrams · Minimum model size | Parameterized complexity | Hurt |
Surprising findings
- Finding a decision set or decision list with only one term (or terms of maximum size 1) is NP-hard even when δ = 2.
- The annotation approach that works for decision sets, lists and trees does not seem to apply to BDDs.
Limitations
- BDD case has branching factor exponential in s (δ^O(s)), and the annotation approach does not apply to BDDs.
- Results are stated for binary (Boolean) features only; extension to ordered domains requires an extra domain-size parameter.
- Hardness results show δ cannot be dropped and solution size alone is insufficient for DS/DL term-based parameters.
Experimental setup
Builds on: Komusiewicz et al. 2023 annotation approach for decision trees Ordyniak and Szeider 2021 decision tree FPT algorithm Eiben et al. 2023
Closest papers by meaning
- Learning Small Decision Trees for Data of Low Rank-Width (AAAI 2024 · similarity 0.85)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.85)
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.85)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.84)
- Local vs. Global Interpretability: A Computational Complexity Perspective (ICML 2024 · similarity 0.84)
- On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.84)
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.