Selecting Informative Universum Sample for Semi-Supervised Learning

1 Introduction

Semi-supervised learning (SSL) is an important topic, which uses both labeled and unlabeled samples. There is an abundance of literature about SSL, e.g. [Joachims, 1999; 2003; Belkin et al., 2004; Zhou et al., 2004; Zhu et al., 2003] and the references therein.

Graph based SSL is one of the important branches of the whole SSL literature, with the representative works such as [Belkin et al., 2004; Zhou et al., 2004; Zhu et al., 2003]. In these methods, a graph is built to describe the structure of the samples in space. Each sample is assigned a node, and the weight of the edge between two nodes corresponds the similarity of the two samples. Then a soft label function f is learnt based on certain consistency and continuity assumptions.

The concept of Universum sample has been introduced by [Vapnik, 2006]. It is defined as the sample that doesn't belong to any of the classes the learning task concerns. For example, in the task of classifying 5 against 8 in handwritten digits recognition, samples of other digits can be considered as Universum samples. The Universum sample is practically easy to get, even easier than the unlabeled sample, since there is so few requirement for it. Take, for instance, the text classification of political news against sports ones. All news from other categories, including economy, entertainment, science, etc. can play the role.

Several works have been done to use the Universum samples both in the supervised learning and SSL settings. In [Weston et al., 2006], the authors give a modified Support Vector Machine (SVM) framework, called U-SVM. [Sinz et al., 2008] gives an analysis of [Weston et al., 2006], suggesting that U-SVM seeks "a hyperplane which has its normal lying in the orthogonal complement of the space spanned by Universum examples" 1 . These two works both contain similar punishing terms in the formulation that require the decision values on Universum samples not far from zero. However the above two works are done under the supervised learning settings, and no unlabeled samples are used. [Zhang et al., 2008] is the first paper to address SSL with Universum samples. The authors suggest the following formulation

ˆ f and ˆy are only on the labeled and unlabeled samples. The Universum samples are taken as out-of-sample examples. In the third term of (1), the value f (x ∗ i ) is inducted from ˆ f . Therefore it can also drive the decision value at Universum samples to zero. However, no explanation is provided about why the Universum samples can be treated as out-of-sample examples in this paper. There may be one uncertainty: ˆ f in Reproducing Kernel Hilbert Space (RKHS) is learned from only the labeled and unlabeled samples. Using it to do the induction on Universum samples is based on the implicit assumption that the distribution of Unversum samples is the same with that of labeled and unlabeled samples. This may not be true sometimes.

All of the three works mentioned above are based on the same assumption: the decision values on the Universum samples should be close to zero. Equally this is to say that the decision boundary should be dragged towards where the Universum samples have been distributed. However, this assumption may sometimes be misleading. Consider the toy example in supervised learning setting (Fig.1(a)). The two classes could be linear separated. Thus SVM would give 100% classification accuracy on the training set (Fig.1(b)). When introducing some Universum samples between the two classes, as shown in Fig.1(c), U-SVM can also give the 100% accuracy. But when using another set of Universum samples (Fig.1(d)) and the same parameter setting as above, the performance of the trained classifier is severely damaged to the accuracy of only 55%. This is due to that the linear decision boundary is dragged towards the Universum samples on the left-hand side, while the optimized setting is to pass through just in between the two classes. This example gives us the idea that not all the Universum samples are useful and there should be some mechanism to filter out the damaging ones. Intuitively, we should keep the Universum samples which is posited in between different classes, since it gives the right direction to which the decision boundary should be dragged to.

1 This is the direct quotation from [Sinz et al., 2008]

In this paper, we propose a method to select the in-between Universum samples (IBU) by using a modified version of betweenness centrality [Freeman, 1977; 1978]. An SSL framework is setup to incorporate the IBU, taking it as labeled sample rather that out-of-sample example. The experimental results on several datasets are promising.

The rest of the paper is organized as follows: In section 2, we give the notation and review the preliminaries for this paper. Our method of SSL using IBU is detailed in section 3, with experiments in section 4. We conclude our work and suggest future direction in section 5.

2 Notation and Preliminaries

