Semi-Supervised Gaussian Process Classifiers

1 Introduction

Practitioners of machine learning methods frequently encounter the following situation: large amounts of data can be cheaply and automatically collected, but subsequent labeling requires expensive and fallible human participation. This has recently motivated a number of efforts to design semisupervised inference algorithms that aim to match the performance of well-trained supervised methods, using a small pool of labeled examples and a large collection of unlabeled data. The scarcity of labeled examples greatly exaggerates the need to incorporate additional sources of prior knowledge, to perform careful model selection, and to deal with noise in labels. A Bayesian framework is ideally suited to handle such issues. In this paper, we construct semi-supervised Gaussian processes, and demonstrate and discuss its practical utility on a number of classification problems.

Our methods are based on the geometric intuition that for many real world problems, unlabeled examples often identify structures, such as data clusters or low dimensional manifolds, whose knowledge may potentially improve inference. For example, one might expect high correlation between class labels of data points within the same cluster or nearby on a manifold. These, respectively, are the cluster and manifold assumptions for semi-supervised learning.

S. Sathiya Keerthi

Yahoo! Research 3333 Media Studios North Burbank, CA 91504, USA selvarak@yahoo-inc.com

We utilize the graph-based construction of semi-supervised kernels in [Sindhwani et al., 2005]. The data geometry is modeled as a graph whose vertices are the labeled and unlabeled examples, and whose edges encode appropriate neighborhood relationships. In intuitive terms, in the limit of infinite unlabeled data we imagine a convergence of this graph to the underlying geometric structure of the probability distribution generating the data. The smoothness enforced by regularization operators (such as the graph Laplacian) over functions on the vertices of this graph is transferred onto a Reproducing Kernel Hilbert space (RKHS) of functions defined over the entire data space. This gives rise to a new RKHS in which standard supervised kernel methods perform semisupervised inference. In this paper, we apply similar ideas for Gaussian processes, with an aim to draw the benefits of a Bayesian approach when only a small labeled set is available. The semi-supervised kernel of [Sindhwani et al., 2005] is motivated through Bayesian considerations, and used for performing Gaussian process inference. We apply expectation propagation (EP) (see [Rasmussen and Williams, 2006] and references therein) for approximating posterior processes and calculating evidence for model selection.

We point out some aspects of the proposed method:

1. Our method, hereafter abbreviated as SSGP, can be seen as providing a Bayesian analogue of Laplacian Support Vector Machines (LapSVM) and Laplacian Regularized Least Squares (LapRLS) proposed in [Sindhwani et al., 2005; Belkin et al., 2006] and semi-supervised logistic regression proposed in [Krishnapuram et al., 2004]. In this paper, we empirically demonstrate that when labeled examples are scarce, model selection by evidence in SSGP is a significant improvement over cross-validation in LapSVM and LapRLS.
2. Several graph-based Bayesian approaches incorporating unlabeled data have recently been proposed. Methods have been designed for transductive Bayesian learning using a graph-based prior in [Zhu et al., 2003; Kapoor et al., 2005]. Since the core probabilistic model in these methods is defined only over the finite collection of labeled and unlabeled inputs, out-of-sample extension to unseen test data requires additional follow-up procedures. By contrast, our approach possesses a Gaussian process model over the entire input space that provides natural out-of-sample prediction.
3. While the focus of this paper is to derive SSGP and verify its usefulness on binary classification tasks, we wish to

comment on its potential in the following respects: (1) SSGP also provides a general framework for other learning tasks, such as regression, multiple-class classification and ranking. (2) SSGP also produces class probabilities and confidence estimates. These can be used to design active learning schemes. (3) Efficient gradient-based strategies can be designed for choosing multiple model parameters such as regularization and kernel parameters.

We begin by briefly reviewing Gaussian process classification in Section 2 and then propose and evaluate SSGP in the following sections.

2 Background and Notation

