nips nips2002 nips2002-165 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: empty-author
Abstract: We discuss the problem of ranking k instances with the use of a
Reference: text
sentIndex sentText sentNum sentScore
1 il Abstract We discuss the problem of ranking k instances with the use of a "large margin" principle. [sent-7, score-0.379]
2 We introduce two main approaches: the first is the "fixed margin" policy in which the margin of the closest neighboring classes is being maximized - which turns out to be a direct generalization of SVM to ranking learning. [sent-8, score-1.554]
3 The second approach allows for k - 1 different margins where the sum of margins is maximized. [sent-9, score-0.572]
4 This approach is shown to reduce to lI-SVM when the number of classes k = 2. [sent-10, score-0.091]
5 Both approaches are optimal in size of 21 where I is the total number of training examples. [sent-11, score-0.065]
6 Experiments performed on visual classification and "collaborative filtering" show that both approaches outperform existing ordinal regression algorithms applied for ranking and multi-class SVM applied to general multi-class classification. [sent-12, score-0.629]
7 1 Introduction In this paper we investigate the problem of inductive learning from the point of view of predicting variables of ordinal scale [3, 7,5], a setting referred to as ranking learning or ordinal regression. [sent-13, score-0.765]
8 We consider the problem of applying the large margin principle used in Support Vector methods [12, 1] to the ordinal regression problem while maintaining an (optimal) problem size linear in the number of training examples. [sent-14, score-0.833]
9 Let x{ be the set of training examples where j = 1, . [sent-15, score-0.033]
10 Let I = 2: j ij be the total number of training examples. [sent-22, score-0.07]
11 The geometric interpretation of this approach is to look for k - 1 parallel hyperplanes represented by vector w E Rn (the dimension of the input vectors) and scalars bl :::; . [sent-24, score-0.436]
12 ~ 2 Iwl Iwl ~ Iwl maximize the m ~in f ~~ :~ ~ . [sent-33, score-0.074]
13 " (w·o) Sum-oj-margins Fixed-margin Figure 1: Lefthand display: fi xed-margin policy for ranking learning. [sent-38, score-0.609]
14 The margin to be maximized is associated with the two closest neighboring classes. [sent-39, score-0.853]
15 As in conventional SVM, the margin is prescaled to be equal to 2/lwl thus maximizing the margin is achieved by minimizing w·w. [sent-40, score-0.955]
16 The support vectors lie on the boundaries between the two closest classes. [sent-41, score-0.322]
17 The objective is to maximize the sum of k - 1 margins . [sent-43, score-0.374]
18 Each class is sandwiched between two hyperplanes, the norm of w is set to unity as a constraint in the optimization problem and as a result the objective is to maximize I:j (b j - aj). [sent-44, score-0.177]
19 In this case, the support vectors lie on the boundaries among all neighboring classes (unlike the fi xed-margin policy) . [sent-45, score-0.421]
20 When the number of classes k = 2, the dual functional is equivalent to v-SVM. [sent-46, score-0.176]
21 data are separated by dividing the space into equally ranked regions by the decision rule f (x) = min rE{l , . [sent-47, score-0.107]
22 (1) In other words, all input vectors x satisfying br - 1 < w . [sent-52, score-0.138]
23 x < br are assigned the rank r (using the convention that bk = (0). [sent-53, score-0.288]
24 For instance, recently [5] proposed an "on-line" algorithm (with similar principles to the classic "perceptron" used for 2-class separation) for finding the set of parallel hyperplanes which would comply with the separation rule above. [sent-54, score-0.345]
25 To continue the analogy to 2-class learning , in addition to the separability constraints on the variables 0: = {w, b1 :S . [sent-55, score-0.253]
26 :S bk-d one would like to control the tradeoff between lowering the "empirical risk" Remp(O:) (error measure on the training set) and lowering the "confidence interval" 1J>(0:, h) controlled by the VC-dimension h of the set of loss functions. [sent-58, score-0.255]
27 The "structural risk minimization" (SRM) principle [12] minimizes a bound on the risk over a structure on the set of functions. [sent-59, score-0.287]
28 The geometric interpretation for 2-class learning is to maximize the margin between the boundaries of the two sets [12, 1]. [sent-60, score-0.662]
29 In our setting of ranking learning, there are k - 1 margins to consider, thus there are two possible approaches to take on the "large margin" principle for ranking learning: "fixed margin" strategy: the margin to be maximized is the one defined by the closest (neighboring) pair of classes. [sent-61, score-1.918]
30 Formally, let w, bq be the hyperplane separating the two pairs of classes which are the closest among all the neighboring pairs of classes. [sent-62, score-0.651]
31 Let w , bq be scaled such the distance of the boundary points from the hyperplane is 1, i. [sent-63, score-0.22]
32 , the margin between the classes q, q + 1 is 2/lwl (see Fig. [sent-65, score-0.548]
33 Thus, the fixed margin policy for ranking learning is to find the direction wand the scalars b1 , . [sent-67, score-1.24]
34 , the margin between classes q, q + 1 is maximized) subject to the separability constraints (modulo margin errors in the non-separable case). [sent-73, score-1.255]
35 "sum of margins" strategy: the sum of all k - 1 margins are to be maximized. [sent-74, score-0.3]
36 In this case, the margins are not necessarily equal (see Fig. [sent-75, score-0.272]
37 Formally, the ranking rule employs a vector w, Iwi = 1, and a set of 2(k - 1) thresholds ai ::::; bi ::::; a2 ::::; b2 ::::; . [sent-77, score-0.495]
38 In other words, all the examples of class 1 ::::; j ::::; k are "sandwiched" between two parallel hyperplanes (w,aj) and (w, bj- t}, where bo = -00 and ak = 00. [sent-86, score-0.294]
39 The k - 1 margins are therefore (bj - aj) and the large margin principle is to maximize Lj (b j - aj) subject to the separability constraints above. [sent-87, score-1.168]
40 It is also fairly straightforward to apply the SRM principle and derive the bounds on the actual risk functional - see [11] for details. [sent-88, score-0.239]
41 In the remainder of this paper we will introduce the algorithmic implications of these two strategies for implementing the large margin principle for ranking learning. [sent-89, score-0.979]
42 The fixedmargin principle will turn out to be a direct generalization of the Support Vector Machine (SYM) algorithm - in the sense that substituting k = 2 in our proposed algorithm would produce the dual functional underlying conventional SVM. [sent-90, score-0.299]
43 1t is interesting to note that the sum-of-margins principle reduces to v-SVM (introduced by [10] and later [2]) when k = 2. [sent-91, score-0.144]
44 2 Fixed Margin Strategy Recall that in the fixed margin policy (w, bq ) is a "canonical" hyperplane normalized such that the margin between the closest classes q, q + 1 is 2/llwll. [sent-92, score-1.652]
45 ::::; bk - i (and the index q) could be solved in a two-stage optimization problem: a Quadratic Linear Programming (QLP) formulation followed by a Linear Programming (LP) formulation. [sent-97, score-0.22]
46 The (primal) QLP formulation of the ("soft margin") fixed-margin policy for ranking learning takes the form: ~w . [sent-98, score-0.58]
47 The scalars c:{ and are positive for data points which are inside the margins or placed on the wrong side of the respective hyperplane. [sent-108, score-0.403]
wordName wordTfidf (topN-words)
[('margin', 0.457), ('ranking', 0.379), ('margins', 0.272), ('separability', 0.19), ('hyperplanes', 0.181), ('ordinal', 0.179), ('policy', 0.173), ('closest', 0.161), ('iwl', 0.154), ('bk', 0.152), ('maximized', 0.123), ('aj', 0.117), ('jerusalem', 0.117), ('principle', 0.115), ('neighboring', 0.112), ('hyperplane', 0.112), ('bq', 0.108), ('br', 0.108), ('display', 0.107), ('lefthand', 0.103), ('qlp', 0.103), ('sandwiched', 0.103), ('scalars', 0.102), ('fixed', 0.093), ('classes', 0.091), ('righthand', 0.089), ('shashua', 0.089), ('risk', 0.086), ('modulo', 0.082), ('lowering', 0.082), ('srm', 0.076), ('maximize', 0.074), ('email', 0.072), ('bj', 0.068), ('separating', 0.067), ('boundaries', 0.061), ('tradeoff', 0.058), ('hebrew', 0.058), ('fi', 0.057), ('israel', 0.053), ('svm', 0.05), ('maintaining', 0.049), ('parallel', 0.049), ('rule', 0.048), ('dual', 0.047), ('predefined', 0.045), ('anat', 0.045), ('strategy', 0.045), ('bi', 0.041), ('conventional', 0.041), ('confidence', 0.041), ('levin', 0.041), ('origins', 0.041), ('geometric', 0.041), ('index', 0.04), ('school', 0.04), ('classification', 0.039), ('cease', 0.038), ('lie', 0.038), ('functional', 0.038), ('separation', 0.037), ('programming', 0.037), ('ij', 0.037), ('formally', 0.036), ('collaborative', 0.036), ('bd', 0.036), ('wand', 0.036), ('primal', 0.034), ('ranks', 0.034), ('bo', 0.034), ('lj', 0.034), ('bl', 0.034), ('training', 0.033), ('support', 0.032), ('constraints', 0.032), ('approaches', 0.032), ('governed', 0.031), ('continue', 0.031), ('ranked', 0.031), ('perceptron', 0.031), ('defining', 0.031), ('generalization', 0.031), ('classic', 0.03), ('ak', 0.03), ('vectors', 0.03), ('later', 0.029), ('wrong', 0.029), ('interpretation', 0.029), ('sum', 0.028), ('implications', 0.028), ('lp', 0.028), ('inductive', 0.028), ('dividing', 0.028), ('convention', 0.028), ('formulation', 0.028), ('subject', 0.028), ('canonical', 0.027), ('thresholds', 0.027), ('filtering', 0.027), ('direct', 0.027)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999982 165 nips-2002-Ranking with Large Margin Principle: Two Approaches
Author: empty-author
Abstract: We discuss the problem of ranking k instances with the use of a
2 0.22251518 19 nips-2002-Adapting Codes and Embeddings for Polychotomies
Author: Gunnar Rätsch, Sebastian Mika, Alex J. Smola
Abstract: In this paper we consider formulations of multi-class problems based on a generalized notion of a margin and using output coding. This includes, but is not restricted to, standard multi-class SVM formulations. Differently from many previous approaches we learn the code as well as the embedding function. We illustrate how this can lead to a formulation that allows for solving a wider range of problems with for instance many classes or even “missing classes”. To keep our optimization problems tractable we propose an algorithm capable of solving them using twoclass classifiers, similar in spirit to Boosting.
3 0.22042269 140 nips-2002-Margin Analysis of the LVQ Algorithm
Author: Koby Crammer, Ran Gilad-bachrach, Amir Navot, Naftali Tishby
Abstract: Prototypes based algorithms are commonly used to reduce the computational complexity of Nearest-Neighbour (NN) classifiers. In this paper we discuss theoretical and algorithmical aspects of such algorithms. On the theory side, we present margin based generalization bounds that suggest that these kinds of classifiers can be more accurate then the 1-NN rule. Furthermore, we derived a training algorithm that selects a good set of prototypes using large margin principles. We also show that the 20 years old Learning Vector Quantization (LVQ) algorithm emerges naturally from our framework. 1
4 0.20015423 161 nips-2002-PAC-Bayes & Margins
Author: John Langford, John Shawe-Taylor
Abstract: unkown-abstract
5 0.1778371 58 nips-2002-Conditional Models on the Ranking Poset
Author: Guy Lebanon, John D. Lafferty
Abstract: A distance-based conditional model on the ranking poset is presented for use in classification and ranking. The model is an extension of the Mallows model, and generalizes the classifier combination methods used by several ensemble learning algorithms, including error correcting output codes, discrete AdaBoost, logistic regression and cranking. The algebraic structure of the ranking poset leads to a simple Bayesian interpretation of the conditional model and its special cases. In addition to a unifying view, the framework suggests a probabilistic interpretation for error correcting output codes and an extension beyond the binary coding scheme.
6 0.13967466 151 nips-2002-Multiplicative Updates for Nonnegative Quadratic Programming in Support Vector Machines
7 0.12534407 3 nips-2002-A Convergent Form of Approximate Policy Iteration
8 0.12418983 156 nips-2002-On the Complexity of Learning the Kernel Matrix
9 0.12222175 130 nips-2002-Learning in Zero-Sum Team Markov Games Using Factored Value Functions
10 0.10413905 88 nips-2002-Feature Selection and Classification on Matrix Data: From Large Margins to Small Covering Numbers
11 0.081867814 155 nips-2002-Nonparametric Representation of Policies and Value Functions: A Trajectory-Based Approach
12 0.075644612 93 nips-2002-Forward-Decoding Kernel-Based Phone Recognition
13 0.074728414 59 nips-2002-Constraint Classification for Multiclass Classification and Ranking
14 0.073861338 33 nips-2002-Approximate Linear Programming for Average-Cost Dynamic Programming
15 0.072545648 121 nips-2002-Knowledge-Based Support Vector Machine Classifiers
16 0.07187824 159 nips-2002-Optimality of Reinforcement Learning Algorithms with Linear Function Approximation
17 0.068775892 69 nips-2002-Discriminative Learning for Label Sequences via Boosting
18 0.06850443 20 nips-2002-Adaptive Caching by Refetching
19 0.066501446 45 nips-2002-Boosted Dyadic Kernel Discriminants
20 0.06406562 24 nips-2002-Adaptive Scaling for Feature Selection in SVMs
topicId topicWeight
[(0, -0.171), (1, -0.117), (2, -0.09), (3, -0.122), (4, 0.194), (5, -0.106), (6, 0.048), (7, -0.074), (8, -0.009), (9, -0.042), (10, 0.038), (11, -0.183), (12, -0.127), (13, -0.248), (14, -0.047), (15, 0.071), (16, 0.152), (17, -0.02), (18, 0.063), (19, 0.045), (20, -0.015), (21, -0.16), (22, 0.1), (23, 0.062), (24, -0.127), (25, -0.026), (26, 0.152), (27, 0.102), (28, 0.019), (29, -0.023), (30, 0.057), (31, -0.12), (32, -0.126), (33, 0.062), (34, 0.137), (35, 0.08), (36, -0.035), (37, -0.021), (38, 0.081), (39, -0.067), (40, 0.192), (41, 0.076), (42, 0.048), (43, -0.033), (44, -0.155), (45, 0.032), (46, 0.006), (47, -0.046), (48, -0.032), (49, 0.058)]
simIndex simValue paperId paperTitle
same-paper 1 0.98138428 165 nips-2002-Ranking with Large Margin Principle: Two Approaches
Author: empty-author
Abstract: We discuss the problem of ranking k instances with the use of a
2 0.66889966 140 nips-2002-Margin Analysis of the LVQ Algorithm
Author: Koby Crammer, Ran Gilad-bachrach, Amir Navot, Naftali Tishby
Abstract: Prototypes based algorithms are commonly used to reduce the computational complexity of Nearest-Neighbour (NN) classifiers. In this paper we discuss theoretical and algorithmical aspects of such algorithms. On the theory side, we present margin based generalization bounds that suggest that these kinds of classifiers can be more accurate then the 1-NN rule. Furthermore, we derived a training algorithm that selects a good set of prototypes using large margin principles. We also show that the 20 years old Learning Vector Quantization (LVQ) algorithm emerges naturally from our framework. 1
3 0.65434068 161 nips-2002-PAC-Bayes & Margins
Author: John Langford, John Shawe-Taylor
Abstract: unkown-abstract
4 0.52401727 151 nips-2002-Multiplicative Updates for Nonnegative Quadratic Programming in Support Vector Machines
Author: Fei Sha, Lawrence K. Saul, Daniel D. Lee
Abstract: We derive multiplicative updates for solving the nonnegative quadratic programming problem in support vector machines (SVMs). The updates have a simple closed form, and we prove that they converge monotonically to the solution of the maximum margin hyperplane. The updates optimize the traditionally proposed objective function for SVMs. They do not involve any heuristics such as choosing a learning rate or deciding which variables to update at each iteration. They can be used to adjust all the quadratic programming variables in parallel with a guarantee of improvement at each iteration. We analyze the asymptotic convergence of the updates and show that the coefficients of non-support vectors decay geometrically to zero at a rate that depends on their margins. In practice, the updates converge very rapidly to good classifiers.
5 0.48781803 19 nips-2002-Adapting Codes and Embeddings for Polychotomies
Author: Gunnar Rätsch, Sebastian Mika, Alex J. Smola
Abstract: In this paper we consider formulations of multi-class problems based on a generalized notion of a margin and using output coding. This includes, but is not restricted to, standard multi-class SVM formulations. Differently from many previous approaches we learn the code as well as the embedding function. We illustrate how this can lead to a formulation that allows for solving a wider range of problems with for instance many classes or even “missing classes”. To keep our optimization problems tractable we propose an algorithm capable of solving them using twoclass classifiers, similar in spirit to Boosting.
6 0.45690909 58 nips-2002-Conditional Models on the Ranking Poset
7 0.39586747 121 nips-2002-Knowledge-Based Support Vector Machine Classifiers
8 0.38909253 130 nips-2002-Learning in Zero-Sum Team Markov Games Using Factored Value Functions
9 0.33374974 3 nips-2002-A Convergent Form of Approximate Policy Iteration
10 0.33045885 20 nips-2002-Adaptive Caching by Refetching
11 0.32387871 33 nips-2002-Approximate Linear Programming for Average-Cost Dynamic Programming
12 0.28866118 156 nips-2002-On the Complexity of Learning the Kernel Matrix
13 0.27156377 93 nips-2002-Forward-Decoding Kernel-Based Phone Recognition
14 0.23640496 149 nips-2002-Multiclass Learning by Probabilistic Embeddings
15 0.23497848 178 nips-2002-Robust Novelty Detection with Single-Class MPM
16 0.22297691 24 nips-2002-Adaptive Scaling for Feature Selection in SVMs
17 0.22242722 134 nips-2002-Learning to Take Concurrent Actions
18 0.21262278 158 nips-2002-One-Class LP Classifiers for Dissimilarity Representations
19 0.21204671 111 nips-2002-Independent Components Analysis through Product Density Estimation
20 0.21158293 59 nips-2002-Constraint Classification for Multiclass Classification and Ranking
topicId topicWeight
[(3, 0.465), (42, 0.052), (54, 0.118), (55, 0.046), (68, 0.013), (73, 0.011), (74, 0.048), (92, 0.067), (98, 0.076)]
simIndex simValue paperId paperTitle
same-paper 1 0.80915356 165 nips-2002-Ranking with Large Margin Principle: Two Approaches
Author: empty-author
Abstract: We discuss the problem of ranking k instances with the use of a
2 0.77818143 154 nips-2002-Neuromorphic Bisable VLSI Synapses with Spike-Timing-Dependent Plasticity
Author: Giacomo Indiveri
Abstract: We present analog neuromorphic circuits for implementing bistable synapses with spike-timing-dependent plasticity (STDP) properties. In these types of synapses, the short-term dynamics of the synaptic efficacies are governed by the relative timing of the pre- and post-synaptic spikes, while on long time scales the efficacies tend asymptotically to either a potentiated state or to a depressed one. We fabricated a prototype VLSI chip containing a network of integrate and fire neurons interconnected via bistable STDP synapses. Test results from this chip demonstrate the synapse’s STDP learning properties, and its long-term bistable characteristics.
3 0.74351537 133 nips-2002-Learning to Perceive Transparency from the Statistics of Natural Scenes
Author: Anat Levin, Assaf Zomet, Yair Weiss
Abstract: Certain simple images are known to trigger a percept of transparency: the input image I is perceived as the sum of two images I(x, y) = I1 (x, y) + I2 (x, y). This percept is puzzling. First, why do we choose the “more complicated” description with two images rather than the “simpler” explanation I(x, y) = I1 (x, y) + 0 ? Second, given the infinite number of ways to express I as a sum of two images, how do we compute the “best” decomposition ? Here we suggest that transparency is the rational percept of a system that is adapted to the statistics of natural scenes. We present a probabilistic model of images based on the qualitative statistics of derivative filters and “corner detectors” in natural scenes and use this model to find the most probable decomposition of a novel image. The optimization is performed using loopy belief propagation. We show that our model computes perceptually “correct” decompositions on synthetic images and discuss its application to real images. 1
4 0.52563351 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 efficient 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 fixed 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 classification, regression, ranking, and principle component analysis. The most prominent learning algorithm that employs kernels is the Support Vector Machines (SVM) [1, 2] designed for classification 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 predefined kernel. A typical approach when using kernels is to choose a kernel before learning starts. Examples to popular predefined 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 specific tasks such as text categorization [3] and protein classification problems [4]. Our work attempts to give a computational alternative to predefined kernels by learning kernel operators from data. We start with a few definitions. 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 finite 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 specific 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 find a weighted combination of kernels ˆ K(x, x ) = j αj Kj (x, x ) that is similar, in a sense that will be defined 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 definition, they defined 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 finite 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 “flattened” into a vector of dimension m2 . Therefore, this definition 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 suffices to construct an excellent classifier 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 find 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 classifier whose empirical loss is zero. Furthermore, the task of finding a good kernel when it is not always possible to find 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 difficulties 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 first 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 classification error (see for instance [9, 7] and the references therein). A recent work by Collins et al. [8] unifies 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 classification error. Given the prediction of a classifier f on an instance x and a label y ∈ {−1, +1} the ExpLoss and the LogLoss are defined 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 classifier f (x). This classifier is a weighted combination of (possibly very simple) base classifiers. (In the boosting framework, the base classifiers 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 find a good of weights αt . Our starting point in this paper is the first sequential algorithm from [8] that enables the construction or creation of weak-hypotheses on-the-fly. 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 reflects how difficult 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 classification 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 unspecified. 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 define the family of base kernels to be the possible outer-products Kw = wwT between a vector w ∈ n and itself. Using this definition 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 specific 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 define 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 fits 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 efficiently 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 define 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 finding 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 semidefinite. 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 finding 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 efficiently. 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 first 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 first 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 (first and third from left) and after learning (second and fourth). For each of the two settings we show the first 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 first 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 classifier 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 classifier 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 figure 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 first two features. In all plots, each bar indicates a 95% confidence level. It is clear from the figure 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 reflects better the structure of the feature space which makes the learned kernel more robust to noise. Fig. 3 further illustrates the benefits of using a boutique kernel. The first 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 first 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 first 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 first 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 classification 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 classifiers 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 classification 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 first ˜ 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 significant 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 classifiers 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 classification 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 classification. In Proceedings of the Pacific 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-definite 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 Classifiers. 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.
5 0.38332635 140 nips-2002-Margin Analysis of the LVQ Algorithm
Author: Koby Crammer, Ran Gilad-bachrach, Amir Navot, Naftali Tishby
Abstract: Prototypes based algorithms are commonly used to reduce the computational complexity of Nearest-Neighbour (NN) classifiers. In this paper we discuss theoretical and algorithmical aspects of such algorithms. On the theory side, we present margin based generalization bounds that suggest that these kinds of classifiers can be more accurate then the 1-NN rule. Furthermore, we derived a training algorithm that selects a good set of prototypes using large margin principles. We also show that the 20 years old Learning Vector Quantization (LVQ) algorithm emerges naturally from our framework. 1
6 0.36999914 149 nips-2002-Multiclass Learning by Probabilistic Embeddings
7 0.36320263 45 nips-2002-Boosted Dyadic Kernel Discriminants
8 0.35383245 156 nips-2002-On the Complexity of Learning the Kernel Matrix
9 0.35333157 193 nips-2002-Temporal Coherence, Natural Image Sequences, and the Visual Cortex
10 0.35002321 42 nips-2002-Bias-Optimal Incremental Problem Solving
11 0.34833008 177 nips-2002-Retinal Processing Emulation in a Programmable 2-Layer Analog Array Processor CMOS Chip
12 0.34790877 37 nips-2002-Automatic Derivation of Statistical Algorithms: The EM Family and Beyond
13 0.34679449 74 nips-2002-Dynamic Structure Super-Resolution
14 0.3417176 186 nips-2002-Spike Timing-Dependent Plasticity in the Address Domain
15 0.3401947 21 nips-2002-Adaptive Classification by Variational Kalman Filtering
16 0.33974111 53 nips-2002-Clustering with the Fisher Score
17 0.33962798 27 nips-2002-An Impossibility Theorem for Clustering
18 0.33960125 68 nips-2002-Discriminative Densities from Maximum Contrast Estimation
19 0.33874768 88 nips-2002-Feature Selection and Classification on Matrix Data: From Large Margins to Small Covering Numbers
20 0.33853114 106 nips-2002-Hyperkernels