Rule Extraction with Guaranteed Fidelity

Ulf Johansson, Rikard König, Henrik Linusson, Tuve Löfström, Henrik Boström

► To cite this version:

Ulf Johansson, Rikard König, Henrik Linusson, Tuve Löfström, Henrik Boström. Rule Extraction with Guaranteed Fidelity. 10th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2014, Rhodes, Greece. pp.281-290, 10.1007/978-3-662-44722-2_30. hal-01391055

HAL Id: hal-01391055

https://inria.hal.science/hal-01391055

Submitted on 2 Nov 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Rule Extraction with Guaranteed Fidelity

Ulf Johansson¹*, Rikard König¹, Henrik Linusson¹, Tuve Löfström¹, and Henrik Boström²

¹ School of Business and IT
University of Borås, Sweden

{ulf.johansson, rikard.konig, henrik.linusson, tuve.lofstrom}@hb.se

² Department of Systems and Computer Sciences
Stockholm University, Sweden
henrik.bostrom@dsv.su.se

**Abstract.** This paper extends the conformal prediction framework to rule extraction, making it possible to extract interpretable models from opaque models in a setting where either the infidelity or the error rate is bounded by a predefined significance level. Experimental results on 27 publicly available data sets show that all three setups evaluated produced valid and rather efficient conformal predictors. The implication is that augmenting rule extraction with conformal prediction allows extraction of models where test set errors or test sets infidelities are guaranteed to be lower than a chosen acceptable level. Clearly this is beneficial for both typical rule extraction scenarios, i.e., either when the purpose is to explain an existing opaque model, or when it is to build a predictive model that must be interpretable.

**Keywords:** Rule extraction, Conformal prediction, Decision trees

## 1 Introduction

When predictive models must be interpretable, most data miners will use decision trees like C4.5/C5.0 [1]. Unfortunately, decision trees are much weaker in terms of predictive performance than opaque models like support vector machines, neural networks and ensembles. Opaque predictive models, on the other hand, make it impossible to assess the model, or even to understand the reasoning behind individual predictions. This dilemma is often referred to as the *accuracy vs. comprehensibility trade-off*.

One way of reducing this trade-off is to apply *rule extraction*, which is the process of generating a transparent model based on a corresponding opaque predictive model. Naturally, extracted models must be as good approximations as possible of the opaque models. This criterion, called *fidelity*, is therefore a key part of the optimization function in most rule extracting algorithms. For classification, the *infidelity rate* is the proportion of test instances where the

<footnote>* This work was supported by the Swedish Foundation for Strategic Research through the project High-Performance Data Mining for Drug Effect Detection (IIS11-0053) and the Knowledge Foundation through the project Big Data Analytics by Online Ensemble Learning (20120192).</footnote>
extracted model outputs a different label than the opaque model. Similarly, the
fidelity is the proportion of test instances where the two models agree. Unfor-
tunately, when *black-box* rule extraction is used, i.e., when the rule extractor
utilizes input-output patterns consisting of the original input vector and the
corresponding prediction from the opaque model to learn the relationship repre-
sented by the opaque model, the result is often a too specific or too general model
resulting in low fidelity on the test set, that is, the extracted model is actually a
poor approximation of the opaque. Consequently, decision makers would like to
have some guarantee *before* applying the extracted model to the test instances
that the predictions will actually mimic the opaque.

In conformal prediction [2], prediction sets with a bounded error are pro-
duced, i.e., for classification, the probability of excluding the correct class label
is guaranteed to be less than the predetermined significance level. The prediction
sets can contain one, multiple or even zero class labels, so the price paid for the
guaranteed error rate is that not all predictions are informative. In, inductive
conformal prediction (ICP) [2], just one model is induced from the training data,
and then used for predicting all test instances, but a separate data set (called
the *calibration set*) must be used for calculating *conformity scores*.

The conformal prediction framework has been applied to several popular
learning schemes, such as ANNs [3], kNN [4] and SVMs [5]. Until now, however,
the guarantee provided by conformal prediction has always been related to the
error rate. In this paper, we extend the conformal prediction framework to rule
extraction, specifically introducing the possibility to bound the infidelity rate by
a preset significance level.

## 2 Background

Rule extraction has been heavily investigated for ANNs, and the techniques have
been applied mainly to ANN models; for an introduction and a good survey of
traditional methods, see [6]. For ANN rule extraction, there are two fundamen-
tally different extraction strategies, *decompositional* (*open-box* or *white-box*) and *pedagogical* (*black-box*). Decompositional approaches focus on extracting rules at
the level of individual units within a trained ANN. Typically, the output of each
hidden and output unit is first modeled as a consequent of their inputs, before
the rules extracted at the individual unit level are aggregated to form the com-
posite rule set for the ANN. Two classic open-box algorithms are RX [7] and
Subset [8].

