nips nips2005 nips2005-92 knowledge-graph by maker-knowledge-mining

92 nips-2005-Hyperparameter and Kernel Learning for Graph Based Semi-Supervised Classification

Source: pdf

Author: Ashish Kapoor, Hyungil Ahn, Yuan Qi, Rosalind W. Picard

Abstract: There have been many graph-based approaches for semi-supervised classiﬁcation. One problem is that of hyperparameter learning: performance depends greatly on the hyperparameters of the similarity graph, transformation of the graph Laplacian and the noise model. We present a Bayesian framework for learning hyperparameters for graph-based semisupervised classiﬁcation. Given some labeled data, which can contain inaccurate labels, we pose the semi-supervised classiﬁcation as an inference problem over the unknown labels. Expectation Propagation is used for approximate inference and the mean of the posterior is used for classiﬁcation. The hyperparameters are learned using EM for evidence maximization. We also show that the posterior mean can be written in terms of the kernel matrix, providing a Bayesian classiﬁer to classify new points. Tests on synthetic and real datasets show cases where there are signiﬁcant improvements in performance over the existing approaches. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 One problem is that of hyperparameter learning: performance depends greatly on the hyperparameters of the similarity graph, transformation of the graph Laplacian and the noise model. [sent-7, score-0.798]

2 We present a Bayesian framework for learning hyperparameters for graph-based semisupervised classiﬁcation. [sent-8, score-0.196]

3 Given some labeled data, which can contain inaccurate labels, we pose the semi-supervised classiﬁcation as an inference problem over the unknown labels. [sent-9, score-0.2]

4 The hyperparameters are learned using EM for evidence maximization. [sent-11, score-0.403]

5 We also show that the posterior mean can be written in terms of the kernel matrix, providing a Bayesian classiﬁer to classify new points. [sent-12, score-0.282]

6 The basic idea is to ﬁrst create a graph with the labeled and unlabeled data points as the vertices and with the edge weights encoding the similarity between the data points. [sent-15, score-0.674]

7 The aim is then to obtain a labeling of the vertices that is both smooth over the graph and compatible with the labeled data. [sent-16, score-0.42]

8 Often the smoothness constraints on the labels are imposed using a transformation of the graph Laplacian and the parameters of the transformation affect the performance. [sent-18, score-0.712]

9 Further, there might be other parameters in the model, such as parameters to address label noise in the data. [sent-19, score-0.336]

10 Finding a right set of parameters is a challenge, and usually the method of choice is cross-validation, which can be prohibitively expensive for real-world problems and problematic when we have few labeled data points. [sent-20, score-0.21]

11 Most of the methods ignore the problem of learning hyperparameters that determine the similarity graph and there are only a few approaches that address this problem. [sent-21, score-0.356]

12 [8] propose learning non-parametric transformation of the graph Laplacians using semidefinite programming. [sent-23, score-0.296]

13 This approach assumes that the similarity graph is already provided; thus, it does not address the learning of edge weights. [sent-24, score-0.26]

14 This paper provides a new way to learn the kernel and hyperparameters for graph based semi-supervised classiﬁcation, while adhering to a Bayesian framework. [sent-26, score-0.398]

15 We use the evidence to simultaneously tune the hyperparameters that deﬁne the structure of the similarity graph, the parameters that determine the transformation of the graph Laplacian, and any other parameters of the model. [sent-28, score-0.888]

16 An additional contribution is a new EM algorithm to learn the hyperparameters for the edge weights, the parameters of the transformation of the graph spectrum. [sent-32, score-0.499]

17 More importantly, we explicitly model the level of label noise in the data, while [9] does not do. [sent-33, score-0.254]

18 We provide what may be the ﬁrst comparison of hyperparameter learning with cross-validation on state-of-the-art algorithms (LLGC [6] and harmonic ﬁelds [7]). [sent-34, score-0.367]

19 Our model assumes that the hard labels ti depend upon hidden soft-labels yi for all i. [sent-45, score-0.324]

20 The posterior can be written as: p(tU |D) = p(tU |y)p(y|D) (1) y In this paper, we propose to ﬁrst approximate the posterior p(y|D) and then use (1) to classify the unlabeled data. [sent-49, score-0.463]

21 Similar to the spirit of graph regularization [5] we use similarity graphs and their transformed Laplacian to induce priors on the soft labels y. [sent-52, score-0.446]

22 In the following subsections ﬁrst we describe the prior and the likelihood in detail and then we show how evidence maximization can be used to learn hyperparameters and other parameters in the model. [sent-55, score-0.625]

23 1 Priors and Regularization on Graphs The prior plays a signiﬁcant role in semi-supervised learning, especially when there is only a small amount of labeled data. [sent-57, score-0.217]

24 The prior imposes a smoothness constraint and should be such that it gives higher probability to the labelings that respect the similarity of the graph. [sent-58, score-0.203]

25 The data points are the nodes of the graph and edge-weights between the nodes are based on similarity. [sent-60, score-0.225]

26 Usually, a transformation r(∆) = i=1 r(λi )vi vi that modiﬁes the spectrum of ∆ is used as a regularizer. [sent-71, score-0.223]

27 Also, different choices of transformation functions lead to different semisupervised learning algorithms. [sent-77, score-0.209]

28 For example, the approach based on Gaussian ﬁelds and harmonic functions (Harmonic) [7] can be thought of as using the transformation r(λ) = λ on the combinatorial Laplacian without any noise model. [sent-78, score-0.434]

29 Therefore, it is easy to see that most of these algorithms can exploit the proposed evidence maximization framework. [sent-80, score-0.353]

30 2 The Likelihood Assuming conditional independence of the observed labels given the hidden soft labels, the n likelihood p(tL |y) can be written as p(tL |y) = i=1 p(ti |yi ). [sent-84, score-0.245]

31 The likelihood models the probabilistic relation between the observed label ti and the hidden label yi . [sent-85, score-0.557]

32 While most people tend to model label errors with a linear or quadratic slack in the likelihood, it has been noted that such an approach does not address the cases where label errors are far from the decision boundary [2]. [sent-87, score-0.37]

33 The above described likelihood explicitly models the labeling error rate; thus, the model should be more robust to the presence of label noise in the data. [sent-90, score-0.446]

34 We use EP to approximate the posterior as a Gaussian and then equation (1) can be used to classify unlabeled data points. [sent-96, score-0.348]

35 In our case, EP starts with the prior deﬁned in (2) and incorporates likelihood to approximate the posterior p(y|D) ∼ N (¯ , Σy ). [sent-99, score-0.283]

36 4 Hyperparameter Learning We use evidence maximization to learn the hyperparameters. [sent-101, score-0.353]

37 Denote the parameters of the kernel as ΘK and the parameters of transformation of the graph Laplacian as ΘT . [sent-102, score-0.493]

38 The main challenge is that the gradient of evidence is not easy to compute. [sent-107, score-0.318]

39 Previously, an EM algorithm for hyperparameter learning [2] has been derived for Gaussian Process classiﬁcation. [sent-108, score-0.21]

