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

HAL
open science

# Distance Metric Learning-Based Conformal Predictor

Fan Yang, Zhigang Chen, Guifang Shao, Huazhen Wang

► To cite this version:

Fan Yang, Zhigang Chen, Guifang Shao, Huazhen Wang. Distance Metric Learning-Based Conformal Predictor. 8th International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2012, Halkidiki, Greece. pp.254-259, 10.1007/978-3-642-33412-2_26 . hal-01523097

HAL Id: hal-01523097

https://hal.science/hal-01523097

Submitted on 16 May 2017

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Distance Metric Learning-based Conformal Predictor

Fan Yang¹, Zhigang Chen¹, Guifang Shao¹, Huazhen Wang²

¹Department of Automation, Xiamen University, Xiamen, 361005, China

²School of Computer Science and Technology, Huaqiao University, Xiamen, 361021, China

**Abstract.** In order to improve the computational efficiency of conformal predictor, distance metric learning methods were used in the algorithm. The process of learning was divided into two stages: offline learning and online learning. Firstly, part of the training data was used in distance metric learning to get a space transformation matrix in the offline learning stage; Secondly, standard CP-KNN was conducted on the remaining training data with a nonconformity measure function defined by K nearest neighbors classifier in the transformed space. Experimental results on three UCI datasets demonstrate the efficiency of the new algorithm.

**Keywords:** conformal predictor; distance metric learning

## 1 Introduction

Most of the machine learning algorithms neglect or even ignore the reliability of the classifications and predictions. The conformal predictor (CP) algorithm focuses on the reliability and confidence of classification and provides a predefined confidence level for each prediction [1]. What's more, the CP algorithm is online by nature, so the CP algorithm has great superiority in practical applications [2-4].

In previous studies, K nearest neighbors (KNN) classifier was often used to design the nonconformity measure function for CPs, which is known as CP-KNN algorithm [6]. There are some disadvantages in CP-KNN [8]. Firstly, the nonconformity measure function of CP-KNN is designed in the original space, but the distance metric in the original space can't adapt to most of the practical problems. Secondly, the distance metric is difficult to determine, and Euclidean distance and other distance are not good for many classification problems. Thirdly, it needs to store large amounts of historical data, and frequently search and access the database, so it will cost a lot of time. Especially, when the data sets are huge, the calculation is intolerable in many practical applications.

There are some existing versions of CPs aiming to improve its computational efficiency, e.g. offline learning transductive confidence machine [5], which is conducted in an offline manner. However, in offline learning, the calibration of CPs can not be guaranteed theoretically. In [7,9], Wang HZ and Yang F et al. proposed a hybrid compression CP which used random forest to learn a proximity matrix on part of training data and apply CP-KNN in an online learning manner on the remaining data in the sample space defined by the random forest proximity matrix. Hence the compu-

This work was partially supported by the Fundamental Research Funds of China for the Central Universities under Grant No. 2010121065 and the Research Grant Council of Huaqiao University with Project No.09BS515.
tational efficiency was improved through the transfer of the online learning computa-
tional cost to the offline learning. Further, Yang F et al. propose to use adaptive ker-
nel learning on part of the training data and also got both high predictive efficiency
and computation efficiency on a fault detection dataset [8]. Different from [10], which
use Multiple Kernel Learning (MKL) methodology to maximize efficiency in the CP
framework, the above work mainly focused on improving the learning framework of
CPs by dividing the learning process into two parts: offline learning and online learn-
ing. And this learning strategy can also be viewed as Mondrian CPs according to [1].

In this paper, we further present the distance metric learning based Conformal Pre-
dictor. Identically, the learning process was divided in to two stages. In the offline
learning section, we used part of the training data sets to get a space transformation
matrix by distance metric learning methods [11-13], and then design the nonconfor-
mity measure function with KNN and apply online CP-KNN in the new space.

## 2 Conformal Predictor

Conformal predictor (CP) is a transductive confidence machine (TCM) based on Kolmogorov randomness theory and conducted in online scheme. When one testing example is coming, we assume the example belongs to every possible class, and get several new test sequences. Randomness test is then applied to every test sequence. If the randomness level of a new sequence is relatively high, the corresponding class may be the true label of the testing example. CP treats all the classes whose randomness levels are greater than the specified risk level as prediction results. So CP is region prediction rather than point prediction of the traditional machine learning algorithms [1]. The key problem of the CP algorithm is the design of nonconformity measures for examples, which is the degree of a testing example consistent with each class's distribution.