In the standard formulation for learning from examples, patterns x are drawn from some space X, typically a subset of Rd and associated labels y come from some space Y. For ease of presentation, in this paper we will focus on binary classification, so that Y can be taken as {+1,-1}. We assume there is an unknown joint probability distribution PX×Y over the space of patterns and labels. A set of patterns {xi}l+u i=1 is drawn i.i.d from the marginal PX(x) = ∑Y PX×Y(x, y); the label yi associated with xi is drawn from the conditional distribution PY(y|xi) for the first l patterns. We are interested in leveraging the unlabeled patterns {xj }l+u j=l+1 for improved inference.

To set our notation for the discussion ahead, we will denote XL = {xi}li=1 as the set of labeled examples with associated labels YL = {yi}li=1 , XU = {xi}l+u i=l+1 as the set of unlabeled patterns. We further denote all the given patterns as XD, i.e., XD = XL ∪XU. Other patterns that are held out for test purposes (or have not been collected yet) are denoted as XT . The set of all patterns (labeled, unlabeled and test) is denoted as X, i.e., X = XD ∪XT , but we will often also use X to denote a generic dataset.

In the standard Gaussian process setting for supervised learning, one proceeds by choosing a covariance function K : X × X ↦→ ℜ. With any point x ∈ X, there is an associated latent variable fx. Given any dataset X, the latent variables fX = {fx}x∈X are treated as random variables in a zero-mean Gaussian process indexed by the data points. The covariance between fx and fz is fully determined by the coordinates of the data points x and z, and is given by K(x, z). Thus, the prior distribution over these variables is a multivariate Gaussian, written as: P(fX) = N(0,ΣXX) where ΣXX is the covariance matrix with elements K(x, z) with x, z ∈ X.

The Gaussian process classification model relates the variable fx at x to the label y through a probit noise model such as y = sign(fx + ξ) where ξ ∼ N(0, σ2n ). Given the latent variables fL associated with labeled data points, the class labels YL are independent Bernoulli variables and their joint likelihood is given by: P(YL|fL) = ∏li=1 P(yi|fxi ) = ∏li=1 Φ ( yifxi σn ) where Φ is the cumulative density function of the normal distribution.

Combining this likelihood term with the Gaussian prior for the latent variables associated with the labeled dataset XL, we obtain the posterior distribution: P(fL|YL) =

∏li=1 P(yi|fxi )N(0,ΣLL)/P(YL) where we use ΣLL as a shorthand for ΣXLXL . The normalization factor P(YL) = ∫ P(YL|fL)P(fL)dfL is known as the evidence for the model parameters (such as parameters of the covariance function and the noise level σ2n).

The posterior distribution above is non-Gaussian. To preserve computational tractability, a family of inference techniques can be applied to approximate the posterior as a Gaussian. Some popular methods include Laplace approximation, mean-field methods, and expectation propagation (EP). In this paper we will use the EP procedure, based on empirical findings that it outperforms Laplace approximation. In EP, the key idea is to approximate the non-Gaussian part in the posterior in the form of an un-normalized Gaussian, i.e. ∏li=1 P(yi|fxi ) ≈ c N(μ,A). The parameters c, μ,A are obtained by locally minimizing the Kullback-Liebler divergence between the posterior and its approximation.

With a Gaussian approximation to the posterior in hand, the distribution of the latent variable fxt at a test point xt, as given by the following integral, becomes a tractable quantity:

P(fxt |YL) = ∫ P(fxt |fL)P(fL|YL)dfL ≈ N(μt, σ2 t ), where μt = ΣTLtΣ-1 LL μ and σ2 t = K(xt, xt)-ΣTLt (Σ-1 LL - Σ-1 LL A Σ-1 LL) ΣLt. Here, the column vector ΣLt = [K(xt, x1), . . . ,K(xt, xl)]T and ΣLL is the gram matrix of K over the labeled inputs. The conditional distribution P(fxt |fL) is a multi-variate Gaussian with mean ΣTLtΣ-1 LLfL and covariance matrix K(xt , xt) - ΣTLtΣ-1 LLΣLt.

Finally, one can compute the Bernoulli distribution over the test label yt, which for the probit noise model becomes P(yt|YL) = Φ (μt/√σ2n +σ2 t ). For more details on Gaussian processes, we point the reader to [Rasmussen and Williams, 2006] and references therein.

