Active Learning with Strong and Weak Views: A Case Study on Wrapper Induction

1 Introduction

Labeling training data for learning algorithms is a tedious, er­ ror prone, time consuming process. Active learning addresses this issue by detecting and asking the user to label only the most informative examples in a domain. In this paper, we focus on Co-Testing [Mus lea et al., 2000], an active learn­ ing technique for domains with multiple views; i.e., domains with disjoint sub-sets of features, each of which is sufficient for learning. Co-Testing is a 2-step iterative algorithm that (1~ u.ses the fe~ available labeled examples to learn a hypoth­ esis m each VIew and (2) queries (i.e., asks the user to label) examples on which the views predict a different label. Such queries are highly informative because they correct mistakes made by one of the views: whenever the views disagree, at

least one of them must be wrong.

Co-Testing was successfully applied to wrapper induction [Muslea et al., 2000], an industrially important application. In wrapper induction the goal is to learn rules that extract the relevant data from collections of Web pages that share the same underlying structure; e.g., extract the book titles and prices fro~ amazon. com. For wrapper induction, Co-Testing uses two VIews: the sequences of tokens that precede and fol­ low the extraction point, respectively. The extraction rules learned in these views are finite automata that consume an item's prefix or suffix within the page, respectively.

The main limitation of existing Co-Testing algorithms [Musl~a et al., 2000; 2002a] is that they are designed to use only VIews that are adequate for learning, thus being unable to also exploit imperfect views that would permit a faster con­ vergence to the target concept. To address this problem, we ~xtend the m~lti-view learning framework by introducing the Idea of leammg from strong and weak views. By definition, ~ strong view consists of features that are adequate for learn­ mg the target concept; in contrast, in a weak view one can only learn a concept that is more general or specific than the target concept. We introduce a novel algorithm, Aggressive Co-Testing, that exploits both strong and weak views with­ out additional data engineering costs. We also describe a case study on wrapper induction, which shows that Aggressive Co­ Testmg clearly outperforms state-of-the-art algorithms.

To illustrate the idea of strong and weak views, consider the task of extracting fax numbers from a directory of restau­ rant Web pages such as Zagat. The two wrapper induction views described above are strong views because each of them is (typically) sufficient to extract the item of interest [Muslea et al., 2000]. In addition to these two strong views, we can also exploit a view that consists of tokens within the item to be extracted. In this view, we learn the grammar " ( Number ) Number - Number" that describes the content of the fax numbers. This additional view is a weak view because the grammar above represents a concept more general than the target one; i.e., it cannot discriminate between fax and phone numbers that appear within the same Web page.

Aggressive Co-Testing for wrapper induction works as fol­ lows: first, it uses a few labeled examples to learn a rule in each view (i.e., one weak and two strong rules). Then it queries an unlabeled example on which the two strong rules extract different strings, both of which are inconsistent with the content-based grammar. Each such query is likely to rep­ rese~t a mistake not only in one, but in both strong views, thus leadmg to faster convergence. We use a collection of 33 dif­ ficu~t extraction tasks to show that using the weak view dra­ m~ti~ally reduces the need for labeled data: compared with existmg state of the art active learners, our novel algorithm requires between 45% and 81% fewer labeled examples.

2 Related work

The idea of exploiting complementary information sources (i.e., types of features) appears in various multi-strategy learners. Of particular interest are two recent papers [Kush­ merick et al., 2001; Nahm and Mooney, 2000] in which the authors use sets of features that clearly do not have the same expressive power. This work can be seen as learning from strong and weak views, even though it was not formalized as such, and it was not used for active learning.

Kushmerick et al. [2001] focus on classifying the lines of text on a business card as a person's name, affiliation, address, phone number, etc. In this domain, the strong view consists of the words that appear on each line, based on which a Naive Bayes text classifier is learned. In the weak view, one can ex­ ploit the relative order of the lines on the card by learning a hidden Markov Model that predicts the probability of a par­ ticular ordering of the lines on the business card (e.g., name followed by address, followed by phone number).

This weak view defines a class of concepts that is more general than the target concept: all line orderings are possi­ ble, even though they are not equally probable. The order of the text lines cannot be used by itself to accurately classify the lines. However, when combined with the strong view, the ordering information leads to a classifier that clearly outper­ forms the stand-alone strong view [Kushmerick et al., 200 1].

Another algorithm that can be seen as learning from strong and weak views is DISCOTEX [Nahm and Mooney, 2000], which extracts job titles, salaries, locations, etc from com­ puter science job postings to the newsgroup austin . jobs. DISCOTEX proceeds in four steps: first, it uses RAPIER [Califf and Mooney, 1999] to learn extraction rules for each item of interest. Second, it applies the learned rules to a large, unlabeled corpus of job postings and creates a database that is populated with the extracted data. Third, by text mining this database, DISCOTEX learns to predict the value of each item based on the values of the other fields. For example, it maydiscoverthat"IF the job requirements include C++ and CORBA THEN the development platforms include Windows". Finally, when the system is deployed and the RAPIER rules fail to extract an item, the mined rules are used to predict the item's content.

In this scenario, the RAPIER rules represent the strong view because they are sufficient for extracting the data of interest. In contrast, the mined rules represent the weak view because they cannot be learned or used by themselves. Furthermore, as DISCOTEX discards all but the most accurate of the mined rules, which are highly-specific, it follows that the weak view can be used to learn only concepts that are more specific than the target concept. Nahm and Mooney show that these mined rules improve the extraction accuracy by capturing informa­ tion that complements the RAPIER extraction rules.

3 Preliminaries

In this section we first explain the main idea behind Co­ Testing algorithms [Muslea et al., 2000; Muslea, 2002], and then we describe the strong and weak views that we use for wrapper induction.

3.1 Background: the Co-Testing approach

Figure 1 provides a formal description of the Co-Testing fam­ ily of algorithms. Given a base learner .C, a set L of labeled

• Given: - a base learner C

• -a learning problem with features V={a1 , a2 , .. . ,aN}
• -two views Vl and V2, where V=V1UV2 and VlnV2=0
• the sets L and U of labeled and unlabeled examples
• number N of queries to be made

LOOP for N iterations

• -use£, Vl(L), and V2(£) to create classifiers h1 and h2
• -let ContentionPoints = { u E U I h1(u) f. h2(u)}
• -IF ContentionPoints is empty THEN quit
• -let Query= SelectQuery(ContentionPoints)
• remove Query from U and ask for its label l
• add labeled Query to L
• CreateOutputHypothesis( h1, h2 )

Figure 1: Co-Testing algorithms repeatedly query examples for which the two views make a different prediction.

examples, and a set U of unlabeled ones, Co-Testing works as follows: first, it learns the classifiers h1 and h2 by apply­ ing the algorithm .C to the projection of the examples in L onto the two views, Vl and V2. Then it applies h1 and h2 to all unlabeled examples in U and detects the set of contention points, which are unlabeled examples for which h1 and h2 predict a different label. Finally, it asks the user to label one of the contention points and repeats the whole process.

The various members of the Co-Testing family differ from each other with two respects: the strategy used to select the next query, and the manner in which the output hypothesis 1 is constructed. In other words, each Co-Testing algorithm is uniquely defined by the choice of the heuristics Select­ Query() and CreateOutputHypothesis(). In turn, these two heuristics depend on the properties of both the application do­ main and the base Ieamer .C.

We consider here two types of query selection strategies:

• random: randomly choose a contention point. This strategy is appropriate for base learners that lack the capability of estimating the confidence of their predictions.
• max-confidence: choose the contention point on which both h1 and h2 make the most confident prediction. This strategy is appropriate for high accuracy domains (e.g., wrapper induction), in which there is little or no noise. On such tasks, discovering examples that are misclassi­ fied "with high confidence" translates into queries that "fix big mistakes," thus leading to fast convergence.

We also consider two "output hypothesis" heuristics:

• winner-takes-all: the output hypothesis is the one learned in the view that makes the smallest number of mistakes over the N queries.
• majority vote: examples are labeled according to the pre­ diction of most views (requires at least three views).

3.2 Wrapper induction: the strong views

In wrapper induction, each item of interest is described by three strings of variable length: the item's content, together with its prefix and suffix within the document. As this is not a typical machine learning representation in which an exam­ ple's description in each view consists of a fixed set of fea­ tures , we describe here in detail how Co-Testing can be ap­ plied to wrapper induction. As a first step, we introduce the basic ideas in STALKER [Muslea et al., 2001], which is the wrapper induction algorithm that we use as base Ieamer.

1 Once training is completed, the output hypothesis is used to pre­ dict the label of all new, unseen examples.

Consider the illustrative task of extracting phone numbers from Web pages similar to the one shown in Figure 2. In STALKER, an extraction rule consists of a start rule and an end rule that identify the beginning and the end of the item, respectively. Given that start and end rules are extremely sim­ ilar, we describe here only the former. In order to find the beginning of the phone number, one can use the start rule

This rule is applied forward, from the beginning of the doc­ ument, and it ignores everything until it finds the string Phone: < i >. For a slightly more complicated extraction task, in which toll-free numbers appear in italics and the other ones in bold, one can use a disjunctive start rule such as

Rl' = either SkipTo "Phone :<i>" or SkipTo "Phone :<b>"

An alternative way to detect the beginning of the phone number is to use the start rule

which is applied backward, from the end of the document. R2 ignores everything until it finds "Fax" and then, again, skips back to the first open parenthesis.

As shown in [Muslea et at., 2001], the above extraction rules can be learned based on user-provided examples of items to be extracted. Note that Rl and R2 represent de­ scriptions of the same concept (i.e., start of phone number) in two different views. That is, the views Vl (forward view) and V2 (backward view) consist of the sequences of tokens that precede and follow the beginning of the item, respectively.

Note that both Vl and V2 represent strong views: as the Web pages to be wrapped share the same underlying struc­ ture, STALKER can be seen as uncovering and exploiting this underlying structure for extraction purposes. Consequently, both the forward and backward rules are expected to extract the relevant data from any page.

3.3 Wrapper induction: the weak view

Besides the two strong views above, one can also use a third, content-based view, which describes the actual item to be ex­ tracted. For example, when extracting phone numbers, one may exploit the fact that they can be described by a simple grammar: " ( Number ) Number- Number". Similarly, when extracting URLs, one can take advantage of the fact that a typical URL starts with the string "http: I lwww. ",ends with the string". html", and contains no HTML tags.

In this paper, we use the following features to describe the content of each item to be extracted:

• the length range (in tokens) of the seen examples. For in­ stance, phone numbers in the format" ( Number ) Number - Number" consist of six tokens (i.e., the three numbers, the dash, and the two parentheses).
• the token types that appear in the training examples. This feature consists of the set of the most specific wildcards (e.g., Number, AllCaps, etc) that match the tokens en­ countered in the item to be extracted. For example, in the phone number case, this list consists of two wild­ cards: Number and Punctuation. The complete hierar­ chy of wildcards is described in Figure 3.
• a start-pattern such as "http : I lwww . " or" (Number)", which describes the beginning of the item of interest.
• an end-pattern such as "AlphaNum. html" or "Number - Number", which describes the end of the item.

In order to learn the content-based description of an item, we use as base Ieamer a simplified version of the DataPro algorithm [Lerman and Minton, 2000]. After tokenizing each of the user-provided examples of strings to be extracted, the weak-view Ieamer proceeds as follows:

• the length range is determined by finding the examples that contain the largest and the smallest number of tokens;
• the token types are obtained by going through the tokens that appear in the labeled examples and adding to the set of "seen types" the most specific wildcard that covers it.
• a start-pattern of length one consists of the most specific wildcard that covers the first token in all labeled exam­ ples; if all examples start with the same token, such as "(" in the phone number example, the actual to­ ken is preferred to the most specific wildcard. A start­ pattern of length k is generated by repeating the proce­ dure above for the first, second, ... , up to k-th position.
• the end-pattern is learned in the same manner as the start pattern, but using the k tokens at the end of the item.

Note that, unlike the forward and backward views, the content-based view is a weak view because, for many extrac­ tion tasks, this view does not uniquely define the item of interest. This is a consequence of the fact the view uses only fea­ tures that describe the content of each item. For Web pages that contain several items with similar descriptions, such as multiple email addresses, phone numbers, URLs, or names, the content-based grammar cannot discriminate between the various items with similar descriptions.

4 Aggressive Co-Testing

We introduce now Aggressive Co-Testing, which provides a framework for naturally exploiting both strong and weak views. For Aggressive Co-Testing, the contention points are defined as unlabeled examples on which the strong views pre­ dict a different label. For the wrapper induction problem, Ag­ gressive Co-Testing uses the two strong and one weak views described earlier (i.e., the forward, backward, and content­ based views). Consequently, the contention points are unla­ beled documents from which the forward and backward rules extract different strings. Aggressive Co-Testing uses the la­ beled examples to learn one hypothesis in each view, detects the contention points, and then uses the following heuristics:

• SelectQuery() returns the contention point on which both strong rules violate the largest number of constraints learned in the weak view; e.g., the extracted strings are longer than the seen examples, the start- and end- pat­ terns do not match, etc. This is a max-confidence query­ ing strategy because the content-based view is maxi­ mally confident that the strong rules extract incorrect strings.
• CreateOutputHypothesis() uses the three views for ma­ jority voting. That is, given a new, unseen document, both strong rules are applied to it; if they extract the same string, this string is returned as the answer. Oth­ erwise the "winner" is the strong rule that violates the fewest constraints learned in the weak view. Note that this flexible approach allows Co-Testing to use the most appropriate strong rule for each document in the dataset.

To better understand how Aggressive Co-Testing works, we contrast it now with Naive Co-Testing [Muslea et al., 2000], which uses only the two strong views. Both algo­ rithms detect the contention points in the same manner, but they use different query selection strategies and output hy­ potheses. More precisely, Naive Co-Testing randomly queries one of the contention points and generates a winner-takes-all output hypothesis (i.e., the rule that makes the fewest mis­ takes on the queries extracts the data from all documents).

5 Empirical Evaluation

The algorithms in the experimental comparison

In this empirical evaluation we compare the following algo­ rithms: Aggressive Co-Testing, Naive Co-Testing, Query­ by-Bagging, and Random Sampling. The first two algo­ rithms were described in the previous section; Random Sam­ pling, which is used as strawman, is identical with Naive Co­ Testing, except that it randomly queries one of the unlabeled examples instead of one of the contention points.

Query-by-Bagging [Abe and Mamitsuka, 1998] is the only single-view active Ieamer that can be used in a straightfor­ ward manner with STALKER and, more generally, for wrap­ per induction. 2 Even Query-by-Boosting [Abe and Mamit­ suka, 1998], which is similar to Query-by-Bagging, cannot use STALKER as a base Ieamer: as STALKER rarely- if ever­ makes mistakes on small training sets, it eliminates the ability of the boosting algorithm to generate a diverse committee.

Query-by-Bagging is based on the idea of creating a com­ mittee of extraction rules and then querying the example on which the committee is the most split (i.e., the rules in the committee extract the largest number of distinct strings); the algorithm's actual predictions are made by majority voting the committee of rules. Query-by-Bagging generates a com­ mittee of 10 extraction rules, each of which is learned by training STALKER with examples obtained by re-sampling with replacement the original training set. We are forced to use such a small committee because of the scarcity of the training data: as STALKER is expected to train on a handful of examples, sampling-with-replacement from a few examples leads to few distinct training sets for creating the committe~!. Query-by-Bagging is run once in each view, and we report only the best results, which are obtained in the forward view.

The datasets

In order to empirically compare the algorithms above, we use the wrapper induction testbed introduced by Kushmerick [2000]. It consists of 206 extraction tasks from 30 Web-based information sources. 3 As shown in [Muslea et al., 2001], on most of these 206 tasks STALKER learns 100% accurate rules from just one or two randomly-chosen labeled exam­ ples. We consider here the 33 most difficult tasks in the testbed, which were also used in previous work on multi-view learning [Muslea et al., 2000; 2002b]:

• the 28 tasks on which 20 random examples are insufficient for learning 1 00%-accurate rules in both strong views;

2 Typical wrapper induction algorithms do not have the properties that active learners require of their base learners; e.g., the ability to evaluate the confidence of each prediction [Lewis and Gale, 1994], or to randomly sample hypotheses from the version space [Seung et al., 1992), or to generate most specific and most general extraction rules [Cohn et al., 1994] .

3 These datasets can be obtained from the RISE repository: http://www.isi.edu/~muslea/RISE/index.html.

• the five additional tasks on which, in order to learn 100%­ accurate rules in both strong views, STALKER requires a large number of random examples [Muslea, 2002].

The empirical results

For each of these 33 tasks, we use 20-fold cross-validation to compare the performance of the algorithms above. Within each fold, the algorithms start with the same two randomly­ chosen examples and then make a succession of queries. In the end, the error rate is averaged over the 20 folds.

Figure 4 summarizes the algorithms' performance over the 33 tasks. In each graph, the X axis shows the number of queries made by the algorithm, while the Y axis shows the number of tasks for which a 100% accurate rule was learned after exactly X queries. Each algorithm is allowed to make 18 queries, for a total of 20 labeled examples. By conven­ tion, the "19 queries" data point denotes tasks for which a 100% accurate rule is not learned even after 18 queries.

Aggressive Co-Testing clearly outperforms the other algo­ rithms: it makes an average of 2.43 queries over the 30 tasks that are solved with 100% accuracy; furthermore, on 11 of these 30 tasks, a single query is sufficient to learn the cor­ rect rule. In contrast, Naive Co-Testing, which comes sec­ ond, makes an average of 4.4 queries per task and converges in a single query on just four of the 33 tasks. Also note that Aggressive Co-Testing solves correctly two of the five tasks that cannot be solved by Naive Co-Testing; the other two al­ gorithms fail to solve 23 and 26 of the 33 tasks, respectively.

Even though Aggressive Co-Testing makes 45% fewer queries that Naive Co-Testing, at first glance the difference between 2.43 and 4.4 queries per task may seem small. How­ ever, one must take into account that wrapper induction is used in information agents [Knoblock et at., 2001], which typically use hundreds of extraction rules; in this context, Ag­ gressive Co-Testing makes a tremendous difference.

To put our work into a larger context, we briefly compare the results above with the ones obtained by WIEN [Kushm­ erick, 2000], which is the only wrapper induction system for which there are published results for all the extraction tasks used here. As the two experimental setups are not identical, 4 this is just an informal comparison that contrasts Co-Testing with a state-of-the-art approach to wrapper induction.

The results in [Kushmerick, 2000] can be summarized as follows: WIEN, which uses random sampling, learns the cor­ rect extraction rule on 15 of the 33 task. On these 15 tasks, WIEN requires between 25 and 90 labeled examples 5 to learn the correct rule. For the same 15 tasks, both Aggressive and Naive Co-Testing learn 100% accurate rules from at most eight labeled examples (two random plus at most six queries).

4 Instead of using cross-validation, WIEN repeatedly splits the dataset into randomly chosen training and test sets.

5 For WIEN, an example consists of a document in which all items of interest are labeled; e.g., a page with 15 labeled names repre­ sents a single example. In contrast, STALKER counts the 15 labeled strings as 15 examples. We convert the WIEN results into equiva­ lent STALKER-like ones by multiplying the number of WIEN labeled pages by the average number of item occurrences per page.

Discussion

The empirical results deserve several comments. First of all, the experiments illustrate the benefits of a framework that naturally integrates strong and weak views: Aggressive Co­ Testing exploits the strengths and mitigates the weaknesses of each individual view. For example, we do not use the weak view to identify the contention points because its mistakes may be "unfixable" (remember that in a weak view one learns a concept more general/specific than the one of interest). On the other hand, we use the weak view both to detect the highly informative contention points and to find the most appropriate strong view for each prediction.

In contrast to Aggressive Co-Testing, existing multi-view learners [Blum and Mitchell, 1998; Muslea et al., 2000] can use only the strong views, thus losing an important source of information. Similarly, single-view learners must either pool all features together or simply ignore all but one view. Note that, in practice, pooling the features together may not be a straightforward task:

• in DISCOTEX [Nahm and Mooney, 2000], the text min­ ing features (the weak view) are the extracted items, which become available only after the extraction rules are learned and applied to the unlabeled corpus.
• the main contribution of [Kushmerick et at., 2001] consists of a novel algorithm that exploits features from both the strong and weak views (i.e., the words in each text line, and the lines's order within the business card).

Second, we ran an additional experiment to determine the usefulness of the weak view with respect to each heuristic (i.e., query selection and output hypothesis). We considered two hybrid algorithms between Aggressive and Naive Co­ Testing: one uses the random and majority vote heuristics, while the other uses max-confidence and winner-takes-all; i.e., each hybrid exploits the weak view in only one of the two heuristics. Because of space constraints, we just summarize our findings: the two hybrids outperform Naive and under­ perform Aggressive Co-Testing; more precisely, they make an average of 3.0 and 3.9 queries per task, respectively. In other words, the weak view improves both the query selec­ tion and the output hypothesis.

Finally, note that on three of the 33 tasks, Aggressive Co­ Testing fails to learn 1 00%-accurate rules; in fact, on these tasks Query-by-Bagging and Random Sampling obtain more accurate rules than both Aggressive and Naive Co-Testing. This happens because, on these three tasks, the backward view is significantly less accurate than the forward one. Con­ sequently, the distribution of the queries is skewed towards mistakes of the "bad view", which are not informative for either view: the "good view" extracts the correct string any­ way, while the "bad view" is inadequate to learn the target concept. To cope with this problem, we plan to use view val­ idation [Muslea et at., 2002b], which predicts whether or not the strong views are appropriate for a particular task.

6 Conclusion and Future Work

In this paper we introduce the concepts of strong and weak views and present a novel active learner that naturally inte­ grates and exploits both types of views. In a case study on wrapper induction, we show that weak views represent a pow­ erful source of information that can be used both to detect highly informative examples and to improve the algorithm's predictions. On a set of 33 difficult extraction tasks, our novel algorithm converges by making up to 81% fewer queries than other state of the art active learners.

We intend to continue our work along several directions. First, we plan to investigate the use of weak views for semi­ supervised multi-view learning [Blum and Mitchell, 1998]. Second, we intend to extend view validation [Muslea et al., 2002b] so that it also accounts for weak views. Finally, we are interested in a theoretical analysis of learning from strong and weak views.

Acknowledgments

This material is based upon work supported in part by the De­ fense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory under contract/agreement num­ bers F30602-01-C-0197 and F30602-00-1-0504, in part by the Air Force Office of Scientific Research under grant num­ bers F49620-0 1-1-0053 and F49620-02-1-0270, in part by the United States Air Force under contract number F49620-02C-0103, and in part by a gift from the Microsoft Corpora­ tion. The U.S.Government is authorized to reproduce and distribute reports for Governmental purposes notwithstand­ ing any copy right annotation thereon. The views and conclu­ sions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of any of the above organizations or any person connected with them.