Wrapper Induction for Information Extraction

1 Introduction

The Internet contains many sources of relational data. For example, when queried with a name, email address services return (name, email) pairs. But because these sites are designed for people, the content is formatted for human browsing (e.g. an HTML page), rather than for use by a program. Therefore, software systems us­ ing such resources (e.g., heterogeneous database systems [Chawathe et al., 1994; Arens et al., 1996] or software agents [Etzioni & Weld, 1994; Kirk et al., 1995]) must translate query responses to relational form.

Wrappers are commonly used as such translators. A wrapper is a procedure, specific to a single information resource, that translates a query response to relational form. Wrappers are typically hand-coded; unfortunately, hand-coding is tedious and error-prone.

We seek an automated solution to this problem of con­ structing wrappers. Natural language processing has been used for similar information-extraction tasks; see [Cowie & Lehnert, 1996] for a recent summary. But many information resources do not exhibit the rich gram­ matical structure such techniques are designed to ex­ ploit. Moreover, linguistic approaches tend to be slow, while ideally wrappers should execute quickly, because they are used on-line to satisfy users' queries.

Wrapper induction is a new technique for automati­ cally constructing wrappers. Our system learns a wrap­ per by generalizing from example query responses. A PAC model bounds the number of examples needed to NETbot, Inc. 4530 Union Bay Pl. NE, Suite 208 Seattle WA 98105 USA bobd@netbot.com generate a satisfactory wrapper. The inductive algo­ rithm requires an oracle to label examples; we solve this labeling problem [Etzioni, 1996] by composing oracles from heuristic knowledge, and we demonstrate that our system degrades gracefully with imperfect heuristics.

We identify HLRT, a class of wrappers which is effi­ ciently learnable, yet expressive enough to handle numer­ ous actual Internet information resources. HLRT is de­ signed for resources that display their content in a tabu­ lar layout. HLRT wrappers scan their input for substrings that delimit the information to be extracted. Though our focus is on Internet resources, these learned delim­ iters need not be HTML tags, but can be arbitrary text.

HLRT corresponds essentially to a class of finite-state automata, so wrapper induction is similar to FSA in­ duction (e.g., [Angluin, 1982]) . Since FSAs run in linear time, HLRT satisfies the desire that wrappers be fast. However, since wrappers are used for parsing (rather than just classification) , the learned FSA must have a specific state topology. Existing FSA induction algo­ rithms do not make such guarantees, so we have devel­ oped a new algorithm targeted specifically at HLRT.

We make the following contributions. First, we for­ malize the wrapper construction problem as that of in­ ductive generalization. Second , we identify the HLRT wrapper class, which is efficiently learnable yet reason­ ably expressive. Third, we show how to compose the required oracle from (possibly imperfect) heuristics.

We proceed as follows. In Sec. 2, we describe wrap­ pers. In Sec. 3, we cast wrapper construction as induc­ tive generalization; we then spell out this framework by describing how to learn HLRT (Sec. 4) , applying the PAC framework (Sec. 5), and presenting a modular approach to building oracles (Sec. 6). Sec. 7 provides an empiri­ cal evaluation of our approach. Finally, Sec. 8 describes related work.

2 Wrappers

A wrapper is a procedure for extracting tuples from a particular information source. Formally, a wrapper is a function from a page 1 to the set of tuples it contains.

1 We use the term page generically, referring to whatever query response is returned by an information resource.

For example, consider a fictitious information resource that provides a tabular list of countries and their tele­ phone country codes. Suppose that in response to a query, the resource responds as displayed in Fig. 1(a), which was rendered from the HTML shown in (b). Many kinds of wrappers could be written; we consider wrap­ pers that use the positions of particular strings to delimit the extracted text. From (b), it appears that this re­ source renders tuples by surrounding countries with <B> and </B>, and country codes with <I> and </I>. 2 So one candidate wrapper relies on these four delimiters.

