Henrik Linusson
email: henrik.linusson@hb.se

Ulf Johansson
email: ulf.johansson@hb.se

Henrik Boström
email: henrik.bostrom@dsv.su.se

Tuve Löfström
email: tuve.lofstrom@hb.se

Efficiency Comparison of Unstable Transductive and Inductive Conformal Classifiers

In the conformal prediction literature, it appears axiomatic that transductive conformal classifiers possess a higher predictive efficiency than inductive conformal classifiers, however, this depends on whether or not the nonconformity function tends to overfit misclassified test examples. With the conformal prediction framework's increasing popularity, it thus becomes necessary to clarify the settings in which this claim holds true. In this paper, the efficiency of transductive conformal classifiers based on decision tree, random forest and support vector machine classification models is compared to the efficiency of corresponding inductive conformal classifiers. The results show that the efficiency of conformal classifiers based on standard decision trees or random forests is substantially improved when used in the inductive mode, while conformal classifiers based on support vector machines are more efficient in the transductive mode. In addition, an analysis is presented that discusses the effects of calibration set size on inductive conformal classifier efficiency.

Introduction

Conformal Prediction [START_REF] Vovk | Algorithmic learning in a random world[END_REF] is a machine learning framework for associating predictions for novel data with a measure of their confidence; whereas traditional machine learning algorithms produce point predictions -a single label ŷ per test example -conformal predictors produce prediction regions -prediction sets Ŷ ⊆ Y that, in the long run, contain the true labels for the test set with some predefined probability 1 -. Historically, such confidence predictions have relied on the Bayesian learning and Probably Approximately Correct (PAC) learning frameworks; however, the validity of Bayesian confidence predictions relies on an assumption of the a priori distribution, while PAC learning confidence measures apply to the entire model, and not the individual predictions [START_REF] Papadopoulos | Inductive conformal prediction: Theory and application to neural networks[END_REF]. In contrast, conformal predictors are able to produce confidence measures tailored for each separate prediction on novel data, and rely only on the assumption that the data is exchangeable -that the ordering of data points does not affect their joint distributions -which is an even weaker assumption than the i.i.d. assumption typically required by traditional machine learning algorithms.

The method of constructing prediction regions using conformal predictors relies on measuring the strangeness -the nonconformity -of each data point, using some (arbitrary) real-valued function, called a nonconformity function, that measures the degree of strangeness of an example (x i , y i ) in relation to a bag (multiset) of examples Z = {(x 1 , y 1 ), ..., (x i , y i ), ..., (x k , y k )}. For classification problems, this nonconformity measure is often based on the predictions of a traditional machine learning algorithm, called the underlying model of the conformal predictor. By comparing the nonconformity of a tentative classification (x k+1 , ỹ) for a novel (test) input pattern x k+1 to the nonconformity scores of previously seen data, a conformal predictor can make inferences as to whether ỹ is likely to be a correct classification for x k+1 , and thus decide whether or not to include ỹ in the prediction region Ŷk+1 .

There are two major categories of conformal predictors: transductive conformal predictors (TCP) [START_REF] Gammerman | Learning by transduction[END_REF][START_REF] Saunders | Transduction with confidence and credibility[END_REF] and inductive conformal predictors (ICP) [START_REF] Papadopoulos | Inductive conformal prediction: Theory and application to neural networks[END_REF][START_REF] Papadopoulos | Inductive confidence machines for regression[END_REF]; both variants are based on the same principles, and place the same exchangability requirement on the data. Where they differ is in their usage of the training data, and their overall training scheme. For a novel input pattern x k+1 and every tentative prediction ỹ ∈ Y , TCP measures the nonconformity of all examples in the bag Z = Z ∪ {(x k+1 , ỹ)} relative to each other, meaning that the instance (x k+1 , ỹ) is considered when calculating the nonconformity scores for the training set Z. Hence, for every new pattern x k+n and every ỹ, the underlying model needs to be retrained, and the nonconformity scores for the training data recomputed, rendering TCP computationally intensive. In ICP, only part of the data is used to train the underlying model (once), while the remaining data (a calibration set) is set aside to provide an unbiased estimate of the distribution of nonconformity scores.

The predictive efficiency -that is, the size of the prediction regions produced -of any conformal predictor is closely tied to the nonconformity function's ability to rank examples by order of strangeness. Moreover, as noted in several papers, ICP models typically suffer a small loss in predictive efficiency compared to corresponding TCP models due to the reduced number of training and calibration examples [START_REF] Vovk | Algorithmic learning in a random world[END_REF][START_REF] Papadopoulos | Inductive confidence machines for regression[END_REF][START_REF] Papadopoulos | Inductive conformal prediction: Theory and application to neural networks[END_REF][7][START_REF] Balasubramanian | Conformal prediction for reliable machine learning: theory, adaptations, and applications[END_REF]. However, as pointed out in [START_REF] Vovk | Algorithmic learning in a random world[END_REF], an unstable nonconformity function -one that is heavily influenced by an outlier example, i.e., an erroneously labled test instance (x k+1 , ỹ) -can cause TCP models to become inefficient. So, the choice between TCP and ICP is not so clear-cut: on the one hand, ICP will surely always produce its predictions faster than TCP, and TCP is often expected to have a higher predictive power than ICP. On the other hand, the efficiency of TCP relies on the chosen nonconformity function being stable, meaning that the underlying model does not train outlier examples into its learned rule [START_REF] Vovk | Algorithmic learning in a random world[END_REF]. When choosing a conformal prediction setup, a user should thus consider not only the trade-off between predictive speed and predictive power in TCP and ICP, but also whether the chosen nonconformity function can be used effectively in TCP.

Decision trees and random forests are commonly used model types that are able to accommodate their training examples well, and, due to their ability to near-perfectly fit their training data, these model types should be expected to function better as underlying models in ICP than in TCP. To the best of our knowledge, however, this claim has not been investigated in existing literature.

In this study, the efficiency of TCP classifiers based on off-the-shelf decision trees and random forests, implemented by the scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF] Python package, is compared to the efficiency of corresponding ICP classifiers; the results of this comparison are juxtaposted with an identical comparison of TCP and ICP classifiers based on stable support vector machines. To allow for a straightforward comparison of TCP and ICP classifiers, an analysis is also presented that discussess the effects of calibration set size on ICP classifier efficiency.

Background

Given some nonconformity scoring function ∆(Z, x i , y i ) → R, a conformal predictor can produce prediction regions that are valid in the sense that they contain the true target with some predefined probability 1 -. For classification problems, a common approach is to define a nonconformity function by combining a traditional machine learning algorithm and some error measure of the algorithm's predictions, e.g., the margin scoring function used in [START_REF] Johansson | Conformal prediction using decision trees[END_REF]:

∆(h, x i , y i ) = P (y i | h(x i )) -arg max y =yi P (y | h(x i )), ( 1
)
where h is a predictive model trained on some set Z, i.e., h represents a generalization of Z. Given the nature of classification problems in general, it is to be expected that a test pattern that deviates from the examples found in Z is likely to be misclassified by h, i.e., examples that are not conforming to Z are likely to be assigned large nonconformity scores.

When making a prediction using a conformal classifier, the nonconformity function is applied to a set of examples with known labels, resulting in a set of nonconformity scores α 1 , ..., α k that represents a sample which is to be used for statistical inference (we here refer to this as the nonconformity baseline). The test pattern x k+1 is then assigned a tentative classification (x k+1 , ỹ), where ỹ ∈ Y , and a nonconformity score α k+1 = ∆(Z, x k+1 , ỹ). Using a form of hypothesis testing (described in Sections 2.1 and 2.2), the conformal classifier attempts to reject the null hypothesis that (x k+1 , ỹ) is conforming with Z, i.e., if the nonconformity score α k+1 is higher than for most examples in Z, as estimated by the nonconformity baseline, then ỹ is considered to be an unlikely classification for x k+1 and can be excluded from the final prediction set.

Transductive Conformal Predictors

A transductive conformal classifier uses the full training set Z to establish the nonconformity baseline. Due to the exchangeability assumption, this requires that the test pattern (x k+1 , ỹ) is considered when calculating the nonconformity scores α 1 , ..., α k , i.e., if the nonconformity function ∆ is based on an inductive model h, then (x k+1 , ỹ) must be included in the training set for h. If it is not, then there is a possibility that h will have a larger bias towards its training examples than towards (x k+1 , ỹ), meaning that the training examples and the test pattern might have different expected nonconformity values (which is a direct violation of the exchangeability assumption3 ). TCP thus requires that the underlying model h is trained n |Y | times, where n is the number of test patterns, using the following scheme:

