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

122 nips-2009-Label Selection on Graphs

Source: pdf

Author: Andrew Guillory, Jeff A. Bilmes

Abstract: We investigate methods for selecting sets of labeled vertices for use in predicting the labels of vertices on a graph. We speciﬁcally study methods which choose a single batch of labeled vertices (i.e. ofﬂine, non sequential methods). In this setting, we ﬁnd common graph smoothness assumptions directly motivate simple label selection methods with interesting theoretical guarantees. These methods bound prediction error in terms of the smoothness of the true labels with respect to the graph. Some of these bounds give new motivations for previously proposed algorithms, and some suggest new algorithms which we evaluate. We show improved performance over baseline methods on several real world data sets. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We investigate methods for selecting sets of labeled vertices for use in predicting the labels of vertices on a graph. [sent-5, score-0.346]

2 We speciﬁcally study methods which choose a single batch of labeled vertices (i. [sent-6, score-0.242]

3 In this setting, we ﬁnd common graph smoothness assumptions directly motivate simple label selection methods with interesting theoretical guarantees. [sent-9, score-0.495]

4 These methods bound prediction error in terms of the smoothness of the true labels with respect to the graph. [sent-10, score-0.393]

5 Assume we have an undirected graph of n nodes given by a symmetric weight matrix W . [sent-14, score-0.295]

6 The ith node in the graph has a label yi ∈ {0, 1} stored in a vector of labels y ∈ {0, 1}n . [sent-15, score-0.675]

7 We want to predict all of y from the labels yL for a labeled subset L ⊂ V = [n]. [sent-16, score-0.236]

8 In order to bound prediction error, we assume that the labels are smoothly varying with respect to the underlying graph. [sent-24, score-0.263]

9 The simple smoothness assumption we use is that i,j Wi,j |yi − yj | is small. [sent-25, score-0.512]

10 This smoothness assumption has been used by graph-based semi-supervised learning algorithms which compute y using a labeled set L chosen uniformly at random from V [Blum and ˆ Chawla, 2001, Hanneke, 2006, Pelckmans et al. [sent-27, score-0.289]

11 , 2006] and by online graph labeling methods that operate on an adversarially ordered stream of vertices [Pelckmans and Suykens, 2008, Brautbar, 2009, Herbster et al. [sent-29, score-0.371]

12 , 2008, 2005, Herbster, 2008] In this work we consider methods that make use of the smoothness assumption and structure of the graph in order to both select L as well as make predictions. [sent-30, score-0.243]

13 Our hope is to achieve higher prediction accuracy as compared to random label selection and other methods for choosing L. [sent-31, score-0.322]

14 The ˆ single batch, ofﬂine label selection problem is important in many real-world applications because it is often the case that problem constraints make requesting more than one batch of labels very costly. [sent-33, score-0.461]

15 For example, if requesting a label involves a time consuming, expensive experiment (potentially 1 involving human subjects), it may be signiﬁcantly less costly to run a single batch of experiments in parallel as compared to running experiments in series. [sent-34, score-0.299]

16 We give several methods which, under the assumption i,j Wi,j |yi − yj | is small, guarantee the prediction error ||y − y ||2 will also be small. [sent-35, score-0.575]

17 Some of the bounds provide interesting justiﬁcations ˆ for previously used methods, and we show improved performance over random label selection and baseline submodular maximization methods on several real world data sets. [sent-36, score-0.541]

18 2 General Worst Case Bound We ﬁrst give a simple worst case bound on prediction error in terms of label smoothness using few assumptions about the method used to select labels or make predictions. [sent-37, score-0.628]

19 The ˆ bound motivates an interesting method for selecting labeled points and provides a new motivation for a standard prediction method Blum and Chawla [2001] when used with arbitrarily selected L. [sent-41, score-0.334]

20 Deﬁne the graph cut function Γ(A, B) Ψ(L) i∈A,j∈B min T ⊆(V \L)=0 Wi,j . [sent-43, score-0.435]

21 Let Γ(T, (V \ T )) |T | Note this function is different from normalized cut (also called sparsest cut). [sent-44, score-0.249]

22 In this function, the denominator is simply |T | while for normalized cut the denominator is min(|T |, |V \ T |). [sent-45, score-0.249]

23 This difference is important: computing normalized cut is NP-hard, but we will show Ψ(L) can be computed in polynomial time. [sent-46, score-0.293]

24 Ψ(L) measures how easily we can cut a large portion of the graph away from L. [sent-47, score-0.366]

25 We show that Ψ(L) where L is the set of labeled vertices measures to what extent prediction error can be high relative to label smoothness. [sent-49, score-0.494]

26 This makes intuitive sense because if Ψ(L) is small than there is a large set of unlabeled nodes which are weakly connected to the remainder of the graph (including L). [sent-50, score-0.298]

27 For any y consistent with a labeled set L ˆ ||y − y ||2 ≤ ˆ 1 2Ψ(L) Wi,j (|yi − yj | ⊕ |ˆi − yj |) ≤ y ˆ i,j 1 ( Wi,j |yi − yj | + 2Ψ(L) i,j Wi,j |ˆi − yj |) y ˆ i,j where ⊕ is the XOR operator. [sent-52, score-1.828]

28 First note that I ∩ L = ∅ (none of the labeled points are incorrectly classiﬁed). [sent-55, score-0.239]

29 |I| = Γ(I, V \ I) |I| Γ(I, V \ I) ≤ Γ(I, V \ I) Ψ(L) Note that for all of the edges (i, j) counted in Γ(I, V \ I), yi = yj implies yi = yj and yi = yj ˆ ˆ ˆ ˆ implies yi = yj . [sent-56, score-2.441]

31 This bound provides an interesting justiﬁcation for the algorithm in Blum and Chawla [2001] and related methods when used with arbitrarily selected labeled sets. [sent-59, score-0.238]

32 The term involving the predicted labels, i,j Wi,j |ˆi − yj |, is the objective function minimized under the constraint yL = yL by the y ˆ ˆ algorithm of Blum and Chawla [2001]. [sent-60, score-0.425]

33 If y = argminy∈{0,1}n :ˆL =yL ˆ ˆ y Wi,j |ˆi − yj | y ˆ i,j for a labeled set L then ||y − y ||2 ≤ ˆ Proof. [sent-65, score-0.553]

35 ˆ The bound also motivates a simple label selection method. [sent-69, score-0.337]

36 Our heuristic is then to simply add a random element from this cut to L. [sent-91, score-0.269]

37 In the next section, we describe a lower bound on the Ψ function based on a notion of graph covering. [sent-96, score-0.241]

38 In other words, every node in the graph is either in L or connected with total weight at least α to nodes in L (or both). [sent-102, score-0.331]

39 Then, α can replace Ψ(L) in the bound in the previous section for a looser upper bound on prediction error. [sent-109, score-0.282]

40 For any y consistent with a labeled set L that is an α-cover ˆ ||y − y ||2 ≤ ˆ 1 2α Wi,j (|yi − yj | ⊕ |ˆi − yj |) ≤ y ˆ i,j 1 ( Wi,j |yi − yj | + 2α i,j Wi,j |ˆi − yj |) y ˆ i,j where ⊕ is the XOR operator. [sent-112, score-1.828]

41 In particular, for a labeled set L that is an α cover, we assume unlabeled nodes are labeled with the weighted majority vote of neighbors in L. [sent-114, score-0.555]

42 In other words, set yi = yi for i ∈ L, and set yi = y for i ∈ L with y such that j∈L:yj =y Wi,j ≥ j∈L:yj =y Wi,j . [sent-115, score-0.531]

43 If L is an α-cover and V \ L is labeled according to majority vote ||y − y ||2 ≤ ˆ 1 α Wi,j |yi − yj |(1 − |ˆi − yj |) ≤ y ˆ i,j 1 α Wi,j |yi − yj | i,j Proof. [sent-118, score-1.56]

44 For every incorrectly labeled node, there is a set of nodes Li = {j ∈ L : yi = yj } which ˆ ˆ satisﬁes yi = yj ∀j ∈ Li , and j∈Li Wi,j ≥ α/2. [sent-120, score-1.526]

45 We then have for every incorrectly labeled node a unique set of edges with total weight at least α/2 included inside the summation in the middle expression. [sent-121, score-0.312]

46 Then, we can replace F with 1 Fα (L) = min( Wi,j , α) n i j∈L and solve min |L| : Fα (L) ≥ α L⊆V This is a submodular set cover problem. [sent-130, score-0.246]

47 In particular, an α-cover is a dominating set for binary weight graphs and α = 1. [sent-137, score-0.263]

48 Finding the smallest dominating set L in a binary weight graph is N P -complete. [sent-142, score-0.351]

49 4 Normalized Cut Algorithm In this section we consider an algorithm that clusters the data set and replaces the Ψ function with a normalized cut value. [sent-148, score-0.292]

50 The normalized cut value for a set T ⊂ V is Γ(T, V \ T ) min(|T |, |V \ T |) In other words, normalized cut is the ratio between the cut value for T and minimum of the size of T and its complement. [sent-149, score-0.739]

51 Computing the minimum normalized cut for a graph is NP-hard. [sent-150, score-0.436]

52 Sk , 2) for each cluster request sufﬁcient labels to estimate the majority class with probability at least 1 − δ/k, and 3) label all nodes in each cluster with the majority label for that cluster. [sent-154, score-1.065]

