Maximum margin classifiers such as Support Vector Machines (SVMs) critically depends upon the convex hulls of the training samples of each class, as they implicitly search for the minimum distance between the convex hulls. We propose Extrapolated Vec(cid:173) tor Machines (XVMs) which rely on extrapolations outside these convex hulls. XVMs improve SVM generalization very significantly on the MNIST [7] OCR data. They share similarities with the Fisher discriminant: maximize the inter-class margin while mini(cid:173) mizing the intra-class disparity.

The choice of an SVM kernel corresponds to the choice of a rep(cid:173) resentation of the data in a feature space and, to improve per(cid:173) formance, it should therefore incorporate prior knowledge such as known transformation invariances. We propose a technique which extends earlier work and aims at incorporating invariances in non(cid:173) linear kernels. We show on a digit recognition task that the pro(cid:173) posed approach is superior to the Virtual Support Vector method, which previously had been the method of choice.

Spontaneous facial expressions differ substan- tially from posed expressions, similar to how continuous, spontaneous speech differs from isolated words produced on command. Previous methods for automatic facial expression recognition assumed images were collected in controlled environments in which the subjects delib- erately faced the camera. Since people often nod or turn their heads, automatic recognition of spontaneous facial behavior requires methods for handling out-of-image-plane head rotations. Here we explore an ap- proach based on 3-D warping of images into canonical views. We eval- uated the performance of the approach as a front-end for a spontaneous expression recognition system using support vector machines and hidden Markov models.

This paper introduces an algorithm for the automatic relevance determi- nation of input variables in kernelized Support Vector Machines. Rele- vance is measured by scale factors defining the input space metric, and feature selection is performed by assigning zero weights to irrelevant variables. The metric is automatically tuned by the minimization of the standard SVM empirical risk, where scale factors are added to the usual set of parameters defining the classifier. Feature selection is achieved by constraints encouraging the sparsity of scale factors. The resulting algorithm compares favorably to state-of-the-art feature selection proce- dures and demonstrates its effectiveness on a demanding facial expres- sion recognition problem.

We introduce a family of classiflers based on a physical analogy to an electrostatic system of charged conductors. The family, called Coulomb classiflers, includes the two best-known support-vector machines (SVMs), the "{SVM and the C{SVM. In the electrostat- ics analogy, a training example corresponds to a charged conductor at a given location in space, the classiflcation function corresponds to the electrostatic potential function, and the training objective function corresponds to the Coulomb energy. The electrostatic framework provides not only a novel interpretation of existing algo- rithms and their interrelationships, but it suggests a variety of new methods for SVMs including kernels that bridge the gap between polynomial and radial-basis functions, objective functions that do not require positive-deflnite kernels, regularization techniques that allow for the construction of an optimal classifler in Minkowski space. Based on the framework, we propose novel SVMs and per- form simulation studies to show that they are comparable or su- perior to standard SVMs.

We introduce a general family of kernels based on weighted transduc- ers or rational relations, rational kernels, that can be used for analysis of variable-length sequences or more generally weighted automata, in appli- cations such as computational biology or speech recognition. We show that rational kernels can be computed efficiently using a general algo- rithm of composition of weighted transducers and a general single-source shortest-distance algorithm. We also describe several general families of positive definite symmetric rational kernels. These general kernels can be combined with Support Vector Machines to form efficient and power- ful techniques for spoken-dialog classification: highly complex kernels become easy to design and implement and lead to substantial improve- ments in the classification accuracy. We also show that the string kernels considered in applications to computational biology are all specific in- stances of rational kernels.

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 monotoni- cally 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 im- provement at each iteration.

We present a framework for sparse Gaussian process (GP) methods which uses forward selection with criteria based on information- theoretic principles, previously suggested for active learning. Our goal is not only to learn d{sparse predictors (which can be evalu- ated in O(d) rather than O(n), d (cid:28) n, n the number of training points), but also to perform training under strong restrictions on time and memory requirements. The scaling of our method is at most O(n (cid:1) d2), and in large real-world classi(cid:12)cation experiments we show that it can match prediction performance of the popular support vector machine (SVM), yet can be signi(cid:12)cantly faster in training. In contrast to the SVM, our approximation produces esti- mates of predictive probabilities ('error bars'), allows for Bayesian model selection and is less complex in implementation.

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 defining a Reproducing Ker- nel 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.

We introduce a new learning algorithm for decision lists to allow features that are constructed from the data and to allow a trade- ofi between accuracy and complexity. We bound its generalization error in terms of the number of errors and the size of the classifler it flnds on the training data. We also compare its performance on some natural data sets with the set covering machine and the support vector machine.