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

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

Source: pdf

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

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 We also propose a graph node ordering algorithm that is cache cognizant and leads to a linear speedup in parallel computations. [sent-6, score-0.518]

2 In one instance, we solve a problem on a 120 million node graph. [sent-9, score-0.133]

3 1 Introduction The process of training classiﬁers with small amounts of labeled data and relatively large amounts of unlabeled data is known as semi-supervised learning (SSL). [sent-10, score-0.287]

4 In many applications, such as speech recognition, annotating training data is time-consuming, tedious and error-prone. [sent-11, score-0.18]

5 SSL lends itself as a useful technique in such situations as one only needs to annotate small amounts of data for training models. [sent-12, score-0.135]

6 Here one assumes that the labeled and unlabeled samples are embedded within a low-dimensional manifold expressed by a graph — each data sample is represented by a vertex within a weighted graph with the weights providing a measure of similarity between vertices. [sent-15, score-0.545]

7 Some graph-based SSL approaches perform random walks on the graph for inference [3, 4] while others optimize a loss function based on smoothness constraints derived from the graph [5, 6, 7, 8]. [sent-16, score-0.322]

8 SSL is based on the premise that unlabeled data is easily 1 obtained, and adding large quantities of unlabeled data leads to improved performance. [sent-26, score-0.192]

9 [15] solves a graph transduction problem with 650,000 samples. [sent-32, score-0.206]

10 To the best of our knowledge, the largest graph-based problem solved to date had about 900,000 samples (includes both labeled and unlabeled data) [16]. [sent-33, score-0.168]

11 6 billion blog posts, 60 billion emails, 2 million photos and 200,000 videos every day [17]. [sent-36, score-0.126]

12 In addition, we propose a graph node ordering algorithm that is cache cognizant and makes obtaining a linear speedup with a parallel implementation more likely. [sent-40, score-0.518]

13 The node ordering algorithm is quite general and can be applied to graph-based SSL algorithm such as [5, 11]. [sent-42, score-0.15]

14 In one instance, we solve a SSL problem over a graph with 120 million vertices. [sent-43, score-0.223]

15 We use the phone classiﬁcation problem to demonstrate the scalability of the algorithm. [sent-44, score-0.321]

16 2 Graph-based SSL Let Dl = {(xi , ri )}l be the set of labeled samples, Du = {xi }l+u , the set of unlabeled samples i=1 i=l+1 and D {Dl , Du }. [sent-46, score-0.249]

17 Here ri is an encoding of the labeled data and will be explained shortly. [sent-47, score-0.153]

