Graph-Based Semi-Supervised Learning as a Generative Model

1 Introduction

In many real world classification tasks, the number of labeled instances is very few due to the prohibitive cost of manually labeling every single data point, while the number of unlabeled data can be very large since they are easy to obtain. Traditional classification algorithms, known as supervised learning, only make use of the labeled data, therefore prove insufficient in these situations. To address this problem, semi-supervised learning has been developed, which makes use of unlabeled data to boost the performance of supervised learning. In particular, graph-based semi-supervised learning algorithms have proved to be effective in many applications, such as hand-written digit classification [Zhu et al., 2003; Zhu et al., 2005], medical image segmentation [Grady and Funka-Lea, 2004], word sense disambiguation [Niu, Ji and Tan, 2005], image retrieval [He et al., 2004], etc.

Compared with other semi-supervised learning methods, such as TSVM [Joachims, 1999], which finds the hyperplane that separates both the labeled and unlabeled data with the maximum margin, graph-based semi-supervised learning methods make better use of the data distribution revealed by unlabeled data. In graph-based semi-supervised learning, a weighted graph is first constructed in which both the labeled and unlabeled data are represented as vertices. Then many of these methods can be viewed as estimating a function on the graph [Zhu, 2005]. Based on the assumption that nearby points in the feature space are likely to have the same label, the function is defined to be locally smooth and consistent with the labeled data. Finally, the classification labels are obtained by comparing the function value and a pre-specified threshold. For example, in the Gaussian random fields and harmonic function method, the learning problem is formulated in terms of a Gaussian random field on the graph, and the mean of the field serves as the function [Zhu et al., 2003]. Another example is the local and global consistency method, in which the function at each point is iteratively determined by both the information propagated from its neighbors and its initial label [Zhou et al., 2004]. Yet another example is the graph mincut method whose function corresponds to partitioning the graph in a way that roughly minimizes the number of similar pairs of examples that are given different labels [Blum and Chawla, 2001]. In the mincut method, the function can only take binary values.

Up till now, graph-based semi-supervised learning methods are generally approached from the discriminative perspective [Zhu, 2005] in that the function on the graph corresponds to posterior probabilities in one way or another. In the discriminative setting, however, the use of unlabeled data does not necessarily guarantee better decision boundaries. In addition, there is no clear explanation why the function on the graph should correspond to posterior probabilities from statistics point of view.

In this paper, we propose a new graph-based semi-supervised learning method from the generative model perspective. Specifically, the class conditional probabilities and the class priors are estimated from the weighted graph. The potential advantages involve several aspects: first, it can be theoretically justified that in the ideal cases where the two classes are separable, the output functions in terms of certain eigenvectors of the graph converge to the class conditional probabilities as the number of training data goes to infinity. In non-ideal cases, our functions still provide a good estimate of the class conditional probabilities. Finally, the estimated class priors make use of both the labeled and unlabeled data, which compensate for the lack of label information in many practical situations. Experimental results show that our approach leads to better performance than other existing graph-based methods on a variety of datasets. Hence we can claim both stronger theoretical justification and better empirical results.

The rest of the paper is organized as follows. In Section 2 and Section 3, we introduce how to estimate the class conditional probabilities and the class priors respectively. Section 4 deals with the out-of-sample problem, followed by an outline of the algorithm in Section 5. Then the experimental results are shown in Section 6. Finally, we give conclusion and hint on future work in Section 7.

2 Estimating Class Conditional Probabilities

2.1 Notation

In a binary classification problem, suppose that we are given a set of n training samples: 1 , d n x x . The first l n samples are labeled, including 1 l n positive ( 1 1, 1, , i l y i n ) and 0 1 l l l n n n negative ( 1 0, 1, , i l l y i n n ) samples. The remaining u l n n n samples are unlabeled. Our goal is to predict the class labels of these u n points by computing the posterior probability i i P y x .

By Bayes rule, we have

i y is predicted to be 1 iff 1 | 0.5 i i P y x . In our generative model, in order to calculate | i i P y x , we need to estimate both i i p x y and p y . In this section, we focus on estimating the class conditional probability i i p x y , and the estimation of p y will be discussed in the next section.

We first form an affinity matrix n n W with , ij i j W x x , where , i j x x is a non-negative function measuring the direct similarity between i x and j x . Then define D as the diagonal matrix, where 1 , 1, n ii ij j D w i n , and 1/ 2 1/ 2 S D WD . Finally define f and f as two n -dimensional vectors. The element of f ( f ) is set to 1 iff the corresponding point is a positive (negative) labeled one.