40 The M-step consists of maximizing the lower bound: F = q(y) log y =− p(y|X, Θ)p(tL |y, Θ) q(y) q(y) log q(y) + y q(y) log N (y; 0, r(∆)−1 ) y n + q(yi ) log ( + (1 − 2 )Φ(yi · ti )) ≤ p(tL |X, Θ) i=1 yi The EM procedure alternates between the E-step and the M-step until convergence. [sent-111, score-0.475]

41 y • M-Step: Update Θi+1 = arg maxΘ y q(y) log p(y|X,Θ)p(tL |y,Θ) q(y) In the M-step the maximization with respect to the Θ cannot be computed in a closed form, but can be solved using gradient descent. [sent-113, score-0.198]

42 When using the linear transformation r(λ) = λ + δ on the Laplacian ∆, the prior p(y|X, Θ) can be written as N (0, (∆ + δI)−1 ). [sent-115, score-0.231]

43 Especially, when the evidence curve is ﬂat and the initial values are far from the optimum, we found that the EM algorithm provided very small steps, thus, taking a long time to converge. [sent-118, score-0.274]

44 Essentially as the gradients of the evidence are hard to compute, they can be approximated by the gradients of the lower bound and can be used in any gradient ascent procedure. [sent-120, score-0.386]

45 −4 −4 −4 Evidence curves (odd vs even, δ=10 , ε=0) Evidence curves (moon data,δ = 10 ,ε=0. [sent-121, score-0.428]

46 1) Evidence curves (PC vs MAC, δ = 10 , ε=0) 10 0 N=5 N=15 N=25 N=40 −5 −10 −15 −20 −20 −30 −30 −40 −50 −40 −20 N=5 N=15 N=35 N=50 −10 Log evidence −10 Log evidence 0 Log evidence 0 N=1 N=6 N=10 N=20 5 −60 −25 −50 −30 0. [sent-122, score-1.142]

47 2 Hyperparameter (γ) for the kernel (b) Recognition and log evidence (moon data N=10) (c) Recognition and log evidence (odd vs even N=25) Recognition and log evidence (PC vs MAC N=35) 100 95 90 85 80 75 0 0. [sent-140, score-1.586]

48 2 Hyperparameter (γ) for the kernel (e) (f) Figure 1: Evidence curves showing similar properties across different datasets (half-moon, odd vs even and PC vs MAC). [sent-145, score-0.816]

49 The top row ﬁgures (a), (b) and (c) show the evidence curves for different amounts of labeled data per class. [sent-146, score-0.582]

50 The bottom row ﬁgures (d), (e) and (f) show the correlation between recognition accuracy on unlabeled points and the evidence. [sent-147, score-0.319]

51 5 Classifying New Points Since we compute a posterior distribution over the soft-labels of the labeled and unlabeled data points, classifying a new point is tricky. [sent-149, score-0.484]

