Online Semi-Supervised Learning With Multiple Regularization Terms

Chao Chen, Boliang Sun, Xingchen Hu, Yan LiIEEE Access 2019 · OpenReview

Abstract

Online semi-supervised learning (OS$^2$L) has gained significant attention due to its practical utility in processing continuous data streams where labeled information is scarce. While most existing OS$^2$L research focuses on manifold regularization, this paper introduces a novel framework capable of incorporating multiple regularization terms simultaneously. By ascending the dual function in a constrained optimization setting and utilizing Fenchel conjugates, the proposed approach integrates various semi-supervised terms directly. To ensure scalability, the framework employs buffering strategies and sparse approximation techniques. Experimental results demonstrate that this method achieves accuracy comparable to offline algorithms while significantly reducing time and memory consumption, even in environments with concept drift.

Introduction

In the era of big data, information often arrives as a high-velocity stream. Labeling this data in real-time is frequently impractical or prohibitively expensive. Online Semi-Supervised Learning (OS$^2$L) addresses this by learning from a continuous flow of data using only a fraction of labeled examples.

Historically, OS$^2$L methods have been limited to single regularization types, typically manifold regularization. However, offline learning has shown that combining multiple views or regularization terms (e.g., co-regularization) can drastically improve performance. The challenge lies in adapting these complex, multi-term optimizations for the efficiency required by online processing.

The OS$^2$L Framework

The core of the proposed framework is the transition from a complex primal optimization problem to a manageable dual space using the Fenchel conjugate transform. This mathematical tool allows the integration of diverse convex regularization terms into a unified dual function.

Visual representation of the Hinge and Absolute functions, which are common convex loss/regularization terms integrated via Fenchel conjugates.

By optimizing in the dual space, the algorithm can perform incremental "ascents," updating only a small subset of dual coefficients for each new data point. This "plug-and-play" flexibility allows for the simultaneous use of:

  • Manifold Regularization: Leveraging the geometric structure of the data (similar points should have similar labels).
  • Co-regularization: Ensuring consistency across different "views" or feature sets of the same data instance.

Practical Implementation: Buffering and Sparsity

To maintain constant computational overhead and prevent the model from growing indefinitely, the authors implemented several key strategies:

  1. Dual Ascending Procedures: Updates are restricted to a limited set of variables per round, ensuring speed.
  2. Buffering Strategies: Two buffers are utilized: Buffer-N for the most recent data points and Buffer-L to prioritize and retain labeled examples.
  3. Sparse Approximation: Techniques like k-Maximal Coefficients (k-MC) are used to prune the model, keeping only the most influential data points in the kernel representation. This ensures that runtime growth remains linear rather than quadratic.

Experimental Evaluation

The framework was tested across three scenarios:

  • Synthetic Multi-View Data: Using a "two-moons-two-lines" dataset, the online algorithm achieved an error rate of approximately 5.2%, rivaling the 3.7% achieved by the state-of-the-art offline MvLapSVM.
  • Real-World Web Classification: Classifying web pages based on page text and anchor text. The framework successfully integrated these two views to improve classification accuracy.
  • Concept Drift Simulation: In a rotating synthetic dataset, the model demonstrated its ability to track a shifting target hyperplane. While stationary models failed as the data distribution changed, the OS$^2$L method maintained high accuracy by prioritizing recent observations through an "Overall Update" scheme with a forgetting factor.

Conclusion

This paper provides a robust mathematical foundation for designing OS$^2$L algorithms that can handle multiple regularization terms. By bridging the gap between the theoretical power of multi-view offline learning and the practical constraints of online data streams, the framework offers a scalable solution for modern machine learning challenges. Future work will explore extending this to non-convex risks and implementing automated hyperparameter tuning.

Summary updated

Abstract

Online semi-supervised learning (OS <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> L) has received much attention recently because of its well practical usefulness. Most of the existing studies of OS <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> L are related to manifold regularization. In this paper, we introduce a novel OS <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> L framework with multiple regularization terms based on the notion of ascending the dual function in constrained optimization. Using the Fenchel conjugate, different semi-supervised regularization terms can be integrated into the dual function easily and directly. This approach is derived by updating limited dual coefficient variables on each learning round. To be practical, we also employ buffering strategies and sparse approximation approaches in this paper. The experimental studies show that our methods achieve accuracy comparable to offline algorithms while consuming less time and memory. Especially, our OS <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> L algorithms can handle the settings where the target hyperplane of classification continually drifts with the sequence of arriving instances. This paper paves a way to design and analyze OS <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> L algorithms with multiple regularization terms.
BibTeX
@inproceedings{chen2019online,
  author = {Chao Chen and Boliang Sun and Xingchen Hu and Yan Li},
  title = {{Online Semi-Supervised Learning With Multiple Regularization Terms}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=OLFj1XDxL9},
}
Figure