Abstract
Semisupervised learning (SSL) leverages unlabeled data to improve model performance when labeled data is scarce. Graph-based SSL techniques, which enforce smoothness on a data manifold, are state-of-the-art but suffer from high computational costs—typically $O(n^3)$ time and $O(n^2)$ space. This paper introduces Prototype Vector Machines (PVM), which use a sparse set of data prototypes to approximate the graph-based regularizer. This approach reduces complexity to linear time, enabling SSL on massive datasets while maintaining high accuracy and model parsimony.
Introduction
Traditional graph-based SSL methods, such as Laplacian SVMs, require manipulating $n \times n$ matrices for $n$ data points. This quadratic space and cubic time complexity make them impractical for large-scale applications. Furthermore, the resulting models are often "dense," requiring the storage of nearly all training points for inference. PVM addresses these bottlenecks by decoupling the number of model parameters from the number of training samples.
Methodology: Prototype Vector Machines
PVM utilizes a small set of $m$ prototypes ($m \ll n$) to serve two distinct roles:
- Manifold Approximation: A low-rank approximation of the graph Laplacian is constructed using these prototypes, similar to Nyström methods, to capture the underlying data structure efficiently.
- Model Sparsification: The predictive model is restricted to a linear combination of basis functions centered only at the $m$ prototypes, rather than all $n$ points.
A key contribution is the principled selection of prototypes. The authors demonstrate that for Gaussian kernels, $k$-means clustering centers are mathematically optimal for minimizing the reconstruction error of the data manifold. This allows the model to capture the "shape" of the data with very few points.
Key Results
The authors evaluated PVM across 13 diverse datasets, including MNIST, USPS, and biological benchmarks.
- Efficiency: PVM achieves linear scaling with respect to the number of samples $n$. On datasets where traditional methods failed due to memory limits (e.g., USPS-FULL), PVM completed training in seconds.
- Accuracy: Despite using fewer than 5% of data points as prototypes, PVM maintained accuracy comparable to full-scale graph methods and frequently outperformed $\ell_1$-regularized sparse models at the same level of sparsity.
- Versatility: The framework supports multiple loss functions, including PVM(sqr) for least-squares and PVM(hinge) for SVM-like hinge loss.
Conclusion
Prototype Vector Machines provide a scalable framework for graph-based SSL. By using $k$-means centers as structural prototypes, PVM achieves significant speedups and memory savings without sacrificing the benefits of manifold regularization. This makes high-performance semisupervised learning accessible for large-scale, real-world applications.
Reference: Zhang, K., Lan, L., Kwok, J. T., Vucetic, S., & Parvin, B. (2015). Scaling Up Graph-Based Semisupervised Learning via Prototype Vector Machines. IEEE Transactions on Neural Networks and Learning Systems, 26(3), 444-457.
Summary updated