Branch and Bound for Semi-Supervised Support Vector Machines
The MIT Press eBooksPublished 7 September 2007
Olivier Chapelle, Vikas Sindhwani, S. Sathiya Keerthi
Citations129
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
Empirical evidence suggests that the globally optimal solution of S3VMs modulo local minima problems in current implementations can return excellent generalization performance in situations where other implementations fail completely.
Abstract
Semi-supervised SVMs (S 3 VM) attempt to learn low-density separators by maximizing the margin over labeled and unlabeled examples.The associated optimization problem is non-convex.To examine the full potential of S 3 VMs modulo local minima problems in current implementations, we apply branch and bound techniques for obtaining exact, globally optimal solutions.Empirical evidence suggests that the globally optimal solution can return excellent generalization performance in situations where other implementations fail completely.While our current implementation is only applicable to small datasets, we discuss variants that can potentially lead to practically useful algorithms.
Keywords
Computer Science
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
The MIT Press eBooksSemi-Supervised Learning
4,308 Citations2006Olivier Chapelle, Schölkopf, B. +1 more
This first comprehensive overview of semi-supervised learning presents state-of-the-art algorithms, a taxonomy of the field, selected applications, benchmark experiments, and perspectives on ongoing and future research.
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.
Machine LearningChoosing Multiple Parameters for Support Vector Machines
2,182 Citations2002Olivier Chapelle, Vladimir Vapnik +2 more
The problem of automatically tuning multiple parameters for pattern recognition Support Vector Machines (SVMs) is considered by minimizing some estimates of the generalization error of SVMs using a gradient descent algorithm over the set of parameters.
Learning from Labeled and Unlabeled Data with Label Propagation
1,568 Citations2002Xiongjie Zhu, Zoubin Ghahramani
A simple iterative algorithm, label propagation, to propagate labels through the dataset along high density areas defined by unlabeled data is proposed and its solution is analyzed, and its connection to several other algorithms is analyzed.
Incremental and Decremental Support Vector Machine Learning
1,158 Citations2000Gert Cauwenberghs, Tomaso Poggio
An on-line recursive algorithm for training support vector machines, one vector at a time, is presented and interpretation of decremental unlearning in feature space sheds light on the relationship between generalization and geometry of the data.
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.
Large Scale Transductive SVMs
463 Citations2006Ronan Collobert, Fabian H. Sinz +2 more
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.
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.
ComputingComputational aspects of a branch and bound algorithm for quadratic zero-one programming
266 Citations1990Pãnos M. Pardalos, Gregory Rodgers
Computational experience in solving unconstrained quadratic zero-one problems using a branch and bound algorithm that incorporates dynamic preprocessing techniques for forcing variables and heuristics to obtain good starting points is described.
A continuation method for semi-supervised SVMs
185 Citations2006Olivier Chapelle, Mingmin Chi +1 more
This paper proposes to use a global optimization technique known as continuation to alleviate the problem of non-convex optimization of S3VMs, which often results in suboptimal performances.
Linear Algebra and its ApplicationsA constrained eigenvalue problem
152 Citations1989Walter Gander, Gene H. Golub +1 more
A Constrained Eigenvalue Problem
134 Citations1991Walter Gander, Gene H. Golub +1 more
Deterministic annealing for semi-supervised kernel machines
129 Citations2006Vikas Sindhwani, S. Sathiya Keerthi +1 more
This paper presents a global optimization framework for semi-supervised Kernel machines where an easier problem is parametrically deformed to the original hard problem and minimizers are smoothly tracked.
Infoscience (Ecole Polytechnique Fédérale de Lausanne)A Taxonomy for Semi-Supervised Learning Methods
1 Citations2006Olivier Chapelle, Bernhard Schölkopf +1 more