3 Distance Metric Learning Algorithms

The KNN rule works well in the design of nonconformity measure in CPs. However
the performance of KNN depends crucially on the distance metric. The performances
of the KNN could vary greatly on different distance metrics. Usually, Euclidean dis-
tances are used as a similarity measure, which is not always the case in most applica-
tions. And the distance metric should adapt to the particular applications. We ex-
pected that the nonconformity measure with KNN could be more effective in a space
learned from the training set. In this paper, we used three distance metric learning
methods to get the space transformation matrix. The methods are Large Margin Near-
est Neighbors Classifier (LMNN) [11], Discriminative Component Analysis (DCA)
[12] and Local Fisher Discriminant Analysis (LFDA) [13].
## 4 Distance Metric Learning-based Conformal Predictor Algorithm

In this paper, the process of learning is divided into two stages: offline learning and online learning. And the training data set is also randomly divided into two parts: compressed data set and calibration data set.

(i) Offline learning. In the original space, the compressed data set is used with Distance Metric Learning methods (LMNN, LFDA and DCA) to get a space transformation matrix (M). The purpose of this stage is to reduce storage size and the online computational cost by compressing part of the training data into knowledge.

(ii) Online learning. We get a new data space from offline learning stage. The transformation matrix not only increases the class separability of the compressed data set, but also increases the class separability of the calibration data set and the testing data set. The nonconformity measure function which is designed by KNN in the new space will be more effective.

The nonconformity measure function can be defined in the new space as:

$$ \alpha_i := A_i([Z_1, \dots, Z_{i-1}, Z_{i+1}, \dots, Z_n], M), i = 1, \dots, n-1 \quad (1) $$

$$ \alpha_n := A_n([Z_1, \dots, Z_{n-1}], M) $$

where $Z_n$ is a testing example and M is the linear transformation matrix. $A_i$ is the nonconformity measure function.

And the output of the prediction:

$$ \Gamma^{\epsilon}(Z_1, \dots, Z_{n-1}, x_n) = \{y \in Y : p = |(i = m_k + 1, \dots, n : \alpha_i \ge \alpha_n)| / n > \epsilon\} \quad (2) $$

The nonconformity measure score was calculated as:

$$ \alpha_i = \frac{\sum_{j=1}^{k} \theta_{ij}^{-y}}{\sum_{j=1}^{k} \theta_{ij}^{y}}, i = m_k + 1, \dots, n, j \neq i \quad (3) $$

Where $\sum \theta_{ij}^{-y}$ denotes the proximity sum of the k nearest neighbors whose class label are not y, and $\sum \theta_{ij}^{y}$ denotes the proximity sum of the k nearest neighbors whose class label are y.

### Algorithm 1. Distance Metric Learning-based Conformal Predictor

Input: $(x_1, y_1), \dots, (x_{n-1}, y_{n-1})$, testing data $x_n$, k, and the risk level $\epsilon$;

Output: the region prediction $\Gamma^{\epsilon}$ of $x_n$.

Step 1. The compressed data set is used with Distance Metric Learning methods to get a space transformation matrix (M);

Step 2. The calibration data set is put into the new space by the space transformation matrix (M);

Step 3. Initialize the region prediction set and the calibration data set:

$$ \Gamma^{\epsilon} = \Phi, $$

$$ V = \{(x_{m+1}, y_{m+1}), \dots, (x_{n-1}, y_{n-1})\}; $$
Step 4. For test example $x_n$, assume every class label $y \in \{1,2,...,c\}$ as its label, and calculate the nonconformity score of each assumption with Eq. (15). If the random level (p) of the nonconformity scores sequence is larger than the risk level ($\varepsilon$), $\Gamma^\varepsilon = \Gamma^\varepsilon \cup y$.

Step 5. Get the true class label ($y_n$) of $x_n$, and add $x_n$ to the calibration data set $V = V \cup \{x_n, y_n\}$.

In our experiments we set $k=3$, $\varepsilon = 80\%,95\%,99\%$ respectively.