Our interest now is to utilize unlabeled data for Gaussian process inference.

3 Semi-supervised Gaussian Processes

3.1 Kernels for Semi-supervised Learning

A symmetric positive semi-definite function K(·, ·) can serve as the covariance function of a Gaussian process and also as a kernel function of a deterministic Reproducing Kernel Hilbert Space (RKHS) H of functions X → ℜ. The RKHS and the GP associated with the same function K(·, ·) are closely related through a classical isometry between H and a Hilbert space of random variables spanned by the GP (i.e. random variables of the form ∑k αkfxk and their mean square limits) 1 . In this section, we review the construction of an RKHS that is adapted for semi-supervised learning of deterministic classifiers [Sindhwani et al., 2005]. The kernel of this RKHS is then used as the covariance function of SSGP.

In the context of learning deterministic classifiers, for many choices of kernels, the norm ‖f‖H can be interpreted as a smoothness measure over functions f in H. The norm can then be used to impose a complexity structure over H and learning algorithms can be developed based on minimizing functionals of the form: V (f, XL, YL) + γ‖f‖2H, where V is a loss function that measures how well f fits the data. Remarkably, for loss functions that only involve f through point evaluations, a representer theorem states that the minimizer is of the form f(x) = ∑li=1 αiK(x, xi) so that only the αi remain to be computed. This provides the algorithmic basis of algorithms like Regularized Least Squares (RLS) and Support Vector Machines (SVM), for squared loss and hinge loss, respectively. In a semi-supervised setting, unlabeled data may suggest alternate measures of complexity, such as smoothness with respect to data manifolds or clusters. Thus, if the space H contains functions that are smooth in these respects, it is only required to re-structure H by refining the norm using labeled and labeled data XD. A general procedure to perform this operation is as follows: we define ˜H to be the space of functions from H with the modified data-dependent inner product: 〈f, g〉 ˜H = 〈f, g〉H + f T Mg, where f and g are the vectors {f(x)}x∈XD and {g(x)}x∈XD respectively, and M is a symmetric positive semi-definite matrix. The norm induced by this modified inner product combines the original ambient smoothness with an intrinsic smoothness measure defined in terms of the matrix M. The definition of M is based on the construction of a data adjacency graph that acts as an empirical substitute of the intrinsic geometry of the marginal PX . M can be derived from the graph Laplacian L; for example, M = L or M = ∑p βpLp are popular choices for families of graph regularizers. The Laplacian matrix of the graph implements an empirical version of the Laplace-Beltrami operator when the underlying space is a Riemannian manifold. This operator measures smoothness with respect to the manifold. The space ˜H can be shown to be an RKHS. With the newdata-dependent norm, ˜Hbecomes better suited, as compared to the original function space H, for semi-supervised learning tasks where the cluster/manifold assumptions hold. The form of the new kernel ˜K associated with ˜H can be derived (see [Sindhwani et al., 2005]) in terms of the kernel function K using reproducing properties of an RKHS and orthogonality arguments, and is given by:

1 For an RKHS function f, the notation f(x) means the function f evaluated at x, whereas for a GP fx refers to the latent random variable associated with x.

˜K(x, z) =K(x, z) -ΣTDx(I +MΣDD)-1MΣDz (1) where ΣDx (and similarly ΣDz) denotes the column vector: [K(x1, x), . . . ,K(xl+u, x)]T . Laplacian SVM and Laplacian RLS solve regularization problems in the RKHS ˜H with hinge and squared loss respectively.

3.2 Data-dependent Conditional Prior

SSGP uses the semi-supervised kernel function ˜K defined above as a covariance function for Gaussian process learning. Thus, in SSGP the covariance between fxi and fxj not only depends on the ambient coordinates of xi and xj , but also on geometric properties of the set XD. In this section, we discuss the derivation of ˜K fromBayesian considerations.

