Large Scale Transductive SVMs
Published 1 December 2006Open access
Ronan Collobert, Fabian H. Sinz, Jason Weston, Léon Bottou
Citations463
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown how the concave-convex procedure can be applied to transductive SVMs, which traditionally require solving a combinatorial search problem, and provides for the first time a highly scalable algorithm in the nonlinear case.
Abstract
We show how the Concave-Convex Procedure can be applied to Transductive SVMs, which traditionally require solving a combinatorial search problem. This provides for the first time a highly scalable algorithm in the nonlinear case. Detailed experiments verify the utility of our approach. Software is available at
Keywords
Computer Science
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
The MIT Press eBooksFast Training of Support Vector Machines Using Sequential Minimal Optimization
5,462 Citations1998John Platt
MPG.PuRe (Max Planck Society)Learning with Local and Global Consistency
3,750 Citations2003Dengyong Zhou, Olivier Bousquet +3 more
A principled approach to semi-supervised learning is to design a classifying function which is sufficiently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points.
Semi-supervised learning using Gaussian fields and harmonic functions
3,377 Citations2003Xiaojin Zhu, Zoubin Ghahramani +1 more
Transductive Inference for Text Classification using Support Vector Machines
2,717 Citations1999Thorsten Joachims
An analysis of why TSVMs are well suited for text classi(cid:12)cation is presented, and an algorithm for training TSVMs e(cid:14)-ciently, handling 10,000 examples and more is proposed.
Journal of Machine Learning ResearchRCV1: A New Benchmark Collection for Text Categorization Research
2,600 Citations2004David Lewis, Yiming Yang +2 more
This work describes the coding policy and quality control procedures used in producing the RCV1 data, the intended semantics of the hierarchical category taxonomies, and the corrections necessary to remove errorful data.
Information science and statisticsEstimation of Dependences Based on Empirical Data
2,238 Citations2006Vladimir Vapnik
Lecture notes in computer scienceKernel principal component analysis
1,893 Citations1997Bernhard Schölkopf, Alexander J. Smola +1 more
A new method for performing a nonlinear form of Principal Component Analysis by the use of integral operator kernel functions is proposed and experimental results on polynomial feature extraction for pattern recognition are presented.
Neural ComputationAsymptotic Behaviors of Support Vector Machines with Gaussian Kernel
1,616 Citations2003S. Sathiya Keerthi, Chih‐Jen Lin
The behavior of the SVM classifier when these hyper parameters take very small or very large values is analyzed, which helps in understanding thehyperparameter space that leads to an efficient heuristic method of searching for hyperparameter values with small generalization errors.
Semi-Supervised Support Vector Machines
793 Citations1998Kristin P. Bennett, Ayhan Demiriz
A general S3VM model is proposed that minimizes both the misclassification error and the function capacity based on all the available data that can be converted to a mixed-integer program and then solved exactly using integer programming.
Semi-Supervised Classification by Low Density Separation
710 Citations2005Olivier Chapelle, Alexander Zien +1 more
Three semi-supervised algorithms are proposed: deriving graph-based distances that emphazise low density regions between clusters, followed by training a standard SVM, and optimizing the Transductive SVM objective function by gradient descent.
Fast Kernel Classifiers With Online And Active Learning
627 Citations2005Antoine Bordes, Şeyda Ertekin +2 more
This contribution presents an online SVM algorithm based on the premise that active example selection can yield faster training, higher accuracies, and simpler models, using only a fraction of the training example labels.
Partially labeled classification with Markov random walks
563 Citations2001Martin Szummer, Tommi Jaakkola
This work combines a limited number of labeled examples with a Markov random walk representation over the unlabeled examples and develops and compares several estimation criteria/algorithms suited to this representation.
Cluster Kernels for Semi-Supervised Learning
461 Citations2002Olivier Chapelle, Jason Weston +1 more
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 is proposed by modifying the eigenspectrum of the kernel matrix.
Maximum Margin Clustering
455 Citations2004Linli Xu, James Neufeld +2 more
A new method for clustering based on finding maximum margin hyperplanes through data that leads naturally to a semi-supervised training method for support vector machines by maximizing the margin simultaneously on labeled and unlabeled training data.
Beyond the point cloud
443 Citations2005Vikas Sindhwani, Partha Niyogi +1 more
This paper constructs a family of data-dependent norms on Reproducing Kernel Hilbert Spaces (RKHS) that allow the structure of the RKHS to reflect the underlying geometry of the data.
The Concave-Convex Procedure (CCCP)
381 Citations2001Alan Yuille, Anand Rangarajan
This work introduces the Concave-Convex procedure (CCCP) which constructs discrete time iterative dynamical systems which are guaranteed to monotonically decrease global optimization/energy functions and proves relationships to some applications of Legendre transform techniques.
Trading convexity for scalability
361 Citations2006Ronan Collobert, Fabian H. Sinz +2 more
It is shown how concave-convex programming can be applied to produce faster SVMs where training errors are no longer support vectors, and much faster Transductive SVMs.
Journal of Machine Learning ResearchA Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs
272 Citations2005S. Sathiya Keerthi, Dennis DeCoste
A fast method for solving linear SVMs with L2 loss function that is suited for large scale data mining tasks such as text classification is developed by modifying the finite Newton method of Mangasarian in several ways.
Kernel methods for missing variables
254 Citations2005Alexander J. Smola, S. V. N. Vishwanathan +1 more
An optimization scheme is proposed which extends the Concave Convex Procedure (CCP) of Yuille and Rangarajan and it is shown how the algorithm can be specialized to various cases in order to efficiently solve the optimization problems that arise.
Optimization methods & softwareSemi-superyised support vector machines for unlabeled data classification
204 Citations2001Glenn Fung, O. L. Mangasarian
Journal of the American Statistical AssociationOn ψ-Learning
191 Citations2003Xiaotong Shen, George C. Tseng +2 more
Neural Information Processing SystemsSemi-supervised Learning via Gaussian Processes
149 Citations2004Neil D. Lawrence, Michael I. Jordan
A probabilistic approach to learning a Gaussian Process classifier in the presence of unlabeled data using a "null category noise model" (NCNM) inspired by ordered categorical noise models.
Machine LearningImproved Generalization Through Explicit Optimization of Margins
131 Citations2000Llew Mason, Peter L. Bartlett +1 more
A theorem bounding the generalization performance of convex combinations in terms of general cost functions of the margin is proved, in contrast to previous results, which were stated in Terms of the particular cost function sgn(θ − margin).
Ghent University Academic Bibliography (Ghent University)Convex Methods for Transduction
114 Citations2003Tijl De Bie, Nello Cristianini
This paper presents a relaxation of the 2-class transduction problem based on semi-definite programming (SDP), resulting in a convex optimization problem that has polynomial complexity in the size of the data set.
Neural Information Processing SystemsUsing manifold structure for partially labelled classification
90 Citations2002Mikhail Belkin, Partha Niyogi
An algorithmic framework to classify a partially labeled data set in a principled manner under the assumption that the data lie on a submanifold in a high dimensional space is developed.
Leveraging the margin more carefully
83 Citations2004Nir Krause, Yoram Singer
Two leveraging algorithms that build on boosting techniques and employ a bounded loss function of the margin are described, which decomposes a non-convex loss into a difference of two convex losses.
Journal of Artificial Intelligence ResearchExplicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms
55 Citations2004Philip Derbeko, Ran El‐Yaniv +1 more
This work derives error bounds for compression schemes such as (transductive) support vector machines and for transduction algorithms based on clustering from the main observation used for deriving these new error bounds and algorithms is that the unlabeled test points in the transductive setting can be used in order to construct useful data dependent prior distributions over the hypothesis space.
The MIT Press eBooksSemi-Supervised Protein Classification Using Cluster Kernels
46 Citations2006Jason Weston, Dengyong Zhou +2 more
Bayesian Transduction
27 Citations1999Thore Graepel, Ralf Herbrich +1 more
Experimental results on real world data indicate that Bayesian Transduction compares favourably to the well-known Support Vector Machine, in particular if the posterior probability of labellings is used as a confidence measure to exclude test points of low confidence.