# 5 Experiment Results

We call the Distance Metric Learning-based Conformal Predictor Algorithms as CP-LMNN, CP-LFDA and CP-DCA respectively. We compared our new algorithms with CP-KNN on three UCI data sets, i.e., SPAM E-mail Database, the Pen-Based Recognition of Handwritten Digits and the Thyroid disease [14].

Four evaluation indicators are used, i.e., certain prediction rate, certain and correct prediction rate, empty prediction rate and exact calibration. The certain prediction rate means the rate of the region predictions which only have one class label. The certain and correct prediction rate denotes the rate of the region predictions which only have one label and the label is just the true class label. The empty prediction rate denotes the rate of the region predictions which have no elements.

Results on SPAM E-mail Database are showed in Fig.1. The results on the other two datasets are similar to Fig.1. And the certain and correct prediction rate are shown in Table 1. The experiments were performed on a laptop machine with a 2.1 GHz core 2 processor. In order to compare the computational efficiency, the CPU time for each experiment is listed in Table 2.

Table 1 shows that the certain and correct prediction rate of the new methods are better than CP-KNN at most confidence levels. The rate of region predictions which only have one label is improved, and most of the predictions are just the true class labels of the testing data. And the average degree of similarity of certain and correct prediction rate and certain prediction rate are also better.

From Table 2 we can see that the time costs of our method on all data sets are less than CP-KNN. Note that, the larger of the compressed data set, the CPU times of CP-LMNN will be less. The compressed data is used in offline learning and would not influence the computation efficiency of online learning. In contrast, as the number of historical data increases, CP-KNN will be very time-consuming. So the new algorithm is suitable for the online learning of huge data sets.

# 6 Conclusions

In this paper we propose a distance metric learning based conformal predictor. The new algorithm works well in improving the computational efficiency of CP. And at the same time, the predictive efficiency is also improved by some degree.
<figure><img src="image_3.png" /><figcaption>Fig. 1. The predictive efficiency on Spam E-mail Database, (a)CP-LMNN (b)CP-DCA (c)CP-LFDA (d)CP-KNN</figcaption></figure>

<table><caption>Table 1. The Comparison of the predictive efficiency*</caption><thead><tr><th></th><th>CL(%)</th><th>0.1</th><th>0.3</th><th>0.5</th><th>0.7</th><th>0.8</th><th>0.9</th><th>Cc/c</th></tr></thead><tbody><tr><td rowspan="4">Spam E-mail</td><td>KNN</td><td>3.6</td><td>19.49</td><td>30.6</td><td>43.37</td><td>53.86</td><td>69.86</td><td>86.58</td></tr><tr><td>LMNN</td><td>10.77</td><td>25.99</td><td>42.71</td><td>60.44</td><td>73.32</td><td>87.04</td><td>96.46</td></tr><tr><td>LFDA</td><td>6.81</td><td>20.53</td><td>36.68</td><td>61.74</td><td>75.12</td><td>58.25</td><td>89.66</td></tr><tr><td>DCA</td><td>9.11</td><td>27.56</td><td>47.4</td><td>67.67</td><td>62.82</td><td>43.83</td><td>79.41</td></tr><tr><td rowspan="4">Hand-written</td><td>KNN</td><td>4.33</td><td>27</td><td>46.53</td><td>66.8</td><td>75.93</td><td>86.4</td><td>99.95</td></tr><tr><td>LMNN</td><td>11.67</td><td>33.73</td><td>53.47</td><td>72.8</td><td>82.73</td><td>91</td><td>99.86</td></tr><tr><td>LFDA)</td><td>10.07</td><td>31.87</td><td>55.47</td><td>75.47</td><td>84.2</td><td>92.2</td><td>99.32</td></tr><tr><td>DCA</td><td>10.8</td><td>31.13</td><td>52.2</td><td>71.8</td><td>82.2</td><td>92.33</td><td>99.41</td></tr><tr><td rowspan="4">Thyroid</td><td>KNN</td><td>11.5</td><td>28.33</td><td>50.09</td><td>69.11</td><td>79.1</td><td>87.64</td><td>92.67</td></tr><tr><td>LMNN</td><td>10.52</td><td>29.59</td><td>52.55</td><td>74.98</td><td>84.2</td><td>81.65</td><td>95.14</td></tr><tr><td>LFDA)</td><td>10.52</td><td>30.17</td><td>54.07</td><td>75.33</td><td>84.15</td><td>73.68</td><td>93.45</td></tr><tr><td>DCA</td><td>9.71</td><td>30.48</td><td>53.22</td><td>75.16</td><td>84.42</td><td>72.11</td><td>93.02</td></tr></tbody></table>

