\section{Learning Interpretable Classifiers with Pareto-Efficient Rules}
\label{chapter.metodologia}

In the discussion that follows throughout this section, we will assume that the classification algorithm\footnote{We will call this algorithm as LAC (Lazy Associative Classification).} used to learn associative classifiers adopts the demand-driven rule extraction strategy described in Section 2.2. This strategy dynamically extends the classifier $\mathcal{R}$ as test instances are informed. More specifically, a classifier $\mathcal{R}_x$ is built for each test instance $x$. We notice that not all rules in $\mathcal{R}_x$ are beneficial to classification, since some of them predicts the wrong class. That is, $\mathcal{R}_x$ is a sub-optimal rule-set in the sense that it may exist other rule-sets that lead to more accurate predictions.
%However, as pointed out in \cite{Wilkins1994}, finding the optimal subset of rules (i.e., the best classifier for each test instance) is a NP-hard problem. Therefore, we must rely on heuristics in order to approximate the optimal rule-set for each test instance.

\subsection{Trading Complexity for Interpretability}

Our basic assumption in this paper is that the choice to use a small classifier leads to more interpretable predictive models in many cases.
Thus, the heuristic solution we propose to approximate optimal classifiers trades the complexity of the classifier for its interpretability. Precisely, we want to find the (approximately) smallest rule-set $\mathcal{R}^{*}$, which is as accurate as the original rule-set $\mathcal{R}$. We decompose this problem into several simpler sub-problems, that is, we want to find the smallest $\mathcal{R}^{*}_x$ that is as accurate as $\mathcal{R}_x$, for each test instance $x$.

\subsection{Optimal Multi-Criteria Rules (or Pareto-Optimal Rules)}
\label{metodologia.filtro.pareto}

There are several smart heuristics that can be used to solve the problem stated above. However, we are also concerned with the time spent to find $\mathcal{R}^*=\{\mathcal{R}^{*}_{x_1}\cup\mathcal{R}^{*}_{x_2}\cup\ldots\cup\mathcal{R}^{*}_{x_k}\}$. Therefore, in addition of being
effective the heuristic solution
must also be fast.
Thus, we propose to evaluate each rule based on multiple criteria or rule statistics\footnote{We decided to employ these statistics because they complement each other in terms of the properties they express (recall Table~\ref{table.intro.metrics.properties}).}, namely: confidence, support, added-value, and Yules'Q. Given that the original associative classification algorithm (i.e., LAC) already computes at least one of such statistics, the cost of computing additional rule statistics is negligible, since no additional data accesses are necessary.
Our intuition is that rules that excel in terms of at least one criterion,
are more valuable in the sense that it carries more utility than rules that do not excel in any criterion.
\begin{wrapfigure}[15]{r}{7cm}
  \centering
  \epsfig{file=./img/support2dEN.eps,width=0.45\textwidth}
  \caption{$\mathcal{R}_x$ and $\mathcal{R}^{*}_x$. Each point corresponds to a rule in $\mathcal{R}_x$. Optimal rules are highlighted.}
  \label{fig.example.pareto}
\end{wrapfigure}
The Pareto Efficiency is a natural way to exploit such intuition $-$ rules lying in the Pareto frontier are the most valuable ones, since by definition, no other rule excels as much as those rules in the frontier. We denote the rules lying in the Pareto frontier as optimal multi-criteria rules, and given a test instance $x$, the corresponding classifier $\mathcal{R}^{*}_x$ is composed of those rules lying in the Pareto frontier.

Figure~\ref{fig.example.pareto} illustrates this intuition with data obtained from a real example. Each point in the figure corresponds to a rule in $\mathcal{R}_x$. It is not evident from the figure if rules pointing to the blue class are better than rules pointing to the red class. However, if we consider only rules lying in the Pareto frontier, it becomes clear that rules pointing to the blue class (which is indeed the correct class) are the ones that excel most.
Furthermore, while $|\mathcal{R}_x|=210$, there are only 8 rules in $\mathcal{R}^{*}_x$, corresponding to a decrease of 96\% in terms of model size.

\subsection{Employing Additional Frontiers}

