Information Extraction from Web Documents Based on Local Unranked Tree Automaton Inference

1 Introduction

Information extraction aims at extracting specific information from a collection of documents. One can distinguish between IE from unstructured and from (semi-) structured texts [Mus­ lea, 1999]. Extracting information from web documents be­ longs to the latter category and gains importance [Levy et a!., 1998]. These documents are not written in natural language, but rather involve explicit annotations such as HTMLIXML tags to convey the structure of the information, making the methods tuned towards natural language unusable.

While special query languages exist [Bry and Schaffert, 2002; XQL, 2002], their use is time consuming and re­ quires nontrivial skill. As argued in [Muslea et a!., 2001; Kushmerick, 2000], there is a need for systems that learn to extract information from a few annotated examples (wrap­ per induction). Several machine learning techniques for in­ ducing wrappers have been proposed. Examples are multi­ strategy approaches [Freitag, 2000] and various grammatical inference techniques that induce a kind of delimiter-based patterns [Muslea eta!., 2001; Freitag and McCallum, 1999; Freitag and Kushmerick, 2000; Soderland, 1999; Freitag, 1997; Hsu and Dung, 1998; Chidlovskii eta!., 2000]. All these methods treat the document as a string of characters.

Structured documents such as HTML and XML docu­ ments, however, have an explicit tree structure. In [Kosala et a!., 2002b; 2002a], it is argued that one can better exploit this tree structure and use tree automata [ Comon eta!., 1999]. The document tree is converted in a ranked binary tree and k­ testable tree automata [Rico-Juan eta!., 2000] are induced and then used for the extraction task. Typically in a IE task from structured documents, there is some structural context close to the target. After linearisation in a string, this context can be arbitrarily far away, making the learning task very dif­ ficult for string based methods. While binarisation may also increase the distance between the context and the target, they remain closer, and the learning task should be easier. This is confirmed by the experiments in [Kosala et a!., 2002b; 2002a]. If distance between the relevant context and the target is indeed a main factor determining the ability to learn an appropriate automaton, then an algorithm inducing a wrapper directly from the unranked tree should perform even better. This path is pursued in the current paper. As in [Kosala et a!., 2002b; 2002a] user intervention is lim­ ited to annotating the field to be extracted in a few rep­ resentative examples. String based methods require sub­ stantially more user intervention, such as splitting the doc­ ument into small fragments, and selecting some of them for use as a training example, e.g. [Soderland, 1999]; the manual specification of the length of a window for the pre­ fix, suffix and target fragments [Freitag and McCallum, 1999; Freitag and Kushmerick, 2000], and of the special tokens or landmarks such as">" or";" [Freitag and Kushmerick, 2000; Muslea et a!., 200 I].

The rest of the paper is organized as follows. Section 2 provides some background on unranked tree automata and their use for IE. Section 3 describes our methodology and introduces our unranked tree inference algorithm. Results are described in Section 4, related work in Section 5. Section 6 concludes.

2 Preliminaries

Grammatical inference and information extraction. Grammatical inference (also called automata induction, grammar induction, or automatic language acquisition) refers to the process of learning rules from a set of labeled ex­ amples. The target domain is a formal language (a set of strings over some alphabet ~) and the hypothesis space is a family of grammars. The inference process aims at find­ ing a minimum automaton (the canonical automaton) that is compatible with the examples. There is a large body of work on grammar induction, for a survey see e.g. [Murphy, 1996; Parekh and Honavar, 1998].

In grammar induction, we have a finite alphabet ~ and a formal language L ~ ~·. Given a set of examples in L (S+)

and a (possibly empty) set of examples not in L (S- ), the task is to infer a deterministic finite automaton (DFA) that ac­ cepts the examples in s+ and rejects those in s-. In [Freitag, 1997], an IE task is mapped into a grammar induction task. A document is converted into a sequence of tokens (from :E). Examples are transformed by replacing the token to be ex­ tracted by the special token x . Then a DFA is inferred that accepts all the transformed examples. In our case, a docu­ ment is converted into a tree and the token to be extracted (at a leaf) is replaced by the special token x. Then a tree auto­ maton is inferred that accepts all the transformed examples. When using the learned automaton, a similar transformation is done. Each token that is a candidate for extraction is in tum replaced by x. The token replaced by x is extracted iff the transformed document is accepted by the automaton.