18 The ﬁrst step in most graph-based SSL algorithms is the construction of an undirected weighted graph G = (V, E), where the vertices (nodes) V = {1, . [sent-51, score-0.202]

19 Let Vl and Vu be the set of labeled and unlabeled vertices respectively. [sent-55, score-0.209]

20 There are many ways of constructing the graph (see section 6. [sent-57, score-0.161]

21 In this paper, we use symmetric k-nearest neighbor (NN) graphs — that is, we ﬁrst form wij [W]ij = sim(xi , xj ) and then make this graph sparse by setting wij = 0 unless i is one of j’s k nearest neighbors or j is one of i’s k nearest neighbors. [sent-59, score-0.61]

22 Choosing the correct similarity measure and |N (i)| are crucial steps in the success of any graph-based SSL algorithm as it determines the graph [2]. [sent-62, score-0.161]

23 For each i ∈ V and j ∈ Vl , deﬁne probability measures pi and rj respectively over the measurable space (Y, Y). [sent-63, score-0.306]

24 As we only consider classiﬁcation problems here, pi and ri are multinomial distributions, pi (y) is the probability that xi belongs to class y and the classiﬁcation result is given by argmaxy pi (y). [sent-66, score-0.679]

25 If the labels are known with certainty, then rj is a “one-hot” vector (with the single 1 at the appropriate position in the vector). [sent-68, score-0.145]

26 rj is also capable of representing cases where the label is uncertain, i. [sent-69, score-0.133]

27 If it is the case that rj (¯1 ), rj (¯2 ) > 0, y1 = y2 , it does not y y ¯ ¯ imply that the input xj possesses two output labels y1 and y2 . [sent-73, score-0.248]

28 As pi , ri are probability measures, they lie within a |Y|-dimensional probability simplex which we represent using |Y| and so pi , ri ∈ |Y| (henceforth denoted as ). [sent-75, score-0.504]

29 Consider the optimization problem proposed in [11] where p∗ = min C1 (p) and m p∈ l C1 (p) = m m DKL ri ||pi + µ i=1 wij DKL pi ||pj − ν i=1 j∈N (i) 2 H(pi ). [sent-86, score-0.354]

30 The ﬁrst term in C1 penalizes the solution pi i ∈ {1, . [sent-90, score-0.214]

31 , l}, when it is far away from the labeled training data Dl , but it does not insist that pi = ri , as allowing for deviations from ri can help especially with noisy labels [20] or when the graph is extremely dense in certain regions. [sent-93, score-0.647]

32 If wij is large, we prefer a solution in which pi and pj are close in the KLD sense. [sent-97, score-0.312]

33 The last term encourages each pi to be close to the uniform distribution if not preferred to the contrary by the ﬁrst two terms. [sent-98, score-0.204]

34 We conjecture that by maximizing the entropy of each pi , the classiﬁer has a better chance of producing high entropy results in graph regions of low conﬁdence (e. [sent-102, score-0.43]

35 C1 is not amenable to optimization using AM and so we have proposed a modiﬁed version of the objective where (p∗ , q∗ ) = minm C2 (p, q) and p,q∈ m l m DKL ri ||qi + µ C2 (p, q) = wij DKL pi ||qj − ν i=1 j∈N (i) i=1 H(pi ). [sent-117, score-0.436]

36 i=1 In the above, a third measure qi , ∀ i ∈ V is deﬁned over the measurable space (Y, Y), W = W + αIn , N (i) = {{i} ∪ N (i)} and α ≥ 0. [sent-118, score-0.155]

37 Here the qi ’s play a similar role as the pi ’s and can potentially be used to obtain a ﬁnal classiﬁcation result (argmaxy qi (y)), but α, which is a hyper-parameter, plays an important role in ensuring that pi and qi are close ∀ i. [sent-119, score-0.711]

38 While the ﬁrst term encourages qi for the labeled vertices to be close to the labels, ri , the last term encourages higher entropy pi ’s. [sent-123, score-0.603]

39 The second term, in addition to acting as a graph regularizer, also acts as glue between the p’s and q’s. [sent-124, score-0.161]

40 The update equations for solving C2 (p, q) are given by (n) pi (y) = µ exp{ γi y µ exp{ γi (n−1) j wij log qj (y)} (n−1) j wij log qj (y)} (n) and qi (y) = ri (y)δ(i ≤ l) + µ δ(i ≤ l) + µ (n) j wji pj (y) j wji where γi = ν + µ j wij . [sent-125, score-0.874]

41 While the two steps of the AM procedure in the case of Tsuda’s work have closed form solutions and the approach is applicable to hyper-graphs, one of the updates (equation 13 in [8]) is a special of the (n) update for pi . [sent-147, score-0.171]

42 If (0) p(n) = argmin C2 (p, q(n−1) ), q(n) = argmin C2 (p(n) , q) and qi (y) > 0 ∀ y ∈ Y, ∀i then p∈ m q∈ m (a) C2 (p, q) + C2 (p, p(0) ) ≥ C2 (p, q(1) ) + C2 (p(1) , q(1) ) for all p, q ∈ (n) (b) lim C2 (p n→∞ (n) ,q ) = inf p,q∈ m m , and C2 (p, q). [sent-159, score-0.209]

43 If {(p(n) , q(n) )}∞ is generated by AM of C2 (p, q) and n=1 C2 (p∗ , q∗ ) inf p,q∈ m C2 (p, q) then m C2 (p(n) , q(n) ) − C2 (p∗ , q∗ ) ≤ (n) δ(i ≤ l) + di βi where βi log sup y i=1 qi (y) (n−1) qi (y) , dj = wij . [sent-172, score-0.348]

44 This immediately yields a T ≥ 1-threaded implementation where the graph is evenly T -partitioned and each thread operates over only a size m/T = (l + u)/T subset of the graph nodes. [sent-203, score-0.408]

45 We constructed a 10-NN graph using the standard TIMIT training and development sets (see section 5). [sent-204, score-0.275]

46 We ran a timing test on a 16 core symmetric multiprocessor with 128GB of RAM, each core operating at 1. [sent-207, score-0.168]

47 We varied the number T of threads from 1 (single-threaded) up to 16, in each case running 3 iterations of AM (i. [sent-209, score-0.144]

48 The speedup for T threads is typically deﬁned as the ratio of time taken for single thread to time taken for T threads. [sent-213, score-0.336]

49 , when using T threads results in a speedup of T . [sent-216, score-0.25]

50 The pointed (green) line shows the actual speedup of the above procedure, typically less than ideal due to inter-process communication and poor shared L1 and/or L2 microprocessor cache interaction. [sent-217, score-0.257]

51 When T ≤ 4, the speedup (green) is close to ideal, but for increasing T the performance diminishes away from the ideal case. [sent-218, score-0.156]

52 Our contention is that the sub-linear speedup is due to the poor cache cognizance of the algorithm. [sent-219, score-0.164]

53 The collective set of neighbors that are being used by these T threads are {∪T N (it )} and this, along with t=1 nodes ∪T {it } (and all memory for the associated measures), constitute the current working set. [sent-224, score-0.354]

54 Our goal, therefore, is for the nodes that are being simultaneously operated on to have a large amount of neighbor overlap thus minimizing the working set size. [sent-226, score-0.212]

55 With such a partition, we may also order the subsets so that the neighbors of Vi would have maximal overlap with the neighbors of Vi+1 . [sent-234, score-0.279]

56 We then schedule the T nodes in Vj to run simultaneously, and schedule the Vj sets successively. [sent-235, score-0.145]

57 Therefore, we propose a simple fast node ordering procedure (Algorithm 1) that can be run once before the parallelization begins. [sent-237, score-0.193]

58 The algorithm orders the nodes such that successive nodes are likely to have a high amount of neighbor overlap with each other and, by transitivity, with nearby nodes in the ordering. [sent-238, score-0.35]

59 It does this by, given a node v, choosing another node v from amongst v’s neighbors’ neighbors (meaning the neighbors of v’s neighbors) that has the highest neighbor overlap. [sent-239, score-0.444]

60 We need not search all V nodes for this, since anything other than v’s neighbors’ neighbors 5 Algorithm 1 Graph Ordering Algorithm Select an arbitrary node v. [sent-240, score-0.281]

61 while there are any unselected nodes remaining do Let N (v) be the set of neighbors, and N 2 (v) be the set of neighbors’ neighbors, of v. [sent-241, score-0.143]

62 number of threads for the TIMIT graph (see section 5). [sent-250, score-0.305]

63 number of threads for with and without ordering cases. [sent-254, score-0.223]

64 Given such an ordering, the tth thread operates on nodes {t, t + m/T, t + 2m/T, . [sent-256, score-0.173]

65 If the threads proceed synchronously (which we do not enforce) the set of nodes being processed at any time instant are {1 + jm/T, 2 + jm/T, . [sent-260, score-0.231]

66 With the graph represented as an adjacency list, and sets of neighbor indices sorted, our algorithm is O(mk 3 ) in time and linear in memory since the intersection between two sorted lists may be computed in O(k) time. [sent-265, score-0.217]

67 We ordered the TIMIT graph nodes, and ran timing tests as explained above. [sent-267, score-0.225]

68 To be fair, the time required for node ordering is charged against every run. [sent-268, score-0.15]

69 Moreover, the ordered case showed better performance even for a single thread T = 1 (CPU time of 539s vs. [sent-271, score-0.115]

70 the graph [5]), and (d) while the focus here was on parallelization across different processors on a symmetric multiprocessor, this would also apply for distributed processing across a network with a shared network disk. [sent-279, score-0.204]

71 5 Results In this section we present results on two popular phone classiﬁcation tasks. [sent-280, score-0.291]

72 With all SWB data added, the graph has 120 million nodes. [sent-284, score-0.223]

73 TIMIT Phone Classiﬁcation: TIMIT is a corpus of read speech that includes time-aligned phonetic transcriptions. [sent-285, score-0.177]

74 As a result, it has been popular in the speech community for evaluating supervised phone classiﬁcation algorithms [26]. [sent-286, score-0.4]

75 We constructed a symmetrized 10-NN graph (G timit ) over the TIMIT training and development sets (minimum graph degree is 10). [sent-290, score-0.706]

76 As phone classiﬁcation performance is improved with context information, each xi was constructed using a 7 frame context window. [sent-295, score-0.342]

77 , number of hidden units and regularization weight in case of MLP, µ and ν in the case of MP and SQ-Loss, were tuned on the development set. [sent-300, score-0.115]

78 Figure 2(a) shows the phone classiﬁcation results on the NIST Core test set (independent of the development set). [sent-309, score-0.366]

79 We varied the number of labeled examples by sampling a fraction f of the TIMIT training set. [sent-310, score-0.111]

80 In all cases, for MP and SQLoss, we use the same graph G timit , but the set of labeled vertices changes based on f . [sent-317, score-0.514]

81 SWB is often used for the training of large vocabulary speech recognizers. [sent-327, score-0.148]

82 In addition, less reliable phone level annotations generated in an automatic manner by a speech recognizer with a non-zero error rate are also available [29]. [sent-329, score-0.4]

83 The Switchboard Transcription Project (STP) [30] was undertaken to accurately annotate SWB at the phonetic and syllable levels. [sent-330, score-0.175]

84 As a result of the arduous and costly nature of this transcription task, only 75 minutes (out of 320 hours) of speech segments selected from different SWB conversations were annotated at the phone level and about 150 minutes annotated at the syllable level. [sent-331, score-0.633]

85 Having such annotations for all of SWB could be useful for speech processing in general, so this is an ideal real-world task for SSL. [sent-332, score-0.159]

86 7 We make use of only the phonetic labels ignoring the syllable annotations. [sent-333, score-0.161]

87 Our goal is to phonetically annotate SWB in STP style while treating STP as labeled data, and in the process show that our aforementioned parallelism efforts scale to extremely large datasets. [sent-334, score-0.208]

88 As with TIMIT, we are interested in phone classiﬁcation and we use a 7 frame context window to generate xi , stepping successive context windows by 10ms as is standard in speech recognition. [sent-337, score-0.451]

89 We randomly split the 75 minute phonetically annotated part of STP into three sets, one each for training, development and testing containing 70%, 10% and 20% of the data respectively (the size of the development set is considerably smaller than the size of the training set). [sent-338, score-0.275]

90 In each case, we trained a phone classiﬁer using the training set, tuned the hyper-parameters on the development set and evaluated the performance on the test set. [sent-342, score-0.405]

91 When s =100%, there were about 120 million nodes in the graph! [sent-347, score-0.149]

92 Due to the large size m = 120M of the dataset, it was not possible to generate the graph using the conventional brute-force search which is O(m2 ). [sent-348, score-0.161]

93 For all the experiments here we used a symmetrized 10-NN graph and = 2. [sent-358, score-0.191]

94 The labeled and unlabeled points in the graph changed based on training, development and test sets used. [sent-360, score-0.404]

95 The mean phone accuracy over the different test sets (and the standard deviations) are shown in ﬁgure 2(b) for the different values of s. [sent-368, score-0.291]

96 Equally importantly, we see that the performance on the STP data improves with the addition of increasing amounts of unlabeled data. [sent-370, score-0.136]

97 Ghahramani, “Learning from labeled and unlabeled data with label propagation,” tech. [sent-386, score-0.198]

98 Joachims, “Transductive learning via spectral graph partitioning,” in Proc. [sent-395, score-0.161]

99 Niyogi, “Semi-supervised learning of speech sounds,” in Interspeech, 2007. [sent-445, score-0.109]

100 Hon, “Speaker independant phone recognition using hidden markov models,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. [sent-492, score-0.291]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('ssl', 0.455), ('phone', 0.291), ('mp', 0.277), ('timit', 0.24), ('swb', 0.213), ('pi', 0.171), ('graph', 0.161), ('threads', 0.144), ('stp', 0.131), ('kld', 0.128), ('mlp', 0.128), ('qi', 0.123), ('neighbors', 0.123), ('speech', 0.109), ('speedup', 0.106), ('rj', 0.103), ('wij', 0.102), ('dkl', 0.097), ('unlabeled', 0.096), ('switchboard', 0.093), ('nodes', 0.087), ('thread', 0.086), ('ri', 0.081), ('ordering', 0.079), ('development', 0.075), ('labeled', 0.072), ('transductive', 0.071), ('node', 0.071), ('phonetic', 0.068), ('sim', 0.064), ('mom', 0.064), ('million', 0.062), ('tsuda', 0.061), ('cache', 0.058), ('neighbor', 0.056), ('annotate', 0.056), ('conversations', 0.056), ('unselected', 0.056), ('manifold', 0.055), ('classi', 0.053), ('vl', 0.051), ('syllable', 0.051), ('xi', 0.051), ('ideal', 0.05), ('amenable', 0.05), ('entropy', 0.049), ('core', 0.048), ('cpu', 0.048), ('transduction', 0.045), ('dl', 0.043), ('parallelization', 0.043), ('annotated', 0.043), ('argmin', 0.043), ('penalizes', 0.043), ('cognizant', 0.043), ('microprocessor', 0.043), ('phonetically', 0.043), ('sqloss', 0.043), ('subramanya', 0.043), ('labels', 0.042), ('vertices', 0.041), ('qj', 0.04), ('transcription', 0.04), ('amounts', 0.04), ('regularization', 0.04), ('training', 0.039), ('pj', 0.039), ('ir', 0.038), ('chunk', 0.037), ('deltas', 0.037), ('multiprocessor', 0.037), ('parallelism', 0.037), ('telephone', 0.037), ('wji', 0.037), ('minimizing', 0.036), ('du', 0.035), ('objectives', 0.035), ('ran', 0.035), ('argmaxy', 0.034), ('phones', 0.034), ('bilmes', 0.034), ('roux', 0.034), ('sq', 0.034), ('wii', 0.034), ('nearest', 0.033), ('overlap', 0.033), ('encourages', 0.033), ('measurable', 0.032), ('minm', 0.032), ('annotating', 0.032), ('billion', 0.032), ('label', 0.03), ('symmetrized', 0.03), ('delalleau', 0.03), ('scalability', 0.03), ('regularizer', 0.03), ('ordered', 0.029), ('collobert', 0.029), ('henceforth', 0.029), ('schedule', 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification

Author: Amarnag Subramanya, Jeff A. Bilmes

2 0.23671515 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.12343463 166 nips-2009-Noisy Generalized Binary Search

Author: Robert Nowak

Abstract: This paper addresses the problem of noisy Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued hypothesis through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search. GBS is used in many applications, including fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and active learning. In most of these cases, the responses to queries can be noisy. Past work has provided a partial characterization of GBS, but existing noise-tolerant versions of GBS are suboptimal in terms of query complexity. This paper presents an optimal algorithm for noisy GBS and demonstrates its application to learning multidimensional threshold functions. 1

4 0.12253842 253 nips-2009-Unsupervised feature learning for audio classification using convolutional deep belief networks

Author: Honglak Lee, Peter Pham, Yan Largman, Andrew Y. Ng

Abstract: In recent years, deep learning approaches have gained signiﬁcant interest as a way of building hierarchical representations from unlabeled data. However, to our knowledge, these deep learning approaches have not been extensively studied for auditory data. In this paper, we apply convolutional deep belief networks to audio data and empirically evaluate them on various audio classiﬁcation tasks. In the case of speech data, we show that the learned features correspond to phones/phonemes. In addition, our feature representations learned from unlabeled audio data show very good performance for multiple audio classiﬁcation tasks. We hope that this paper will inspire more research on deep learning approaches applied to a wide range of audio recognition tasks. 1

5 0.1030855 72 nips-2009-Distribution Matching for Transduction

Author: Novi Quadrianto, James Petterson, Alex J. Smola

Abstract: Many transductive inference algorithms assume that distributions over training and test estimates should be related, e.g. by providing a large margin of separation on both sets. We use this idea to design a transduction algorithm which can be used without modiﬁcation for classiﬁcation, regression, and structured estimation. At its heart we exploit the fact that for a good learner the distributions over the outputs on training and test sets should match. This is a classical two-sample problem which can be solved efﬁciently in its most general form by using distance measures in Hilbert Space. It turns out that a number of existing heuristics can be viewed as special cases of our approach. 1

6 0.10198131 57 nips-2009-Conditional Random Fields with High-Order Features for Sequence Labeling

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

8 0.099404454 102 nips-2009-Graph-based Consensus Maximization among Multiple Supervised and Unsupervised Models

9 0.099065691 122 nips-2009-Label Selection on Graphs

10 0.094949484 184 nips-2009-Optimizing Multi-Class Spatio-Spectral Filters via Bayes Error Estimation for EEG Classification

11 0.089513525 15 nips-2009-A Rate Distortion Approach for Semi-Supervised Conditional Random Fields

12 0.085723668 213 nips-2009-Semi-supervised Learning using Sparse Eigenfunction Bases

13 0.084625833 26 nips-2009-Adaptive Regularization for Transductive Support Vector Machine

14 0.078262113 261 nips-2009-fMRI-Based Inter-Subject Cortical Alignment Using Functional Connectivity

15 0.078135915 141 nips-2009-Local Rules for Global MAP: When Do They Work ?

16 0.073556766 186 nips-2009-Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units

17 0.073124662 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms

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

19 0.068137042 95 nips-2009-Fast subtree kernels on graphs

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

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.223), (1, 0.074), (2, -0.069), (3, 0.053), (4, -0.067), (5, -0.021), (6, -0.069), (7, 0.034), (8, -0.135), (9, 0.03), (10, -0.167), (11, 0.167), (12, -0.019), (13, -0.127), (14, -0.031), (15, -0.013), (16, 0.093), (17, -0.059), (18, -0.104), (19, -0.074), (20, 0.143), (21, -0.031), (22, -0.034), (23, 0.017), (24, 0.054), (25, -0.053), (26, 0.047), (27, -0.031), (28, -0.056), (29, 0.031), (30, 0.025), (31, 0.024), (32, 0.028), (33, -0.033), (34, -0.079), (35, 0.041), (36, -0.008), (37, 0.073), (38, 0.012), (39, 0.045), (40, 0.114), (41, -0.077), (42, 0.069), (43, 0.031), (44, -0.066), (45, -0.077), (46, -0.07), (47, -0.012), (48, -0.012), (49, 0.004)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.92797267 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification

Author: Amarnag Subramanya, Jeff A. Bilmes

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

Author: Boaz Nadler, Nathan Srebro, Xueyuan Zhou

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

4 0.61994696 122 nips-2009-Label Selection on Graphs

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

5 0.59162831 15 nips-2009-A Rate Distortion Approach for Semi-Supervised Conditional Random Fields

Author: Yang Wang, Gholamreza Haffari, Shaojun Wang, Greg Mori

Abstract: We propose a novel information theoretic approach for semi-supervised learning of conditional random ﬁelds that deﬁnes a training objective to combine the conditional likelihood on labeled data and the mutual information on unlabeled data. In contrast to previous minimum conditional entropy semi-supervised discriminative learning methods, our approach is grounded on a more solid foundation, the rate distortion theory in information theory. We analyze the tractability of the framework for structured prediction and present a convergent variational training algorithm to defy the combinatorial explosion of terms in the sum over label conﬁgurations. Our experimental results show the rate distortion approach outperforms standard l2 regularization, minimum conditional entropy regularization as well as maximum conditional entropy regularization on both multi-class classiﬁcation and sequence labeling problems. 1

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

7 0.56086373 102 nips-2009-Graph-based Consensus Maximization among Multiple Supervised and Unsupervised Models

8 0.5502156 184 nips-2009-Optimizing Multi-Class Spatio-Spectral Filters via Bayes Error Estimation for EEG Classification

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

10 0.51916438 166 nips-2009-Noisy Generalized Binary Search

11 0.4925606 57 nips-2009-Conditional Random Fields with High-Order Features for Sequence Labeling

12 0.47691226 212 nips-2009-Semi-Supervised Learning in Gigantic Image Collections

13 0.47156626 146 nips-2009-Manifold Regularization for SIR with Rate Root-n Convergence

14 0.46752205 261 nips-2009-fMRI-Based Inter-Subject Cortical Alignment Using Functional Connectivity

15 0.46111655 143 nips-2009-Localizing Bugs in Program Executions with Graphical Models

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

17 0.44081864 141 nips-2009-Local Rules for Global MAP: When Do They Work ?

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

19 0.43258479 149 nips-2009-Maximin affinity learning of image segmentation

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

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.012), (10, 0.017), (24, 0.062), (25, 0.071), (35, 0.054), (36, 0.105), (39, 0.064), (48, 0.298), (58, 0.072), (71, 0.034), (86, 0.095)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.80063266 198 nips-2009-Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions

Author: Parikshit Ram, Dongryeol Lee, Hua Ouyang, Alexander G. Gray

Abstract: The long-standing problem of efďŹ cient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 ďŹ ngerprinting to bioinformatics to movie recommendations. As the dimensionality of the dataset increases, exact NN search becomes computationally prohibitive; (1+đ?œ–) distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. This paper presents a simple, practical algorithm allowing the user to, for the ďŹ rst time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN. Experiments on high-dimensional datasets show that our algorithm often achieves faster and more accurate results than the best-known distance-approximate method, with much more stable behavior. 1

same-paper 2 0.79283166 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification

Author: Amarnag Subramanya, Jeff A. Bilmes

3 0.70171267 77 nips-2009-Efficient Match Kernel between Sets of Features for Visual Recognition

Author: Liefeng Bo, Cristian Sminchisescu

Abstract: In visual recognition, the images are frequently modeled as unordered collections of local features (bags). We show that bag-of-words representations commonly used in conjunction with linear classiﬁers can be viewed as special match kernels, which count 1 if two local features fall into the same regions partitioned by visual words and 0 otherwise. Despite its simplicity, this quantization is too coarse, motivating research into the design of match kernels that more accurately measure the similarity between local features. However, it is impractical to use such kernels for large datasets due to their signiﬁcant computational cost. To address this problem, we propose efﬁcient match kernels (EMK) that map local features to a low dimensional feature space and average the resulting vectors to form a setlevel feature. The local feature maps are learned so their inner products preserve, to the best possible, the values of the speciﬁed kernel function. Classiﬁers based on EMK are linear both in the number of images and in the number of local features. We demonstrate that EMK are extremely efﬁcient and achieve the current state of the art in three difﬁcult computer vision datasets: Scene-15, Caltech-101 and Caltech-256. 1

4 0.65351623 215 nips-2009-Sensitivity analysis in HMMs with application to likelihood maximization

Author: Pierre-arnaud Coquelin, Romain Deguest, Rémi Munos

Abstract: This paper considers a sensitivity analysis in Hidden Markov Models with continuous state and observation spaces. We propose an Inﬁnitesimal Perturbation Analysis (IPA) on the ﬁltering distribution with respect to some parameters of the model. We describe a methodology for using any algorithm that estimates the ﬁltering density, such as Sequential Monte Carlo methods, to design an algorithm that estimates its gradient. The resulting IPA estimator is proven to be asymptotically unbiased, consistent and has computational complexity linear in the number of particles. We consider an application of this analysis to the problem of identifying unknown parameters of the model given a sequence of observations. We derive an IPA estimator for the gradient of the log-likelihood, which may be used in a gradient method for the purpose of likelihood maximization. We illustrate the method with several numerical experiments.

5 0.56361341 135 nips-2009-Learning to Hash with Binary Reconstructive Embeddings

Author: Brian Kulis, Trevor Darrell

Abstract: Fast retrieval methods are increasingly critical for many large-scale analysis tasks, and there have been several recent methods that attempt to learn hash functions for fast and accurate nearest neighbor searches. In this paper, we develop an algorithm for learning hash functions based on explicitly minimizing the reconstruction error between the original distances and the Hamming distances of the corresponding binary embeddings. We develop a scalable coordinate-descent algorithm for our proposed hashing objective that is able to efﬁciently learn hash functions in a variety of settings. Unlike existing methods such as semantic hashing and spectral hashing, our method is easily kernelized and does not require restrictive assumptions about the underlying distribution of the data. We present results over several domains to demonstrate that our method outperforms existing state-of-the-art techniques. 1

6 0.54696989 104 nips-2009-Group Sparse Coding

7 0.54625922 169 nips-2009-Nonlinear Learning using Local Coordinate Coding

8 0.54413033 87 nips-2009-Exponential Family Graph Matching and Ranking

9 0.5439626 129 nips-2009-Learning a Small Mixture of Trees

10 0.54335624 122 nips-2009-Label Selection on Graphs

11 0.54300702 137 nips-2009-Learning transport operators for image manifolds

12 0.54241872 112 nips-2009-Human Rademacher Complexity

13 0.54222882 212 nips-2009-Semi-Supervised Learning in Gigantic Image Collections

14 0.54170823 158 nips-2009-Multi-Label Prediction via Sparse Infinite CCA

15 0.54053748 72 nips-2009-Distribution Matching for Transduction

16 0.54035765 260 nips-2009-Zero-shot Learning with Semantic Output Codes

17 0.54007751 26 nips-2009-Adaptive Regularization for Transductive Support Vector Machine

18 0.53995991 220 nips-2009-Slow Learners are Fast

19 0.53895223 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations

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