2.2 The Ideal Case

To start with, let us first consider the ideal case where the two classes are far apart. In this case, we have the following equation:

where x y is the observed class label of data point x .

Based on this assumption, if i x and j x are from two different classes, the corresponding 0 ij W . Therefore if we knew the labels of all the samples and put together the samples from the same class, the affinity matrix W , and thus the symmetric matrix S would be block-diagonal. To be specific, let

where 1 W and 0 W represent the sub-matrices corresponding to the positive and negative samples respectively, and 0 represents zero matrix. If the total number of positive (negative) samples in the training set is 1 n ( 0 n ), 1 W ( 0 W ) is an 1 1 n n ( 0 0 n n ) square matrix. Let 1 D and 0 D be two diagonal matrices, the diagonal elements of which are the row sums of 1 W and 0 W . Then S can be written as

The following theorem connects the class conditional probabilities with the diagonal elements of D .

Theorem 1. If , i j i j n n x x x x V , where n and n V are positive parameters, and the function satisfies the following conditions: 0 u , 1 u du , sup u u , 1 lim 0 d i i u u u , lim 0 n n V , lim n n nV , as the number of examples n goes to infinity, i ii y D n converges to i i p x y .

The proof of the theorem is straightforward and therefore we put it in the appendix. Notice that this theorem is similar to a result in kernel density estimation. The difference is that in kernel density estimation, we only have labeled data from a single class; while in our situation, we have both labeled and unlabeled data, and we could estimate the class conditional distributions of the two classes at the same time.

Suppose that the labeled data are noise-free. According to Theorem 1, we can use ii D to approximate the class conditional probability of i x given the observed label i y . However, for the unlabeled points, we do not know if ii D corresponds to 1 i i p x y or 0 i i p x y . To address this problem, we can make use of the eigenvectors of S .

It is easy to show that the largest eigenvalue of 1 S and 0 S is 1, and if 1 W and 0 W form a connected graph respectively, the corresponding eigenvectors would be 1/ 2 1 1 v D and 1/ 2 0 1 v D [Chung, 1997]. Based on v and v , we can construct two eigenvectors of S with eigenvalue 1:

where 0 is a zero vector. Notice that if we square 1 v and 0 v by elements to get 2 1 v and 2 0 v , and then add them up, we get

Obviously, 2 1 v and 2 0 v correspond to 1 i i p x y and 0 i i p x y respectively, and their non-zero elements are equal to ii D .

To get v and v , we perform f S f and f S f until convergence. Since the initial value of f is not orthogonal to 1 v (the elements of f and 1 v are non-negative), f will converge to 1 v . Similarly, f will converge to 0 v . Therefore, upon convergence, 2 i f ( 2 i f ) is in proportion to the class conditional probability of the positive (negative) class. After normalizing 2 i f ( 2 i f ) so that it sums to 1, we have an empirical estimation of 1 i i p x y ( 0 i i p x y ), which converges to its true value as n goes to infinity.

Figure 1 gives an example of density estimation in the ideal case. Figure 1(a) shows the training data, where the two moons represent two classes, and each class has one labeled example marked as star. Figure 1(b) and 1(c) show the estimated class conditional distributions of the two classes.

2.3 The General Case

In the general cases, the two classes are not far apart, and we have the following theorem.

Theorem 2. If , i j x x satisfies the conditions in Theorem 1, as the number of samples n goes to infinity, ii D n converges to 1 1 0 0 i i i i p x y P y p x y P y

The proof to this theorem is quite similar to Theorem 1. So we omit the details here. It can be seen easily that Theorem 1 is a special case of Theorem 2 when the two classes are far apart, i.e.

Equation (7), together with the fact that 1 lim 1 n n n P y , leads to Theorem 1.

In the general cases, W tends to form one connected graph instead of two, and S only has one eigenvector that corresponds to eigenvalue 1. If we still iterate f S f and f S f until convergence, both f and f will converge to the same eigenvector. On the other hand, the operation of f S f and f S f can be seen as the labeled data gradually spreading their information to nearby points. If the iteration steps are unlimited, every data point will be equally influenced by the positive and negative labeled data, leading to the same value of f and f .

To solve this problem, in our algorithm, we have designed a stopping criterion, and the iteration process is stopped once the criterion is satisfied. To be more specific, when estimating the class conditional probabilities of the positive class, we could get an estimate of 1 i i p x y in each iteration step