Our general approach is summarized as follows. We begin with a standard Gaussian process. Given unlabeled and labeled data XD, we define a joint probability distribution over the associated latent process variables fD and an abstract collection of random variables, denoted as G, whose instantiation is interpreted as realization of a certain geometry. Then, conditioning on the geometry of unlabeled data through these variables, a Bayesian update gives a posterior over the latent variables. SSGP is the resulting posterior process, which incorporates the localized spatial knowledge of the data via Bayesian learning.

There are many ways to define an appropriate likelihood evaluation for the geometry variables G. One simple formulation for P(G|fD) is given by:

where pD = [P(y = 1|fx1 ), . . . ,P(y = 1|fxl+u )]T = [Φ(fx1 ), . . . , Φ(fxl+u )]T is a column vector of conditional label probabilities for latent variables associated with XD, M is a graph-based matrix such as the graph Laplacian in Section 3.1, and Z is a normalization factor. P(G|fD) may be interpreted as a measure of how much fD corroborates with a given geometry, computed in terms of the smoothness of the associated conditional distributions with respect to unlabeled data. This implements a specific assumption about the connection between the true underlying unknown conditional and marginal distributions - that if two points x1, x2 ∈ X are close in the intrinsic geometry of PX , then the conditional distributions P(y|x1) and P(y|x2) are similar, i.e., as a function of x, P(y|x) is smooth with respect to PX .

Since the likelihood form (Eqn 2) leads to a non-Gaussian posterior, a natural substitute is to use an un-normalized Gaussian form, as commonly used with EP approximations. The posterior is then approximated as:

Such a form captures the functional dependency between the latent and the geometry variables while rendering subsequent computations tractable. The value of c is inconsequential in defining this approximate posterior distribution (since c cancels due to the normalizing term P(G)), although it is important for evidence computations. In Section 3.3, we further comment on the role of the c and propose the use of partial evidence for model selection. The matrix M is approximated by the Laplacian matrix of the data-adjacency graph, to correspond to the deterministic algorithms introduced in [Sindhwani et al., 2005; Belkin et al., 2006]. We note that c,M can alternatively be computed from EP calculations, leading to a novel graph regularizer and tractable computations for the full evidence. We outline more details in this direction in [Chu et al., 2006].

To proceed further, we make the assumption that given fD, G is independent of latent variables at other points, i.e., if the data set X contains XD and a set of unseen test points XT , we have:

This assumption allows out of sample extension without the need to recompute the graph for a new dataset.

The posterior distribution of fX given G is: P(fX|G) ∝ P(G|fX)P(fX) = P(G|fD)P(fX).

The prior distribution for fX is a Gaussian N(0,ΣXX) given by the standard Gaussian processes. In the form of block matrices, the prior P(fX) can be written as follows: fX = [ fD fT ] ∼ N ([ 00 ] , [ ΣDD ΣDT ΣTDT ΣTT ]), where we use the shorthand D for XD and T for XT . The posterior distribution of fX conditioned on G can be written as a zero-mean Gaussian distribution P(fX|G) ∝ exp(- 12 f TX ˜Σ-1 XX fX) where

Proposition: Given Eqn 3, for any finite collection of data points X, the random variables fX = {f(x)}x∈X conditioned on G have a multivariate normal distribution N(0, ˜ΣXX), where ˜ΣXX is the covariance matrix whose elements are given by evaluating the following kernel function ˜K : X ×X ↦→ℜ,

for x, z ∈ X. Here ΣDx denotes the column vector [K(x1, x), . . . , K(xn, x)]T .

This proposition shows that the Gaussian process conditioned on the geometry variable G is a Gaussian process with a modified covariance function ˜K. A proof of this result uses straightforward matrix algebra and is omitted for brevity.

SSGP is the posterior process obtained by conditioning the original GP with respect to G. Note that the form of its covariance function ˜K is the same as in Eqn 1, which is derived from properties of RKHS.

3.3 Model Selection

