nips nips2009 nips2009-214 knowledge-graph by maker-knowledge-mining

214 nips-2009-Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction

Source: pdf

Author: Kwang I. Kim, Florian Steinke, Matthias Hein

Abstract: Semi-supervised regression based on the graph Laplacian suffers from the fact that the solution is biased towards a constant and the lack of extrapolating power. Based on these observations, we propose to use the second-order Hessian energy for semi-supervised regression which overcomes both these problems. If the data lies on or close to a low-dimensional submanifold in feature space, the Hessian energy prefers functions whose values vary linearly with respect to geodesic distance. We ﬁrst derive the Hessian energy for smooth manifolds and continue to give a stable estimation procedure for the common case where only samples of the underlying manifold are given. The preference of ‘’linear” functions on manifolds renders the Hessian energy particularly suited for the task of semi-supervised dimensionality reduction, where the goal is to ﬁnd a user-deﬁned embedding function given some labeled points which varies smoothly (and ideally linearly) along the manifold. The experimental results suggest superior performance of our method compared with semi-supervised regression using Laplacian regularization or standard supervised regression techniques applied to this task. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com 1 Abstract Semi-supervised regression based on the graph Laplacian suffers from the fact that the solution is biased towards a constant and the lack of extrapolating power. [sent-5, score-0.182]

2 Based on these observations, we propose to use the second-order Hessian energy for semi-supervised regression which overcomes both these problems. [sent-6, score-0.327]

3 If the data lies on or close to a low-dimensional submanifold in feature space, the Hessian energy prefers functions whose values vary linearly with respect to geodesic distance. [sent-7, score-0.428]

4 We ﬁrst derive the Hessian energy for smooth manifolds and continue to give a stable estimation procedure for the common case where only samples of the underlying manifold are given. [sent-8, score-0.419]

5 The experimental results suggest superior performance of our method compared with semi-supervised regression using Laplacian regularization or standard supervised regression techniques applied to this task. [sent-10, score-0.483]

6 A large class of methods for semi-supervised learning is based on the manifold assumption, that is, the data points do not ﬁll the whole feature space but they are concentrated around a low-dimensional submanifold. [sent-12, score-0.167]

7 Under this assumption unlabeled data points can be used to build adaptive regularization functionals which penalize variation of the regression function only along the underlying manifold. [sent-13, score-0.494]

8 One of the main goals of this paper is to propose an appropriate regularization functional on a manifold, the Hessian energy, and show that it has favourable properties for semi-supervised regression compared to the well known Laplacian regularization [2, 12]. [sent-14, score-0.501]

9 Opposite to the Laplacian regularizer, the Hessian energy allows functions that extrapolate, i. [sent-15, score-0.207]

10 Particularly if only few labeled points are available, we show that this extrapolation capability leads to signiﬁcant improvements. [sent-18, score-0.189]

11 The second property of the proposed Hessian energy is that it favors functions which vary linearly along the manifold, so-called geodesic functions deﬁned later. [sent-19, score-0.463]

12 These user-guided embeddings are supposed to vary smoothly or even linearly along the manifold, where the later case corresponds to a setting where the user tries to 1 recover a low-distortion parameterization of the manifold. [sent-22, score-0.187]

13 The proposed Hessian energy is motivated by the recently proposed Eells energy for mappings between manifolds [11], which contains as a special case the regularization of real-valued functions on a manifold. [sent-24, score-0.645]

14 However, we will show that their operator due to problems in the estimation of the Hessian, leads to useless results when used as regularizer for regression. [sent-26, score-0.263]

15 On the contrary, our novel estimation procedure turns out to be more stable for regression and as a side effects leads also to a better estimation of the eigenvectors used in Hessian eigenmaps. [sent-27, score-0.354]

16 We present experimental results on several datasets, which show that our method for semi-supervised regression is often superior to other semi-supervised and supervised regression techniques. [sent-28, score-0.31]

17 2 Regression on manifolds Our approach for regression is based on regularized empirical risk minimization. [sent-29, score-0.248]

18 First, we will discuss the problem and the regularizer in the ideal case where we know the manifold exactly, corresponding to the case where we have access to an unlimited number of unlabeled data. [sent-30, score-0.327]

19 However, we have unlabeled data which can be used to estimate it, or more precisely we can use the unlabeled data to build an estimate ˆ S(f ) of the true regularizer S(f ). [sent-35, score-0.262]

20 For the moment we just want to discuss regularization functionals in the ideal case, where we know the manifold. [sent-37, score-0.237]

21 Our main goal is to construct a regularization functional on manifolds, which is particularly suited for semi-supervised regression and semi-supervised dimensionality reduction. [sent-42, score-0.37]

22 We follow here the framework of [11] who discuss regularization of mappings between manifolds, where we are interested in the special case of real-valued output. [sent-43, score-0.201]

23 Note, that the energy is by deﬁnition independent of the coordinate representation and depends only on the properties of M . [sent-45, score-0.212]

24 However, in a special coordinate system on M , the so called normal coordinates, one can evaluate it quite easily. [sent-48, score-0.149]

25 In sloppy terms, normal coordinates at a given point p are coordinates on M such that the manifold looks as Euclidean as possible (up to second order) around p. [sent-49, score-0.512]

26 Thus in normal coordinates xr centered at p, m m a bf = p ∂2f dxr ⊗ dxs b ∂xr ∂xs p a r,s=1 =⇒ a 2 b f T ∗ M ⊗T ∗ M p p = r,s=1 ∂2f ∂xr ∂xs 2 , (1) so that at p the norm of the second covariant derivative is just the Frobenius norm of the Hessian of f in normal coordinates. [sent-50, score-0.89]

27 Therefore we call the resulting functional the Hessian regularizer SHess (f ). [sent-51, score-0.136]

28 The Laplacian regularization has always a bias towards the constant function (for a non-zero regularization parameter it will not ﬁt the data exactly) and the extrapolation beyond data points to the boundary of the domain is always constant. [sent-53, score-0.469]

29 On the contrary the Hessian regularization ﬁts the data perfectly and extrapolates nicely to unseen data, since it’s null space contains functions which vary linearly with the geodesic distance. [sent-55, score-0.556]

30 In particular, its difference to the regularizer S∆ (f ) using the Laplacian, S∆ (f ) = f 2 dV (x) M proposed by Belkin and Niyogi [2] for semi-supervised classiﬁcation and in the meantime also adopted for semi-supervised regression [12]. [sent-57, score-0.291]

31 While this regularizer makes sense for classiﬁcation, it is of limited use for regression. [sent-58, score-0.136]

32 The following adaptation of a result in [4] shows that the Hessian regularizer has a richer null-space. [sent-60, score-0.136]

33 Proposition 1 (Eells, Lemaire [4]) A function f : M → R with f ∈ C ∞ (M ) has zero second derivative, a b f = 0, ∀x ∈ M , if and only if for any geodesic γ : (−ε, ε) → M parameterx ized by arc length s, there exists a constant cγ depending only on γ such that ∂ f γ(s) = cγ , ∂s ∀ − ε < s < ε. [sent-61, score-0.171]

34 They correspond to linear maps in Euclidean space and encode a constant variation with respect to the geodesic distance of the manifold. [sent-64, score-0.171]

35 First, the use of Laplacian regularization leads always to a bias towards the constant function and does not extrapolate beyond data points. [sent-68, score-0.256]

36 On the contrary, Hessian regularization is not biased towards constant functions if geodesic functions exist and extrapolates “linearly” (if possible) beyond data points. [sent-69, score-0.486]

37 These crucial differences are illustrated in Figure 1 where we compare Laplacian regularization using the graph Laplacian as in [2] to Hessian regularization as introduced in the next section for a densely sampled spiral. [sent-70, score-0.443]

38 3 Semi-supervised regression using Hessian energy As discussed in the last section unlabeled data provides us valuable information about the data manifold. [sent-72, score-0.39]

39 We use this information to construct normal coordinates around each unlabeled point, which requires the estimation of the local structure of the manifold. [sent-73, score-0.389]

