Disagreement-Based Active Learning in Online Settings

Boshuang Huang, Sudeep Salgia, Qing Zhao

TL;DR

This paper introduces a novel online active learning algorithm (OLA) that efficiently learns from streaming data by strategically querying labels. It achieves near-optimal performance in terms of label complexity and prediction accuracy, even under noisy data conditions, by balancing the need for information with the cost of queries.

What Problem Does This Paper Address?

In many real-world scenarios, data arrives sequentially (streaming data), and obtaining labels for each data point is expensive or time-consuming. Active learning aims to address this by allowing the learning algorithm to intelligently select which data points to query for labels, thereby minimizing the number of queries while still achieving high accuracy. This paper focuses on the online active learning setting, where decisions must be made in real-time as data streams in, and there's a strict constraint on the number of prediction errors allowed. The challenge lies in balancing the desire to reduce the number of queries (label complexity) with the need to maintain high prediction accuracy (bounded regret), especially when the data is noisy (Tsybakov noise). Existing methods often struggle to balance these trade-offs effectively in the online setting.

Methods

The core contribution is a new algorithm called OLA (OnLine Active), which is based on the disagreement-based approach. This approach centers on maintaining a "version space" of plausible hypotheses and a "region of disagreement" (RoD) where these hypotheses disagree.

Here's a breakdown of the key methodological aspects:

  • Disagreement-Based Approach: OLA queries a label only when an incoming instance falls within the RoD. This ensures that queries are made only when they are most informative for reducing uncertainty among the current hypotheses.
  • Epoch-Based Structure: OLA operates in epochs. An epoch ends after a fixed number of labels (M) have been queried. This structured approach allows for efficient updates and analysis.
  • Threshold Design: A crucial innovation is the design of an "elimination threshold." This threshold determines when a hypothesis is considered sufficiently suboptimal and can be removed from the version space. The authors propose an aggressive threshold design that focuses on empirical errors incurred over significant examples, leading to a tighter concentration inequality and reduced label complexity.
  • Analysis Techniques: The paper employs novel techniques for analyzing online label complexity, separating the analysis into stages based on the size of the RoD. This involves constructing supermartingales and using optimal stopping theorems.
  • Trade-off Management: OLA is designed to operate at a specific point on the regret vs. label complexity trade-off curve. The paper also introduces a variant, RW-OLA (Random Walk OLA), which can operate at different points on this curve by incorporating a verification stage to mitigate the risk of eliminating the true hypothesis.

Datasets

The paper does not introduce new datasets. Instead, it uses theoretical analysis and simulations on synthetic data generated according to specific noise models (Tsybakov noise) and hypothesis spaces (e.g., linear separators, intervals) to evaluate the performance of their algorithms.

Key Insights and Ideas

  • Online Active Learning is Harder: The online setting introduces unique challenges compared to offline active learning. The inability to skip instances without consequence and the strict error constraints make aggressive query strategies riskier.
  • Disagreement is Key: The disagreement-based approach, by focusing on instances where hypotheses disagree, is shown to be more suitable for the online setting than more aggressive margin-based approaches.
  • Optimizing the Threshold: The design of the elimination threshold is critical for balancing label complexity and regret. The paper's novel threshold design leads to significant improvements.
  • Order Optimality: The proposed OLA algorithm achieves label complexity that is provably optimal up to a poly-logarithmic factor, meaning it's as good as theoretically possible for this problem setting.
  • RW-OLA for Flexibility: The RW-OLA variant demonstrates how to achieve a better trade-off between label complexity and regret, offering more flexibility for different application needs.

Key Results

  • Label Complexity: OLA achieves a label complexity of $O(dT^{2-2\alpha} \log^2 T)$ under Tsybakov noise with parameter $\alpha$, and a bounded regret. This is shown to be order-optimal.
  • RW-OLA Performance: For Massart noise, RW-OLA achieves an even better label complexity of $O(d \log T)$, with a small epoch length.
  • Simulation Results: Extensive simulations demonstrate that OLA and RW-OLA significantly outperform existing disagreement-based algorithms (A2, DHM, ACAL) in terms of label complexity across various noise conditions and hypothesis spaces. They also show competitive or superior performance compared to margin-based algorithms.
  • Regret Bound: The paper establishes a bounded regret of $1/2$ for OLA, indicating that its classification accuracy is practically the same as the Bayes optimal classifier.

Limitations and Future Work

  • Incomplete Trade-off Characterization: The authors acknowledge that the characterization of the regret vs. label complexity trade-off is not fully complete.
  • Algorithm for Any Trade-off Point: They suggest that further investigation is needed to develop online learning algorithms that can operate at any given point on the trade-off curve.
  • Generalization: While the paper discusses extensions to general hypothesis spaces, the detailed analysis and simulations often focus on specific cases like linear separators. Further exploration of performance on more complex hypothesis spaces could be beneficial.
  • Computational Complexity: While the paper discusses approximate implementations for linear classification, the core disagreement-based approach can still be computationally intensive. Investigating more efficient implementations remains an area for future work.

Summary updated

Abstract

We study online active learning for classifying streaming instances within the framework of statistical learning theory. At each time, the learner either queries the label of the current instance or predicts the label based on past seen examples. The objective is to minimize the number of queries while constraining the number of prediction errors over a horizon of length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> . We develop a disagreement-based online learning algorithm for a general hypothesis space and under the Tsybakov noise and establish its label complexity under a constraint of bounded regret in terms of classification errors. We further establish a matching (up to a poly-logarithmic factor) lower bound, demonstrating the order optimality of the proposed algorithm. We address the tradeoff between label complexity and regret and show that the algorithm can be modified to operate at a different point on the tradeoff curve.
BibTeX
@article{huang2022disagreement,
  author = {Boshuang Huang and Sudeep Salgia and Qing Zhao},
  title = {{Disagreement-Based Active Learning in Online Settings}},
  journal = {IEEE Trans. Signal Process.},
  year = {2022},
  url = {https://openreview.net/forum?id=DeRqEZuysG},
}
Figure