53 Here the probability 1 − δ/k is with respect to the choice of the labeled nodes used to estimate the majority class for each cluster. [sent-155, score-0.364]

54 If y labels every i ∈ Sl ˆ according to the estimated majority label for Sl then with probability at least 1 − δ 1 1 Wi,j |yi − yj | ≤ ||y − y ||2 ≤ ˆ Wi,j |yi − yj | 2φl 2φ i,j l i,j∈Sl where φl = min T ⊂Sl Γ(T, Sl \ T ) min(|T |, |Sl \ T |) and φ = min φl l 5 Proof. [sent-161, score-1.421]

55 By the union bound, the estimated majority labels for all of the clusters are correct with probability at least 1 − δ. [sent-162, score-0.278]

56 Let I be the set of incorrectly labeled nodes (errors). [sent-163, score-0.322]

57 I = l=1 Il Note that |Il | ≤ |Sl \ Il | since we labeled cluster according to the majority label for the cluster. [sent-166, score-0.533]

58 Then |Il | |I| = |Il | = Γ(Il , Sl \ Il ) Γ(Il , Sl \ Il ) l = l Γ(Il , Sl \ Il ) l min(|Il |, |Sl \ Il |) Γ(Il , Sl \ Il ) Γ(Il , Sl \ Il ) φl ≤ l For any i, j, with i ∈ Il and j ∈ Sl \ Il , we must have yi = yj . [sent-167, score-0.602]