But note that this simple left-right (LR) strategy fails , because not all occurrences of <B>· · ·</B> indicate a coun­ try. However, the string <P> can be used to distinguish the head of the page from the tuples proper. Similarly, <HR> separates the last tuple from the tail. Fig. l(c) shows ExtractCCs, a wrapper based on this more sophis­ ticated head-left-right-.tail (HLRT) approach.

We focus on wrappers that are structurally similar to ExtractCCs. Fig. 1( d) shows the template for HLRT wrap­ pers. Note that instantiating the template with the six strings (<P>,<HR>,<B>,</B>,<I>,</I>) yields ExtractCCs.

2 Note that though this example involves HTML tags such as <B>, our system does not require the use of HTML; any text fragment (such as just B>) that reliably delimits the attribute is acceptable.

Formally, an HLRT wrapper for a domain with K at­ tributes per tuple is encoded as a vector of 2K +2 strings (h, t, £1, r1 , ... , £K, r K ). One string (h) marks the end of the header, another (t) marks the start of the tail, and two strings (fk and rk) delimit each of the K attributes.

We focus on HLRT, but alternatives abound. Fig. 2 illustrates a partial hierarchy of wrapper classes. LR is less expressive than HLRT; for example, the country/ code resource can be wrapped by HLRT but not LR. BELR's b and e mark the .Qeginning· and ~nd of each tuple, rather than page's body. In the extreme, arbitrary finite-state automata could be used as wrappers. In [Kushmerick, 1997], we analyze this hierarchy in detail.

3 Constructing wrappers by induction

The wrapper construction problem is the following: given a supply of example query responses, learn a wrapper for the information resource that generated them. For the country /code resource, the problem is to induce the Extr­ actCCs procedure, given a supply of HTML pages similar to that shown in Fig. 1(b) .

Induction thus provides a natural framework for for­ malizing wrapper construction. Induction is the task of generalizing from labeled examples to a hypothesis, a function for labeling instances. For our problem:

Instances correspond to pages-e.g. Fig. l(b).

Labels correspond to pages' tuples-e.g. the example page is labeled as containing {(Congo,242) , (Egypt ,20) , (Belize,501), (Spain,34)} .

Hypotheses correspond to HLRT wrapper template parameters- e.g. (<P>,<HR>,<B>,</B>,<I>,</I>) is the encoding of ExtractCCs.

Oracles correspond to sources of example query re­ sponses and their labels. We split the traditional ora­ cle (which returns a single labeled instance) into two parts. PageOracle generates example pages, and La­ beiOracle produces correct labels for these instances. PageOracle is specific to a particular information re­ source, while LabeiOracle is composed from heuristics that are reusable across domains.

PAC analysis is used to terminate the learning pro­ cess, so the system takes as input accuracy (E) and confidence ( 8) parameters.

With this framework in place, we now present the wrapper induction algorithm; see Fig. 3. Wrapper in­ duction proceeds by accumulating a set £ of labeled ex­ ample pages. On each iteration, BuildHLRT is called with£, which returns wrapper w. Learning stops when w satisfies the PAC bound. In Sees. 4- 6, we describe the algorithm's main components:

BuildHLRT constructs an HLRT wrapper from a set of labeled example pages; see Sec. 4.

Pr[E(w)<t:] > 1-8 isaPAC-theoreticterminationcon­ dition, testing whether enough examples have been seen to be confident that a satisfactory wrapper has been learned; see Sec. 5.

Label Oracle is a function from a page to a label. In Sec. 6 we describe how to compose a correct labeling oracle from (possibly imperfect) heuristic knowledge.

4 Building HLRT wrappers

BuildHLRT takes as input a set of labeled pages, and returns an HLRT wrapper that is consistent with each labeled page. A wrapper is consistent with a labeled page if it generates the label for the page. Fig. 4 shows the BuildHLRT algorithm.

BuildHLRT reasons about the conditions that must hold if wrapper (h,t,£1,r1, ... ,eK, rK) is to be consis­ tent. For example, in Fig. 1(b), the string <I> is a valid value for £2, because <I> actually precedes every instance of the second attribute. Such constraints apply to each rk, and to each ek fork> 1.

