nips nips2004 nips2004-133 knowledge-graph by maker-knowledge-mining

133 nips-2004-Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

Source: pdf

Author: Xiaojin Zhu, Jaz Kandola, Zoubin Ghahramani, John D. Lafferty

Abstract: We present an algorithm based on convex optimization for constructing kernels for semi-supervised learning. The kernel matrices are derived from the spectral decomposition of graph Laplacians, and combine labeled and unlabeled data in a systematic fashion. Unlike previous work using diffusion kernels and Gaussian random ﬁeld kernels, a nonparametric kernel approach is presented that incorporates order constraints during optimization. This results in ﬂexible kernels and avoids the need to choose among different parametric forms. Our approach relies on a quadratically constrained quadratic program (QCQP), and is computationally feasible for large datasets. We evaluate the kernels on real datasets using support vector machines, with encouraging results. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 The kernel matrices are derived from the spectral decomposition of graph Laplacians, and combine labeled and unlabeled data in a systematic fashion. [sent-2, score-0.948]

2 Unlike previous work using diffusion kernels and Gaussian random ﬁeld kernels, a nonparametric kernel approach is presented that incorporates order constraints during optimization. [sent-3, score-1.135]

3 This results in ﬂexible kernels and avoids the need to choose among different parametric forms. [sent-4, score-0.437]

4 Our approach relies on a quadratically constrained quadratic program (QCQP), and is computationally feasible for large datasets. [sent-5, score-0.42]

5 We evaluate the kernels on real datasets using support vector machines, with encouraging results. [sent-6, score-0.397]

6 Semi-supervised methods have the potential to improve many real-world problems, since unlabeled data are often far easier to obtain than labeled data. [sent-10, score-0.216]

7 A promising family of semi-supervised learning methods can be viewed as constructing kernels by transforming the spectrum of a “local similarity” graph over labeled and unlabeled data. [sent-12, score-0.785]

8 These kernels, or regularizers, penalize functions that are not smooth over the graph [7]. [sent-13, score-0.283]

9 Informally, a smooth eigenvector has the property that two elements of the vector have similar values if there are many large weight paths between them on the graph. [sent-14, score-0.153]

10 , spectral clustering approaches [2], diffusion kernels [5], and the Gaussian random ﬁeld approach [9]. [sent-17, score-0.892]

11 However, the modiﬁcation to the spectrum, called a spectral transformation, is often a function chosen from some parameterized family. [sent-18, score-0.248]

12 As examples, for the diffusion kernel the spectral transformation is an exponential function, and for the Gaussian ﬁeld kernel the transformation is a smoothed inverse function. [sent-19, score-1.339]

13 In using a parametric approach one faces the difﬁcult problem of choosing an appropriate family of spectral transformations. [sent-20, score-0.357]

14 In this paper we propose an effective nonparametric method to ﬁnd an optimal spectral transformation using kernel alignment. [sent-22, score-0.698]

15 The main advantage of using kernel alignment is that it gives us a convex optimization problem, and does not suffer from poor convergence to local minima. [sent-23, score-0.566]

16 A key assumption of a spectral transformation is monotonicity, so that unsmooth functions over the data graph are penalized more severly. [sent-24, score-0.584]

17 The optimization problem in general is solved using semideﬁnite programming (SDP) [1]; however, in our approach the problem can be formulated in terms of quadratically constrained quadratic programming (QCQP), which can be solved more efﬁciently than a general SDP. [sent-26, score-0.48]

18 In Section 2 we review some graph theoretic concepts and relate them to the construction of kernels for semi-supervised learning. [sent-28, score-0.652]

19 In Section 3 we introduce convex optimization via QCQP and relate it to the more familiar linear and quadratic programming commonly used in machine learning. [sent-29, score-0.329]

20 Section 4 poses the problem of kernel based semi-supervised learning as a QCQP problem with order constraints. [sent-30, score-0.326]

21 The results indicate that the semi-supervised kernels constructed from the learned spectral transformations perform well in practice. [sent-32, score-0.605]

22 Our objective is to construct a kernel that is appropriate for the classiﬁcation task. [sent-40, score-0.285]

23 Since our methods use both the labeled and unlabeled data, we will refer to the resulting kernels as semi-supervised kernels. [sent-41, score-0.573]

24 For this approach to be effective such kernel matrices must also take into account the distribution of unlabeled data, in order that the unlabeled data can aid in the classiﬁcation task. [sent-47, score-0.634]

25 Once these kernel matrices have been constructed, they can be deployed in standard kernel methods, for example support vector machines. [sent-48, score-0.55]

26 In this paper we motivate the construction of semi-supervised kernel matrices from a graph theoretic perspective. [sent-49, score-0.567]