Model selection for SSGP involves choosing the kernel parameters and the noise variance σn (see Section 2). The definition of ˜K is based on the choice of a covariance function K and a graph regularization matrix M. As in [Sindhwani et al., 2005], in this paper we restrict our attention to the following choices: K(x, z) = exp (- ‖x-z‖2 2σ2 ) , M = γI γA Lp and use the kernel 1 γA ˜K. The parameters γA and γI balance ambient and intrinsic covariance. The parameters related to the computation of the graph Laplacian L are - the number of nearest neighbors NN and the graph adjacency matrix W. We set Wij = exp (- ‖xi-xj ‖2 2σ2 t ), if xi and xj are adjacent in a NN-nearest neighbor graph and zero otherwise.

Denote φ as the collection of model parameters. The optimal values of φ are determined by maximizing the evidence P(YL|G, φ) which is available from EP computations.

Model selection is particularly challenging in semisupervised settings in the presence of few labeled examples. Popular model selection techniques like cross-validation (for deterministic methods like Laplacian SVM/RLS) require subsets of the already-scarce labeled data to be held out from training. Moreover, for graph-based semi-supervised learning, a proper cross-validation should also exclude the held out subset from the adjacency graph instead of simply suppressing labels, in order to ensure good out-of-sample extension. This adds a major expense since the semi-supervised kernel in Eqn 1 needs to be recomputed multiple times. Also, since cross-validation is based on counts, it may often be unable to uniquely identify a good set of parameters. By contrast, evidence maximization neither needs to suppress expensive labels nor needs to hold out labeled examples from the graph. As a continuous function of many model parameters, it is more precise in parameter selection (demonstrated in Section 4) and also amenable to gradient-based techniques. In addition to these benefits, we note the novel possibility of employing unlabeled data for model selection by maximizing the full evidence P(YL, G|φ) = P(YL|G, φ)P(G|φ). The latter term may be computed as P(G|φ) = ∫ P(G|fD)P(fD)dfD. Given Eqn 3, one can immediately derive logP(G|φ) = log c - 12 log det(MΣDD + I) where I is the identity matrix. For simplicity, in this paper we focus on comparing standard evidence maximization in SSGP with standard cross-validation in Laplacian SVM/RLS.

4 Experiments

We performed experiments on a synthetic two-dimensional dataset and four real world datasets for binary classification problems. The statistics of these datasets are described in Table 1.

Synthetic Data

The toy 2-D dataset MOONS, meant to visually demonstrate SSGP, is shown in Figure 1 as a collection of unlabeled examples (small black dots) and two labeled examples per class (large colored points). The classification boundary and the contours of the mean of the predictive distribution over the unit square are shown for standard GP and SSGP (Figure 1(a,c)). These plots demonstrate how SSGP utilizes unlabeled data for classification tasks. The uncertainty in prediction (Figure 1(d)) respects the geometry of the data, increasing anisotropically as one moves away from the labeled examples. Figure 1(b) also demonstrates evidence-based model selection.

Real World Data sets

For all the real world data sets (except 3VS5), we generated a fixed training/test split by randomly drawing one-fourth of the original data set into a test set of unseen examples, and retaining the rest as a training set of labeled and unlabeled examples. Learning curves were plotted for varying amount of labeled data, randomly chosen from the training set. For 3VS5, we chose the exact data splits used in [Lawrence and Jordan, 2004] to facilitate comparison between algorithms.

To reduce the complexity of model selection, we fix NN = 10 and p = 2 for 3VS5, SET1 and NN = 50 and p = 5 for

-1.5

-1

-0.5

0

0.5

1

1.5

2

2.5

-1 -0.5

0

0.5

1

1.5

2

2.5

Figure 1: MOONS: The mean of the predictive distribution of supervised GP is shown in graph (a). Based on maximum evidence, the best settings are found at log2 σt = -3.0 and log2 σ = -2.25, shown as a cross in graph (b). The results of SSGP with the best settings are shown in graph (c) and (d).

