nips nips2002 nips2002-52 knowledge-graph by maker-knowledge-mining

52 nips-2002-Cluster Kernels for Semi-Supervised Learning

Source: pdf

Author: Olivier Chapelle, Jason Weston, Bernhard SchĂślkopf

Abstract: We propose a framework to incorporate unlabeled data in kernel classifier, based on the idea that two points in the same cluster are more likely to have the same label. This is achieved by modifying the eigenspectrum of the kernel matrix. Experimental results assess the validity of this approach. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 de Abstract We propose a framework to incorporate unlabeled data in kernel classifier, based on the idea that two points in the same cluster are more likely to have the same label. [sent-4, score-1.211]

2 This is achieved by modifying the eigenspectrum of the kernel matrix. [sent-5, score-0.378]

3 1 Introduction We consider the problem of semi-supervised learning, where one has usually few labeled examples and a lot of unlabeled examples. [sent-7, score-0.602]

4 One of the first semi-supervised algorithms [1] was applied to web page classification. [sent-8, score-0.082]

5 This is a typical example where the number of unlabeled examples can be made as large as possible since there are billions of web page, but labeling is expensive since it requires human intervention. [sent-9, score-0.4]

6 Since then, there has been a lot of interest for this paradigm in the machine learning community; an extensive review of existing techniques can be found in [10]. [sent-10, score-0.098]

7 It has been shown experimentally that under certain conditions, the decision function can be estimated more accurately, yielding lower generalization error [1, 4, 6] . [sent-11, score-0.135]

8 However, in a discriminative framework, it is not obvious to determine how unlabeled data or even the perfect knowledge of the input distribution P(x) can help in the estimation of the decision function. [sent-12, score-0.499]

9 Thus, to make use of unlabeled data, one needs to formulate assumptions. [sent-14, score-0.363]

10 One which is made, explicitly or implicitly, by most of the semi-supervised learning algorithms is the so-called "cluster assumption" saying that two points are likely to have the same class label if there is a path connecting them passing through regions of high density only. [sent-15, score-0.113]

11 Another way of stating this assumption is to say that the decision boundary should lie in regions of low density. [sent-16, score-0.172]

12 In real world problems, this makes sense: let us consider handwritten digit recognition and suppose one tries to classify digits 0 from 1. [sent-17, score-0.316]

13 The probability of having a digit which in between a 0 and 1 is very low. [sent-18, score-0.102]

14 In this article, we will show how to design kernels which implement the cluster assumption, i. [sent-19, score-0.576]

15 kernels such that the induced distance is small for points in the same cluster and larger for points in different clusters. [sent-21, score-0.789]

16 + Figure 1: Decision function obtained by an SVM with the kernel (1). [sent-29, score-0.343]

17 On this toy problem, this kernel implements perfectly the cluster assumption: the decision function cuts a cluster only when necessary. [sent-30, score-1.233]

18 2 Kernels implementing the cluster assumption In this section, we explore different ideas on how to build kernels which take into account the fact that the data is clustered. [sent-31, score-0.685]

19 1 Kernels from mixture models It is possible to design directly a kernel taking into account the generative model learned from the unlabeled data. [sent-34, score-0.911]

20 Seeger [9] derived such a kernel in a Bayesian setting. [sent-35, score-0.343]

21 He proposes to use the unlabeled data to learn a mixture of models and he introduces the Mutual Information kernel which is defined in such way that two points belonging to different components of the mixture model will have a low dot product. [sent-36, score-0.971]

22 Thus, in the case of a mixture of Gaussians, this kernel is an implementation of the cluster assumption. [sent-37, score-0.811]

23 Note that in the case of a single mixture model, the Fisher kernel [3] is an approximation of this Mutual Information kernel. [sent-38, score-0.419]

24 Independently, another extension of the Fisher kernel has been proposed in [12] which leads, in the case of a mixture of Gaussians (J. [sent-39, score-0.419]

25 Lk, ~k) to the Marginalized kernel whose behavior is similar to the mutual information kernel, q K(x, y) = L P(klx)P(kly)x T~kly. [sent-40, score-0.393]

26 (1) k=l To understand the behavior of the Marginalized kernel, we designed a 2D-toy problem (figure 1): 200 unlabeled points have been sampled from a mixture of two Gaussians, whose parameters have then been learned with EM applied to these points. [sent-41, score-0.552]

27 An SVM has been trained on 3 labeled points using the Marginalized kernel (1). [sent-42, score-0.597]

28 2 Random walk kernel The kernels presented in the previous section have the drawback of depending on a generative model: first, they require an unsupervised learning step, but more importantly, in a lot of real world problems, they cannot model the input distribution with sufficient accuracy. [sent-45, score-0.747]

29 When applying the mixture of Gaussians method (presented above) to real world problems, one cannot expect the "ideal" result of figure 1. [sent-46, score-0.109]

30 For this reason, in clustering and semi-supervised learning, there has been a lot of interest to find algorithms which do not depend on a generative model. [sent-47, score-0.259]

31 We will present two of them, find out how they are related and present a kernel which extends them. [sent-48, score-0.39]

32 The first one is the random walk representation proposed in [11] . [sent-49, score-0.134]