The core pedagogical idea is to view rule extraction as a learning task, where
the target concept is the function originally learned by the opaque model. Black-
box rule extraction is therefore an instance of predictive modeling, where each
input-output pattern consists of the original input vector $x_i$ and the correspond-
ing prediction $f(x_i; \theta)$ from the opaque model. One typical and well-known black-
box algorithm is TREPAN [9].

It must be noted that black-box rule extraction algorithms can be applied to
any opaque model, including ensembles, and it can use any learning algorithm
producing interpretable models as the actual rule extractor. An inherent problem for open-box methods, regarding both running time and comprehensibility, is the scalability. The potential size of a rule for a unit with *n* inputs each having *k* possible values is *k*ⁿ, meaning that a straightforward search for possible rules is normally impossible for larger networks. Consequently, most modern rule extraction algorithms are black-box, see the more recent survey [10].

There is, however, one very important problem associated with black-box rule extraction. Even if the algorithm aims for maximizing fidelity in the learning phase, there is no guarantee that the extracted model will actually be faithful to the opaque model when applied to test set instances. Instead, since black-box rule extraction is just a special case of predictive modeling, the extracted models may very well overfit or underfit the training data, leading to poor fidelity on test data. The potentially low test set fidelity for black-box techniques stands in sharp contrast to open-box methods where the rules, at least in theory, should have perfect fidelity, even on the test set. Consequently, in situations where a very high fidelity is needed, open-box methods may be necessary; see e.g., [11]. Ideally though, we would like to have the best of both worlds, i.e., providing the efficiency and the freedom to use any type of opaque model present in black-box rule extractors, while guaranteeing test set fidelity. Again, the purpose of this paper is to show how the conformal prediction framework can be employed for achieving this.

An interesting discussion about the purpose of rule extraction is found in [12], where Zhou argues that rule extraction really should be seen as two very different tasks; rule extraction for neural networks and rule extraction using neural networks<fnref n="1" />. While the first task is solely aimed at understanding the inner workings of an opaque model, the second task is explicitly aimed at extracting a comprehensible model with higher accuracy than a comprehensible model created directly from the data set. More specifically, in rule extraction for opaque models, the purpose is most often to explain the reasoning behind individual predictions from an opaque model, i.e., the actual predictions are still made by the opaque model. In that situation, test set fidelity must be regarded as the most important criterion, since we use the extracted model to understand the opaque. In rule extraction using opaque models, the predictions are made by the extracted model, so it is used both as the predictive model and as a tool for understanding and analysis of the underlying relationship. In that situation, predictive performance is what matters, so the data miner must have reasons to believe that the extracted model will be more accurate than other comprehensible models induced directly from the data. The motivation for that rule extraction using opaque models may work is that even a highly accurate opaque model is a smoothed representation of the underlying relationship. In fact, training instances misclassified by the opaque model are often atypical, i.e., learning such instances will reduce the generalization capability. Consequently, rule ex-

<footnote n="1">¹ Naturally this distinction is as relevant for rule extraction from any opaque model, not just from ANNs, so we use the terms rule extraction for or using *opaque models* instead.</footnote>
traction is most often less prone to overfitting than standard induction, resulting in smaller and more general models.

## 2.1 Conformal prediction

A key component in ICP is the conformity function, which produces a score for each instance-label pair. When classifying a test instance, scores are calculated for all possible class labels, and these scores are compared to scores obtained from a calibration set consisting of instances with known labels. Each class is assigned a probability that it does conform to the calibration set based on the fraction of calibration instances with a higher conformity score. For each test instance, the conformal predictor outputs a set of predictions with all class labels having a probability higher than some predetermined significance level. This prediction set may contain one, several, or even no class labels. Under very general assumptions, it can be guaranteed that the probability of excluding the true class label is bounded by the chosen significance level, independently of the conformity function used, for more details see [2].

In ICP, the conformity function $A$ is normally defined relative to a trained model $M$:

$$A(\langle \bar{x}, c \rangle) = F(c, M(\bar{x})) \quad (1)$$

where $\bar{x}$ is a vector of feature values (representing the example to be classified), $c$ is a class label, $M(\bar{x})$ returns the class probability distribution predicted by the model, and the function $F$ returns a score calculated from the chosen class label and predicted class distribution.

Using a conformity function, a p-value for an example $\bar{x}$ and a class label $c$ is calculated in the following way:

$$p_{\langle \bar{x}, c \rangle} = \frac{|\{s : s \in S \wedge A(s) \leq A(\langle \bar{x}, c \rangle)\}|}{|S|} \quad (2)$$