PCMAC, REUTERS. These values are based on experimental experience from [Sindhwani et al., 2005] with image and text data sets. We used weighted graphs with Euclidean distance as the graph similarity measure, and Gaussian weights with width (σt) set to the mean distance between adjacent vertices. The behavior of evidence-based model selection for SSGP and cross-validation (CV) based model selection for Laplacian SVM was investigated over a range of values for the parameters σ, γA, γI . For each dataset, we computed the mean length of feature vectors (σ0) in the training set, and probed σ in the range [ σ0 4 σ0 2 σ0 2σ0 4σ0 ]; the range for γA was [10-6 10-4 10-2 1 100] and the choices for ratio γI γA were [0 1 10 100 1000] (note that a choice of 0 ignored unlabeled data and reduces the algorithm to its standard supervised mode). The noise parameter σn in the probit model for class labels was set to 10-4 in all experiments. Note that this parameter allows SSGP to potentially deal with label noise.

1. BENEFIT OF UNLABELED DATA: In Figure 2, we plot the mean error rates on the test sets for the four datasets as a function of the number of labeled examples (expressed in terms of probability of finding a labeled example in the training set) for SSGP and standard supervised GP (which ignores unlabeled data). Figure 3 shows the corresponding curves for performance on the unlabeled data. The solid curves show the mean and standard deviation of the minimum error rates for SSGP and GP over the set of parameters σ, γA, γI (γI = 0 for GP) and the dashed curves show the mean and standard deviation of error rates at parameters chosen by maximizing evidence. The mean and standard deviations are computed over 10 random draws for every choice of the amount of labeled data. We make several observations: (a) By utilizing unlabeled data, SSGP makes significant performance improvements over standard GP on both the test and unlabeled sets, the gap being larger on the unlabeled set. This holds true across the entire span of varying amounts of labeled data for all datasets, except PCMAC where the gap seems to converge faster. (b) Performance based on parameters chosen by evidence based model selection is much closer to the optimal performance for SSGP than for GP. The performance curves for SSGP have lesser variance.

2. EVIDENCE MAXIMIZATION VERSUS CV: We next compare evidence-based model selection in SSGP with CV based model selection in Laplacian SVM. In Figure 4, we plot the mean error rates on the test sets for the four datasets as a function of the number of labeled examples for SSGP and Laplacian SVM, both of which utilize unlabeled data through the same kernel. Figure 5 shows the corresponding curves for performance on the unlabeled data. The solid curves show the mean and standard deviation of the minimum error rates for SSGP and Laplacian SVM over the set of parameters σ, γA, γI; and the dashed curves show corresponding curves at a parameter setting chosen by evidencemaximization and CV for SSGP and Laplacian SVM respectively. The mean and standard deviations are computed over 10 random draws for every choice of the amount of labeled data. We used 5-fold CV for each labeled set, except those with 10 or fewer examples, in which case leave-one-out cross validation was used. It is important to note that our CV protocol for Laplacian SVMs only suppresses labels but does not exclude the labeled examples from the graph. We make the following observations: (a) In terms of best performance over the range of parameters (i.e the solid curves), SSGP and Laplacian SVM return nearly identical mean error rates, except in 3VS5, where when given very few labeled examples, SSGP outperforms LapSVM. (b) By looking at the performance curves at parameters chosen by their corresponding model selection strategies (i.e the dashed curves), the superiority of evidence maximization in SSGP over CV in Laplacian SVM becomes quite evident. This is true for both test and unlabeled set performance. (c) The quality of CV based performance of Laplacian SVM is significantly better over unlabeled data as compared to that over test data, indicating that CV drives the model selection towards parameters that favor transduction at the expense of semi-supervised induction. These experiments show that evidence maximization returns significantly better performance than CV on both the test and unlabeled sets.

3. COMPARISON WITH OTHER METHODS: Finally, in Figure 6, we superimpose the SSGP performance curves over the results of the Null Category Noise Model (NCNM), Informative Vector Machine (IVM), SVM, and transductive SVM (TSVM) plotted in [Lawrence and Jordan, 2004]. The same experimental protocol and data splits were used. We are encouraged to see that SSGP outperforms all algorithms tested in this experiment.

5 Conclusion

To conclude, we have presented semi-supervised Gaussian process classifiers based on a data-dependent covariance function that is adapted to the geometry of unlabeled data. We have empirically demonstrated the utility of SSGP on several learning tasks, and observed the benefits of evidence-based model selection in comparison to cross-validation techniques in Laplacian SVM/RLS.