1. Assume a label ỹ and form the set

Z = Z ∪ {(x k+1 , ỹ)}. 2. Use Z to train a model h. 3. For each (x i , y i ) ∈ Z calculate α i = ∆(h, x i , y i ). 4. Calculate the p-value for (x k+1 , ỹ) as p(x k+1 , ỹ) = |{z i ∈ Z | α i ≥ α k+1 }| |Z | . (2)
5. If p(x k+1 , ỹ) > , include ỹ in the prediction region Ŷk+1 .

Inductive Conformal Predictors

Inductive conformal predictors instead use only part of the training data to fit the underlying model h, setting aside a calibration set that is later used to establish the nonconformity baseline. Since the proper training set Z t ⊂ Z used to fit h and the calibration set Z c ⊂ Z are disjoint, the nonconformity scores α 1 , ..., α k-t are exchangeable (unbiased) with the nonconformity score α k+1 without the need for including (x k+1 , ỹ) in the training of h; thus, an ICP only needs to be trained once:

1. Divide Z into two disjoint subsets Z t and Z c . 2. Use Z t to train a model h.

For each (x

i , y i ) ∈ Z c , calculate α i = ∆(h, x i , y i ).
For a novel test instance x k+1 :

1. Assume a label ỹ and calculate α k+1 = ∆(h, x k+1 , ỹ). 2. Calculate the p-value for (x k+1 , ỹ) as

p(x k+1 , ỹ) = |{z i ∈ Z c | α i ≥ α k+1 }| + 1 |Z c | + 1 . (3)
3. If p(x k+1 , ỹ) > , include ỹ in the prediction region Ŷk+1 .

The main point of interest of this study is the efficiency comparison of TCP and ICP classifiers based on decision tree, random forest and support vector machine models, but, to provide a straightforward comparison between the two, it is also necessary to find a suitable choice of calibration set size for the ICP classifiers.

To the best of our knowledge, no thorough investigation has been published that discusses the effects of calibration set size on ICP classifier efficiency, and so the results presented in this paper contain first a discussion of ICP classifier setup, and second a comparison of ICP and TCP classifier efficiency.

To investigate what effect the calibration set size has on the efficiency of ICP classifiers using various types of underlying models, several ICP models were trained on five binary classification sets from the LIBSVM website [START_REF] Chang | Libsvm: a library for support vector machines[END_REF] (a9a, covertype, cod-rna, ijcnn1 and w8a), using different amounts of training and calibration data. To compare the efficiency of the ICP and TCP variants, both types of classifiers were trained on 19 binary classification sets from the UCI repository [START_REF] Bache | UCI machine learning repository[END_REF]. The ICP models used a suitable calibration size as suggested by the results from the first experiment (20%). To limit the training time required for the TCP models, results from the larger datasets (kr-vs-kp, sick and spambase) were obtained using 1x10-fold cross-validation, while the results from the remaining sets were obtained using 5x10-fold cross-validation.

In both experiments, three different types of underlying models were used: decision trees (CART) [START_REF] Breiman | Classification and regression trees[END_REF], random forests (RF) [START_REF] Breiman | Random forests[END_REF] and support vector machines (SVM) [START_REF] Cortes | Support-vector networks[END_REF]. The CART models used relative frequency probability estimates and no pruning, making them highly susceptible to overfitting noisy data. RF models (here consisting of 100 trees) are relatively robust to noise, but since the ensemble members are simple CART models, noisy examples are still fit into the learned rule to some extent. SVM models are, in contrast, stable to isolated noisy data points [START_REF] Buciu | Demonstrating the stability of support vector machines for classification[END_REF]. The scikit-learn library [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF] for Python, using default settings, was used to train the underlying models. The margin nonconformity function (1) was used to construct the conformal classifiers, and predictions were made in the off-line (batch) mode.

Results

Figure 1 shows the relationships between training set size, calibration set size and efficiency (measured as AvgC -the average number of labels per prediction). The size of the calibration set is expressed as a portion of the full dataset, i.e., the point (500, 1000) uses 500 of the total (1000) available examples as calibration data, and the remaining 500 examples as training data. The results are averaged over all five datasets and all five iterations. Clearly, the more data that is made available to the ICP classifier, the more efficient its predictions are, but only if the data is used sensibly. If more data is made available, and all newly available examples are added to the calibration set (any line y = x+k in the six plots), the efficiency remains virtually unchanged at = 0.05. If instead all newly available examples are added to the proper training set (any line parallel to the Y axis) the efficiency of the ICP model increases greatly, whereas, naturally then, the efficiency decreases if a larger calibration set is used while the total amount of available data remains unchanged (any line parallel to the X axis). The chosen (absolute) size of the calibration set thus has a small effect on ICP classifier efficiency, while the size of the proper training set is more strongly correlated with efficiency (cf. the correlations, r t for training set size and r c for calibration set size, listed below the plots). As illustrated by Figures 1d, 1e and1f, the size of the calibration set plays a larger role in determining efficiency when = 0.01 than it does when = 0.05, although the training set size is clearly the most important factor for maximizing efficiency at both significance levels. The best performing ICP classifiers are those using 15 -30% of the full training set as their calibration set. Notably, the performance of ICP classifiers using a calibration set containing less than 500 examples is quite poor when = 0.01, regardless of training set size, suggesting that at least a few hundred examples should be used for calibration unless this leaves too few examples in the proper training set. The coverage (i.e. the 'empirical validity') of the conformal classifiers is not tabulated, however, all tested conformal classifiers show a coverage at or near the expected error rates on average. Note though, that the conformal classifiers using a very small calibration set (100 examples) displayed a larger variance in their coverage than the conformal classifiers using 500 calibration examples; in turn, using 500 calibration examples showed no substantial increase in variance compared to using a larger calibration set. Tables 1 and2 show a comparison of the efficiency of ICP and TCP classifiers based on CART, random forest and SVM models. Note that the ranks are computed only within each TCP-ICP pair, i.e., the different underlying model types are not compared to each other in terms of efficiency ranks. Mean ranks in bold indicate significant differences at α = 0.05 as reported by a two-tailed Wilcoxon signed-ranks test.

The stable SVM models do indeed appear to gain from being able to use the full dataset for both training and calibration when used in the TCP mode. At = 0.01, the SVM-based TCP classifiers are significantly more efficient that SVMbased ICP classifiers; at = 0.05 the SVM-TCP classifiers are more efficient on average, although the difference is not significant. It is evident, however, that the unpruned CART models -the most noise sensitive of the three model types -struggle with rejecting erroneous class labels in a TCP setting, likely due to the noisy test examples (x i , ỹ = y i ) being fitted into the learned rules. TCP models based on CART are significantly less efficient than ICP-CART, both at = 0.05 and = 0.01. As expected, the RF models fare better in terms of TCP efficiency; the overfitting of the underlying CART models is counteracted by the smoothing effect of the ensemble constellation, however, not to such an extent that the TCP-RF models are more efficient than ICP-RF. ICP-RF is more efficient than TCP-RF on average, but the difference is not significant, neither at = 0.05 nor at = 0.01.

Related Work

As noted in [START_REF] Vovk | Algorithmic learning in a random world[END_REF], TCP classifiers using unstable nonconformity functions can be made more efficient through a slight modification of the transductive procedure. This modification involves calculating the nonconformity scores in a leave-oneout manner (LOOTCP), where the nonconformity of an example (x i , y i ) ∈ Z is calculated from the set Z \ (x i , y i ). Hence, in LOOTCP, the underlying model needs to be retrained not only for every test example and every tentative classification, but also for every training example. In principle, LOOTCP should indeed be expected to produce more efficient predictions than ICP, however, as LOOTCP increases the computational complexity of the (already computationally intensive) TCP classifier by a factor k, it is questionable whether it is truly applicable in practice when the nonconformity function requires training.

In [START_REF] Devetyarov | Prediction with confidence based on a random forest classifier[END_REF], random forests are used to construct conformal classifiers run in the transductive mode. Rather than using the entire forest when calculating the nonconformity scores for calibration and test examples, the error of the out-of-bag prediction is used, i.e., to calculate the nonconformity score for a specific only ensemble members not trained on that particular example are considered (similar to LOOTCP). Although not explicitly stated by the authors, this effectively results in a random forest TCP that is not affected by the potential issues of strange examples being trained into the model In [START_REF] Costa | Estimating prediction certainty in decision trees[END_REF], a method for estimating the prediction certainty in decision trees, similar to conformal prediction, is proposed. The authors note that the default tree induction algorithm requires a modification for the predictions to be useful. Since the goal is to identify examples that are difficult to predict, the test instance (which is, as in TCP, included in the training data) is only allowed to affect node splitting to a limited extent, to avoid fitting strange examples into the models.

