Scaling Up Graph-Based Semisupervised Learning via Prototype Vector Machines

Kai Zhang, Liang Lan, James T. Kwok, Slobodan Vucetic, Bahram Parvin

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell_{1}$ </tex-math></inline-formula> -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.
BibTeX
@article{zhang2014scaling,
  author = {Kai Zhang and Liang Lan and James T. Kwok and Slobodan Vucetic and Bahram Parvin},
  title = {{Scaling Up Graph-Based Semisupervised Learning via Prototype Vector Machines}},
  journal = {IEEE Transactions on Neural Networks and Learning Systems},
  year = {2014},
  doi = {10.1109/tnnls.2014.2315526},
}

Loading related content...

Figure