In some cases, the Pareto frontier is composed of very few rules. As a consequence, the classifier $\mathcal{R}^{*}_x$ may be over-simplified and it may be dangerous to perform predictions since rules in $\mathcal{R}^{*}_x$ may be due to noise. Our approach to overcome this problem is to use additional Pareto frontiers. That is, instead of using only the first frontier, we may also exploit subsequent frontiers. This will obviously increase the size of the classifier, since more rules will be included into $\mathcal{R}^{*}_x$, reducing the impact of noisy rules. Algorithm~\ref{alg.lacp}, which we call PE-LAC (Pareto-Efficient Lazy Associative Classification), shows detailed steps of the entire process of learning interpretable classifiers using Pareto-Efficient rules.

\begin{algorithm}
  \caption{\textbf{PE-LAC} Pareto Efficient Lazy Associative Classification}
  \label{alg.lacp}
  \begin{algorithmic}[1]
    \Require{Training-set $\mathcal{D}$, test instance $x$,
      statistics $\theta$ to be used in Equation~\ref{eq1},
      number of frontiers $\eta$}
    \Statex

	\State $\mathcal{R}_{x} \gets $ \textbf{\textit{induceRules}}$(x, \mathcal{D})$
	\State  $F_{x} \gets \emptyset$
	\For{$i=1$ \textbf{to} $\eta$ }
	  \State $F_{x} \gets  F_{x}$~$\cup$ \textbf{\textit{paretoFrontier}}($\mathcal{R}_{x} - F_{x}$)
	  \Comment apply BNL
	\EndFor
%	\State $minValue \gets \displaystyle \min_{r ~ \in ~ RF^{x_i}}(\mathcal{M}(r))$
%	\Comment menor valor das regras
%	\State $shift \gets -\min(0, minValue)$ 
%	\Comment evitar valores positivos
%	 \ForAll{class $y_i \in \mathcal{Y}$}
%	    \State $s(x, y_i) \gets | F_{x}^{y_i} | * shift +  \displaystyle \sum_{r ~ \in ~RF_{x_i}^{c_j} } \mathcal{M}(r) $
%	 \EndFor
	 \ForAll{class $y_i \in \mathcal{Y}$}
	\Comment notice that $\mathcal{Y}$ is the set of all class labels 
            \State $s(x,y_i) \gets \displaystyle\sum_{r\in F^{y_i}_x} \theta(r)$ 
% 	\Comment notice that $r\in F^{y_i}_x$
	 \EndFor
	 \ForAll{class $y_i \in \mathcal{Y}$}
	    \State $\hat{p}(y_i|x) \gets \frac{ s(x, y_i) }{ \displaystyle \sum_{k=1}^{|\mathcal{Y}|} s(x, y_k)} $ 
	 \EndFor
	  
	  \State \textbf{\textit{predict}} $y_i\in\mathcal{Y}: argmax(~\hat{p}(y_i|x)~)  \}$

     
  \end{algorithmic}
  
\end{algorithm}


\subsection{Computational Complexity}

The computational complexity of the original associative classification algorithm, LAC, is given as:

\begin{equation}
\label{lac}
\nonumber
O(|\mathcal{D}|\times|\mathcal{Y}|\times\displaystyle \sum_{k=1}^{l} \binom{|x|}{k})
\end{equation}

\noindent where $x$ is a test instance, $\mathcal{Y}=\{y_1, y_2, \ldots, y_m\}$ is the set of possible class labels, and $l$ is the maximum cardinality allowed for the rules (which is bounded by the cardinality of the test instance, that is $|x|$).
As shown in Section \ref{referencial.pareto}, the BNL algorithm we use to find the Pareto frontier has linear complexity in the best- and average-cases.
Thus, in such cases, the complexity of PE-LAC is given as:

\vspace{-0.5cm}
\begin{equation}
\label{pelac1}
\nonumber
O(|\mathcal{D}|\times|\mathcal{Y}|\times\eta\times\displaystyle \sum_{k=1}^{l} \binom{|x|}{k})
\end{equation}

However, since $\eta$ is a small constant, we conclude that PE-LAC has essentially the same complexity as LAC. In the worst-case scenario, the BNL algorithm is quadratic, and thus the complexity of PE-LAC becomes:

\vspace{-0.5cm}
\begin{equation}
\label{pelac1}
\nonumber
O(|\mathcal{D}|\times|\mathcal{Y}|\times\eta\times(\displaystyle \sum_{k=1}^{l} \binom{|x|}{k})^2)
\end{equation}
