Transduction with Confidence and Credibility

1 Introduction

In this paper, we describe a new method of transduc­ tive inference using Support Vector machines [Vapnik, 1995]. Whereas induction tries to learn a general rule (e.g. of classification) from a given training set, trans­ duction reasons from particular to particular. That is, instead of trying to obtain a general rule, the learning process is focussed on obtaining the classification of a single new example, or given set of new examples. In sec­ tion 3 we introduce a method of transduction based on a Support Vector (SV) machine which uses the statistical measure of p-values. By measuring p-values the algo­ rithm gives confidence values for each of its predictions. The method also provides a credibility measure based on the p-values for different predictions. These mea­ sures can be interpreted as an indication of the quality of our prediction. The performance of the new algorithm is then compared to two other techniques (which simply give flat predictions, and no measure of confidence or credibility), viz. a standard Support Vector Machine, and Vapnik's margin transduction.

Results show that the transductive method presented here is comparable to, and sometimes exceeds the performance of the other two methods, whilst providing the additional information of confidence and credibility val­ ues for its prediction. Our trasnductive algorithm there­ fore gives us the best of both worlds: as in [Gammerman et al., 1998; Gammerman, 1997] it provides confidence and credibility values (the predictive performance how­ ever, of the algorithm described in [Gammerman et al., 1998] is poor; this is probably explained by the "dis­ tortion phenomenon" : see [Gammerman et al., 1998], section 8.2 for details); as in Support Vector Machines, it achieves good predictive performance.

2 SV Implementation

In this section we describe the method upon which the transduction algorithms used in this paper are based. The method involves adding k examples to a training set and then training a separate SV machine for every possible classification of the k examples. Although the two transduction algorithms discussed here (our new al­ gorithm and Vapnik's margin technique) both use this as a basis, the method of prediction, and any additional information (such as confidence and possibility) about the test examples which they produce, is different. The · details of the algorithms will be presented in the next sec­ tion, for now though we present the general ideas which are common to both.

Suppose we have some training data

and a set of test data,

(Note: as with a Support Vector Machine, we assume that both the training and test data are generated inde­ pendently from the same distribution.) For a fixed set of classifications of the test data

we construct a Support Vector Machine on the combined sequence

For simplicity we will only consider the separable case, however the following can easily be generalised to the non-separable case (for details see e.g. [Vapnik, 1995]). We therefore want to find an optimal hyperplane w such that

is minimised, subject to the constraints

In order to find the optimal hyperplane we have to solve the following quadratic opti.misation problem: maximise

subject to the constraints

Here K ( x;, x;) is a kernel function - a general expression for the inner product in Hilbert space. According to Hilbert-Schmidt theory K(x;,x;) can be any symmetric function that satisfies Mercer's conditions (for details see [Vapnik, 1995]).

The process above is repeated for all possible classifi­ cations Yi, ... , yj. of the test set. In the following sections we shall describe how the two·algorithms use this process in different ways.

3 Transduction Algorithms

The method of transduction which we introduce here uses the statistical measure of p-values to determine the significance of the a;-value(s) associated with the test ex­ ample(s), once the quadratic optimisation problem (8)­ ( 11) has been solved for all possible classifications of the test set. This method not only gives predicted classifi­ cations, but also provides valid measures of confidence and credibility for its predictions [Vovk and Gammer­ man, 1999]. First of all we shall consider the case when the test set to be classified only contains one example and there are two possible classifications. This will then be extended to a multi-class classification. Finally we shall consider problems involving multiple test examples and binary classes.

3.1 Confidence values for a single test example

If we are only interested in the binary classification of a single example, then the quadratic optimisation problem (8) has to be solved twice (once where the new example is classified as +1, the other -1), and therefore two hy­ perplanes are obtained. For each hyperplane, we obtain a value of "strangeness" for the test example. This is defined as follows.

Consider the training set, with the new test example included,

Once (8) has been solved, each of the examples in this set has an associated Lagrange multiplier

Suppose we are interested in the probability that the anew is actually the largest Lagrange multiplier in this set. Since the training examples and the one new exam­ ple are exchangeable, then this probability is

(the randomisation is over all permutations of the ex­ amples). The value of the Lagrange multiplier can be interpreted as a measure of "supportiveness" of the ex­ ample, and therefore high values indicate that this ex­ ample is "strange" and unlikely to occur. In order to determine how unlikely a certain a-value is, we can use the statistical measure of p-values.

Simply examining whether or not the o-value associ­ ated with the new test example is the highest or not and accepting or rejecting it as the correct classification based on this alone would not produce a reliable classi­ fier. We therefore look at the p-value associated with the o-value and make a decision based on this value. If the rank of anew is n (i.e. anew is the nth highest o-value), the p-value is defined as

(once again, the randomisation is over all permutations of the examples), which is equivalent to

The p-value is a measure of how "strange" our test ex­ ample is when given a certain classification. That is, the p-value tells us the probability of observing this partic­ ular ordering of the alpha values under the assumption that Ynew is the correct classification. The classification Ynew which yields the highest corresponding p-value, de­ termines the classification predicted by the algorithm. The confidence in prediction can then be defined as

where P2 is the p-value obtained when the example was given the classification which we did not predict.

3.2 Classifying multiple new examples

If we are to consider the case when multiple new exam­ ples xi, ... , xk are added to the existing training set, then the QP problem (8)-(11) has to be solved a total of 2k times (in a two-class scenario). Unfortunately this is impractical for large values of k (e.g. k ~ 7) Each solution of this problem yields Lagrange multipliers cor­ responding to each of the test examples. The p-value associated with a particular assignment of classifications is then defined as

wh~re n1, ·.· , nk are the actual measured ranks of the corresponding Lagrange multipliers et11 ... , ak, and the randomisation is over all permutations of the examples. As in the single example case, the classifications pre­ dicted for the test examples are those which yield the highest p-value. Confidence is de.fined to be 1-P2 where P2 is the second highest p-value, and as in the single ex­ ample case, P1 (the highest p-value) corresponds to our credibility.

3.3 Measure of Credibility

Not only do we obtain a confidence value for our predic­ tion, but we also consider a measure of credibility which indicates the quality of the data on which we base our decision. We define credibility as the value P11 i.e. the p-value obtained when the test data are given the pre­ dicted classification(s).

In order to see how this can be interpreted as a mea­ sure of the quality of the data, first consider an "ideal" case. Suppose we are adding a single test example. Also suppose that when the correct classification is given to our test example it is not a support vector and there­ fore will have a p-value of 1. Assume that when given the incorrect classification, the p-value obtained from the example is at most 0.05. In this situation, our confidence would be 95% or greater and the value of credibility would be 1 (100%). This would mean we have high con­ fidence in our prediction from a good set of data. Now consider a similar case where the highest p-value still cor­ responds to the correct classification, but is much lower, say 0.3. If the other p-value obtained was the same as before, then we would still have a high confidence of95%. Our measure of credibility however would be much lower (30%). This would convey the meaning that although we confidently rejected all other classifications of this test example, the test example is actually "strange" in both scenarios and therefore the data is not sufficient to give us a totally secure prediction. Section 4.1 introduces empirical evidence which supports this line of reasoning.

The measure of credibility provides us with a filter mechanism with which we can "reject" certain predic­ tions. That is, if for any task the consequences of making a wrong prediction are quite severe, we can choose to re­ ject those predictions which have a low credibility value associated with them. The more severe the consequences for making an incorrect prediction are, the higher we can set the rejection threshold.

3.4 Vapnik's Margin Transduction

As a point of comparison for our technique we shall use a method of transduction suggested by Vapnik [Vapnik, 1998]. This method also uses the basic ideas described in section 2. The predicted classifications are the ones which separate the joint sequence

with maximal margin.

The predicted classifications are therefore given by

(subject to constraints (6) and (7)), over all possible clas­ sifications Yi , ... , YZ.

In the dual representation, this is equivalent to max­ imising (8)-(11) for all possible classifications of the test set, and predicting the classifications which achieve the overall minimum.

4 Experiments and Results

First of all we shall present some empirical evidence of the quality of the confidence and credibility values ob­ tained by the new transductive algorithm, based on a two-class digit recognition problem. A performance com­ parison is then made between our new algorithm, Vap­ nik's Margin algorithm, and a standard SV machine on the same data set.

Unless stated otherwise, the experiments in this sec­ tion were performed on the US Postal Service database of handwritten digits (see e.g. [LeCun et al., 1990]).

The kernel function used in these experiments was a polynomial of the form

for which the best performance is achieved with d = 3.

4.1 Confidence and Credibility Values

Table 1 shows an example of the confidence and credibil­ ity values obtained on a digit-recognition task of sepa­ rating the digit '8' from all other digits. The training set used in these experiments consisted of 49 examples of the digit '8' and 451 examples of other digits ('0' ... '9'). The test set consisted of 100 other digits from the database. Both the new transduction algorithm and an SV machine were run on the data. Out of 100 test examples both methods classified all but three examples correctly (they both misclassified the same three examples). The ta­ ble shows the confidence and credibility values for these three misclassified examples (along with the examples themselves). For all of the misclassified examples the credibility of the prediction is very low (no more than 5%). This suggests that for all of these examples, the quality of the data is not sufficient on which to base a prediction.

4.2 Relative Performance of the Algorithms

In this section we compare the predictive performance of the new algorithm, alongside the margin transduction technique and a Support Vector Machine. For this ex­ periment, we again used a subset of the digit database. All of the examples of the digits 2 and 7 were extracted from the database, giving a total set of 1721 examples. In each of these experiments a subset of n examples were randomly chosen and used as a training set. A single further example was then randomly picked as a test ex­ ample. All three algorithms were trained on the same training set and gave their predictions for the test exam­ ple. This process was then repeated for a total of 20000 runs, and for different values of n. Table 2 summarises these results. It is clear from the table that the new algorithm does not suffer in performance despite provid­ ing the extra information of confidence and credibility values.

5 Discussion

In this section we briefly discuss related work and high­ light possible directions for further research based on the results presented in this paper.

5.1 Adding multiple examples

At the present time, adding k examples to our original training set in order for them to be classified is imprac­ tical for large values of k. Recent developments in the training of Support Vector machines, however, such as those presented in [Platt, 1998] may yield improvements in the application of this algorithm. Another transduc­ tive algorithm has recently been proposed in [Bennett and Demiriz, 1998] which is based on the margin trans­ duction technique. This technique minimises thew vec­ tor in the L1-norm rather than the L2-norm and uses integer programming to rapidly find hyperplanes which separate the training data, even if the number of exam­ ples is large. This method however, does not provide confidences or credibility values for its predictions.

5.2 Extension to Regression

An important direction of this research is to extend it to the case of regression, i.e. where the classifications y; are no longer required to be binary values, but can be real numbers. Statistically valid p-values may be obtainable from Support Vector Machines for regression estimation (see e.g. [Vapnik, 1998]), or other related methods such as those in [Saunders et al., 1998].

6 Conclusion

In this paper we have presented a new transduction algo­ rithm which is based on the Support Vector technique. It has been shown that the algorithm produces confi­ dence values for its predictions, and also gives a measure of credibility which indicates the quality of data upon which the prediction is based, and therefore serves as a guideline of how reliable the prediction actually is. Em­ pirical results have been presented which show that val­ ues of confidence and credibility produced by the algo­ rithm do correctly reflect the reliability of the predictions given. This method has been shown not only to produce these values, but also to have good generalisation ability on a test set, comparable to and sometimes exceeding the results achievable by a Support Vector Machine.

7 Acknowledgements

This work was partially supported by EPSRC GR/135812 and GR/M15972, and EU INTAS-93-725ext grants. In addition we are indebted to the support provided by IFR Ltd. We would also like to an anony­ mous referee whose helpful comments prompted many changes and improvements in the paper.