27 A graph is constructed where the nodes are the data instances {1, . [sent-50, score-0.217]

28 The intuition underlying the graph is that even if two nodes are not directly connected, they should be considered similar as long as there are many paths between them. [sent-55, score-0.246]

29 Several semi-supervised learning algorithms have been proposed under the general graph theoretic theme, based on techniques such as random walks [8], diffusion kernels [5], and Gaussian ﬁelds [9]. [sent-56, score-0.881]

30 The graph can be represented by an n × n weight matrix W = [wij ] where wij is the edge weight between nodes i and j, with wij = 0 if there is no edge. [sent-58, score-0.413]

31 This allows us to deﬁne the combinatorial graph Laplacian as L = D − W (the normalized Laplacian ˜ L = D−1/2 LD−1/2 can be used as well). [sent-62, score-0.183]

32 Perhaps the most important property of the Laplacian related to semi-supervised learning is the following: a smaller eigenvalue λ corresponds to a smoother eigenvector φ over the graph; that is, the value ij wij (φ(i) − φ(j))2 is small. [sent-65, score-0.195]

33 In a physical system the smoother eigenvectors correspond to the major vibration modes. [sent-66, score-0.165]

34 Assuming the graph structure is correct, from a regularization perspective we want to encourage smooth functions, to reﬂect our belief that labels should vary slowly over the graph. [sent-67, score-0.38]

35 A “soft labeling” function f = ci φi in a kernel machine has a penalty term in the RKHS norm given by Ω(||f ||2 ) = Ω( c2 /r(λi )). [sent-69, score-0.249]

36 2 For example, the diffusion kernel [5] corresponds to r(λ) = exp(− σ λ) and the Gaussian 2 1 ﬁeld kernel [10] corresponds to r(λ) = λ+ . [sent-72, score-0.785]

37 Cross validation has been used to ﬁnd the hyperparameters σ or for these spectral transformations. [sent-73, score-0.344]

38 Moreover, the number of degrees of freedom (or the number of hyperparameters) may not suit the task at hand, resulting in overly constrained kernels. [sent-75, score-0.216]

39 The contribution of the current paper is to address these limitations using a convex optimization approach by imposing an ordering constraint on r but otherwise not assuming any parametric form for the kernels. [sent-76, score-0.31]

40 The semin supervised kernel K is a linear combination K = i=1 µi Ki , where µi ≥ 0. [sent-78, score-0.277]

41 We formulate the problem of ﬁnding the spectral transformation as one that ﬁnds the interpolation coefﬁcients {r(λi ) = µi } by optimizing some convex objective function on K. [sent-79, score-0.583]

42 Semideﬁnite optimization can be described as the problem of optimizing a linear function of a symmetric matrix subject to linear equality constraints and the condition that the matrix be positive semi-deﬁnite. [sent-81, score-0.356]

43 The well-known linear programming problem can be generalized to a semi-deﬁnite optimization by replacing the vector of variables with a symmetric matrix, and replacing the non-negativity constraints with a positive semi-deﬁnite constraints. [sent-82, score-0.24]

44 However, an important special case of SDPs are quadratically constrained quadratic programs (QCQP) which are computationally more efﬁcient. [sent-85, score-0.408]

45 Here both the objective function and the constraints are quadratic as illustrated below, minimize subject to 1 1 x P0 x + q0 x + r0 2 1 x Pi x + qi x + ri ≤ 0 2 Ax = b (2) i = 1···m We use a slightly different notation where r is the inverse of that in [7]. [sent-86, score-0.225]

46 In a QCQP, we minimize a convex quadratic function over a feasible region that is the intersection of ellipsoids. [sent-91, score-0.247]

47 For the semi-supervised kernel learning task presented here solving an SDP would be computationally infeasible. [sent-94, score-0.282]

48 Recent work [4, 6] has proposed kernel target alignment that can be used not only to assess the relationship between the feature spaces generated by two different kernels, but also to assess the similarity between spaces induced by a kernel and that induced by the labels themselves. [sent-95, score-0.799]

49 Previous work using kernel alignment did not take into account that the Ki ’s were derived from the graph Laplacian with the goal of semi-supervised learning. [sent-101, score-0.578]

50 This can be rectiﬁed by requiring smoother eigenvectors to receive larger coefﬁcients, as shown in the next section. [sent-103, score-0.165]

51 4 Semi-Supervised Kernels with Order Constraints As stated above, we would like to maintain a decreasing order on the spectral transformation µi = r(λi ) to encourage smooth functions over the graph. [sent-104, score-0.613]

52 This motivates the set of order constraints µi ≥ µi+1 , i = 1···n − 1 (6) And we can specify the desired semi-supervised kernel as follows. [sent-105, score-0.395]

53 The formulation is an extension to [6] with order constraints, and with special components Ki ’s from the graph Laplacian. [sent-107, score-0.26]

54 Since µi ≥ 0 and Ki ’s are outer products, K will automatically be positive semi-deﬁnite and hence a valid kernel matrix. [sent-108, score-0.319]

55 The trace constraint is needed to ﬁx the scale invariance of kernel alignment. [sent-109, score-0.308]

56 It is important to notice the order constraints are convex, and as such the whole problem is convex. [sent-110, score-0.146]

57 An improvement of the above order constrained semi-supervised kernel can be obtained by studying the Laplacian eigenvectors with zero eigenvalues. [sent-113, score-0.605]

58 For a graph Laplacian there will be k zero eigenvalues if the graph has k connected subgraphs. [sent-114, score-0.452]

59 The ﬁrst m < n eigenvectors with the smallest eigenvalues work well empirically. [sent-123, score-0.193]

60 However we neglect this observation, making it easier to incorporate other kernel components if necessary. [sent-125, score-0.249]

61 It is illustrative to compare and contrast the order constrained semi-supervised kernels to other semi-supervised kernels with different spectral transformation. [sent-126, score-1.211]

62 We call the original kernel alignment solution in [6] a maximal-alignment kernel. [sent-127, score-0.395]

63 It is the solution to Deﬁnition 1 without the order constraints (11). [sent-128, score-0.146]

64 Because it does not have the additional constraints, it maximizes kernel alignment among all spectral transformation. [sent-129, score-0.643]

65 The hyperparameters σ and of the Diffusion kernel and Gaussian ﬁelds kernel (described earlier) can be learned by maximizing the alignment score also, although the optimization problem is not necessarily convex. [sent-130, score-0.768]

66 These kernels use different information from the original Laplacian eigenvalues λi . [sent-131, score-0.443]

67 The order constrained semi-supervised kernels only use the order of λi and ignore their actual values. [sent-133, score-0.683]

68 The diffusion and Gaussian ﬁeld kernels use the actual values. [sent-134, score-0.644]

69 In terms of the degree of freedom in choosing the spectral transformation µi ’s, the maximal-alignment kernels are completely free. [sent-135, score-0.802]

70 The diffusion and Gaussian ﬁeld kernels are restrictive since they have an implicit parametric form and only one free parameter. [sent-136, score-0.724]

71 The order constrained semi-supervised kernels incorporates desirable features from both approaches. [sent-137, score-0.702]

72 5 Experimental Results We evaluate the order constrained kernels on seven datasets. [sent-138, score-0.606]

73 one-two (2200/2), odd-even (4000/2) and ten digits (4000/10) are handwritten digits recognition tasks. [sent-142, score-0.271]

74 even “0, 2, 4, 6, 8” digits, such that each class has several well deﬁned internal clusters; ten digits is 10-way classiﬁcation. [sent-145, score-0.162]

75 We use 10NN unweighted graphs on all datasets except isolet which is 100NN. [sent-148, score-0.166]

76 For all datasets, we use the smallest m = 200 eigenvalue and eigenvector pairs from the graph Laplacian. [sent-149, score-0.244]

77 For a given labeled set size, we perform 30 random trials in which a labeled set is randomly sampled from the whole dataset. [sent-152, score-0.176]

78 We compare 5 semi-supervised kernels (improved order constrained kernel, order constrained kernel, Gaussian ﬁeld kernel, diffusion kernel2 and maximal-alignment kernel), and 3 standard supervised kernels (RBF (bandwidth learned using 5-fold cross validation),linear and quadratic). [sent-155, score-1.557]

79 We compute the spectral transformation for order constrained kernels and maximal-alignment kernels by solving the QCQP using standard solvers (SeDuMi/YALMIP). [sent-156, score-1.364]

80 The semi-supervised kernels tend to outperform standard supervised kernels. [sent-165, score-0.385]

81 The improved order constrained kernels are consistently among the best. [sent-166, score-0.675]

82 Figure 1 shows the spectral transformation µi of the semi-supervised kernels for different tasks. [sent-167, score-0.758]

83 The x-axis is in increasing order of λi (the original eigenvalues of the Laplacian). [sent-169, score-0.163]

84 As expected the maximal-alignment kernels’ spectral transformation is zigzagged, diffusion and Gaussian ﬁeld’s are very smooth, while order constrained kernels’ are in between. [sent-172, score-0.937]

85 The order constrained kernels (green) have large µ1 because of the order constraint. [sent-173, score-0.683]

86 This seems to be disadvantageous — the spectral transformation tries to balance it out by increasing the value of other µi ’s so that the constant K1 ’s relative inﬂuence is smaller. [sent-174, score-0.401]

87 On the other hand the improved order constrained kernels (black) allow µ1 to be small. [sent-175, score-0.675]

88 6 Conclusions We have proposed and evaluated a novel approach for semi-supervised kernel construction using convex optimization. [sent-177, score-0.387]

89 The method incorporates order constraints, and the resulting convex optimization problem can be solved efﬁciently using a QCQP. [sent-178, score-0.296]

90 In this work the base kernels were derived from the graph Laplacian, and no parametric form for the spectral transformation was imposed, making the approach more general than previous approaches. [sent-179, score-1.021]

91 2 The hyperparameters σ 2 and are learned with the fminbnd() function in Matlab to maximize kernel alignment. [sent-181, score-0.311]

92 Atheism 1 1 Improved order Order Max−align Gaussian field Diffusion 0. [sent-189, score-0.167]

93 7 µ scaled Improved order Order Max−align Gaussian field Diffusion 0. [sent-196, score-0.239]

94 1 0 5 10 15 20 25 30 35 40 45 0 50 0 5 10 15 20 rank Ten Digits (10 classes) 30 35 40 45 50 ISOLET (26 classes) 1 1 Improved order Order Max−align Gaussian field Diffusion 0. [sent-207, score-0.221]

95 8 Improved order Order Max−align Gaussian field Diffusion 0. [sent-209, score-0.167]

96 1 0 0 5 10 15 20 25 rank 30 35 40 45 50 0 0 5 10 15 20 25 30 35 40 45 50 rank Figure 1: Comparison of spectral transformation for the 5 semi-supervised kernels. [sent-225, score-0.509]

97 Spectral graph theory, Regional Conference Series in Mathematics, No. [sent-241, score-0.183]

98 Diffusion kernels on graphs and other discrete input spaces. [sent-255, score-0.357]

99 26 (709) Order semi-supervised kernels Gaussian Diffusion Field Max-align RBF standard kernels Linear Quadratic 84. [sent-365, score-0.714]

100 Each cell has two rows: The upper row is test set accuracy with standard error; the lower row is training set alignment (SeDuMi/YALMIP run time in seconds is given in parentheses). [sent-892, score-0.262]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('kernels', 0.357), ('diffusion', 0.287), ('kernel', 0.249), ('spectral', 0.248), ('qcqp', 0.247), ('ktr', 0.19), ('graph', 0.183), ('constrained', 0.172), ('laplacian', 0.167), ('transformation', 0.153), ('ki', 0.148), ('alignment', 0.146), ('unlabeled', 0.128), ('isolet', 0.126), ('vec', 0.126), ('sdps', 0.11), ('convex', 0.109), ('digits', 0.109), ('eigenvectors', 0.107), ('field', 0.09), ('quadratic', 0.089), ('labeled', 0.088), ('eigenvalues', 0.086), ('align', 0.08), ('parametric', 0.08), ('quadratically', 0.077), ('order', 0.077), ('wij', 0.076), ('gaussian', 0.073), ('eld', 0.073), ('scaled', 0.072), ('improved', 0.069), ('constraints', 0.069), ('smooth', 0.063), ('optimization', 0.062), ('hyperparameters', 0.062), ('eigenvector', 0.061), ('smoother', 0.058), ('theoretic', 0.054), ('rank', 0.054), ('ten', 0.053), ('paired', 0.052), ('cance', 0.052), ('matrices', 0.052), ('semide', 0.049), ('feasible', 0.049), ('desirable', 0.048), ('incorporates', 0.048), ('nonparametric', 0.048), ('freedom', 0.044), ('nite', 0.044), ('sdp', 0.044), ('matrix', 0.044), ('elds', 0.044), ('row', 0.043), ('zhu', 0.042), ('assess', 0.042), ('classes', 0.042), ('xl', 0.042), ('subgraphs', 0.042), ('encourage', 0.042), ('datasets', 0.04), ('similarity', 0.04), ('programming', 0.04), ('programs', 0.037), ('penalize', 0.037), ('outer', 0.037), ('optimizing', 0.037), ('smoothly', 0.036), ('objective', 0.036), ('symmetric', 0.036), ('validation', 0.034), ('lafferty', 0.034), ('nodes', 0.034), ('cristianini', 0.033), ('computationally', 0.033), ('positive', 0.033), ('vary', 0.032), ('mellon', 0.032), ('carnegie', 0.032), ('rbf', 0.031), ('subject', 0.031), ('labels', 0.031), ('imposing', 0.03), ('maintain', 0.03), ('cross', 0.03), ('accuracy', 0.03), ('trace', 0.03), ('constraint', 0.029), ('family', 0.029), ('construction', 0.029), ('relate', 0.029), ('uk', 0.029), ('paths', 0.029), ('regularization', 0.029), ('supervised', 0.028), ('elisseeff', 0.027), ('nij', 0.027), ('maxk', 0.027), ('boldface', 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 133 nips-2004-Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

Author: Xiaojin Zhu, Jaz Kandola, Zoubin Ghahramani, John D. Lafferty

2 0.2046068 168 nips-2004-Semigroup Kernels on Finite Sets

Author: Marco Cuturi, Jean-philippe Vert

Abstract: Complex objects can often be conveniently represented by ﬁnite sets of simpler components, such as images by sets of patches or texts by bags of words. We study the class of positive deﬁnite (p.d.) kernels for two such objects that can be expressed as a function of the merger of their respective sets of components. We prove a general integral representation of such kernels and present two particular examples. One of them leads to a kernel for sets of points living in a space endowed itself with a positive deﬁnite kernel. We provide experimental results on a benchmark experiment of handwritten digits image classiﬁcation which illustrate the validity of the approach. 1

3 0.20421039 115 nips-2004-Maximum Margin Clustering

Author: Linli Xu, James Neufeld, Bryce Larson, Dale Schuurmans

Abstract: We propose a new method for clustering based on ﬁnding maximum margin hyperplanes through data. By reformulating the problem in terms of the implied equivalence relation matrix, we can pose the problem as a convex integer program. Although this still yields a difﬁcult computational problem, the hard-clustering constraints can be relaxed to a soft-clustering formulation which can be feasibly solved with a semidefinite program. Since our clustering technique only depends on the data through the kernel matrix, we can easily achieve nonlinear clusterings in the same manner as spectral clustering. Experimental results show that our maximum margin clustering technique often obtains more accurate results than conventional clustering methods. The real beneﬁt of our approach, however, is that it leads naturally to a semi-supervised training method for support vector machines. By maximizing the margin simultaneously on labeled and unlabeled training data, we achieve state of the art performance by using a single, integrated learning principle. 1

4 0.1923573 42 nips-2004-Computing regularization paths for learning multiple kernels

Author: Francis R. Bach, Romain Thibaux, Michael I. Jordan

Abstract: The problem of learning a sparse conic combination of kernel functions or kernel matrices for classiﬁcation or regression can be achieved via the regularization by a block 1-norm [1]. In this paper, we present an algorithm that computes the entire regularization path for these problems. The path is obtained by using numerical continuation techniques, and involves a running time complexity that is a constant times the complexity of solving the problem for one value of the regularization parameter. Working in the setting of kernel linear regression and kernel logistic regression, we show empirically that the effect of the block 1-norm regularization differs notably from the (non-block) 1-norm regularization commonly used for variable selection, and that the regularization path is of particular value in the block case. 1

5 0.18613249 79 nips-2004-Hierarchical Eigensolver for Transition Matrices in Spectral Methods

Author: Chakra Chennubhotla, Allan D. Jepson

Abstract: We show how to build hierarchical, reduced-rank representation for large stochastic matrices and use this representation to design an efﬁcient algorithm for computing the largest eigenvalues, and the corresponding eigenvectors. In particular, the eigen problem is ﬁrst solved at the coarsest level of the representation. The approximate eigen solution is then interpolated over successive levels of the hierarchy. A small number of power iterations are employed at each stage to correct the eigen solution. The typical speedups obtained by a Matlab implementation of our fast eigensolver over a standard sparse matrix eigensolver [13] are at least a factor of ten for large image sizes. The hierarchical representation has proven to be effective in a min-cut based segmentation algorithm that we proposed recently [8]. 1 Spectral Methods Graph-theoretic spectral methods have gained popularity in a variety of application domains: segmenting images [22]; embedding in low-dimensional spaces [4, 5, 8]; and clustering parallel scientiﬁc computation tasks [19]. Spectral methods enable the study of properties global to a dataset, using only local (pairwise) similarity or afﬁnity measurements between the data points. The global properties that emerge are best understood in terms of a random walk formulation on the graph. For example, the graph can be partitioned into clusters by analyzing the perturbations to the stationary distribution of a Markovian relaxation process deﬁned in terms of the afﬁnity weights [17, 18, 24, 7]. The Markovian relaxation process need never be explicitly carried out; instead, it can be analytically expressed using the leading order eigenvectors, and eigenvalues, of the Markov transition matrix. In this paper we consider the practical application of spectral methods to large datasets. In particular, the eigen decomposition can be very expensive, on the order of O(n 3 ), where n is the number of nodes in the graph. While it is possible to compute analytically the ﬁrst eigenvector (see §3 below), the remaining subspace of vectors (necessary for say clustering) has to be explicitly computed. A typical approach to dealing with this difﬁculty is to ﬁrst sparsify the links in the graph [22] and then apply an efﬁcient eigensolver [13, 23, 3]. In comparison, we propose in this paper a specialized eigensolver suitable for large stochastic matrices with known stationary distributions. In particular, we exploit the spectral properties of the Markov transition matrix to generate hierarchical, successively lower-ranked approximations to the full transition matrix. The eigen problem is solved directly at the coarsest level of representation. The approximate eigen solution is then interpolated over successive levels of the hierarchy, using a small number of power iterations to correct the solution at each stage. 2 Previous Work One approach to speeding up the eigen decomposition is to use the fact that the columns of the afﬁnity matrix are typically correlated. The idea then is to pick a small number of representative columns to perform eigen decomposition via SVD. For example, in the Nystrom approximation procedure, originally proposed for integral eigenvalue problems, the idea is to randomly pick a small set of m columns; generate the corresponding afﬁnity matrix; solve the eigenproblem and ﬁnally extend the solution to the complete graph [9, 10]. The Nystrom method has also been recently applied in the kernel learning methods for fast Gaussian process classiﬁcation and regression [25]. Other sampling-based approaches include the work reported in [1, 2, 11]. Our starting point is the transition matrix generated from afﬁnity weights and we show how building a representational hierarchy follows naturally from considering the stochastic matrix. A closely related work is the paper by Lin on reduced rank approximations of transition matrices [14]. We differ in how we approximate the transition matrices, in particular our objective function is computationally less expensive to solve. In particular, one of our goals in reducing transition matrices is to develop a fast, specialized eigen solver for spectral clustering. Fast eigensolving is also the goal in ACE [12], where successive levels in the hierarchy can potentially have negative afﬁnities. A graph coarsening process for clustering was also pursued in [21, 3]. 3 Markov Chain Terminology We ﬁrst provide a brief overview of the Markov chain terminology here (for more details see [17, 15, 6]). We consider an undirected graph G = (V, E) with vertices vi , for i = {1, . . . , n}, and edges ei,j with non-negative weights ai,j . Here the weight ai,j represents the afﬁnity between vertices vi and vj . The afﬁnities are represented by a non-negative, symmetric n × n matrix A having weights ai,j as elements. The degree of a node j is n n deﬁned to be: dj = i=1 ai,j = j=1 aj,i , where we deﬁne D = diag(d1 , . . . , dn ). A Markov chain is deﬁned using these afﬁnities by setting a transition probability matrix M = AD −1 , where the columns of M each sum to 1. The transition probability matrix deﬁnes the random walk of a particle on the graph G. The random walk need never be explicitly carried out; instead, it can be analytically expressed using the leading order eigenvectors, and eigenvalues, of the Markov transition matrix. Because the stochastic matrices need not be symmetric in general, a direct eigen decomposition step is not preferred for reasons of instability. This problem is easily circumvented by considering a normalized afﬁnity matrix: L = D −1/2 AD−1/2 , which is related to the stochastic matrix by a similarity transformation: L = D −1/2 M D1/2 . Because L is symmetric, it can be diagonalized: L = U ΛU T , where U = [u1 , u2 , · · · , un ] is an orthogonal set of eigenvectors and Λ is a diagonal matrix of eigenvalues [λ1 , λ2 , · · · , λn ] sorted in decreasing order. The eigenvectors have unit length uk = 1 and from the form of A and D it can be shown that the eigenvalues λi ∈ (−1, 1], with at least one eigenvalue equal to one. Without loss of generality, we take λ1 = 1. Because L and M are similar we can perform an eigen decomposition of the Markov transition matrix as: M = D1/2 LD−1/2 = D1/2 U Λ U T D−1/2 . Thus an eigenvector u of L corresponds to an eigenvector D 1/2 u of M with the same eigenvalue λ. The Markovian relaxation process after β iterations, namely M β , can be represented as: M β = D1/2 U Λβ U T D−1/2 . Therefore, a particle undertaking a random walk with an initial distribution p 0 acquires after β steps a distribution p β given by: p β = M β p 0 . Assuming the graph is connected, as β → ∞, the Markov chain approaches a unique n stationary distribution given by π = diag(D)/ i=1 di , and thus, M ∞ = π1T , where 1 is a n-dim column vector of all ones. Observe that π is an eigenvector of M as it is easy to show that M π = π and the corresponding eigenvalue is 1. Next, we show how to generate hierarchical, successively low-ranked approximations for the transition matrix M . 4 Building a Hierarchy of Transition Matrices The goal is to generate a very fast approximation, while simultaneously achieving sufﬁcient accuracy. For notational ease, we think of M as a ﬁne-scale representation and M as some coarse-scale approximation to be derived here. By coarsening M further, we can generate successive levels of the representation hierarchy. We use the stationary distribution π to construct a corresponding coarse-scale stationary distribution δ. As we just discussed a critical property of the ﬁne scale Markov matrix M is that it is similar to the symmetric matrix L and we wish to preserve this property at every level of the representation hierarchy. 4.1 Deriving Coarse-Scale Stationary Distribution We begin by expressing the stationary distribution π as a probabilistic mixture of latent distributions. In matrix notation, we have (1) π = K δ, where δ is an unknown mixture coefﬁcient vector of length m, K is an n × m non-negative n kernel matrix whose columns are latent distributions that each sum to 1: i=1 Ki,j = 1 and m n. It is easy to derive a maximum likelihood approximation of δ using an EM type algorithm [16]. The main step is to ﬁnd a stationary point δ, λ for the Lagrangian: m n i=1 m Ki,j δj + λ πi ln E≡− j=1 δj − 1 . (2) j=1 An implicit step in this EM procedure is to compute the the ownership probability r i,j of the j th kernel (or node) at the coarse scale for the ith node on the ﬁne scale and is given by ri,j = δj Ki,j . m k=1 δk Ki,k (3) The EM procedure allows for an update of both δ and the latent distributions in the kernel matrix K (see §8.3.1 in [6]). For initialization, δ is taken to be uniform over the coarse-scale states. But in choosing kernels K, we provide a good initialization for the EM procedure. Speciﬁcally, the Markov matrix M is diffused using a small number of iterations to get M β . The diffusion causes random walks from neighboring nodes to be less distinguishable. This in turn helps us select a small number of columns of M β in a fast and greedy way to be the kernel matrix K. We defer the exact details on kernel selection to a later section (§4.3). 4.2 Deriving the Coarse-Scale Transition Matrix In order to deﬁne M , the coarse-scale transition matrix, we break it down into three steps. First, the Markov chain propagation at the coarse scale can be deﬁned as: q k+1 = M q k , (4) where q is the coarse scale probability distribution after k steps of the random walk. Second, we expand q k into the ﬁne scale using the kernels K resulting in a ﬁne scale probability distribution p k : p k = Kq k . (5) k Finally, we lift p k back into the coarse scale by using the ownership probability of the j th kernel for the ith node on the ﬁne grid: n qjk+1 = ri,j pik i=1 (6) Substituting for Eqs.(3) and (5) in Eq. 6 gives n m qjk+1 = i=1 n Ki,t qtk = ri,j t=1 i=1 δj Ki,j m k=1 δk Ki,k m Ki,t qtk . (7) t=1 We can write the preceding equation in a matrix form: q k+1 = diag( δ ) K T diag K δ −1 Kq k . (8) Comparing this with Eq. 4, we can derive the transition matrix M as: M = diag( δ ) K T diag K δ −1 (9) K. It is easy to see that δ = M δ, so δ is the stationary distribution for M . Following the deﬁnition of M , and its stationary distribution δ, we can generate a symmetric coarse scale afﬁnity matrix A given by A = M diag(δ) = diag( δ ) K T diag K δ −1 Kdiag(δ) , (10) where we substitute for the expression M from Eq. 9. The coarse-scale afﬁnity matrix A is then normalized to get: L = D−1/2 AD−1/2 ; D = diag(d1 , d2 , · · · , dm ), (11) where dj is the degree of node j in the coarse-scale graph represented by the matrix A (see §3 for degree deﬁnition). Thus, the coarse scale Markov matrix M is precisely similar to a symmetric matrix L. 4.3 Selecting Kernels For demonstration purpose, we present the kernel selection details on the image of an eye shown below. To begin with, a random walk is deﬁned where each pixel in the test image is associated with a vertex of the graph G. The edges in G are deﬁned by the standard 8-neighbourhood of each pixel. For the demonstrations in this paper, the edge weight ai,j between neighbouring pixels xi and xj is given by a function of the difference in the 2 corresponding intensities I(xi ) and I(xj ): ai,j = exp(−(I(xi ) − I(xj ))2 /2σa ), where σa is set according to the median absolute difference |I(xi ) − I(xj )| between neighbours measured over the entire image. The afﬁnity matrix A with the edge weights is then used to generate a Markov transition matrix M . The kernel selection process we use is fast and greedy. First, the ﬁne scale Markov matrix M is diffused to M β using β = 4. The Markov matrix M is sparse as we make the afﬁnity matrix A sparse. Every column in the diffused matrix M β is a potential kernel. To facilitate the selection process, the second step is to rank order the columns of M β based on a probability value in the stationary distribution π. Third, the kernels (i.e. columns of M β ) are picked in such a way that for a kernel Ki all of the neighbours of pixel i which are within the half-height of the the maximum value in the kernel Ki are suppressed from the selection process. Finally, the kernel selection is continued until every pixel in the image is within a half-height of the peak value of at least one kernel. If M is a full matrix, to avoid the expense of computing M β explicitly, random kernel centers can be selected, and only the corresponding columns of M β need be computed. We show results from a three-scale hierarchy on the eye image (below). The image has 25 × 20 pixels but is shown here enlarged for clarity. At the ﬁrst coarse scale 83 kernels are picked. The kernels each correspond to a different column in the ﬁne scale transition matrix and the pixels giving rise to these kernels are shown numbered on the image. Using these kernels as an initialization, the EM procedure derives a coarse-scale stationary distribution δ 21 14 26 4 (Eq. 2), while simultaneously updating the kernel ma12 27 2 19 trix. Using the newly updated kernel matrix K and the 5 8 13 23 30 18 6 9 derived stationary distribution δ a transition matrix M 28 20 15 32 10 22 is generated (Eq. 9). The coarse scale Markov matrix 24 17 7 is then diffused to M β , again using β = 4. The kernel Coarse Scale 1 Coarse Scale 2 selection algorithm is reapplied, this time picking 32 kernels for the second coarse scale. Larger values of β cause the coarser level to have fewer elements. But the exact number of elements depends on the form of the kernels themselves. For the random experiments that we describe later in §6 we found β = 2 in the ﬁrst iteration and 4 thereafter causes the number of kernels to be reduced by a factor of roughly 1/3 to 1/4 at each level. 72 28 35 44 51 64 82 4 12 31 56 19 77 36 45 52 65 13 57 23 37 5 40 53 63 73 14 29 6 66 38 74 47 24 7 30 41 54 71 78 58 15 8 20 39 48 59 67 25 68 79 21 16 2 11 26 42 49 55 60 75 32 83 43 9 76 50 17 27 61 33 69 80 3 46 18 70 81 34 10 62 22 1 25 11 1 3 16 31 29 At coarser levels of the hierarchy, we expect the kernels to get less sparse and so will the afﬁnity and the transition matrices. In order to promote sparsity at successive levels of the hierarchy we sparsify A by zeroing out elements associated with “small” transition probabilities in M . However, in the experiments described later in §6, we observe this sparsiﬁcation step to be not critical. To summarize, we use the stationary distribution π at the ﬁne-scale to derive a transition matrix M , and its stationary distribution δ, at the coarse-scale. The coarse scale transition in turn helps to derive an afﬁnity matrix A and its normalized version L. It is obvious that this procedure can be repeated recursively. We describe next how to use this representation hierarchy for building a fast eigensolver. 5 Fast EigenSolver Our goal in generating a hierarchical representation of a transition matrix is to develop a fast, specialized eigen solver for spectral clustering. To this end, we perform a full eigen decomposition of the normalized afﬁnity matrix only at the coarsest level. As discussed in the previous section, the afﬁnity matrix at the coarsest level is not likely to be sparse, hence it will need a full (as opposed to a sparse) version of an eigen solver. However it is typically the case that e ≤ m n (even in the case of the three-scale hierarchy that we just considered) and hence we expect this step to be the least expensive computationally. The resulting eigenvectors are interpolated to the next lower level of the hierarchy by a process which will be described next. Because the eigen interpolation process between every adjacent pair of scales in the hierarchy is similar, we will assume we have access to the leading eigenvectors U (size: m × e) for the normalized afﬁnity matrix L (size: m × m) and describe how to generate the leading eigenvectors U (size: n × e), and the leading eigenvalues S (size: e × 1), for the ﬁne-scale normalized afﬁnity matrix L (size: n × n). There are several steps to the eigen interpolation process and in the discussion that follows we refer to the lines in the pseudo-code presented below. First, the coarse-scale eigenvectors U can be interpolated using the kernel matrix K to generate U = K U , an approximation for the ﬁne-scale eigenvectors (line 9). Second, interpolation alone is unlikely to set the directions of U exactly aligned with U L , the vectors one would obtain by a direct eigen decomposition of the ﬁne-scale normalized afﬁnity matrix L. We therefore update the directions in U by applying a small number of power iterations with L, as given in lines 13-15. e e function (U, S) = CoarseToFine(L, K, U , S) 1: INPUT 2: L, K ⇐ {L is n × n and K is n × m where m n} e e e e 3: U /S ⇐ {leading coarse-scale eigenvectors/eigenvalues of L. U is of size m × e, e ≤ m} 4: OUTPUT 5: U, S ⇐ {leading ﬁne-scale eigenvectors/eigenvalues of L. U is n × e and S is e × 1.} x 10 0.4 3 0.96 0.94 0.92 0.9 0.35 2.5 Relative Error Absolute Relative Error 0.98 Eigen Value |δλ|λ−1 −3 Eigen Spectrum 1 2 1.5 1 5 10 15 20 Eigen Index (a) 25 30 0.2 0.15 0.1 0.5 0.88 0.3 0.25 0.05 5 10 15 20 Eigen Index (b) 25 30 5 10 15 20 Eigen Index 25 30 (c) Figure 1: Hierarchical eigensolver results. (a) comparing ground truth eigenvalues S L (red circles) with multi-scale eigensolver spectrum S (blue line) (b) Relative absolute error between eigenvalues: |S−SL | (c) Eigenvector mismatch: 1 − diag |U T UL | , between SL eigenvectors U derived by the multi-scale eigensolver and the ground truth U L . Observe the slight mismatch in the last few eigenvectors, but excellent agreement in the leading eigenvectors (see text). 6: CONSTANTS: TOL = 1e-4; POWER ITERS = 50 7: “ ” e 8: TPI = min POWER ITERS, log(e × eps/TOL)/ log(min(S)) {eps: machine accuracy} e 9: U = K U {interpolation from coarse to ﬁne} 10: while not converged do 11: Uold = U {n × e matrix, e n} 12: for i = 1 to TPI do 13: U ⇐ LU 14: end for 15: U ⇐ Gram-Schmidt(U ) {orthogonalize U } 16: Le = U T LU {L may be sparse, but Le need not be.} 17: Ue Se UeT = svd(Le ) {eigenanalysis of Le , which is of size e × e.} 18: U ⇐ U Ue {update the leading eigenvectors of L} 19: S = diag(Se ) {grab the leading eigenvalues of L} T 20: innerProd = 1 − diag( Uold U ) {1 is a e × 1 vector of all ones} 21: converged = max[abs(innerProd)] < TOL 22: end while The number of power iterations TPI can be bounded as discussed next. Suppose v = U c where U is a matrix of true eigenvectors and c is a coefﬁcient vector for an arbitrary vector v. After TPI power iterations v becomes v = U diag(S TPI )c, where S has the exact eigenvalues. In order for the component of a vector v in the direction Ue (the eth column of U ) not to be swamped by other components, we can limit it’s decay after TPI iterations as TPI follows: (S(e)/S(1)) >= e×eps/TOL, where S(e) is the exact eth eigenvalue, S(1) = 1, eps is the machine precision, TOL is requested accuracy. Because we do not have access to the exact value S(e) at the beginning of the interpolation procedure, we estimate it from the coarse eigenvalues S. This leads to a bound on the power iterations TPI, as derived on the line 9 above. Third, the interpolation process and the power iterations need not preserve orthogonality in the eigenvectors in U . We ﬁx this by Gram-Schmidt orthogonalization procedure (line 16). Finally, there is a still a problem with power iterations that needs to be resolved, in that it is very hard to separate nearby eigenvalues. In particular, for the convergence of the power iterations the ratio that matters is between the (e + 1) st and eth eigenvalues. So the idea we pursue is to use the power iterations only to separate the reduced space of eigenvectors (of dimension e) from the orthogonal subspace (of dimension n − e). We then use a full SVD on the reduced space to update the leading eigenvectors U , and eigenvalues S, for the ﬁne-scale (lines 17-20). This idea is similar to computing the Ritz values and Ritz vectors in a Rayleigh-Ritz method. 6 Interpolation Results Our multi-scale decomposition code is in Matlab. For the direct eigen decomposition, we have used the Matlab program svds.m which invokes the compiled ARPACKC routine [13], with a default convergence tolerance of 1e-10. In Fig. 1a we compare the spectrum S obtained from a three-scale decomposition on the eye image (blue line) with the ground truth, which is the spectrum SL resulting from direct eigen decomposition of the ﬁne-scale normalized afﬁnity matrices L (red circles). There is an excellent agreement in the leading eigenvalues. To illustrate this, we show absolute relative error between the spectra: |S−SL | in Fig. 1b. The spectra agree mostly, except for SL the last few eigenvalues. For a quantitative comparison between the eigenvectors, we plot in Fig. 1c the following measure: 1 − diag(|U T UL |), where U is the matrix of eigenvectors obtained by the multi-scale approximation, UL is the ground-truth resulting from a direct eigen decomposition of the ﬁne-scale afﬁnity matrix L and 1 is a vector of all ones. The relative error plot demonstrates a close match, within the tolerance threshold of 1e-4 that we chose for the multi-scale method, in the leading eigenvector directions between the two methods. The relative error is high with the last few eigen vectors, which suggests that the power iterations have not clearly separated them from other directions. So, the strategy we suggest is to pad the required number of leading eigen basis by about 20% before invoking the multi-scale procedure. Obviously, the number of hierarchical stages for the multi-scale procedure must be chosen such that the transition matrix at the coarsest scale can accommodate the slight increase in the subspace dimensions. For lack of space we are omitting extra results (see Ch.8 in [6]). Next we measure the time the hierarchical eigensolver takes to compute the leading eigenbasis for various input sizes, in comparison with the svds.m procedure [13]. We form images of different input sizes by Gaussian smoothing of i.i.d noise. The Gaussian function has a standard deviation of 3 pixels. The edges in graph G are deﬁned by the standard 8-neighbourhood of each pixel. The edge weights between neighbouring pixels are simply given by a function of the difference in the corresponding intensities (see §4.3). The afﬁnity matrix A with the edge weights is then used to generate a Markov transition matrix M . The fast eigensolver is run on ten different instances of the input image of a given size and the average of these times is reported here. For a fair comparison between the two procedures, we set the convergence tolerance value for the svds.m procedure to be 1e-4, the same as the one used for the fast eigensolver. We found the hierarchical representation derived from this tolerance threshold to be sufﬁciently accurate for a novel min-cut based segmentation results that we reported in [8]. Also, the subspace dimensionality is ﬁxed to be 51 where we expect (and indeed observe) the leading 40 eigenpairs derived from the multi-scale procedure to be accurate. Hence, while invoking svds.m we compute only the leading 41 eigenpairs. In the table shown below, the ﬁrst column corresponds to the number of nodes in the graph, while the second and third columns report the time taken in seconds by the svds.m procedure and the Matlab implementation of the multi-scale eigensolver respectively. The fourth column reports the speedups of the multi-scale eigensolver over svds.m procedure on a standard desktop (Intel P4, 2.5GHz, 1GB RAM). Lowering the tolerance threshold for svds.m made it faster by about 20 − 30%. Despite this, the multi-scale algorithm clearly outperforms the svds.m procedure. The most expensive step in the multi-scale algorithm is the power iteration required in the last stage, that is interpolating eigenvectors from the ﬁrst coarse scale to the required ﬁne scale. The complexity is of the order of n × e where e is the subspace dimensionality and n is the size of the graph. Indeed, from the table we can see that the multi-scale procedure is taking time roughly proportional to n. Deviations from the linear trend are observed at speciﬁc values of n, which we believe are due to the n 322 632 642 652 1002 1272 1282 1292 1602 2552 2562 2572 5112 5122 5132 6002 7002 8002 svds.m 1.6 10.8 20.5 12.6 44.2 91.1 230.9 96.9 179.3 819.2 2170.8 871.7 7977.2 20269 7887.2 10841.4 15048.8 Multi-Scale 1.5 4.9 5.5 5.1 13.1 20.4 35.2 20.9 34.4 90.3 188.7 93.3 458.8 739.3 461.9 644.2 1162.4 1936.6 Speedup 1.1 2.2 3.7 2.5 3.4 4.5 6.6 4.6 5.2 9.1 11.5 9.3 17.4 27.4 17.1 16.8 12.9 variations in the difﬁculty of the speciﬁc eigenvalue problem (eg. nearly multiple eigenvalues). The hierarchical representation has proven to be effective in a min-cut based segmentation algorithm that we proposed recently [8]. Here we explored the use of random walks and associated spectral embedding techniques for the automatic generation of suitable proposal (source and sink) regions for a min-cut based algorithm. The multiscale algorithm was used to generate the 40 leading eigenvectors of large transition matrices (eg. size 20K × 20K). In terms of future work, it will be useful to compare our work with other approximate methods for SVD such as [23]. Ack: We thank S. Roweis, F. Estrada and M. Sakr for valuable comments. References [1] D. Achlioptas and F. McSherry. Fast Computation of Low-Rank Approximations. STOC, 2001. [2] D. Achlioptas et al Sampling Techniques for Kernel Methods. NIPS, 2001. [3] S. Barnard and H. Simon Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems. PPSC, 627-632. [4] M. Belkin et al Laplacian Eigenmaps and Spectral Techniques for Embedding. NIPS, 2001. [5] M. Brand et al A unifying theorem for spectral embedding and clustering. AI & STATS, 2002. [6] C. Chennubhotla. Spectral Methods for Multi-scale Feature Extraction and Spectral Clustering. http://www.cs.toronto.edu/˜chakra/thesis.pdf Ph.D Thesis, Department of Computer Science, University of Toronto, Canada, 2004. [7] C. Chennubhotla and A. Jepson. Half-Lives of EigenFlows for Spectral Clustering. NIPS, 2002. [8] F. Estrada, A. Jepson and C. Chennubhotla. Spectral Embedding and Min-Cut for Image Segmentation. Manuscript Under Review, 2004. [9] C. Fowlkes et al Efﬁcient spatiotemporal grouping using the Nystrom method. CVPR, 2001. [10] S. Belongie et al Spectral Partitioning with Indeﬁnite Kernels using Nystrom app. ECCV, 2002. [11] A. Frieze et al Fast Monte-Carlo Algorithms for ﬁnding low-rank approximations. FOCS, 1998. [12] Y. Koren et al ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs IEEE Symp. on InfoVis 2002, pp. 137-144 [13] R. B. Lehoucq, D. C. Sorensen and C. Yang. ARPACK User Guide: Solution of Large Scale Eigenvalue Problems by Implicitly Restarted Arnoldi Methods. SIAM 1998. [14] J. J. Lin. Reduced Rank Approximations of Transition Matrices. AI & STATS, 2002. [15] L. Lova’sz. Random Walks on Graphs: A Survey Combinatorics, 1996, 353–398. [16] G. J. McLachlan et al Mixture Models: Inference and Applications to Clustering. 1988 [17] M. Meila and J. Shi. A random walks view of spectral segmentation. AI & STATS, 2001. [18] A. Ng, M. Jordan and Y. Weiss. On Spectral Clustering: analysis and an algorithm NIPS, 2001. [19] A. Pothen Graph partitioning algorithms with applications to scientiﬁc computing. Parallel Numerical Algorithms, D. E. Keyes et al (eds.), Kluwer Academic Press, 1996. [20] G. L. Scott et al Feature grouping by relocalization of eigenvectors of the proximity matrix. BMVC, pg. 103-108, 1990. [21] E. Sharon et al Fast Multiscale Image Segmentation CVPR, I:70-77, 2000. [22] J. Shi and J. Malik. Normalized cuts and image segmentation. PAMI, August, 2000. [23] H. Simon et al Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications SIAM J. of Sci. Comp. 21(6):2257-2274, 2000. [24] N. Tishby et al Data clustering by Markovian Relaxation NIPS, 2001. [25] C. Williams et al Using the Nystrom method to speed up the kernel machines. NIPS, 2001.

6 0.18285131 30 nips-2004-Binet-Cauchy Kernels

7 0.16887563 103 nips-2004-Limits of Spectral Clustering

8 0.15523334 188 nips-2004-The Laplacian PDF Distance: A Cost Function for Clustering in a Kernel Feature Space

9 0.14431772 161 nips-2004-Self-Tuning Spectral Clustering

10 0.1262055 177 nips-2004-Supervised Graph Inference

11 0.1257523 187 nips-2004-The Entire Regularization Path for the Support Vector Machine

12 0.12422726 164 nips-2004-Semi-supervised Learning by Entropy Minimization

13 0.11907038 142 nips-2004-Outlier Detection with One-class Kernel Fisher Discriminants

14 0.11842457 98 nips-2004-Learning Gaussian Process Kernels via Hierarchical Bayes

15 0.11279693 19 nips-2004-An Application of Boosting to Graph Classification

16 0.11046536 165 nips-2004-Semi-supervised Learning on Directed Graphs

17 0.10882187 148 nips-2004-Probabilistic Computation in Spiking Populations

18 0.10681912 59 nips-2004-Efficient Kernel Discriminant Analysis via QR Decomposition

19 0.10667001 18 nips-2004-Algebraic Set Kernels with Application to Inference Over Local Image Representations

20 0.10648818 92 nips-2004-Kernel Methods for Implicit Surface Modeling

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.325), (1, 0.154), (2, -0.135), (3, 0.112), (4, -0.184), (5, -0.132), (6, -0.215), (7, -0.13), (8, -0.074), (9, -0.101), (10, -0.147), (11, -0.021), (12, -0.023), (13, 0.025), (14, 0.073), (15, 0.11), (16, 0.09), (17, -0.093), (18, 0.102), (19, -0.025), (20, 0.071), (21, 0.032), (22, 0.028), (23, 0.01), (24, -0.125), (25, 0.028), (26, 0.009), (27, 0.035), (28, -0.04), (29, 0.037), (30, 0.038), (31, 0.017), (32, 0.029), (33, -0.055), (34, 0.027), (35, -0.009), (36, 0.088), (37, 0.035), (38, 0.011), (39, -0.019), (40, 0.045), (41, 0.006), (42, 0.012), (43, 0.052), (44, -0.095), (45, -0.082), (46, -0.025), (47, -0.044), (48, 0.055), (49, -0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97983861 133 nips-2004-Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

Author: Xiaojin Zhu, Jaz Kandola, Zoubin Ghahramani, John D. Lafferty

2 0.83264697 30 nips-2004-Binet-Cauchy Kernels

Author: Alex J. Smola, S.v.n. Vishwanathan

Abstract: We propose a family of kernels based on the Binet-Cauchy theorem and its extension to Fredholm operators. This includes as special cases all currently known kernels derived from the behavioral framework, diffusion processes, marginalized kernels, kernels on graphs, and the kernels on sets arising from the subspace angle approach. Many of these kernels can be seen as the extrema of a new continuum of kernel functions, which leads to numerous new special cases. As an application, we apply the new class of kernels to the problem of clustering of video sequences with encouraging results. 1

3 0.7656194 168 nips-2004-Semigroup Kernels on Finite Sets

Author: Marco Cuturi, Jean-philippe Vert

4 0.75126064 79 nips-2004-Hierarchical Eigensolver for Transition Matrices in Spectral Methods

Author: Chakra Chennubhotla, Allan D. Jepson

5 0.74304062 94 nips-2004-Kernels for Multi--task Learning

Author: Charles A. Micchelli, Massimiliano Pontil

Abstract: This paper provides a foundation for multi–task learning using reproducing kernel Hilbert spaces of vector–valued functions. In this setting, the kernel is a matrix–valued function. Some explicit examples will be described which go beyond our earlier results in [7]. In particular, we characterize classes of matrix– valued kernels which are linear and are of the dot product or the translation invariant type. We discuss how these kernels can be used to model relations between the tasks and present linear multi–task learning algorithms. Finally, we present a novel proof of the representer theorem for a minimizer of a regularization functional which is based on the notion of minimal norm interpolation. 1

6 0.63326901 177 nips-2004-Supervised Graph Inference

7 0.62526667 18 nips-2004-Algebraic Set Kernels with Application to Inference Over Local Image Representations

8 0.59826779 165 nips-2004-Semi-supervised Learning on Directed Graphs

9 0.5962404 115 nips-2004-Maximum Margin Clustering

10 0.59120083 103 nips-2004-Limits of Spectral Clustering

11 0.56892163 42 nips-2004-Computing regularization paths for learning multiple kernels

12 0.55925101 201 nips-2004-Using the Equivalent Kernel to Understand Gaussian Process Regression

13 0.54383761 188 nips-2004-The Laplacian PDF Distance: A Cost Function for Clustering in a Kernel Feature Space

14 0.53350079 60 nips-2004-Efficient Kernel Machines Using the Improved Fast Gauss Transform

15 0.52914697 161 nips-2004-Self-Tuning Spectral Clustering

16 0.50889671 142 nips-2004-Outlier Detection with One-class Kernel Fisher Discriminants

17 0.50837237 61 nips-2004-Efficient Out-of-Sample Extension of Dominant-Set Clusters

18 0.48692352 59 nips-2004-Efficient Kernel Discriminant Analysis via QR Decomposition

19 0.48147774 93 nips-2004-Kernel Projection Machine: a New Tool for Pattern Recognition

20 0.47880584 150 nips-2004-Proximity Graphs for Clustering and Manifold Learning

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.085), (15, 0.198), (25, 0.174), (26, 0.06), (31, 0.038), (33, 0.227), (35, 0.018), (39, 0.058), (50, 0.054)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.97177535 123 nips-2004-Multi-agent Cooperation in Diverse Population Games

Author: K. Wong, S. W. Lim, Z. Gao

Abstract: We consider multi-agent systems whose agents compete for resources by striving to be in the minority group. The agents adapt to the environment by reinforcement learning of the preferences of the policies they hold. Diversity of preferences of policies is introduced by adding random biases to the initial cumulative payoffs of their policies. We explain and provide evidence that agent cooperation becomes increasingly important when diversity increases. Analyses of these mechanisms yield excellent agreement with simulations over nine decades of data. 1

2 0.96176785 109 nips-2004-Mass Meta-analysis in Talairach Space

Author: Finn \. Nielsen

Abstract: We provide a method for mass meta-analysis in a neuroinformatics database containing stereotaxic Talairach coordinates from neuroimaging experiments. Database labels are used to group the individual experiments, e.g., according to cognitive function, and the consistent pattern of the experiments within the groups are determined. The method voxelizes each group of experiments via a kernel density estimation, forming probability density volumes. The values in the probability density volumes are compared to null-hypothesis distributions generated by resamplings from the entire unlabeled set of experiments, and the distances to the nullhypotheses are used to sort the voxels across groups of experiments. This allows for mass meta-analysis, with the construction of a list with the most prominent associations between brain areas and group labels. Furthermore, the method can be used for functional labeling of voxels. 1

3 0.95528811 52 nips-2004-Discrete profile alignment via constrained information bottleneck

Author: Sean O'rourke, Gal Chechik, Robin Friedman, Eleazar Eskin

Abstract: Amino acid proﬁles, which capture position-speciﬁc mutation probabilities, are a richer encoding of biological sequences than the individual sequences themselves. However, proﬁle comparisons are much more computationally expensive than discrete symbol comparisons, making proﬁles impractical for many large datasets. Furthermore, because they are such a rich representation, proﬁles can be diﬃcult to visualize. To overcome these problems, we propose a discretization for proﬁles using an expanded alphabet representing not just individual amino acids, but common proﬁles. By using an extension of information bottleneck (IB) incorporating constraints and priors on the class distributions, we ﬁnd an informationally optimal alphabet. This discretization yields a concise, informative textual representation for proﬁle sequences. Also alignments between these sequences, while nearly as accurate as the full proﬁleproﬁle alignments, can be computed almost as quickly as those between individual or consensus sequences. A full pairwise alignment of SwissProt would take years using proﬁles, but less than 3 days using a discrete IB encoding, illustrating how discrete encoding can expand the range of sequence problems to which proﬁle information can be applied. 1

4 0.93745607 10 nips-2004-A Probabilistic Model for Online Document Clustering with Application to Novelty Detection

Author: Jian Zhang, Zoubin Ghahramani, Yiming Yang

Abstract: In this paper we propose a probabilistic model for online document clustering. We use non-parametric Dirichlet process prior to model the growing number of clusters, and use a prior of general English language model as the base distribution to handle the generation of novel clusters. Furthermore, cluster uncertainty is modeled with a Bayesian Dirichletmultinomial distribution. We use empirical Bayes method to estimate hyperparameters based on a historical dataset. Our probabilistic model is applied to the novelty detection task in Topic Detection and Tracking (TDT) and compared with existing approaches in the literature. 1

same-paper 5 0.92205018 133 nips-2004-Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

Author: Xiaojin Zhu, Jaz Kandola, Zoubin Ghahramani, John D. Lafferty

6 0.9179548 206 nips-2004-Worst-Case Analysis of Selective Sampling for Linear-Threshold Algorithms

7 0.86948872 178 nips-2004-Support Vector Classification with Input Data Uncertainty

8 0.86464274 110 nips-2004-Matrix Exponential Gradient Updates for On-line Learning and Bregman Projection

9 0.86296338 189 nips-2004-The Power of Selective Memory: Self-Bounded Learning of Prediction Suffix Trees

10 0.86125773 31 nips-2004-Blind One-microphone Speech Separation: A Spectral Learning Approach

11 0.86122638 187 nips-2004-The Entire Regularization Path for the Support Vector Machine

12 0.86114401 16 nips-2004-Adaptive Discriminative Generative Model and Its Applications

13 0.85966611 167 nips-2004-Semi-supervised Learning with Penalized Probabilistic Clustering

14 0.85780364 131 nips-2004-Non-Local Manifold Tangent Learning

15 0.85775125 161 nips-2004-Self-Tuning Spectral Clustering

16 0.85736692 174 nips-2004-Spike Sorting: Bayesian Clustering of Non-Stationary Data

17 0.85718513 68 nips-2004-Face Detection --- Efficient and Rank Deficient

18 0.85711855 124 nips-2004-Multiple Alignment of Continuous Time Series

19 0.85628641 2 nips-2004-A Direct Formulation for Sparse PCA Using Semidefinite Programming

20 0.85603684 9 nips-2004-A Method for Inferring Label Sampling Mechanisms in Semi-Supervised Learning