Laplacian Support Vector Machines Trained in the Primal

Abstract

In the last few years, due to the growing ubiquity of unlabeled data, much effort has been spent by the machine learning community to develop better understanding and improve the quality of classifiers exploiting unlabeled data. Following the manifold regularization approach, Laplacian Support Vector Machines (LapSVMs) have shown the state of the art performance in semi--supervised classification. In this paper we present two strategies to solve the primal LapSVM problem, in order to overcome some issues of the original dual formulation. Whereas training a LapSVM in the dual requires two steps, using the primal form allows us to collapse training to a single step. Moreover, the computational complexity of the training algorithm is reduced from O(n^3) to O(n^2) using preconditioned conjugate gradient, where n is the combined number of labeled and unlabeled examples. We speed up training by using an early stopping strategy based on the prediction on unlabeled data or, if available, on labeled validation examples. This allows the algorithm to quickly compute approximate solutions with roughly the same classification accuracy as the optimal ones, considerably reducing the training time. Due to its simplicity, training LapSVM in the primal can be the starting point for additional enhancements of the original LapSVM formulation, such as those for dealing with large datasets. We present an extensive experimental evaluation on real world data showing the benefits of the proposed approach.

39 pages, 14 figures

Cited by in corpus (20)

• Semi-Supervised Classification Based on Classification from Positive and Unlabeled Data
• The Responsibility Weighted Mahalanobis Kernel for Semi-Supervised Training of Support Vector Machines for Classification
• Supervised learning of sparse context reconstruction coefficients for data representation and classification
• Quantum Semi-Supervised Kernel Learning
• Data-dependent kernels in nearly-linear time
• Learning to see like children: proof of concept
• Large-Scale Semi-Supervised Learning via Graph Structure Learning over High-Dense Points
• Mining Functionally Related Genes with Semi-Supervised Learning
• Scalable Semi-supervised Learning with Graph-based Kernel Machine
• Semi-Supervised Representation Learning based on Probabilistic Labeling
• Deep Metric Learning with Density Adaptivity
• Semi-Supervised Active Learning for Support Vector Machines: A Novel Approach that Exploits Structure Information in Data
• A Laplacian-Based Approach for Finding Near Globally Optimal Solutions to OPF Problems
• Multiscale Laplacian Learning
• Deep Constraint-based Propagation in Graph Neural Networks
• Supervised Heterogeneous Multiview Learning for Joint Association Study and Disease Diagnosis
• Multi-Label Learning with Global and Local Label Correlation
• Representing data by sparse combination of contextual data points for classification
• Comparison of SVM Optimization Techniques in the Primal
• Mini-batch stochastic Nesterov's smoothing method for constrained convex stochastic composite optimization