Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions

Active and semi-supervised learning are important techniques when labeled data are scarce. We combine the two under a Gaussian random field model. Labeled and unlabeled data are represented as vertices in a weighted graph, with edge weights encoding the similarity between instances. The semi-supervised learning problem is then formulated in terms of a Gaussian random field on this graph, the mean of which is characterized in terms of harmonic functions. Active learning is performed on top of the semisupervised learning scheme by greedily selecting queries from the unlabeled data to minimize the estimated expected classification error (risk); in the case of Gaussian fields the risk is efficiently computed using matrix methods. We present experimental results on synthetic data, handwritten digit recognition, and text classification tasks. The active learning scheme requires a much smaller number of queries to achieve high accuracy compared with random query selection. 1.  Semi-supervised learning targets the common situation where labeled data are scarce but unlabeled data are abundant. Under suitable assumptions, it uses unlabeled data to help supervised learning tasks. Various semi-supervised learning methods have been proposed and show promising results; Seeger (2001) gives a survey. These methods typically assume that the labeled data set is given and fixed. In practice, it may make sense to utilize active learning in conjunction with semi-supervised learning. That is, we might allow the learning algorithm to pick a set of unlabeled instances to be labeled by a domain expert, which will then be used as (or to augment) the labeled data set. In other words, if we have to label a few instances for semisupervised learning, it may be attractive to let the learning algorithm tell us which instances to label, rather than selecting them randomly. We will limit the range of query selection to the unlabeled data set, a practice known as poolbased active learning or selective sampling. There has been a great deal of research in active learning. For example, Tong and Koller (2000) select queries to minimize the version space size for support vector machines; Cohn et al. (1996) minimize the variance component of the estimated generalization error; Freund et al. (1997) employ a committee of classifiers, and query a point whenever the committee members disagree. Most of the active learning methods do not take further advantage of the large amount of unlabeled data once the queries are selected. Exceptions include McCallum and Nigam (1998) who use EM with unlabeled data integrated into the active learning, and Muslea et al. (2002) who use a semi-supervised learning method during training. In addition to this body of work from the machine learning community, there is a large literature on the closely related topic of experimental design in statistics; Chaloner and Verdinelli (1995) give a survey of experimental design from a Bayesian perspective. Recently Zhu et al. (2003) introduced a semi-supervised learning framework which is based on Gaussian random fields and harmonic functions. In this paper we demonstrate how this framework allows a combination of active learning and semi-supervised learning. In brief, the framework allows one to efficiently estimate the expected generalization error after querying a point, which leads to a better query selection criterion than naively selecting the point with maximum label ambiguity. Then, once the queries are selected and added to the labeled data set, the classifier can be trained using both the labeled and remaining unlabeled data. We present results on synthetic data, text classificaProceedings of the ICML-2003 Workshop on The Continuum from Labeled to Unlabeled Data, Washington DC, 2003. tion and image classification tasks that indicate the combination of these techniques can result in highly effective learning schemes. 2. Gaussian random fields and harmonic energy minimizing functions We begin by briefly describing the semi-supervised learning framework of Zhu et al. (2003). There are labeled points , and unlabeled points ; usually . We will use , ! to denote the labeled and unlabeled set, and "$#% '&( the total number of points. We assume the labels are binary: *),+.-0/1 243 . We assume a connected graph 56#6 87' 9: is given with nodes 7 corresponding to the " data points, of which the nodes in are labeled with the corresponding ’s. The edges 9 are represented by an "<;=" weight matrix > which is given. For example if ?+A@CB , > can be the radial basis function (RBF): DFEHG #JI KML NPO 2 Q R B STVU E T O G T R W (1) so that nearby points in Euclidean space are assigned large edge weights. Other weightings are possible, of course, and may be more appropriate when is discrete or symbolic. For our purposes the matrix > fully specifies the data manifold structure. We note that a method for learning the scale parameter Q is proposed in (Zhu et al., 2003). The semi-supervised algorithm in this paper is based on a relaxation of the requirement that labels are binary, resulting in a simple and tractable family of algorithms. We allow continuous labels on unlabeled nodes MXZY[7]\^@ . The labels on labeled data are still constrained to be 0 or 1: _` C#a 4)b c_ d+A-e/ 243 for _P#(24 f . We also denote the constraint by g ) U h i . Since we want unlabeled points that are nearby in the graph to have similar labels, we define the energy to be 9j c 1 C# 2 k S E l G D EmG _` O onp R (2) so that low energy corresponds to a slowly varying function over the graph. Define the diagonal matrix q6#sr*_`t*u[ 8r E whose entries r E #wv G DFEmG are the weighted degrees of the nodes in 5 . The combinatorial Laplacian is the "x;y" matrix z{#aq O > . We can rewrite the energy function in matrix form as 9| c 1 #( } z: . We consider the Gaussian random field ~ c 1 C# 2 P I KML< OF 9j c 1 f where  is an “inverse temperature” parameter, and   is the partition function  #s h  i U h i I KpL< OF 9j M r4 . The Gaussian random field differs from the “standard” discrete Markov random field in that the field configurations are over a continuous state space. Moreover, for a Gaussian field the joint probability distribution over unlabeled nodes is Gaussian with covariance matrix  z| 0 . z 0 is the submatrix of z corresponding to unlabeled data. The minimum energy function # arg min h  i U h i 9| c 1 of the Gaussian field is harmonic; that is, it satisfies zA#/ on unlabeled data points ! , and is equal to ) on the labeled data points . The harmonic property means that the value at each unlabeled node is the average of neighboring nodes: b onp C# 2 r G S EG DEmG b _` for n#Z &a24 f &? which is consistent with our prior notion of smoothness with respect to the graph. Because of the maximum principle of harmonic functions (Doyle & Snell, 1984),  is unique. Furthermore,  satisfies /(b onp 2 for n+! when ! is connected and labeled nodes from both classes are present at the boundary (the usual case; otherwise  takes on the extremum 0 or 1). By definition  is the mode of the Gaussian random field, but since the joint distribution is Gaussian,  is also the mean of the field. The harmonic energy minimizing function  can be computed with matrix methods. We partition the Laplacian matrix z into blocks for labeled and unlabeled nodes, z# z m z z e z 0  and let ,#  0   where  # ) , and  denotes the mean values on the unlabeled data points. The solution is given by  # O z  0 z e  (3) It is not hard to show that the Gaussian field, conditioned on labeled data, is a multivariate normal: * ya   fz  0 . To carry out classification with a Gaussian field, we note that the harmonic energy minimizing function  is the mean of the field. Therefore the Bayes classification rule is to label node _ as class 1 in case b c_ dJ/1 H , and to label node _ class 0 otherwise. The harmonic function  has many nice interpretations, of which the random walk view is particularly relevant here. Define the transition matrix # q  > . Consider the random walk on graph 5 by a particle. Starting from an unlabeled node _ , it moves to a node n with probability  EHG after one step. The walk continues until the particle reaches a labeled node. Then  E is the probability that the particle, starting from node _ , reaches a labeled node with label 1. The labeled data are the absorbing boundary for the random walk. More on this semi-supervised learning framework can be found in (Zhu et al., 2003). 3. Active learning We propose to perform active learning with the Gaussian random field model by greedily selecting queries from the unlabeled data to minimize the risk of the harmonic energy minimization function. The risk is the estimated generalization error of the Bayes classifier, and can be efficiently computed with matrix methods. We define the true risk  of the Bayes classifier based on the harmonic function  to be  # S E U S h U l sgn  E # E ~ E g where sgn 8 E is the Bayes decision rule, where (with a slight abuse of notation) sgn  E # 2 if  E ^/  and sgn  E #,/ otherwise. Here ~ E g is the unknown true label distribution at node _ , given the labeled data. Because of this 8 is not computable. In order to proceed, it is necessary to make assumptions. We begin by assuming that we can estimate the unknown distribution ~ c E g d with the mean of the Gaussian field model: ~ c E # 2pg d Z E Intuitively, recalling  E is the probability of reaching 1 in a random walk on the graph, our assumption is that we can approximate the distribution using a biased coin at each node, whose probability of heads is  E . With this assumption we can compute the estimated risk 8 as  8 # S E U sgn  E # / 2 O  E & sgn 8 E #(2  E # S E U  E 2 O  E (4) If we perform active learning and query an unlabeled node , we will receive an answer (0 or 1). Adding this point to the tr