Concluding Remarks

This study shows that inductive conformal classifiers based on standard decision tree and random forest models can be more efficient than corresponding transductive conformal classifiers, while the opposite is true for support vector machines. This is contrary to the commonly accepted claim that transductive conformal predictors are by default more efficient than inductive conformal predictors. It has also been shown that to maximize the efficiency of inductive conformal classifiers, the calibration set should be kept small relative to the amount of available data (15 -30%). At the same time, if the training set is large enough, it appears favourable to let the calibration set contain at least a few hundred examples.

For future work, we suggest that transductive and inductive conformal classifiers based on other types of classification models should be compared, to provide guidelines for designing conformal classification systems. Similarly, the efficiency of specialized transductive models, such as those proposed in [START_REF] Devetyarov | Prediction with confidence based on a random forest classifier[END_REF], should be contrasted to the efficiency of standard transductive and inductive variants.

  For each dataset, stratified random samples of s = 500, 1000, ..., 4500 examples were drawn, and for each s, several ICP models were applied to the same test set of 100 examples, each ICP model using c = 100, 200, ..., s -100 calibration examples and t = s -c training examples.

Fig. 1 :

 1 Fig. 1: ICP AvgC based on portion of examples used in the calibration set. The y-axis represents a growing dataset, while the x-axis represents a growing calibration set (relative to the full dataset). Blue areas represent the most efficient combinations of training and calibration set sizes, green and yellow areas are moderately efficient, while brown areas are the most inefficient.

Table 1 :

 1 AvgC of TCP and ICP based on CART, RF and SVM, = 0.05.

			CART	RF	SVM
	dataset	#f #ex ICP TCP ICP TCP ICP TCP
	balance-scale	4 577 1.571 1.891 1.037 1.044 0.957 0.951
	breast-cancer	9 286 1.878 1.859 1.719 1.809 1.711 1.733
	breast-w	10 699 1.259 1.520 0.973 0.976 0.987 0.993
	credit-a	15 690 1.747 1.902 1.284 1.328 1.766 1.774
	credit-g	20 1000 1.845 1.902 1.548 1.596 1.821 1.849
	diabetes	20 769 1.842 1.896 1.541 1.601 1.822 1.861
	haberman	3 306 1.849 1.843 1.649 1.773 1.680 1.607
	heart-c	14 303 1.796 1.903 1.402 1.452 1.885 1.849
	heart-h	14 264 1.808 1.898 1.402 1.460 1.838 1.836
	heart-s	13 270 1.813 1.896 1.445 1.460 1.904 1.900
	hepatitis	19 155 1.821 1.885 1.400 1.350 1.844 1.820
	ionosphere	34 351 1.588 1.896 1.057 1.047 1.059 1.040
	kr-vs-kp	36 3196 0.949 1.895 0.953 0.949 1.036 1.016
	labor	16	57 1.719 1.909 1.400 1.115 1.525 1.039
	liver-disorders	7 345 1.859 1.880 1.753 1.740 1.857 1.846
	sonar	30 208 1.829 1.904 1.373 1.401 1.720 1.648
	tic-tac-toe	9 958 1.255 1.906 0.960 0.963 1.161 1.045
	sick	30 3772 0.964 1.886 0.954 0.950 1.062 1.036
	spambase	57 4601 1.370 1.549 1.021 1.028 1.050 1.052
	mean rank		1.105 1.895 1.316 1.684 1.684 1.316

Table 2 :

 2 AvgC of TCP and ICP based on CART, RF and SVM, = 0.01.

			CART	RF	SVM
	dataset	#f #ex ICP TCP ICP TCP ICP TCP
	balance-scale	4 577 1.911 1.979 1.175 1.217 1.039 1.022
	breast-cancer	9 286 1.977 1.976 1.931 1.965 1.940 1.972
	breast-w	10 699 1.843 1.589 1.178 1.187 1.256 1.228
	credit-a	15 690 1.951 1.982 1.806 1.810 1.934 1.936
	credit-g	20 1000 1.969 1.981 1.838 1.871 1.959 1.972
	diabetes	20 769 1.970 1.978 1.798 1.875 1.964 1.979
	haberman	3 306 1.971 1.959 1.894 1.936 1.935 1.922
	heart-c	14 303 1.966 1.800 1.815 1.982 1.976
	heart-h	14 294 1.963 1.980 1.814 1.821 1.950 1.933
	heart-s	13 270 1.953 1.979 1.837 1.827 1.984 1.979
	hepatitis	19 155 1.960 1.983 1.832 1.758 1.976 1.966
	ionosphere	34 351 1.917 1.974 1.589 1.454 1.543 1.330
	kr-vs-kp	36 3196 1.067 1.980 1.008 1.000 1.203 1.258
	labor	16	57 1.952 1.987 1.845 1.683 1.914 1.615
	liver-disorders	7 345 1.978 1.959 1.945 1.929 1.969 1.948
	sonar	30 208 1.968 1.980 1.804 1.672 1.922 1.872
	tic-tac-toe	9 958 1.828 1.978 1.059 1.062 1.488 1.328
	sick	30 3772 1.356 1.957 1.013 1.021 1.749 1.621
	spambase	57 4601 1.875 1.673 1.272 1.623 1.352 1.344
	mean rank		1.263 1.737 1.368 1.632 1.737 1.263

If the model is able to better predict the correct output for the training examples than the test example, then the p-values for the true targets will no longer be uniformly distributed as required by the conformal prediction framework[START_REF] Vovk | Algorithmic learning in a random world[END_REF].

Acknowledgements

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).


James Smith
email: james.smith.2009@cs.rhul.ac.uk

Ilia Nouretdinov

Rachel Craddock

Charles Offer

Alexander Gammerman

Anomaly detection of trajectories with Kernel Density Estimation by Conformal Prediction

This paper describes conformal prediction techniques for detecting anomalous trajectories in the maritime domain. The data used in experiments were obtained from Automatic Identification System (AIS) broadcasts -a system for tracking vessel locations. A dimensionality reduction package is used and a kernel density estimation function as a nonconformity measure has been applied to detect anomalies. We propose average p-value as an efficiency criteria for conformal anomaly detection. A comparison with a k-nearest neighbours non-conformity measure is presented and the results are discussed.

Introduction

Anomaly detection is a large area of research in machine learning and many interesting techniques have been developed to detect 'abnormal' behaviour of objects. The word 'anomaly' here is used in the sense that there are some patterns in the data that do not conform to typical behaviour. These non-conforming patterns are often called 'anomalies' or 'abnormalities' or 'outliers' [START_REF] Chandola | Anomaly Detection A Survey[END_REF]. Recently some new techniques known as conformal predictors (CP) have emerged which allow the detection of the non-conformal behaviour of objects using some measures of non-conformity [START_REF] Vovk | Algorithmic learning in a random world[END_REF][START_REF] Gammerman | Hedging predictions in machine learning[END_REF]. This technique also has an advantage in delivering provably valid confidence measures under the exchangeability assumption that is usually weaker than those traditionally used.

Consider, for example, a set of moving objects (vessels, vehicles, planes, etc.) z 1 , z 2 , ... and this movement might be normal (typical, conformal) or anomalous (atypical, non-conformal). We make an idealised assumption that z 1 , z 2 , ... are from the same probability distribution P on the measurable feature space X independent from each other; however no further assumptions are made about P, which is completely unknown.

In this paper, the problem of anomaly detection in the maritime domain deals with trajectories of the ships to detect suspicious behaviours: a sudden change of direction, or speed, or anchoring, etc.

There has been previous research in applying conformal prediction to anomaly detection in the maritime surveillance domain [START_REF] Laxhammar | Conformal prediction for distributionindependent anomaly detection in streaming vessel data[END_REF]. Those methods focus on nonconformity measures using nearest neighbours with Hausdorff distance or local densities of neighbourhoods with Local Outlier Factor [START_REF] Laxhammar | Sequential Conformal Anomaly Detection in Trajectories based on Hausdorff Distance[END_REF][START_REF] Laxhammar | Conformal anomaly detection: Detecting abnormal trajectories in surveillance applications[END_REF].

In this paper we experiment with two different measures of non-conformity. In particular, the nearest neighbours non-conformity measure and the kernel density non-conformity measure have been used to detect anomalies. The data was obtained from Automatic Identification System (AIS) -a tracking system for vessels that is used to broadcast the location (retrieved by a GPS receiver onboard) of a vessel over radio-waves every few seconds.

