  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.