(by normalizing 2 i f so that it sums to 1). By summing up this probability for negative labeled samples, we have the average likelihood of these samples in the positive class: 1 1 l n i i i n L p x y n . We stop the iteration when the second derivative of L with respect to the iteration steps crosses 0. This criterion can be justified as follows: in the initial iteration steps, only a few negative data get positive score from their nearby positive labeled points, so the rate at which L increases is very low; as the iteration proceeds, those negative data have accumulated high scores and propagate to the majority of negative points, so the rate gradually increases; finally, as f begins to converge, its value at each data point becomes stable, so the rate decreases until it reaches 0. If we plot the curve of L with respect to the number of iteration steps, the shape would be convex first, and then concave until convergence (Figure 2(b)). Notice that in the initial iteration steps, the positive points, which are far away from the positive labeled points but connected to them via some kind of manifold, cannot get positive scores. If the algorithm stops at this stage, it may not fully explore the data distribution and cause misclassification on certain clusters of data. Therefore we choose the transition point between convex and concave as the stopping point in order to trade off between prematurity and excessive propagation. The stopping criterion for the negative class can be derived similarly, i.e. 1 1 1 0 l n i i l i L p x y n . A key point in our algorithm is that the estimation of the class conditional probabilities of the two classes is independent, i.e. the numbers of iteration steps when the two stopping criterions are satisfied are not necessarily the same.

Figure 2 gives an example of density estimation in the general case showing the effectiveness of our criterion. This example is quite similar to the one shown in Figure 1 except that the two classes are not far apart. Figure 2(b) shows the value of L (the upper curve) and L (the lower curve) in each iteration step. The arrows point to the positions in the curves where the two criterions are satisfied. Figure 2(c) and 2(d) show the estimated class conditional distributions of the two classes. Although there are small gaps in the middle of the distributions, the moon structure is recovered fairly well.

Note that the stopping criterion discussed above is based on simple heuristics. Currently we are trying to design a stopping criterion in a more principled manner.

3 Estimating Class Priors

In this section, we focus on estimating the class prior P y . Existing graph-based semi-supervised learning methods only use the labeled set to estimate the class priors, either explicitly [Zhu et al., 2003] or implicitly [Zhou et al., 2004]. Obviously, in real applications, the proportion of positive and negative labeled data is often far from the true class priors.

In our algorithm, we use both the labeled and unlabeled data to estimate the class priors. According to Theorem 2, once we have estimated the class conditional probability i i p x y , we can feed them into the following equations and form a linear regression problem, the solution of which is equal to the least squares estimator of 1 P y .

However, when the number of labeled data is small, the estimated class conditional probabilities may not be very accurate, and thus ˆp is not very reliable. To solve this problem, we use a beta distribution as the prior distribution for 1 P y , the parameters of which are ˆp and ˆ 1 p . Then the estimate of 1 P y based on the labeled set:

which is equivalent to smoothing the proportion of the positive and negative samples in the labeled set. When the number of labeled data is small, unlabeled data can be fully exploited to compensate for the proportion in the labeled set that is not the same as the class priors; when the number of labeled data is large, labeled data will dominate the estimation of the class priors.

4 Prediction of New Testing Data

To classify a data point d x that is not present during the training stage, we first calculate its class conditional probabilities via kernel regression:

Using these class conditional probabilities and the class priors obtained during the training stage, we can calculate the posterior probability and make a prediction.

5 The Algorithm

The procedures for estimating i i p x y and P y are summarized in Table 1 and Table 2 respectively.

1. Form the affinity matrix n n W , where , ij i j W x x . Calculate D and S .
2. Initialize f and f . The element of f ( f ) is set to 1 if the corresponding point is a positive (negative) labeled one, and 0 otherwise.
3. Update f S f , f S f .
4. Assign 2 1 i i i p x y f , 2 0 ( ) i i i p x y f , and normalize so that 1 1 1 n i i i p x y , 1 0 1 n i i i p x y .
5. Calculate the average likelihood of negative (positive) labeled points in the positive (negative) class:

Go to step 4 unless one of the following conditions is satisfied:

1. L ( L ) remains at 0, and f ( f ) has converged; b. L ( L ) does not remain at 0, and the second derivative of L ( L ) with respect to the iteration steps crosses 0.

Table 1. Description of Estimation for i i p x y

1. Solve the following linear regression problem for the least squares estimator ˆp of 1 P y :

1. Calculate the class priors as the smoothed proportion of the positive and negative samples in the labeled set

Table 2. Description of Estimation for P y

6 Experimental Results