BuildHLRT is complicated by the fact that £1 , t, and h interact. For example, to determine whether <B> is acceptable as £1 (even though the head and tail contain <B>), BuildHLRT must find an hand t such that <B> does in fact reliably mark the start of the first attribute. In this case, h = <P> and t = <HR> are satisfactory. Lines {a­ d) in Fig. 4 capture the constraints that £1 , t, and h must satisfy. BuildHLRT examines all possible combinations of el, h, and t, stopping when it finds values that jointly satisfy these constraints.

To summarize, BuildHLRT iterates over all choices for the 2K +2 delimiters, stopping when a consistent wrap­ per is encountered. BuildHLRT's search is made more efficient by decomposing the constraint satisfaction prob- BuildHLRT(labeled pages [ = { . . . , (Pn , Ln), . .. } ) Note that each label Ln partitions page Pn into its attributes, separated by the strings between tuples and between the K attributes within a tuple.

fork= 1 to K rk <--- any common prefix of the strings following each (but not contained in any) attribute k fork= 2 to K lk +--- any common suffix of the strings preceding each attribute k for each common suffix £1 of the pages' heads for each common substring h of the pages' heads for each common substring t of the pages' tails if (a) h precedes £1 in each of the pages' heads; and (b) t precedes £1 in each of the pages' tails; and (c) t occurs between h and £1 in no page's head; and (d) £1 doesn't follow t in any inter-tuple separator then return (h, t, £1, r1, . .. , lK, r K)

lem into three independant subproblems: finding values for (1) the rk; (2) the ek (k> 1) ; and (3) h, t, and el.

In [Kushmerick, 1997], we prove that: {1) BuildHLRT is sound (if BuildHLRT returns a wrapper, then it is con­ sistent) and complete (if a consistent wrapper exists, Bui­ ldHLRT finds it); and {2) under reasonable assumptions, BuildHLRT runs in time O(KNMS 3 ), where each tuple has K attributes, the shortest of the N example pages has length S, and M is maximum number of tuples in any single example.

Appendix A formally describes the conditions under which an HLRT wrapper is consistent with a labeled page.

5 PAC analysis

PAC analysis answers the question, 'How many exam­ ples must a learner see to be confident that its hypoth­ esis is good enough-i.e., to be probably approximately correct?'; see [Kearns & Vazirani, 1994] for an introduc­ tion. A PAC model defines an error metric over hy­ pothesis: E( w) is the probability that hypothesis w will incorrectly label the next instance. The learning task is then analyzed in order to bound the number of exam­ ples which ensure that Pr[E(w) > E] < 8, for any given accuracy parameter f and confidence parameter 6. In [Kushmerick, 1997], we prove the following theorem.

Theorem 1 (HLRT sample complexity) Suppose BuildHLRT(£) returns wrapper w, where£ contains col­ lectively T tuples, each with K attributes. If

For example, with f = 6 = 0.1, K = 4, and an average of 5 tuples/page, BuildHLRT must examine at least 72 examples to satisfy the PAC criteria.

This bound is relatively tight compared to typical PAC results. For example, the number of possible HLRT wrap­ pers is infinite, but our bound does not depend on the number of wrappers. Thus clearly the stated bound is tighter than obtainable under simple PAC models (e.g., [Valiant, 1984; Blumer et al., 1987]), in which sam­ ple complexity grows with the number of hypotheses. The bound is also tighter than obtainable using Vapnik­ Chervonenkis analysis [Haussler, 1988]. To understand these results, recall that BuildHLRT is essentially com­ puting common prefixes and suffixes of sets of strings, which are highly constrained after relatively few exam­ ples; see [Kushmerick, 1997] for a detailed discussion.

6 Composing oracles

A key to induction is an oracle that labels examples. So far we have assumed that LabeiOracle is provided as in­ put . We now describe how to compose LabeiOracle from modular heuristic knowledge, which we call recognizers. A recognizer finds instances of a particular attribute on a page. For example, a country name recognizer would identify the four countries contained in Fig. 1 (b)'s HTML. These recognized instances are then corroborated to la­ bel the entire page. For example, given a recognizer for countries and another for country codes, corroboration produces an oracle that labels pages containing pairs of these attributes .

Corroboration is trivial if each recognizer is perfect. 3 But an important feature of our approach is that it han­ dles imperfect recognizers. Recognizers are either perfect (accept all positive instances and reject all negative in­ stances of their target attribute), incomplete (reject all negative instances but reject some positive instances), unsound (accept all positive instances but accept some negative instances), or unreliable (reject some positive instances and accept some negative instances).

We require that each recognizer be annotated with the kind of error it makes. We expect this annotation to be natural for many kinds of recognizers. For example, a company name recognizer based on Fortune-500 data is incomplete, while a country code recognizer accepting any digit sequence is unsound. The intent is that rec­ ognizers are reusable across domains; a company name recognizer, for example, can be used with any informa­ tion resource displaying companies.

Recall that LabeiOracle is a function from a page to a label for the page. A label is an array, where rows cor­ respond to tuples, and columns are attributes. A recog­ nizer is a function from a page to a set of instances (sub­ sequences of the page). The set of recognized instances is a column of the overall label array. The corroboration problem, then, is to build the entire label array from the individual columns. Note that the attributes' ordering within tuples is not part of the input; the corroboration algorithm must determine this ordering.

3 Wrappers are needed even with perfect recognizers, be­ cause recognizers might be slow, while wrappers must be fast.

The basic idea of corroboration is that the location of some instances greatly constrains the possible location of others. Suppose recognizer A is unsound and identifies an instance at position 10- 20, while perfect recognizer B finds an instance at 14- 16. Since attributes never overlap, the A at 10-20 must be a false positive (FP) and thus must be ignored, while the B at 14- 16 is a true positive (TP).

In the remainder of this section, we describe corrobo­ ration by walking through an example, present the Cor­ rob corroboration algorithm, and describe how our work is extended to handle imperfect recognizers.

Example. Fig. 5 extends the country/code example to include an additional attribute, the country's capital. 4 Corroboration begins by noting the type of error made by each recognizer: in this simple example, assume the recognizer for the codes is perfect, but the country recog­ nizer is incomplete and the capital recognizer is unsound.

Next, note that since the Code recognizer is perfect, all Code instances are TPs. Thus Code can be simply copied to the label array. The incomplete Ctry column is almost as easy: it is copied verbatim, but Code is used to align each Ctry instance. This leaves a "hole" in the Ctry column. Next, the corroborator processes the iln­ sound Cap column. 5- 7 must be a FP, because were it a TP, Code would have included an additional instance prior to 5. Next, since 19- 25 overlaps with Code's 18- 20, 19-25 must be a FP. Since 22- 28 is the only remaining possibility for the first tuple's Cap instance, 22- 28 must be a TP. However, for the second tuple, there is no way to choose between 42- 48 and 44- 49: one must be a TP and the other a FP, but there is no way to decide. Corrob­ oration thus uses 42- 48EB44- 49, indicating that exactly one of the two instances is a TP. Finally, corroboration rejects 59- 65 because it overlaps with 58- 60.

The Corrob algorithm. Fig. 6 shows Corrob, an al­ gorithm for corroborating imperfect recogniz;rs, fo~ th_e case when at least one recognizer is perfect. As mdi­ cated in the example, Corrob builds the label array by

4 The indices in this example do not match Fig. l(b).

5 People can be used as perfect recognizers, though we seek to automate wrapper construction as much as possible.

Corrob ( recognizers { . .. , Rk , ... } , instances { ... , IJ, ... } ) N t t . Ik . th ·th . o a wn: i ts e J- mstance recognized by Rk . A +- BuildArray( {Ij : Rk is perfect or incomplete}) for each IJ such that Rk is unsound or unreliable if IJ is possibly a TP (based on the TPs in A) , then m +- RowOf(IJ , A) Am,k +- Am,k EB IJ return A BuildArray(necessarily TP instances { ... , Jj , ... }) Build array with each IJ installed in the correct cell. RowOf(possibly TP instance IJ , array A)

Determine the row m of A to which IJ belongs, which is always determined when at least one Rk is perfect.

