Large-Scale Sparsified Manifold Regularization

Ivor W. Tsang, James T. KwokNeurIPS 2006 · OpenReview

TL;DR

This paper introduces SLapCVM (Sparsified Laplacian Core Vector Machine), a semi-supervised learning algorithm that scales manifold regularization to millions of data points. By replacing the standard manifold regularizer with an $\epsilon$-insensitive loss and leveraging the Core Vector Machine (CVM) framework, the authors achieve sparse solutions that are orders of magnitude faster than the state-of-the-art Laplacian SVM.

The Bottleneck in Semi-Supervised Learning

Semi-supervised learning (SSL) is a powerful paradigm that uses a small amount of labeled data alongside a vast pool of unlabeled data to improve model performance. A leading framework for this is Manifold Regularization, which assumes that data points living on the same "manifold" (a low-dimensional structure in high-dimensional space) should have similar labels.

The gold standard for this approach has traditionally been the Laplacian SVM (LapSVM). However, LapSVM has two major "deal-breakers" for real-world big data:

  1. Lack of Sparsity: Unlike a standard SVM, the LapSVM solution involves kernel expansions of all labeled and unlabeled examples. This makes the model incredibly slow during the testing and prediction phases.
  2. Scalability: LapSVM requires an expensive matrix inversion, resulting in $O((m+n)^3)$ time complexity. In practice, it struggles to handle more than a few thousand unlabeled examples.

Methodology: SLapCVM

To overcome these limitations, the authors propose SLapCVM, integrating manifold regularization with the Core Vector Machine (CVM). Their approach relies on two key innovations:

  • Sparsified Manifold Regularizer: In traditional manifold regularization, the "smoothness" penalty is a squared term. The authors replace this with an $\epsilon$-insensitive loss function (similar to what is used in Support Vector Regression). This ensures that if two points are "close enough" on the manifold, the penalty becomes zero, leading to a sparse solution where only a few "core" points are needed to define the decision boundary.
  • Geometric Optimization (MEB): They show that the resulting optimization problem can be transformed into a center-constrained Minimum Enclosing Ball (MEB) problem. This allows them to use the CVM’s $(1+\epsilon)$-approximation algorithm. The beauty of CVM is that its time complexity is independent of the number of data points for a fixed approximation accuracy, making it ideal for massive datasets.

Experimental Datasets

The algorithm was evaluated on three primary benchmarks to test both accuracy and extreme scaling:

Two-Moons dataset classification boundary
  • Two-Moons Data Set: A classic synthetic SSL benchmark (visualized above), scaled up to 1 million unlabeled points to test extreme scaling capabilities.
  • Extended USPS: A handwritten digit dataset (approx. 266,000 patterns) used for digit classification.
  • Extended MIT Face Data Set: A massive face detection dataset containing nearly 900,000 patterns.

Key Insights

  • Sparsity is the Key to Speed: By forcing the manifold regularizer to be sparse, the authors solve the "slow testing" problem of LapSVM. The model only needs to remember a tiny fraction of the data points (the "core set") to make predictions.
  • SSL Can Rival Supervised Learning: In the MIT Face experiments, SLapCVM—using only 10 labeled examples and the rest unlabeled—performed as well as or better than a supervised CVM trained on 900,000 labeled examples. This highlights the massive untapped potential of unlabeled data.
  • Complexity Independence: The most striking insight is that by using the CVM framework, the computational cost becomes nearly constant regardless of how many unlabeled points you add, provided you are willing to accept a tiny, controlled approximation error.

Key Results

CPU time and kernel expansions vs. number of unlabeled points
  • Massive Scaling: As shown in the performance graphs above, SLapCVM successfully handled 1 million unlabeled examples on a standard PC. In contrast, the original LapSVM failed after just a few thousand points due to memory and time constraints.
  • Efficiency: On the Two-Moons dataset, SLapCVM was significantly faster than LapSVM and produced a much sparser model (requiring far fewer kernel expansions).
  • Accuracy: On the USPS dataset, SLapCVM achieved lower error rates than both the standard SVM (which ignores unlabeled data) and the reduced LapSVM.
  • Face Detection: On the MIT Face dataset, SLapCVM achieved an Area Under the Curve (AUC) of ~0.94 using only 10 labeled points, rivaling models trained on the full labeled set.

Limitations and Future Work

  • Graph Construction: While the optimization is fast, the paper assumes the neighborhood graph (used to approximate the manifold) is already constructed. For millions of points, building a $k$-nearest neighbor graph is itself a significant computational challenge.
  • Parameter Sensitivity: The method introduces several user-defined parameters ($C, \mu, \theta$). While the authors use a validation set, tuning these for massive datasets can be time-consuming.
  • Approximation Trade-off: The CVM relies on a $(1+\epsilon)$ approximation. While theoretically sound, users must balance the trade-off between the tightness of the approximation and the speed of convergence.

Summary updated

Abstract

Semi-supervised learning is more powerful than supervised learning by using both labeled and unlabeled data. In particular, the manifold regularization framework, together with kernel methods, leads to the Laplacian SVM (LapSVM) that has demonstrated state-of-the-art performance. However, the LapSVM solution typically involves kernel expansions of all the labeled and unlabeled examples, and is slow on testing. Moreover, existing semi-supervised learning methods, including the LapSVM, can only handle a small number of unlabeled examples. In this paper, we integrate manifold regularization with the core vector machine, which has been used for large-scale supervised and unsupervised learning. By using a sparsified manifold regularizer and formulating as a center-constrained minimum enclosing ball problem, the proposed method produces sparse solutions with low time and space complexities. Experimental results show that it is much faster than the LapSVM, and can handle a million unlabeled examples on a standard PC; while the LapSVM can only handle several thousand patterns.
BibTeX
@inproceedings{tsang2006large,
  author = {Ivor W. Tsang and James T. Kwok},
  title = {{Large-Scale Sparsified Manifold Regularization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=rkWxCdZuZr},
}
Figure