59 Also, for any i, j with yi = yj and i, j ∈ Sl , either i ∈ Il or j ∈ Il . [sent-168, score-0.602]

60 In other words, there is a one-to-one correspondence between 1) edges i, j for which i, j ∈ Sl and either i ∈ Il or j ∈ Il and 2) edges i, j for which i, j ∈ Sl and yi = yj . [sent-169, score-0.668]

61 Note in practice we only label the unlabeled nodes in each cluster using the majority label estimates. [sent-171, score-0.745]

62 Using the true labels for the labeled nodes only decreases error, so the theorem still holds. [sent-172, score-0.383]

63 This is different from the standard normalized cut clustering problem; we do not care if clusters are strongly connected to each other only that each cluster is internally dense. [sent-176, score-0.457]

64 In our experiments, we try several standard clustering algorithms and achieve good real world performance, but it remains an interesting open question to design a clustering algorithm for directly maximizing φ. [sent-177, score-0.274]

65 An approach we have not yet tried is to use the error bound to choose between the results of different clustering algorithms. [sent-178, score-0.258]

66 If we uniformly sample labels from a cluster, standard results give that the probability of incorrectly estimating the majority decreases exponentially with the number of labels if the fraction of nodes in the minority class is bounded away from 1/2 by a constant. [sent-180, score-0.684]

67 We now show that if the labels are sufﬁciently smooth and the cluster is sufﬁciently dense then the fraction of nodes in the minority class is small. [sent-181, score-0.407]

68 The fraction of nodes in the minority class of S is at most i,j∈S Wi,j |yi − yj | φ|S| where φ = min T ⊂S Γ(T, S \ T ) min(|T |, |S \ T |) Proof. [sent-183, score-0.713]

69 Let S − be the set of nodes belonging to the minority class and S + be the set of nodes belonging to the other class. [sent-184, score-0.302]

70 In our experiments, we simply request a single label per cluster. [sent-187, score-0.236]

71 We cluster the data then label each cluster according to a single randomly chosen point. [sent-314, score-0.358]

72 We chose the number of clusters to be equal to the number of labeled points observing that if a cluster is split evenly amongst the two classes then we will have a high error rate regardless of how well we estimate the majority class. [sent-315, score-0.447]

73 We tried three clustering algorithms: a spectral clustering method [Ng et al. [sent-316, score-0.323]

74 As a baseline we use random label selection and prediction using the label propagation method of Bengio et al. [sent-318, score-0.684]

75 We also experimented with a method motivated by the graph covering bound, but for lack of space we omit these results. [sent-320, score-0.251]

76 We set k1 and k2 for each data set and label count to be the parameters which give the lowest average error rate for label propagation averaging over 100 trials and choosing from the set {5, 10, 50, 100}. [sent-327, score-0.557]

77 We tune the graph construction parameters to give low error for the baseline method to ensure any bias is in favor of the baseline as opposed to the new methods we propose. [sent-328, score-0.33]

78 We then report average error over 1000 trials in the 10 label case and 100 trials in the 100 label case for each combination of data set and algorithm. [sent-329, score-0.515]

79 These methods performed well matching or beating the baseline method on the 10 label trials and in some cases signiﬁcantly improving performance. [sent-340, score-0.283]

80 In general, we expect label selection to help more when learning from very few labels. [sent-343, score-0.252]

81 The clustering methods which work best seem to be methods which minimize normalize cut like objectives. [sent-345, score-0.295]

82 This is not surprising given the presence of the normalized cut term in Theorem 4, but it is an open problem to give a clustering method for directly minimizing the bound. [sent-346, score-0.371]

83 One modiﬁcation we tried is to use label propagation for prediction in conjunction with our label selection methods. [sent-351, score-0.608]

84 6 Related Work Previous work has also used clustering, covering, and other graph properties to guide label selection on graphs. [sent-353, score-0.408]

85 We are, however, the ﬁrst to our knowledge to give bounds which relate prediction error to label smoothness for single batch label selection methods. [sent-354, score-0.805]

86 Most previous work on label selection methods for learning on graphs has considered active (i. [sent-355, score-0.361]

87 sequential) label selection [Zhu and Lafferty, 2003, Pucci et al. [sent-357, score-0.326]

88 [2007] show in this setting O(c log(n/c)) where c = i,j Wi,j |yi − yj | labels are sufﬁcient and necessary to learn the labeling exactly under some balance assumptions. [sent-363, score-0.575]

89 In some cases, our bounds are better despite considering only non sequential label selection. [sent-365, score-0.257]

90 In comparison, our graph covering bound needs an α-cover with α = a/ . [sent-369, score-0.302]

91 For some graph topologies, the size of such a cover can grow sublinearly with n (for example if the graph contains large, dense clusters). [sent-370, score-0.36]

92 Other work has given generalization error bounds in terms of label smoothness [Pelckmans et al. [sent-375, score-0.461]

93 These bounds are PAC style which typically show that, roughly, the error rate decreases with O( i,j Wi,j |yi − yj |/(b|L|)) where b is the minimum 2-cut of the graph. [sent-378, score-0.558]

94 For example, if a binary weight graph contains c cliques of size n/c then, we can ﬁnd an α cover of size cα log(cα) giving an error rate of O( i,j Wi,j |yi − yj |/(nα)). [sent-380, score-0.728]

95 A line of work has examined mistake bounds in terms of label smoothness for online learning on graphs [Pelckmans and Suykens, 2008, Brautbar, 2009, Herbster et al. [sent-382, score-0.619]

96 Herbster [2008] also considers how cluster structure can improve mistake bounds in this setting and gives a mistake bound similar to our graph covering bound on prediction error. [sent-385, score-0.774]

97 Our work differs from this previous work by considering prediction error bounds for ofﬂine learning as opposed to mistake bounds for online learning. [sent-388, score-0.364]

98 The mistake bound setting is signiﬁcantly different as the prediction method receives feedback after every prediction. [sent-389, score-0.244]

99 Learning from labeled and unlabeled data using graph mincuts. [sent-414, score-0.317]

100 An analysis of graph cut size for transductive learning. [sent-448, score-0.405]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('yj', 0.425), ('sl', 0.339), ('il', 0.307), ('cut', 0.21), ('label', 0.198), ('yi', 0.177), ('herbster', 0.166), ('graph', 0.156), ('pelckmans', 0.142), ('dominating', 0.139), ('submodular', 0.129), ('labeled', 0.128), ('majority', 0.127), ('afshani', 0.119), ('chawla', 0.119), ('blum', 0.115), ('nodes', 0.109), ('labels', 0.108), ('yl', 0.108), ('metis', 0.095), ('mistake', 0.089), ('smoothness', 0.087), ('incorrectly', 0.085), ('clustering', 0.085), ('bound', 0.085), ('minority', 0.084), ('krause', 0.084), ('cuts', 0.082), ('cluster', 0.08), ('et', 0.074), ('prediction', 0.07), ('min', 0.069), ('graphs', 0.068), ('mint', 0.068), ('suykens', 0.062), ('covering', 0.061), ('valued', 0.061), ('heuristic', 0.059), ('bounds', 0.059), ('batch', 0.059), ('ine', 0.057), ('vertices', 0.055), ('selection', 0.054), ('hardness', 0.053), ('chapelle', 0.052), ('maximizing', 0.05), ('cover', 0.048), ('brautbar', 0.047), ('computecut', 0.047), ('guillory', 0.047), ('gus', 0.047), ('saran', 0.047), ('supermodular', 0.047), ('baseline', 0.047), ('tried', 0.045), ('computing', 0.044), ('online', 0.044), ('propagation', 0.043), ('error', 0.043), ('clusters', 0.043), ('labeling', 0.042), ('karypis', 0.042), ('looser', 0.042), ('pucci', 0.042), ('requesting', 0.042), ('xor', 0.042), ('active', 0.041), ('transductive', 0.039), ('normalized', 0.039), ('trials', 0.038), ('request', 0.038), ('bilmes', 0.038), ('hanneke', 0.038), ('theorem', 0.038), ('give', 0.037), ('node', 0.036), ('cunningham', 0.036), ('bengio', 0.035), ('spectral', 0.034), ('greedy', 0.034), ('zhao', 0.034), ('ow', 0.034), ('experimented', 0.034), ('edges', 0.033), ('unlabeled', 0.033), ('minimum', 0.031), ('weight', 0.03), ('vote', 0.03), ('terminates', 0.03), ('zhu', 0.029), ('seems', 0.028), ('lemma', 0.027), ('real', 0.027), ('world', 0.027), ('points', 0.026), ('binary', 0.026), ('fraction', 0.026), ('icml', 0.026), ('words', 0.025), ('selected', 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 122 nips-2009-Label Selection on Graphs

Author: Andrew Guillory, Jeff A. Bilmes

2 0.17920706 239 nips-2009-Submodularity Cuts and Applications

Author: Yoshinobu Kawahara, Kiyohito Nagano, Koji Tsuda, Jeff A. Bilmes

Abstract: Several key problems in machine learning, such as feature selection and active learning, can be formulated as submodular set function maximization. We present herein a novel algorithm for maximizing a submodular set function under a cardinality constraint — the algorithm is based on a cutting-plane method and is implemented as an iterative small-scale binary-integer linear programming procedure. It is well known that this problem is NP-hard, and the approximation factor achieved by the greedy algorithm is the theoretical limit for polynomial time. As for (non-polynomial time) exact algorithms that perform reasonably in practice, there has been very little in the literature although the problem is quite important for many applications. Our algorithm is guaranteed to ﬁnd the exact solution ﬁnitely many iterations, and it converges fast in practice due to the efﬁciency of the cutting-plane mechanism. Moreover, we also provide a method that produces successively decreasing upper-bounds of the optimal solution, while our algorithm provides successively increasing lower-bounds. Thus, the accuracy of the current solution can be estimated at any point, and the algorithm can be stopped early once a desired degree of tolerance is met. We evaluate our algorithm on sensor placement and feature selection applications showing good performance. 1

3 0.15028398 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

4 0.12188118 102 nips-2009-Graph-based Consensus Maximization among Multiple Supervised and Unsupervised Models

Author: Jing Gao, Feng Liang, Wei Fan, Yizhou Sun, Jiawei Han

Abstract: Ensemble classiﬁers such as bagging, boosting and model averaging are known to have improved accuracy and robustness over a single model. Their potential, however, is limited in applications which have no access to raw data but to the meta-level model output. In this paper, we study ensemble learning with output from multiple supervised and unsupervised models, a topic where little work has been done. Although unsupervised models, such as clustering, do not directly generate label prediction for each individual, they provide useful constraints for the joint prediction of a set of related objects. We propose to consolidate a classiﬁcation solution by maximizing the consensus among both supervised predictions and unsupervised constraints. We cast this ensemble task as an optimization problem on a bipartite graph, where the objective function favors the smoothness of the prediction over the graph, as well as penalizing deviations from the initial labeling provided by supervised models. We solve this problem through iterative propagation of probability estimates among neighboring nodes. Our method can also be interpreted as conducting a constrained embedding in a transformed space, or a ranking on the graph. Experimental results on three real applications demonstrate the beneﬁts of the proposed method over existing alternatives1 . 1

5 0.099065691 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification

Author: Amarnag Subramanya, Jeff A. Bilmes

Abstract: We prove certain theoretical properties of a graph-regularized transductive learning objective that is based on minimizing a Kullback-Leibler divergence based loss. These include showing that the iterative alternating minimization procedure used to minimize the objective converges to the correct solution and deriving a test for convergence. We also propose a graph node ordering algorithm that is cache cognizant and leads to a linear speedup in parallel computations. This ensures that the algorithm scales to large data sets. By making use of empirical evaluation on the TIMIT and Switchboard I corpora, we show this approach is able to outperform other state-of-the-art SSL approaches. In one instance, we solve a problem on a 120 million node graph. 1

6 0.098694667 212 nips-2009-Semi-Supervised Learning in Gigantic Image Collections

7 0.091536321 157 nips-2009-Multi-Label Prediction via Compressed Sensing

8 0.09139552 181 nips-2009-Online Learning of Assignments

9 0.09127669 71 nips-2009-Distribution-Calibrated Hierarchical Classification

10 0.090778209 141 nips-2009-Local Rules for Global MAP: When Do They Work ?

11 0.089387558 45 nips-2009-Beyond Convexity: Online Submodular Minimization

12 0.089375585 95 nips-2009-Fast subtree kernels on graphs

13 0.084136203 106 nips-2009-Heavy-Tailed Symmetric Stochastic Neighbor Embedding

14 0.083915263 120 nips-2009-Kernels and learning curves for Gaussian process regression on random graphs

15 0.07980001 57 nips-2009-Conditional Random Fields with High-Order Features for Sequence Labeling

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

17 0.078785688 160 nips-2009-Multiple Incremental Decremental Learning of Support Vector Machines

18 0.074821383 9 nips-2009-A Game-Theoretic Approach to Hypergraph Clustering

19 0.073258869 240 nips-2009-Sufficient Conditions for Agnostic Active Learnable

20 0.072894678 148 nips-2009-Matrix Completion from Power-Law Distributed Samples

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.214), (1, 0.112), (2, -0.047), (3, 0.031), (4, -0.057), (5, 0.019), (6, -0.095), (7, 0.041), (8, -0.127), (9, 0.026), (10, -0.183), (11, 0.058), (12, 0.057), (13, -0.11), (14, -0.057), (15, 0.2), (16, 0.076), (17, -0.092), (18, -0.026), (19, -0.07), (20, 0.026), (21, -0.032), (22, -0.009), (23, -0.024), (24, 0.039), (25, 0.011), (26, -0.046), (27, -0.07), (28, -0.062), (29, -0.163), (30, 0.105), (31, -0.097), (32, -0.085), (33, 0.173), (34, -0.01), (35, 0.016), (36, 0.09), (37, 0.086), (38, 0.054), (39, 0.036), (40, -0.013), (41, -0.05), (42, -0.061), (43, 0.152), (44, -0.054), (45, -0.001), (46, -0.066), (47, 0.003), (48, 0.006), (49, -0.039)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96272314 122 nips-2009-Label Selection on Graphs

Author: Andrew Guillory, Jeff A. Bilmes

2 0.65522194 102 nips-2009-Graph-based Consensus Maximization among Multiple Supervised and Unsupervised Models

Author: Jing Gao, Feng Liang, Wei Fan, Yizhou Sun, Jiawei Han

3 0.65007263 239 nips-2009-Submodularity Cuts and Applications

Author: Yoshinobu Kawahara, Kiyohito Nagano, Koji Tsuda, Jeff A. Bilmes

4 0.64188391 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification

Author: Amarnag Subramanya, Jeff A. Bilmes

5 0.56052589 71 nips-2009-Distribution-Calibrated Hierarchical Classification

Author: Ofer Dekel

Abstract: While many advances have already been made in hierarchical classiﬁcation learning, we take a step back and examine how a hierarchical classiﬁcation problem should be formally deﬁned. We pay particular attention to the fact that many arbitrary decisions go into the design of the label taxonomy that is given with the training data. Moreover, many hand-designed taxonomies are unbalanced and misrepresent the class structure in the underlying data distribution. We attempt to correct these problems by using the data distribution itself to calibrate the hierarchical classiﬁcation loss function. This distribution-based correction must be done with care, to avoid introducing unmanageable statistical dependencies into the learning problem. This leads us off the beaten path of binomial-type estimation and into the unfamiliar waters of geometric-type estimation. In this paper, we present a new calibrated deﬁnition of statistical risk for hierarchical classiﬁcation, an unbiased estimator for this risk, and a new algorithmic reduction from hierarchical classiﬁcation to cost-sensitive classiﬁcation.

6 0.55399084 149 nips-2009-Maximin affinity learning of image segmentation

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

8 0.51377654 160 nips-2009-Multiple Incremental Decremental Learning of Support Vector Machines

9 0.51098478 106 nips-2009-Heavy-Tailed Symmetric Stochastic Neighbor Embedding

10 0.50991476 127 nips-2009-Learning Label Embeddings for Nearest-Neighbor Multi-class Classification with an Application to Speech Recognition

11 0.50105798 234 nips-2009-Streaming k-means approximation

12 0.50054801 143 nips-2009-Localizing Bugs in Program Executions with Graphical Models

13 0.49207819 249 nips-2009-Tracking Dynamic Sources of Malicious Activity at Internet Scale

14 0.47645232 26 nips-2009-Adaptive Regularization for Transductive Support Vector Machine

15 0.46579924 72 nips-2009-Distribution Matching for Transduction

16 0.46413013 15 nips-2009-A Rate Distortion Approach for Semi-Supervised Conditional Random Fields

17 0.45371851 181 nips-2009-Online Learning of Assignments

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

19 0.44628224 49 nips-2009-Breaking Boundaries Between Induction Time and Diagnosis Time Active Information Acquisition

20 0.44498962 95 nips-2009-Fast subtree kernels on graphs

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(21, 0.01), (24, 0.121), (25, 0.123), (35, 0.043), (36, 0.112), (38, 0.205), (39, 0.067), (48, 0.011), (58, 0.061), (71, 0.04), (81, 0.024), (86, 0.095), (91, 0.011)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.85321182 122 nips-2009-Label Selection on Graphs

Author: Andrew Guillory, Jeff A. Bilmes

2 0.83523381 126 nips-2009-Learning Bregman Distance Functions and Its Application for Semi-Supervised Clustering

Author: Lei Wu, Rong Jin, Steven C. Hoi, Jianke Zhu, Nenghai Yu

Abstract: Learning distance functions with side information plays a key role in many machine learning and data mining applications. Conventional approaches often assume a Mahalanobis distance function. These approaches are limited in two aspects: (i) they are computationally expensive (even infeasible) for high dimensional data because the size of the metric is in the square of dimensionality; (ii) they assume a ﬁxed metric for the entire input space and therefore are unable to handle heterogeneous data. In this paper, we propose a novel scheme that learns nonlinear Bregman distance functions from side information using a nonparametric approach that is similar to support vector machines. The proposed scheme avoids the assumption of ﬁxed metric by implicitly deriving a local distance from the Hessian matrix of a convex function that is used to generate the Bregman distance function. We also present an efﬁcient learning algorithm for the proposed scheme for distance function learning. The extensive experiments with semi-supervised clustering show the proposed technique (i) outperforms the state-of-the-art approaches for distance function learning, and (ii) is computationally efﬁcient for high dimensional data. 1

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

Author: Boaz Nadler, Nathan Srebro, Xueyuan Zhou

4 0.72648859 91 nips-2009-Fast, smooth and adaptive regression in metric spaces

Author: Samory Kpotufe

Abstract: It was recently shown that certain nonparametric regressors can escape the curse of dimensionality when the intrinsic dimension of data is low ([1, 2]). We prove some stronger results in more general settings. In particular, we consider a regressor which, by combining aspects of both tree-based regression and kernel regression, adapts to intrinsic dimension, operates on general metrics, yields a smooth function, and evaluates in time O(log n). We derive a tight convergence rate of the form n−2/(2+d) where d is the Assouad dimension of the input space. 1

5 0.72546679 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

6 0.72068173 116 nips-2009-Information-theoretic lower bounds on the oracle complexity of convex optimization

7 0.71975672 212 nips-2009-Semi-Supervised Learning in Gigantic Image Collections

8 0.71795243 59 nips-2009-Construction of Nonparametric Bayesian Models from Parametric Bayes Equations

9 0.71636617 71 nips-2009-Distribution-Calibrated Hierarchical Classification

10 0.7162447 78 nips-2009-Efficient Moments-based Permutation Tests

11 0.71544158 112 nips-2009-Human Rademacher Complexity

12 0.71530163 9 nips-2009-A Game-Theoretic Approach to Hypergraph Clustering

13 0.71487397 129 nips-2009-Learning a Small Mixture of Trees

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

15 0.71455282 225 nips-2009-Sparsistent Learning of Varying-coefficient Models with Structural Changes

16 0.71273112 86 nips-2009-Exploring Functional Connectivities of the Human Brain using Multivariate Information Analysis

17 0.71252519 211 nips-2009-Segmenting Scenes by Matching Image Composites

18 0.71252126 157 nips-2009-Multi-Label Prediction via Compressed Sensing

19 0.7116943 97 nips-2009-Free energy score space

20 0.70958894 133 nips-2009-Learning models of object structure