40 Subsequently, we employ the normal coordinates to estimate the Hessian regularizer using the simple form of the second covariant derivative provided in Equation (1). [sent-74, score-0.47]

41 However, their estimate of the regularizer has stability problems when applied to semi-supervised regression as is discussed below. [sent-76, score-0.291]

42 The solution of the semi-supervised regression problem is obtained by solving a sparse linear system. [sent-78, score-0.155]

43 In the following, capital letters Xi correspond to sample points and xr denote normal coordinates. [sent-79, score-0.422]

44 The estimation of local normal coordinates can be done using the set of k nearest neighbors (NN) Nk (Xi ) of point Xi . [sent-81, score-0.326]

45 However, for real-world datasets like images the sampling is usually not dense enough so that the dimension of the manifold can not be detected automatically. [sent-86, score-0.147]

46 Having the exact tangent space TXi M one can determine the normal coordinates xr of a point Xj ∈ Nk (Xi ) as follows. [sent-88, score-0.491]

47 The rescaling makes sense only if local geodesic distances can be accurately estimated. [sent-90, score-0.237]

48 For all other datasets we therefore use xr (Xj ) = ur , Xj − Xi as normal coordinates. [sent-92, score-0.424]

49 In [11] it is shown that this replacement yields an error of 2 2 order O( a f κ2 ) in the estimation of , where κ is the maximal principal curvature a bf (the curvature of M with respect to the ambient space Rd ). [sent-93, score-0.156]

50 The Hessian regularizer, the squared norm of the second co2 variant derivative, , corresponds to the Frobenius norm of the Hessian of f in normal a bf coordinates, see Equation 1. [sent-95, score-0.313]

51 Thus, given normal coordinates xr at Xi we would like to have an operator H which given the function values f (Xj ) on Nk (Xi ) estimates the Hessian of f at Xi , ∂2f ∂xr ∂xs k (i) ≈ Xi Hrsj f (Xj ). [sent-96, score-0.491]

52 j=1 This can be done by ﬁtting a second-order polynomial p(x) in normal coordinates to {f (Xj )}k , j=1 n p(i) (x) = f (Xi ) + n n r s=r Br xr + Ars xr xs , r=1 (2) where the zeroth-order term is ﬁxed at f (Xi ). [sent-97, score-0.877]

53 , xm xm ], of the normal coordinates (centered at Xi ) of Xj ∈ Nk (xi ) up to second order. [sent-106, score-0.311]

54 Moreover, since we sum up the energy over all points, the squared norm of the Hessian is actually weighted with the local density of the points leading to a stronger penalization of the Hessian ˆ in densely sampled regions. [sent-111, score-0.431]

55 There the samples of the spiral are generated by uniform sampling of the angle leading to a more densely sampled “interior” region, which leads to the non-linear behavior of the function for the Laplacian regularization. [sent-114, score-0.239]

56 For the Hessian energy this phenomena cannot be seen in this example, since the Hessian of a “geodesic” function is zero everywhere and therefore it does not matter if it is weighted with the density. [sent-115, score-0.172]

57 Using the ideas of the previous paragraphs the ﬁnal algorithmic scheme for semi-supervised regression can now be immediately stated. [sent-120, score-0.155]

58 However, the quality of the estimate of the Hessian energy depends on the quality of the local ﬁt of p(i) for each data point Xi . [sent-127, score-0.199]

59 Note that during the estimation of local Hessian, we do not use the full second-order polynomial but ﬁx its zeroth-order term at the value of f (i. [sent-132, score-0.148]

60 If such a function ﬁts the data well we get useless regression results1 see Fig. [sent-139, score-0.201]

61 5 Regression results using full polynomial 20 15 40 f Full polynomial Fixed zeroth−order 1st eigenvector 2nd eigenvector 3rd eigenvector 0. [sent-144, score-0.374]

62 05 20 1st eigenvector 2nd eigenvector 3rd eigenvector 0. [sent-146, score-0.24]

63 2 −4 −4 −2 0 2 Figure 2: Fitting two points on the spiral revisited (see Fig. [sent-154, score-0.144]

64 1): Left image shows the regression result f using the Hessian energy estimated by ﬁtting a full polynomial in normal coordinates. [sent-155, score-0.592]

65 The Hessian energy of this heavily oscillating function is 0, since every local ﬁt is linear (an example shown in the right image; green curve). [sent-156, score-0.271]

66 However, ﬁxing the zeroth-order term yields a high Hessian energy as desired (local ﬁt is shown as the red curve in the right image). [sent-157, score-0.172]

67 1 0 10 20 Figure 3: Sinusoid on the spiral: Left two images show the result of semi-supervised regression using the Hessian estimate of [3] and the corresponding smallest eigenvectors of the Hessian “matrix”. [sent-160, score-0.266]

68 Our estimation procedure of the Hessian has similar motivation as the one done in Hessian eigenmaps [3]. [sent-165, score-0.134]

69 This seems to be suitable for Hessian eigenmaps as they do not use the full Hessian, but only its m + 1-dimensional null space (where m is the intrinsic dimension of the manifold). [sent-167, score-0.131]

70 However, using their estimator for semi-supervised regression leads to useless results, see Fig. [sent-169, score-0.228]

71 Moreover, we would like to note that using our estimator not only the eigenvectors of the null space but also eigenvectors corresponding to higher eigenvalues can be well estimated, see Fig. [sent-171, score-0.179]

72 4 Experiments We test our semi-supervised regression method using Hessian regularization on one synthetic and two real-world data sets. [sent-173, score-0.328]

73 We compare with the results obtained using Laplacian-based regularization and kernel ridge regression (KRR) trained only with the labeled examples. [sent-174, score-0.394]

74 For the digit and ﬁgure datasets, the experiments were repeated with 5 different assignments of labeled examples. [sent-178, score-0.128]

75 Each of the variation corresponds then to a separate regression problem which we ﬁnally stick together to get an embedding into four dimensions. [sent-184, score-0.189]

76 Note, that this dataset is quite challenging since translation of the digit leads to huge Euclidean distances between digits although they look visually very similar. [sent-185, score-0.127]

77 2, KRR (K) and Hessian (H) regularization recover well the two parameters of line width and rotation (all other embeddings can be found in the supplementary material). [sent-189, score-0.306]

78 As discussed previously, the Laplacian (L) regularization tends to shrink the estimated parameters towards a constant as it penalizes the “geodesic” functions. [sent-190, score-0.238]

79 2 Although KRR estimates well the thickness parameter, it fails for the rotation parameter (cf. [sent-192, score-0.148]

80 2 where we 2 In this ﬁgure, each parameter is normalized to lie in the unit interval while the regression was performed in the original scale. [sent-194, score-0.155]

81 First row: the 2D-embedding of the digits obtained by regression for the rotation and thickness parameter with 100 labels. [sent-199, score-0.341]

82 Second row: 21 digit images sampled at regular intervals in the estimated parameter spaces: two reference points (inverted images) are sampled in the ground truth parameter space and then in the corresponding estimated embedding. [sent-200, score-0.328]

83 Then, 19 points are sampled in the estimated parameter spaces based on linear inter/extrapolation of the parameters. [sent-201, score-0.143]

84 In each parameter space the interpolated points, the corresponding closest data points and the reference points are marked with red dots, blue and cyan circles. [sent-203, score-0.165]

85 01) show the images corresponding to equidistant inter/extrapolation in the estimated parameter space between two ﬁxed digits (inverted image)). [sent-257, score-0.123]

86 The Hessian regularization provided a moderate level of accuracy in recovering the thickness parameter and performed best on the remaining ones. [sent-258, score-0.258]

87 3) sampled based on regular intervals in zenith and azimuth angles on the upper hemisphere around the centered object [10]. [sent-261, score-0.192]

88 3 shows the results of regression for three parameters - the zenith angle, and the azimuth angle is transformed into Euclidean x,y coordinates. [sent-263, score-0.316]

89 Image colorization refers to the task of estimating the color components of a given gray level image. [sent-268, score-0.203]

90 This is essentially a semi-supervised regression problem where the user-speciﬁed color components correspond to the labels. [sent-271, score-0.204]

