MLIC: A MaxSAT-Based framework for learning interpretable classification rules

Abstract

The wide adoption of machine learning approaches in the industry, government, medicine and science has renewed the interest in interpretable machine learning: many decisions are too important to be delegated to black-box techniques such as deep neural networks or kernel SVMs. Historically, problems of learning interpretable classifiers, including classification rules or decision trees, have been approached by greedy heuristic methods as essentially all the exact optimization formulations are NP-hard. Our primary contribution is a MaxSAT-based framework, called MLIC, which allows principled search for interpretable classification rules expressible in propositional logic. Our approach benefits from the revolutionary advances in the constraint satisfaction community to solve large-scale instances of such problems. In experimental evaluations over a collection of benchmarks arising from practical scenarios, we demonstrate its effectiveness: we show that the formulation can solve large classification problems with tens or hundreds of thousands of examples and thousands of features, and to provide a tunable balance of accuracy vs. interpretability. Furthermore, we show that in many problems interpretability can be obtained at only a minor cost in accuracy. The primary objective of the paper is to show that recent advances in the MaxSAT literature make it realistic to find optimal (or very high quality near-optimal) solutions to large-scale classification problems. The key goal of the paper is to excite researchers in both interpretable classification and in the CP community to take it further and propose richer formulations, and to develop bespoke solvers attuned to the problem of interpretable ML.

Paper published in Proceedings of International Conference on Constraint Programming (CP), 2018

References in corpus (2)

• Predictive learning via rule ensembles
• Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems

Cited by in corpus (9)

• IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules
• Advances in Machine Learning for the Behavioral Sciences
• Explainable AI using expressive Boolean formulas
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Efficient Learning of Interpretable Classification Rules
• Neural-Symbolic Descriptive Action Model from Images: The Search for STRIPS
• Computing Optimal Decision Sets with SAT
• Certifying Pareto-Optimality in Multi-Objective Maximum Satisfiability
• An Incremental MaxSAT-based Model to Learn Interpretable and Balanced Classification Rules