33 The main idea is to compute the RBF kernel matrix (with the labeled and unlabeled points) Kij = exp( -llxi - Xj 112 /2( 2 ) and to interpret it as a transition matrix of . [sent-50, score-1.037]

34 a random walk on a graph with vertices Xi , P(Xi -+ Xj) = "K'ktp . [sent-51, score-0.098]

35 J p (where t is a parameter to be determined) , the probability of going from a point Xi to a point Xj should be quite high if both points belong to the same cluster and should stay low if they are in two different clusters. [sent-53, score-0.537]

36 Let D be the diagonal matrix whose elements are Dii = Lj K ij . [sent-54, score-0.143]

37 The one step transition matrix is D - 1 K and after t steps it is pt = (D - 1 K)t. [sent-55, score-0.232]

38 In [11], the authors design a classifier which uses directly those transition probabilities. [sent-56, score-0.191]

39 One would be tempted to use pt as a kernel matrix for a SVM classifier. [sent-57, score-0.569]

40 However, it is not possible to directly use pt as a kernel matrix since it is not even symmetric. [sent-58, score-0.537]

41 We will see in section 3 how a modified version of pt can be used as a kernel. [sent-59, score-0.118]

42 3 Kernel induced by a clustered representation Another idea to implement the cluster assumption is to change the representation of the input points such that points in the same cluster are grouped together in the new representation. [sent-61, score-1.333]

43 For this purpose, one can use tools of spectral clustering (see [13] for a review) Using the first eigenvectors of a similarity matrix, a representation where the points are naturally well clustered has been recently presented in [5]. [sent-62, score-0.392]

44 We suggest to train a discriminative learning algorithm in this representation. [sent-63, score-0.073]

45 This algorithm, which resembles kernel PCA, is the following: 1. [sent-64, score-0.343]

46 Compute the affinity matrix, which is an RBF kernel matrix but with diagonal elements being 0 instead of 1. [sent-65, score-0.695]

47 Let D be a diagonal matrix with diagonal elements equal to the sum of the rows (or the columns) of K and construct the matrix L = D - 1 / 2 KD - 1 / 2 . [sent-67, score-0.317]

48 The new representation of the point Xi is (Vii' . [sent-74, score-0.036]

49 0:=;= 1 The reason to consider the first eigenvectors of the affinity matrix is the following. [sent-78, score-0.402]

50 One can show that in this case, the first k eigenvalues of the affinity matrix will be 1 and the eigenvalue k + 1 will be strictly less than 1 [5]. [sent-80, score-0.449]

51 The value of this gap depends on how well connected each cluster is: the better connected, the larger the gap is (the smaller the k + 1st eigenvalue). [sent-81, score-0.472]

52 ,Zk orthonormal to each other such that each training point is mapped to one of those k points depending on the cluster it belongs to. [sent-85, score-0.54]

53 This simple example show that in this new representation points are naturally clustered and we suggest to train a linear classifier on the mapped points. [sent-86, score-0.315]

54 3 Extension of the cluster kernel Based on the ideas of the previous section, we propose the following algorithm: 1. [sent-87, score-0.776]

55 As before, compute the RBF matrix K from both labeled and unlabeled points (this time with 1 on the diagonal and not 0) and D, the diagonal matrix whose elements are the sum of the rows of K. [sent-88, score-0.934]

56 Compute L = D- 1 / 2 K D- 1 / 2 and its eigendecomposition L = U AUT. [sent-90, score-0.059]

57 Given a transfer function n + 10 For large sizes of the (labeled) training set, all approaches give similar results. [sent-92, score-0.227]

58 The polynomial transfer function does not give good results for very small training sets (but nevertheless outperforms the standard SVM for medium sizes). [sent-95, score-0.269]

59 This might be due to the fact that in this example, the second largest eigenvalue is 0. [sent-96, score-0.103]

60 Since the polynomial transfer function tends 1 We consider here an RBF kernel and for this reason the matrix K is always invertible. [sent-98, score-0.771]

61 to push to 0 the small eigenvalues, it turns out that the new kernel has "rank almost one" and it is more difficult to learn with such a kernel. [sent-99, score-0.375]

62 To avoid this problem, the authors of [11] consider a sparse affinity matrix with non-zeros entries only for neighbor examples. [sent-100, score-0.32]

63 In this way the data are by construction more clustered and the eigenvalues are larger. [sent-101, score-0.182]

64 We verified experimentally that the polynomial transfer function gave better results when applied to a sparse affinity matrix. [sent-102, score-0.541]

65 Concerning the step transfer function, the value of the cut-off index corresponds to the number of dimensions in the feature space induced by the kernel, since the latter is linear in the representation given by the eigendecomposition of the affinity matrix. [sent-103, score-0.656]

66 Intuitively, it makes sense to have the number of dimensions increase with the number of training examples, that is the reason why we chose a cutoff index equal to n + 10. [sent-104, score-0.292]

67 The general form of this transfer function is i i ~ r >r ' (2) where p, q E lR and r E N are 3 hyperparameters. [sent-109, score-0.192]

68 It is possible to do so by gradient descent on an estimate of the generalization error [2]. [sent-111, score-0.075]

69 To assess the possibility of estimating accurately the test error associated with the poly-step kernel, we computed the span estimate [2] in the same setting as in the previous section. [sent-112, score-0.288]

70 We fixed p = q = 2 and the number of training points to 16 (8 per class). [sent-113, score-0.148]

71 The span estimate and the test error are plotted on the left side of figure 3. [sent-114, score-0.254]

72 Another possibility would be to explore methods that take into account the spectrum of the kernel matrix in order to predict the test error [7]. [sent-115, score-0.62]

73 3 Comparison with other algorithms We summarized the test errors (averaged over 100 trials) of different algorithms trained on 16 labeled examples in the following table. [sent-117, score-0.185]

74 The transductive SVM algorithm consists in maximizing the margin on both labeled and unlabeled. [sent-118, score-0.3]

75 To some extent it implements also the cluster assumption since it tends to put the decision function in low density regions. [sent-119, score-0.69]

76 This algorithm has been successfully applied to text categorization [4] and is a state-of-the-art algorithm for 0. [sent-120, score-0.081]

77 22 ,----~~-~~-7_ T' "= O, ==]l ~= '''== --e- S an estimale -e- S an estimate 0. [sent-122, score-0.037]

78 15 10 15 20 25 30 10 12 14 16 16 20 Figure 3: The span estimate predicts accurately the minimum of the test error for different values of the cutoff index r in the poly-step kernel (2). [sent-131, score-0.745]

79 Left: text classification task, right: handwritten digit classification performing semi-supervised learning. [sent-132, score-0.455]

80 The result of the Random walk kernel is taken directly from [11]. [sent-133, score-0.441]

81 Finally, the cluster kernel performance has been obtained with p = q = 2 and r = 10 in the transfer function 2. [sent-134, score-0.927]

82 The value of r was the one minimizing the span estimate (see left side of figure 3). [sent-135, score-0.172]

83 Future experiments include for instance the Marginalized kernel (1) with the standard generative model used in text classification by Naive Bayes classifier [6]. [sent-136, score-0.676]

84 4 Digit recognition In a second set of experiments, we considered the task of classifying the handwritten digits 0 to 4 against 5 to 9 of the USPS database. [sent-138, score-0.139]

85 The cluster assumption should apply fairly well on this database since the different digits are likely to be clustered. [sent-139, score-0.543]

86 For a given run, one of the subsets was used as the labeled training set, whereas the other points remained unlabeled. [sent-141, score-0.32]

87 The width of the RBF kernel was set to 5 (it was the value minimizing the test error in the supervised case). [sent-142, score-0.425]

88 5%), whereas the transductive SVM algorithm of [4] did not yield a significant improvement (17. [sent-145, score-0.19]

89 As for the cluster kernel (2), the cutoff index r was again selected by minimizing the span estimate (see right side of figure 3). [sent-148, score-1.053]

90 It is interesting to note in figure 3 the local minimum at r = 10, which can be interpreted easily since it corresponds to the number of different digits in the database. [sent-152, score-0.077]

91 It is somehow surprising that the transductive SVM algorithm did not improve the test error on this classification problem, whereas it did for text classification. [sent-153, score-0.49]

92 We conjecture the following explanation: the transductive SVM is more sensitive to outliers in the unlabeled set than the cluster kernel methods since it directly tries to maximize the margin on the unlabeled points. [sent-154, score-1.662]

93 For instance, in the top middle part of figure 1, there is an unlabeled point which would have probably perturbed this algorithm. [sent-155, score-0.363]

94 However, in high dimensional problems such as text classification, the influence of outlier points is smaller. [sent-156, score-0.194]

95 5 Conclusion In a discriminative setting, a reasonable way to incorporate unlabeled data is through the cluster assumption. [sent-158, score-0.828]

96 Based on the ideas of spectral clustering and random walks, we proposed a framework for constructing kernels which implement the cluster assumption: the induced distance depends on whether the points are in the same cluster or not. [sent-159, score-1.243]

97 This is done by changing the spectrum of the kernel matrix. [sent-160, score-0.397]

98 Finally, note that the cluster assumption might also be useful in a purely supervised learning task. [sent-162, score-0.466]

99 Transductive inference for text classification using support vector machines. [sent-185, score-0.186]

100 Learning to classify text from labeled and unlabeled documents. [sent-201, score-0.585]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('cluster', 0.392), ('unlabeled', 0.363), ('kernel', 0.343), ('affinity', 0.209), ('transfer', 0.192), ('transductive', 0.159), ('marginalized', 0.148), ('labeled', 0.141), ('pt', 0.118), ('svm', 0.118), ('points', 0.113), ('kernels', 0.113), ('classification', 0.105), ('cutoff', 0.104), ('digit', 0.102), ('eigenvalues', 0.101), ('rbf', 0.098), ('walk', 0.098), ('lot', 0.098), ('span', 0.094), ('classifier', 0.085), ('text', 0.081), ('clustered', 0.081), ('digits', 0.077), ('matrix', 0.076), ('mixture', 0.076), ('assumption', 0.074), ('discriminative', 0.073), ('szummer', 0.07), ('tends', 0.067), ('diagonal', 0.067), ('scholkopf', 0.066), ('eigenvectors', 0.066), ('eigenvalue', 0.063), ('gaussians', 0.063), ('decision', 0.063), ('handwritten', 0.062), ('generative', 0.062), ('dimensions', 0.06), ('eigendecomposition', 0.059), ('induced', 0.058), ('spectrum', 0.054), ('chapelle', 0.053), ('clustering', 0.052), ('put', 0.051), ('reason', 0.051), ('mutual', 0.05), ('xj', 0.047), ('find', 0.047), ('page', 0.045), ('xi', 0.044), ('test', 0.044), ('spectral', 0.044), ('implements', 0.043), ('accurately', 0.043), ('polynomial', 0.042), ('index', 0.042), ('tries', 0.042), ('side', 0.041), ('ideas', 0.041), ('gap', 0.04), ('largest', 0.04), ('error', 0.038), ('implement', 0.038), ('transition', 0.038), ('estimate', 0.037), ('web', 0.037), ('representation', 0.036), ('fisher', 0.036), ('authors', 0.035), ('volume', 0.035), ('stating', 0.035), ('blum', 0.035), ('dii', 0.035), ('eigenspectrum', 0.035), ('menlo', 0.035), ('planck', 0.035), ('zl', 0.035), ('training', 0.035), ('kaufmann', 0.034), ('experimentally', 0.034), ('account', 0.034), ('explanation', 0.034), ('design', 0.033), ('world', 0.033), ('gave', 0.032), ('stay', 0.032), ('jason', 0.032), ('kin', 0.032), ('neurocolt', 0.032), ('somehow', 0.032), ('tempted', 0.032), ('tsuda', 0.032), ('verified', 0.032), ('walks', 0.032), ('turns', 0.032), ('assess', 0.032), ('whereas', 0.031), ('explore', 0.031), ('rows', 0.031)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9999997 52 nips-2002-Cluster Kernels for Semi-Supervised Learning

Author: Olivier Chapelle, Jason Weston, Bernhard SchĂślkopf

2 0.25486684 156 nips-2002-On the Complexity of Learning the Kernel Matrix

Author: Olivier Bousquet, Daniel Herrmann

Abstract: We investigate data based procedures for selecting the kernel when learning with Support Vector Machines. We provide generalization error bounds by estimating the Rademacher complexities of the corresponding function classes. In particular we obtain a complexity bound for function classes induced by kernels with given eigenvectors, i.e., we allow to vary the spectrum and keep the eigenvectors ﬁx. This bound is only a logarithmic factor bigger than the complexity of the function class induced by a single kernel. However, optimizing the margin over such classes leads to overﬁtting. We thus propose a suitable way of constraining the class. We use an efﬁcient algorithm to solve the resulting optimization problem, present preliminary experimental results, and compare them to an alignment-based approach.

3 0.25277606 120 nips-2002-Kernel Design Using Boosting

Author: Koby Crammer, Joseph Keshet, Yoram Singer

Abstract: The focus of the paper is the problem of learning kernel operators from empirical data. We cast the kernel design problem as the construction of an accurate kernel from simple (and less accurate) base kernels. We use the boosting paradigm to perform the kernel construction process. To do so, we modify the booster so as to accommodate kernel operators. We also devise an efﬁcient weak-learner for simple kernels that is based on generalized eigen vector decomposition. We demonstrate the effectiveness of our approach on synthetic data and on the USPS dataset. On the USPS dataset, the performance of the Perceptron algorithm with learned kernels is systematically better than a ﬁxed RBF kernel. 1 Introduction and problem Setting The last decade brought voluminous amount of work on the design, analysis and experimentation of kernel machines. Algorithm based on kernels can be used for various machine learning tasks such as classiﬁcation, regression, ranking, and principle component analysis. The most prominent learning algorithm that employs kernels is the Support Vector Machines (SVM) [1, 2] designed for classiﬁcation and regression. A key component in a kernel machine is a kernel operator which computes for any pair of instances their inner-product in some abstract vector space. Intuitively and informally, a kernel operator is a means for measuring similarity between instances. Almost all of the work that employed kernel operators concentrated on various machine learning problems that involved a predeﬁned kernel. A typical approach when using kernels is to choose a kernel before learning starts. Examples to popular predeﬁned kernels are the Radial Basis Functions and the polynomial kernels (see for instance [1]). Despite the simplicity required in modifying a learning algorithm to a “kernelized” version, the success of such algorithms is not well understood yet. More recently, special efforts have been devoted to crafting kernels for speciﬁc tasks such as text categorization [3] and protein classiﬁcation problems [4]. Our work attempts to give a computational alternative to predeﬁned kernels by learning kernel operators from data. We start with a few deﬁnitions. Let X be an instance space. A kernel is an inner-product operator K : X × X → . An explicit way to describe K is via a mapping φ : X → H from X to an inner-products space H such that K(x, x ) = φ(x)·φ(x ). Given a kernel operator and a ﬁnite set of instances S = {xi , yi }m , the kernel i=1 matrix (a.k.a the Gram matrix) is the matrix of all possible inner-products of pairs from S, Ki,j = K(xi , xj ). We therefore refer to the general form of K as the kernel operator and to the application of the kernel operator to a set of pairs of instances as the kernel matrix. The speciﬁc setting of kernel design we consider assumes that we have access to a base kernel learner and we are given a target kernel K manifested as a kernel matrix on a set of examples. Upon calling the base kernel learner it returns a kernel operator denote Kj . The goal thereafter is to ﬁnd a weighted combination of kernels ˆ K(x, x ) = j αj Kj (x, x ) that is similar, in a sense that will be deﬁned shortly, to ˆ the target kernel, K ∼ K . Cristianini et al. [5] in their pioneering work on kernel target alignment employed as the notion of similarity the inner-product between the kernel matrices < K, K >F = m K(xi , xj )K (xi , xj ). Given this deﬁnition, they deﬁned the i,j=1 kernel-similarity, or alignment, to be the above inner-product normalized by the norm of ˆ ˆ ˆ ˆ ˆ each kernel, A(S, K, K ) = < K, K >F / < K, K >F < K , K >F , where S is, as above, a ﬁnite sample of m instances. Put another way, the kernel alignment Cristianini et al. employed is the cosine of the angle between the kernel matrices where each matrix is “ﬂattened” into a vector of dimension m2 . Therefore, this deﬁnition implies that the alignment is bounded above by 1 and can attain this value iff the two kernel matrices are identical. Given a (column) vector of m labels y where yi ∈ {−1, +1} is the label of the instance xi , Cristianini et al. used the outer-product of y as the the target kernel, ˆ K = yy T . Therefore, an optimal alignment is achieved if K(xi , xj ) = yi yj . Clearly, if such a kernel is used for classifying instances from X , then the kernel itself sufﬁces to construct an excellent classiﬁer f : X → {−1, +1} by setting, f (x) = sign(y i K(xi , x)) where (xi , yi ) is any instance-label pair. Cristianini et al. then devised a procedure that works with both labelled and unlabelled examples to ﬁnd a Gram matrix which attains a good alignment with K on the labelled part of the matrix. While this approach can clearly construct powerful kernels, a few problems arise from the notion of kernel alignment they employed. For instance, a kernel operator such that the sign(K(x i , xj )) is equal to yi yj but its magnitude, |K(xi , xj )|, is not necessarily 1, might achieve a poor alignment score while it can constitute a classiﬁer whose empirical loss is zero. Furthermore, the task of ﬁnding a good kernel when it is not always possible to ﬁnd a kernel whose sign on each pair of instances is equal to the products of the labels (termed the soft-margin case in [5, 6]) becomes rather tricky. We thus propose a different approach which attempts to overcome some of the difﬁculties above. Like Cristianini et al. we assume that we are given a set of labelled instances S = {(xi , yi ) | xi ∈ X , yi ∈ {−1, +1}, i = 1, . . . , m} . We are also given a set of unlabelled m ˜ ˜ examples S = {˜i }i=1 . If such a set is not provided we can simply use the labelled inx ˜ ˜ stances (without the labels themselves) as the set S. The set S is used for constructing the ˆ primitive kernels that are combined to constitute the learned kernel K. The labelled set is used to form the target kernel matrix and its instances are used for evaluating the learned ˆ kernel K. This approach, known as transductive learning, was suggested in [5, 6] for kernel alignment tasks when the distribution of the instances in the test data is different from that of the training data. This setting becomes in particular handy in datasets where the test data was collected in a different scheme than the training data. We next discuss the notion of kernel goodness employed in this paper. This notion builds on the objective function that several variants of boosting algorithms maintain [7, 8]. We therefore ﬁrst discuss in brief the form of boosting algorithms for kernels. 2 Using Boosting to Combine Kernels Numerous interpretations of AdaBoost and its variants cast the boosting process as a procedure that attempts to minimize, or make small, a continuous bound on the classiﬁcation error (see for instance [9, 7] and the references therein). A recent work by Collins et al. [8] uniﬁes the boosting process for two popular loss functions, the exponential-loss (denoted henceforth as ExpLoss) and logarithmic-loss (denoted as LogLoss) that bound the empir- ˜ ˜ Input: Labelled and unlabelled sets of examples: S = {(xi , yi )}m ; S = {˜i }m x i=1 i=1 Initialize: K ← 0 (all zeros matrix) For t = 1, 2, . . . , T : • Calculate distribution over pairs 1 ≤ i, j ≤ m: Dt (i, j) = exp(−yi yj K(xi , xj )) 1/(1 + exp(−yi yj K(xi , xj ))) ExpLoss LogLoss ˜ • Call base-kernel-learner with (Dt , S, S) and receive Kt • Calculate: + − St = {(i, j) | yi yj Kt (xi , xj ) > 0} ; St = {(i, j) | yi yj Kt (xi , xj ) < 0} + Wt = (i,j)∈S + Dt (i, j)|Kt (xi , xj )| ; Wt− = (i,j)∈S − Dt (i, j)|Kt (xi , xj )| t t 1 2 + Wt − Wt • Set: αt = ln ; K ← K + α t Kt . Return: kernel operator K : X × X → Figure 1: The skeleton of the boosting algorithm for kernels. ical classiﬁcation error. Given the prediction of a classiﬁer f on an instance x and a label y ∈ {−1, +1} the ExpLoss and the LogLoss are deﬁned as, ExpLoss(f (x), y) = exp(−yf (x)) LogLoss(f (x), y) = log(1 + exp(−yf (x))) . Collins et al. described a single algorithm for the two losses above that can be used within the boosting framework to construct a strong-hypothesis which is a classiﬁer f (x). This classiﬁer is a weighted combination of (possibly very simple) base classiﬁers. (In the boosting framework, the base classiﬁers are referred to as weak-hypotheses.) The strongT hypothesis is of the form f (x) = t=1 αt ht (x). Collins et al. discussed a few ways to select the weak-hypotheses ht and to ﬁnd a good of weights αt . Our starting point in this paper is the ﬁrst sequential algorithm from [8] that enables the construction or creation of weak-hypotheses on-the-ﬂy. We would like to note however that it is possible to use other variants of boosting to design kernels. In order to use boosting to design kernels we extend the algorithm to operate over pairs of instances. Building on the notion of alignment from [5, 6], we say that the inner-product of x1 and x2 is aligned with the labels y1 and y2 if sign(K(x1 , x2 )) = y1 y2 . Furthermore, we would like to make the magnitude of K(x, x ) to be as large as possible. We therefore use one of the following two alignment losses for a pair of examples (x 1 , y1 ) and (x2 , y2 ), ExpLoss(K(x1 , x2 ), y1 y2 ) = exp(−y1 y2 K(x1 , x2 )) LogLoss(K(x1 , x2 ), y1 y2 ) = log(1 + exp(−y1 y2 K(x1 , x2 ))) . Put another way, we view a pair of instances as a single example and cast the pairs of instances that attain the same label as positively labelled examples while pairs of opposite labels are cast as negatively labelled examples. Clearly, this approach can be applied to both losses. In the boosting process we therefore maintain a distribution over pairs of instances. The weight of each pair reﬂects how difﬁcult it is to predict whether the labels of the two instances are the same or different. The core boosting algorithm follows similar lines to boosting algorithms for classiﬁcation algorithm. The pseudo code of the booster is given in Fig. 1. The pseudo-code is an adaptation the to problem of kernel design of the sequentialupdate algorithm from [8]. As with other boosting algorithm, the base-learner, which in our case is charge of returning a good kernel with respect to the current distribution, is left unspeciﬁed. We therefore turn our attention to the algorithmic implementation of the base-learning algorithm for kernels. 3 Learning Base Kernels The base kernel learner is provided with a training set S and a distribution D t over a pairs ˜ of instances from the training set. It is also provided with a set of unlabelled examples S. Without any knowledge of the topology of the space of instances a learning algorithm is likely to fail. Therefore, we assume the existence of an initial inner-product over the input space. We assume for now that this initial inner-product is the standard scalar products over vectors in n . We later discuss a way to relax the assumption on the form of the inner-product. Equipped with an inner-product, we deﬁne the family of base kernels to be the possible outer-products Kw = wwT between a vector w ∈ n and itself. Using this deﬁnition we get, Kw (xi , xj ) = (xi ·w)(xj ·w) . Input: A distribution Dt . Labelled and unlabelled sets: ˜ ˜ Therefore, the similarity beS = {(xi , yi )}m ; S = {˜i }m . x i=1 i=1 tween two instances xi and Compute : xj is high iff both xi and xj • Calculate: ˜ are similar (w.r.t the standard A ∈ m×m , Ai,r = xi · xr ˜ inner-product) to a third vecm×m B∈ , Bi,j = Dt (i, j)yi yj tor w. Analogously, if both ˜ ˜ K ∈ m×m , Kr,s = xr · xs ˜ ˜ xi and xj seem to be dissim• Find the generalized eigenvector v ∈ m for ilar to the vector w then they the problem AT BAv = λKv which attains are similar to each other. Dethe largest eigenvalue λ spite the restrictive form of • Set: w = ( r vr xr )/ ˜ ˜ r vr xr . the inner-products, this famt ily is still too rich for our setReturn: Kernel operator Kw = ww . ting and we further impose two restrictions on the inner Figure 2: The base kernel learning algorithm. products. First, we assume ˜ that w is restricted to a linear combination of vectors from S. Second, since scaling of the base kernels is performed by the boosted, we constrain the norm of w to be 1. The m ˜ resulting class of kernels is therefore, C = {Kw = wwT | w = r=1 βr xr , w = 1} . ˜ In the boosting process we need to choose a speciﬁc base-kernel K w from C. We therefore need to devise a notion of how good a candidate for base kernel is given a labelled set S and a distribution function Dt . In this work we use the simplest version suggested by Collins et al. This version can been viewed as a linear approximation on the loss function. We deﬁne the score of a kernel Kw w.r.t to the current distribution Dt to be, Score(Kw ) = Dt (i, j)yi yj Kw (xi , xj ) . (1) i,j The higher the value of the score is, the better Kw ﬁts the training data. Note that if Dt (i, j) = 1/m2 (as is D0 ) then Score(Kw ) is proportional to the alignment since w = 1. Under mild assumptions the score can also provide a lower bound of the loss function. To see that let c be the derivative of the loss function at margin zero, c = Loss (0) . If all the √ training examples xi ∈ S lies in a ball of radius c, we get that Loss(Kw (xi , xj ), yi yj ) ≥ 1 − cKw (xi , xj )yi yj ≥ 0, and therefore, i,j Dt (i, j)Loss(Kw (xi , xj ), yi yj ) ≥ 1 − c Dt (i, j)Kw (xi , xj )yi yj . i,j Using the explicit form of Kw in the Score function (Eq. (1)) we get, Score(Kw ) = i,j D(i, j)yi yj (w·xi )(w·xj ) . Further developing the above equation using the constraint that w = m ˜ r=1 βr xr we get, ˜ Score(Kw ) = βs βr r,s i,j D(i, j)yi yj (xi · xr ) (xj · xs ) . ˜ ˜ To compute efﬁciently the base kernel score without an explicit enumeration we exploit the fact that if the initial distribution D0 is symmetric (D0 (i, j) = D0 (j, i)) then all the distributions generated along the run of the boosting process, D t , are also symmetric. We ˜ now deﬁne a matrix A ∈ m×m where Ai,r = xi · xr and a symmetric matrix B ∈ m×m ˜ with Bi,j = Dt (i, j)yi yj . Simple algebraic manipulations yield that the score function can be written as the following quadratic form, Score(β) = β T (AT BA)β , where β is m dimensional column vector. Note that since B is symmetric so is A T BA. Finding a ˜ good base kernel is equivalent to ﬁnding a vector β which maximizes this quadratic form 2 m ˜ under the norm equality constraint w = ˜ 2 = β T Kβ = 1 where Kr,s = r=1 βr xr xr · xs . Finding the maximum of Score(β) subject to the norm constraint is a well known ˜ ˜ maximization problem known as the generalized eigen vector problem (cf. [10]). Applying simple algebraic manipulations it is easy to show that the matrix AT BA is positive semideﬁnite. Assuming that the matrix K is invertible, the the vector β which maximizes the quadratic form is proportional the eigenvector of K −1 AT BA which is associated with the m ˜ generalized largest eigenvalue. Denoting this vector by v we get that w ∝ ˜ r=1 vr xr . m ˜ m ˜ Adding the norm constraint we get that w = ( r=1 vr xr )/ ˜ vr xr . The skeleton ˜ r=1 of the algorithm for ﬁnding a base kernels is given in Fig. 3. To conclude the description of the kernel learning algorithm we describe how to the extend the algorithm to be employed with general kernel functions. Kernelizing the Kernel: As described above, we assumed that the standard scalarproduct constitutes the template for the class of base-kernels C. However, since the proce˜ dure for choosing a base kernel depends on S and S only through the inner-products matrix A, we can replace the scalar-product itself with a general kernel operator κ : X × X → , where κ(xi , xj ) = φ(xi ) · φ(xj ). Using a general kernel function κ we can not compute however the vector w explicitly. We therefore need to show that the norm of w, and evaluation Kw on any two examples can still be performed efﬁciently. First note that given the vector v we can compute the norm of w as follows, T w 2 = vr xr ˜ vs xr ˜ r s = vr vs κ(˜r , xs ) . x ˜ r,s Next, given two vectors xi and xj the value of their inner-product is, Kw (xi , xj ) = vr vs κ(xi , xr )κ(xj , xs ) . ˜ ˜ r,s Therefore, although we cannot compute the vector w explicitly we can still compute its norm and evaluate any of the kernels from the class C. 4 Experiments Synthetic data: We generated binary-labelled data using as input space the vectors in 100 . The labels, in {−1, +1}, were picked uniformly at random. Let y designate the label of a particular example. Then, the ﬁrst two components of each instance were drawn from a two-dimensional normal distribution, N (µ, ∆ ∆−1 ) with the following parameters, µ=y 0.03 0.03 1 ∆= √ 2 1 −1 1 1 = 0.1 0 0 0.01 . That is, the label of each examples determined the mean of the distribution from which the ﬁrst two components were generated. The rest of the components in the vector (98 8 0.2 6 50 50 100 100 150 150 200 200 4 2 0 0 −2 −4 −6 250 250 −0.2 −8 −0.2 0 0.2 −8 −6 −4 −2 0 2 4 6 8 300 20 40 60 80 100 120 140 160 180 200 300 20 40 60 80 100 120 140 160 180 Figure 3: Results on a toy data set prior to learning a kernel (ﬁrst and third from left) and after learning (second and fourth). For each of the two settings we show the ﬁrst two components of the training data (left) and the matrix of inner products between the train and the test data (right). altogether) were generated independently using the normal distribution with a zero mean and a standard deviation of 0.05. We generated 100 training and test sets of size 300 and 200 respectively. We used the standard dot-product as the initial kernel operator. On each experiment we ﬁrst learned a linear classier that separates the classes using the Perceptron [11] algorithm. We ran the algorithm for 10 epochs on the training set. After each epoch we evaluated the performance of the current classiﬁer on the test set. We then used the boosting algorithm for kernels with the LogLoss for 30 rounds to build a kernel for each random training set. After learning the kernel we re-trained a classiﬁer with the Perceptron algorithm and recorded the results. A summary of the online performance is given in Fig. 4. The plot on the left-hand-side of the ﬁgure shows the instantaneous error (achieved during the run of the algorithm). Clearly, the Perceptron algorithm with the learned kernel converges much faster than the original kernel. The middle plot shows the test error after each epoch. The plot on the right shows the test error on a noisy test set in which we added a Gaussian noise of zero mean and a standard deviation of 0.03 to the ﬁrst two features. In all plots, each bar indicates a 95% conﬁdence level. It is clear from the ﬁgure that the original kernel is much slower to converge than the learned kernel. Furthermore, though the kernel learning algorithm was not expoed to the test set noise, the learned kernel reﬂects better the structure of the feature space which makes the learned kernel more robust to noise. Fig. 3 further illustrates the beneﬁts of using a boutique kernel. The ﬁrst and third plots from the left correspond to results obtained using the original kernel and the second and fourth plots show results using the learned kernel. The left plots show the empirical distribution of the two informative components on the test data. For the learned kernel we took each input vector and projected it onto the two eigenvectors of the learned kernel operator matrix that correspond to the two largest eigenvalues. Note that the distribution after the projection is bimodal and well separated along the ﬁrst eigen direction (x-axis) and shows rather little deviation along the second eigen direction (y-axis). This indicates that the kernel learning algorithm indeed found the most informative projection for separating the labelled data with large margin. It is worth noting that, in this particular setting, any algorithm which chooses a single feature at a time is prone to failure since both the ﬁrst and second features are mandatory for correctly classifying the data. The two plots on the right hand side of Fig. 3 use a gray level color-map to designate the value of the inner-product between each pairs instances, one from training set (y-axis) and the other from the test set. The examples were ordered such that the ﬁrst group consists of the positively labelled instances while the second group consists of the negatively labelled instances. Since most of the features are non-relevant the original inner-products are noisy and do not exhibit any structure. In contrast, the inner-products using the learned kernel yields in a 2 × 2 block matrix indicating that the inner-products between instances sharing the same label obtain large positive values. Similarly, for instances of opposite 200 1 12 Regular Kernel Learned Kernel 0.8 17 0.7 16 0.5 0.4 0.3 Test Error % 8 0.6 Regular Kernel Learned Kernel 18 10 Test Error % Averaged Cumulative Error % 19 Regular Kernel Learned Kernel 0.9 6 4 15 14 13 12 0.2 11 2 0.1 10 0 0 10 1 10 2 10 Round 3 10 4 10 0 2 4 6 Epochs 8 10 9 2 4 6 Epochs 8 10 Figure 4: The online training error (left), test error (middle) on clean synthetic data using a standard kernel and a learned kernel. Right: the online test error for the two kernels on a noisy test set. labels the inner products are large and negative. The form of the inner-products matrix of the learned kernel indicates that the learning problem itself becomes much easier. Indeed, the Perceptron algorithm with the standard kernel required around 94 training examples on the average before converging to a hyperplane which perfectly separates the training data while using the Perceptron algorithm with learned kernel required a single example to reach a perfect separation on all 100 random training sets. USPS dataset: The USPS (US Postal Service) dataset is known as a challenging classiﬁcation problem in which the training set and the test set were collected in a different manner. The USPS contains 7, 291 training examples and 2, 007 test examples. Each example is represented as a 16 × 16 matrix where each entry in the matrix is a pixel that can take values in {0, . . . , 255}. Each example is associated with a label in {0, . . . , 9} which is the digit content of the image. Since the kernel learning algorithm is designed for binary problems, we broke the 10-class problem into 45 binary problems by comparing all pairs of classes. The interesting question of how to learn kernels for multiclass problems is beyond the scopre of this short paper. We thus constraint on the binary error results for the 45 binary problem described above. For the original kernel we chose a RBF kernel with σ = 1 which is the value employed in the experiments reported in [12]. We used the kernelized version of the kernel design algorithm to learn a different kernel operator for each of the binary problems. We then used a variant of the Perceptron [11] and with the original RBF kernel and with the learned kernels. One of the motivations for using the Perceptron is its simplicity which can underscore differences in the kernels. We ran the kernel learning al˜ gorithm with LogLoss and ExpLoss, using bith the training set and the test test as S. Thus, we obtained four different sets of kernels where each set consists of 45 kernels. By examining the training loss, we set the number of rounds of boosting to be 30 for the LogLoss and 50 for the ExpLoss, when using the trainin set. When using the test set, the number of rounds of boosting was set to 100 for both losses. Since the algorithm exhibits slower rate of convergence with the test data, we choose a a higher value without attempting to optimize the actual value. The left plot of Fig. 5 is a scatter plot comparing the test error of each of the binary classiﬁers when trained with the original RBF a kernel versus the performance achieved on the same binary problem with a learned kernel. The kernels were built ˜ using boosting with the LogLoss and S was the training data. In almost all of the 45 binary classiﬁcation problems, the learned kernels yielded lower error rates when combined with the Perceptron algorithm. The right plot of Fig. 5 compares two learned kernels: the ﬁrst ˜ was build using the training instances as the templates constituing S while the second used the test instances. Although the differenece between the two versions is not as signiﬁcant as the difference on the left plot, we still achieve an overall improvement in about 25% of the binary problems by using the test instances. 6 4.5 4 5 Learned Kernel (Test) Learned Kernel (Train) 3.5 4 3 2 3 2.5 2 1.5 1 1 0.5 0 0 1 2 3 Base Kernel 4 5 6 0 0 1 2 3 Learned Kernel (Train) 4 5 Figure 5: Left: a scatter plot comparing the error rate of 45 binary classiﬁers trained using an RBF kernel (x-axis) and a learned kernel with training instances. Right: a similar scatter plot for a learned kernel only constructed from training instances (x-axis) and test instances. 5 Discussion In this paper we showed how to use the boosting framework to design kernels. Our approach is especially appealing in transductive learning tasks where the test data distribution is different than the the distribution of the training data. For example, in speech recognition tasks the training data is often clean and well recorded while the test data often passes through a noisy channel that distorts the signal. An interesting and challanging question that stem from this research is how to extend the framework to accommodate more complex decision tasks such as multiclass and regression problems. Finally, we would like to note alternative approaches to the kernel design problem has been devised in parallel and independently. See [13, 14] for further details. Acknowledgements: Special thanks to Cyril Goutte and to John Show-Taylor for pointing the connection to the generalized eigen vector problem. Thanks also to the anonymous reviewers for constructive comments. References [1] V. N. Vapnik. Statistical Learning Theory. Wiley, 1998. [2] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge University Press, 2000. [3] Huma Lodhi, John Shawe-Taylor, Nello Cristianini, and Christopher J. C. H. Watkins. Text classiﬁcation using string kernels. Journal of Machine Learning Research, 2:419–444, 2002. [4] C. Leslie, E. Eskin, and W. Stafford Noble. The spectrum kernel: A string kernel for svm protein classiﬁcation. In Proceedings of the Paciﬁc Symposium on Biocomputing, 2002. [5] Nello Cristianini, Andre Elisseeff, John Shawe-Taylor, and Jaz Kandla. On kernel target alignment. In Advances in Neural Information Processing Systems 14, 2001. [6] G. Lanckriet, N. Cristianini, P. Bartlett, L. El Ghaoui, and M. Jordan. Learning the kernel matrix with semi-deﬁnite programming. In Proc. of the 19th Intl. Conf. on Machine Learning, 2002. [7] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics, 28(2):337–374, April 2000. [8] Michael Collins, Robert E. Schapire, and Yoram Singer. Logistic regression, adaboost and bregman distances. Machine Learning, 47(2/3):253–285, 2002. [9] Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Functional gradient techniques for combining hypotheses. In Advances in Large Margin Classiﬁers. MIT Press, 1999. [10] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 1985. [11] F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65:386–407, 1958. [12] B. Sch¨ lkopf, S. Mika, C.J.C. Burges, P. Knirsch, K. M¨ ller, G. R¨ tsch, and A.J. Smola. Input o u a space vs. feature space in kernel-based methods. IEEE Trans. on NN, 10(5):1000–1017, 1999. [13] O. Bosquet and D.J.L. Herrmann. On the complexity of learning the kernel matrix. NIPS, 2002. [14] C.S. Ong, A.J. Smola, and R.C. Williamson. Superkenels. NIPS, 2002.

4 0.23152617 119 nips-2002-Kernel Dependency Estimation

Author: Jason Weston, Olivier Chapelle, Vladimir Vapnik, André Elisseeff, Bernhard Schölkopf

Abstract: We consider the learning problem of finding a dependency between a general class of objects and another, possibly different, general class of objects. The objects can be for example: vectors, images, strings, trees or graphs. Such a task is made possible by employing similarity measures in both input and output spaces using kernel functions, thus embedding the objects into vector spaces. We experimentally validate our approach on several tasks: mapping strings to strings, pattern recognition, and reconstruction from partial images. 1

5 0.16549389 106 nips-2002-Hyperkernels

Author: Cheng S. Ong, Robert C. Williamson, Alex J. Smola

Abstract: We consider the problem of choosing a kernel suitable for estimation using a Gaussian Process estimator or a Support Vector Machine. A novel solution is presented which involves deﬁning a Reproducing Kernel Hilbert Space on the space of kernels itself. By utilizing an analog of the classical representer theorem, the problem of choosing a kernel from a parameterized family of kernels (e.g. of varying width) is reduced to a statistical estimation problem akin to the problem of minimizing a regularized risk functional. Various classical settings for model or kernel selection are special cases of our framework.

6 0.16410361 125 nips-2002-Learning Semantic Similarity

7 0.16402854 145 nips-2002-Mismatch String Kernels for SVM Protein Classification

8 0.15825781 98 nips-2002-Going Metric: Denoising Pairwise Data

9 0.15444878 113 nips-2002-Information Diffusion Kernels

10 0.15356398 197 nips-2002-The Stability of Kernel Principal Components Analysis and its Relation to the Process Eigenspectrum

11 0.13627708 114 nips-2002-Information Regularization with Partially Labeled Data

12 0.13190666 24 nips-2002-Adaptive Scaling for Feature Selection in SVMs

13 0.12950294 27 nips-2002-An Impossibility Theorem for Clustering

14 0.12946475 109 nips-2002-Improving a Page Classifier with Anchor Extraction and Link Analysis

15 0.12789284 187 nips-2002-Spikernels: Embedding Spiking Neurons in Inner-Product Spaces

16 0.12766883 53 nips-2002-Clustering with the Fisher Score

17 0.12677115 191 nips-2002-String Kernels, Fisher Kernels and Finite State Automata

18 0.12342421 86 nips-2002-Fast Sparse Gaussian Process Methods: The Informative Vector Machine

19 0.11281651 99 nips-2002-Graph-Driven Feature Extraction From Microarray Data Using Diffusion Kernels and Kernel CCA

20 0.11202866 77 nips-2002-Effective Dimension and Generalization of Kernel Learning

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.313), (1, -0.214), (2, 0.156), (3, -0.133), (4, -0.225), (5, -0.024), (6, 0.146), (7, 0.048), (8, -0.019), (9, 0.112), (10, 0.082), (11, 0.052), (12, -0.077), (13, 0.068), (14, 0.004), (15, -0.044), (16, -0.011), (17, -0.071), (18, 0.104), (19, 0.098), (20, 0.055), (21, -0.061), (22, 0.068), (23, 0.04), (24, 0.111), (25, -0.115), (26, -0.06), (27, -0.082), (28, -0.131), (29, 0.032), (30, -0.056), (31, -0.091), (32, -0.014), (33, 0.178), (34, 0.04), (35, 0.077), (36, 0.005), (37, 0.034), (38, 0.025), (39, 0.024), (40, -0.045), (41, 0.096), (42, -0.056), (43, -0.027), (44, 0.027), (45, 0.052), (46, 0.122), (47, -0.034), (48, -0.037), (49, -0.129)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97079504 52 nips-2002-Cluster Kernels for Semi-Supervised Learning

Author: Olivier Chapelle, Jason Weston, Bernhard SchĂślkopf

2 0.71042448 119 nips-2002-Kernel Dependency Estimation

Author: Jason Weston, Olivier Chapelle, Vladimir Vapnik, André Elisseeff, Bernhard Schölkopf

3 0.67555171 120 nips-2002-Kernel Design Using Boosting

Author: Koby Crammer, Joseph Keshet, Yoram Singer

4 0.65377825 156 nips-2002-On the Complexity of Learning the Kernel Matrix

Author: Olivier Bousquet, Daniel Herrmann

5 0.63926721 106 nips-2002-Hyperkernels

Author: Cheng S. Ong, Robert C. Williamson, Alex J. Smola

6 0.6002025 98 nips-2002-Going Metric: Denoising Pairwise Data

7 0.55605751 113 nips-2002-Information Diffusion Kernels

8 0.54080099 197 nips-2002-The Stability of Kernel Principal Components Analysis and its Relation to the Process Eigenspectrum

9 0.5324865 125 nips-2002-Learning Semantic Similarity

10 0.52253091 145 nips-2002-Mismatch String Kernels for SVM Protein Classification

11 0.49526399 70 nips-2002-Distance Metric Learning with Application to Clustering with Side-Information

12 0.48040271 99 nips-2002-Graph-Driven Feature Extraction From Microarray Data Using Diffusion Kernels and Kernel CCA

13 0.45711932 188 nips-2002-Stability-Based Model Selection

14 0.4534218 187 nips-2002-Spikernels: Embedding Spiking Neurons in Inner-Product Spaces

15 0.45236501 167 nips-2002-Rational Kernels

16 0.45103899 191 nips-2002-String Kernels, Fisher Kernels and Finite State Automata

17 0.43900904 100 nips-2002-Half-Lives of EigenFlows for Spectral Clustering

18 0.42505008 8 nips-2002-A Maximum Entropy Approach to Collaborative Filtering in Dynamic, Sparse, High-Dimensional Domains

19 0.42490411 201 nips-2002-Transductive and Inductive Methods for Approximate Gaussian Process Regression

20 0.42451105 124 nips-2002-Learning Graphical Models with Mercer Kernels

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(11, 0.028), (14, 0.016), (23, 0.034), (42, 0.132), (54, 0.185), (55, 0.041), (67, 0.021), (68, 0.022), (74, 0.166), (87, 0.01), (92, 0.038), (95, 0.105), (98, 0.126)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95646822 52 nips-2002-Cluster Kernels for Semi-Supervised Learning

Author: Olivier Chapelle, Jason Weston, Bernhard SchĂślkopf

2 0.92102867 3 nips-2002-A Convergent Form of Approximate Policy Iteration

Author: Theodore J. Perkins, Doina Precup

Abstract: We study a new, model-free form of approximate policy iteration which uses Sarsa updates with linear state-action value function approximation for policy evaluation, and a “policy improvement operator” to generate a new policy based on the learned state-action values. We prove that if the policy improvement operator produces -soft policies and is Lipschitz continuous in the action values, with a constant that is not too large, then the approximate policy iteration algorithm converges to a unique solution from any initial policy. To our knowledge, this is the ﬁrst convergence result for any form of approximate policy iteration under similar computational-resource assumptions.

3 0.91972649 127 nips-2002-Learning Sparse Topographic Representations with Products of Student-t Distributions

Author: Max Welling, Simon Osindero, Geoffrey E. Hinton

Abstract: We propose a model for natural images in which the probability of an image is proportional to the product of the probabilities of some ﬁlter outputs. We encourage the system to ﬁnd sparse features by using a Studentt distribution to model each ﬁlter output. If the t-distribution is used to model the combined outputs of sets of neurally adjacent ﬁlters, the system learns a topographic map in which the orientation, spatial frequency and location of the ﬁlters change smoothly across the map. Even though maximum likelihood learning is intractable in our model, the product form allows a relatively efﬁcient learning procedure that works well even for highly overcomplete sets of ﬁlters. Once the model has been learned it can be used as a prior to derive the “iterated Wiener ﬁlter” for the purpose of denoising images.

4 0.91877425 124 nips-2002-Learning Graphical Models with Mercer Kernels

Author: Francis R. Bach, Michael I. Jordan

Abstract: We present a class of algorithms for learning the structure of graphical models from data. The algorithms are based on a measure known as the kernel generalized variance (KGV), which essentially allows us to treat all variables on an equal footing as Gaussians in a feature space obtained from Mercer kernels. Thus we are able to learn hybrid graphs involving discrete and continuous variables of arbitrary type. We explore the computational properties of our approach, showing how to use the kernel trick to compute the relevant statistics in linear time. We illustrate our framework with experiments involving discrete and continuous data.

5 0.9155432 132 nips-2002-Learning to Detect Natural Image Boundaries Using Brightness and Texture

Author: David R. Martin, Charless C. Fowlkes, Jitendra Malik

Abstract: The goal of this work is to accurately detect and localize boundaries in natural scenes using local image measurements. We formulate features that respond to characteristic changes in brightness and texture associated with natural boundaries. In order to combine the information from these features in an optimal way, a classiﬁer is trained using human labeled images as ground truth. We present precision-recall curves showing that the resulting detector outperforms existing approaches.

6 0.91226423 169 nips-2002-Real-Time Particle Filters

7 0.91146672 53 nips-2002-Clustering with the Fisher Score

8 0.91032517 74 nips-2002-Dynamic Structure Super-Resolution

9 0.90817684 37 nips-2002-Automatic Derivation of Statistical Algorithms: The EM Family and Beyond

10 0.90518117 2 nips-2002-A Bilinear Model for Sparse Coding

11 0.90491992 175 nips-2002-Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games

12 0.90295327 68 nips-2002-Discriminative Densities from Maximum Contrast Estimation

13 0.90197468 88 nips-2002-Feature Selection and Classification on Matrix Data: From Large Margins to Small Covering Numbers

14 0.9000622 82 nips-2002-Exponential Family PCA for Belief Compression in POMDPs

15 0.89861965 188 nips-2002-Stability-Based Model Selection

16 0.8983624 122 nips-2002-Learning About Multiple Objects in Images: Factorial Learning without Factorial Search

17 0.89810514 203 nips-2002-Using Tarjan's Red Rule for Fast Dependency Tree Construction

18 0.89691627 39 nips-2002-Bayesian Image Super-Resolution

19 0.89497662 152 nips-2002-Nash Propagation for Loopy Graphical Games

20 0.89468902 21 nips-2002-Adaptive Classification by Variational Kalman Filtering