Figure 6: The Corrob algorithm.

first installing instances recognized by perfect or incom­ plete recognizers. These TPs are then used to categorize the remaining instances as either necessarily FPs (mean­ ing they can be ignored), or possibly TPs (meaning they are inserted using 'EB'). In [Kushmerick, 1997], we de­ scribe Corrob in more detail and prove that it is correct.

Handling mistakes. Note that Corrob's output might contain attributes that are missing ('?' indicates at­ tributes falsely rejected by their recognizers) or ambigu­ ous ('EB' indicates under-constrained attributes). But BuildHLRT assumes that LabeiOracle produces a perfect label. We now describe how to extend our work to han­ dle this discrepancy.

Missing attributes require only minor changes to Build­ HLRT: the algorithm must simply generalize from fewer examples. For example, recall the original country/ code resource in Fig. 1. Suppose that corroboration yields a label that is correct except that the country Congo is missing. In this case, when learning f 1 , the algo­ rithm generalizes from just the three occurrences of </I><BR>.ij.<B> 6 that precede the recognized instances of the first attribute, and the algorithm may well fail to generate the correct wrapper. Only if the first coun­ try name is correctly recognized on a subsequent exam­ ple page will BuildHLRT realize that f 1 must be a suf­ fix of <HTML><TITLE>Sorne Country· · ·Codes</B><P>.lJ.<B> as well as of </I><BR>.ij.<B>.

The PAC model must also be extended to accommo­ date missing attributes. To do so, we generalize Thm. 1 so that, instead of assuming exactly N head and tail and T left and right delimiter examples, the model counts the actual numbers, based on the non-missing attributes. So, in the previous example, there are four examples for 12 , r2 and t, but only three for 11 and r 1 , and zero for h.

Ambiguity requires more substantial changes. There are two kinds of ambiguity. First, as described earlier, Corrob uses 'EB' to indicate that more than one recog­ nized instance is consistent with a particular cell in the label array. Second, recall that Corrob must determine the ordering of attributes within tuples. But the recognized instances may be consistent with more than one ordering. For example, in Fig. 5, a valid label exists for the ordering (Cap, Ctry, Code) as well as for (Ctry, Code, Cap) . (We previously ignored ordering ambiguity to simplify the presentation of Cor rob.)

6 '.ij.' indicates a carriage return character.

We extend BuildHLRT to handle both types of ambigu­ ity as follows. An ambiguous label actually corresponds to a set of unambiguous labels, one for each way to re­ solve each ambiguity. Exactly one such label is correct; the rest either contain FPs or corresponds to an incorrect attribute ordering. Faced with ambiguity, BuildHLRT it­ erates over each possibility, stopping when a wrapper can be induced.

Clearly the number of such possibilities grows expo­ nentially in the number of ambiguities. In practice this growth is tolerable for both unsound and incomplete rec­ ognizers, even with very high error rates; see Sec. 7. However, Corrob is impractical for unreliable recogniz­ ers, because the number of ambiguities grows quickly with an unreliable recognizer's error rate.

We extend the PAC model to handle ambiguous labels by accounting for situations in which BuildHLRT consid­ ers an incorrect way to resolve a label's ambiguity, and yet a consistent wrapper exists anyway. For example, in Fig. 5(d), if the second tuple's Cap attribute is actu­ ally 42- 48 rather than 44- 49, but BuildH LRT tries 44- 49 first and successfully finds a wrapper, then BuildHLRT has probably made a mistake. Similarly, if BuildHLRT considers the ordering (Cap, Ctry, Code) before (Ctry, Code, Cap), then BuildHLRT is probably wrong if it finds a consistent wrapper.

We model this effect Ly assuming that such a situation happens with probability at most J..L per opportunity, and thus the left-hand side of the bound in Thm. 1 is multi­ plied by (1-J..L)R, where R is the number of opportunities that a mistake of this type could have occurred as Build­ HLRT was enumerating the possible labels. In practice, we find that J..L is extremely close to zero and R is rela­ tively small , and thus ambiguity has a negligible effect on the PAC results. In [Kushmerick, 1997], we compare this noise model to others in the PAC literature.

