PaperlayerView exact revision on arXiv

Source-linked AI summary

Wrapper Maintenance: A Machine Learning Approach

C. A. Knoblock, K. Lerman, S. N. Minton

arXiv:1106.4872v1cs.AI

TL;DR

Web-source changes can make wrappers extract incorrect data, while wrapper maintenance has received less attention than wrapper generation. The paper introduces DataProG, which learns structural patterns from positive examples for wrapper verification and reinduction. Across the reported evaluations, verification detected 35 of 37 wrapper changes, and reinduced wrappers achieved 0.90 precision and 0.80 recall on extraction.

  • Problem

    Wrapper maintenance is needed because changes in Web-source layout or data format can break wrappers, but it has received less attention than wrapper induction.

  • Method

    DataProG learns structural information from positive examples and uses the resulting patterns for wrapper verification and reinduction.

  • Results

    The verification algorithm correctly discovered 35 of 37 wrapper changes, while reinduced extraction rules achieved 0.90 precision and 0.80 recall.

  • Takeaways & Limitations

    Learned content patterns supported detecting wrapper failures and identifying data for automatically rebuilding extraction rules.

  • Takeaways & Limitations

    The experiments excluded the geocoder and CIA Factbook wrappers because their sources were unavailable or outside the method's Web-page scope.

Abstract

from arXiv · show

The proliferation of online information sources has led to an increased use of wrappers for extracting data from Web sources. While most of the previous research has focused on quick and efficient generation of wrappers, the development of tools for wrapper maintenance has received less attention. This is an important research problem because Web sources often change in ways that prevent the wrappers from extracting data correctly. We present an efficient algorithm that learns structural information about data from positive examples alone. We describe how this information can be used for two wrapper maintenance applications: wrapper verification and reinduction. The wrapper verification system detects when a wrapper is not extracting correct data, usually because the Web source has changed its format. The reinduction algorithm automatically recovers from changes in the Web source by identifying data on Web pages so that a new wrapper may be generated for this source. To validate our approach, we monitored 27 wrappers over a period of a year. The verification algorithm correctly discovered 35 of the 37 wrapper changes, and made 16 mistakes, resulting in precision of 0.73 and recall of 0.95. We validated the reinduction algorithm on ten Web sources. We were able to successfully reinduce the wrappers, obtaining precision and recall values of 0.90 and 0.80 on the data extraction task.

1. Introduction

Wrapper maintenance addresses the problem that Web-source changes can break extraction rules. The paper introduces DataProG, which learns content structure from examples and supports verification and reinduction.

  • Motivation: Wrapper maintenance has received less attention than wrapper induction, despite layout changes that can prevent correct extraction.The paper frames maintenance as an important problem for applications relying on extracted Web data.
  • Approach: The proposed maintenance approach combines wrapper verification with reinduction after Web-source changes.Verification detects inconsistent output, while reinduction repairs extraction rules using data located on changed pages.
  • Approach: DataProG learns structural information about common data fields from positive examples and supplies the core learning technique.The method learns content-based patterns that describe field structure.
  • Contribution: Content-based patterns complement landmark-based extraction rules by describing the structure of the field itself.The paper distinguishes page-structure rules from patterns that exploit field structure.

2. Learning Content Patterns

The paper represents structured Web fields with hierarchical token patterns and learns statistically significant sequences from positive examples. DataProG grows, prunes, and extracts these patterns from a prefix tree.

  • Motivation: Structured fields such as addresses share regularities that can be learned as data prototypes.The objective is to learn field structure rather than treat examples as arbitrary strings.
  • Data Representation: The representation uses word-level token types arranged in a hierarchy, allowing patterns to generalize at multiple levels.Tokens are assigned syntactic categories, and frequently occurring specific strings can receive unique token types.
  • Learning from Positive Examples: DataProG learns conserved patterns from positive examples alone because suitable negative examples are problematic.It identifies token sequences occurring more often than expected under random independent generation.
  • Learning from Positive Examples: Statistical significance is assessed against baseline token probabilities using hypothesis testing.The algorithm compares observed sequence occurrences with the expected frequency under a chance model.
  • DataProG Algorithm: DataProG incrementally grows a token-type prefix tree, prunes less significant nodes, and extracts the significant patterns remaining in the tree.Each path from the root represents a learned significant pattern.

3. Applications of Pattern Learning

Wrapper maintenance addresses source changes that can make extracted data incorrect by combining verification with automatic reinduction. Pattern learning supports both detecting broken extraction and recovering wrappers, while specificity bias affected verification performance.

  • Wrapper maintenance handles layout and source-format changes that can cause wrappers to extract nothing or incorrect data.The paper divides maintenance into wrapper verification and wrapper reinduction.
  • Wrapper verification detects invalid extraction, while reinduction uses learned data descriptions to locate examples and repair broken wrappers.
  • Eliminating specificity bias improved verification performance after the bias had caused many false positives.
  • Table 2 presents Bigbook business-name and address examples alongside the patterns learned from them.
  • Table 3 presents Bigbook city, state, and phone-number examples alongside the patterns learned from them.
  • Table 4 presents Yahoo Quote data examples alongside the patterns learned from them.