The remaining part of this paper describes some details of conformal predictors including non-conformity measures, efficiency (performance) criteria, then a dimensionality reduction package T-SNE, the description of the data and the results with discussion. In particular, we propose average p-value as a levelindependent criterion for assessing the efficiency.

Method

Conformal Prediction

Conformal prediction is a framework that allows making predictions with valid measures of confidence. Conformal Anomaly Detection (CAD) is an extension of Conformal Prediction that focuses on one-class (normal) in the unsupervised or semi-supervised setting [START_REF] Laxhammar | Sequential Conformal Anomaly Detection in Trajectories based on Hausdorff Distance[END_REF].

Conformal Anomaly Detection

Input : Non-Conformity Measure A, significance level , training objects z 1 , z 2 , ..., z n-1 and new object z n Output: P-value p n , boolean variable Anomaly

D = {z 1 , ..., z n } for i ← 1 to n do α i ← A(D \ z i , z i ) τ ← U (0, 1) p n ← |{i:ai>an}|+τ |{i:ai=an}| n if p n < then Anomaly j ← true else Anomaly j ← false
Basically, the method tests whether a new object z n might be generated by the same distribution as the previous (training) objects z 1 , . . . , z n-1 . If produced p-value p n is small, then the hypothesis of the new object's normalcy is likely to be rejected, so the abnormality is confirmed.

The significance level regulates the pre-determined level of confidence. According to the validity property [START_REF] Vovk | Algorithmic learning in a random world[END_REF], if all the data objects z 1 , . . . , z n are really generated by the same distribution, then probability that p n ≤ is at most . In the context of anomaly detection this means that if z n is not an anomaly, it will be classified as anomaly with probability at most . This allows the false positive rate to be calibrated with a significance level parameter [START_REF] Laxhammar | Conformal anomaly detection: Detecting abnormal trajectories in surveillance applications[END_REF].

Another goal is efficiency: if z n is an anomaly, we wish this to be captured by our test assigning a small p-value.

This performance depends on the selection of a Non-Conformity measure (NCM) denoted as A -that is a sort of information distance between an object and a set of the same type objects.

In this paper we use leave-one-out cross-validation to evaluate the performance. For each object a p-value is calculated using the rest of the objects as a training set. One advantage of using leave-one-out is independence on the order of data objects. Another is that it allows doing fair cross-validation using dimensionality reduction just once.

Performance Criterion

The validation of leave-one-out is done with supervised anomaly detection which has labelled anomalies and normal objects (from a testing set) where the correctness of output can be checked.

As mentioned above, the output (and the performance measure) typically depend on the significance level . Using a fixed , the more objects are classified as anomalies, the more sensitive the p-values as a test for randomness.

For supervised anomaly detection, to get an overall performance measure, independent of we adopt the well-known measure receiver operating curve (ROC) and use the-area under ROC curve (AUC) . For each value of we can produce two statistics: the percentage of normal objects classified as normal objects (that is close to 1 -by validity), and the percentage of captured anomalies. AUC is the area under the corresponding -parametrized two-dimensional curve inside the square [0, 1] 2 .

In [START_REF] Laxhammar | Conformal anomaly detection: Detecting abnormal trajectories in surveillance applications[END_REF], partial AUC (pAUC) is suggested for conformal anomaly detection, because it is important to minimise the number of false positives. pAUC only considers a subsection of the AUC, in particular false positive rate ∈ [0, 0.01] and pAUC is normalised such that its outputs are ∈ [0, 1].

Another important goal is to make the size of the prediction set as small as possible. The prediction set is the set of all the possible objects z n from the feature space such that p(z n ) ≥ . Such kind of performance measure was investigated in the context of anomaly detection by Lei et al. [START_REF] Lei | Distribution-Free Prediction Sets[END_REF].

We propose a new -independent version of this performance measure called average p-value (APV). Average p-value is the p-value of a potential new object, averaged over its location in the feature space. Its approximation can be calculated by using a finite grid of points uniformly spaced out. Every object in the grid will have a p-value calculated using a training set. The training set is fixed for each element of the grid. In the online setting it is possible to generate an APV after each iteration (using the set of normal examples as the training set). In this paper we choose to use all normal and abnormal objects in the training set to match the leave-one-out setting. We recommend using the min and max points from observed data to be used as the corners of the grid. A grid of g d cells is generated where g is the grid resolution, and d is number of dimensions of the feature space. A p-value is generated for each cell using the center point of each cell as the object to be evaluated. In this paper we use g = 100 and d = 2 to give a grid of 100x100 cells.

An alternative setting is the unsupervised anomaly detection setting which is designed for when either the data is unlabelled or no examples of anomalous objects have been provided. It considers the whole feature space as an 'ideal' testing set and considers its training set z 1 , . . . , z n-1 as normal. In this setting AUC, and pAUC are not applicable as they both require labels, however APV could be used as a criterion in this setting. In the supervised setting AUC is preferable to APV for measuring performance, but APV can still provide information on the efficiency of non-conformity measures.

Non-conformity measures

In this work we consider two non-conformity measures: the first is based on Kernel Density Estimation (KDE) and another, for comparison, on Nearest Neighbours algorithm. Lei et al. [START_REF] Lei | Distribution-Free Prediction Sets[END_REF] considered KDE as a conformity measure in the unsupervised setting.

We shall start with the Kernel Density Estimation (KDE) measure. It allows assessing non-conformity based on the density of data points. The normal objects usually are concentrated in a relatively small areas (high density areas or clusters) while anomalies will be outside of these clusters. This can be exploited by estimating a probability density function from empirical data set. A standard method to do this is to use kernel density estimation. It is a non-parametric technique that requires no knowledge of the underlying distribution.

We can interpret a density function as a measure of conformity -many similar type of data points will be located together; hence we can multiply it by minus one to convert it to a non-conformity measure for consistency.

Input : Object z i , Set of objects z 1 , z 2 , ...z n (note in this setup z i is included in the set), bandwidth h, Kernel function K, number of dimensions d Output: Non-conformity score

A A i = -1 nh d n j=1 K zi-zj h
Kernel density estimators use the previous objects with a bandwidth parameter h that specifies the width of each object.

We will treat the bandwidth uniformly in each dimension, and fixed for each object. A kernel K is a symmetric function centred around each data point. In this work we use a Gaussian Kernel function:

K(u) = (2π) -d/2 e -1 2 u T u
Lei et al. [START_REF] Lei | Distribution-Free Prediction Sets[END_REF] have carried out work extending conformal prediction to produce minimal prediction regions with the use of kernel density estimators and initially proposed KDE as a conformity measure in the unsupervised setting. Their method is underpinned by utilizing a custom bandwidth estimator that minimises the Lebesgue measure of the prediction set in the space.

We have not applied any bandwidth estimators in this paper because we wish to compare KDE with another method that also has a parameter and test performance for the parameters against multiple performance criterion.

We also apply k-Nearest Neighbour (kNN) NCM [START_REF] Laxhammar | Conformal prediction for distributionindependent anomaly detection in streaming vessel data[END_REF]: d + ij is the jth nearest distance to an object z i from other objects.

Input : Object z i , Set of objects z 1 , z 2 , ...z n , number of nearest neighbours k Output: Non-Conformity score A

A i = k j=1 d + ij
The nearest neighbour non-conformity measure was found to be useful in detecting anomalies [START_REF] Laxhammar | Conformal prediction for distributionindependent anomaly detection in streaming vessel data[END_REF] and we shall use it to compare performance with the KDE NCM.

Dimensionality reduction

The dimensionality of trajectory data is high (4N , where N is a number of points in a trajectory) and in order to apply kernel density estimation, we need to decrease the dimensionality of our data. This is achieved by applying a package called T-SNE -a dimensionality reduction system. The t-Distributed Stochastic Neighbour Embedding (T-SNE) algorithm [START_REF] Van Der Maaten | Visualizing Data using t-SNE[END_REF] is a non-deterministic and effective dimensionality reduction algorithm. It has been primarily used for visualisation but we use it to transform our data to lower-dimensional space to evaluate non-conformity measures.

In this particular application of T-SNE to trajectory data we replaced the Euclidean pairwise distance matrix with the Hausdorff distance matrix [START_REF] Laxhammar | Sequential Conformal Anomaly Detection in Trajectories based on Hausdorff Distance[END_REF], but otherwise use the standard MATLAB implementation 3 . To remind the reader that the directional Hausdorff distance -→ H (F, G) is the distance from set F to set G. H(F, G) is the symmetrical Hausdorff distance. Hausdorff uses a distance metric dist between the sets of points:

- → H (F, G) = max a∈F min b∈G {dist(a, b)} H(F, G) = max - → H (F, G), - → H (G, F )
3 Data

An object in our task is a trajectory that can be represented as a function of position over time. We convert the trajectories into a sequence of discrete 4D points (x, y, x speed , y speed ) in a similar method to [START_REF] Laxhammar | Sequential Conformal Anomaly Detection in Trajectories based on Hausdorff Distance[END_REF]. The original broadcasts are interpolated at a sampling distance of 200m. If a vessel leaves the observation area for a period of 10 minutes or more, or if the vessel is stationary for a period of 5 minutes or more we consider this as the end of a trajectory. Therefore a trajectory is a sequence of 4D Points and can have any length. The 4D points are normalised such that x, y ∈ [0, 1] and

x speed , y speed ∈ [-1, 1].
The Portsmouth dataset we evaluate was collected from a single AIS receiver on the south coast of England, during July of 2012 for one week. We filtered the data such that it only contains AIS broadcasts that report their location in a specific area between the Isle of Wight and Portsmouth. This was done to ensure consistency as the further an AIS broadcast travels the more likely it is to be lost and the data becomes less reliable.

In this dataset we consider only passenger, tanker and cargo vessels to reflect a degree of 'regular' behaviour (going from A to B and back). We assume that this data does not contain anomalous behaviour. To add anomalies we artificially inserted two sources of anomalies data points. The first contains 22 search & rescue helicopter trajectories. The other source is 180 'artificial' anomalies: random walks that have been generated starting from a random position of a random observed normal vessel. They follow a random direction and speed and a new point is generated every 200m as it has been suggested in [START_REF] Laxhammar | Conformal prediction for distributionindependent anomaly detection in streaming vessel data[END_REF]. However, unlike in [START_REF] Laxhammar | Sequential Conformal Anomaly Detection in Trajectories based on Hausdorff Distance[END_REF] we only consider the entire trajectory and do not calculate detection delay.

Instead of generating anomalous trajectories of 3km in length we are using different length of "artificial" anomalies. The composition of our 180 'artificial' trajectories is the following: 150 200m long, 20 400m long, 10 600m long, 10 800m long and 10 that are 1000m long. The aim is to diversify the difficulty by providing both easy and difficult anomalies to detect.

The dataset consists of 1124 normal trajectories with 202 anomalies added to it. All these trajectories can be seen in Fig 1.

Prior to applying conformal prediction we run the T-SNE algorithm to produce 2D representations of the trajectories.

Results

For measuring the performance of the non-conformity measures we use AUC as introduced in section 2.2. The partial AUC (pAUC) is also used to show performance for f pr ∈ [0, 0.01], note that pAUC is normalised to be in the range [0,1]. The average p-value (APV) introduced in section 2.2 is calculated, recall the lower the APV the more efficient the classifier. AUC and pAUC are our criteria for anomaly detection ability in the supervised setting and the average p-value in the unsupervised setting which doubles as a measure of efficiency. We compare both non-conformity measures for the best parameter values of AUC, pAUC and APV. The APV, AUC and pAUC for various parameter values of both NCMs can be found in the Table 1.

Table 2 was created to expand upon the k neighbours parameter as it is apparent that the highest AUC k-NN classifier was not in the initial parameter set. A rather important thing to note with testing leave-one-out is that anomalies are part of the training set, in practical applications ideally the training set would not contain anomalies. From the tables for all the parameters the highest AUC (supervised setting) are for KDE h = 3 0.7830 and kNN k = 80 0.7616, it is clear that KDE has the higher AUC, and is therefore better at detecting anomalies across all in the leave-one-out setting. For both these parameters k-NN (k = 80) also has a larger APV 0.0638 against KDE (h = 3) 0.0606 which indicates that KDE is more efficient and offers better performance than k-NN when AUC is the criterion. When we consider the most efficient APV (unsupervised setting) as a criterion k-NN's best parameter is k = 7 with APV of 0.0453 , whilst KDE's smallest APV is 0.0441 for h = 1.

The optimal result for the supervised problem requires more neighbours (k=80) than the unsupervised one (k=7) because most of the anomalies are close to each other (concentrating in a small area on Fig. 2) which makes this problem harder. At the same time their influence on the unsupervised prediction is relatively small.

The pAUC Criterion in our leave-one-out setting may not be appropriate as the number of anomalies is far greater than a 1% composition of the dataset, but it is still a vital criterion for the purpose of minimising the false positive rate. KDE's best parameter by pAUC is h = 2 with a pAUC 0.484 and k-NN's best pAUC is with k = 10 with 0.484, however with these parameters k = 10 has a smaller APV and is thus more efficient. k-NN also achieves higher pAUC for more parameter values than KDE. This is quite apparent through with pAUC > 0.03 for k = 7 to k = 20, and for k = 40 to k = 100, where as for KDE only h = {2, 7, 8} has pAUC above 0.03.

Figure 2 visualises the 'normal' class prediction sets of various for the KDE NCM. It is generated using a grid as the test set and all the objects from our dataset as the training set for each object in the grid.

Conclusions and future work

In this paper we applied conformal anomaly detection and studied applicable performance measures of efficiency. We have seen that it may be problematic to evaluate the performance of conformal anomaly detection directly because usu- ally either the amount of labelled data for testing the accuracy is small or these data are not representative enough. Therefore we propose average p-value. Average p-value is an as a performance criterion that works in both the supervised and unsupervised settings and does not require labelled anomalies to evaluate performance. At the same time, it is independent on the significance level.

However, we applied some supervised criteria as well.

As examples of NCMs, we used two methods based on the idea of density approximation. One of them is nearest neighbours (k-NN) algorithm and the other is kernel density estimation (KDE) that considers an entire trajectory to the maritime surveillance domain. In addition, we reduced the dimensionality of our dataset to compare the different non-conformity measures.

In the leave-one-out supervised setting KDE NCM for our dataset in the supervised leave-one-out setting has higher AUC than the k-NN NCM. However for most anomaly detection applications performance at small false positive rates is more important. If small false positive rate (in the form of pAUC) is the primary criterion then k-NN NCM performs better than the KDE NCM.

Going to average p-value we see that KDE can lead to more efficient predictions with a smaller average p-value than k-NN, this indicates KDE NCM in the unsupervised setting with a good choice of parameter performs better with our dataset than the k-NN NCM.

Both KDE NCM and k-NN NCM performances for all criterion are dependent on the choice of parameter h and k respectively. We included some observations related to that.

For future work, it would be interesting to continue the work using other sources of data and to reach some explanation of the noticed effects. We also plan to apply various other NCMs in search of anomalous objects.

Fig. 1 .

 1 Fig. 1. Blue shows normal trajectories. Red shows the last 200m of the artificial anomalous trajectories. The green trajectories are the helicopters .

Fig. 2 .

 2 Fig. 2. Prediction sets for various parameters of in T-SNE space for KDE NCM (h=3). The labelled colours are for various values of , the red objects are anomalies, and the teal colour is used for the normal trajectories.

Table 1 .

 1 AUC, APV and pAUC for various parameters of k-NN and KDE NCMs

	k (k-NN)
	or h (KDE)	1	2	3	4	5	6	7	8	9	10
	KDE AUC 0.6116 0.7620 0.7830 0.7455 0.6727 0.5932 0.5086 0.4406 0.3811 0.3518
	k-NN AUC 0.2977 0.3051 0.3407 0.3611 0.3894 0.4066 0.4193 0.4323 0.4466 0.4618
	KDE APV 0.0441 0.0519 0.0606 0.0694 0.0801 0.0936 0.1103 0.1307 0.1575 0.1941
	k-NN APV 0.0490 0.0481 0.0469 0.0461 0.0458 0.0454 0.0453 0.0453 0.0455 0.0456
	KDE pAUC 0.0082 0.0484 0.0285 0.0235 0.0270 0.0297 0.0415 0.0342 0.0250 0.0000
	k-NN pAUC 0.0001 0.0099 0.0099 0.0099 0.0150 0.0276 0.0340 0.0381 0.0427 0.0484
	k (k-NN)	20	30	40	50	60	70	80	90	100	110
	K-NN AUC 0.6157 0.7051 0.7257 0.7403 0.7519 0.7547 0.7616 0.6832 0.6301 0.6032
	k-NN APV 0.0486 0.0519 0.0549 0.0574 0.0595 0.0615 0.0638 0.0705 0.0827 0.0954
	k-NN pAUC 0.0304 0.0253 0.0327 0.0308 0.0400 0.0381 0.0384 0.0434 0.0375 0.0110

Table 2 .

 2 Extension of k-NN results

http://homepage.tudelft.nl/19j49/t-SNE.html

Acknowledgements James Smith is very grateful for a PhD studentship jointly funded by Thales UK and Royal Holloway, University of London. This work is supported by EPSRC grant EP/K033344/1 ("Mining the Network Behaviour of Bots"); by the National Natural Science Foundation of China (No.61128003) grant; and by grant 'Development of New Venn Prediction Methods for Osteoporosis Risk Assessment' from the Cyprus Research Promotion Foundation. We are also grateful to Rikard Laxhammar, Vladimir Vovk, Christopher Watkins and Jiaxin Kou for useful discussions. AIS Data was provided by Thales UK.


Ulf Johansson
email: ulf.johansson@hb.se

Rikard König
email: rikard.konig@hb.se

Henrik Linusson
email: henrik.linusson@hb.se

Tuve Löfström
email: tuve.lofstrom@hb.se

Henrik Boström
email: henrik.bostrom@dsv.su.se

Rule Extraction with Guaranteed Fidelity

Keywords: Rule extraction, Conformal prediction, Decision trees

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.

Introduction

When predictive models must be interpretable, most data miners will use decision trees like C4.5/C5.0 [START_REF] Quinlan | C4.5: programs for machine learning[END_REF]. 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 extracted model outputs a different label than the opaque model. Similarly, the fidelity is the proportion of test instances where the two models agree. Unfortunately, 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 represented 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 [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF], prediction sets with a bounded error are produced, 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) [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF], 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 [START_REF] Papadopoulos | Inductive conformal prediction: Theory and application to neural networks[END_REF], kNN [START_REF] Nguyen | Conformal prediction for indoor localisation with fingerprinting method[END_REF] and SVMs [START_REF] Makili | Computationally efficient svm multi-class image recognition with confidence measures[END_REF]. 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.

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 [START_REF] Andrews | Survey and critique of techniques for extracting rules from trained artificial neural networks[END_REF]. For ANN rule extraction, there are two fundamentally 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 composite rule set for the ANN. Two classic open-box algorithms are RX [START_REF] Rudy | Neurorule: A connectionist approach to data mining[END_REF] and Subset [START_REF] Fu | Rule learning by searching on adapted nets[END_REF].

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. Blackbox rule extraction is therefore an instance of predictive modeling, where each input-output pattern consists of the original input vector x i and the corresponding prediction f (x i ; θ) from the opaque model. One typical and well-known blackbox algorithm is TREPAN [START_REF] Craven | Extracting tree-structured representations of trained networks[END_REF].

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 n , 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 [START_REF] Huysmans | Using rule extraction to improve the comprehensibility of predictive models[END_REF].

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., [START_REF] Martens | Rule extraction from support vector machines: An overview of issues and application in credit scoring[END_REF]. 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 [START_REF] Zhou | Rule extraction: using neural networks or for neural networks?[END_REF], 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 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-traction is most often less prone to overfitting than standard induction, resulting in smaller and more general models.

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 [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF].

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

A( x, c ) = F (c, M (x)) (1)
where x is a vector of feature values (representing the example to be classified), c is a class label, M (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 x and a class label c is calculated in the following way:

p x,c = |{s : s ∈ S ∧ A(s) ≤ A( x, c )}| |S| ( 2
)
where S is the calibration set. The prediction for an example x, where {c 1 , . . . , c n } are the possible class labels, is:

P (x, σ) = {c : c ∈ {c 1 , . . . , c n } ∧ p x,c > σ} (3)
where σ is a chosen significance level, e.g., 0.05.

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 [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF]. 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, Mul-tiC 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 [START_REF] Asuncion | UCI machine learning repository[END_REF] or the PROMISE Software Engineering Repository [START_REF] Sayyad Shirabad | PROMISE Repository of Software Engineering Databases[END_REF].

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 α = 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. 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. 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 = 0.05, and then rises quickly to over 70% at = 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 = 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 ensemble predictions as targets for calibration. 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 = 0.10. 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 = 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.

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.

Fig. 1 .

 1 Fig. 1. Rule extraction using opaque model. Iono.

Fig. 2 .

 2 Fig. 2. Rule extraction for opaque model. Iono.

Table 1 .

 1 Accuracy, AUC and Size

		Accuracy AUC	Size	Accuracy AUC	Size
	Data set Ind. Ext. Ind. Ext. Ind. Ext. Data set Ind. Ext. Ind. Ext. Ind. Ext.
	ar1	.909 .913 .457 .608 8.0 6.3 kc1	.839 .848 .680 .595 100.0 10.8
	ar4	.817 .808 .664 .660 8.5 5.8 kc2	.827 .828 .785 .674 26.5 8.0
	breast-w .921 .928 .953 .945 20.8 15.0 kc3	.889 .903 .688 .629 25.5 4.8
	colic	.705 .717 .713 .731 34.8 21.8 letter	.824 .800 .838 .824 20.0 23.3
	credit-a .712 .751 .771 .800 57.5 32.5 liver	.578 .620 .561 .610 22.3 23.5
	credit-g .683 .712 .620 .643 108.0 51.3 mw1	.901 .917 .679 .616 15.5 4.5
	cylinder .644 .634 .630 .638 63.3 50.3 sonar	.618 .680 .657 .733 18.8 14.0
	diabetes .691 .711 .690 .684 33.3 29.5 spect	.771 .793 .699 .731 25.0 11.8
	heart-c .719 .723 .754 .773 31.0 21.8 spectf	.744 .756 .718 .691 20.3 13.0
	heart-h .760 .786 .769 .804 28.5 14.5 tic-tac-toe .770 .694 .775 .631 52.8 45.5
	heart-s .767 .748 .810 .784 31.3 17.3 vote	.899 .905 .933 .928 19.8 13.5
	hepatitis .781 .781 .746 .701 18.5 14.0 vowel	.786 .725 .804 .782 13.5 15.3
	iono	.769 .789 .732 .750 13.3 13.8 Mean	.761 .767 .719 .712 31.9 19.0
	jEdit4042 .642 .639 .669 .671 21.3 14.8 Wins	8 19 15 12	4	23
	jEdit4243 .583 .589 .606 .599 23.5 15.8

Table 2 .

 2 Conformal prediction with = 0.1. Bold numbers indicate criteria that are guaranteed by the conformal prediction framework.

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

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.

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).

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 = 0.05, OneC and AvgC will, for this significance level, produce the same ordering of the setups. 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 = 0.05, 0.084 for = 0.1 and 0.183 for = 0.2. Similarly, the averaged infidelities for RE-f are 0.035 for = 0.05, 0.084 for = 0.1 and 0.190 for = 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.


I Nouretdinov

Conformal prediction under probabilistic input

In this paper we discuss a possible approach to confident prediction from data containing missing values presented in a probabilistic form. To achieve this we revise and generalize the notion of credibility known in the theory of conformal prediction.

Introduction

The task of machine learning is to predict a label for a new (or a testing) example x l+1 from a given training set of feature vectors x 1 , x 2 , . . . , x l supplied with labels y 1 , y 2 , . . . , y l . The conformal prediction technique introduced in [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF] and had many applications and extensions later. It allows to make a valid confident prediction.

Originally it was introduced for supervised machine learning problem with clear data structure. But in many practical problems data representation may be complex and combine multiple sorts of information. The conformal prediction was extended in previous works. In [START_REF] Adamskiy | Conformal prediction in semi-supervised case[END_REF], it was semi-supervised learning when only some examples are presented with labels. In [START_REF] Nouretdinov | Determining Confidence of Predicted Interactions Between HIV-1 and Human Proteins Using Conformal Method[END_REF] training labels were available only for one of two classes. In [START_REF] Lei | Efficient Nonparametric Conformal Pre-diction Regions[END_REF] an unsupervised learning problem of anomaly detection was considered. Another kind of the task is Vapnik's Learning under privileged information [START_REF] Vapnik | A new learning paradigm: Learning using privileged information[END_REF] that can be interpreted as having missing values in testing examples. A conformal approach to it was made in the work [START_REF] Yang | Learning by Conformal Predictors with Additional Information Proceedings of The 9th Artificial Intelligence Applications and Innovations Conference[END_REF].

The direction presented here is probabilistic representation of feature vectors or labels. Assume that there is kind of a priori distribution on features and/or labels. For example it is concentrated at one value when a feature is presented, it is uniform when it is completely missing, and other distributions are applicable when it is known partially or hypothetically. This means neither to try to exclude examples with missing values nor to fill them in a unique way.

An approach to this task is based on the notion of credibility that appears in the standard (supervised) conformal prediction. Unlike the confidence assigned to a likely hypothesis about the new example's label, the credibility answers the question whether any of these hypotheses is true at all. So the credibility is a characteristic of an unfinished data sequence, that includes a new example without its label. This can be naturally extended to the task when some part of training information is missing.

As an area of application needed for an illustration of the proposed method, we take LED data set from UCI repository [2], because a priori distribution on the values has a clear sense for these data.

Machine learning background 2.1 Conformal prediction

Let us remind the properties of conformal prediction (in the case of classification) according to [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF]. Assume that each data example z i consists of x i that is an m-dimensional vector x i = (x i1 , . . . , x im ) and a label y i that is an element of a finite set Y .

Conformal predictor in supervised case assigns p-value (the value of a test for randomness) to a data sequence p(y) = p((x 1 , y 1 ), . . . , (x l , y l ); (x l+1 , y))

= card{i = 1, . . . , l + 1 : α i ≥ α l+1 } l + 1
where x 1 , . . . , x l ∈ X are feature vectors of training examples with known classifications y 1 , . . . , y l ∈ Y , x l+1 is a new or testing example with a hypothetical label y, and

α i = A ({(x 1 , y 1 ), . . . , (x l , y l ), (x l+1 , y)}, (x i , y i ))
for a nonconformity measure A that is a strangeness function of a set of labeled feature vectors and one of its elements.

The plan is to check each possible hypothesis about the label of a new example, and to the label of new example would conform the assumption of exchangeability, or with which label the example 'fits well' into the training set? The prediction set consists of satisfactory hypotheses y such that p(y) exceeds a significance level γ. The calculations of prediction regions are based on a special function called nonconformity measure (NCM) that reflects how strange an example is with respect to others. Then p-value is assigned to each There are two ways to present the results. One of them is the prediction set: a list of y which meet this confidence requirement p(y) ≥ γ. The validity property implies that the probability of error is at most 1γ whenever the i.i.d. assumption is true. Here an error means true value of y n being outside the prediction set.

Alternatively we can provide the prediction of a new label together with measures of its individual confidence. The correspondence between two types of output is that the confidence is the highest confidence level at which the prediction region consists of (at most) one value. In terms of p-values assigned to different labels, the confidence is a complement to 1 of the second highest p-value.

An individual prediction is also naturally completed with credibility that is the first highest p-value. If the credibility is low this means that any existing hypothesis about the label of the new object is unlikely. In other words, the new object itself is not credible enough as a continuation of the data sequence, and this could be said before its label is known. So it can be understood as dealing with an unknown testing label.

Our aim is to extend this idea, dealing other sort of incomplete information in analogous way.

Standard credibility

In this work we call credibility a measure of conformity of an incomplete data sequence.

Originally it was applied to the data sequences of the following type:

(x 1 , y 1 ), . . . , (x l , y l ), x l+1 .

with y l+1 missing.

The credibility is obtained by maximization conformal p-values over all its possible completions:

p cred ((x 1 , y 1 ), . . . , (x l , y l ), x l+1 ) = max y l+1 ∈Y p((x 1 , y 1 ), . . . , (x l , y l ), (x l+1 , y l+1 )).
The validity property of conformal prediction regions can be easily extended to the credibility. If a data sequence (x 1 , y 1 ), . . . , (x l+1 , y l+1 ) is generated by P = P l+1 1 where P 1 is a distribution on X × {0, 1}, then

P {p cred ((x 1 , y 1 ), . . . , (x l , y l ), x l+1 ) ≤ γ} ≤ γ for any γ ∈ (0, 1).
In this form it was assumed that the incomplete sequence is obtained from the complete one by forgetting y l+1 . In other words it could be said that the incomplete sequence (x 1 , y 1 ), . . . , (x l , y l ), y l+1 is generated by P l × P X where P X is the marginal distribution of the feature vector averaged over Y .

Extensions of credibility

As we have seen, the standard credibility is the p-value (test for randomness) assigned to an incomplete sequence of examples. Incompleteness means there that the label of the last example is totally missing.

Sometimes a similar aproach can be applied to other kinds of missing values. A close problem is having an unknown feature (not a label) of a new (testing) example. This task is equivalent to learning under privileged (additional) information framework formulated in [START_REF] Vapnik | A new learning paradigm: Learning using privileged information[END_REF]. The conformal approach of this task was developed in the work [START_REF] Yang | Learning by Conformal Predictors with Additional Information Proceedings of The 9th Artificial Intelligence Applications and Innovations Conference[END_REF]. An analogue of credibility was assigned to the sequence

(x 1 , x * 1 , y 1 ), . . . , (x l , x * l , y l ), (x l+1 , y)
with x * l+1 unknown. The feature x * was called privileged bacause it is available for the training examples.

Next step might be related to missing values in training examples. But a straightforward approach to this task (maximizing p-value over possible fillings of the gap) is not effective because the conformal predictor concentrates on the conformity of the testing example without checking training examples for strangeness. Therefore we would like to consider missing values as distributions.

For convenience of presentation, in this section we will start form the case of unclear information about binary labels y i presented in a probabilistic form of a priori distribution. Then we will show how to apply it in a more general case.

Task and assumptions

Suppose that Y = {0, 1}, but some information about y 1 , . . . , y l is missing. However, for each i = 1, . . . , l we know that p i has a meaning of probability that y i = 1. As for y l+1 , we assume that it is known as a hypothesis according to the conformal prediction procedure.

How to state this task in a well-defined way and what would be a proper analogue of the i.i.d. assumption in this case?

A mechanism should generate both the 'true' data sequence (including hidden values of y i ) and the 'visible' one (with probabilistic values p i ). This means that the triple (x i , y i , p i ) is generated simultaneously. But some agreement between p i and y i is also needed so that probabilistic values p i make sense as probabilities.

To define this formally, assume that P 1 is a distribution on X × (0, 1) and Θ is the uniform distribution on (0,1). First, P = (P 1 ×Θ ) l+1 generates (x 1 , p 1 , θ 1 ), . . . , (x l+1 , p l+1 , θ l+1 ).

Setting y i = 1 if p i < θ i and y i = 0 otherwise, we can also say that P * generates a sequence of triples (x 1 , p 1 , y 1 ), (x 2 , p 2 , y 2 ), . . . , (x l+1 , p l+1 , y l+1 ) where p i is 'visible' label and y i is the 'hidden' one, y i is stochastically obtained from p i .

Special credibility

In order to make a conformal prediction of y l+1 for x l+1 we need to consider different hypotheses about it. When a hypothesis is chosen, we work with 'visible' labels p 1 , . . . , p l for training examples and for a 'hidden' value y l+1 for the new one. Thus the task is to assign a valid credibility value for a sequence (x 1 , p 1 ), . . . , (x l , p l ); (x l+1 , y l+1 ).

Fix a parameter s > 0 called allowance which is a trade-off between testing the hypothetical new label with respect to a version of the training data set, and testing the training data set with respect to a priori distribution on missing values.

Suppose that Q is the conditional distribution of p((x 1 , y 1 ), . . . , (x l , y l ), (x l+1 , y l+1 )) given (p 1 , . . . , p l ) and y l+1 , q 0 = q 0 (p 1 , . . . , p l ) is the smallest q such that Q{p > q|p 1 , . . . , p l ; y l+1 } ≤ s and p cred = p cred ((x 1 , p 1 ), . . . , (x l , p l ); (x l+1 , y l+1 )) = q 0 (p 1 , . . . , p l ; y l+1 ) + s.

