Laplacian Support Vector Machines Trained in the Primal

By Stefano Melacci, Mikhail Belkin. Journal of machine learning research, 2009

390 citations recorded by the source corpus.

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. In particular, training a LapSVM in the primal can be efficiently performed with preconditioned conjugate gradient. 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. The computational complexity of the training algorithm is reduced from O(n3) to O(kn2), where n is the combined number of labeled and unlabeled examples and k is empirically evaluated to be significantly smaller than n. 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 data sets. We present an extensive experimental evaluation on real world data showing the benefits of the proposed approach.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/2ab5330706c6b12942a212b6d72ed1221b578729

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Dacheng Tao
2. Trevor Darrell
3. Kate Saenko
4. Tao Mei
5. Gabriella Csurka
6. Judy Hoffman
7. Luc Van Gool
8. Ting Yao

Citations in the corpus

• Scalable Semi-Supervised Learning by Efficient Anchor Graph Regularization (2016, methodology): “The EAGR also empirically shows its advantages over many existing SSL methods developed for large datasets, such as the methods in [26], [47], [48].”
• Multi-Label Learning with Global and Local Label Correlation (2017, background): “re the corresponding classier outputs, and vice versa. Let S 0 = [S ij] 2Rl l be the 5 global label correlation matrix. The manifold regularizer P i;j S ijkf i;: f j;:k 2 2 should have a small value [12]. Here, f i;:, the ith row of F 0, is the vector of classier outputs for the ith label on the nsa”
• Visual Classification by ℓ1-Hypergraph Modeling (2015, methodology): “LapSVM is a semi-supervised learning method, which is extended from the standard SVM by adding a smoothness penalty term to represent both labeled and unlabeled data with the graph Laplacian.”
• Semi-supervised Domain Adaptation with Instance Constraints (2013, methodology): “Manifold regularization To integrate unlabeled data with similarity constraints into a learning objective function, we use manifold regularization in the form of a Laplacian regularizer, which has been shown effective for semisupervised learning [22].”
• Semi-Supervised and Unsupervised Extreme Learning Machines (2014, methodology): “As in [57], this random fold generation process was repeated three times, resulting in 12 different splits in total.”
• Distributed learning for Random Vector Functional-Link networks (2015, background): “G50C, differently from the others, is an artificial dataset [24], whose main interest is given by the fact that the optimal error rate is designed so as to be equal to exactly 5%.”
• Click-through-based cross-view learning for image search (2014, background): “Structure preservation or manifold regularization has been shown effective for semi-supervised learning [21] and multiview learning [7].”
• Semi-supervised clinical text classification with Laplacian SVMs: an application to cancer case management (2013, methodology): “LapSVM implements primal and dual optimizers [23].”
• Which Looks Like Which: Exploring Inter-class Relationships in Fine-Grained Visual Categorization (2014, background): “In addition, the squared hinge loss provides a better computational efficiency, which is extremely important when we need to solve the primal problem directly [15,29].”