3.1 Wrapper Verification

The wrapper verification system compares structural and numeric features of new extractions with correct training examples to detect source or wrapper changes. Across 438 comparisons, it detected 35 of 37 changes, with recall 0.95 and precision 0.73, while false positives arose from tokenization, incomplete coverage, and format changes.

  • The verifier learns patterns and global numeric features from correct historical extractions, then tests whether new field distributions remain statistically similar.Features include patterns and measurements such as tuples per page, token counts and token-type densities; a significance test determines whether the test data changed.
  • 438 comparisons contained 37 source-layout or data-format changes, of which the algorithm correctly detected 35.The evaluation monitored 27 wrappers representing 23 Web sources over ten months, with periodic query results compared against the last correct wrapper output.
  • Recall was 0.95, while precision was 0.73 and accuracy was 0.97.The system produced 13 false positives and two false negatives among the manually identified changes and comparison outcomes.
  • Compared with the earlier system, precision improved from 0.47 to 0.73 while recall remained 0.95.For the same subset, numeric features alone yielded P = 0.92 and R = 0.55, whereas patterns plus numeric features yielded P = 0.71 and R = 1.00.
  • False positives reflected improper URL tokenization, overly specific patterns from incomplete coverage, and genuine data-format or result changes.Examples include punctuation-rich URLs, units changing from km2 to sq km, and altered result distributions or field values.

3.2 Wrapper Reinduction

Wrapper reinduction identifies data on changed Web pages and uses those examples to generate new extraction rules. It combines learned content patterns with page structure and template information, achieving strong but imperfect extraction performance across sources and changes.

  • Automatic labeling: Training examples provide starting and ending patterns, while example lengths and page structure help identify candidate data fields.The method assumes the data format remains unchanged and uses supervised and unsupervised techniques.
  • Page templates: Templates are induced from token sequences appearing exactly once on every page and help distinguish correct data examples from surrounding page content.A sequence must contain at least three tokens to become part of the template.
  • Reinduction pipeline: The reinduction algorithm automatically labels data on new pages, then applies wrapper induction to generate extraction rules.Its automatic labeling stage is the focus because wrapper induction is described elsewhere.
  • Results: 277 fields were correctly identified across data sets, while 61 mistakes comprised 31 false positives and 30 false negatives.A field counted as successfully extracted when correctly identified on at least two of ten pages.
  • Results: Average extraction precision was 0.90 and recall was 0.80 for rules evaluated on test pages.Performance was good for most fields, with the STATE field of Bigbook a notable exception.
  • Limitations: For changed sources, high precision but lower recall occurred when the same field appeared in different contexts and required multiple rules.The approach extracted only a subset of examples sharing one context and ignored the rest.

4. Previous Work

Previous work spans grammar induction, relational learning, wrapper verification, and wrapper reinduction. The paper compares these approaches with DataProG and identifies differences in generalization, feature design, and dependence on negative examples.

  • Grammar induction: Grammar-induction research learns common string structure, but prior Web-domain results found that ALERGIA merged too many states and produced over-general grammars.WIL modified ALERGIA to reduce faulty merges and improved recognition in relevant Web domains.
  • Grammar induction: On wrapper-verification data, WIL1 achieved precision 0.20 and recall 0.81 using specific-token grammar induction.The comparison used wrapper-extracted examples from 26 Web sources observed on ten occasions.
  • Relational learning: FOIL learns relational clauses from positive and negative examples, but its results depended critically on the supplied negative examples and were often overly general.For weakly structured classes, it sometimes covered only single examples or found no clauses.
  • Wrapper verification: Rapture verifies wrappers using global numeric features, and HTML density alone reportedly identified almost all monitored changes, although it missed 17 changes in the comparison.The paper states that adding other features reduced Rapture’s performance.
  • Wrapper reinduction: Prior reinduction work adapted WHIRL to recognize page structure for narrow classes of simple lists and hotlists.The approach used previously extracted data and page-structure heuristics to reconstruct wrappers after structural changes.
  • DataProG comparison: DataProG uses token-level patterns and multi-level generalization, whereas earlier representations described entire fields or used character-level finite-state representations.The paper argues that coarse-grained token-level descriptions are more suitable for most Web data types.

5. Conclusion

The paper presents DataProG for learning data-field structure and applies it to wrapper verification and reinduction. Verification achieved 97% accuracy, while reinduced extraction rules successfully extracted data from test pages; tuple-list sources remain an unresolved case.

  • DataProG learns structural information about data fields from examples for wrapper verification and reinduction.Verification detects when extraction fails, while reinduction identifies new field examples for rebuilding wrappers.
  • 97% accuracy was achieved by the verification algorithm.This exceeded results reported in the authors’ earlier work.
  • The reinduction process identified many data fields that enabled automatic learning of Stalker rules.The resulting rules were validated by successfully extracting data from test pages.
  • Automatic regeneration of Stalker rules for sources returning lists of tuples remains unsupported.The authors identify combining data structure with expectations about list organization as future work.
Loading 1106.4872v1…