Personalized Interpretable Classification

To date, there is still no consensus on a precise definition of interpretability [16]. In practice, simplicity, predictivity and stability are generally regarded as basic requirements for interpretable models [17]. In the context of rule-based classification models, the simplicity of model structure can be evaluated based on the number of rules, the length of each rule and the overlap among rules. The predictivity corresponds to the classification accuracy, which has been one of the long-term goals for any classifier. The stability refers to the model robustness with respect to small data perturbations [17].

To identify classification rules, heuristic sequential covering method and divide-and-conquer strategy are typically employed by early algorithms [7, 8]. However, simply being rule-based cannot fully guarantee the interpretability [6] and the final rule set is not explicitly optimized with respect to the interpretability. That is, these classical rule-based classifiers mainly focus on maximizing the classification accuracy, ignoring other interpretability measures such as simplicity and stability.

Recently, with the renewed interest on rule-based interpretable classification models, people begin to construct classifiers that explicitly optimize both accuracy and simplicity. These algorithms can be roughly divided into two categories. The classification algorithms in the first category [1, 2, 6, 18, 19] typically adopt a two-stage pipeline: rule generation and rule selection. In rule generation, an association rule mining algorithm such as FP-Growth is first employed to produce a set of candidate rules. In rule selection, a small and compact subset of rules are selected via either heuristic algorithms or the solution to a new optimization problem. Alternatively, some algorithms extract interpretable rules from random forests [17, 20]. The classification algorithms in the second category [3, 4, 21, 22, 23, 24, 25, 26] directly learn rules from the data by formulating the rule set discovery issue as different types of optimization problems.

Despite of their seeming difference with respect to problem formulation and rule discovery algorithms, all existing rule-based interpretable classification models follow an inductive learning paradigm. That is, these classifiers conduct rule learning only on the training data, which are unable to provide a potentially customized rule for each individual test sample.

In addition to the training data, the transductive learning approach employs information from the testing data as well [27]. In the context of classification, a personalized transductive classification model creates a unique model for each test sample adaptively [13]. Hence, such a learning paradigm naturally fits the applications where the focus is on the prediction and illustration for each individual sample.

The most representative personalized transductive classification algorithm is the k nearest neighbor (kNN) classifier [28], in which the prediction model is dynamically constructed based on samples within the kNN neighborhood. Recently, the support vector machine (SVM) is customized to generate various personalized models and these models are applied to tackle various biomedical data analysis tasks [13, 14, 15].

Either the lazy learning approach such as kNN or the personalized SVM cannot provide an explicit explanation on the classification decision. Hence, a personalized yet interpretable classification model is still lacking in the literature.

How to interpret a black-box machine model has been widely investigated recently [29, 30]. There are two closely related problems towards this direction: the interpretation of a learned model and the interpretation of an individual prediction. For existing solutions on the former issue, please refer to a recent review in [29]. Here we only focus on the latter issue since our algorithm also seeks to provide an explanation on the prediction for each test sample.

To date, many effective algorithms have been proposed to learn an interpretation for each individual prediction of any classifier (e.g. [10, 11, 12]). Despite of their great successes, we have the following remarks.

First of all, these methods provide an explanation after the model selection procedure. That is, they did not construct an interpretable model for each test sample during the model selection phase in an adaptive manner. As a result, we may fail to find a more appropriate interpretation due to the separation of model construction and interpretation. Moreover, these methods generally cannot provide explanations in terms of rules. For example, the model to be explained is approximated with a linear model in a local region around the test sample in [10]. And the feature importance scores derived from the weights of the linear model are employed to explain the corresponding prediction.

Let $D=\left\{(x_{i},y_{i})|i=1,...,N\right\}$ denote the training set of $N$ samples, where $x_{i}$ comprises $M$ categorical feature values and $y_{i}\in Y$ is a class label. We use $f_{j}$ to denote the $j$th feature and a predicate takes the form of $f_{j}=x_{ij}$, where $x_{ij}$ is one of the possible feature values for the $j$th feature. An itemset $s$ is defined as a conjunction of $k$ $(1\leqslant k\leqslant M)$ predicates. For a given sample $(x_{i},y_{i})$, it satisfies an itemset $s$ only if all predicates in $s$ are true in the sample. We use $s\subseteq x_{i}$ to denote the fact that $x_{i}$ satisfies $s$. A rule $r$ is a tuple $(s,y)$ where $s$ is an itemset and $y$ is a class label.

For each test sample $(x,?)$ in which the class label is unknown, we try to find a “best” rule $\hat{r}=(\hat{s},\hat{y})$ such that $x$ satisfies $\hat{s}$, and then $\hat{y}$ is the label we predict. Hence, the personalized interpretable classification problem can be cast as the following algorithmic issue:

• •

  Input: A training dataset $D$, a test sample $x$.

• •

  Output: The “best” rule $\hat{r}=(\hat{s},\hat{y})$ that matches $x$.