In this paper, our methods only focuses on the binary classification case, while it can be extended to the multi-class scenario straightforwardly. Suppose we are given a dataset with three different parts. The first one is a labeled subset {(x l 1 , y1), (x l 2 , y2), . . . , (x l m , ym)} with m samples, where yi is corresponding label taking the value of ±1 for binary classification problems. The second one is an unlabeled subset {x u 1 , x u 2 , . . . , x u n } with n samples. And the third one is an Universum subset {x ∗ 1 , x ∗ 2 , . . . , x ∗ q }. x l i , x u j and x ∗ k are from the same input space χ where χ ∈ R d . We unify the three parts to {x1, x2, . . . , xm+n+q} so that

For supervised learning, only the labeled dataset is provided, while the unlabeled dataset is provided as complement in the SSL setting. The Universum dataset can serve both the supervised learning and SSL setting. We mainly focused on the SSL in this paper.

3 SSL Framework using IBU

In this section, we introduce our SSL framework using IBU. Firstly we give a brief introduction of the measure of centrality based on betweenness. Then we provide an algorithm to find the IBU using the defined measure of centrality. Finally, we set up the SSL framework to incorporate the IBU. The IBU is considered as labeled sample.

3.1 Betweenness of the Universum Samples

As mentioned in the introduction section, we hope to find the portion of the Universum samples that are in between samples from different classes. Thus a quantity to measure this betweenness is needed. We define it as

where σx l j ,x l k is the number of shortest paths on the graph from labeled sample x l j to labeled sample x l k . σx l j ,x l k (x ∗ i ) is the number of those paths that pass through the Universum sample x ∗ i . Intuitively, bU(x ∗ i ) gives a quantitative measure of to what extent Universum sample x ∗ i is in between any pairs of labeled samples from different classes. We can simplify the expression by letting σx l j ,x l k = 1, since the probability of existence of more than one shortest path between two vertices approaches zero when taking enough precision of the data into account. Thus the definition becomes

By using a manually set threshold t, we define IBU as

It is worth mentioning that our definition of betweenness is derived from the betweenness centrality in the graph theory and social network area ([Freeman, 1977; 1978]).

3.2 An Algorithm of Finding IBU

We give an algorithm to find IBU. The detail is listed in Table 1. The time complexity and space complexity are O((m + n + q) 3 ) and O((m + n + q) 2 ) respectively. We also give a simple demonstration on the well-known two-moon dataset with Universum samples added by us in Fig.2(a). We see that IBU do posit in between the two different classes. Also, the number of IBU is relatively small comparing to the whole Universum samples.

Input:

A dataset {x1, x2, . . . , xm+n+q}, with m labeled samples, n unlabeled samples and q Universum samples.

A label set {y1, y2, . . . , yn}for the labeled samples. A threshold t

Step 1:

Calculate the neighbor distance matrix G

where Nk(xi) is the set of the k-nearest neighbors of xi Step 2:

Initialize bU(x ∗ i ) = 0, 1 ≤ i ≤ q Step 3: for k = 1 : m + n + q for i, j = 1 : m+ n + q if Gik +Gk j < Gi j and m + n + 1 ≤ k ≤ m + n + q and yi nequal yj bU(x ∗ k-m-n ) = bU(x ∗ k-m-n ) + 1 end if Gi j = min(Gi j,Gik +Gk j) end for end for Output: The set of IBU UIB = {x ∗ i |bU(x ∗ i ) ≥ t}

-2

-1

0

1

2

3

-2

-1

0

1

2

3

Figure 2: The result of our finding IBU algorithm on the twomoon dataset with Universum samples. The distribution of provided samples are shown in (a). △ and □ stand for labeled samples from two classes respectively. ▪ is the unlabeled sample and © is the Universum sample. The result after our finding IBU algorithm is shown in (b), in which we use © to represent IBU found.

3.3 SSL Framework using IBU

As explained in the introduction part, treating the Universum samples as out-of-sample examples is unconvincing. We suggest to treat the IBU, which can be considered as the representative part of the Universum samples, as the labeled samples with label 0. So we reformulate the following optimization problem

|UIB| is the number of IBU. f is the predicted soft label, defined on labeled, unlabeled and IBU samples. y is the (m + n + |UIB|) × 1 given label vector, with its first m elements equal the label of labeled samples yi, while others 0. C is a diagonal weight matrix, with