7 Empirical evaluation

In this section, we present preliminary evidence demon­ strating the feasibility of HLRT learning. Our Lisp im­ plementation requires between 4 and 40 SGI Indy CPU seconds per example page, depending on the domain. Normalizing for the number of attributes (K) and the size of the example pages, our system requires about 0.21 CPU sec. per attribute per KB of example data.

Our first experiment verifies the utility of the HLRT bias. Learnability aside, can a significant fraction of in­ teresting information resources be wrapped by HLRT? We surveyed 100 Internet resources selected randomly from an independent organization's index (search. corn), and found that 48% can be wrapped by HLRT. We take this result to be evidence that HLRT is genuinely useful.

Our second experiment measures the robustness of the system to the recognizers' error rates. We tested our sys­ tem on (i) the OKRA email service, okra.ucr.edu/okra; and (ii) the BIG BOOK telephone directory, bigbook. corn.

By hand, we constructed perfect recognizers for each attribute; OKRA has four attributes and BIGBOOK has six. As a baseline, we ran our system with these perfect recognizers. We then increased the error rates up to 40% (creating both incomplete and unsound recognizers for each attribute) and increased the number of imperfect recognizers from zero until all but one were imperfect. 7 We tested our system using two termination conditions: (a) we ran the system until the PAC criteria was satisfied (for t = b = 0.1); and (b) we required that the learned wrapper be 100% correct on a suite of test pages.

Fig. 7 shows the number of pages needed to induce a wrapper, as a function of the error rate, for each ter­ mination condition, and for each domain. Each curve within a graph represents a different number of imperfect recognizers. For example, the points marked "perfect" represent trials in which all recognizers are perfect, while the points marked "30% error rate of each recognizer" on the "2 imperfect recognizers" curves indicate trials in which two of the recognizers are imperfect (yielding either 30% FPs or 30% FNs) while the remaining rec­ ognizers are perfect . Thus in each graph, increasing the abscissa or examining curves with additional imperfect recognizers corresponds to trials in which the recognizers make more mistakes.

Figs. 7(i- ii.b) indicate that, from a practical perspec­ tive, relatively few examples are needed before the sys­ tem learns the correct wrapper; across all conditions, about 4.9 examples suffice for OKRA and 29 for BIGBOOK. We conclude that the number of examples required is small enough that HLRT wrapper induction is practical, even for extremely high recognizer error rates.

Figs. 7(i- ii.a) show that the PAC bound is relatively loose. Across all conditions, about 105 examples are needed required to satisfy the PAC criteria. Thus the PAC bound is too loose by about an order of magnitude. We conclude that the current PAC model is too weak to tightly constrain the induction process. Nevertheless, since wrapper construction is intended to be an off-line process, the bound is not so loose as to be useless.

Finally, we have developed WIEN (pronounced "Vi­ enna") , a jyrapper induction environment. Using a Web browser, a user shows WIEN an example information re­ source page, and then uses the mouse to label the page. WIEN then tries to learn a wrapper for the resource. When the user shows WIEN a second example, it uses the learned wrapper to automatically label the new ex­ ample. The user then corrects any mistakes, and WIEN generalizes from both examples. This process repeats until the user is satisfied. WIEN provides a complete im­ plementation of BuildHLRT, though the user is assumed to label pages perfectly, so WIEN implements neither at­ tribute recognition nor corroboration.

7 Recall that Corrob is impractical for unreliable recogniz­ ers and requires at least one perfect recognizer.

WIEN and the experimental data are available at www . cs .washington . edu/hornes/nick/research/wrappers .

8 Related work

As suggested at the outset, wrapper construction is motivated by the software engineering issues involved with deploying software systems that rely on external information resources; examples include [Chawathe et al., 1994; Etzioni & Weld, 1994; Arens et al., 1996; Kirk et al., 1995]. While data interchange protocols (e.g. KQML [Finin et al., 1994]) have been proposed to address these issues, they require cooperatioh on the part of in­ formation providers, and such cooperation is rare.