91 To facilitate quantitative evaluation, we adopted 20 color images, sampled a subset of pixels in each image as labels, and used the corresponding gray levels as inputs. [sent-272, score-0.173]

92 The number of labeled points were 30 and 100 for each images, which we regard as a moderate level of user intervention. [sent-273, score-0.176]

93 As error measure, we use the mean square distance between the original image and the corresponding 3 Although the underlying manifold is two dimensional, the parametrization cannot be directly found based on regression as the azimuth angle is periodic. [sent-274, score-0.412]

94 7 ground truth KRR Laplacian regularization Hessian regularization 1 1 1 1 0. [sent-276, score-0.346]

95 05 0 0 10 25 50 100 Laplacian regularization KRR Hessian regularization 0 10 25 50 100 number of labeled points 10 25 50 100 Figure 3: Results of regression on the ﬁgure dataset. [sent-295, score-0.634]

96 Second row: Left: some example images of the dataset, Right: error plots for each regression variable for different number of labeled points. [sent-297, score-0.268]

97 [8] Figure 4: Example of image colorization with 30 labels. [sent-299, score-0.17]

98 KRR failed in reconstructing (the color of) the red pepper at the lower-right corner, while the Laplacian regularizer produced overall, a greenish image. [sent-300, score-0.217]

99 Despite the slight diffusion of red color at the upper-left corner, overall, the result of Hessian regularization looks best which is also conﬁrmed by the reconstruction error. [sent-302, score-0.253]

100 The Hessian regularizer clearly outperformed the KRR and the Laplacianbased regression and produced slightly better results than those of Levin et al. [sent-311, score-0.291]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('hessian', 0.573), ('xr', 0.246), ('laplacian', 0.211), ('krr', 0.204), ('regularization', 0.173), ('energy', 0.172), ('geodesic', 0.171), ('regression', 0.155), ('coordinates', 0.136), ('regularizer', 0.136), ('xj', 0.123), ('colorization', 0.119), ('xi', 0.118), ('normal', 0.109), ('nk', 0.103), ('bf', 0.102), ('manifold', 0.1), ('levin', 0.097), ('manifolds', 0.093), ('txi', 0.091), ('thickness', 0.085), ('eigenmaps', 0.08), ('eigenvector', 0.08), ('spiral', 0.077), ('xs', 0.073), ('ars', 0.073), ('ur', 0.069), ('azimuth', 0.068), ('eells', 0.068), ('shess', 0.068), ('polynomial', 0.067), ('points', 0.067), ('labeled', 0.066), ('eigenvectors', 0.064), ('unlabeled', 0.063), ('rotation', 0.063), ('digit', 0.062), ('hrs', 0.06), ('densely', 0.059), ('covariant', 0.055), ('zenith', 0.055), ('estimation', 0.054), ('null', 0.051), ('image', 0.051), ('linearly', 0.05), ('color', 0.049), ('images', 0.047), ('useless', 0.046), ('irregular', 0.046), ('eurographics', 0.045), ('extrapolates', 0.045), ('hrsj', 0.045), ('seells', 0.045), ('user', 0.043), ('dimensionality', 0.042), ('dm', 0.041), ('ll', 0.041), ('coordinate', 0.04), ('embeddings', 0.039), ('rescaling', 0.039), ('digits', 0.038), ('estimated', 0.038), ('sampled', 0.038), ('angle', 0.038), ('belkin', 0.037), ('functionals', 0.036), ('oscillating', 0.036), ('dv', 0.036), ('heavily', 0.036), ('functions', 0.035), ('gray', 0.035), ('norm', 0.034), ('derivative', 0.034), ('br', 0.034), ('embedding', 0.034), ('squared', 0.034), ('germany', 0.033), ('xm', 0.033), ('frobenius', 0.033), ('rgb', 0.032), ('reconstructing', 0.032), ('looks', 0.031), ('contrary', 0.031), ('tting', 0.031), ('width', 0.031), ('interpolated', 0.031), ('tx', 0.031), ('centered', 0.031), ('extrapolation', 0.029), ('extrapolate', 0.029), ('riemannian', 0.028), ('smoothly', 0.028), ('inverted', 0.028), ('discuss', 0.028), ('ful', 0.027), ('leads', 0.027), ('towards', 0.027), ('parameterization', 0.027), ('rendering', 0.027), ('local', 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000008 214 nips-2009-Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction

Author: Kwang I. Kim, Florian Steinke, Matthias Hein

2 0.2330019 229 nips-2009-Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data

Author: Boaz Nadler, Nathan Srebro, Xueyuan Zhou

Abstract: We study the behavior of the popular Laplacian Regularization method for SemiSupervised Learning at the regime of a ﬁxed number of labeled points but a large number of unlabeled points. We show that in Rd , d 2, the method is actually not well-posed, and as the number of unlabeled points increases the solution degenerates to a noninformative function. We also contrast the method with the Laplacian Eigenvector method, and discuss the “smoothness” assumptions associated with this alternate method. 1 Introduction and Setup In this paper we consider the limit behavior of two popular semi-supervised learning (SSL) methods based on the graph Laplacian: the regularization approach [15] and the spectral approach [3]. We consider the limit when the number of labeled points is ﬁxed and the number of unlabeled points goes to inﬁnity. This is a natural limit for SSL as the basic SSL scenario is one in which unlabeled data is virtually inﬁnite. We can also think of this limit as “perfect” SSL, having full knowledge of the marginal density p(x). The premise of SSL is that the marginal density p(x) is informative about the unknown mapping y(x) we are trying to learn, e.g. since y(x) is expected to be “smooth” in some sense relative to p(x). Studying the inﬁnite-unlabeled-data limit, where p(x) is fully known, allows us to formulate and understand the underlying smoothness assumptions of a particular SSL method, and judge whether it is well-posed and sensible. Understanding the inﬁnite-unlabeled-data limit is also a necessary ﬁrst step to studying the convergence of the ﬁnite-labeled-data estimator. We consider the following setup: Let p(x) be an unknown smooth density on a compact domain Ω ⊂ Rd with a smooth boundary. Let y : Ω → Y be the unknown function we wish to estimate. In case of regression Y = R whereas in binary classiﬁcation Y = {−1, 1}. The standard (transductive) semisupervised learning problem is formulated as follows: Given l labeled points, (x1 , y1 ), . . . , (xl , yl ), with yi = y(xi ), and u unlabeled points xl+1 , . . . , xl+u , with all points xi sampled i.i.d. from p(x), the goal is to construct an estimate of y(xl+i ) for any unlabeled point xl+i , utilizing both the labeled and the unlabeled points. We denote the total number of points by n = l + u. We are interested in the regime where l is ﬁxed and u → ∞. 1 2 SSL with Graph Laplacian Regularization We ﬁrst consider the following graph-based approach formulated by Zhu et. al. [15]: y (x) = arg min In (y) ˆ subject to y(xi ) = yi , i = 1, . . . , l y where 1 n2 In (y) = Wi,j (y(xi ) − y(xj ))2 (1) (2) i,j is a Laplacian regularization term enforcing “smoothness” with respect to the n×n similarity matrix W . This formulation has several natural interpretations in terms of, e.g. random walks and electrical circuits [15]. These interpretations, however, refer to a ﬁxed graph, over a ﬁnite set of points with given similarities. In contrast, our focus here is on the more typical scenario where the points xi ∈ Rd are a random sample from a density p(x), and W is constructed based on this sample. We would like to understand the behavior of the method in terms of the density p(x), particularly in the limit where the number of unlabeled points grows. Under what assumptions on the target labeling y(x) and on the density p(x) is the method (1) sensible? The answer, of course, depends on how the matrix W is constructed. We consider the common situation where the similarities are obtained by applying some decay ﬁlter to the distances: xi −xj σ Wi,j = G (3) where G : R+ → R+ is some function with an adequately fast decay. Popular choices are the 2 Gaussian ﬁlter G(z) = e−z /2 or the ǫ-neighborhood graph obtained by the step ﬁlter G(z) = 1z<1 . For simplicity, we focus here on the formulation (1) where the solution is required to satisfy the constraints at the labeled points exactly. In practice, the hard labeling constraints are often replaced with a softer loss-based data term, which is balanced against the smoothness term In (y), e.g. [14, 6]. Our analysis and conclusions apply to such variants as well. Limit of the Laplacian Regularization Term As the number of unlabeled examples grows the regularization term (2) converges to its expectation, where the summation is replaced by integration w.r.t. the density p(x): lim In (y) = I (σ) (y) = n→∞ G Ω Ω x−x′ σ (y(x) − y(x′ ))2 p(x)p(x′ )dxdx′ . (4) In the above limit, the bandwidth σ is held ﬁxed. Typically, one would also drive the bandwidth σ to zero as n → ∞. There are two reasons for this choice. First, from a practical perspective, this makes the similarity matrix W sparse so it can be stored and processed. Second, from a theoretical perspective, this leads to a clear and well deﬁned limit of the smoothness regularization term In (y), at least when σ → 0 slowly enough1 , namely when σ = ω( d log n/n). If σ → 0 as n → ∞, and as long as nσ d / log n → ∞, then after appropriate normalization, the regularizer converges to a density weighted gradient penalty term [7, 8]: d lim d+2 In (y) n→∞ Cσ (σ) d (y) d+2 I σ→0 Cσ = lim ∇y(x) 2 p(x)2 dx = J(y) = (5) Ω where C = Rd z 2 G( z )dz, and assuming 0 < C < ∞ (which is the case for both the Gaussian and the step ﬁlters). This energy functional J(f ) therefore encodes the notion of “smoothness” with respect to p(x) that is the basis of the SSL formulation (1) with the graph constructions speciﬁed by (3). To understand the behavior and appropriateness of (1) we must understand this functional and the associated limit problem: y (x) = arg min J(y) ˆ subject to y(xi ) = yi , i = 1, . . . , l (6) y p When σ = o( d 1/n) then all non-diagonal weights Wi,j vanish (points no longer have any “close by” p neighbors). We are not aware of an analysis covering the regime where σ decays roughly as d 1/n, but would be surprised if a qualitatively different meaningful limit is reached. 1 2 3 Graph Laplacian Regularization in R1 We begin by considering the solution of (6) for one dimensional data, i.e. d = 1 and x ∈ R. We ﬁrst consider the situation where the support of p(x) is a continuous interval Ω = [a, b] ⊂ R (a and/or b may be inﬁnite). Without loss of generality, we assume the labeled data is sorted in increasing order a x1 < x2 < · · · < xl b. Applying the theory of variational calculus, the solution y (x) ˆ satisﬁes inside each interval (xi , xi+1 ) the Euler-Lagrange equation d dy p2 (x) = 0. dx dx Performing two integrations and enforcing the constraints at the labeled points yields y(x) = yi + x 1/p2 (t)dt xi (yi+1 xi+1 1/p2 (t)dt xi − yi ) for xi x xi+1 (7) with y(x) = x1 for a x x1 and y(x) = xl for xl x b. If the support of p(x) is a union of disjoint intervals, the above analysis and the form of the solution applies in each interval separately. The solution (7) seems reasonable and desirable from the point of view of the “smoothness” assumptions: when p(x) is uniform, the solution interpolates linearly between labeled data points, whereas across low-density regions, where p(x) is close to zero, y(x) can change abruptly. Furthermore, the regularizer J(y) can be interpreted as a Reproducing Kernel Hilbert Space (RKHS) squared semi-norm, giving us additional insight into this choice of regularizer: b 1 Theorem 1. Let p(x) be a smooth density on Ω = [a, b] ⊂ R such that Ap = 4 a 1/p2 (t)dt < ∞. 2 Then, J(f ) can be written as a squared semi-norm J(f ) = f Kp induced by the kernel x′ ′ Kp (x, x ) = Ap − 1 2 x with a null-space of all constant functions. That is, f the RKHS induced by Kp . 1 p2 (t) dt Kp . (8) is the norm of the projection of f onto If p(x) is supported on several disjoint intervals, Ω = ∪i [ai , bi ], then J(f ) can be written as a squared semi-norm induced by the kernel 1 bi dt 4 ai p2 (t) ′ Kp (x, x ) = − 1 2 x′ dt x p2 (t) if x, x′ ∈ [ai , bi ] (9) if x ∈ [ai , bi ], x′ ∈ [aj , bj ], i = j 0 with a null-space spanned by indicator functions 1[ai ,bi ] (x) on the connected components of Ω. Proof. For any f (x) = i αi Kp (x, xi ) in the RKHS induced by Kp : df dx J(f ) = 2 p2 (x)dx = αi αj Jij (10) i,j where Jij = d d Kp (x, xi ) Kp (x, xj )p2 (x)dx dx dx When xi and xj are in different connected components of Ω, the gradients of Kp (·, xi ) and Kp (·, xj ) are never non-zero together and Jij = 0 = Kp (xi , xj ). When they are in the same connected component [a, b], and assuming w.l.o.g. a xi xj b: Jij = = xi 1 4 1 4 a b a 1 dt + p2 (t) 1 1 dt − p2 (t) 2 xj xi xj xi −1 dt + p2 (t) xj 1 dt p2 (t) 1 dt = Kp (xi , xj ). p2 (t) Substituting Jij = Kp (xi , xj ) into (10) yields J(f ) = 3 b αi αj Kp (xi , xj ) = f (11) Kp . Combining Theorem 1 with the Representer Theorem [13] establishes that the solution of (6) (or of any variant where the hard constraints are replaced by a data term) is of the form: l y(x) = αj Kp (x, xj ) + βi 1[ai ,bi ] (x), j=1 i where i ranges over the connected components [ai , bi ] of Ω, and we have: l J(y) = αi αj Kp (xi , xj ). (12) i,j=1 Viewing the regularizer as y 2 p suggests understanding (6), and so also its empirical approximaK tion (1), by interpreting Kp (x, x′ ) as a density-based “similarity measure” between x and x′ . This similarity measure indeed seems sensible: for a uniform density it is simply linearly decreasing as a function of the distance. When the density is non-uniform, two points are relatively similar only if they are connected by a region in which 1/p2 (x) is low, i.e. the density is high, but are much less “similar”, i.e. related to each other, when connected by a low-density region. Furthermore, there is no dependence between points in disjoint components separated by zero density regions. 4 Graph Laplacian Regularization in Higher Dimensions The analysis of the previous section seems promising, at it shows that in one dimension, the SSL method (1) is well posed and converges to a sensible limit. Regretfully, in higher dimensions this is not the case anymore. In the following theorem we show that the inﬁmum of the limit problem (6) is zero and can be obtained by a sequence of functions which are certainly not a sensible extrapolation of the labeled points. Theorem 2. Let p(x) be a smooth density over Rd , d 2, bounded from above by some constant pmax , and let (x1 , y1 ), . . . , (xl , yl ) be any (non-repeating) set of labeled examples. There exist continuous functions yǫ (x), for any ǫ > 0, all satisfying the constraints yǫ (xj ) = yj , j = 1, . . . , l, such ǫ→0 ǫ→0 that J(yǫ ) −→ 0 but yǫ (x) −→ 0 for all x = xj , j = 1, . . . , l. Proof. We present a detailed proof for the case of l = 2 labeled points. The generalization of the proof to more labeled points is straightforward. Furthermore, without loss of generality, we assume the ﬁrst labeled point is at x0 = 0 with y(x0 ) = 0 and the second labeled point is at x1 with x1 = 1 and y(x1 ) = 1. In addition, we assume that the ball B1 (0) of radius one centered around the origin is contained in Ω = {x ∈ Rd | p(x) > 0}. We ﬁrst consider the case d > 2. Here, for any ǫ > 0, consider the function x ǫ yǫ (x) = min ,1 which indeed satisﬁes the two constraints yǫ (xi ) = yi , i = 0, 1. Then, J(yǫ ) = Bǫ (0) p2 (x) dx ǫ2 pmax ǫ2 dx = p2 Vd ǫd−2 max (13) Bǫ (0) where Vd is the volume of a unit ball in Rd . Hence, the sequence of functions yǫ (x) satisfy the constraints, but for d > 2, inf ǫ J(yǫ ) = 0. For d = 2, a more extreme example is necessary: consider the functions 2 x yǫ (x) = log +ǫ ǫ log 1+ǫ ǫ for x 1 and yǫ (x) = 1 for x > 1. These functions satisfy the two constraints yǫ (xi ) = yi , i = 0, 1 and: J(yǫ ) = 4 h “ ”i 1+ǫ 2 log ǫ 4πp2 max h “ ”i 1+ǫ 2 log ǫ x B1 (0) log ( x 1+ǫ ǫ 2 2 +ǫ)2 p2 (x)dx 4p2 h “ max ”i2 1+ǫ log ǫ 4πp2 max ǫ→0 = −→ 0. log 1+ǫ ǫ 4 1 0 r2 (r 2 +ǫ)2 2πrdr The implication of Theorem 2 is that regardless of the values at the labeled points, as u → ∞, the solution of (1) is not well posed. Asymptotically, the solution has the form of an almost everywhere constant function, with highly localized spikes near the labeled points, and so no learning is performed. In particular, an interpretation in terms of a density-based kernel Kp , as in the onedimensional case, is not possible. Our analysis also carries over to a formulation where a loss-based data term replaces the hard label constraints, as in l 1 y = arg min ˆ (y(xj ) − yj )2 + γIn (y) y(x) l j=1 In the limit of inﬁnite unlabeled data, functions of the form yǫ (x) above have a zero data penalty term (since they exactly match the labels) and also drive the regularization term J(y) to zero. Hence, it is possible to drive the entire objective functional (the data term plus the regularization term) to zero with functions that do not generalize at all to unlabeled points. 4.1 Numerical Example We illustrate the phenomenon detailed by Theorem 2 with a simple example. Consider a density p(x) in R2 , which is a mixture of two unit variance spherical Gaussians, one per class, centered at the origin and at (4, 0). We sample a total of n = 3000 points, and label two points from each of the two components (four total). We then construct a similarity matrix using a Gaussian ﬁlter with σ = 0.4. Figure 1 depicts the predictor y (x) obtained from (1). In fact, two different predictors are shown, ˆ obtained by different numerical methods for solving (1). Both methods are based on the observation that the solution y (x) of (1) satisﬁes: ˆ n y (xi ) = ˆ n Wij y (xj ) / ˆ j=1 Wij on all unlabeled points i = l + 1, . . . , l + u. (14) j=1 Combined with the constraints of (1), we obtain a system of linear equations that can be solved by Gaussian elimination (here invoked through MATLAB’s backslash operator). This is the method used in the top panels of Figure 1. Alternatively, (14) can be viewed as an update equation for y (xi ), ˆ which can be solved via the power method, or label propagation [2, 6]: start with zero labels on the unlabeled points and iterate (14), while keeping the known labels on x1 , . . . , xl . This is the method used in the bottom panels of Figure 1. As predicted, y (x) is almost constant for almost all unlabeled points. Although all values are very ˆ close to zero, thresholding at the “right” threshold does actually produce sensible results in terms of the true -1/+1 labels. However, beyond being inappropriate for regression, a very ﬂat predictor is still problematic even from a classiﬁcation perspective. First, it is not possible to obtain a meaningful conﬁdence measure for particular labels. Second, especially if the size of each class is not known apriori, setting the threshold between the positive and negative classes is problematic. In our example, setting the threshold to zero yields a generalization error of 45%. The differences between the two numerical methods for solving (1) also point out to another problem with the ill-posedness of the limit problem: the solution is numerically very un-stable. A more quantitative evaluation, that also validates that the effect in Figure 1 is not a result of choosing a “wrong” bandwidth σ, is given in Figure 2. We again simulated data from a mixture of two Gaussians, one Gaussian per class, this time in 20 dimensions, with one labeled point per class, and an increasing number of unlabeled points. In Figure 2 we plot the squared error, and the classiﬁcation error of the resulting predictor y (x). We plot the classiﬁcation error both when a threshold ˆ of zero is used (i.e. the class is determined by sign(ˆ(x))) and with the ideal threshold minimizing y the test error. For each unlabeled sample size, we choose the bandwidth σ yielding the best test performance (this is a “cheating” approach which provides a lower bound on the error of the best method for selecting the bandwidth). As the number of unlabeled examples increases the squared error approaches 1, indicating a ﬂat predictor. Using a threshold of zero leads to an increase in the classiﬁcation error, possibly due to numerical instability. Interestingly, although the predictors become very ﬂat, the classiﬁcation error using the ideal threshold actually improves slightly. Note that 5 DIRECT INVERSION SQUARED ERROR SIGN ERROR: 45% OPTIMAL BANDWIDTH 1 0.9 1 5 0 4 2 0.85 y(x) > 0 y(x) < 0 6 0.95 10 0 0 −1 10 0 200 400 600 800 0−1 ERROR (THRESHOLD=0) 0.32 −5 10 0 5 −10 0 −10 −5 −5 0 5 10 10 1 0 0 200 400 600 800 OPTIMAL BANDWIDTH 0.5 0 0 200 400 600 800 0−1 ERROR (IDEAL THRESHOLD) 0.19 5 200 400 600 800 OPTIMAL BANDWIDTH 1 0.28 SIGN ERR: 17.1 0.3 0.26 POWER METHOD 0 1.5 8 0 0.18 −1 10 6 0.17 4 −5 10 0 5 −10 0 −5 −10 −5 0 5 10 Figure 1: Left plots: Minimizer of Eq. (1). Right plots: the resulting classiﬁcation according to sign(y). The four labeled points are shown by green squares. Top: minimization via Gaussian elimination (MATLAB backslash). Bottom: minimization via label propagation with 1000 iterations - the solution has not yet converged, despite small residuals of the order of 2 · 10−4 . 0.16 0 200 400 600 800 2 0 200 400 600 800 Figure 2: Squared error (top), classiﬁcation error with a threshold of zero (center) and minimal classiﬁcation error using ideal threhold (bottom), of the minimizer of (1) as a function of number of unlabeled points. For each error measure and sample size, the bandwidth minimizing the test error was used, and is plotted. ideal classiﬁcation performance is achieved with a signiﬁcantly larger bandwidth than the bandwidth minimizing the squared loss, i.e. when the predictor is even ﬂatter. 4.2 Probabilistic Interpretation, Exit and Hitting Times As mentioned above, the Laplacian regularization method (1) has a probabilistic interpretation in terms of a random walk on the weighted graph. Let x(t) denote a random walk on the graph with transition matrix M = D−1 W where D is a diagonal matrix with Dii = j Wij . Then, for the binary classiﬁcation case with yi = ±1 we have [15]: y (xi ) = 2 Pr x(t) hits a point labeled +1 before hitting a point labeled -1 x(0) = xi − 1 ˆ We present an interpretation of our analysis in terms of the limiting properties of this random walk. Consider, for simplicity, the case where the two classes are separated by a low density region. Then, the random walk has two intrinsic quantities of interest. The ﬁrst is the mean exit time from one cluster to the other, and the other is the mean hitting time to the labeled points in that cluster. As the number of unlabeled points increases and σ → 0, the random walk converges to a diffusion process [12]. While the mean exit time then converges to a ﬁnite value corresponding to its diffusion analogue, the hitting time to a labeled point increases to inﬁnity (as these become absorbing boundaries of measure zero). With more and more unlabeled data the random walk will fully mix, forgetting where it started, before it hits any label. Thus, the probability of hitting +1 before −1 will become uniform across the entire graph, independent of the starting location xi , yielding a ﬂat predictor. 5 Keeping σ Finite At this point, a reader may ask whether the problems found in higher dimensions are due to taking the limit σ → 0. One possible objection is that there is an intrinsic characteristic scale for the data σ0 where (with high probability) all points at a distance xi − xj < σ0 have the same label. If this is the case, then it may not necessarily make sense to take values of σ < σ0 in constructing W . However, keeping σ ﬁnite while taking the number of unlabeled points to inﬁnity does not resolve the problem. On the contrary, even the one-dimensional case becomes ill-posed in this case. To see this, consider a function y(x) which is zero everywhere except at the labeled points, where y(xj ) = yj . With a ﬁnite number of labeled points of measure zero, I (σ) (y) = 0 in any dimension 6 50 points 500 points 3500 points 1 1 0.5 0.5 0.5 0 0 0 −0.5 y 1 −0.5 −0.5 −1 −2 0 2 4 6 −1 −2 0 2 4 6 −1 −2 0 2 4 6 x Figure 3: Minimizer of (1) for a 1-d problem with a ﬁxed σ = 0.4, two labeled points and an increasing number of unlabeled points. and for any ﬁxed σ > 0. While this limiting function is discontinuous, it is also possible to construct ǫ→0 a sequence of continuous functions yǫ that all satisfy the constraints and for which I (σ) (yǫ ) −→ 0. This behavior is illustrated in Figure 3. We generated data from a mixture of two 1-D Gaussians centered at the origin and at x = 4, with one Gaussian labeled −1 and the other +1. We used two labeled points at the centers of the Gaussians and an increasing number of randomly drawn unlabeled points. As predicted, with a ﬁxed σ, although the solution is reasonable when the number of unlabeled points is small, it becomes ﬂatter, with sharp spikes on the labeled points, as u → ∞. 6 Fourier-Eigenvector Based Methods Before we conclude, we discuss a different approach for SSL, also based on the Graph Laplacian, suggested by Belkin and Niyogi [3]. Instead of using the Laplacian as a regularizer, constraining candidate predictors y(x) non-parametrically to those with small In (y) values, here the predictors are constrained to the low-dimensional space spanned by the ﬁrst few eigenvectors of the Laplacian: The similarity matrix W is computed as before, and the Graph Laplacian matrix L = D − W is considered (recall D is a diagonal matrix with Dii = j Wij ). Only predictors p j=1 aj ej y (x) = ˆ (15) spanned by the ﬁrst p eigenvectors e1 , . . . , ep of L (with smallest eigenvalues) are considered. The coefﬁcients aj are chosen by minimizing a loss function on the labeled data, e.g. the squared loss: (ˆ1 , . . . , ap ) = arg min a ˆ l j=1 (yj − y (xj ))2 . ˆ (16) Unlike the Laplacian Regularization method (1), the Laplacian Eigenvector method (15)–(16) is well posed in the limit u → ∞. This follows directly from the convergence of the eigenvectors of the graph Laplacian to the eigenfunctions of the corresponding Laplace-Beltrami operator [10, 4]. Eigenvector based methods were shown empirically to provide competitive generalization performance on a variety of simulated and real world problems. Belkin and Niyogi [3] motivate the approach by arguing that ‘the eigenfunctions of the Laplace-Beltrami operator provide a natural basis for functions on the manifold and the desired classiﬁcation function can be expressed in such a basis’. In our view, the success of the method is actually not due to data lying on a low-dimensional manifold, but rather due to the low density separation assumption, which states that different class labels form high-density clusters separated by low density regions. Indeed, under this assumption and with sufﬁcient separation between the clusters, the eigenfunctions of the graph Laplace-Beltrami operator are approximately piecewise constant in each of the clusters, as in spectral clustering [12, 11], providing a basis for a labeling that is constant within clusters but variable across clusters. In other settings, such as data uniformly distributed on a manifold but without any signiﬁcant cluster structure, the success of eigenvector based methods critically depends on how well can the unknown classiﬁcation function be approximated by a truncated expansion with relatively few eigenvectors. We illustrate this issue with the following three-dimensional example: Let p(x) denote the uniform density in the box [0, 1] × [0, 0.8] × [0, 0.6], where the box lengths are different to prevent eigenvalue multiplicity. Consider learning three different functions, y1 (x) = 1x1 >0.5 , y2 (x) = 1x1 >x2 /0.8 and y3 (x) = 1x2 /0.8>x3 /0.6 . Even though all three functions are relatively simple, all having a linear separating boundary between the classes on the manifold, as shown in the experiment described in Figure 4, the Eigenvector based method (15)–(16) gives markedly different generalization performances on the three targets. This happens both when the number of eigenvectors p is set to p = l/5 as suggested by Belkin and Niyogi, as well as for the optimal (oracle) value of p selected on the test set (i.e. a “cheating” choice representing an upper bound on the generalization error of this method). 7 Prediction Error (%) p = #labeled points/5 40 optimal p 20 labeled points 40 Approx. Error 50 20 20 0 20 20 40 60 # labeled points 0 10 20 40 60 # labeled points 0 0 5 10 15 # eigenvectors 0 0 5 10 15 # eigenvectors Figure 4: Left three panels: Generalization Performance of the Eigenvector Method (15)–(16) for the three different functions described in the text. All panels use n = 3000 points. Prediction counts the number of sign agreements with the true labels. Rightmost panel: best ﬁt when many (all 3000) points are used, representing the best we can hope for with a few leading eigenvectors. The reason for this behavior is that y2 (x) and even more so y3 (x) cannot be as easily approximated by the very few leading eigenfunctions—even though they seem “simple” and “smooth”, they are signiﬁcantly more complicated than y1 (x) in terms of measure of simplicity implied by the Eigenvector Method. Since the density is uniform, the graph Laplacian converges to the standard Laplacian and its eigenfunctions have the form ψi,j,k (x) = cos(iπx1 ) cos(jπx2 /0.8) cos(kπx3 /0.6), making it hard to represent simple decision boundaries which are not axis-aligned. 7 Discussion Our results show that a popular SSL method, the Laplacian Regularization method (1), is not wellbehaved in the limit of inﬁnite unlabeled data, despite its empirical success in various SSL tasks. The empirical success might be due to two reasons. First, it is possible that with a large enough number of labeled points relative to the number of unlabeled points, the method is well behaved. This regime, where the number of both labeled and unlabeled points grow while l/u is ﬁxed, has recently been analyzed by Wasserman and Lafferty [9]. However, we do not ﬁnd this regime particularly satisfying as we would expect that having more unlabeled data available should improve performance, rather than require more labeled points or make the problem ill-posed. It also places the user in a delicate situation of choosing the “just right” number of unlabeled points without any theoretical guidance. Second, in our experiments we noticed that although the predictor y (x) becomes extremely ﬂat, in ˆ binary tasks, it is still typically possible to ﬁnd a threshold leading to a good classiﬁcation performance. We do not know of any theoretical explanation for such behavior, nor how to characterize it. Obtaining such an explanation would be very interesting, and in a sense crucial to the theoretical foundation of the Laplacian Regularization method. On a very practical level, such a theoretical understanding might allow us to correct the method so as to avoid the numerical instability associated with ﬂat predictors, and perhaps also make it appropriate for regression. The reason that the Laplacian regularizer (1) is ill-posed in the limit is that the ﬁrst order gradient is not a sufﬁcient penalty in high dimensions. This fact is well known in spline theory, where the Sobolev Embedding Theorem [1] indicates one must control at least d+1 derivatives in Rd . In the 2 context of Laplacian regularization, this can be done using the iterated Laplacian: replacing the d+1 graph Laplacian matrix L = D − W , where D is the diagonal degree matrix, with L 2 (matrix to d+1 the 2 power). In the inﬁnite unlabeled data limit, this corresponds to regularizing all order- d+1 2 (mixed) partial derivatives. In the typical case of a low-dimensional manifold in a high dimensional ambient space, the order of iteration should correspond to the intrinsic, rather then ambient, dimensionality, which poses a practical problem of estimating this usually unknown dimensionality. We are not aware of much practical work using the iterated Laplacian, nor a good understanding of its appropriateness for SSL. A different approach leading to a well-posed solution is to include also an ambient regularization term [5]. However, the properties of the solution and in particular its relation to various assumptions about the “smoothness” of y(x) relative to p(x) remain unclear. Acknowledgments The authors would like to thank the anonymous referees for valuable suggestions. The research of BN was supported by the Israel Science Foundation (grant 432/06). 8 References [1] R.A. Adams, Sobolev Spaces, Academic Press (New York), 1975. [2] A. Azran, The rendevous algorithm: multiclass semi-supervised learning with Markov Random Walks, ICML, 2007. [3] M. Belkin, P. Niyogi, Using manifold structure for partially labelled classiﬁcation, NIPS, vol. 15, 2003. [4] M. Belkin and P. Niyogi, Convergence of Laplacian Eigenmaps, NIPS 19, 2007. [5] M. Belkin, P. Niyogi and S. Sindhwani, Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples, JMLR, 7:2399-2434, 2006. [6] Y. Bengio, O. Delalleau, N. Le Roux, label propagation and quadratic criterion, in Semi-Supervised Learning, Chapelle, Scholkopf and Zien, editors, MIT Press, 2006. [7] O. Bosquet, O. Chapelle, M. Hein, Measure Based Regularization, NIPS, vol. 16, 2004. [8] M. Hein, Uniform convergence of adaptive graph-based regularization, COLT, 2006. [9] J. Lafferty, L. Wasserman, Statistical Analysis of Semi-Supervised Regression, NIPS, vol. 20, 2008. [10] U. von Luxburg, M. Belkin and O. Bousquet, Consistency of spectral clustering, Annals of Statistics, vol. 36(2), 2008. [11] M. Meila, J. Shi. A random walks view of spectral segmentation, AI and Statistics, 2001. [12] B. Nadler, S. Lafon, I.G. Kevrekidis, R.R. Coifman, Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators, NIPS, vol. 18, 2006. [13] B. Sch¨ lkopf, A. Smola, Learning with Kernels, MIT Press, 2002. o [14] D. Zhou, O. Bousquet, T. Navin Lal, J. Weston, B. Sch¨ lkopf, Learning with local and global consistency, o NIPS, vol. 16, 2004. [15] X. Zhu, Z. Ghahramani, J. Lafferty, Semi-Supervised Learning using Gaussian ﬁelds and harmonic functions, ICML, 2003. 9

3 0.13286042 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

Author: Sahand Negahban, Bin Yu, Martin J. Wainwright, Pradeep K. Ravikumar

Abstract: High-dimensional statistical inference deals with models in which the the number of parameters p is comparable to or larger than the sample size n. Since it is usually impossible to obtain consistent procedures unless p/n → 0, a line of recent work has studied models with various types of structure (e.g., sparse vectors; block-structured matrices; low-rank matrices; Markov assumptions). In such settings, a general approach to estimation is to solve a regularized convex program (known as a regularized M -estimator) which combines a loss function (measuring how well the model ﬁts the data) with some regularization function that encourages the assumed structure. The goal of this paper is to provide a uniﬁed framework for establishing consistency and convergence rates for such regularized M estimators under high-dimensional scaling. We state one main theorem and show how it can be used to re-derive several existing results, and also to obtain several new results on consistency and convergence rates. Our analysis also identiﬁes two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure the corresponding regularized M -estimators have fast convergence rates. 1

4 0.12500173 169 nips-2009-Nonlinear Learning using Local Coordinate Coding

Author: Kai Yu, Tong Zhang, Yihong Gong

Abstract: This paper introduces a new method for semi-supervised learning on high dimensional nonlinear manifolds, which includes a phase of unsupervised basis learning and a phase of supervised function learning. The learned bases provide a set of anchor points to form a local coordinate system, such that each data point x on the manifold can be locally approximated by a linear combination of its nearby anchor points, and the linear weights become its local coordinate coding. We show that a high dimensional nonlinear function can be approximated by a global linear function with respect to this coding scheme, and the approximation quality is ensured by the locality of such coding. The method turns a difﬁcult nonlinear learning problem into a simple global linear learning problem, which overcomes some drawbacks of traditional local learning methods. 1

5 0.12178318 212 nips-2009-Semi-Supervised Learning in Gigantic Image Collections

Author: Rob Fergus, Yair Weiss, Antonio Torralba

Abstract: With the advent of the Internet it is now possible to collect hundreds of millions of images. These images come with varying degrees of label information. “Clean labels” can be manually obtained on a small fraction, “noisy labels” may be extracted automatically from surrounding text, while for most images there are no labels at all. Semi-supervised learning is a principled framework for combining these different label sources. However, it scales polynomially with the number of images, making it impractical for use on gigantic collections with hundreds of millions of images and thousands of classes. In this paper we show how to utilize recent results in machine learning to obtain highly efﬁcient approximations for semi-supervised learning that are linear in the number of images. Speciﬁcally, we use the convergence of the eigenvectors of the normalized graph Laplacian to eigenfunctions of weighted Laplace-Beltrami operators. Our algorithm enables us to apply semi-supervised learning to a database of 80 million images gathered from the Internet. 1

6 0.11848962 137 nips-2009-Learning transport operators for image manifolds

7 0.11378017 103 nips-2009-Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation

8 0.10710309 128 nips-2009-Learning Non-Linear Combinations of Kernels

9 0.10437172 213 nips-2009-Semi-supervised Learning using Sparse Eigenfunction Bases

10 0.10158034 37 nips-2009-Asymptotically Optimal Regularization in Smooth Parametric Models

11 0.10136647 207 nips-2009-Robust Nonparametric Regression with Metric-Space Valued Output

12 0.10066563 146 nips-2009-Manifold Regularization for SIR with Rate Root-n Convergence

13 0.09036433 238 nips-2009-Submanifold density estimation

14 0.087662786 97 nips-2009-Free energy score space

15 0.085844137 26 nips-2009-Adaptive Regularization for Transductive Support Vector Machine

16 0.082493626 38 nips-2009-Augmenting Feature-driven fMRI Analyses: Semi-supervised learning and resting state activity

17 0.080116652 224 nips-2009-Sparse and Locally Constant Gaussian Graphical Models

18 0.076343477 108 nips-2009-Heterogeneous multitask learning with joint sparsity constraints

19 0.073729679 129 nips-2009-Learning a Small Mixture of Trees

20 0.072189167 256 nips-2009-Which graphical models are difficult to learn?

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.236), (1, 0.082), (2, -0.081), (3, 0.162), (4, -0.086), (5, 0.006), (6, 0.06), (7, 0.023), (8, 0.039), (9, 0.102), (10, -0.049), (11, 0.144), (12, -0.019), (13, -0.125), (14, 0.01), (15, -0.041), (16, -0.101), (17, -0.009), (18, 0.044), (19, -0.003), (20, -0.139), (21, 0.01), (22, 0.055), (23, -0.104), (24, 0.091), (25, 0.032), (26, 0.093), (27, 0.08), (28, -0.019), (29, 0.136), (30, 0.013), (31, 0.043), (32, 0.089), (33, -0.042), (34, -0.118), (35, -0.089), (36, -0.074), (37, -0.013), (38, 0.024), (39, 0.018), (40, 0.015), (41, 0.062), (42, 0.179), (43, 0.075), (44, -0.042), (45, 0.011), (46, 0.002), (47, 0.063), (48, -0.114), (49, 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96904051 214 nips-2009-Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction

Author: Kwang I. Kim, Florian Steinke, Matthias Hein

2 0.7436738 146 nips-2009-Manifold Regularization for SIR with Rate Root-n Convergence

Author: Wei Bian, Dacheng Tao

Abstract: In this paper, we study the manifold regularization for the Sliced Inverse Regression (SIR). The manifold regularization improves the standard SIR in two aspects: 1) it encodes the local geometry for SIR and 2) it enables SIR to deal with transductive and semi-supervised learning problems. We prove that the proposed graph Laplacian based regularization is convergent at rate root-n. The projection directions of the regularized SIR are optimized by using a conjugate gradient method on the Grassmann manifold. Experimental results support our theory.