In this section, we present the comparative experimental results on two datasets: Cedar Buffalo binary digits database [Hull, 1994], and a document genre-classification dataset [Liu et al., 2003]. Our algorithm is compared with two other graph-based semi-supervised learning methods: Gaussian random fields [Zhu et al., 2003] and the local and global consistency method [Zhou et al., 2004]. We did not compare with supervised learning methods, such as one nearest neighbor, since they have been proved to be less effective than Gaussian random fields based on experimental results [Zhu et al., 2003].

We have designed two kinds of experiments: balanced and unbalanced. In the balanced case, the ratio of labeled points from each class is always the same as the class priors; in the unbalanced case, if not explained otherwise, we fix the total number l n of labeled points, and perturb the number of positive labeled points around 2 l n with a Gaussian distribution of mean 0 and standard deviation 10 l n . In each experiment, we gradually increase the number of labeled data, perform 20 trials for each labeled data volume, and average the accuracy at each volume point.

6.1 Cedar Buffalo Binary Digits Database

We first perform experiments on Cedar Buffalo binary digits database [Hull, 1994] including two classification tasks: classifying digits "1" vs "2", with 1100 images in each class; and odd vs even digits, with 2000 images in each class (400 images for each digit). The data we use are the same as those used in [Zhu et al., 2003]. Here 2 2 2 2 , 2 exp 2 d i j i j x x x x , where is the

average distance between each data point and its 10 nearest neighbors.

1

case, while the performance of our algorithm is comparable to the balanced case. This is because the class mass normalization procedure adopted in Gaussian random fields depends on the labeled set only to estimate the class priors; while our algorithm makes use of both the labeled and the unlabeled set to estimate the class priors. Therefore, it is more robust against the perturbation in the proportion of the positive and negative data in the labeled set.

6.2 Genre Dataset

Genre classification is to classify the documents based on its writing styles, such as political articles and movie reviews. The genre dataset that we use consists of documents from 10 genres, including biographies (b), interview scripts (is), movie reviews (mr), product reviews (pr), product press releases (ppr), product descriptions on store websites (pd), political articles on newspapers (pa), editorial papers on politics (ep), news (n), and search results from multiple search engines using 10 queries (sr). We randomly select 380 documents from each category to compose the whole dataset of 3800 documents. Each document is processed into a "tf.idf" vector, which is generated based on the top 10,000 most frequent words in this dataset after stemming, with the header and stop words removed. Here , exp 1 0.03 i j i j i j x x x x x x , which is borrowed from [Zhu et al., 2003] and roughly measures the similarity between documents. The only difference is that we keep all the edges instead of keeping edges for only 10 nearest neighbors. Next we perform experiments to compare the three algorithms. The results are provided in Figure 5 and

Figure 6 respectively.

anced cases respectively. In the balanced case, Gaussian random fields is better than our algorithm and the local and global consistency method. This might be because the function , i j x x does not have some of the nice properties required by Theorem 2. However, in the unbalanced case, Gaussian random fields tends to suffer a lot. On the contrary, our algorithm is quite robust despite of the perturbation.

In Figure 6, we try to classify pa and b against all the other categories. In these experiments, the class priors are 0.1 for the positive class and 0.9 for the negative class. However, here we provide equal numbers of positive and negative points in the labeled set. From the figures, we can see that the performance of our algorithm is rather stable, while the performance of both Gaussian random fields and the local and global consistency method is largely affected by the misleading labeled set, since they only depend on the labeled set to estimate the class priors, either explicitly or implicitly.

7 Conclusion and Future Work

In this paper, we propose a novel graph-based semi-supervised learning method to estimate both the class conditional probabilities and the class priors. It is a generative model, in contrast to existing graph-based methods, which are essentially discriminative. In the ideal case, the estimated class conditional probabilities have been proved to converge to the true value. In the general case, our algorithm can still output reasonable estimates of the class conditional probabilities. For data points outside the training set, the class conditional probabilities are estimated via kernel regression. When estimating the class priors, we effectively use the unlabeled data to make up for the labeled data with unrepresentative class prior distributions. Experimental results on two datasets demonstrate the superiority of our algorithm over recent existing graph-based semi-supervised learning methods, especially when the proportion in the labeled set is not the same as the class priors.

In our experiments, we notice that in some cases, adding even a single labeled point into the labeled set brings about significant improvement in classification accuracy; while in other cases, adding many labeled points into the labeled set does not help improve the performance. Currently we are incorporating active learning into our framework. Particularly, we are interested in determining when to invoke active learning (not just which instances to label) in order to achieve the biggest gain while minimizing incremental labeling cost.