where $S$ is the calibration set. The prediction for an example $\bar{x}$, where $\{c_1, \dots, c_n\}$ are the possible class labels, is:

$$P(\bar{x}, \sigma) = \{c : c \in \{c_1, \dots, c_n\} \wedge p_{\langle \bar{x}, c \rangle} > \sigma\} \quad (3)$$

where $\sigma$ is a chosen significance level, e.g., 0.05.

## 3 Method

The purpose of this study is to extend the conformal prediction framework to rule extraction, and show how it can be used for both rule extraction for opaque models and rule extraction using opaque models. Since standard ICP is used, the difference between the scenarios is just how the calibration set is used. For the final modeling, all setups use J48 trees from the Weka workbench [13]. Here J48, which is the Weka implementation of C4.5, uses default settings, but pruning was turned off and Laplace smoothing was used for calculating the probability estimates. The three different setups evaluated are described below:
- **J48**: J48 trees built directly from the data. When used as a conformal predictor, the calibration set uses the true targets, i.e., the guarantee is that the error rate is bounded by the significance level.

- **RE-a**: Rule extraction using opaque models. Here, an opaque model is first trained, and then a J48 tree is built using original training data inputs, but with the predictions from the opaque model as targets. For the conformal prediction, the calibration set uses the true targets, so the guarantee is again that the error rate is bounded by the significance level.

- **RE-f**: Rule extraction for opaque models. The J48 model is trained identically to RE-a, but now the conformal predictor uses predictions from the opaque model as targets for the calibration. Consequently, the guarantee is that the infidelity rate will be lower than the significance level.

In the experimentation, bagged ensembles of 15 RBF networks were used as opaque models. With guaranteed validity, the most important criterion for comparing conformal predictors is *efficiency*. Since high efficiency roughly corresponds to a large number of singleton predictions, *OneC*, i.e., the proportion of predictions that include just one single class, is a natural choice. Similarly, *MultiC* and *ZeroC* are the proportions of predictions consisting of more than one class, and empty predictions, respectively. One way of aggregating these number is *AvgC*, which is the average number of classes in the predictions.

In this study, the well-known concept of *margin* was used as the conformity function. For an instance *i* with the true class *Y*, the higher the probability estimate for class *Y* the more conforming the instance, and the higher the other estimates the less conforming the instance. For the evaluation, 4-fold cross-validation is used. The training data was split 2:1; i.e., 50% of the available instances were used for training and 25% were used for calibration. The 27 data sets used are all publicly available from either the UCI repository [14] or the PROMISE Software Engineering Repository [15].

# 4 Results

Table 1 below shows the accuracy, AUC and size (total number of nodes) for the J48 models produced using either standard induction or rule extraction. As described in the introduction, the rule extraction is supposed to increase model accuracy, produce smaller models, or both. Comparing mean values and wins/ties/losses, the results show that the use of rule extraction actually produced models with higher accuracy. A standard sign test requires 19 wins for significance when $\alpha = 0.05$, so the difference is statistically significant at that level. Looking at models sizes, the extracted models are also significantly less complex. When comparing the ranking ability, however, the larger induced tree models obtained higher AUCs, on a majority of the data sets.
<table><caption>**Table 1.** Accuracy, AUC and Size</caption><thead><tr><th rowspan="2">Data set</th><th colspan="2">Accuracy</th><th colspan="2">AUC</th><th colspan="2">Size</th><th rowspan="2">Data set</th><th colspan="2">Accuracy</th><th colspan="2">AUC</th><th colspan="2">Size</th></tr><tr><th>Ind.</th><th>Ext.</th><th>Ind.</th><th>Ext.</th><th>Ind.</th><th>Ext.</th><th>Ind.</th><th>Ext.</th><th>Ind.</th><th>Ext.</th><th>Ind.</th><th>Ext.</th></tr></thead><tbody><tr><td>ar1</td><td>.909</td><td>.913</td><td>.457</td><td>.608</td><td>8.0</td><td>6.3</td><td>kc1</td><td>.839</td><td>.848</td><td>.680</td><td>.595</td><td>100.0</td><td>10.8</td></tr><tr><td>ar4</td><td>.817</td><td>.808</td><td>.664</td><td>.660</td><td>8.5</td><td>5.8</td><td>kc2</td><td>.827</td><td>.828</td><td>.785</td><td>.674</td><td>26.5</td><td>8.0</td></tr><tr><td>breast-w</td><td>.921</td><td>.928</td><td>.953</td><td>.945</td><td>20.8</td><td>15.0</td><td>kc3</td><td>.889</td><td>.903</td><td>.688</td><td>.629</td><td>25.5</td><td>4.8</td></tr><tr><td>colic</td><td>.705</td><td>.717</td><td>.713</td><td>.731</td><td>34.8</td><td>21.8</td><td>letter</td><td>.824</td><td>.800</td><td>.838</td><td>.824</td><td>20.0</td><td>23.3</td></tr><tr><td>credit-a</td><td>.712</td><td>.751</td><td>.771</td><td>.800</td><td>57.5</td><td>32.5</td><td>liver</td><td>.578</td><td>.620</td><td>.561</td><td>.610</td><td>22.3</td><td>23.5</td></tr><tr><td>credit-g</td><td>.683</td><td>.712</td><td>.620</td><td>.643</td><td>108.0</td><td>51.3</td><td>mw1</td><td>.901</td><td>.917</td><td>.679</td><td>.616</td><td>15.5</td><td>4.5</td></tr><tr><td>cylinder</td><td>.644</td><td>.634</td><td>.630</td><td>.638</td><td>63.3</td><td>50.3</td><td>sonar</td><td>.618</td><td>.680</td><td>.657</td><td>.733</td><td>18.8</td><td>14.0</td></tr><tr><td>diabetes</td><td>.691</td><td>.711</td><td>.690</td><td>.684</td><td>33.3</td><td>29.5</td><td>spect</td><td>.771</td><td>.793</td><td>.699</td><td>.731</td><td>25.0</td><td>11.8</td></tr><tr><td>heart-c</td><td>.719</td><td>.723</td><td>.754</td><td>.773</td><td>31.0</td><td>21.8</td><td>spectf</td><td>.744</td><td>.756</td><td>.718</td><td>.691</td><td>20.3</td><td>13.0</td></tr><tr><td>heart-h</td><td>.760</td><td>.786</td><td>.769</td><td>.804</td><td>28.5</td><td>14.5</td><td>tic-tac-toe</td><td>.770</td><td>.694</td><td>.775</td><td>.631</td><td>52.8</td><td>45.5</td></tr><tr><td>heart-s</td><td>.767</td><td>.748</td><td>.810</td><td>.784</td><td>31.3</td><td>17.3</td><td>vote</td><td>.899</td><td>.905</td><td>.933</td><td>.928</td><td>19.8</td><td>13.5</td></tr><tr><td>hepatitis</td><td>.781</td><td>.781</td><td>.746</td><td>.701</td><td>18.5</td><td>14.0</td><td>vowel</td><td>.786</td><td>.725</td><td>.804</td><td>.782</td><td>13.5</td><td>15.3</td></tr><tr><td>iono</td><td>.769</td><td>.789</td><td>.732</td><td>.750</td><td>13.3</td><td>13.8</td><td>Mean</td><td>.761</td><td>.767</td><td>.719</td><td>.712</td><td>31.9</td><td>19.0</td></tr><tr><td>jEdit4042</td><td>.642</td><td>.639</td><td>.669</td><td>.671</td><td>21.3</td><td>14.8</td><td>Wins</td><td>8</td><td>19</td><td>15</td><td>12</td><td>4</td><td>23</td></tr><tr><td>jEdit4243</td><td>.583</td><td>.589</td><td>.606</td><td>.599</td><td>23.5</td><td>15.8</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

Turning to the results for conformal prediction, Fig 1 shows the behavior of extracted J48 trees as conformal predictors on the Iono data set, when using true targets for calibration. Since the conformal predictor is calibrated using true targets, it is the error and not the infidelity that is bounded by the significance level.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Rule extraction using opaque model. Iono.</figcaption></figure>

First of all, the conformal predictor is valid and well-calibrated, since the error rate is very close to the corresponding significance level. Analyzing the efficiency, the number of singleton predictions (OneC) starts at approximately
40% for $\epsilon = 0.05$, and then rises quickly to over 70% at $\epsilon = 0.15$. The number of multiple predictions (MultiC), i.e., predictions containing both classes, has the exact opposite behavior. The first empty predictions (ZeroC) appear at $\epsilon = 0.10$. Interestingly enough, OneAcc (the accuracy of the singleton predictions) is always higher than the accuracy of the underlying tree model (0.769), so singleton predictions from the conformal predictor could be trusted more than predictions from the original model. Finally, the fidelity of the singleton predictions (One-Fid) is very high, always over 80%. In fact, the infidelity rate is always lower than the error, indicating that the extracted conformal predictor is very faithful to the opaque model, even if this is not enforced by the conformal prediction framework in this setup.

Fig 2 below shows the behavior of extracted J48 trees as conformal predictors on the Iono data set, when using the ensemble predictions as targets for calibration.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Rule extraction for opaque model. Iono.</figcaption></figure>

In this setup, it is the infidelity and not the error that is guaranteed, and indeed the actual infidelity rate is very close to the significance level. Here, singleton predictions are more common than for the other setup, i.e., it is easier to have high confidence in predictions about ensemble predictions than true targets. The error rate is slightly higher than the significance level, but interestingly enough both OneAcc and OneFid are comparable to the results for the previous setup.

Table 2 below shows detailed results for the three different conformal prediction setups, when the level of significance is $\epsilon = 0.10$.
<table><caption>**Table 2.** Conformal prediction with $\epsilon = 0.1$. Bold numbers indicate criteria that are guaranteed by the conformal prediction framework.</caption><thead><tr><th rowspan="2"></th><th colspan="3">Error</th><th colspan="3">OneC</th><th colspan="3">OneAcc</th><th colspan="3">OneFid</th></tr><tr><th>J48</th><th>RE-a</th><th>RE-f</th><th>J48</th><th>RE-a</th><th>RE-f</th><th>J48</th><th>RE-a</th><th>RE-f</th><th>J48</th><th>RE-a</th><th>RE-f</th></tr></thead><tbody><tr><td>ar1</td><td><strong>.070</strong></td><td><strong>.070</strong></td><td>.124</td><td>.054</td><td><strong>.091</strong></td><td></td><td>.904</td><td>.821</td><td>.842</td><td>.919</td><td>.939</td><td>.930</td><td>.957</td><td>.950</td></tr><tr><td>ar4</td><td><strong>.043</strong></td><td><strong>.052</strong></td><td>.083</td><td>.042</td><td><strong>.056</strong></td><td></td><td>.369</td><td>.366</td><td>.649</td><td>.757</td><td>.870</td><td>.907</td><td>.881</td><td>.917</td></tr><tr><td>breast-w</td><td><strong>.090</strong></td><td><strong>.094</strong></td><td>.105</td><td>.095</td><td><strong>.102</strong></td><td></td><td>.936</td><td>.886</td><td>.852</td><td>.940</td><td>.944</td><td>.948</td><td>.946</td><td>.952</td></tr><tr><td>colic</td><td><strong>.098</strong></td><td><strong>.094</strong></td><td>.143</td><td>.063</td><td><strong>.086</strong></td><td></td><td>.538</td><td>.503</td><td>.652</td><td>.800</td><td>.797</td><td>.770</td><td>.870</td><td>.861</td></tr><tr><td>credit-a</td><td><strong>.094</strong></td><td><strong>.111</strong></td><td>.182</td><td>.055</td><td><strong>.089</strong></td><td></td><td>.556</td><td>.644</td><td>.818</td><td>.803</td><td>.818</td><td>.770</td><td>.908</td><td>.885</td></tr><tr><td>credit-g</td><td><strong>.104</strong></td><td><strong>.085</strong></td><td>.195</td><td>.024</td><td><strong>.090</strong></td><td></td><td>.440</td><td>.409</td><td>.745</td><td>.753</td><td>.780</td><td>.733</td><td>.935</td><td>.880</td></tr><tr><td>cylinder</td><td><strong>.097</strong></td><td><strong>.099</strong></td><td>.122</td><td>.073</td><td><strong>.093</strong></td><td></td><td>.317</td><td>.344</td><td>.427</td><td>.664</td><td>.695</td><td>.698</td><td>.764</td><td>.785</td></tr><tr><td>diabetes</td><td><strong>.083</strong></td><td><strong>.096</strong></td><td>.191</td><td>.044</td><td><strong>.098</strong></td><td></td><td>.415</td><td>.447</td><td>.723</td><td>.795</td><td>.774</td><td>.734</td><td>.888</td><td>.865</td></tr><tr><td>heart-c</td><td><strong>.073</strong></td><td><strong>.091</strong></td><td>.127</td><td>.045</td><td><strong>.084</strong></td><td></td><td>.407</td><td>.452</td><td>.586</td><td>.793</td><td>.787</td><td>.770</td><td>.879</td><td>.857</td></tr><tr><td>heart-h</td><td><strong>.083</strong></td><td><strong>.080</strong></td><td>.163</td><td>.034</td><td><strong>.075</strong></td><td></td><td>.509</td><td>.565</td><td>.858</td><td>.786</td><td>.845</td><td>.818</td><td>.931</td><td>.914</td></tr><tr><td>heart-s</td><td><strong>.070</strong></td><td><strong>.072</strong></td><td>.119</td><td>.037</td><td><strong>.059</strong></td><td></td><td>.461</td><td>.458</td><td>.625</td><td>.852</td><td>.834</td><td>.804</td><td>.915</td><td>.897</td></tr><tr><td>hepatitis</td><td><strong>.045</strong></td><td><strong>.055</strong></td><td>.081</td><td>.032</td><td><strong>.048</strong></td><td></td><td>.528</td><td>.445</td><td>.578</td><td>.925</td><td>.853</td><td>.851</td><td>.936</td><td>.914</td></tr><tr><td>iono</td><td><strong>.078</strong></td><td><strong>.089</strong></td><td>.108</td><td>.090</td><td><strong>.096</strong></td><td></td><td>.570</td><td>.608</td><td>.625</td><td>.845</td><td>.850</td><td>.805</td><td>.806</td><td>.813</td></tr><tr><td>jEdit4042</td><td><strong>.091</strong></td><td><strong>.089</strong></td><td>.197</td><td>.022</td><td><strong>.062</strong></td><td></td><td>.369</td><td>.291</td><td>.619</td><td>.717</td><td>.659</td><td>.662</td><td>.908</td><td>.880</td></tr><tr><td>jEdit4243</td><td><strong>.083</strong></td><td><strong>.080</strong></td><td>.265</td><td>.015</td><td><strong>.068</strong></td><td></td><td>.245</td><td>.221</td><td>.665</td><td>.647</td><td>.620</td><td>.627</td><td>.940</td><td>.888</td></tr><tr><td>kcl1</td><td><strong>.093</strong></td><td><strong>.097</strong></td><td>.217</td><td>.002</td><td><strong>.095</strong></td><td></td><td>.784</td><td>.729</td><td>.900</td><td>.881</td><td>.866</td><td>.870</td><td>.997</td><td>.997</td></tr><tr><td>kcl2</td><td><strong>.088</strong></td><td><strong>.100</strong></td><td>.216</td><td>.011</td><td><strong>.101</strong></td><td></td><td>.758</td><td>.691</td><td>.934</td><td>.883</td><td>.853</td><td>.840</td><td>.985</td><td>.969</td></tr><tr><td>kcl3</td><td><strong>.075</strong></td><td><strong>.081</strong></td><td>.157</td><td>.011</td><td><strong>.088</strong></td><td></td><td>.878</td><td>.931</td><td>.916</td><td>.920</td><td>.913</td><td>.920</td><td>.989</td><td>.995</td></tr><tr><td>letter</td><td><strong>.098</strong></td><td><strong>.089</strong></td><td>.098</td><td>.082</td><td><strong>.090</strong></td><td></td><td>.657</td><td>.650</td><td>.657</td><td>.860</td><td>.853</td><td>.851</td><td>.871</td><td>.865</td></tr><tr><td>liver</td><td><strong>.094</strong></td><td><strong>.072</strong></td><td>.170</td><td>.042</td><td><strong>.104</strong></td><td></td><td>.253</td><td>.263</td><td>.516</td><td>.626</td><td>.724</td><td>.665</td><td>.851</td><td>.783</td></tr><tr><td>mwl1</td><td><strong>.091</strong></td><td><strong>.091</strong></td><td>.129</td><td>.047</td><td><strong>.089</strong></td><td></td><td>.963</td><td>.990</td><td>.932</td><td>.911</td><td>.919</td><td>.935</td><td>.967</td><td>.983</td></tr><tr><td>sonar</td><td><strong>.070</strong></td><td><strong>.108</strong></td><td>.072</td><td>.091</td><td><strong>.089</strong></td><td></td><td>.233</td><td>.423</td><td>.303</td><td>.702</td><td>.737</td><td>.729</td><td>.788</td><td>.701</td></tr><tr><td>spect</td><td><strong>.070</strong></td><td><strong>.088</strong></td><td>.158</td><td>.026</td><td><strong>.056</strong></td><td></td><td>.549</td><td>.665</td><td>.844</td><td>.875</td><td>.866</td><td>.819</td><td>.960</td><td>.934</td></tr><tr><td>spectf</td><td><strong>.078</strong></td><td><strong>.085</strong></td><td>.114</td><td>.066</td><td><strong>.085</strong></td><td></td><td>.491</td><td>.444</td><td>.559</td><td>.826</td><td>.808</td><td>.805</td><td>.843</td><td>.807</td></tr><tr><td>tic-tac-toe</td><td><strong>.105</strong></td><td><strong>.087</strong></td><td>.235</td><td>.023</td><td><strong>.116</strong></td><td></td><td>.635</td><td>.370</td><td>.794</td><td>.792</td><td>.758</td><td>.707</td><td>.926</td><td>.857</td></tr><tr><td>vote</td><td><strong>.096</strong></td><td><strong>.079</strong></td><td>.091</td><td>.062</td><td><strong>.077</strong></td><td></td><td>.875</td><td>.845</td><td>.869</td><td>.923</td><td>.939</td><td>.934</td><td>.954</td><td>.946</td></tr><tr><td>vowel</td><td><strong>.083</strong></td><td><strong>.064</strong></td><td>.078</td><td>.100</td><td><strong>.097</strong></td><td></td><td>.581</td><td>.458</td><td>.378</td><td>.836</td><td>.854</td><td>.805</td><td>.777</td><td>.724</td></tr><tr><td>Mean</td><td><strong>.083</strong></td><td><strong>.085</strong></td><td><strong>.146</strong></td><td><strong>.048</strong></td><td><strong>.085</strong></td><td></td><td><strong>.564</strong></td><td><strong>.553</strong></td><td><strong>.699</strong></td><td><strong>.816</strong></td><td><strong>.821</strong></td><td><strong>.804</strong></td><td><strong>.903</strong></td><td><strong>.882</strong></td></tr><tr><td>Mean Rank</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td></td><td>2.19</td><td>2.41</td><td>1.41</td><td>1.85</td><td>1.81</td><td>2.33</td><td>1.26</td><td>1.74</td></tr></tbody></table>

Investigating the errors and infidelities, it is obvious that the conformal prediction framework applies to both rule extraction scenarios, i.e., when the error rate or the infidelity rate must be lower than the significance level. On almost all data sets, the errors for J48 and RE-a are quite close to the significance level $\epsilon = 0.1$, indicating that the conformal predictors are valid and well-calibrated. Similarly, the infidelities for RE-f are also close to 0.1, on most data sets. Looking at the efficiency, measured using the OneC metric, RE-f is clearly the most efficient conformal predictor. An interesting observation is that the errors for RE-f often are much higher than the corresponding significance level, thus indicating that the extracted model quite often is certain about the prediction from the ensemble, even when the ensemble prediction turns out to be wrong. This phenomenon is also obvious from the lower OneAcc exhibited by RE-f.
Regarding infidelities and OneFid, it may be noted that RE-a turns out to be overly conservative. This actually results in a higher OneFid, compared to RE-f, but the explanation is the much fewer singleton predictions. Simply put, with a high demand on confidence in the selected singleton predictions, these tend to be predicted identically by the ensemble.

Table 3 below shows a summary, presenting averaged values and mean ranks over all data sets for three different significance levels. Included here is the metric AvgC, which is the average number of labels in the prediction sets. Since there are very few empty predictions at $\epsilon = 0.05$, OneC and AvgC will, for this significance level, produce the same ordering of the setups.

