Semi-supervised Classification Using Local and Global Regularization

Fei Wang, Tao Li, Gang Wang, Changshui ZhangAAAI 2008 · OpenReview

Abstract

In this paper, we propose a semi-supervised learning (SSL) algorithm based on local and global regularization. In the local regularization part, our algorithm constructs a regularized classifier for each data point using its neighborhood, while the global regularization part adopts a Laplacian regularizer to smooth the data labels predicted by those local classifiers. We show that some existing SSL algorithms can be derived from our framework. Finally we present some experimental results to show the effectiveness of our method.

Introduction

Semi-supervised learning (SSL) addresses the challenge of training effective models when labeled data is scarce but unlabeled data is abundant. Traditional graph-based SSL methods typically seek a single global function that fits labeled examples while maintaining smoothness across the data graph. However, finding a complex global predictor that performs well across the entire data space is inherently difficult.

Following Vapnik's learning theory, it is often easier to find simple predictors for small, local regions. The primary obstacle is that these local regions frequently lack sufficient labeled data for robust training. This paper introduces LGReg (Local and Global Regularization), a framework designed to bridge the gap between local accuracy and global consistency by combining local linear predictors with global smoothing.

Methodology

The LGReg framework employs a dual regularization strategy:

  1. Local Regularization: Instead of a single global model, the algorithm constructs $n$ local linear classifiers, one for the neighborhood of each data point. It introduces "hidden labels" ($f_i$) for every point, and the local loss measures the prediction error of these local classifiers. This local behavior is mathematically condensed into a "local learning" matrix ($M$).
  2. Global Regularization: To ensure stability despite sparse local data, a standard Laplacian regularizer ($L$) is added. This acts as a global smoother, ensuring that predicted labels respect the intrinsic geometry of the data manifold.

The resulting objective function minimizes error on labeled points while simultaneously penalizing local prediction errors and global label variance. This "Mixed-Regularization" task yields a closed-form solution involving a single matrix inversion, ensuring computational predictability.

Experimental Setup

The effectiveness of LGReg was evaluated across 12 diverse datasets, encompassing various domains and dimensionalities:

  • Artificial Benchmarks: g241c and g241n.
  • Image Recognition: USPS (digits), COIL (objects), and digit1.
  • Text Mining (WebKB): Cornell, Texas, Wisconsin, and Washington.
  • UCI/Other: BCI (Brain-Computer Interface), Diabetes, and Ionosphere.

These datasets represent a wide range of dimensions (from 8 to over 4,000) and classes, providing a comprehensive stress test for the algorithm's generalization capabilities.

Results and Discussion

Experimental results demonstrate that LGReg consistently outperforms or matches state-of-the-art SSL methods across diverse data types.

Average classification accuracy across various datasets as a function of the percentage of labeled points.

As shown in the performance curves above, LGReg (represented by red stars) maintains high accuracy even with very few labeled points. Notably, on the USPS digit dataset, LGReg achieves a peak accuracy of 99.21%, significantly surpassing methods like LapRLS (88.80%).

Comparison of average classification accuracy and standard deviation for LGReg against other SSL algorithms.

Key insights from the results include:

  • Local Learning as Smoothing: The authors demonstrate that the local learning penalty matrix ($M$) behaves similarly to a Laplacian matrix, suggesting that local learning is effectively a sophisticated form of graph smoothing.
  • Complementary Regularization: Combining local linear models with standard Gaussian kernels captures complementary data features, resulting in a more robust classifier than using either approach in isolation.
  • Framework Generality: The LGReg framework is shown to be a generalization of several existing SSL algorithms, such as GRF and LLGC, which emerge as special cases when specific parameters are zeroed.

Conclusion

LGReg offers a powerful approach to SSL by integrating local predictive power with global manifold smoothing. While the method demonstrates superior performance across image and text datasets, future work may address the computational complexity of large-scale matrix inversions and the challenges of hyperparameter tuning in label-scarce environments.

Summary updated

Abstract

In this paper, we propose a semi-supervised learning (SSL) algorithm based on local and global regularization. In the local regularization part, our algorithm constructs a regularized classifier for each data point using its neighborhood, while the global regularization part adopts a Laplacian regularizer to smooth the data labels predicted by those local classifiers. We show that some existing SSL algorithms can be derived from our framework. Finally we present some experimental results to show the effectiveness of our method.
BibTeX
@inproceedings{wang2008semi,
  author = {Fei Wang and Tao Li and Gang Wang and Changshui Zhang},
  title = {{Semi-supervised Classification Using Local and Global Regularization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
  url = {https://openreview.net/forum?id=rJVQURldWH},
}
Figure