Vladimir Vapnik

JMLR Journal 2016 Journal Article

Synergy of Monotonic Rules

• Vladimir Vapnik
• Rauf Izmailov

This article describes a method for constructing a special rule (we call it synergy rule) that uses as its input information the outputs (scores) of several monotonic rules which solve the same pattern recognition problem. As an example of scores of such monotonic rules we consider here scores of SVM classifiers. In order to construct the optimal synergy rule, we estimate the conditional probability function based on the direct problem setting, which requires solving a Fredholm integral equation. Generally, solving a Fredholm equation is an ill-posed problem. However, in our model, we look for the solution of the equation in the set of monotonic and bounded functions, which makes the problem well-posed. This allows us to solve the equation accurately even with training data sets of limited size. In order to construct a monotonic solution, we use the set of functions that belong to Reproducing Kernel Hilbert Space (RKHS) associated with the INK-spline kernel (splines with Infinite Numbers of Knots) of degree zero. The paper provides details of the methods for finding multidimensional conditional probability in a set of monotonic functions to obtain the corresponding synergy rules. We demonstrate effectiveness of such rules for 1) solving standard pattern recognition problems, 2) constructing multi-class classification rules, 3) constructing a method for knowledge transfer from multiple intelligent teachers in the LUPI paradigm. [abs] [ pdf ][ bib ] &copy JMLR 2016. ( edit, beta )

JMLR Journal 2015 Journal Article

Learning Using Privileged Information: Similarity Control and Knowledge Transfer

• Vladimir Vapnik
• Rauf Izmailov

This paper describes a new paradigm of machine learning, in which Intelligent Teacher is involved. During training stage, Intelligent Teacher provides Student with information that contains, along with classification of each example, additional privileged information (for example, explanation) of this example. The paper describes two mechanisms that can be used for significantly accelerating the speed of Student's learning using privileged information: (1) correction of Student's concepts of similarity between examples, and (2) direct Teacher-Student knowledge transfer. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

JMLR Journal 2015 Journal Article

V-Matrix Method of Solving Statistical Inference Problems

• Vladimir Vapnik
• Rauf Izmailov

This paper presents direct settings and rigorous solutions of the main Statistical Inference problems. It shows that rigorous solutions require solving multidimensional Fredholm integral equations of the first kind in the situation where not only the right-hand side of the equation is an approximation, but the operator in the equation is also defined approximately. Using Stefanuyk-Vapnik theory for solving such ill-posed operator equations, constructive methods of empirical inference are introduced. These methods are based on a new concept called $V$-matrix. This matrix captures geometric properties of the observation data that are ignored by classical statistical methods. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

YNIMG Journal 2011 Journal Article

Machine learning classification with confidence: Application of transductive conformal predictors to MRI-based diagnostic and prognostic markers in depression

• Ilia Nouretdinov
• Sergi G. Costafreda
• Alexander Gammerman
• Alexey Chervonenkis
• Vladimir Vovk
• Vladimir Vapnik
• Cynthia H.Y. Fu

There is rapidly accumulating evidence that the application of machine learning classification to neuroimaging measurements may be valuable for the development of diagnostic and prognostic prediction tools in psychiatry. However, current methods do not produce a measure of the reliability of the predictions. Knowing the risk of the error associated with a given prediction is essential for the development of neuroimaging-based clinical tools. We propose a general probabilistic classification method to produce measures of confidence for magnetic resonance imaging (MRI) data. We describe the application of transductive conformal predictor (TCP) to MRI images. TCP generates the most likely prediction and a valid measure of confidence, as well as the set of all possible predictions for a given confidence level. We present the theoretical motivation for TCP, and we have applied TCP to structural and functional MRI data in patients and healthy controls to investigate diagnostic and prognostic prediction in depression. We verify that TCP predictions are as accurate as those obtained with more standard machine learning methods, such as support vector machine, while providing the additional benefit of a valid measure of confidence for each prediction.

NeurIPS Conference 2010 Conference Paper

On the Theory of Learnining with Privileged Information

• Dmitry Pechyony
• Vladimir Vapnik

In Learning Using Privileged Information (LUPI) paradigm, along with the standard training data in the decision space, a teacher supplies a learner with the privileged information in the correcting space. The goal of the learner is to find a classifier with a low generalization error in the decision space. We consider a new version of empirical risk minimization algorithm, called Privileged ERM, that takes into account the privileged information in order to find a good function in the decision space. We outline the conditions on the correcting space that, if satisfied, allow Privileged ERM to have much faster learning rate in the decision space than the one of the regular empirical risk minimization.

ICML Conference 2006 Conference Paper

Inference with the Universum

• Jason Weston
• Ronan Collobert
• Fabian H. Sinz
• Léon Bottou
• Vladimir Vapnik

NeurIPS Conference 2004 Conference Paper

Parallel Support Vector Machines: The Cascade SVM

• Hans Graf
• Eric Cosatto
• Léon Bottou
• Igor Dourdanovic
• Vladimir Vapnik

We describe an algorithm for support vector machines (SVM) that can be parallelized efficiently and scales to very large problems with hundreds of thousands of training vectors. Instead of analyzing the whole training set in one optimization step, the data are split into subsets and optimized separately with multiple SVMs. The partial results are combined and filtered again in a ‘Cascade’ of SVMs, until the global optimum is reached. The Cascade SVM can be spread over multiple processors with minimal communication overhead and requires far less memory, since the kernel matrices are much smaller than for a regular SVM. Convergence to the global optimum is guaranteed with multiple passes through the Cascade, but already a single pass provides good generalization. A single pass is 5x – 10x faster than a regular SVM for problems of 100, 000 vectors when implemented on a single processor. Parallel implementations on a cluster of 16 processors were tested with over 1 million vectors (2-class problems), converging in a day or two, while a regular SVM never converged in over a week.

NeurIPS Conference 2002 Conference Paper

Kernel Dependency Estimation

• Jason Weston
• Olivier Chapelle
• Vladimir Vapnik
• André Elisseeff
• Bernhard Schölkopf

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 ker(cid: 173) nel 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 par(cid: 173) tial images.

JMLR Journal 2001 Journal Article

Support Vector Clustering (Kernel Machines Section)

• Asa Ben-Hur
• David Horn
• Hava T. Siegelmann
• Vladimir Vapnik

We present a novel clustering method using the approach of support vector machines. Data points are mapped by means of a Gaussian kernel to a high dimensional feature space, where we search for the minimal enclosing sphere. This sphere, when mapped back to data space, can separate into several components, each enclosing a separate cluster of points. We present a simple algorithm for identifying these clusters. The width of the Gaussian kernel controls the scale at which the data is probed while the soft margin constant helps coping with outliers and overlapping clusters. The structure of a dataset is explored by varying the two parameters, maintaining a minimal number of support vectors to assure smooth cluster boundaries. We demonstrate the performance of our algorithm on several datasets.

NeurIPS Conference 2000 Conference Paper

A Support Vector Method for Clustering

• Asa Ben-Hur
• David Horn
• Hava Siegelmann
• Vladimir Vapnik

We present a novel method for clustering using the support vector ma(cid: 173) chine approach. Data points are mapped to a high dimensional feature space, where support vectors are used to define a sphere enclosing them. The boundary of the sphere forms in data space a set of closed contours containing the data. Data points enclosed by each contour are defined as a cluster. As the width parameter of the Gaussian kernel is decreased, these contours fit the data more tightly and splitting of contours occurs. The algorithm works by separating clusters according to valleys in the un(cid: 173) derlying probability distribution, and thus clusters can take on arbitrary geometrical shapes. As in other SV algorithms, outliers can be dealt with by introducing a soft margin constant leading to smoother cluster bound(cid: 173) aries. The structure of the data is explored by varying the two parame(cid: 173) ters. We investigate the dependence of our method on these parameters and apply it to several data sets.

NeurIPS Conference 2000 Conference Paper

Feature Selection for SVMs

• Jason Weston
• Sayan Mukherjee
• Olivier Chapelle
• Massimiliano Pontil
• Tomaso Poggio
• Vladimir Vapnik

We introduce a method of feature selection for Support Vector Machines. The method is based upon finding those features which minimize bounds on the leave-one-out error. This search can be efficiently performed via gradient descent. The resulting algorithms are shown to be superior to some standard feature selection algorithms on both toy data and real-life problems of face recognition, pedestrian detection and analyzing DNA micro array data.

NeurIPS Conference 2000 Conference Paper

Vicinal Risk Minimization

• Olivier Chapelle
• Jason Weston
• Léon Bottou
• Vladimir Vapnik

The Vicinal Risk Minimization principle establishes a bridge between generative models and methods derived from the Structural Risk Mini(cid: 173) mization Principle such as Support Vector Machines or Statistical Reg(cid: 173) ularization. We explain how VRM provides a framework which inte(cid: 173) grates a number of existing algorithms, such as Parzen windows, Support Vector Machines, Ridge Regression, Constrained Logistic Classifiers and Tangent-Prop. We then show how the approach implies new algorithm(cid: 173) s for solving problems usually associated with generative models. New algorithms are described for dealing with pattern recognition problems with very different pattern distributions and dealing with unlabeled data. Preliminary empirical results are presented.