<table><caption>**Table 3.** Conformal prediction summary. Bold numbers indicate criteria that are guaranteed by the conformal prediction framework.</caption><thead><tr><th rowspan="2"></th><th colspan="3">ε = 0.05</th><th colspan="3">ε = 0.1</th><th colspan="3">ε = 0.2</th></tr><tr><th>Ind</th><th>RE-a</th><th>RE-f</th><th>Ind</th><th>RE-a</th><th>RE-f</th><th>Ind</th><th>RE-a</th><th>RE-f</th></tr></thead><tbody><tr><td>Error</td><td><strong>.034</strong></td><td><strong>.034</strong></td><td>.084</td><td><strong>.083</strong></td><td><strong>.085</strong></td><td>.146</td><td><strong>.184</strong></td><td><strong>.183</strong></td><td>.251</td></tr><tr><td>Infidelity</td><td>-</td><td>.018</td><td><strong>.035</strong></td><td>-</td><td>.046</td><td><strong>.084</strong></td><td>-</td><td>.124</td><td><strong>.190</strong></td></tr><tr><td>AvgC</td><td>1.66</td><td>1.70</td><td>1.46</td><td>1.43</td><td>1.44</td><td>1.26</td><td>1.15</td><td>1.15</td><td>1.01</td></tr><tr><td>Rank</td><td>2.11</td><td>2.70</td><td>1.19</td><td>2.30</td><td>2.48</td><td>1.22</td><td>2.48</td><td>2.33</td><td>1.19</td></tr><tr><td>OneC</td><td>.339</td><td>.297</td><td>.525</td><td>.564</td><td>.552</td><td>.701</td><td>.772</td><td>.778</td><td>.821</td></tr><tr><td>Rank</td><td>2.11</td><td>2.70</td><td>1.19</td><td>2.19</td><td>2.41</td><td>1.41</td><td>2.15</td><td>2.04</td><td>1.81</td></tr><tr><td>OneAcc</td><td>.772</td><td>.752</td><td>.778</td><td>.815</td><td>.819</td><td>.805</td><td>.794</td><td>.796</td><td>.794</td></tr><tr><td>Rank</td><td>1.78</td><td>1.89</td><td>2.33</td><td>1.85</td><td>1.89</td><td>2.26</td><td>2.07</td><td>1.93</td><td>2.00</td></tr><tr><td>OneFid</td><td>-</td><td>.824</td><td>.857</td><td>-</td><td>.906</td><td>.884</td><td>-</td><td>.878</td><td>.869</td></tr><tr><td>Rank</td><td>-</td><td>1.44</td><td>1.56</td><td>-</td><td>1.22</td><td>1.78</td><td>-</td><td>1.48</td><td>1.52</td></tr></tbody></table>