Unranked tree automata. Some existing algorithms for string automaton induction have been upgraded to ranked tree automaton induction (e.g. [Rico-Juan eta/., 2000; Abe and Mamitsuka, I997]) 1 · By converting documents (which are unranked) into binary trees (which are ranked), tree auto­ maton induction can be used for IE as shown in [Kosala et a/., 2002b]. The present work avoids binarisation and uses unranked trees. Unranked tree automata have been studied since the late 60's, see e.g. [Briiggemann-Klein eta/., 2001] for a survey. To our knowledge, algorithms for inducing them do not yet exist. This paper is a first step in this direction.

An unranked label is a label with a variable rank (arity). Thus the number of children is not fixed by the label. Given a set V of labels in an unranked alphabet, we can define yT, the set of all ( unranked) trees, as follows:

• a is a tree where a E V .
• a( u1 , 0 0 0 , Un) is a tree, where a E V and each Ui is a tree.

An unranked tree automaton (UTA) is a quadruple (V, Q, Cl., FS), where V is a set of unranked labels, Q is a finite set of states, F S ~ Q is a set of final (accepting) states, and Cl. is a set of transitions where each transition is of the form v(e) -+ q, where v E V, q E Q, and e is a regular expression over Q.

A bottom up UTA processes trees bottom up. When a leaf node is labeled v and there is a transition v(e) -+ q such that e matches the empty string, then the node is assigned state q. When an internal node is labeled v, its children have been assigned states q1 , ... , qn, and there is a transition v(e) -+ q such that the string q1 , 0 0 · , qn matches the regular expression e, then the node is assigned state q. A tree is accepted if the state of its root is assigned an accepting state q E F S.

3 Approach and algorithm

Preprocessing. Fig. 1 shows a representative task. For dealing with text nodes, we follow the approach described in [Kosala et a/., 2002b]: we replace most text nodes by CDATA 2 , making an exception for so-called distinguishing context, specific text that is useful for the identification of the field of interest. E.g., the text "Organization:" may be relev­ ant for the extraction, hence this text should not be changed into CDATA. In each data set, at most one text field is identi­ fied as distinguishing context. It is found automatically using the approach described in [Kosala et a/., 2002b].

1 Ranked: the label determines the number of children.

2 See Fig. 2 for an example.

Approach. Our approach for information extraction has the following characteristics:

• Strings stored at the text nodes are treated as single la­ bels. If extracted, the whole string is returned.
• One automaton is learned for one type of field to be ex­ tracted, e.g., the field following "Organization".
• In examples used during learning, one target field (a text node) is replaced by x. A document gives rise to several examples when several targets occur.

The learning phase proceeds as follows:

• Replace in the examples the target by "x", the distin­ guishing context(s) (if present) by "ctx" and all other text fields by CDATA.
• Map examples to trees and learn a tree automaton.

The extraction phase repeats for all candidate targets:

• Map the document to a tree and replace the candidate target by "x", the distinguishing context(s) (if present)

by "ctx" and all other text fields by CDATA.

• Run the tree automaton; if the tree is accepted, then out­ put the original text of the node labeled with x.

3.1 Local unranked tree automaton inference algorithm

Preliminaries. A partition of a set S is a set of dis­ joint nonempty subsets of S such that the union of the subsets is S. The height of a tree is defined as: height( v) = 1 and height( v( t 1 , ... , tn)) = 1 + max(height(tr), ... ,height(tn)). Ift = l(tr, ... ,tn) then the ti are called subtrees oft, and subtrees of t i are also sub­ trees oft. When a tree tis "cut off'' at level k, this means all subtrees at level k become leaves. Thus the height of the cut­ offtree can be at most k. Given a tree t , the set of roots rk(t) is the singleton containing t cut off at k; the set of forks f k ( t) contains all subtrees oft of height at least k, cut off at k; and the set of subtrees s k ( t) contains all subtrees oft of height at most k. Roughly, these sets respectively collect all subtrees ofheight kat the top, in the middle, and at the bottom oft. See [Rico-Juan eta/., 2000] for a formal definition.

Example 1 Lett = a(b(a(b,x)),c) then r1 (t) = {a}. h(t) = {a(b ,c),b(a),a(b,x)}. ands1(t) = {b,x,c} .

Algorithm 1 Local unranked tree inference algorithm Input: Positive examples (set T) and an integer kc > 1. Output: An unranked tree automaton (V, Q, ~. FS). 1: FS = F = S = 0; 2: for each t E T do 3: t' = convertJabels(t) 4: F=FU/2(t') %2-forks · 5: S = S U s1 (t') % !-subtrees 6: FS = FS U r1 (t') % !-root 7: end for 8: Q=FSU{rl(f)I/EF}US 9: D.= {v(E)-+ vlv E S} 10: P = partition(F) II : for each (v, Str) E P do 12: if v = v., and the length of the shortest string in Str >= kc then 13: e = k_contextual(kc, Str) %a DFA 14: else if v = v., then 15: e = k_contextual(2, Str) %a DFA 16: else 17: e = * % accepts any sequence 18: end if 19: ~=~U{v(e)-+v} 20: end for