To illustrate above concepts, the dataset in Table I is taken as an example. In Table I, rows stand for samples and columns represent their class label and features. There are 7 training samples in which 3 samples are drawn from class 1 and another 4 samples are obtained from class 2. We take the sample in the last line as a test sample. Assume that we find a “best” rule $\hat{r}=(f_{1}=a_{1}\land f_{3}=c_{2},2)$. Obviously, the test sample satisfies this rule and it will be classified to class $2$.

Since our algorithm can only handle categorical features, we adopt a pre-processing procedure to discretize numeric features into categorical ones. More precisely, we employ the equal width discretization method to split the $j$th numeric feature values into $g_{j}$ groups, where $g_{j}$ is a user-specified parameter.

Obviously, the “best” rule we find should satisfy the test sample. Apart from this necessary condition, we evaluate each candidate rule by its accuracy and simplicity. For accuracy, we use a linear combination of precision and recall. For simplicity, since we only choose one rule so that the number of rules and the overlap among rules make no sense in our problem. Therefore, the length of a rule is the only indicator for simplicity and shorter rules are preferred than longer ones.

For a rule $r=(s,y)$, its length $length(r)$ is defined as the number of predicates in $s$. The precision is defined as the ratio between the number of samples satisfying $s$ in class $y$ and the number of all samples satisfying $s$. The recall is the ratio between the number of samples satisfying $s$ in class $y$ and the number of all samples in class $y$.

To make a trade-off between precision and recall, we use the linear combination of precision and recall:

where $\alpha$ is a user-specified parameter. Then, our two objectives can be summarized as follows:

• •

  For simplicity: minimize $length(\hat{r})$.

• •

  For accuracy: maximize $A(\hat{r},D)$.

For example, suppose that there are two rules $r_{1}=(f_{1}=a_{1}\land f_{3}=c_{2},2)$ and $r_{2}=(f_{2}=b_{3}\land f_{3}=c_{2},1)$. In the training samples in Table I, two samples from class 2 satisfy $f_{1}=a_{1}\land f_{3}=c_{2}$ and one sample from class 1 satisfies $f_{2}=b_{3}\land f_{3}=c_{2}$. The precision of $r_{1}$ is the ratio between the number of samples satisfying $r_{1}$ in class 2 and the number of all samples satisfying $r_{1}$, which is $2\div 2=1$. The recall of $r_{1}$ in class 2 is calculated as the ratio between the number of samples satisfying $r_{1}$ in class 2 and the number of all samples in class 2, which is $2\div 4=0.5$. The precision and recall of $r_{2}$ can be calculated in the same way, whose values are $1$ and $0.333$. If we set $\alpha=0.5$, then $A(r_{1},D)$ is $0.75$ and $A(r_{2},D)$ is $0.667$. Hence, $r_{1}$ is better than $r_{2}$ because it has a higher accuracy score and both rules have the same length of 2.

To date, there is still no universally recognized precise definition of interpretability. In our case, we try to measure the performance of each algorithm in terms of interpretability via the length of rule, the number of total rules and the comparison between the distinct “personalized” rules and the common rules.

Table VIII shows the average length of rules reported by four methods. For the PIC algorithm, we calculate the average length of all the rules found in a 5-fold cross-validation. In comparison, we use the average length of the 5 rule sets reported by the other methods. The rules reported by DR-Net are longer than the ones reported by other methods on most of the datasets except transfusion. DR-Net does not find any rules on the transfusion data set. In contrast, the rules found by our PIC algorithm are shorter and their lengths are all less than $4$. The rules found when $\alpha=0.7$ are shorter than those found when $\alpha=0.9$.

Table IX shows the average number of rules reported by four methods. The PIC algorithm can find more rules than any other algorithms on COMPAS, heloc, magic and transfusion, which means that our method is more likely to find more “personalized” rules for distinct samples. Fig 2 shows the distribution of the rules reported by PIC on mushroom in a 5-fold cross-validation when $\alpha=0.9$. PIC reports 23 rules, 8 of them are from class 0 and 15 of them are from class 1. We can find that there are 2 rules, ({ring-number=o} {gill-size=b} {odor=n} $\rightarrow$ 0) and ({gill-spacing=c} {stalk-surface-above-ring=k} $\rightarrow$ 1), which appear more times than others. And the other rules only appear less than 1000 times in the experiment.

We consider a rule $r_{1}=(s_{1},y_{1})$ reported by PIC is a common rule when there is a rule $r_{2}=(s_{2},y_{2})$ reported by other methods that satisfies $s_{1}\subseteq s_{2}\land y_{1}=y_{2}$. Table X shows the common rules found on mushroom by PIC and other methods and the “personalized” rules only reported by PIC when $\alpha$ is set to 0.9. We find 4 “personalized” rules in this experiment, 2 for class 0 and 2 for class 1. Their frequency values are all in the range of 10 to 1000, so they do not appear by accident. This fact demonstrates that the PIC algorithm really can find some “personalized” rules which cannot be discovered by other methods.