Online Coregularization for Multiview Semisupervised Learning

Boliang Sun, Guohui Li, Jia Li, Kuihua HuangThe Scientific World JOURNAL 2013 · DOI

TL;DR

This paper introduces a novel online coregularization framework for multiview semi-supervised learning by leveraging duality in optimization. It shows how existing methods are approximations of this framework and proposes new, more aggressive algorithms that achieve comparable accuracy to offline methods while being more efficient and robust to concept drift.

What Problem Does This Paper Address?

Semi-supervised learning (SSL) aims to learn from both labeled and unlabeled data, which is particularly useful when labeling is expensive. Multiview SSL deals with data that can be represented from multiple perspectives (e.g., text and links for a webpage). Online SSL (OSSL) is crucial for scenarios where data arrives sequentially and cannot be stored entirely, requiring models to learn and adapt on the fly. A key challenge in OSSL is the lack of true labels for unlabeled data, necessitating indirect feedback for model updates. Coregularization is a technique that improves SSL by enforcing agreement between predictions from different views on unlabeled data. However, existing offline coregularization methods struggle with the computational demands of large-scale online learning. This paper addresses the need for efficient and effective online coregularization algorithms that can handle streaming data, adapt to changing data distributions (concept drift), and maintain high accuracy.

Methods

The core contribution is a novel online coregularization framework built upon the concept of duality in constrained optimization. Instead of directly optimizing the primal problem (which is difficult in an online setting), the authors transform the problem into maximizing the dual function. They demonstrate that existing online coregularization algorithms can be seen as approximations of this dual ascent process using standard gradient ascent.

The paper then proposes new algorithms derived from a more aggressive dual ascending procedure. This involves solving a constrained quadratic programming (QP) problem at each learning round to update dual variables. To further enhance efficiency, they introduce two sparse approximation approaches for kernel representation:

  • Absolute Threshold: Discards examples with very small associated coefficients.
  • k Maximal Coefficients (k-MC): Retains only the top k examples with the largest coefficients.

These sparse methods aim to reduce the computational complexity and memory footprint by avoiding the need to store all past examples.

Datasets

The paper evaluates its methods on the following datasets:

  • Two-Moons-Two-Lines Synthetic Data Set: A standard benchmark for multiview learning, featuring two distinct views (e.g., geometric shapes and linear relationships).
  • Web Page Categorization (WebKB): A real-world dataset for text classification, using page content and link structure as two views.
  • Rotating Two-Moons-Two-Lines Synthetic Data Set: A novel benchmark designed to specifically test the algorithms' ability to handle concept drift, where the underlying data distributions change over time.

Key Insights and Ideas

  • Duality as a Unifying Framework: The paper elegantly shows that the online coregularization problem can be effectively tackled by ascending the dual function, providing a theoretical foundation for designing and analyzing new algorithms.
  • Existing Methods as Approximations: Recognizing that prior online coregularization algorithms are essentially gradient ascent approximations of the dual ascent is a significant insight, explaining their limitations.
  • Aggressive Dual Ascent for Efficiency: The proposed aggressive dual ascending procedures lead to faster convergence and better performance, suggesting that maximizing the dual function more vigorously is beneficial.
  • Sparse Kernels for Scalability: The sparse approximation techniques are crucial for making kernel-based online coregularization practical by significantly reducing memory requirements.
  • Robustness to Concept Drift: The framework's ability to adapt to changing data distributions (concept drift) is a key advantage for real-world streaming applications.

Key Results

  • The proposed online coregularization algorithms achieve test error rates comparable to offline algorithms (e.g., CoLapSVM) on synthetic and real-world datasets.
  • The aggressive dual ascending (ADA) algorithms generally outperform gradient ascent-based methods, showing lower error rates.
  • Sparse approximation techniques (especially k-MC) lead to significantly reduced computational complexity and memory usage, making the algorithms scalable.
  • The algorithms demonstrate strong performance in handling concept drift on the rotating two-moons-two-lines dataset, maintaining relatively low error rates.
  • The paper shows that the primal and dual objective functions converge as the learning process progresses, supporting the theoretical framework.

Limitations and Future Work

  • Parameter Tuning: While the paper uses a finite grid search for parameter optimization, more intelligent online parameter selection methods could be explored.
  • Generalization to More Views: The paper primarily focuses on two-view scenarios; extending the framework to handle a larger number of views could be a future direction.
  • More Complex Models: Investigating the application of this framework to other semi-supervised learning models beyond linear classifiers is suggested.
  • Adaptive Buffering Strategies: While Buffer-N and Buffer-L are tested, further research into more adaptive buffering strategies could improve performance, especially in dynamic environments.

Summary updated

Abstract

We propose a novel online coregularization framework for multiview semisupervised learning based on the notion of duality in constrained optimization. Using the weak duality theorem, we reduce the online coregularization to the task of increasing the dual function. We demonstrate that the existing online coregularization algorithms in previous work can be viewed as an approximation of our dual ascending process using gradient ascent. New algorithms are derived based on the idea of ascending the dual function more aggressively. For practical purpose, we also propose two sparse approximation approaches for kernel representation to reduce the computational complexity. Experiments show that our derived online coregularization algorithms achieve risk and accuracy comparable to offline algorithms while consuming less time and memory. Specially, our online coregularization algorithms are able to deal with concept drift and maintain a much smaller error rate. This paper paves a way to the design and analysis of online coregularization algorithms.
BibTeX
@article{sun2013online,
  author = {Boliang Sun and Guohui Li and Jia Li and Kuihua Huang},
  title = {{Online Coregularization for Multiview Semisupervised Learning}},
  journal = {The Scientific World JOURNAL},
  year = {2013},
  doi = {10.1155/2013/398146},
}
Figure