Proposition 1. Assume tgat (x 1 , p 1 ), . . . , (x l , p l ) and (x l+1 , y l+1 are generated by the mechanism described in Section 3.1 and p cred us calculated as in Section 3.2, then P{p cred ≤ γ} ≤ γ for any γ ∈ (0, 1).

Proof: Recall that p = p(y 1 , . . . , y l ) > q = q(p 1 , . . . , p l ) with probability at most s for any given p 1 , . . . , p l . On the other hand, p is valid as a standard conformal predictor's output thus p ≤ γs with overall probability at most γs. Therefore γs < p < q with probability at least 1s -(γs) = 1γ and probability that q + s < γ is bounded by γ.

Missing values in features

For convenience of presentation we earlier assumed that the labels y 1 , . . . , y l are given in probabilistic form, although this can be extended to the objects x 1 , . . . , x l as well.

So let us now assume that P * generates (H i , x i , y i ) where 'visible' H i is a distribution on X, while 'hidden' x i ∈ X is randomly generated by H i .

If x i is known clearly, this means that H i is a distribution concentrated at one point. Otherwise H i can be understood as an a priori distribution on its missing values. If X is discrete, then H i can be presented in a vector form.

The extended credibility is defined by analogy. Suppose that Q is the conditional distribution of p((x 1 , y 1 ), . . . , (x l , y l ), (x l+1 , y l+1 )) given (H 1 , . . . , H l , H l+1 ) and a fixed y l+1 , q 0 is the smallest q such that Q{p > q|H 1 , . . . , H l+1 ; y l+1 } ≤ s and p cred ((H 1 , y 1 ), . . . , (H l , y l ), (H l+1 , y l+1 )) = q 0 + s.

Obviously an analogue of Proposition 1 is also true in this case.

Efficient approximation

To find q 0 exactly one has to know the condition distribution of p given 'visible' data.

For the aims of computational efficiency this distribution can be replaced with an empirical one, using Monte-Carlo approximation. Let H 1 ×H 2 ×H l+1 generate a large amount of vectors (x 1 , . . . , x l+1 ) and calculate conformal p-value for each of them. Then we will get an empirical distribution of p that allows to estimate q 0 by sorting these p-values and taking one with corresponding rank. An example will be given in Section 4.3.

Experiments

For the experiments we use benchmark LED data sets generated by a program from the UCI repository[2]. LED means light emitting diode electronic display. A LED image of a digits has of 7 binary features (pixels). The task is to predict a digit from an image in the sevensegment display. Each of digits 0, 1, . . . , 9 has a canonical image that should normally represent it. Few examples are presented on Fig. 1.

Assume now that visible displays can contain mistakes. Each pixel can occasionally show 'on' instead of 'off' or vice versa with probability p 0 . For our example we assume that p 0 = 0.1 although normally it is much less. The data generating program first randomly selects a canonically represented digit then each of the attributes is inverted with a probability of noise p 0 and the noisy example is added to the data set.

In the work [START_REF] Fedorova | Conformal prediction under hypergraphical models[END_REF] the conformal approach was applied to LED data in its standard supervised form. Now we make some changes in the data statement. First, the probability p 0 itself is known for us. T his means that all values in the training set are probabilistic ones. When we see that a pixel is 'on' this in fact means that it is on with probability 1p 0 and 'off' with p 0 , and vice versa. Second, in the testing examples there are no mistakes (as if p 0 = 0). The task is to classify a testing example with full information after training on the examples with probabilistic information. It is assumed that the canonical representations are not available for the learner, who has to make predictions based only on the examples with possible mistakes as they are presented in the data.

For experiments we generate some amount of LED digits. The number and distribution (frequency) of labels (0,1,2,. . . ,9) is not restricted, we borrow it from well-known USPS (US Postal Service) benchmark data set in order to have imbalanced classes. Size of the classes is shown in Table 1.

Class label (digit) 0 1 2 3 [START_REF] Vapnik | A new learning paradigm: Learning using privileged information[END_REF] For a training example, given a label, we take its canonical LED image and make an error in each of the feature with probability γ. In the most of experiments γ = 0.1 unless stated another.

Testing examples are not probabilistic by the task, so in principle we can make predictions on 2 7 = 128 possible images. This number includes 10 canonical images of digits.

Later we will consider two types of testing set. A proper one is generated with the same distribution on classes as the training set and therefore contains only canonical images. An auxiliary testing set contains all the possible images.

Nonconformity measure

For convenience we use one of the simplest NCM that can be applied. As the space is discrete, NCM of an example with respect to the set of another ones is defined as the number of 'zero distance other class neighbors', i.e. number of examples in the set that have the same features but in fact belong to another class: α i = A ({(x 1 , y 1 ), . . . , (x l , y l ), (x l+1 , y)}, (x i , y i )) = card{ j : x i = x j , y i = y j }.

Probabilistic values of the features

We apply our approach in its form mentioned in Section 3.3. All the features of X are binary and we assumed that the mistakes in features are done independently of each other. The connection between a 'hidden' vector x = (x(1), . . . , x( 7)) ∈ X = {0, 1} 7 and a corresponding 'visible' distribution H is the following. H is a distribution on X such that:

x(1), . . . , x( 7) are H-independent on each other; for each j = 1, . . . , 7, H{x( j) = 1} is either 1p 0 or p 0 ; a mistake x( j) in a feature x( j) is done with probability γ; if there is no mistake in x( j) then H{x( j

) = 1} = 1 -γ if x( j) = 1, γ if x( j) = 0; -if there is a mistake in x( j) then H{x( j) = 1} = γ if x( j) = 1, 1 -γ if x( j) = 0.
This means that in the 'visible' features vectors all the features are probabilistic. Each of the features is either 1 with probability 1γ, 0 with probability γ or 1 with probability γ, 0 with probability 1γ.

Other details

Following 3.2 we set the 'allowance' coefficient to s = 0.01. Following the note 3.4 we avoid scanning all possible combinations by calculating p-values as Monte-Carlo approximations. the number of trials is 1000. Further we will see that this approximation does not affect validity properties.

Summarizing, there were 1000 trials (i.e. random filling of the missing values), and consider as the approximate credibility p cred the 10-th largest of these p-values plus the allowance s = 0.01.

Remind that p cred finally is the p-value assigned to a new example (x l+1 , y l+1 ).

To check the validity we wish to check what p-value is assigned to the true hypothesis about y l+1 . The correspoding p cred is called p true .

If y l+1 is unknown then each possible hypothesis about its value should be checked and assigned a p-value. As well as in the standard conformal predictor, the prediction is the hypothesis with the largest p-value and confidence in it is 1 minus the second largest p-value.

Validity

According to our problem statement, the validity is checked on testing examples that do not contain uncertainty and have the same distribution as the training examples before introducing mistakes. Therefore, each of the testing examples is one of ten digits (y ∈ {0, 1, . . . , 9}) presented with its canonical image x. In order to satisfy i.i.d. assumption with training set, the distribution of ten types also corresponds to one from USPS data.

The corresponding validity plot is presented on Fig. 2. It show that the probability of error (true value being outside the prediction set) does not exceed the selected significance level, for example: P{p true ≤ 0.16} = 0.08; P{p true ≤ 0.27} = 0.17.

The validity is satisfied with some excess. The same effect is known for the standard credibility and for LUPI due to involving incomplete information into the data.

Confidence

Recall that the testing set consists only of canonical images, so there are only 10 possible different configurations.

Individual confidences for them can be seen on Fig. 5.2 (boxed items), average value is 0.87. The smallest of these confidences is 0.79 assigned to the digit 7, because this digit is mixable with 1 (Hamming distance between them is the smallest) and relatively rare in the training set.

For comparison we also included confidence values that would be assigned to all 128 possible pixel combinations (auxiliary testing set) and they are much lower (0.18 in average).

The more indefinite the data are the smaller is the achieved level of confidence. For example, if we increase the probability of mistake from p 0 = 0.1 to p 0 = 0.2 then the figures of average confidence falls down to 0.55 and 0.11 respectively. In this work we formulated an approach to get confident prediction from the data with missing values (or labels) presented in a probabilistic form. Probabilistic input means that there is an a priori distribution on possible filling of these missing values.

The advantages of conformal approach for this task are not ignoring examples with incomplete information, and on the other hand not wasting time attempting to restore the missing values.

The missing features are taken as a priori distributions on their possible values. This is an analogue of Bayesian distribution on a parameter of a statistical model. So we can expect as well that it might be assumed in other practical problems with incomplete information.

Fig. 1 .

 1 Fig. 1. Canonical images of 7,8,9 in LED data.

Fig. 2 .

 2 Fig. 2. Validity plot

Fig. 3 .

 3 Fig. 3. Predictions for all possible pixel combinations. Predictions for the canonical images are put in boxes.

Table 1 .

 1 Size of different training classes

	5 6 7 8 9 Total

Acknowledgments

This work was supported by EPSRC grant EP/K033344/1 ("Mining the Network Behaviour of Bots"); by Thales grant ("Development of automated methods for detection of anomalous behaviour"); by the National Natural Science Foundation of China (No.61128003) grant; and by grant 'Development of New Venn Prediction Methods for Osteoporosis Risk Assessment' from the Cyprus Research Promotion Foundation.

We are grateful to Judith Klein-Seetharaman and Alex Gammerman for motivating discussions.