\subsection{Related Work}
\label{relatedwork}

In this section we discuss relevant related work. In particular, we devote special attention to previous attempts for building interpretable classifiers. Decision lists, for instance, are models largely used in expert systems \cite{expert}.
The knowledge base of an expert system is composed
of simple statements of the  ``if$-$then'' form.
Decision lists are a particular case of associative classifier, meaning that the list is formed
from decision rules. In the past, associative classifiers have been
built from heuristic mechanisms \cite{lists,cba,cmar,cpar,marchand}.
Some of these sorting mechanisms provably work well in special cases, for instance
when the decision problem is easy and the classes are easy to separate~\cite{book}.
Sometimes associative
classifiers are formed by averaging several rules together~\cite{lac}, but the the resulting
classifier is still interpretable.
Interpretability
is closely related to the concept of explanation; an interpretable predictive
model ought to be able to
explain
its predictions. A small literature has
explored the concept of explanation in statistical modeling~\cite{madigan}.

Decision lists are a simple type of
decision tree. However decision trees can be much harder to construct
than decision lists, because the space of possible decision trees is much larger
than the space of possible decision lists (designed from the computed
rules). Because the space of possible decision trees is so large, they are
usually constructed greedily, and then pruned heuristically.
For instance, CART~\cite{trees}
and C4.5 trees~\cite{quinlan}
are constructed this way. Because the trees are not fully
optimized, if the top of the decision tree happened to have been chosen badly
at the start of the procedure, it could cause problems with both accuracy
and interpretability. Bayesian Decision Trees \cite{btm}
are also constructed in
an approximate way, where the sampling procedure repeatedly restarts when
the samples start to concentrate around a posterior mode, which is claimed
to happen quickly. This means that the tree that is actually found is a local
posterior maximum.

Our work is also related to the
Hierarchical Association Rule Model
(HARM)
presented recently by \cite{harm}.
HARM is a Bayesian model that uses
rules and
estimates the conditional probabilities of each rule in a conservative
way, and does not explicitly aim to learn the
ordering
of rules.
HARM's estimates of conditional probability are based on the principle of the adjusted confidence~\cite{rudin},
where rules that do not appear often
enough in the training-set may not considered to be trustworthy enough to make
accurate predictions. HARM is a Bayesian model for these conditional probabilities, and it makes predictions by ranking rules by the posterior means of
the (conditional) probabilities.
Our work is also related to~\cite{rudin2}, which produce predictive models that are not only accurate, but are also
interpretable to human experts.

Finally, our work differs from all aforementioned works in the sense that we propose novel strategies to decrease the number of rules that compose the model. We introduce a rule filtering approach based on the concept of Pareto Efficiency, which enables us to reduce the complexity of the classifier, improving interpretability without compromising accuracy. Therefore, our proposed strategy differs from the strategies proposed in~\cite{salvatore,krimp} in the sense that it focus on learning classifiers and not on explaining the dataset. Also, our proposed strategy differs from the strategy proposed in~\cite{fidelis} in the sense that we are interested on exploiting the trade-off between the complexity of the classifier and its accuracy, being in accordance with the Occam's Razor principle. The strategy proposed in~\cite{fidelis}, on the other hand, employs only one rule per class (i.e., the smallest possible classifier), and clearly this is not guaranteed to be the best number of rules, since a classifier composed of more rules could be more accurate.