3 0.73594862 229 nips-2009-Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data

Author: Boaz Nadler, Nathan Srebro, Xueyuan Zhou

4 0.68712711 26 nips-2009-Adaptive Regularization for Transductive Support Vector Machine

Author: Zenglin Xu, Rong Jin, Jianke Zhu, Irwin King, Michael Lyu, Zhirong Yang

Abstract: We discuss the framework of Transductive Support Vector Machine (TSVM) from the perspective of the regularization strength induced by the unlabeled data. In this framework, SVM and TSVM can be regarded as a learning machine without regularization and one with full regularization from the unlabeled data, respectively. Therefore, to supplement this framework of the regularization strength, it is necessary to introduce data-dependant partial regularization. To this end, we reformulate TSVM into a form with controllable regularization strength, which includes SVM and TSVM as special cases. Furthermore, we introduce a method of adaptive regularization that is data dependant and is based on the smoothness assumption. Experiments on a set of benchmark data sets indicate the promising results of the proposed work compared with state-of-the-art TSVM algorithms. 1

5 0.61929417 103 nips-2009-Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation

Author: Yusuke Watanabe, Kenji Fukumizu

Abstract: We propose a new approach to the analysis of Loopy Belief Propagation (LBP) by establishing a formula that connects the Hessian of the Bethe free energy with the edge zeta function. The formula has a number of theoretical implications on LBP. It is applied to give a sufﬁcient condition that the Hessian of the Bethe free energy is positive deﬁnite, which shows non-convexity for graphs with multiple cycles. The formula clariﬁes the relation between the local stability of a ﬁxed point of LBP and local minima of the Bethe free energy. We also propose a new approach to the uniqueness of LBP ﬁxed point, and show various conditions of uniqueness. 1