<footnote>*CL: confidence level; Cc/c: certain and correct prediction rate/certain prediction rate</footnote>
<table><caption>**Table 2.** The Comparison on the Time Cost*(s)</caption><thead><tr><th>Dataset</th><th>N</th><th>CM</th><th>CA</th><th>TE</th><th>Attribute</th><th>LMNN</th><th>LFDA</th><th>DCA</th><th>KNN</th></tr></thead><tbody><tr><td>E-mail</td><td>4601</td><td>1000</td><td>1000</td><td>2601</td><td>58</td><td>4697</td><td>4139</td><td>3987</td><td>7409</td></tr><tr><td>Hand-written</td><td>4500</td><td>2000</td><td>1000</td><td>1500</td><td>17</td><td>5849</td><td>6257</td><td>6437</td><td>15778</td></tr><tr><td>Thyroid</td><td>4534</td><td>1150</td><td>1150</td><td>2234</td><td>22</td><td>9126</td><td>8833</td><td>9442</td><td>16873</td></tr></tbody></table>

*N : the number of examples used in the experiments; CM (compressed): the number of training data used for distance metric learning; CA (calibration): number of remaining training data used for online learning. TE :the test data.

## References

1. Vovk, V., Gammerman, A., Shafer, G.: Algorithmic learning in a random world. Springer, New York (2005).

2. Gammerman, A., Vovk, V.: Prediction algorithms and confidence measures based on algorithmic randomness theory. Theoretical Computer Science. 287,209-217(2002).

3. Gammerman, A., Vovk, V.: Hedging predictions in machine learning. Computer Journal. 50,151-177(2007).

4. Vovk, V.: A Universal Well-Calibrated Algorithm for On-line Classification. J. Mach. Learn. Res. 5,575-604(2004).

5. Stijn, V., Laurens, V.D.M., Ida S.K.: Off-line learning with transductive confidence machines: an empirical evaluation. In: Petra Perner (eds.), LNAI, vol.4571, pp.310-323, Leipzig, Germany, Springer(2007)

6. Papadopoulos, H., Vovk, V., Gammerman, A.: Regression Conformal Prediction with Nearest Neighbours. J. Artif. Intell. Res. 40, 815-840(2011)

7. Wang H.Z., Lin C.D., Yang F., Zhuang J.F. An online Algorithm with confidence for Real-Time Fault Detection. Journal of Information and Computational Science, 6(1),305-313 (2009)

8. Yang F., Luo J., Wang H.Z., Peng Y.Q., Mi H. Optimized Kernel-Based Conformal Predictor for Online Fault Detection. Journal of Tianjin University, 42(7), 614-621(2009)

9. Yang, F., Wang, H.Z., Mi, H., Lin, C.D., Cai, W.W. Using random forest for reliable classification and cost-sensitive learning for medical diagnosis. BMC Bioinformatics, 10, S1(2009)

10. Balasubramanian, V., Ye, J., Chakraborty, S., Panchanathan, S. Kernel Learning for Efficiency Maximization in the Conformal Predictions Framework. In: 9th International Conference on Machine Learning and Applications, Washington DC(2010)

11. Kilian, Q., Weinberger, Lawrence, K., Saul. Distance Metric Learning for Large Margin Nearest Neighbor Classification. J. Mach. Learn. Res.10,207-244(2009)

12. Peltonen, J., Goldberger, J., Kaski, S. Fast discriminative component analysis for comparing examples. Learning to Compare Examples-NIPS 2006 Workshop, 12(2006)

13. Masashi, S. Dimensionality Reduction of Multimodal Labeled Data by Local Fisher Discriminant Analysis. J. Mach. Learn. Res. 8, 1027-1061(2007)

14. Frank, A., Asuncion, A. UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science.