NeurIPS Conference 1999 Conference Paper

Model Selection for Support Vector Machines

• Olivier Chapelle
• Vladimir Vapnik

New functionals for parameter (model) selection of Support Vector Ma(cid: 173) chines are introduced based on the concepts of the span of support vec(cid: 173) tors and rescaling of the feature space. It is shown that using these func(cid: 173) tionals, one can both predict the best choice of parameters of the model and the relative quality of performance for any value of parameter.

NeurIPS Conference 1999 Conference Paper

Support Vector Method for Multivariate Density Estimation

• Vladimir Vapnik
• Sayan Mukherjee

A new method for multivariate density estimation is developed based on the Support Vector Method (SVM) solution of inverse ill-posed problems. The solution has the form of a mixture of den(cid: 173) sities. This method with Gaussian kernels compared favorably to both Parzen's method and the Gaussian Mixture Model method. For synthetic data we achieve more accurate estimates for densities of 2, 6, 12, and 40 dimensions.

NeurIPS Conference 1999 Conference Paper

Transductive Inference for Estimating Values of Functions

• Olivier Chapelle
• Vladimir Vapnik
• Jason Weston

We introduce an algorithm for estimating the values of a function at a set of test points Xe+! ,. .. , xl+m given a set of training points (XI, YI), .. ., (xe, Ye) without estimating (as an intermediate step) the regression function. We demonstrate that this direct (transduc(cid: 173) ti ve) way for estimating values of the regression (or classification in pattern recognition) can be more accurate than the tradition(cid: 173) alone based on two steps, first estimating the function and then calculating the values of this function at the points of interest.

UAI Conference 1998 Conference Paper

Learning by Transduction

• Alex Gammerman
• Vladimir Vovk
• Vladimir Vapnik

We describe a method for predicting a classification of an object given classifications of the objects in the training set, assuming that the pairs object/classification are generated by an i.i.d. process from a continuous probability distribution. Our method is a modification of Vapnik's support-vector machine; its main novelty is that it gives not only the prediction itself but also a practicable measure of the evidence found in support of that prediction. We also describe a procedure for assigning degrees of confidence to predictions made by the support vector machine. Some experimental results are presented, and possible extensions of the algorithms are discussed.

NeurIPS Conference 1997 Conference Paper

Prior Knowledge in Support Vector Kernels

• Bernhard Schölkopf
• Patrice Simard
• Alex Smola
• Vladimir Vapnik

We explore methods for incorporating prior knowledge about a problem at hand in Support Vector learning machines. We show that both invari(cid: 173) ances under group transfonnations and prior knowledge about locality in images can be incorporated by constructing appropriate kernel functions.

ICML Conference 1996 Invited Paper

Statistical Theory of Generalization (Abstract)

• Vladimir Vapnik

NeurIPS Conference 1996 Conference Paper

Support Vector Method for Function Approximation, Regression Estimation and Signal Processing

• Vladimir Vapnik
• Steven Golowich
• Alex Smola

The Support Vector (SV) method was recently proposed for es(cid: 173) timating regressions, constructing multidimensional splines, and solving linear operator equations [Vapnik, 1995]. In this presenta(cid: 173) tion we report results of applying the SV method to these problems.

NeurIPS Conference 1996 Conference Paper

Support Vector Regression Machines

• Harris Drucker
• Christopher Burges
• Linda Kaufman
• Alex Smola
• Vladimir Vapnik

A new regression technique based on Vapnik's concept of support vectors is introduced. We compare support vector regression (SVR) with a committee regression technique (bagging) based on regression trees and ridge regression done in feature space. On the basis of these experiments, it is expected that SVR will have advantages in high dimensionality space because SVR optimization does not depend on the dimensionality of the input space.

ICML Conference 1994 Conference Paper

Boosting and Other Machine Learning Algorithms

• Harris Drucker
• Corinna Cortes
• Larry D. Jackel
• Yann LeCun
• Vladimir Vapnik

NeurIPS Conference 1993 Conference Paper

Learning Curves: Asymptotic Values and Rate of Convergence

• Corinna Cortes
• L. Jackel
• Sara Solla
• Vladimir Vapnik
• John Denker

Training classifiers on large databases is computationally demand(cid: 173) ing. It is desirable to develop efficient procedures for a reliable prediction of a classifier's suitability for implementing a given task, so that resources can be assigned to the most promising candidates or freed for exploring new classifier candidates. We propose such a practical and principled predictive method. Practical because it avoids the costly procedure of training poor classifiers on the whole training set, and principled because of its theoretical foundation. The effectiveness of the proposed procedure is demonstrated for both single- and multi-layer networks. 1