title: Scaling up graph-based semisupervised learning via prototype vector machines.
abstract: 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 l1 -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.
authors.forename: Kai
authors.initials: K
authors.lastname: Zhang
authors.forename: Liang
authors.initials: L
authors.lastname: Lan
authors.forename: James T
authors.initials: JT
authors.lastname: Kwok
authors.forename: Slobodan
authors.initials: S
authors.lastname: Vucetic
authors.forename: Bahram
authors.initials: B
authors.lastname: Parvin
mesh_terms: D066264:Datasets as Topic / Q000639:trends; D010363:Pattern Recognition, Automated / Q000379:methods* / Q000639:trends; D000069553:Supervised Machine Learning / Q000639:trends; D060388:Support Vector Machine / Q000639:trends