From a formal perspective, in Sec. 1 we discussed the relationship between HLRT and FSA induction.

From an application perspective, our work is similar to [Ashish & Knoblock, 1997]. Their system learns a more expressive wrapper class than HLRT, but relies on many heuristics that are specific to HTML. In contrast, our sys­ tems treats HTML tags just as ordinary text. Moreover, their system requires human intervention to correct its mistakes, while our corroboration process is intended to correct mistakes automatically. A second related appli­ cation is SHOPBOT [Doorenbos et al., 1997] . Though in many respects SHOPBOT is more ambitious, its wrapper language is less expressive than HLRT.

Finally, our recognition knowledge is similar to work on semantically labeling natural text, such as the MUC-6 "Named Entity" task [DARPA, 1995], though relatively little work has been done on corroborating multiple such knowledge sources.

9 Conclusions

Wrapper induction is a new technique for automatically constructing wrappers. We have made three contri­ butions. First, we have formalized the wrapper con­ struction problem as induction. Second, we have de­ fined the HLRT bias, which is efficiently learnable in this framework. Third, we have shown how to use heuristic knowledge to compose the algorithm's oracle. Though our work has involved primarily Internet information re­ sources, we expecte that our results are applicable to similar information-extraction tasks in other domains.

We intend to extend our framework in several ways. In addition to the biases shown in Fig. 2, we want to de­ sign wrappers that can handle non-tabular pages, such as pages organized hierarchically. The research issues in­ volve exploring the tradeoff between expressiveness and learnability. We also hope to tighten the PAC model so it is more useful in practice as well as more predictive of observed learning curves.

Acknowledgments. This research is funded in part by ONR Grant N00014-94-1-0060, by NSF Grant IRI9303461, by ARPA / Rome Labs grant F30602-95-10024, and by a gift from Rockwell International Palo Alto Research. Thanks to the UW CS&E AI group, Steve Minton and David Smith for helpful discussion, and to Boris Bak for help with the search. com survey.

A HLRT consistency conditions

In this Appendix, we list the conditions under which HLRT wrapper W = { h, t, £1, r1, . .. , fK, TK} outputs label L = { ((b1,1, e1,1), ... , (b1,K, e1,K)), .. . , ((bM,1, eM,1), . . . , (bM,K, eM,K))} for page P. This notation indicates that that P contains M tuples having K attributes each, where the kili attribute of the mili tuple .Qegins at index bm,k of P and ~nds at em,k· Note that L partitions Pas follows('·' indicates concatenation): P = So,wA1,1-S1 ,1 ' A1 2· · · · ·S1 K-1·A1 wS1 K" · · · ·AM 1·SM 1 ·AM 2· · · · · s~ K-1-AM ~-SM K: The' Am k are the att~ibute'values: Am,, k = P(bm,k, ~m,k]· The 'sm,k separate the tuples, and attributes within a tuple: Sm,k = P[em,k> bm,!.+d (except that So ,K = P[O, b1,1], SM,K = P[eM,K, JPJ], and Sm,K := Sm+1,o = P[em,K, bm+1,1]).

Under this notation, w is consistent with P and L iff:

1. the ek immediately precede their attributes
2. (So,K/h)/1!1 f= H 1\ 'im,k>l ISm,k-1/fkl = 0
3. the rk follow (but don't occur within) their attributes 'im,k rk·((Am,k'Sm,k )/rk) = Sm,k
4. h occurs in the head and t occurs in the tail So,K /h f= H 1\ SM,K jt i- U
5. t never precedes 1!1 in an inter-tuple separator V'm<M Sm,K /t f= U => lf1l > It · (Sm,K /t)l
6. t doesn't occur between h and 1!1 in the head
7. (So ,K/h)jt f= U => lf1 l > it ·((So,K/h)/t)i
8. t precedes 1!1 in the tail

SM,K /1!1 t= H => it ·(SM,K/t)i > lfdSM,K/1!1)1

(where s/s' is the substring of s after the first occurrence of s', with sfs' = H indicating that s doesn't contain s').