AAAI 2024technical4 citations
A General Theoretical Framework for Learning Smallest Interpretable Models
Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki, Stefan Szeider
Abstract
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.
BibTeX
@article{Ordyniak_Paesani_Rychlicki_Szeider_2024, title={A General Theoretical Framework for Learning Smallest Interpretable Models}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/28937}, DOI={10.1609/aaai.v38i9.28937}, abstractNote={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.}, number={9}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Ordyniak, Sebastian and Paesani, Giacomo and Rychlicki, Mateusz and Szeider, Stefan}, year={2024}, month={Mar.}, pages={10662-10669} }