52 That is: ¯ y = r(∆)−1 a where, a ∈ I (n+m)×1 R Further, if the similarity matrix K is a valid kernel matrix1 then we can write the mean directly in terms of the linear combination of the columns of K: ¯ y = KK −1 r(∆)−1 a = Kb T (4) −1 −1 Here, b = [b1 , . [sent-151, score-0.188]

53 3 Experiments We performed experiments to evaluate the three main contributions of this work: Bayesian hyperparameter learning, classiﬁcation of unseen data points, and robustness with respect to noisy labels. [sent-156, score-0.324]

54 For all the experiments we use the linear transformation r(λ) = λ + δ either on normalized Laplacian (EP-NL) or the combinatorial Laplacian (EP-CL). [sent-157, score-0.187]

55 Two real-world datasets were the handwritten digits and the newsgroup data from [7]. [sent-159, score-0.286]

56 We evaluated the task of classifying odd vs even digits (15 labeled, 485 unlabeled and rest new 1 The matrix K is the adjacency matrix of the graph and depending upon the similarity criterion might not always be positive semi-deﬁnite. [sent-160, score-0.921]

57 Evidence curves (affect data, K=3, δ=10−4) −4 Evidence curves (affect data, δ = 10 , ε = 0. [sent-162, score-0.216]

58 05) 0 −5 N=5 N=15 N=25 N=40 −10 −15 Log evidence −20 −30 −40 N=5 N=15 N=25 N=40 −10 −15 −20 Log evidence −10 Log evidence Evidence curves (affect data, K = 3, ε = 0. [sent-163, score-0.93]

59 The ﬁgures (a), (b) and (c) show the evidence curves for different amount of labeled data per class for the three different parameters in the model. [sent-176, score-0.623]

60 The ﬁgures in the top row (a) and (b) show error rates on unlabeled points and the bottom row ﬁgures (c) and (d) on the new points. [sent-178, score-0.286]

61 (d) (unseen) points per class) and classifying PC vs MAC (5 labeled, 895 unlabeled and rest as new (unseen) points per class). [sent-182, score-0.657]

62 An RBF kernel was used for handwritten digits, whereas x Tx 1 kernel K(xi , xj ) = exp[− γ (1 − |xii ||xjj| )] was used on 10-NN graph to determine similarity. [sent-183, score-0.435]

63 The labels in this database are suspected to be noisy because of human labeling. [sent-186, score-0.222]

64 Hyperparameter learning: Figure 1 (a), (b) and (c) plots log evidence versus kernel parameters that determine the similarity graphs for the different datasets with varying size of the labeled set per class. [sent-188, score-0.865]

65 Figure 2 (a), (b) and (c) plots the log evidence versus the noise parameter ( ), the kernel parameter (k in k-NN) and the transformation parameter (δ) for the affect dataset. [sent-190, score-0.775]

66 First, we see that the evidence curves generated with very little data are ﬂat and as the number of labeled data points increases we see the curves become peakier. [sent-191, score-0.73]

67 When there is very little labeled data, there is not much information available for the evidence maximization framework to prefer one parameter value over the other. [sent-192, score-0.522]

68 With more labeled data, the evidence curves become more informative. [sent-193, score-0.551]

69 Figure 1 (d), (e) and (f) show the correlation between the evidence curves and the recognition rate on the unlabeled data and reveal that the recognition over the unlabeled data points is highly correlated with the evidence. [sent-194, score-0.919]

70 Note that both of these effects are observed across all the datasets as well as all the different parameters, justifying evidence maximization for hyperparameter learning. [sent-195, score-0.61]

71 We performed experiments on the handwritten digits and on the newsgroup data and compared with 1-NN, LLGC and Harmonic approach. [sent-209, score-0.239]

72 The kernel parameters for both LLGC and Harmonic were estimated using leave one out cross validation2 . [sent-210, score-0.189]

73 We performed experiments with both the normalized (EP-NL) and the combinatorial Laplacian (EP-CL) with the proposed framework to classify the digits and the newsgroup data. [sent-213, score-0.285]

74 The approximate gradient descent was ﬁrst used to ﬁnd an initial value of the kernel parameter for the EM algorithm. [sent-214, score-0.207]

75 All three parameters were learnt and the top row in ﬁgure 3 shows the average error obtained for 5 different runs on the unlabeled points. [sent-215, score-0.297]

76 On the task of classifying odd vs even the error rate for EP-NL was 14. [sent-216, score-0.48]

77 Since the prior in EP-NL is determined using the normalized Laplacian and there is no label noise in the data, we expect EP-NL to at least work as well as LLGC (16. [sent-223, score-0.302]

78 Handling label noise: Figure 4(a) shows a synthetic dataset with noisy labels. [sent-238, score-0.271]

79 We performed semi-supervised classiﬁcation both with and without the likelihood model given in (3) and the EM algorithm was used to tune all the parameters including the noise ( ). [sent-239, score-0.219]

80 Besides modifying the spectrum of the Laplacian, the transformation parameter δ can also be considered as latent noise and provides a quadratic slack for the noisy labels [2]. [sent-240, score-0.478]

81 It was suspected that due to the manual labeling the affect dataset might have some label noise. [sent-245, score-0.435]

82 To conﬁrm this and as a sanity check, we ﬁrst plotted evidence using all the available data. [sent-246, score-0.274]

83 Figure 5(a) shows the plot for the evidence against the noise parameter ( ). [sent-248, score-0.364]

84 From the ﬁgure, we see that the evidence peaks at = 0. [sent-249, score-0.274]

85 Figure 5(b) shows comparisons with other semi-supervised (LLGC and SVM with graph kernel) and supervised methods (SVM with RBF kernel) for different sizes of the labeled dataset. [sent-251, score-0.323]

86 Each point in the graph is the average error on 20 random splits of the data, where the error bars represent the standard error. [sent-252, score-0.274]

87 We used the same transformation r(λ) = λ + δ on the graph kernel in the semi-supervised SVM. [sent-254, score-0.411]

88 When the number of labeled points are small, both 2 Search space for σ (odd vs even) was 100 to 400 with increments of 10 and for γ (PC vs MAC) was 0. [sent-256, score-0.699]

89 1 45 EP−NL LLGC SVM (RBF) SVM (N−Laplacian) Evidence curve for the whole affect data (K=3, δ=10−4) −60 Error on unlabeled data 40 −65 Log evidence −70 −75 −80 −85 35 EP−NL (N = 80) 30 25 Harmonic (N = 92) 20 −90 0. [sent-259, score-0.527]

90 5 Number of labels per class Error rate on unlabeled points (1 vs 2) (b) (c) Figure 5: (a) Evidence vs noise parameter plotted using all the available data in the affect dataset. [sent-272, score-1.021]

91 05 suggests that there is around 5% label noise in the data. [sent-274, score-0.254]

92 (b) Performance comparison of the proposed approach with LLGC, SVM using graph kernel and the supervised SVM (RBF kernel) on the affect dataset which has label noise. [sent-275, score-0.559]

93 (c) Comparison of the proposed EM method for hyperparameter learning with the result reported in [7] using label entropy minimization. [sent-277, score-0.374]

94 One of the reasons is when you have few labels the probability of the labeled set of points containing a noisy label is low. [sent-280, score-0.578]

95 As the size of the labeled set increases the labeled data has more noisy labels. [sent-281, score-0.398]

96 As the number of labels increase, the evidence curve turns informative and EP-NL starts to learn the label noise correctly, outperforming the other Both the SVMs show competitive performance with more labels but still are worse than EP-NL. [sent-283, score-0.824]

97 Finally, we also test the method on the task of classifying “1” vs “2” in the handwritten digits dataset. [sent-284, score-0.414]

98 With 40 labeled examples per class (80 total labels and 1800 unlabeled), EP-NL obtained an average recognition accuracy of 99. [sent-285, score-0.388]

99 43% reported in [7], where the hyperparameter were learnt by minimizing label entropy with 92 labeled and 2108 unlabeled examples. [sent-289, score-0.758]

100 The results indicate that evidence maximization works well for learning hyperparameters, including the amount of label noise in the data. [sent-291, score-0.607]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('llgc', 0.383), ('evidence', 0.274), ('vs', 0.212), ('hyperparameter', 0.21), ('ep', 0.21), ('tl', 0.195), ('unlabeled', 0.174), ('labeled', 0.169), ('mac', 0.168), ('label', 0.164), ('laplacian', 0.161), ('harmonic', 0.157), ('graph', 0.154), ('transformation', 0.142), ('hyperparameters', 0.129), ('odd', 0.122), ('kernel', 0.115), ('labels', 0.114), ('curves', 0.108), ('newsgroup', 0.104), ('rbf', 0.103), ('em', 0.103), ('ti', 0.102), ('ipping', 0.1), ('labeling', 0.097), ('noise', 0.09), ('digits', 0.084), ('nl', 0.084), ('pc', 0.082), ('affect', 0.079), ('maximization', 0.079), ('log', 0.075), ('classi', 0.075), ('posterior', 0.074), ('yi', 0.073), ('similarity', 0.073), ('points', 0.071), ('cl', 0.071), ('classifying', 0.067), ('semisupervised', 0.067), ('zhu', 0.066), ('noisy', 0.06), ('gures', 0.06), ('nn', 0.058), ('tu', 0.058), ('svm', 0.056), ('unseen', 0.054), ('gaussian', 0.054), ('bayesian', 0.054), ('likelihood', 0.054), ('classify', 0.052), ('vi', 0.051), ('handwritten', 0.051), ('tn', 0.05), ('picard', 0.048), ('suspected', 0.048), ('approximate', 0.048), ('prior', 0.048), ('dataset', 0.047), ('datasets', 0.047), ('combinatorial', 0.045), ('gradient', 0.044), ('slack', 0.042), ('labelings', 0.042), ('kapoor', 0.042), ('error', 0.041), ('written', 0.041), ('parameters', 0.041), ('learnt', 0.041), ('tr', 0.04), ('smoothness', 0.04), ('graphs', 0.04), ('recognition', 0.04), ('rate', 0.038), ('moon', 0.038), ('outperforming', 0.038), ('bars', 0.038), ('soft', 0.036), ('increments', 0.035), ('laplacians', 0.035), ('propagation', 0.035), ('upon', 0.035), ('lafferty', 0.034), ('accuracy', 0.034), ('tune', 0.034), ('gradients', 0.034), ('leave', 0.033), ('edge', 0.033), ('cation', 0.033), ('ghahramani', 0.033), ('per', 0.031), ('svms', 0.031), ('inference', 0.031), ('elds', 0.03), ('spectrum', 0.03), ('starts', 0.03), ('incorporates', 0.029), ('xu', 0.029), ('kij', 0.029), ('regularization', 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 92 nips-2005-Hyperparameter and Kernel Learning for Graph Based Semi-Supervised Classification

Author: Ashish Kapoor, Hyungil Ahn, Yuan Qi, Rosalind W. Picard

2 0.23401718 42 nips-2005-Combining Graph Laplacians for Semi--Supervised Learning

Author: Andreas Argyriou, Mark Herbster, Massimiliano Pontil

Abstract: A foundational problem in semi-supervised learning is the construction of a graph underlying the data. We propose to use a method which optimally combines a number of differently constructed graphs. For each of these graphs we associate a basic graph kernel. We then compute an optimal combined kernel. This kernel solves an extended regularization problem which requires a joint minimization over both the data and the set of graph kernels. We present encouraging results on different OCR tasks where the optimal combined kernel is computed from graphs constructed with a variety of distances functions and the ‘k’ in nearest neighbors. 1

3 0.20327395 123 nips-2005-Maximum Margin Semi-Supervised Learning for Structured Variables

Author: Y. Altun, D. McAllester, M. Belkin

Abstract: Many real-world classiﬁcation problems involve the prediction of multiple inter-dependent variables forming some structural dependency. Recent progress in machine learning has mainly focused on supervised classiﬁcation of such structured variables. In this paper, we investigate structured classiﬁcation in a semi-supervised setting. We present a discriminative approach that utilizes the intrinsic geometry of input patterns revealed by unlabeled data points and we derive a maximum-margin formulation of semi-supervised learning for structured variables. Unlike transductive algorithms, our formulation naturally extends to new test points. 1

4 0.2009315 30 nips-2005-Assessing Approximations for Gaussian Process Classification

Author: Malte Kuss, Carl E. Rasmussen

Abstract: Gaussian processes are attractive models for probabilistic classiﬁcation but unfortunately exact inference is analytically intractable. We compare Laplace’s method and Expectation Propagation (EP) focusing on marginal likelihood estimates and predictive performance. We explain theoretically and corroborate empirically that EP is superior to Laplace. We also compare to a sophisticated MCMC scheme and show that EP is surprisingly accurate. In recent years models based on Gaussian process (GP) priors have attracted much attention in the machine learning community. Whereas inference in the GP regression model with Gaussian noise can be done analytically, probabilistic classiﬁcation using GPs is analytically intractable. Several approaches to approximate Bayesian inference have been suggested, including Laplace’s approximation, Expectation Propagation (EP), variational approximations and Markov chain Monte Carlo (MCMC) sampling, some of these in conjunction with generalisation bounds, online learning schemes and sparse approximations. Despite the abundance of recent work on probabilistic GP classiﬁers, most experimental studies provide only anecdotal evidence, and no clear picture has yet emerged, as to when and why which algorithm should be preferred. Thus, from a practitioners point of view probabilistic GP classiﬁcation remains a jungle. In this paper, we set out to understand and compare two of the most wide-spread approximations: Laplace’s method and Expectation Propagation (EP). We also compare to a sophisticated, but computationally demanding MCMC scheme to examine how close the approximations are to ground truth. We examine two aspects of the approximation schemes: Firstly the accuracy of approximations to the marginal likelihood which is of central importance for model selection and model comparison. In any practical application of GPs in classiﬁcation (usually multiple) parameters of the covariance function (hyperparameters) have to be handled. Bayesian model selection provides a consistent framework for setting such parameters. Therefore, it is essential to evaluate the accuracy of the marginal likelihood approximations as a function of the hyperparameters, in order to assess the practical usefulness of the approach Secondly, we need to assess the quality of the approximate probabilistic predictions. In the past, the probabilistic nature of the GP predictions have not received much attention, the focus being mostly on classiﬁcation error rates. This unfortunate state of affairs is caused primarily by typical benchmarking problems being considered outside of a realistic context. The ability of a classiﬁer to produce class probabilities or conﬁdences, have obvious relevance in most areas of application, eg. medical diagnosis. We evaluate the predictive distributions of the approximate methods, and compare to the MCMC gold standard. 1 The Gaussian Process Model for Binary Classiﬁcation Let y ∈ {−1, 1} denote the class label of an input x. Gaussian process classiﬁcation (GPC) is discriminative in modelling p(y|x) for given x by a Bernoulli distribution. The probability of success p(y = 1|x) is related to an unconstrained latent function f (x) which is mapped to the unit interval by a sigmoid transformation, eg. the logit or the probit. For reasons of analytic convenience we exclusively use the probit model p(y = 1|x) = Φ(f (x)), where Φ denotes the cumulative density function of the standard Normal distribution. In the GPC model Bayesian inference is performed about the latent function f in the light of observed data D = {(yi , xi )|i = 1, . . . , m}. Let fi = f (xi ) and f = [f1 , . . . , fm ] be shorthand for the values of the latent function and y = [y1 , . . . , ym ] and X = [x1 , . . . , xm ] collect the class labels and inputs respectively. Given the latent function the class labels are independent Bernoulli variables, so the joint likelihood factories: m m p(yi |fi ) = p(y|f ) = i=1 Φ(yi fi ), i=1 and depends on f only through its value at the observed inputs. We use a zero-mean Gaussian process prior over the latent function f with a covariance function k(x, x |θ), which may depend on hyperparameters θ [1]. The functional form and parameters of the covariance function encodes assumptions about the latent function, and adaptation of these is part of the inference. The posterior distribution over latent function values f at the observed X for given hyperparameters θ becomes: m p(f |D, θ) = N (f |0, K) Φ(yi fi ), p(D|θ) i=1 where p(D|θ) = p(y|f )p(f |X, θ)df , denotes the marginal likelihood. Unfortunately neither the marginal likelihood, nor the posterior itself, or predictions can be computed analytically, so approximations are needed. 2 Approximate Bayesian Inference For the GPC model approximations are either based on a Gaussian approximation to the posterior p(f |D, θ) ≈ q(f |D, θ) = N (f |m, A) or involve Markov chain Monte Carlo (MCMC) sampling [2]. We compare Laplace’s method and Expectation Propagation (EP) which are two alternative approaches to ﬁnding parameters m and A of the Gaussian q(f |D, θ). Both methods also allow approximate evaluation of the marginal likelihood, which is useful for ML-II hyperparameter optimisation. Laplace’s approximation (LA) is found by making a second order Taylor approximation of the (un-normalised) log posterior [3]. The mean m is placed at the mode (MAP) and the covariance A equals the negative inverse Hessian of the log posterior density at m. The EP approximation [4] also gives a Gaussian approximation to the posterior. The parameters m and A are found in an iterative scheme by matching the approximate marginal moments of p(fi |D, θ) by the marginals of the approximation N (fi |mi , Aii ). Although we cannot prove the convergence of EP, we conjecture that it always converges for GPC with probit likelihood, and have never encountered an exception. A key insight is that a Gaussian approximation to the GPC posterior is equivalent to a GP approximation to the posterior distribution over latent functions. For a test input x∗ the fi 1 0.16 0.14 0.8 0.6 0.1 fj p(y|f) p(f|y) 0.12 Likelihood p(y|f) Prior p(f) Posterior p(f|y) Laplace q(f|y) EP q(f|y) 0.08 0.4 0.06 0.04 0.2 0.02 0 −4 0 4 8 0 f . (a) (b) Figure 1: Panel (a) provides a one-dimensional illustration of the approximations. The prior N (f |0, 52 ) combined with the probit likelihood (y = 1) results in a skewed posterior. The likelihood uses the right axis, all other curves use the left axis. Laplace’s approximation peaks at the posterior mode, but places far too much mass over negative values of f and too little at large positive values. The EP approximation matches the ﬁrst two posterior moments, which results in a larger mean and a more accurate placement of probability mass compared to Laplace’s approximation. In Panel (b) we caricature a high dimensional zeromean Gaussian prior as an ellipse. The gray shadow indicates that for a high dimensional Gaussian most of the mass lies in a thin shell. For large latent signals (large entries in K), the likelihood essentially cuts off regions which are incompatible with the training labels (hatched area), leaving the upper right orthant as the posterior. The dot represents the mode of the posterior, which remains close to the origin. approximate predictive latent and class probabilities are: 2 q(f∗ |D, θ, x∗ ) = N (µ∗ , σ∗ ), and 2 q(y∗ = 1|D, x∗ ) = Φ(µ∗ / 1 + σ∗ ), 2 where µ∗ = k∗ K−1 m and σ∗ = k(x∗ , x∗ )−k∗ (K−1 − K−1 AK−1 )k∗ , where the vector k∗ = [k(x1 , x∗ ), . . . , k(xm , x∗ )] collects covariances between x∗ and training inputs X. MCMC sampling has the advantage that it becomes exact in the limit of long runs and so provides a gold standard by which to measure the two analytic methods described above. Although MCMC methods can in principle be used to do inference over f and θ jointly [5], we compare to methods using ML-II optimisation over θ, thus we use MCMC to integrate over f only. Good marginal likelihood estimates are notoriously difﬁcult to obtain; in our experiments we use Annealed Importance Sampling (AIS) [6], combining several Thermodynamic Integration runs into a single (unbiased) estimate of the marginal likelihood. Both analytic approximations have a computational complexity which is cubic O(m3 ) as common among non-sparse GP models due to inversions m × m matrices. In our implementations LA and EP need similar running times, on the order of a few minutes for several hundred data-points. Making AIS work efﬁciently requires some ﬁne-tuning and a single estimate of p(D|θ) can take several hours for data sets of a few hundred examples, but this could conceivably be improved upon. 3 Structural Properties of the Posterior and its Approximations Structural properties of the posterior can best be understood by examining its construction. The prior is a correlated m-dimensional Gaussian N (f |0, K) centred at the origin. Each likelihood term p(yi |fi ) softly truncates the half-space from the prior that is incompatible with the observed label, see Figure 1. The resulting posterior is unimodal and skewed, similar to a multivariate Gaussian truncated to the orthant containing y. The mode of the posterior remains close to the origin, while the mass is placed in accordance with the observed class labels. Additionally, high dimensional Gaussian distributions exhibit the property that most probability mass is contained in a thin ellipsoidal shell – depending on the covariance structure – away from the mean [7, ch. 29.2]. Intuitively this occurs since in high dimensions the volume grows extremely rapidly with the radius. As an effect the mode becomes less representative (typical) for the prior distribution as the dimension increases. For the GPC posterior this property persists: the mode of the posterior distribution stays relatively close to the origin, still being unrepresentative for the posterior distribution, while the mean moves to the mass of the posterior making mean and mode differ signiﬁcantly. We cannot generally assume the posterior to be close to Gaussian, as in the often studied limit of low-dimensional parametric models with large amounts of data. Therefore in GPC we must be aware of making a Gaussian approximation to a non-Gaussian posterior. From the properties of the posterior it can be expected that Laplace’s method places m in the right orthant but too close to the origin, such that the approximation will overlap with regions having practically zero posterior mass. As an effect the amplitude of the approximate latent posterior GP will be underestimated systematically, leading to overly cautious predictive distributions. The EP approximation does not rely on a local expansion, but assumes that the marginal distributions can be well approximated by Gaussians. This assumption will be examined empirically below. 4 Experiments In this section we compare and inspect approximations for GPC using various benchmark data sets. The primary focus is not to optimise the absolute performance of GPC models but to compare the relative accuracy of approximations and to validate the arguments given in the previous section. In all experiments we use a covariance function of the form: k(x, x |θ) = σ 2 exp − 1 x − x 2 2 / 2 , (1) such that θ = [σ, ]. We refer to σ 2 as the signal variance and to as the characteristic length-scale. Note that for many classiﬁcation tasks it may be reasonable to use an individual length scale parameter for every input dimension (ARD) or a different kind of covariance function. Nevertheless, for the sake of presentability we use the above covariance function and we believe the conclusions about the accuracy of approximations to be independent of this choice, since it relies on arguments which are independent of the form of the covariance function. As measure of the accuracy of predictive probabilities we use the average information in bits of the predictions about the test targets in excess of that of random guessing. Let p∗ = p(y∗ = 1|D, θ, x∗ ) be the model’s prediction, then we average: I(p∗ , yi ) = i yi +1 2 log2 (p∗ ) + i 1−yi 2 log2 (1 − p∗ ) + H i (2) over all test cases, where H is the entropy of the training labels. The error rate E is equal to the percentage of erroneous class assignments if prediction is understood as a decision problem with symmetric costs. For the ﬁrst set of experiments presented here the well-known USPS digits and the Ionosphere data set were used. A binary sub-problem from the USPS digits is deﬁned by only considering 3’s vs. 5’s (which is probably the hardest of the binary sub-problems) and dividing the data into 767 cases for training and 773 for testing. The Ionosphere data is split into 200 training and 151 test cases. We do an exhaustive investigation on a ﬁne regular grid of values for the log hyperparameters. For each θ on the grid we compute the approximated log marginal likelihood by LA, EP and AIS. Additionally we compute the respective predictive performance (2) on the test set. Results are shown in Figure 2. Log marginal likelihood −150 −130 −200 Log marginal likelihood 5 −115 −105 −95 4 −115 −105 3 −130 −100 −150 2 1 log magnitude, log(σf) log magnitude, log(σf) 4 Log marginal likelihood 5 −160 4 −100 3 −130 −92 −160 2 −105 −160 −105 −200 −115 1 log magnitude, log(σf) 5 −92 −95 3 −100 −105 2−200 −115 −160 −130 −200 1 −200 0 0 0 −200 3 4 log lengthscale, log(l) 5 2 3 4 log lengthscale, log(l) (1a) 4 0.84 4 0.8 0.8 0.25 3 0.8 0.84 2 0.7 0.7 1 0.5 log magnitude, log(σf) 0.86 5 0.86 0.8 0.89 0.88 0.7 1 0.5 3 4 log lengthscale, log(l) 2 3 4 log lengthscale, log(l) (2a) Log marginal likelihood −90 −70 −100 −120 −120 0 −70 −75 −120 1 −100 1 2 3 log lengthscale, log(l) 4 0 −70 −90 −65 2 −100 −100 1 −120 −80 1 2 3 log lengthscale, log(l) 4 −1 −1 5 5 f 0.1 0.2 0.55 0 1 0.4 1 2 3 log lengthscale, log(l) 5 0.5 0.1 0 0.3 0.4 0.6 0.55 0.3 0.2 0.2 0.1 1 0 0.2 4 5 −1 −1 0.4 0.2 0.6 2 0.3 10 0 0.1 0.2 0.1 0 0 0.5 1 2 3 log lengthscale, log(l) 0.5 0.5 0.55 3 0 0.1 0 1 2 3 log lengthscale, log(l) 0.5 0.3 0.5 4 2 5 (3c) 0.5 3 4 Information about test targets in bits 4 log magnitude, log(σf) 4 2 0 (3b) Information about test targets in bits 0.3 log magnitude, log(σ ) −75 0 −1 −1 5 5 0 −120 3 −120 (3a) −1 −1 −90 −80 −65 −100 2 Information about test targets in bits 0 −75 4 0 3 5 Log marginal likelihood −90 3 −100 0 0.25 3 4 log lengthscale, log(l) 5 log magnitude, log(σf) log magnitude, log(σf) f log magnitude, log(σ ) −80 3 0.5 (2c) −75 −90 0.7 0.8 2 4 −75 −1 −1 0.86 0.84 Log marginal likelihood 4 1 0.7 1 5 5 −150 2 (2b) 5 2 0.88 3 0 5 0.84 0.89 0.25 0 0.7 0.25 0 0.86 4 0.84 3 2 5 Information about test targets in bits log magnitude, log(σf) log magnitude, log(σf) 5 −200 3 4 log lengthscale, log(l) (1c) Information about test targets in bits 5 2 2 (1b) Information about test targets in bits 0.5 5 log magnitude, log(σf) 2 4 5 −1 −1 0 1 2 3 log lengthscale, log(l) 4 5 (4a) (4b) (4c) Figure 2: Comparison of marginal likelihood approximations and predictive performances of different approximation techniques for USPS 3s vs. 5s (upper half) and the Ionosphere data (lower half). The columns correspond to LA (a), EP (b), and MCMC (c). The rows show estimates of the log marginal likelihood (rows 1 & 3) and the corresponding predictive performance (2) on the test set (rows 2 & 4) respectively. MCMC samples Laplace p(f|D) EP p(f|D) 0.2 0.15 0.45 0.1 0.4 0.05 0.3 −16 −14 −12 −10 −8 −6 f −4 −2 0 2 4 p(xi) 0 0.35 (a) 0.06 0.25 0.2 0.15 MCMC samples Laplace p(f|D) EP p(f|D) 0.1 0.05 0.04 0 0 2 0.02 xi 4 6 (c) 0 −40 −35 −30 −25 −20 −15 −10 −5 0 5 10 15 f (b) Figure 3: Panel (a) and (b) show two marginal distributions p(fi |D, θ) from a GPC posterior and its approximations. The true posterior is approximated by a normalised histogram of 9000 samples of fi obtained by MCMC sampling. Panel (c) shows a histogram of samples of a marginal distribution of a truncated high-dimensional Gaussian. The line describes a Gaussian with mean and variance estimated from the samples. For all three approximation techniques we see an agreement between marginal likelihood estimates and test performance, which justiﬁes the use of ML-II parameter estimation. But the shape of the contours and the values differ between the methods. The contours for Laplace’s method appear to be slanted compared to EP. The marginal likelihood estimates of EP and AIS agree surprisingly well1 , given that the marginal likelihood comes as a 767 respectively 200 dimensional integral. The EP predictions contain as much information about the test cases as the MCMC predictions and signiﬁcantly more than for LA. Note that for small signal variances (roughly ln(σ 2 ) < 1) LA and EP give very similar results. A possible explanation is that for small signal variances the likelihood does not truncate the prior but only down-weights the tail that disagrees with the observation. As an effect the posterior will be less skewed and both approximations will lead to similar results. For the USPS 3’s vs. 5’s we now inspect the marginal distributions p(fi |D, θ) of single latent function values under the posterior approximations for a given value of θ. We have chosen the values ln(σ) = 3.35 and ln( ) = 2.85 which are between the ML-II estimates of EP and LA. Hybrid MCMC was used to generate 9000 samples from the posterior p(f |D, θ). For LA and EP the approximate marginals are q(fi |D, θ) = N (fi |mi , Aii ) where m and A are found by the respective approximation techniques. In general we observe that the marginal distributions of MCMC samples agree very well with the respective marginal distributions of the EP approximation. For Laplace’s approximation we ﬁnd the mean to be underestimated and the marginal distributions to overlap with zero far more than the EP approximations. Figure (3a) displays the marginal distribution and its approximations for which the MCMC samples show maximal skewness. Figure (3b) shows a typical example where the EP approximation agrees very well with the MCMC samples. We show this particular example because under the EP approximation p(yi = 1|D, θ) < 0.1% but LA gives a wrong p(yi = 1|D, θ) ≈ 18%. In the experiment we saw that the marginal distributions of the posterior often agree very 1 Note that the agreement between the two seems to be limited by the accuracy of the MCMC runs, as judged by the regularity of the contour lines; the tolerance is less than one unit on a (natural) log scale. well with a Gaussian approximation. This seems to contradict the description given in the previous section were we argued that the posterior is skewed by construction. In order to inspect the marginals of a truncated high-dimensional multivariate Gaussian distribution we made an additional synthetic experiment. We constructed a 767 dimensional Gaussian N (x|0, C) with a covariance matrix having one eigenvalue of 100 with eigenvector 1, and all other eigenvalues are 1. We then truncate this distribution such that all xi ≥ 0. Note that the mode of the truncated Gaussian is still at zero, whereas the mean moves towards the remaining mass. Figure (3c) shows a normalised histogram of samples from a marginal distribution of one xi . The samples agree very well with a Gaussian approximation. In the previous section we described the somewhat surprising property, that for a truncated high-dimensional Gaussian, resembling the posterior, the mode (used by LA) may not be particularly representative of the distribution. Although the marginal is also truncated, it is still exceptionally well modelled by a Gaussian – however, the Laplace approximation centred on the origin would be completely inappropriate. In a second set of experiments we compare the predictive performance of LA and EP for GPC on several well known benchmark problems. Each data set is randomly split into 10 folds of which one at a time is left out as a test set to measure the predictive performance of a model trained (or selected) on the remaining nine folds. All performance measures are averages over the 10 folds. For GPC we implement model selection by ML-II hyperparameter estimation, reporting results given the θ that maximised the respective approximate marginal likelihoods p(D|θ). In order to get a better picture of the absolute performance we also compare to results obtained by C-SVM classiﬁcation. The kernel we used is equivalent to the covariance function (1) without the signal variance parameter. For each fold the parameters C and are found in an inner loop of 5-fold cross-validation, in which the parameter grids are reﬁned until the performance stabilises. Predictive probabilities for test cases are obtained by mapping the unthresholded output of the SVM to [0, 1] using a sigmoid function [8]. Results are summarised in Table 1. Comparing Laplace’s method to EP the latter shows to be more accurate both in terms of error rate and information. While the error rates are relatively similar the predictive distribution obtained by EP shows to be more informative about the test targets. Note that for GPC the error rate only depends of the sign of the mean µ∗ of the approximated posterior over latent functions and not the entire posterior predictive distribution. As to be expected, the length of the mean vector m shows much larger values for the EP approximations. Comparing EP and SVMs the results are mixed. For the Crabs data set all methods show the same error rate but the information content of the predictive distributions differs dramatically. For some test cases the SVM predicts the wrong class with large certainty. 5 Summary & Conclusions Our experiments reveal serious differences between Laplace’s method and EP when used in GPC models. From the structural properties of the posterior we described why LA systematically underestimates the mean m. The resulting posterior GP over latent functions will have too small amplitude, although the sign of the mean function will be mostly correct. As an effect LA gives over-conservative predictive probabilities, and diminished information about the test labels. This effect has been show empirically on several real world examples. Large resulting discrepancies in the actual posterior probabilities were found, even at the training locations, which renders the predictive class probabilities produced under this approximation grossly inaccurate. Note, the difference becomes less dramatic if we only consider the classiﬁcation error rates obtained by thresholding p∗ at 1/2. For this particular task, we’ve seen the the sign of the latent function tends to be correct (at least at the training locations). Laplace EP SVM Data Set m n E% I m E% I m E% I Ionosphere 351 34 8.84 0.591 49.96 7.99 0.661 124.94 5.69 0.681 Wisconsin 683 9 3.21 0.804 62.62 3.21 0.805 84.95 3.21 0.795 Pima Indians 768 8 22.77 0.252 29.05 22.63 0.253 47.49 23.01 0.232 Crabs 200 7 2.0 0.682 112.34 2.0 0.908 2552.97 2.0 0.047 Sonar 208 60 15.36 0.439 26.86 13.85 0.537 15678.55 11.14 0.567 USPS 3 vs 5 1540 256 2.27 0.849 163.05 2.21 0.902 22011.70 2.01 0.918 Table 1: Results for benchmark data sets. The ﬁrst three columns give the name of the data set, number of observations m and dimension of inputs n. For Laplace’s method and EP the table reports the average error rate E%, the average information I (2) and the average length m of the mean vector of the Gaussian approximation. For SVMs the error rate and the average information about the test targets are reported. Note that for the Crabs data set we use the sex (not the colour) of the crabs as class label. The EP approximation has shown to give results very close to MCMC both in terms of predictive distributions and marginal likelihood estimates. We have shown and explained why the marginal distributions of the posterior can be well approximated by Gaussians. Further, the marginal likelihood values obtained by LA and EP differ systematically which will lead to different results of ML-II hyperparameter estimation. The discrepancies are similar for different tasks. Using AIS we were able to show the accuracy of marginal likelihood estimates, which to the best of our knowledge has never been done before. In summary, we found that EP is the method of choice for approximate inference in binary GPC models, when the computational cost of MCMC is prohibitive. In contrast, the Laplace approximation is so inaccurate that we advise against its use, especially when predictive probabilities are to be taken seriously. Further experiments and a detailed description of the approximation schemes can be found in [2]. Acknowledgements Both authors acknowledge support by the German Research Foundation (DFG) through grant RA 1030/1. This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST2002-506778. This publication only reﬂects the authors’ views. References [1] C. K. I. Williams and C. E. Rasmussen. Gaussian processes for regression. In David S. Touretzky, Michael C. Mozer, and Michael E. Hasselmo, editors, NIPS 8, pages 514–520. MIT Press, 1996. [2] M. Kuss and C. E. Rasmussen. Assessing approximate inference for binary Gaussian process classiﬁcation. Journal of Machine Learning Research, 6:1679–1704, 2005. [3] C. K. I. Williams and D. Barber. Bayesian classiﬁcation with Gaussian processes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(12):1342–1351, 1998. [4] T. P. Minka. A Family of Algorithms for Approximate Bayesian Inference. PhD thesis, Department of Electrical Engineering and Computer Science, MIT, 2001. [5] R. M. Neal. Regression and classiﬁcation using Gaussian process priors. In J. M. Bernardo, J. O. Berger, A. P. Dawid, and A. F. M. Smith, editors, Bayesian Statistics 6, pages 475–501. Oxford University Press, 1998. [6] R. M. Neal. Annealed importance sampling. Statistics and Computing, 11:125–139, 2001. [7] D. J. C. MacKay. Information Theory, Inference and Learning Algorithms. CUP, 2003. [8] J. C. Platt. Probabilities for SV machines. In Advances in Large Margin Classiﬁers, pages 61–73. The MIT Press, 2000.

5 0.17250407 27 nips-2005-Analysis of Spectral Kernel Design based Semi-supervised Learning

Author: Tong Zhang, Rie Kubota Ando

Abstract: We consider a framework for semi-supervised learning using spectral decomposition based un-supervised kernel design. This approach subsumes a class of previously proposed semi-supervised learning methods on data graphs. We examine various theoretical properties of such methods. In particular, we derive a generalization performance bound, and obtain the optimal kernel design by minimizing the bound. Based on the theoretical analysis, we are able to demonstrate why spectral kernel design based methods can often improve the predictive performance. Experiments are used to illustrate the main consequences of our analysis.

6 0.12626649 105 nips-2005-Large-Scale Multiclass Transduction

7 0.11874361 202 nips-2005-Variational EM Algorithms for Non-Gaussian Latent Variable Models

8 0.11738419 57 nips-2005-Distance Metric Learning for Large Margin Nearest Neighbor Classification

9 0.11675643 14 nips-2005-A Probabilistic Interpretation of SVMs with an Application to Unbalanced Classification

10 0.10782955 41 nips-2005-Coarse sample complexity bounds for active learning

11 0.10471889 179 nips-2005-Sparse Gaussian Processes using Pseudo-inputs

12 0.098247655 178 nips-2005-Soft Clustering on Graphs

13 0.094451815 113 nips-2005-Learning Multiple Related Tasks using Latent Independent Component Analysis

14 0.091099523 190 nips-2005-The Curse of Highly Variable Functions for Local Kernel Machines

15 0.08593031 104 nips-2005-Laplacian Score for Feature Selection

16 0.085917532 199 nips-2005-Value Function Approximation with Diffusion Wavelets and Laplacian Eigenfunctions

17 0.082592674 114 nips-2005-Learning Rankings via Convex Hull Separation

18 0.082246229 47 nips-2005-Consistency of one-class SVM and related algorithms

19 0.081090309 10 nips-2005-A General and Efficient Multiple Kernel Learning Algorithm

20 0.076429643 13 nips-2005-A Probabilistic Approach for Optimizing Spectral Clustering

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.286), (1, 0.158), (2, -0.103), (3, -0.049), (4, -0.021), (5, -0.028), (6, 0.151), (7, -0.047), (8, 0.083), (9, 0.074), (10, 0.063), (11, -0.1), (12, 0.058), (13, 0.087), (14, -0.064), (15, -0.291), (16, 0.11), (17, -0.018), (18, 0.123), (19, 0.082), (20, -0.048), (21, 0.072), (22, 0.029), (23, 0.02), (24, 0.105), (25, -0.053), (26, 0.028), (27, -0.012), (28, -0.065), (29, -0.068), (30, 0.043), (31, -0.071), (32, -0.049), (33, 0.024), (34, 0.079), (35, -0.055), (36, -0.085), (37, -0.005), (38, 0.012), (39, -0.023), (40, 0.028), (41, -0.014), (42, -0.009), (43, -0.011), (44, -0.005), (45, 0.017), (46, 0.096), (47, 0.106), (48, 0.081), (49, -0.101)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96409994 92 nips-2005-Hyperparameter and Kernel Learning for Graph Based Semi-Supervised Classification

Author: Ashish Kapoor, Hyungil Ahn, Yuan Qi, Rosalind W. Picard

2 0.7029568 123 nips-2005-Maximum Margin Semi-Supervised Learning for Structured Variables

Author: Y. Altun, D. McAllester, M. Belkin

3 0.69141555 105 nips-2005-Large-Scale Multiclass Transduction

Author: Thomas Gärtner, Quoc V. Le, Simon Burton, Alex J. Smola, Vishy Vishwanathan

Abstract: We present a method for performing transductive inference on very large datasets. Our algorithm is based on multiclass Gaussian processes and is effective whenever the multiplication of the kernel matrix or its inverse with a vector can be computed sufﬁciently fast. This holds, for instance, for certain graph and string kernels. Transduction is achieved by variational inference over the unlabeled data subject to a balancing constraint. 1

4 0.68190646 42 nips-2005-Combining Graph Laplacians for Semi--Supervised Learning

Author: Andreas Argyriou, Mark Herbster, Massimiliano Pontil

5 0.64636135 30 nips-2005-Assessing Approximations for Gaussian Process Classification

Author: Malte Kuss, Carl E. Rasmussen

6 0.5479781 27 nips-2005-Analysis of Spectral Kernel Design based Semi-supervised Learning

7 0.52130443 14 nips-2005-A Probabilistic Interpretation of SVMs with an Application to Unbalanced Classification

8 0.50008678 10 nips-2005-A General and Efficient Multiple Kernel Learning Algorithm

9 0.46429232 174 nips-2005-Separation of Music Signals by Harmonic Structure Modeling

10 0.445476 140 nips-2005-Nonparametric inference of prior probabilities from Bayes-optimal behavior

11 0.44223493 57 nips-2005-Distance Metric Learning for Large Margin Nearest Neighbor Classification

12 0.43983525 190 nips-2005-The Curse of Highly Variable Functions for Local Kernel Machines

13 0.43813714 113 nips-2005-Learning Multiple Related Tasks using Latent Independent Component Analysis

14 0.43238288 205 nips-2005-Worst-Case Bounds for Gaussian Process Models

15 0.41954744 104 nips-2005-Laplacian Score for Feature Selection

16 0.41236672 76 nips-2005-From Batch to Transductive Online Learning

17 0.40865779 195 nips-2005-Transfer learning for text classification

18 0.40157846 160 nips-2005-Query by Committee Made Real

19 0.39496982 197 nips-2005-Unbiased Estimator of Shape Parameter for Spiking Irregularities under Changing Environments

20 0.3939454 75 nips-2005-Fixing two weaknesses of the Spectral Method

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(3, 0.062), (10, 0.037), (27, 0.023), (31, 0.034), (34, 0.15), (39, 0.016), (41, 0.015), (50, 0.025), (55, 0.036), (69, 0.069), (72, 0.196), (73, 0.047), (88, 0.12), (91, 0.092)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.935911 31 nips-2005-Asymptotics of Gaussian Regularized Least Squares

Author: Ross Lippert, Ryan Rifkin

Abstract: We consider regularized least-squares (RLS) with a Gaussian kernel. We prove that if we let the Gaussian bandwidth σ → ∞ while letting the regularization parameter λ → 0, the RLS solution tends to a polynomial 1 whose order is controlled by the rielative rates of decay of σ2 and λ: if λ = σ −(2k+1) , then, as σ → ∞, the RLS solution tends to the kth order polynomial with minimal empirical error. We illustrate the result with an example. 1

2 0.86731327 58 nips-2005-Divergences, surrogate loss functions and experimental design

Author: Xuanlong Nguyen, Martin J. Wainwright, Michael I. Jordan

Abstract: In this paper, we provide a general theorem that establishes a correspondence between surrogate loss functions in classiﬁcation and the family of f -divergences. Moreover, we provide constructive procedures for determining the f -divergence induced by a given surrogate loss, and conversely for ﬁnding all surrogate loss functions that realize a given f -divergence. Next we introduce the notion of universal equivalence among loss functions and corresponding f -divergences, and provide necessary and sufﬁcient conditions for universal equivalence to hold. These ideas have applications to classiﬁcation problems that also involve a component of experiment design; in particular, we leverage our results to prove consistency of a procedure for learning a classiﬁer under decentralization requirements. 1

same-paper 3 0.8629334 92 nips-2005-Hyperparameter and Kernel Learning for Graph Based Semi-Supervised Classification

Author: Ashish Kapoor, Hyungil Ahn, Yuan Qi, Rosalind W. Picard

4 0.7501294 105 nips-2005-Large-Scale Multiclass Transduction

Author: Thomas Gärtner, Quoc V. Le, Simon Burton, Alex J. Smola, Vishy Vishwanathan

5 0.74891287 32 nips-2005-Augmented Rescorla-Wagner and Maximum Likelihood Estimation

Author: Alan L. Yuille

Abstract: We show that linear generalizations of Rescorla-Wagner can perform Maximum Likelihood estimation of the parameters of all generative models for causal reasoning. Our approach involves augmenting variables to deal with conjunctions of causes, similar to the agumented model of Rescorla. Our results involve genericity assumptions on the distributions of causes. If these assumptions are violated, for example for the Cheng causal power theory, then we show that a linear Rescorla-Wagner can estimate the parameters of the model up to a nonlinear transformtion. Moreover, a nonlinear Rescorla-Wagner is able to estimate the parameters directly to within arbitrary accuracy. Previous results can be used to determine convergence and to estimate convergence rates. 1

6 0.74808967 50 nips-2005-Convex Neural Networks

7 0.74777073 114 nips-2005-Learning Rankings via Convex Hull Separation

8 0.7420525 184 nips-2005-Structured Prediction via the Extragradient Method

9 0.73579746 54 nips-2005-Data-Driven Online to Batch Conversions

10 0.73540711 98 nips-2005-Infinite latent feature models and the Indian buffet process

11 0.73385453 57 nips-2005-Distance Metric Learning for Large Margin Nearest Neighbor Classification

12 0.73103696 137 nips-2005-Non-Gaussian Component Analysis: a Semi-parametric Framework for Linear Dimension Reduction

13 0.73099202 24 nips-2005-An Approximate Inference Approach for the PCA Reconstruction Error

14 0.73008245 30 nips-2005-Assessing Approximations for Gaussian Process Classification

15 0.72879314 190 nips-2005-The Curse of Highly Variable Functions for Local Kernel Machines

16 0.72857308 23 nips-2005-An Application of Markov Random Fields to Range Sensing

17 0.72816896 43 nips-2005-Comparing the Effects of Different Weight Distributions on Finding Sparse Representations

18 0.72751379 132 nips-2005-Nearest Neighbor Based Feature Selection for Regression and its Application to Neural Activity

19 0.72688335 133 nips-2005-Nested sampling for Potts models

20 0.72682536 160 nips-2005-Query by Committee Made Real