
## 4.1.2 Relational Learning

As a sequence of n tokens, a pattern can also be viewed as a non-recursive n**-ary predicate.**
Therefore, we can use a relation-learning algorithm like FOIL (Quinlan, 1990) to learn them.

Given a set of positive and negative examples of a class, FOIL **learns first order predicate**
logic clauses defining the class. Specifically, it finds a discriminating description that covers many positive and none of the negative examples.

We used Foil.6 with the no-negative-literals option to learn patterns describing several different data fields. In all cases the closed world assumption was used to construct negative examples from the known objects: thus, for the Bigbook **source, names and addresses were**
the negative examples for the phone number class. We used the **following encoding to**
translate the training examples to allow foil.6 to learn logical relations. For each data field, FOIL learned clauses of the form

## Data Field(A) := P(A) Followed By(A, B) P(B), (3)

as a definition of the field, where A and B **are tokens, and the terms on the right hand side**
are predicates. The predicate followed by(A, B**) expresses the sequential relation between**
the tokens. The predicate P(A) allows us to specify the token A **as a specific token (***e.g.*,
John(A**)) or a general type (***e.g.*, Upper(A), Alpha(A**)), thus, allowing FOIL the same**
multi-level generalization capability as DataProG.

We ran Foil.6 on the examples associated with the Bigbook **(see Tables 2–3). The**
relational definitions learned by Foil.6 from these examples **are shown in Table 10.**
In many cases, there were similarities between the definitions learned by FOIL and the patterns learned by DataProG**, though clauses learned by FOIL tended to be overly** general. Another problem was when given examples of a class with little structure, such as names and book titles, FOIL tended to create clauses that covered single examples, or it failed to find any clauses. In general, the description learned by FOIL depended critically on what we supplied as negative examples of that field. For example, if we were trying to learn a definition for book titles in the presence of prices, FOIL would learn that something that starts with a capitalized word is a title. If author names were supplied as negative examples as well, the learned definition would have been different. Therefore, using FOIL
in situations where the complete set of negative examples is **not known or available, is** problematic.

## 4.2 Wrapper Maintenance

Kushmerick (Kushmerick, 1999) addressed the problem of wrapper verification by proposing an algorithm Rapture **to verify that a wrapper correctly extracts data from a Web page.** In that work, each data field was described by a collection of global features, such as word count, average word length, and density of types, *i.e.***, proportion of characters in the** training examples that are of an HTML, alphabetic, or numeric type. Rapture **calculated** the mean and variance of each feature's distribution over the training examples. Given a set of queries for which the wrapper output is known, Rapture **generates a new result for** each query and calculates the probability of generating the **observed value for every feature.** Individual feature probabilities are then combined to produce an overall probability that the wrapper has extracted data correctly. If this probability exceeds a certain threshold,