• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
MLIC: A MaxSAT-Based framework for learning interpretable classification rules .
Malioutov,Dmitry, and Kuldeep S. Meel.
In Proceedings of International Conference on Constraint Programming (CP), August 2018.
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.
@inproceedings{MM18,
title={
MLIC: A MaxSAT-Based framework for learning interpretable classification
rules
},
author={Malioutov,Dmitry and Meel, Kuldeep S.},
booktitle=CP,
month=aug,
year={2018},
bib2html_rescat={Formal Methods 4 ML},
code={https://github.com/meelgroup/MLIC},
bib2html_dl_pdf={../Papers/cp2018mm.pdf},
bib2html_pubtype={Refereed Conference},
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.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Thu Apr 30, 2026 09:22:03