The algorithm. We have designed a procedure, which is shown in Algorithm 1, to learn an unranked tree automaton from a set T of positive examples. The inferred automaton is "local" in the sense that it identifies a tree with its 2-forks as defined above. Note that DTDs for XML do the same [Murata eta/., 200 1]. In addition to the input T, it takes as additional parameter a positive integer kc > 1, which is the parameter for the k_contextual subroutine that it calls.

In a first for-loop, our algorithm collects all 2-forks, !­ subtrees and 1-roots. The latter become final states. However, before these steps, the node labels of each input tree t are re­ written using the function convertlabels(t). This function (Algorithm 2) rewrites node labels. The label v of the root of a subtree is changed into Vx if that subtree contains a "x" and into Vctx if that subtree contains a "ctx". The effect is that the special labels are remembered up to the root 3 .

Algorithm 2 convertJabels(t)

Input: A tree t = v(lt, ... , tn) . Output: A tree t' 1: t~ = convertJabels(t1), . .. , t~ = converLlabels(tn) 2: if :li : t~ has Iabell., or x then 3: t' = Vx ( t~ , ... , t~) 4: else if :li : t~ has labellct:z: or ctx then 5: t' = Vctx(t~, ... , t~) 6: else 7: t' = t 8: end if

Algorithm 3 k_contextual(k, Str)

