Source-linked AI summary
Automatic Wrappers for Large Scale Web Extraction
Nilesh Dalvi, Ravi Kumar, Mohamed Soliman
TL;DR
Traditional wrappers require site-level labeled examples, limiting their use for Web-scale extraction. This paper makes wrapper induction noise-tolerant by generating and ranking wrappers from noisy labels, and reports high precision and recall across more than 300 websites, with production use at Yahoo!.
Problem
Traditional wrapper-based extraction requires human-labeled examples from every site, limiting its use for Web-scale tasks such as collecting store listings.
Source: §1 · p. 1Method
Results
Experiments across more than 300 websites in multiple domains achieve very high precision and recall, and the system powers live Yahoo! search applications.
Source: §1 · p. 2Takeaways & Limitations
The framework supports Web-scale extraction without the site-level supervision required by wrapper-based techniques.
Source: §1 · p. 2The enumeration algorithms rely on a well-behaved wrapper inductor, a condition that machine-learning or already noise-tolerant inductors may not satisfy.
Source: §5 · p. 5
Abstract
from arXiv · showhide
We present a generic framework to make wrapper induction algorithms tolerant to noise in the training data. This enables us to learn wrappers in a completely unsupervised manner from automatically and cheaply obtained noisy training data, e.g., using dictionaries and regular expressions. By removing the site-level supervision that wrapper-based techniques require, we are able to perform information extraction at web-scale, with accuracy unattained with existing unsupervised extraction techniques. Our system is used in production at Yahoo! and powers live applications.
1. INTRODUCTION
Wrappers can extract structured information from script-generated webpages, but traditional methods require labels from each site, limiting web-scale use. The paper makes wrapper induction tolerant to noisy, automatically obtained labels and reports high precision and recall across more than 300 websites.
1. INTRODUCTION
- Human labeling on every store-locator site makes traditional wrappers infeasible for extracting listings across the Web.Pages from each site share structure, but the method still requires a few labeled examples from every site.Source: §1 · p. 1
- A single incorrect annotation can make traditional wrapper induction over-generalize its extraction rule.The paper illustrates this with a rule that extracts all text nodes under a table cell rather than just dealer names.Source: §1 · p. 1
- The framework uses a wrapper inductor as a black box, enumerates wrappers generated by subsets of noisy labels, and ranks them using annotation and web-publication models.Its quality score reflects both the likelihood of the noisy labels and the likelihood that a wrapper is good, guided by the web publication model.Source: §1 · p. 2
- Experiments cover over 300 websites across multiple domains and report very high precision and recall; the system powers live Yahoo! search applications.The authors also report production use at Yahoo! for large-scale information extraction from the Web.Source: §1 · p. 2
2. MODEL AND PROBLEM
The paper models extraction as inferring data types from webpages and noisy annotations, using both an annotation model and a web publication model. It formulates extraction as maximizing the probability of a type assignment given labels, while presenting single-type extraction in the main text.
2. MODEL AND PROBLEM
- The framework models label errors with an annotation model and uses a web publication model to distinguish good from bad wrappers.The section overview introduces these models before formally defining extraction.Source: §2 · p. 2
2.1 Publication and annotation models
- The web publication model generates domain webpages by choosing a schema, a rendering script, and schema elements to render.The business-listing example uses a list of name, address, and phone tuples rendered as HTML.Source: §2.1 · p. 2
- Type-specific annotators label subsets of text elements, and their errors are characterized by precision and recall.An annotator may miss true nodes or label nonmatching nodes; a dictionary-based business-name annotator can have low recall and high, imperfect precision.Source: §2.1 · p. 2
2.2 The extraction problem
- Extraction seeks the most likely type assignment X given annotations L, maximizing P(L | X)P(X).P(L | X) models annotation errors, while P(X) represents the prior probability of the assignment under the web publication process.Source: §2.2 · p. 2
- The main text presents single-type extraction, while the authors say the techniques straightforwardly extend to multi-type extraction.The paper states that Appendix A contains details and multi-type experiments; extraction may also leave uninterested node types unmapped.Source: §2.2 · pp. 2–3
3. OUR APPROACH
The approach generates candidate wrappers from subsets of noisy labels, then ranks them by how well they explain the labels and how plausible their extracted lists are. This ranking can favor a well-structured wrapper even when it misses some labels.
3. OUR APPROACH
- Enumerating subsets can produce far fewer unique wrappers than subsets, as the TABLE example reduces 32 subsets to eight wrappers.With all possible n^2 labels on an n × n table, the example inductor produces n^2 + 2n + 1 unique wrappers.Source: §3 · p. 3
- The ranking score combines the likelihood of the observed labels under a wrapper with the wrapper’s prior goodness as a list.For candidate outputs X_i, the score is P(L | X_i)P(X_i).Source: §3 · p. 3
- The label-likelihood term reflects annotator errors and recall, so wrappers matching more labels are not automatically preferred.In the example, the likelihood accounts for mistakes and correct labels, and can be lower for a wrapper if the annotator is expected to have high recall.Source: §3 · p. 3
- The wrapper prior evaluates schema size and repeating structure against domain knowledge about typical records.The example treats a regular list with an implausibly small record schema as less likely.Source: §3 · p. 3
- The example ranks the first-column wrapper highest despite its missing two labels because it has good list properties.The approach first considers wrappers induced by label subsets, then ranks the resulting candidates.Source: §3 · p. 3
4. ENUMERATION
The enumeration problem is to generate the unique wrappers induced by all subsets of labels without exhaustively calling the wrapper inductor on every subset. The paper gives a sound and complete bottom-up algorithm and a feature-based top-down algorithm that makes exactly one call per unique wrapper.
4. ENUMERATION
- The enumeration problem asks for the unique wrappers generated by label subsets in time polynomial in the label set and wrapper-space sizes.The wrapper space may be much smaller than the exponentially many subsets of labels.Source: §4 · p. 4
- A well-behaved inductor satisfies fidelity, closure, and monotonicity, properties used to enumerate wrappers efficiently.Fidelity includes the training labels in the output; closure means adding the output as training data does not change it; monotonicity preserves inclusion as labels are added.Source: §4 · p. 4
4.1 A bottom-up algorithm
- BottomUp expands label subsets and their closures; it is sound and complete and makes at most k · |L| calls for wrapper-space size k.The closure step avoids enumerating all 2^|L| subsets.Source: §4.1 · p. 4
4.2 A top-down approach
- BottomUp can require k · |L| inductor calls, motivating a feature-based top-down method with exactly k calls.The top-down method relies on wrapper features to generate the wrapper space directly.Source: §4.2 · p. 4
- For feature-based inductors, TopDown partitions labels using feature values and makes exactly k calls for a wrapper space of size k.The paper notes that both Wien and XPath have natural feature-based representations.Source: §4.2 · pp. 4–5
5. WRAPPER INDUCTORS
Section 5 analyzes WIEN’s LR wrappers and XPATH, showing both qualify as well-behaved inductors. It also expresses them as feature-based wrappers so TopDown can enumerate their wrapper spaces.
5. WRAPPER INDUCTORS
- WIEN’s LR wrappers delimit labeled examples with longest common preceding and following strings; HLRT variants add context strings.The analysis of LR wrappers also extends to HLRT and related variants.Source: §5 · p. 5
- LR and XPATH are both shown to be well-behaved wrapper inductors.The section establishes this for LR and XPATH separately.Source: §5 · p. 5
- Both inductors can be expressed as feature-based wrappers, allowing TopDown to enumerate their wrapper spaces.For LR, the feature set can be large, but subdivision can be implemented without constructing it.Source: §5 · p. 5
- XPATH induction starts from //* and specializes it while maintaining recall of 1; the example selects text from the second column of each row in the first table.The method uses paths through the parsed HTML tree.Source: §5 · p. 5
- The framework’s well-behaved-inductor assumption may not hold for machine-learning extractors or for inductors that already handle noise.Source: §5 · p. 5
6. RANKING MODEL
The ranking model scores each candidate wrapper using both the likelihood of its labels under an annotation model and the structural goodness of its extracted list. It estimates structural goodness from record segments using domain-informed features.
6. RANKING MODEL
- A wrapper’s score is P(L | X)P(X): label likelihood under the annotation model multiplied by the structural goodness of its output list.The score depends on the wrapper’s output, not its language.Source: §6 · p. 5
- The annotation model treats node-label decisions independently and characterizes them by r, the inclusion probability for correct nodes, and p, the complement of the incorrect-node inclusion probability.A perfect annotator has p = r = 1.Source: §6 · p. 5
- The web publication model favors structurally regular lists; using candidate nodes as record boundaries can yield shifted segments while preserving their structural similarity.The method uses target-list nodes for segmentation and compares segment structure rather than inferring a full grammar.Source: §6 · p. 6
6.1 Features
- Schema size approximates shared text attributes and maximum pairwise edit distance measures alignment; the two features’ distributions are learned from domain websites and suffice to identify good lists in the experiments.An alignment score of 0 corresponds to a perfect list.Source: §6.1 · p. 6
7. EXPERIMENTS
Across DEALERS and DISC, the noise-tolerant framework improves extraction results for both wrapper inductors, while enumeration is much more efficient than naive search. Experiments also examine ranking components and performance across annotator precision and recall settings.
7. EXPERIMENTS
- DEALERS covers 330 store-locator businesses and DISC covers 15 discography sites; correct rules were manually created, and model distributions were learned from half the websites.Source: §7 · pp. 6–7
7.1 Wrapper enumeration
- TopDown and BottomUp require far fewer wrapper calls than naive enumeration; TopDown finishes under a second for most sites, while BottomUp takes under a couple of minutes.BottomUp makes an order of magnitude more wrapper calls than TopDown.Source: §7.1 · p. 7
7.2 Ranking
- With XPATH wrappers, the noise-tolerant framework improves precision to 1 with a negligible recall drop; on the same dataset, LR accuracy is 90% versus XPATH close to 100%.On DISC, it achieves perfect precision and recall for both wrapper inductors.Source: §7.2 · p. 7
7.3 Ranking model components
- Neither ranking component alone accounts for NTW’s total accuracy; labeling-error scoring nearly reaches maximum accuracy for XPATH but helps LR much less.Source: §7.3 · p. 7
7.4 Effect of annotators
- On DEALERS with XPATH, the F1 study finds effective noise tolerance across a broad annotator precision/recall range, with modest requirements.Source: §7.4 · p. 7
8. CONCLUSIONS
The paper concludes with a framework for learning wrappers from noisy training data, combining supervised induction with domain knowledge and unsupervised grammar induction. The techniques also extend to multi-type extraction.
8. CONCLUSIONS
- The framework combines supervised wrapper induction, domain knowledge, and unsupervised grammar induction to learn wrappers from noisy training data.It is designed to accept any wrapper language and wrapper induction system.Source: §8 · p. 7
- The framework’s evaluation includes NTW accuracy as a function of annotator quality.The table caption identifies accuracy as the outcome and annotator as the varying factor; the supplied passages do not give cell values.Source: Table 1 · p. 8
A. MULTI-TYPE EXTRACTION
- The techniques presented for single-type extraction also apply to the general multi-type extraction problem.The paper presents the multi-type treatment in the appendix.Source: A. MULTI-TYPE EXTRACTION · p. 9
A.1 Methodology
The methodology extends noise-tolerant wrapper induction to multi-type extraction, where wrappers must assemble records from multiple fields. It adapts both wrapper enumeration and ranking to account for types and record structure.
A.1 Methodology
- Multi-type extraction must assemble records from multiple fields, a harder task when some fields are missing.The paper’s example is a business listing with name, address, and phone fields.Source: §A.1 · p. 9
- Enumeration passes each labeled node’s type to the wrapper inductor when enumerating multi-type wrappers.The algorithms described for single-type extraction can also be used for this enumeration.Source: §A.1 · p. 9
- Ranking multiplies the independently computed annotation-error terms across types and evaluates structural priors using record segments and type-aligned nodes.Record segments use any type as a boundary; ranking includes schema size and edit distance between segments.Source: §A.1 · p. 9
A.2 Experiments
The experiments test a multi-type name-and-zipcode wrapper on dealer pages using noisy automatic annotations. NTW achieves precision and recall close to 1, while its joint extraction maintains or slightly improves per-type accuracy relative to single-type extraction.
A.2 Experiments
- The tested inductor learns XPath rules for names and zipcodes, then assembles interleaved values into records.It returns empty results on a page if it cannot assemble records successfully.Source: §A.2 · p. 9
- The name and zipcode annotators both introduce noise, including five-digit street addresses and page-header or footer text among zipcode labels.The name annotator uses a business-name database; the zipcode annotator uses a five-digit US zipcode regular expression.Source: §A.2 · p. 9
- Noise harms multi-type extraction more sharply because an error in either type can prevent successful record assembly.The wrapper inductor learned correct rules and assembled records when given clean manual labels.Source: §A.2 · p. 9
- NTW achieves precision and recall close to 1 on multi-type extraction, while NAIVE has recall and F1 close to 0.NAIVE often learns an imperfect wrapper for at least one type and then fails to assemble records.Source: §A.2 · p. 9
- Joint NTW extraction matches single-type zipcode accuracy and yields slightly higher name accuracy.The paper attributes this to joint alignment during ranking, where annotations for each type help evaluate the other type’s wrapper.Source: §A.2 · p. 9
B. OTHER EXPERIMENTS
The other experiments include cellphone extraction on shopping websites and single-entity album-title extraction. For single entities, the method selects wrappers that extract one item per page and cover the most annotations; it learned a correct wrapper for every tested website.
B.1 Products domain
- For PRODUCTS, the task is to extract cellphones from ten shopping websites, and NAIVE and NTW show behavior similar to the DEALERS and DISC datasets.The cellphone dictionary was built from five popular brands and contained 463 models.Source: §B.1 · p. 9
B.2 Single-entity extraction
- Single-entity extraction avoids the list-extraction tension between expanding annotations to cover a list and contracting them to account for noise.Each page contains only one entity of interest, so the method does not expand annotations within a page.Source: §B.2 · p. 10
- The method enumerates distinct wrappers, discards those that extract multiple items per page, and selects the wrapper covering the most labels.This adapts the framework to noisy annotations and single-entity extraction.Source: §B.2 · p. 10
- The noise-tolerant wrapper learned the correct album-title wrapper on every DISC website tested for single-entity extraction.Some sites had multiple top-ranked correct wrappers because album names appeared in multiple consistent locations.Source: §B.2 · p. 10
C. PROOFS
The proofs establish that BottomUp exactly outputs the wrapper space and bound its wrapper-inductor calls. The appendix also gives pseudocode for BottomUp and TopDown and supplementary dataset illustrations.
C. PROOFS
- BottomUp is sound and complete, precisely outputting the wrapper space of L.The proofs also establish that the wrapper-space size equals the number of closed subsets.Source: C. PROOFS · p. 10
- If the wrapper space has size k, BottomUp makes at most k · |L| calls to the wrapper inductor.The proof relates k to the number of closed subsets.Source: C. PROOFS · p. 10
D. PSEUDOCODE
- BottomUp expands label subsets using wrapper-inductor calls and closed-set updates, while TopDown subdivides sets by attributes before inducing wrappers.The appendix provides pseudocode for both algorithms.Source: D. PSEUDOCODE · p. 11
E. SUPPLEMENTARY FIGURES
- The supplementary figures show business-listing pages, wrapper-spanned record boundaries, and the websites and albums used in DISC.Figure 7 illustrates record boundaries; Figures 8 and 9 list DISC websites and albums.Source: E. SUPPLEMENTARY FIGURES · p. 11
F. RELATED WORK
The related work contrasts domain-centric extraction with web-centric and non-wrapper approaches, and explains why noisy wrapper induction is poorly served by several existing alternatives. Grammar induction captures page structure but does not itself specify which fields to extract.
F. RELATED WORK
- Non-wrapper extraction approaches such as NLP and CRFs are source-centric and perform poorly when test data differs in characteristics from training data.The authors state that such probabilistic models cannot represent the full diversity of the web.Source: F. RELATED WORK · p. 11
- CRF-based extraction reports 60% to 80% accuracy on 10 websites, while this work reports close to 100% across more than 300 websites.The authors describe the reported CRF results as showing a fundamental limitation of that approach.Source: F. RELATED WORK · p. 12
- Grammar induction captures repeating page structure but does not identify target fields, so the authors combine its ideas with supervised wrapper induction.A grammar for repeated table rows, for example, does not specify which cell contains the business name.Source: F. RELATED WORK · p. 12
- The authors characterize their approach as domain-centric: it leverages domain knowledge and attaches types to extracted data, unlike web-centric approaches requiring separate schema matching.They describe it as achieving very high accuracy in scaling domain-specific extraction to the entire web.Source: F. RELATED WORK · p. 12
- Bagging and multi-strategy learning are poor fits because wrapper learners fit noisy labels, and even one incorrect annotation can over-generalize a wrapper.The authors note that multi-strategy learners can make the same errors and that incomplete noisy annotations prevent evaluating wrapper correctness.Source: F. RELATED WORK · p. 12