C can be considered as the tradeoff between each parts of the samples. R is a regularization matrix. It can be the Laplacian or normalized Laplacian matrix on the labeled, unlabeled and IBU samples. The first term of (6) restricts f to be close to the given label on the labeled sample, and close to 0 on IBU. The second term is the regularization term that requires f does not change much on nearby samples. We denote our algorithm as Lap-IBU and NLap-IBU respectively. By setting the derivative of (6) to be 0, we obtain

The solution of this linear equation can be written in a pseudo-inverse form

This method avoids the mentioned problem of [Zhang et al., 2008] in the introduction part, because the labeled samples, unlabeled samples and IBU equally fit into the framework as a prior. This is to say that f is learned based on a mixture distribution of the three parts of samples. Also, as shown in the demonstration of last subsection, the number of IBU is small compared to that of the whole Universum samples. It won't affect the scale of the graph based SSL too much. One should notice that, this method can be considered as a special case of the framework in [Belkin et al., 2005], with the addition of IBU as labeled sample. The justification of the method can be found therein. Besides, we could do the induction on the out-of-sample examples when given a semi-definite kernel function k(· , ·) as

where K is the kernel matrix defined on labeled, unlabeled and IBU samples. k(x) is a (m + n + |UIB|) × 1 vector whose each element is the value of the kernel function applied on the out-of-sample example x and the provided labeled, unlabeled and IBU samples.

Moreover, we would like to show one possible good quality of our finding-IBU-strategy through an example in Fig. 3. Comparatively, the function learned from our method is less complex than that from the method of [Zhang et al., 2008]. Also in our method, the difference between the decision values of the two classes is greater. These mean that we could expect better generalization performances of our methods 2 . Intuitively, this is because we don't use the Universum samples that are not around the possible region of decision boundary. These samples would serve to "warp" the function towards zero on the periphery of the task-concerned data, and meanwhile affecting the decision value of the task-concerned data. Thus by discarding them, the learned function could be simplified, and the gap between two classed enlarged.

2 We assume that the to-be-predicted samples are task-concerned.

4 Experiments and Discussion

In this section, we conduct experiments on various datasets includingWine 3 , USPS 4 , MNIST 5 and Umist 6 to show the effectiveness of our methods. We compare our algorithm with four other ones, namely Lap-Universum, NLap-Universum, Lap-IBU* and NLap-IBU*. Lap-Universum and NLapUniversum are from [Zhang et al., 2008]. Lap-IBU* and NLap-IBU* use the same SSL framework as Lap-Universum and NLap-Universum, while incorporate IBU selected by our algorithm rather than the original Universum samples. We set Cl = 1 and k = kL = 15 (kL is the number of nearest neighbors in constructing the Laplacian or normalized Laplacian matrix). We also need to tune Cu, CU and the bandwidth σ in the RBF kernel.

4.1 Wine Dataset

The wine dataset is from the UCI machine learning repository ([Asuncion and Newman, 2007]). It contains 178 instances of wine from 3 different classes, each representing a wine cultivar. Each instance contains 13 attributes from chemical analysis. Our experiment is on the binary classification problem of class 1 (59 instances)and class 3 (48 instances), while using class 2 (71 instances) as Universum samples. For the class 1 and class 3 samples, we randomly pick part of them as the labeled samples. Others are treated as unlabeled samples. We vary the number of labeled samples and each setting is repeated 500 times. The average accuracy and the variance are listed in Table 2.

3 http://archive.ics.uci.edu/ml/datasets/Wine

4 http://cervisia.org/machine learning data.php

5 http://yann.lecun.com/exdb/mnist/

6 http://www.shef.ac.uk/eee/research/vie/research/face.html

4.2 USPS Dataset

The USPS dataset is a handwritten digit dataset scanned from envelopes. We used an abridged subset, with 200 samples for 2, 3, 5 and 8 respectively. Each sample is represented by a 256-dimensional vector extracted from the original 16 × 16 image. We test on the 5 vs 8 classification problem, with 2 and 3 treated as Universum samples. Different numbers of labeled samples corresponds different settings, which are repeated 50 times. The result is shown in Table 3.

4.3 MNISTDataset

MNIST Dataset is also a handwritten digit dataset with samples from 0 to 9. Each sample is a 16 × 16 image. For the 5 vs 8 classification problem, We select 100 5s, 100 8s and 1000 other digits uniformly distributed from the classes as the Universum samples. The numbers of randomly given labels are changed to form different settings, which is repeated 100 times. The result is listed in Table 4. We are also interested in what the IBU really are. So we pile the used IBU in the experiment up, and calculate the portion of each digit. They are listed in Table 5.

4.4 Umist Dataset

Umist dataset is a collection of 575 28 × 23 images of faces from 20 people, among which there are 4 female and 16 male (Fig. 4). We test on the classification of person 9 and person 20, two females, using samples of other 18 people as Universum samples. The accuracy against the number of labeled samples m is shown in Table 6, where each setting is repeated 100 times. We follow the setup of the experiment on MNIST and inspect the constituent of the IBU collection. It only contains two persons, 8.33% of person 6 and 91.67% of person 7.

4.5 Discussion

From the result of our experiments, we can tell that our methods based on IBU outperforms the former ones using the whole Universum dataset equally. The accuracy of using both Laplacian and normalized Laplacian favors ours algorithm. Besides, while both incorporating IBU, the methods of our SSL framework is better than that of former SSL framework in most cases. The only exception is that on the Umist dataset with normalized Laplacian matrix. These results show that: i).Using IBU is the main reason for the improvement of accuracy; ii). Our SSL framework is better than the former one under most of the circumstances. Moreover, the experiments give an intuitive demonstration of what IBU is like. In Table 5, digit 3 takes the greatest part of the IBU. This is mainly because 3 looks like both 5 and 8, justifying its high betweenness. In other word, 3 is the most useful Universum of classifying 5 and 8. This result coincides with [Sinz et al., 2008]. Digits 1, 6 and 9 as Universum also contribute to the problem greatly. Similarly in the experiment on Umist dataset, person 7 is important in the person 9 vs 20 classification task because it is also female.

We would like to give an explanation about how IBU works based on the experiment results. As shown above, IBU resembles both of the samples from two classes. Equally that is to say IBU can be taken as a "transition phase" of the two classes. Thus it can be helpful in following ways: Where the IBU lies represents a region that intercepts the changing trace from one class to the other class. Also it is a region that belongs to neither class. These characteristic is compatible with that of decision boundary and we use it as a guide to find it.

5 Conclusion and Future Work

In this paper, we research on the use of Universum sample, which is defined to be the sample that belongs to neither of the concerned classes. We suggest that not all the Universum samples should be treated equally, which is not realized in the existing works. An algorithm and a framework are proposed to pick the useful portion of Universum samples, defined as IBU, and incorporate them for the SSL setting. The results of experiments show that our methods is advantageous in predicting accuracy against the former ones. The experiments also give a demonstration of what IBU is - the "transition phase" between different classes.

The learning with Universum is related with some other fields of machine learning. [Zhang et al., 2008] refers the relations with multi-class and ordinal regression problem. A new proposed branch - self-taught learning, is also connected with the problem of learning with Universum ([Raina et al., 2007; Dai et al., 2008]). In the self-taught setting, one is provided with two parts of samples. One part contains the samples that belong to the classes the problem concerns. It could be labeled for the supervised learning or unlabeled for the clustering setting. The other part contains a great amount of randomly picked samples with no labels, which could belong to the classes the problem concerns or not. In our term, the second part includes unlabeled samples and Universum samples, with no indication of which is which. Self-taught methods use the second part of samples to assist the task defined originally on the first part. Since we cannot distinguish the unlabeled samples and the Universum samples, it cannot be adapted to learning with Universum framework directly.

Besides, as a more general framework, there are four kinds of samples we may encounter in a learning problem. We list them in a descending order of importance: labeled sample, unlabeled sample, "unrelated" sample and "out-of-domain" sample. The "unrelated" sample is the sample that shares the same domain with the labeled and unlabeled sample, whereas does not belong to any of the concerned classes. The "out-of-domain" sample is the sample other than the defined three kinds. The mixture of "unrelated" sample and "out-ofdomain" sample is the Universum sample. We give an illustration of each kinds of samples in the 5 vs 8 classification problem (Fig. 5).

The existing learning problems using different combination of the four kinds of samples are listed in Table 7. Obviously, the four kinds of samples carry different amount of a priori. One possible future work is to set up a general framework to incorporate all the combination of the four kinds of samples and their mixtures.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant No.60835002 and 60721003). We would like to thank Yangqiu Song, Dan Zhang, Jianwen Zhang, Zheng Wang, Chenping Hou, Feiping Nie and Kun Gai for their help. We also appreciate the valuable comments by the anonymous reviewers.