Even when analyzing all three significance levels, all conformal predictors seem to be valid and reasonably well-calibrated. Looking for instance at RE-a, the averaged errors over all data sets are 0.034 for $\epsilon = 0.05$, 0.084 for $\epsilon = 0.1$ and 0.183 for $\epsilon = 0.2$. Similarly, the averaged infidelities for RE-f are 0.035 for $\epsilon = 0.05$, 0.084 for $\epsilon = 0.1$ and 0.190 for $\epsilon = 0.2$.

Comparing efficiencies, RE-f is significantly more efficient, with regard to both OneC and AvgC, than the other two setups. J48 and RE-a have comparable efficiencies. Regarding OneAcc, J48 and RE-a are most often more accurate than RE-f. It must, however, be noted that RE-f has a fundamentally different purpose than RE-a and J48, so RE-a should only be compared directly to J48; they are both instances of, in Zhou's terminology, rule extraction using opaque models, while RE-f, is rule extraction for opaque models. Consequently the most important observation is that all setups have worked as intended, producing valid, well-calibrated and rather efficient conformal predictors for the two different rule extraction scenarios.
## 5 Concluding remarks

In this paper, which should be regarded as a proof-of-concept, conformal prediction has been extended to rule extraction for opaque models and rule extraction using opaque models. The results show that conformal prediction enables extraction of efficient and comprehensible models, where either the error rate or the infidelity rate is guaranteed. This represents an important addition to the rule extraction tool-box, specifically addressing the problem with a potentially poor test set fidelity present in most black-box rule extractors.

For some reason rule extraction has not been extensively used on regression models, so the next step is to apply conformal prediction to this. We believe that the prediction intervals produced by conformal prediction regression will be a natural part of making extracted regression models accurate and comprehensible.

## References

1. Quinlan, J.R.: C4.5: programs for machine learning. Morgan Kaufmann (1993)

2. Vovk, V., Gammerman, A., Shafer, G.: Algorithmic Learning in a Random World. Springer-Verlag New York, Inc. (2005)

3. Papadopoulos, H.: Inductive conformal prediction: Theory and application to neural networks. Tools in Artificial Intelligence **18** (2008) 315–330

4. Nguyen, K., Luo, Z.: Conformal prediction for indoor localisation with fingerprinting method. Artificial Intelligence Applications and Innovations (2012) 214–223

5. Makili, L., Vega, J., Dormido-Canto, S., Pastor, I., Murari, A.: Computationally efficient svm multi-class image recognition with confidence measures. Fusion Engineering and Design **86**(6) (2011) 1213–1216

6. Andrews, R., Diederich, J., Tickle, A.B.: Survey and critique of techniques for extracting rules from trained artificial neural networks. Knowl.-Based Syst. **8**(6) (1995) 373–389

7. Rudy, H.L., Lu, H., Setiono, R., Liu, H.: Neurorule: A connectionist approach to data mining. (1995) 478–489

8. Fu, L.: Rule learning by searching on adapted nets. In: AAAI. (1991) 590–595

9. Craven, M.W., Shavlik, J.W.: Extracting tree-structured representations of trained networks. In: Advances in Neural Information Processing Systems, MIT Press (1996) 24–30

10. Huysmans, J., Baesens, B., Vanthienen, J.: Using rule extraction to improve the comprehensibility of predictive models. FETEW Research Report KBI 0612, K. U. Leuven (2006)

11. Martens, D., Huysmans, J., Setiono, R., Vanthienen, J., Baesens, B.: Rule extraction from support vector machines: An overview of issues and application in credit scoring. In: Rule Extraction from Support Vector Machines. (2008) 33–63

12. Zhou, Z.H.: Rule extraction: using neural networks or for neural networks? J. Comput. Sci. Technol. **19**(2) (2004) 249–253

13. Witten, I.H., Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann (2005)

14. Asuncion, A., Newman, D.J.: UCI machine learning repository (2007)

15. Sayyad Shirabad, J., Menzies, T.: PROMISE Repository of Software Engineering Databases. School of Information Technology and Engineering, University of Ottawa, Canada (2005)