Efficient Learning of Interpretable Classification Rules
Machine learning has become omnipresent with applications in various
safety-critical domains such as medical, law, and transportation. In these
domains, high-stake decisions provided by machine learning necessitate
researchers to design interpretable models, where the prediction is
understandable to a human. In interpretable machine learning, rule-based
classifiers are particularly effective in representing the decision boundary
through a set of rules comprising input features. The interpretability of
rule-based classifiers is in general related to the size of the rules, where
smaller rules are considered more interpretable. To learn such a classifier,
the brute-force direct approach is to consider an optimization problem that
tries to learn the smallest classification rule that has close to maximum
accuracy. This optimization problem is computationally intractable due to its
combinatorial nature and thus, the problem is not scalable in large datasets.
To this end, in this paper we study the triangular relationship among the
accuracy, interpretability, and scalability of learning rule-based classifiers.
  The contribution of this paper is an interpretable learning framework IMLI,
that is based on maximum satisfiability (MaxSAT) for synthesizing
classification rules expressible in proposition logic. Despite the progress of
MaxSAT solving in the last decade, the straightforward MaxSAT-based solution
cannot scale. Therefore, we incorporate an efficient incremental learning
technique inside the MaxSAT formulation by integrating mini-batch learning and
iterative rule-learning. In our experiments, IMLI achieves the best balance
among prediction accuracy, interpretability, and scalability. As an
application, we deploy IMLI in learning popular interpretable classifiers such
as decision lists and decision sets.