IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules

By Bishwamittra Ghosh, Kuldeep S. Meel. 2019

37 citations recorded by the source corpus.

The wide adoption of machine learning in the critical domains such as medical diagnosis, law, education had propelled the need for interpretable techniques due to the need for end users to understand the reasoning behind decisions due to learning systems. The computational intractability of interpretable learning led practitioners to design heuristic techniques, which fail to provide sound handles to tradeoff accuracy and interpretability. Motivated by the success of MaxSAT solvers over the past decade, recently MaxSAT-based approach, called MLIC, was proposed that seeks to reduce the problem of learning interpretable rules expressed in Conjunctive Normal Form (CNF) to a MaxSAT query. While MLIC was shown to achieve accuracy similar to that of other state of the art black-box classifiers while generating small interpretable CNF formulas, the runtime performance of MLIC is significantly lagging and renders approach unusable in practice. In this context, authors raised the question: Is it possible to achieve the best of both worlds, i.e., a sound framework for interpretable learning that can take advantage of MaxSAT solvers while scaling to real-world instances? In this paper, we take a step towards answering the above question in affirmation. We propose IMLI: an incremental approach to MaxSAT based framework that achieves scalable runtime performance via partition-based training methodology. Extensive experiments on benchmarks arising from UCI repository demonstrate that IMLI achieves up to three orders of magnitude runtime improvement without loss of accuracy and interpretability.

Subfields: Artificial Intelligence, Safety, Robustness & Interpretability, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Safety, Robustness & Interpretability

In Mathematical Optimization

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, neutral): “…2016; Yu et al., 2020a; Angelino et al., 2017, 2018; Aı̈vodji et al., 2019) and decision sets (Wang and Rudin, 2015b; Lakkaraju et al., 2016; Ignatiev et al., 2018; Dash et al., 2018b; Malioutov and Meel, 2018; Ghosh and Meel, 2019; Dhamnani et al., 2019; Yu et al., 2020b; Cao et al., 2020).”
Computing Optimal Decision Sets with SAT (2020, methodology): “All in all, the proposed approach to sparse decision sets embodies a viable alternative to the state of the art represented by prior logic-based solutions [20,31,39] as well as by efficient heuristic methods [11–13].”