A General Theoretical Framework for Learning Smallest Interpretable Models

We develop a general algorithmic framework that allows us to obtain fixed-parameter tractability for computing smallest symbolic models that represent given data. Our framework applies to all ML model types that admit a certain extension property. By showing this extension property for decision trees, decision sets, decision lists, and binary decision diagrams, we obtain that minimizing these fundamental model types is fixed-parameter tractable. Our framework even applies to ensembles, which combine individual models by majority decision.

Authors

• Sebastian Ordyniak University of Leeds
• Giacomo Paesani University of Leeds
• Mateusz Rychlicki University of Leeds
• Stefan Szeider Technische Universität Wien

Keywords

• KRR: Computational Complexity of Reasoning
• ML: Transparent, Interpretable, Explainable ML