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.
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:
- Dual Ascending Procedures: Updates are restricted to a limited set of variables per round, ensuring speed.
- Buffering Strategies: Two buffers are utilized: Buffer-N for the most recent data points and Buffer-L to prioritize and retain labeled examples.
- 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