6 0.5986557 238 nips-2009-Submanifold density estimation

7 0.51818311 207 nips-2009-Robust Nonparametric Regression with Metric-Space Valued Output

8 0.5161429 169 nips-2009-Nonlinear Learning using Local Coordinate Coding

9 0.48603469 137 nips-2009-Learning transport operators for image manifolds

10 0.47484946 34 nips-2009-Anomaly Detection with Score functions based on Nearest Neighbor Graphs

11 0.46047047 37 nips-2009-Asymptotically Optimal Regularization in Smooth Parametric Models

12 0.45688081 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

13 0.45558515 91 nips-2009-Fast, smooth and adaptive regression in metric spaces

14 0.45156068 15 nips-2009-A Rate Distortion Approach for Semi-Supervised Conditional Random Fields

15 0.44535804 38 nips-2009-Augmenting Feature-driven fMRI Analyses: Semi-supervised learning and resting state activity

16 0.44165635 213 nips-2009-Semi-supervised Learning using Sparse Eigenfunction Bases

17 0.43456888 106 nips-2009-Heavy-Tailed Symmetric Stochastic Neighbor Embedding

18 0.43246621 97 nips-2009-Free energy score space

19 0.43075407 124 nips-2009-Lattice Regression

20 0.42959192 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(24, 0.04), (25, 0.242), (35, 0.034), (36, 0.141), (39, 0.048), (43, 0.104), (50, 0.01), (58, 0.104), (71, 0.035), (81, 0.022), (86, 0.085), (91, 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95579439 214 nips-2009-Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction

Author: Kwang I. Kim, Florian Steinke, Matthias Hein

2 0.92786402 258 nips-2009-Whose Vote Should Count More: Optimal Integration of Labels from Labelers of Unknown Expertise

Author: Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier R. Movellan, Paul L. Ruvolo

Abstract: Modern machine learning-based approaches to computer vision require very large databases of hand labeled images. Some contemporary vision systems already require on the order of millions of images for training (e.g., Omron face detector [9]). New Internet-based services allow for a large number of labelers to collaborate around the world at very low cost. However, using these services brings interesting theoretical and practical challenges: (1) The labelers may have wide ranging levels of expertise which are unknown a priori, and in some cases may be adversarial; (2) images may vary in their level of difﬁculty; and (3) multiple labels for the same image must be combined to provide an estimate of the actual label of the image. Probabilistic approaches provide a principled way to approach these problems. In this paper we present a probabilistic model and use it to simultaneously infer the label of each image, the expertise of each labeler, and the difﬁculty of each image. On both simulated and real data, we demonstrate that the model outperforms the commonly used “Majority Vote” heuristic for inferring image labels, and is robust to both noisy and adversarial labelers. 1

3 0.91951412 245 nips-2009-Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation

Author: Shuheng Zhou

Abstract: Given n noisy samples with p dimensions, where n ≪ p, we show that the multistep thresholding procedure can accurately estimate a sparse vector β ∈ Rp in a linear model, under the restricted eigenvalue conditions (Bickel-Ritov-Tsybakov 09). Thus our conditions for model selection consistency are considerably weaker than what has been achieved in previous works. More importantly, this method allows very signiﬁcant values of s, which is the number of non-zero elements in the true parameter. For example, it works for cases where the ordinary Lasso would have failed. Finally, we show that if X obeys a uniform uncertainty principle and if the true parameter is sufﬁciently sparse, the Gauss-Dantzig selector (Cand` se Tao 07) achieves the ℓ2 loss within a logarithmic factor of the ideal mean square error one would achieve with an oracle which would supply perfect information about which coordinates are non-zero and which are above the noise level, while selecting a sufﬁciently sparse model. 1

4 0.91750139 7 nips-2009-A Data-Driven Approach to Modeling Choice

Author: Vivek Farias, Srikanth Jagabathula, Devavrat Shah

Abstract: We visit the following fundamental problem: For a ‘generic’ model of consumer choice (namely, distributions over preference lists) and a limited amount of data on how consumers actually make decisions (such as marginal preference information), how may one predict revenues from oﬀering a particular assortment of choices? This problem is central to areas within operations research, marketing and econometrics. We present a framework to answer such questions and design a number of tractable algorithms (from a data and computational standpoint) for the same. 1

5 0.91415095 160 nips-2009-Multiple Incremental Decremental Learning of Support Vector Machines

Author: Masayuki Karasuyama, Ichiro Takeuchi

Abstract: We propose a multiple incremental decremental algorithm of Support Vector Machine (SVM). Conventional single incremental decremental SVM can update the trained model efﬁciently when single data point is added to or removed from the training set. When we add and/or remove multiple data points, this algorithm is time-consuming because we need to repeatedly apply it to each data point. The proposed algorithm is computationally more efﬁcient when multiple data points are added and/or removed simultaneously. The single incremental decremental algorithm is built on an optimization technique called parametric programming. We extend the idea and introduce multi-parametric programming for developing the proposed algorithm. Experimental results on synthetic and real data sets indicate that the proposed algorithm can signiﬁcantly reduce the computational cost of multiple incremental decremental operation. Our approach is especially useful for online SVM learning in which we need to remove old data points and add new data points in a short amount of time.

6 0.90788841 201 nips-2009-Region-based Segmentation and Object Detection

7 0.89297062 133 nips-2009-Learning models of object structure

8 0.88404858 211 nips-2009-Segmenting Scenes by Matching Image Composites

9 0.88281232 25 nips-2009-Adaptive Design Optimization in Experiments with People

10 0.881185 225 nips-2009-Sparsistent Learning of Varying-coefficient Models with Structural Changes

11 0.87431592 1 nips-2009-$L 1$-Penalized Robust Estimation for a Class of Inverse Problems Arising in Multiview Geometry

12 0.86883837 229 nips-2009-Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data

13 0.86460096 152 nips-2009-Measuring model complexity with the prior predictive

14 0.85124683 175 nips-2009-Occlusive Components Analysis

15 0.84373915 37 nips-2009-Asymptotically Optimal Regularization in Smooth Parametric Models

16 0.84330553 174 nips-2009-Nonparametric Latent Feature Models for Link Prediction

17 0.8432405 131 nips-2009-Learning from Neighboring Strokes: Combining Appearance and Context for Multi-Domain Sketch Recognition

18 0.84176868 97 nips-2009-Free energy score space

19 0.84103543 5 nips-2009-A Bayesian Model for Simultaneous Image Clustering, Annotation and Object Segmentation

20 0.84022868 115 nips-2009-Individuation, Identification and Object Discovery