Input: An integer k > 1 and set of strings Str over I: Output: A k-contextual DFA (I:, Q, ~. FS) . 1: Q = FS = ~ = 0; 2: U = {#k- 1 s#ls E Str,# ¢I:} 3: Grams= {sis is a substring ofu, u E U, lsi= k} 4: for each 9 E Grams do 5: Let 9 = uv with lui = 1 and I vi = k - 1 6: Q = Qu {v} 7: ifv = v'# then 8: FS=FSU{v} 9: end if 10: ~ = ~ u { uv -+ v} II: end for

Next, the states are collected (the 1-root, the !-subtrees, and the 1-roots of the forks) in Q, the transitions are initial­ ized with one transition for each !-subtree and the 2-forks are partitioned according to the label of the forks' root. The latter results in a set of pairs ( v, Str) with Str a set of se­ quences, each sequence being the children of a fork. E.g., {a, { (b, c), (b, c, c)}} represents two forks with root label a.

In the second for-loop, the k_contextual algorithm (Al­ gorithm 3) [Muggleton, 1990; Ahonen, 1996] is used to learn a deterministic finite automaton (DFA) that can be used as the representation of the regular expressions e to be used in the transitions v(e) -+ q of the UTA. As an illustration, consider an input string ab for k = 3. The value of U is ##ab# and one obtains F S = {b#} and .6. = {##a -+ #a, #ab -+ ab, ab# -+ b# }, where# is a distinguished label that is not in~- It is capable of identifying in the limit any k-contextual string automaton, a subset of the finite automata, from posit­ ive examples only. In principle, we could use any string auto­ maton inference algorithm for this purpose (see e.g. [Murphy, 1996; Parekh and Honavar, 1998] for others). We choose the k_contextual algorithm because it is efficient, simple, and works well in practice.

3 As a result, the tree automaton is not purely local.

An element ( v, Str) of the partition gives all positive ex­ amples for a particular label v. The regular expression e cap­ tures the regularity in these examples (the document content model in XML terminology). To obtain sufficient generaliz­ ation, we decided, after some experimentation, to distinguish three cases. If all children of a Vx node are long enough, we construct a DFA using the k-contextual algorithm with k-value kc, otherwise with value 2. For other labels (either a Vctx label or an original label), we ignore the content of the children and accept any sequence (the regular expression "*").

Using a result of [Muggleton, 1990], it is quite straight­ forward to make an incremental version of Algorithm 1. We omit it here due to lack of space. Using a basic result of [Angluin, 1980], we can prove:

Theorem 1 Every unranked tree language that is definable by a local unranked tree automaton with k-contextual regular expressions is identifiable in the limit, from positive examples only, by our algorithm.

Example 2 Applying the Algorithm I on the tree of Ex­ ample I for kc = 2, we obtain:

• t' = a.,(b.,(a.,(b,x)),c)
• n(t') ={a.,}
• F= h(t') = {a.,(b.,,c), b.,(a.,), a.,(b,x)}
• S = s1(t') = {b, x, c}.
• FS ={a.,}
• Q ={a.,, b.,, b, x, c}
• Pl = {a.,,{(b.,,c),(b,x)}}
• P2 = {b.,, {(a.,)}}
• DFAl : ~ = {#,bx -t bx; bx,C -t Cj c,# -t #; #,b -t b; b,x -t x; x,# -t #}, Q = {bx,c,#,b,x}, FS = {#}.
• DFA2: ~={#,ax-tax; ax,# -t #}, Q ={ax,#}, FS = {#}.
• transitions:

• bE S: b(t:) -t b
• X E S : x(e) -t X
• c E S : c(t:) -t c
• Pl:ax(DFAl)-tax
• P2: bx(DF A2) -t bx

4 Experimental results

We evaluated our method on two semi-structured data sets commonly used in IE research (available online from http://www.isi.edurmuslea!RISE/): a collection of web pages containing people's contact addresses (the Internet Address Finder (IAF) database) and a collection of web pages about stock quotes (the Quote Server (QS) database). For each dataset, there are two tasks; they are the extraction of al­ ternative and organization fields in the IAF dataset and of the date and volume fields in the QS dataset. Each data­ set consists of 10 documents. The number of fields to be extracted is respectively 94 (IAF-organization), 12 (IAF­ alt.name), 24 (QS-date), and 25 (QS-vol). We choose these datasets because they are benchmark datasets that are com­ monly used for research in IE; hence they allow us to com­ pare results. In order to provide a close comparison, we use the same train and test splits as in [Freitag and Kush­ merick, 2000]. In addition, they require the extraction of a whole leaf node (our algorithms are designed for that task).

Moreover, the results obtained so far [Muslea eta!., 1999; Hsu and Chang, 1999] indicate that they are difficult tasks. In fact one of the authors in [Muslea et at., 1999] has tried to build a hand-crafted extractor given all available documents from the QS dataset and achieved only 88% accuracy (or re­ call in our criteria below). We also test our method on a signi­ ficantly reduced Shakespeare XML dataset (available online from http://www.ibiblio.org/bosak/). We use the same train­ ing and test set as in [Kosala eta!., 2002b]. The task on this dataset is to extract the second scene from one act in a partic­ ular play.

We apply the commonly used criteria of IE research for evaluating our method. Precision P is the number of cor­ rectly extracted objects divided by the total number of extrac­ tions, while recall R is the number of correct extractions di­ vided by the total number of objects present in the answer template. The F1 score is defined as 2PR/(P + R), the harmonic mean of P and R. Table 1 shows the results we obtained as well as those obtained by some current state-of­ the-art string-based methods: an algorithm based on Hidden Markov Models (HMMs) [Freitag and McCallum, 1999], the Stalker wrapper induction algorithm [Muslea et at., 2001] and BWI [Freitag and Kushmerick, 2000]. We also include the results of the k-testable algorithm in [Kosala et a!., 2002b] which works on ranked trees. The results of HMM, Stalker and BWI are taken from [Freitag and Kushmerick, 2000]. All tests are performed with 10-fold cross validation following the splits used in [Freitag and Kushmerick, 2000], except in the small Shakespeare dataset which uses 2-fold cross valida­ tion. Each split has 5 documents for training and 5 for testing. We refer to Section 5 for a description of these methods.

Table 1 shows the best results of the unranked method with a certain kc (cross-validation on one fold of 50% random training and test examples.) As can be seen, our method is the only one giving optimal results.

Table 2 shows the value of k and kc used respectively by the k-testable and the unranked algorithm. It is well­ known that when learning from positive examples only, there is a problem of over-generalization. Our algorithm re­ quires a cross-validation on the value of kc to avoid over­ generalization.

Algorithm 1 runs in time O(cn), where n is the total num­ ber of nodes in the training examples and c is a constant. It takes an average time between 19 and 26 ms in a 1. 7 Ghz Pentium 4 PC for Algorithm 1 to learn an example in the IAF and QS datasets.

5 Related work

The IE work for (semi-) structured texts can be divided into systems built manually using a knowledge engineering ap­ proach, e.g. [Hammer eta!., 1997] and systems built (semi-) automatically using machine learning techniques or other al­ gorithms. The latter are called wrapper induction methods. We briefly survey them.

The three systems referred to in Table 1 learn wrappers based on regular expressions. BWI [Freitag and Kushmerick, 2000] uses a boosting approach in which the weak learner learns a simple regular expression with high precision but low recall. The HMM approach [Freitag and McCallum, 1999] learns a hidden Markov model; it solves the problem of es­ timating probabilities from sparse data by using a statistical technique called shrinkage. This model has been shown to achieve state-of-the-art performance on a range of IE tasks. Stalker [Mus lea et a!., 200 1] induces extraction rules that are expressed as simple landmark grammars, a class of fi­ nite automata; it performs hierarchical extraction guided by a manually built embedded catalog tree that describes the struc­ ture of the fields to be extracted.

Several techniques based on naive-Bayes, two regular lan­ guage inference algorithms, and their combinations for IE from unstructured texts are described in [Freitag, 1997]. WHISK [Soderland, 1999] learns extraction rules based on a fotm of regular expression patterns with a top-down rule in­ duction technique. [Chidlovskii et al., 2000] describe an in­ cremental grammar induction approach; they use a subclass of deterministic finite automata that do not contain cyclic pat­ terns. The SoftMealy system [Hsu and Dung, 1998] learns separators that identify the boundaries of the fields of interest. [Hsu and Chang, 1999] propose two classes of SoftMealy ex­ tractors: single pass, which is biased for tabular documents such as QS data (they reach up to 97% recall), and multi pass, which is biased for tagged-list document such as IAF data (they reach up to 57% recall). We cannot really compare results because the experimental setting is different.

All above methods use algorithms for learning string lan­ guages and require some manual intervention. HMMs and BWI require to specify a window length for the prefix, suffix and the target fragments. Stalker and BWI require to spe­ cify special tokens or landmarks such as ">" or";". Soft­ Mealy extractors in [Hsu and Chang, 1999] requires to choose between single and multi pass bias.

In [Kosala et al., 2002b], the document is converted in a ranked (binary) tree and an algorithm is used that induces a k-testable tree automaton. However, as binarisation increases the distance between target and distinguishing context, large k are needed and the resulting automaton is precise but does not generalize enough (Table 1). In [Kosala et al., 2002a], the same authors generalize the obtained automaton by se­ lectively introducing wild-card labels. This gives some mod­ est improvement in recall but does not solve the problem. Our unranked tree automaton induction algorithm does.

The most apparent limitation of our method is that it can only output a whole text node. To overcome this, it could be extended with a second step where string based methods are used to extract part of the text node. For example, to extract the substring "the web" from the whole string "Data on the web" (Fig. 2). Another limitation is that our method only output a single field (slot) in one run.

Finally, a disadvantage that is not apparent from the res­ ults reported above, is that when the identification of target fields does not require dependencies between nodes in the tree but can rely on a local pattern (e.g., the field to be extracted is always surrounded by specific delimiters), our tree based method needs more examples to learn the same extraction rule as methods that automatically focus on local patterns. In­ tuitively, more variations in further-away nodes need to be ob­ served before these variations are considered irrelevant. This is simply an instance of the well-known trade-offbetween the generality of a hypothesis space and the efficiency with which the correct hypothesis can be extracted from it.

Some other approaches that exploit the structure of the doc­ uments are: WL 2 [Cohen et al., 2002], a logic-based wrapper learner that uses multiple (string, tree, visual, and geometric) representations of the HTML documents. In fact, WL 2 is able to extract all four tasks in the IAF and QS datasets with 100% recall; and wrappers [Sakamoto et al., 2002] that identify a field with a path from root to leaf, imposing conditions on each node in the path.

6 Conclusion

We have presented an algorithm for the inference of a local unranked tree automaton with k-contextual regular expres­ sions and have shown that it can be used for IE from struc­ tured documents. Our results confirm the claim of [Kosala et al., 2002b] that utilizing the tree structure of the documents is worthwhile for structured IE tasks. Whereas the latter work transforms the positive examples into binary ranked trees, we use them directly as unranked trees. Our results are optimal for the previously considered benchmarks, substantially im­ proving upon the published results of other string and tree based methods and are a strong indication that unranked tree automata are much better suited than ranked ones for struc­ tured IE tasks.

Possible future work includes experiments with larger and more difficult datasets, adapting tree automata for multi slot extraction in one run, and a more formal analysis of the al­ gorithm.

Acknowledgements

We thank Nicholas Kushmerick for providing us with the datasets used for BWI experiments and anonymous reviewers for their very valuable comments. This work is supported by the FWO project query languages for data mining. Hendrik Blockeel is a post-doctoral fellow of the Fund for Scientific Research of Flanders.