Active Learning with Strong and Weak Views: A Case Study on Wrapper Induction

Ion Muslea, Steven Minton, Craig A. KnoblockIJCAI 2003

Introduction

Data labeling remains a primary bottleneck in machine learning, often requiring significant human effort that is both costly and time-consuming. Active learning addresses this by strategically selecting the most informative examples for human labeling. A prominent technique in this domain is Co-Testing, which leverages multi-view learning—analyzing data through different feature sets or "views."

Traditional Co-Testing relies on the assumption that all views are "strong," meaning each is capable of learning the target concept perfectly. However, in many real-world scenarios, we have access to "weak views"—imperfect feature sets that provide useful constraints but cannot achieve perfect accuracy on their own. This paper introduces Aggressive Co-Testing, a novel algorithm that integrates these weak views to significantly enhance the efficiency of active learning, particularly in the context of web data extraction.

Methodology: Aggressive Co-Testing

The authors apply their approach to Wrapper Induction, the automated process of extracting structured data (e.g., prices, addresses) from semi-structured web pages. The system utilizes the STALKER induction algorithm as its base learner.

Multi-View Framework

The algorithm employs three distinct views:

  1. Strong Views: Two views based on token sequences surrounding the target data—Forward rules (prefixes) and Backward rules (suffixes).
  2. Weak View: A content-based grammar that describes the internal structure of the data itself. This view uses a hierarchy of tokens to define what the extracted field should look like.
Token hierarchy used to define content-based weak views.

Query Selection and Hypothesis Generation

In standard Co-Testing, queries are selected when strong views disagree. Aggressive Co-Testing refines this by selecting examples where the predictions of the strong views most significantly violate the constraints established by the weak view. This "aggressive" approach targets instances where the current model is likely making substantial errors.

For final predictions, the system employs a dynamic rule selection strategy. Rather than choosing a single best rule for the entire task, it evaluates which strong rule violates the fewest weak-view constraints for each specific document, allowing it to mitigate the individual weaknesses of each view.

Experimental Evaluation

The researchers evaluated Aggressive Co-Testing using a standard wrapper induction testbed consisting of 206 extraction tasks from 30 web sources. The study focused on the 33 most difficult tasks, defined as those where traditional methods failed to reach 100% accuracy even after 20 random labeled examples.

Key Results and Discussion

The results demonstrate a dramatic improvement in learning efficiency. Aggressive Co-Testing required an average of only 2.43 queries to reach 100% accuracy on solved tasks, a significant reduction from the 4.4 queries required by Naive Co-Testing.

Comparison of convergence rates across different active learning strategies: Aggressive Co-Testing, Naive Co-Testing, Query-by-Bagging, and Random Sampling.

Key findings include:

  • Rapid Convergence: On 11 of the 33 difficult tasks, the algorithm achieved perfect accuracy after just a single query.
  • Efficiency Gains: Compared to existing state-of-the-art active learners, Aggressive Co-Testing reduced the required labeled examples by 45% to 81%.
  • Superior Robustness: The algorithm successfully solved 30 out of the 33 difficult tasks, doubling the success rate of previous methods like WIEN, which only solved 15.

Limitations and Future Directions

Despite its success, the algorithm failed to reach 100% accuracy on 3 of the 33 tasks. This typically occurred when one strong view was significantly less accurate than the other, leading to a skewed query distribution. To address this, future work will focus on "view validation"—automatically assessing the appropriateness of a view for a specific task. Additionally, the authors plan to explore the application of weak views in semi-supervised learning environments.

Summary updated

BibTeX
@inproceedings{muslea2003active,
  author = {Ion Muslea and Steven Minton and Craig A. Knoblock},
  title = {{Active Learning with Strong and Weak Views: A Case Study on Wrapper Induction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure