Scaling Up Graph-Based Semisupervised Learning via Prototype Vector Machines

• Published in: IEEE transaction on neural networks and learning systems 2015-03, Vol.26 (3), p.444-457
• Main Authors: Kai Zhang, Liang Lan, Kwok, James T., Vucetic, Slobodan, Parvin, Bahram
• Format: Article
• Language: English
• Subjects: Approximation; Approximation methods; Complexity; Datasets as Topic - trends; Graph-based methods; Graphs; Kernel; Laplace equations; large data sets; Learning; low-rank approximation; manifold regularization; Manifolds; Neural networks; Pattern Recognition, Automated - methods; Pattern Recognition, Automated - trends; Prototypes; Semisupervised learning; Supervised Machine Learning - trends; Support Vector Machine - trends; Training
• ISSN: 2162-237X; 2162-2388
• DOI: 10.1109/TNNLS.2014.2315526

When the amount of labeled data are limited, semisupervised learning can improve the learner's performance by also using the often easily available unlabeled data. In particular, a popular approach requires the learned function to be smooth on the underlying data manifold. By approximating this manifold as a weighted graph, such graph-based techniques can often achieve state-of-the-art performance. However, their high time and space complexities make them less attractive on large data sets. In this paper, we propose to scale up graph-based semisupervised learning using a set of sparse prototypes derived from the data. These prototypes serve as a small set of data representatives, which can be used to approximate the graph-based regularizer and to control model complexity. Consequently, both training and testing become much more efficient. Moreover, when the Gaussian kernel is used to define the graph affinity, a simple and principled method to select the prototypes can be obtained. Experiments on a number of real-world data sets demonstrate encouraging performance and scaling properties of the proposed approach. It also compares favorably with models learned via ℓ 1 -regularization at the same level of model sparsity. These results demonstrate the efficacy of the proposed approach in producing highly parsimonious and accurate models for semisupervised learning.