\documentstyle[jair,twoside,11pt,theapa]{article}

\input{epsf}

\jairheading{18}{2003}{149-181}{10/02}{02/03}
\ShortHeadings{Wrapper Maintenance}
{Lerman, Minton \& Knoblock}
\firstpageno{149}

\long\def\comment#1{}
\newcommand{\etc}{{\em etc.}}
\newcommand{\eg}{{\em e.g.}}
\newcommand{\ie}{{\em i.e.}}
\newcommand{\ea}{{\em et al.}}
\newcommand{\noi}{\noindent}

\begin{document}

\title{Wrapper Maintenance: A Machine Learning Approach}

\author{\name Kristina Lerman \email lerman@isi.edu \\
       \addr USC Information Sciences Institute\\
       4676 Admiralty Way\\
       Marina del Rey, CA  90292 USA
       \AND
       \name Steven N.~Minton \email minton@fetch.com \\
       \addr Fetch Technologies\\
       4676 Admiralty Way\\
       Marina del Rey, CA  90292 USA
       \AND
       \name Craig A.~Knoblock \email knoblock@isi.edu \\
       \addr USC Information Sciences Institute and Fetch Technologies\\
       4676 Admiralty Way\\
       Marina del Rey, CA  90292 USA}

%********************************************

\maketitle

%\pagenumbering{arabic}
%\setcounter{page}{93}
%\pagestyle{empty}
%\thispagestyle{empty} 


\begin{abstract}
The proliferation of online information sources has led to an increased use of wrappers for extracting data from Web sources. While most of the previous research has focused on quick and efficient generation of wrappers, the development of tools for wrapper maintenance has received less attention. This is an important research problem because Web sources often change in ways that prevent the wrappers from extracting data correctly. 
We present an efficient algorithm that learns structural information about data from positive examples alone. We describe how this information can be used for two wrapper maintenance applications: wrapper verification and reinduction. The wrapper verification system detects when a wrapper is not extracting correct data, usually because the Web source has changed its format. 
The reinduction algorithm automatically recovers from changes in the Web source by identifying data on Web pages so that a new wrapper may be generated for this source. 
To validate our approach, we monitored $27$ wrappers over a period of a year. The verification algorithm correctly discovered $35$ of the $37$ wrapper changes, and made $16$ mistakes, resulting in precision of $0.73$ and recall of $0.95$. We validated the reinduction algorithm on ten Web sources. We were able to successfully reinduce the wrappers, obtaining precision and recall values of $0.90$ and $0.80$ on the data extraction task. 
%Our results indicate that combining structural information about data with {\em a priori} expectations about page structure is a feasible approach to automatically generating wrappers.

\end{abstract}

%\tableofcontents

\section{Introduction}

There is a tremendous amount of information available online, but
much of this information is formatted to be easily read by human
users, not computer applications. 
Extracting information from semi-structured Web pages is an
increasingly important capability for Web-based software applications that
perform information management functions, such as shopping
agents~\cite{Shopbot} and virtual travel assistants~\cite{Heracles,Ambite02}, among others.
These applications, often referred to as agents, rely
on Web wrappers that extract information from semi-structured sources and
convert it to a structured format. 
Semi-structured sources are those that have no explicitly specified grammar or schema, but have an implicit grammar
that can be used to identify relevant information on  the page.
Even text sources such
as email messages have some structure in the heading that can be
exploited to extract the date, sender, addressee, title, and body
of the messages.  Other sources, such as online catalogs, have a
very regular structure that can be exploited to extract all the data
automatically.

Wrappers rely on extraction rules to identify the
data field to be extracted. Semi-automatic creation of
extraction rules, or wrapper induction, has been an
active area of research in recent
years~\cite{KLMM2001,Kushmerick97}. The most advanced of these
wrapper generation systems use machine learning techniques to learn
the extraction rules by example. For instance, the wrapper induction tool developed at USC~\cite{KLMM2001,STALKER} and commercialized by Fetch Technologies, allows the user to mark up data to be extracted on several example pages from an online source using a graphical user interface. The system then generates ``landmark''-based extraction rules for these data that rely on the page layout. The USC wrapper tool is able to
efficiently create extraction rules from a small number of
examples; moreover, it can extract data from pages that contain
lists, nested structures, and other complicated formatting
layouts.

In comparison to wrapper induction, wrapper maintenance has
received less attention. This is an important problem, because
even slight changes in the Web page layout can break a wrapper that uses landmark-based rules 
and prevent it from extracting data correctly. 
In this paper we discuss our approach to the wrapper maintenance problem, which consists of two parts: wrapper verification and reinduction. A {\em wrapper
verification} system monitors the validity of data returned by
the wrapper. If the site changes, the wrapper may extract nothing
at all or some data that is not correct. The verification
system will detect data inconsistency and notify the operator
or automatically launch a wrapper repair process. A {\em wrapper
reinduction} system repairs the extraction rules so that the wrapper works
on changed pages. 

\begin{figure}[htpb]
\epsfxsize = 3.0in 
\center{\epsffile{figures/lifecycle.eps}} 
\caption{Life cycle of a wrapper}
\label{fig:lifecycle}
\end{figure}


Figure~\ref{fig:lifecycle} graphically illustrates the entire life cycle of a wrapper. As shown in the figure, the wrapper induction system takes a set of web pages labeled with examples of the data to be extracted. The output of the wrapper induction system is a wrapper, consisting of a set of extraction rules that describe how to locate the desired information on a Web page. The wrapper verification system uses the functioning wrapper to collect extracted data. It then learns patterns describing the structure of data. These patterns are used to verify that the wrapper is correctly extracting data at a later date. If a change is detected, the system can automatically repair a wrapper by using this structural information to locate examples of data on the new pages and re-running the wrapper induction system with these examples. 
At the core of these wrapper maintenance applications is a machine learning algorithm that learns structural information about common data fields. 
In this paper we introduce the algorithm, {\sc DataProG}, and describe its application to the wrapper maintenance tasks in detail.
Though we focus on web applications, the learning
technique is not web-specific, and can be used for data validation in general.

Note that we distinguish two types of extraction rules: landmark-based rules that
extract data by exploiting the structure of the Web page, and content-based
rules, which we refer to as content patterns or simply patterns, that exploit the structure of the field itself. 
Our previous work focused on learning landmark
rules for information extraction~\cite{Muslea01}. The current work shows that augmenting these rules with content-based patterns provides a foundation for sophisticated wrapper maintenance applications.

\section{Learning Content Patterns}
The goal of our research is to extract information from semi-structured information sources. This typically involves identifying small chunks of highly informative data on formatted pages (as opposed to parsing natural language text). 
Either by convention or design, these {\em fields} are usually structured: phone numbers, prices, dates, street addresses, names, schedules, {\em etc.} 
Several examples of street addresses are given in Fig.~\ref{fig:examples}. Clearly, these strings are not arbitrary, but share some similarities.
The objective of our work is to learn the structure of such fields. 


\begin{figure}[htpb]
\center{
\small {
  4676 Admiralty Way\\
  10924 Pico Boulevard\\
  512 Oak Street\\
  2431 Main Street\\
  5257 Adams  Boulevard
  } 
  }
\caption{Examples of a street address field}
\label{fig:examples} 
\end{figure}



\subsection{Data Representation}
\label{sec:datarep}

In previous work, researchers described the fields extracted from Web
pages by a character-level grammar \cite{GoanEtAl96}
or a collection of global features, such as the number of words
and the density of numeric characters \cite{Kushmerick99}. We
employ an intermediate word-level representation that balances
the descriptive power and specificity of the character-level
representation with the compactness and computational efficiency
of the global representation. Words, or more accurately tokens,
are strings generated from an alphabet containing different types
of characters: alphabetic, numeric, punctuation, {\em etc}. We use the
token's character types to assign it to one or more syntactic
categories: alphabetic, numeric, {\em etc}. These categories form a
hierarchy depicted in Fig.~\ref{fig:hierarchy}, where the
arrows point from more general to less general categories. A
unique specific token type is created for every string that appears in at
least $k$ examples, as determined in a preprocessing step. The
hierarchical representation allows for multi-level generalization.
Thus, the token ``Boulevard'' belongs to the general token types
{\sc Alphanum} (alphanumeric strings), {\sc Alpha} (alphabetic
strings), {\sc Upper} (capitalized words), as well as to the
specific type representing the string ``Boulevard''. This
representation is flexible and may be expanded to include domain
specific information. For example, the numeric type is divided into categories that include range information about the number --- {\sc Large} (larger than 1000), {\sc Medium} (medium numbers, between 10 and 1000) and {\sc Small} (smaller than 10)--- and number of digits: $1-$, $2-$, and $3-$digit. Likewise, we may explicitly include knowledge about the type of information being
parsed, \eg, some $5$-digit numbers could be represented as {\sc zipcode}.
%% Figure here

\begin{figure}[htbp]
\epsfxsize = 2.6in 
\center{\epsffile{figures/token_hierarchy2.eps} 
\caption{Portion of the token type syntactic hierarchy}} 
\label{fig:hierarchy}
\end{figure}


We have found that a sequence of specific and general token types is
more useful for describing the content of information than the character-level finite state
representations used in previous work \cite{ALERGIA,GoanEtAl96}. 
The character-level description is far too fine grained to compactly describe data and, therefore, leads to poor generality. The coarse-grained token-level representation is more appropriate for most Web data types. In addition, the data representation schemes used in previous work attempt to describe the entire data field, while we use only the starting and
ending sequences, or patterns, of tokens to capture the structure of the
data fields. The reason for this is similar to the one above: using the starting and ending patterns allows us to generalize the structural information for many complex fields which have a lot of variability. Such fields, \eg, addresses, usually have some regularity in how they start and end that we can exploit.
We call the starting and ending patterns collectively
a {\em data prototype}. As an example, consider a set of street
addresses in Fig.~\ref{fig:examples}. All of the examples start with a pattern {\sc
\verb+<+Number Upper}\verb+>+ and end with a specific type \verb+<+Boulevard\verb+>+ or
more generally \verb+<+{\sc Upper}\verb+>+. Note that the pattern language does not
allow loops or recursion. We believe that recursive expressions are not useful representations of the types of data we are trying to learn, because they are harder to learn and lead to over-generalization.

\subsection{Learning from Positive Examples}
\label{sec:learning}
The problem of learning the data prototype from a set of examples
that are labeled as belonging (or not) to a class may be stated
in one of two related ways: as a classification or as a
conservation task. In the classification task, both positive and
negative instances of the class are used to learn a rule that
will correctly classify new examples. Classification algorithms,
like FOIL \cite{Quinlan90}, use negative examples to guide the
specialization of the rule. They construct discriminating
descriptions --- those that are satisfied by the positive
examples and not the negative examples. The conservation task,
on the other hand, attempts to find a characteristic description \cite{Michalski} or conserved patterns \cite{BJEG95}, in a set of positive examples of a class. Unlike the
discriminating description, the characteristic description will
often include redundant features. 
%elaboration on redundant features
For example, when learning a description of street addresses, with city names serving as negative examples, a classification algorithm will learn that \verb+<+{\sc Number}\verb+>+ is a good description, because all the street addresses start with it and none of the city names do. The capitalized word that follows the number in addresses is a redundant feature, because it does not add to the discriminating power of the learned description. However, if an application using this description encounters a zipcode in the future, it will incorrectly classify it as a street address. This problem could have been avoided if \verb+<+{\sc  Number Upper}\verb+>+ was learned as a description of street addresses. 
Therefore, when negative examples are not
available to the learning algorithm, the description has to capture all the regularity of data, including the redundant features, in order to correctly identify new instances of the class and differentiate them from other classes. Ideally, the characteristic description learned from positive examples alone is the same as the discriminating description learned by the
classification algorithm from positive and negative examples, where negative examples are
drawn from infinitely many classes. While most of the widely used
machine learning algorithms (\eg, decision trees \cite{Quinlan93}, inductive logic programming \cite{ILP}) solve the
classification task, there are fewer algorithms that learn characteristic
descriptions.


In our applications, an appropriate source of negative examples is
problematic; therefore, we chose to frame the learning problem as
a conservation task. We introduce an
algorithm that learns data prototypes from positive examples of
the data field alone. The algorithm finds statistically
significant sequences of tokens.
A sequence of token types is significant if it occurs more
frequently than would be expected if the tokens were generated
randomly and independently of one another. In other words, each such sequence constitutes a pattern that describes many of
the positive examples of data and is highly unlikely to have been
generated by chance. 

The algorithm estimates
the baseline probability of a token type's occurrence from the
proportion of all types in the examples of the data field that are
of that type. Suppose we are learning a description of the set of street addresses in Fig.~\ref{fig:examples}, and have already found a significant token
sequence --- \eg, the pattern consisting of the single token {\sc
\verb+<+Number}\verb+>+ --- and want to determine whether the more specific pattern,
\verb+<+{\sc Number Upper}\verb+>+, is also a significant pattern. Knowing the
probability of occurrence of the type {\sc Upper}, we can compute
how many times {\sc Upper} can be expected to follow {\sc Number}
completely by chance. If we observe a considerably greater number
of these sequences, we conclude that the longer pattern is also
significant.

We use hypothesis testing \cite{Papoulis} to decide
whether a pattern is significant. The null hypothesis is that
observed instances of this pattern were generated by chance, via
the random, independent generation of the individual token types.
Hypothesis testing decides, at a given confidence level, whether
the data supports rejecting the null hypothesis. Suppose $n$
identical sequences have been generated by a random source. The
probability that a token type $T$ (whose overall probability of
occurrence is $p$) will be the next type in $k$ of these sequences
has a binomial distribution. For a large $n$, the binomial
distribution approaches a normal distribution $P(x,\mu,\sigma)$
with $\mu = np$ and $\sigma^2 = np(1-p)$. The cumulative
probability is the probability of observing at least $n_1$ events:
\begin{equation}\label{eq:cum_prob}
  P(k \geq n_1)=\int_{n_1}^\infty{P(x,\mu,\sigma)dx}
\end{equation}
\noindent We use polynomial approximation formulas \cite{AS64} to compute the value of the integral.

The significance level of the test, $\alpha$, is the probability
that the null hypothesis is rejected even though it is true, and
it is given by the cumulative probability above. Suppose we set
$\alpha = 0.05$. This means that we expect to observe at least $n_1$
events $5\%$ of the time under the null hypothesis. If the number
of observed events  is greater, we reject the null hypothesis (at
the given significance level), \ie, decide that the observation
is significant. Note that the hypothesis we test is derived from
observation (data). This constraint reduces the number of degrees of freedom of the test; therefore, we must subtract one from the
number of observed events.
This also prevents the anomalous case when a single occurrence of
a rare event is judged to be significant.

\subsection{{\sc DataProG} Algorithm}
\label{sec:dataprog}
We now describe {\sc DataProG}, the algorithm that finds statistically
significant patterns in a set of token sequences. 
During the preprocessing step the text is tokenized, and the
tokens are assigned one or more syntactic types (see
Figure~\ref{fig:hierarchy}). 
The patterns are encoded in a type of prefix
tree, where each node corresponds to a token type. {\sc DataProG} relies on significance judgements to grow
the tree and prune the nodes. Every path through the resulting tree starting at the root node
corresponds to a significant pattern found by the algorithm. 
In this section, we focus the discussion on the version of the algorithm 
that learns starting patterns. The algorithm is easily adapted
to learn ending patterns.


We present the pseudocode of the {\sc DataProG} algorithm in Table~\ref{tbl:dataprog}.
{\sc DataProG} grows the pattern tree incrementally by (1) finding all significant specializations (\ie, longer patterns) of a pattern and (2) pruning the less significant of the generalizations (or specializations) among patterns of the same length. As the last step, {\sc DataProG} extracts all significant patterns from the pattern tree, including those generalizations (\ie, shorter patterns) found to be significant given the more specific (\ie, longer) patterns.

%% pseudocode here
\begin{table}[htbp]
\small{ 
\begin{tabbing}
DATAPROG MAIN LOOP\\
Create \= root node of tree;\\
For next node Q of tree\\
\>  Create children of Q;\\
\>  Prune nodes;\\
Extract patterns from tree; 
\end{tabbing}

\vskip 0.1in

\begin{tabbing}
CREATE CHILDREN OF Q \\
For \= each token type T at next position in examples \\
\>  Let C = NewNode; \\
\>  Let $C.token$ = T; \\
\>  Let $C.examples$  = Q.examples that are followed by T; \\
\>  Let $C.count$ = $|C.examples|$; \\
\>  Let $C.pattern$ \= = concat($Q.pattern\, T$);\\
\>  If Significant($C.count,\ Q.count,\ T.probability$)\\
\>  \>  AddChildToTree(C, Q);\\
\>  End If \\
End T loop
\end{tabbing}

\vskip 0.1in

\begin{tabbing}
PRUNE NODES \\
For \= each child C of Q \\
\>  For \= each sibling S of C s.t. $S.pattern \subset C.pattern$\\
\>  \>  Let $N$ \= $= C.count - S.count$\\
\>  \>  If Not\=(Significant($N, Q.count, C.token.probability$)) \\
\>  \>  \>  Delete C; \\
\>  \>  \>  break;\\
\>  \>  Else\\
\>  \>  \>  Delete S; \\
\>  \>  End If\\
\>  End S loop\\
End C loop
\end{tabbing}

\vskip 0.1in

\begin{tabbing}
EXTRACT PATTERNS FROM TREE \\
Create empty list; \\
For \= every node Q of tree\\
\>  For \= every child C of Q\\
\>  \>  Let  \= $N = C.count - \sum_{i} (S_i.count | S_i \in Children(C))$\\
\>  \>  If Significant( $N, Q.count, C.token.probability$) \\
\>  \>  \>  Add $C.pattern$ to the list; \\
Return (list of patterns); 
\end{tabbing} 
}
\normalsize
\caption{Pseudocode of the {\sc DataProG} algorithm}
\label{tbl:dataprog}
\end{table}


The tree is empty initially, and children are added to the root node. The children represent all tokens that occur in the first position in the training examples more often than expected by chance. 
For example, when learning addresses from the examples in Fig.~\ref{fig:examples}, the root will have two child nodes: {\sc Alphanum} and {\sc Number}.
The tree is extended incrementally at each node $Q$. A new child is added to $Q$ for every significant specialization of the pattern ending at $Q$. As explained previously, a child node is judged to be significant
with respect to its parent node if the number of occurrences of
the pattern ending at the child node is sufficiently large, given
the number of occurrences of the pattern ending at the parent node
and the baseline probability of the token type used to extend the
pattern. 
To illustrate on our addresses example, suppose we have already found
that a pattern \verb+<+{\sc Number Upper}\verb+>+ is significant. 
There are five ways to extend the tree (see Fig.~\ref{fig:pattern_tree}) given the data: \verb+<+{\sc Number Upper Alphanum}\verb+>+, \verb+<+{\sc Number Upper Alpha}\verb+>+, \verb+<+{\sc Number Upper Upper}\verb+>+, \verb+<+{\sc Number Upper} Street\verb+>+, \verb+<+{\sc Number Upper} Boulevard\verb+>+, and \verb+<+{\sc Number Upper} Way\verb+>+. All but the last of these patterns are judged to be significant at $\alpha = 0.05$. For example, \verb+<+{\sc Number Upper Upper}\verb+>+ is significant, because {\sc Upper} follows the pattern \verb+<+{\sc Number Upper}\verb+>+ five out of five times,\footnote{Such small numbers are used for illustrative purposes only --- the typical data sets from which the patterns are learned are much larger.} 
and the probability of observing at least that many longer sequences purely by chance is $0.0002$.\footnote{The calculation of this cumulative probability depends on the occurrence probability of {\sc Upper}. We count the occurrence of each token type independently of the others. In our example, occurrence probability (relative fraction) of type {\sc Upper} is $0.18$.}
Since this probability is less than $\alpha$, we judge this sequence to be  significant.
\comment{If, on the other hand, $45\%$ of all token types were {\sc Upper}, then the cumulative probability of observing the longer pattern including this type would have been $0.058$, and we would not have judged this sequence to be significant since it could be explained by pure chance alone.}


%% Figure here
\begin{figure}[htbp]
 \epsfxsize = 3.0in 
\center{\epsffile{figures/pattern_tree.eps}} 
\caption{Pattern tree that describes the structure of addresses. Dashed lines link to nodes that are deleted during the pruning step.}
 \label{fig:pattern_tree}
 \end{figure}



The next step is to prune the tree. The algorithm examines each pair of sibling nodes, one of which is more general than the other, and eliminates the less significant of the pair. More precisely, the algorithm iterates through the newly created children of $Q$, from the most to least general, and for every pair of children $C_i$ and $C_j$, such that $C_i.pattern \subset C_j.pattern$ (\ie, $C_j.pattern$ is strictly more general than $C_i.pattern$), the algorithm keeps only $C_j$ if it explains significantly more data; otherwise, it keeps only $C_i$.
\footnote{{\sc DataProG} is based on an earlier version of the algorithm, DataPro, described in the conference paper~\protect\cite{KLerman00}. Note that in the original version of the algorithm, the specific patterns were always kept, regardless of whether the more general patterns were found to be significant or not. This introduced a strong bias for specific patterns into the results, which led to a high proportion of false positives during the wrapper verification experiments. Eliminating the specificity bias, improved the performance of the algorithm on the verification task.}

Let us illustrate the pruning step with the example pattern tree in Fig.~\ref{fig:pattern_tree}. We can eliminate the node {\sc AlphaNum}, because all the examples that match the pattern \verb+<+{\sc Number Upper Alphanum}\verb+>+ also match the pattern \verb+<+{\sc Number Upper Alpha}\verb+>+ --- thus, {\sc Alphanum} is not significant given its specialization {\sc Alpha}. We can eliminate node {\sc Alpha} for a similar reason. Next, we check whether \verb+<+{\sc Number Upper Upper}\verb+>+ is significant given the patterns \verb+<+{\sc Number Upper} Boulevard\verb+>+ and \verb+<+{\sc Number Upper} Street\verb+>+. 
There are $2$ instances of the address field that match the
pattern \verb+<+{\sc Number Upper} Boulevard\verb+>+, and $2$ addresses that
match \verb+<+{\sc Number Upper} Street\verb+>+. If \verb+<+{\sc Number Upper
Upper}\verb+>+ matches significantly more than $4$ addresses, it will be
retained and the more specific patterns will be pruned from the
tree; otherwise, it will be deleted and the
more specific ones kept.
%complexity argument
Because every example is described by at most one pattern of a given length, the pruning step ensures that the size of the tree remains polynomial in the number of tokens, thereby, guaranteeing a reasonable performance of the algorithm.



Once the entire tree has been expanded,
the final step is to extract all significant patterns from the tree. Here, the algorithm judges whether the shorter (more general) pattern, \eg, \verb+<+{\sc Number Upper}\verb+>+, is significant given the longer specializations of it, \eg, \verb+<+{\sc Number Upper} Boulevard\verb+>+ and {\sc
\verb+<+Number Upper} Street\verb+>+. This amounts to testing whether the excess number of examples that are explained by the shorter pattern, and not by the longer patterns, is significant. Any pattern that ends at a terminal node of the tree is significant.  
Note that the set of significant patterns may not cover all the examples in the data set, just a fraction of them that occur more frequently than expected by chance (at some significance level). Tables~\ref{tbl:bigbook_examples}--\ref{tbl:quote_examples} show examples of several data fields from a yellow pages source ($Bigbook$) and a stock quote source ($Yahoo\ Quote$), as well as the starting patterns learned for each field.




%Examples
\begin{table}
\center{
\small
\begin{tabular}{|l|l|}
\hline
BUSINESS NAME & ADDRESS \\ \hline
Chado Tea House & 8422 West 1st Street \\
Saladang & 363 South Fair Oaks Avenue  \\
Information Sciences Institute & 4676 Admiralty Way \\
Chaya Venice & 110 Navy Street \\
Acorda Therapeutics & 330 West 58th Street \\
Cajun Kitchen & 420 South Fairview Avenue  \\
Advanced Medical Billing Services & 9478 River Road \\
Vega 1 Electrical Corporation & 1723 East 8th Street \\
21st Century Foundation & 100 East 85th Street \\
TIS the Season Gift Shop & 15 Lincoln Road \\
Hide Sushi Japanese Restaurant & 2040 Sawtelle Boulevard \\
Afloat Sushi & 87 East Colorado Boulevard \\
Prebica Coffee \& Cafe & 4325 Glencoe Avenue \\
L ' Orangerie & 903 North La Cienega Boulevard \\
Emils Hardware & 2525 South Robertson Boulevard \\
Natalee Thai Restaurant & 998 South Robertson Boulevard \\
Casablanca & 220 Lincoln Boulevard \\
Antica Pizzeria & 13455 Maxella Avenue \\
NOBU Photographic Studio & 236 West 27th Street \\
Lotus Eaters & 182 5th Avenue \\
Essex On Coney & 1359 Coney Island Avenue \\
National Restaurant & 273 Brighton Beach Avenue \\
Siam Corner Cafe & 10438 National Boulevard \\
Grand Casino French Bakery & 3826 Main Street \\
Alejo ' s Presto Trattoria & 4002 Lincoln Boulevard \\
Titos Tacos Mexican Restaurant Inc & 11222 Washington Place \\
Killer Shrimp & 523 Washington Boulevard \\
Manhattan Wonton CO & 8475 Melrose Place \\
\hline
Starting patterns & \\ \hline
\verb+<+{\sc Alpha Upper}\verb+>+ & \verb+<+{\sc Number Upper Upper}\verb+>+ \\
\verb+<+{\sc Alpha Upper Upper} Restaurant\verb+>+ & \verb+<+{\sc Number Upper Upper} Avenue\verb+>+ \\
\verb+<+{\sc Alpha} '\verb+>+ & \verb+<+{\sc Number Upper Upper} Boulevard\verb+>+ \\ 
\hline
\end{tabular}
\caption{Examples of the business name and address fields from the $Bigbook$ source, and the patterns learned from them}}
\label{tbl:bigbook_examples}
\end{table}

\begin{table}
\center{
\begin{tabular}{|l|l|l|}
\hline
CITY & STATE & PHONE \\ \hline
Los Angeles & CA & ( 323 ) 655 - 2056 \\
Pasadena & CA & ( 626 ) 793 - 8123 \\
Marina Del Rey & CA & ( 310 ) 822 - 1511 \\
Venice & CA & ( 310 ) 396 - 1179 \\
New York & NY & ( 212 ) 376 - 7552 \\
Goleta & CA & ( 805 ) 683 - 8864 \\
Marcy & NY & ( 315 ) 793 - 1871 \\
Brooklyn & NY & ( 718 ) 998 - 2550 \\
New York & NY & ( 212 ) 249 - 3612 \\
Buffalo & NY & ( 716 ) 839 - 5090 \\
Los Angeles & CA & ( 310 ) 477 - 7242 \\
Pasadena & CA & ( 626 ) 792 - 9779 \\
Marina Del Rey & CA & ( 310 ) 823 - 4446 \\
West Hollywood & CA & ( 310 ) 652 - 9770 \\
Los Angeles & CA & ( 310 ) 839 - 8571 \\
Los Angeles & CA & ( 310 ) 855 - 9380 \\
Venice & CA & ( 310 ) 392 - 5751 \\
Marina Del Rey & CA & ( 310 ) 577 - 8182 \\
New York & NY & ( 212 ) 924 - 7840 \\
New York & NY & ( 212 ) 929 - 4800 \\
Brooklyn & NY & ( 718 ) 253 - 1002 \\
Brooklyn & NY & ( 718 ) 646 - 1225 \\
Los Angeles & CA & ( 310 ) 559 - 1357 \\
Culver City & CA & ( 310 ) 202 - 6969 \\
Marina Del Rey & CA & ( 310 ) 822 - 0095 \\
Culver City & CA & ( 310 ) 391 - 5780 \\
Marina Del Rey & CA & ( 310 ) 578 - 2293 \\
West Hollywood & CA & ( 323 ) 655 - 6030 \\
\hline
Starting patterns  & & \\ \hline
\verb+<+{\sc Upper Upper}\verb+>+ & \verb+<+{\sc AllCaps}\verb+>+ & \verb+<+( {\sc 3digit} ) {\sc 3digit - Large}\verb+>+ \\
\verb+<+{\sc Upper Upper} Rey\verb+>+ & & \\
\hline
\end{tabular}
\caption{Examples of the city, state and phone number fields from the $Bigbook$ source, and the patterns learned from them}}
\label{tbl:bigbook_examples2}
\end{table}


\begin{table}
\center{
\begin{tabular}{|l|l|l|l|}
\hline
PRICE CHANGE & TICKER & VOLUME & PRICE \\ \hline
+ 0 . 51 & INTC & 17 , 610 , 300 & 122 3 / 4 \\
+ 1 . 51 & IBM & 4 , 922 , 400 & 109 5 / 16 \\
+ 4 . 08 & AOL & 24 , 257 , 300 & 63 13 / 16 \\
+ 0 . 83 & T & 8 , 504 , 000 & 53 1 / 16 \\
+ 2 . 35 & LU & 9 , 789 , 300 & 68 \\
& ATHM & 5 , 646 , 400 & 29 7 / 8 \\
- 10 . 84 & COMS & 15 , 388 , 200 & 57 11 / 32 \\
- 1 . 24 & CSCO & 19 , 135 , 900 & 134 1 / 2 \\
- 1 . 59 & GTE & 1 , 414 , 900 & 65 15 / 16 \\
- 2 . 94 & AAPL & 2 , 291 , 800 & 117 3 / 4 \\
+ 1 . 04 & MOT & 3 , 599 , 600 & 169 1 / 4 \\
- 0 . 81 & HWP & 2 , 147 , 700 & 145 5 / 16 \\
+ 4 . 45 & DELL & 40 , 292 , 100 & 57 3 / 16 \\
+ 0 . 16 & GM & 1 , 398 , 100 & 77 15 / 16 \\
- 3 . 48 & CIEN & 4 , 120 , 200 & 142 \\
+ 0 . 49 & EGRP & 7 , 007 , 400 & 25 7 / 8 \\
- 3 . 38 & HLIT & 543 , 400 & 128 13 / 16 \\
+ 1 . 15 & RIMM & 307 , 500 & 132 1 / 4 \\
& C & 6 , 145 , 400 & 49 15 / 16 \\
- 2 . 86 & GPS & 1 , 023 , 600 & 44 5 / 8 \\
- 6 . 46 & CFLO & 157 , 700 & 103 1 / 4 \\
- 0 . 82 & DCLK & 1 , 368 , 100 & 106 \\
+ 2 . 00 & NT & 4 , 579 , 900 & 124 1 / 8 \\
+ 0 . 13 & BFRE & 149 , 000 & 46 9 / 16 \\
- 1 . 63 & QCOM & 7 , 928 , 900 & 128 1 / 16 \\
\hline
Starting patterns & & & \\ \hline
\footnotesize
\verb+<+{\sc Punct 1digit . 2digit}\verb+>+ & 
\footnotesize \verb+<+{\sc AllCaps}\verb+>+ & 
\footnotesize \verb+<+{\sc Number , 3digit , 3digit}\verb+>+ & 
\footnotesize \verb+<+{\sc Medium 1digit / Number}\verb+>+  \\
 & & & \footnotesize \verb+<+{\sc Medium} 15 / 16 \verb+>+\\ \hline
\end{tabular}
\caption{Data examples from the $Yahoo\ Quote$ source, and the patterns learned from them}}
\label{tbl:quote_examples}
\end{table}

\normalsize


\section{Applications of Pattern Learning}
As we explained in the introduction, wrapper induction systems use information from the layout of Web pages to create data extraction rules and are therefore vulnerable to changes in the layout, which occur frequently when the site is redesigned. In some cases the wrapper continues to extract, but the data is no longer correct. The output of the wrapper may also change because the format of the source data itself has changed: \eg, when ``\$'' is dropped from the price field (``9.95'' instead of ``\$9.95''), or book availability changes from ``Ships immediately'' to ``In Stock: ships immediately.'' Because other applications, such as Web agents \cite{Ambite02,Elves}, rely on data extracted by wrappers, wrapper maintenance is an important research problem.
We divide the wrapper maintenance problem into two parts, each described separately in the paper.
{\em Wrapper verification} automatically detects when a wrapper is not extracting data correctly from a Web source, while {\em wrapper reinduction} automatically fixes broken wrappers.
Both applications learn a description of data, of which patterns learned by {\sc DataProG} are a significant part.


\subsection{Wrapper Verification}
\label{sec:verification}

If the data extracted by the wrapper changes significantly, this is an indication that the Web source may have changed its format. Our wrapper verification system uses examples of data extracted by the wrapper in the past that are known to be correct in order to acquire a description of the data. The learned description contains features of two types: patterns learned by {\sc DataProG}  and global numeric features, such as the density of tokens of a particular type. The application then checks that this description still applies to the new data extracted by the wrapper. Thus, wrapper verification is a specific instance of the data validation task.

The verification algorithm works in the following way. A set of queries is used to retrieve HTML pages from which the wrapper extracts (correct) training examples. The algorithm then computes the values of a vector of features, $\vec{k}$, that describes each field of the training examples. These features include the patterns that describe the common beginnings (or endings) of the field. During the verification phase, the wrapper generates a set of (new) test examples from pages retrieved using the same set of queries, and computes the feature vector $\vec{r}$ associated with each field of the test examples. If the two distributions, $\vec{k}$ and $\vec{r}$ (see Fig.~\ref{fig:verification}), are statistically the same (at some significance level), the wrapper is judged to be extracting correctly; otherwise, it is judged to have failed. 


\begin{figure}[htbp]
\epsfxsize = 3.0in 
\center{\epsffile{figures/verification.eps} 
\caption{A hypothetical distribution of features over the training and test examples } \label{fig:verification}}
\end{figure}

Each field is described by a vector, whose $i$th component is the value of the $i$th feature, such as the number of examples that match pattern $j$. In addition to patterns, we use the following numeric features to describe the sets of training and test examples: the average number of tuples-per-page, mean number of tokens in the examples, mean token length, and the density of alphabetic, numeric, HTML-tag and punctuation types. We use goodness of fit method (Papoulis 1990) to decide whether the two distributions are the same. To use the goodness of fit method, we must first compute Pearson's test statistic for the data. The Pearson's test statistic is defined as:

\begin{equation}\label{eq:pearsons}
  q = \sum_{i=1}^{m}{(t_i - e_i)^2 \over {e_i}}
\end{equation}
\noindent where $t_i$ is the observed value of the $i$th feature in the test data, and $e_i$ is the expected value for that feature, and $m$ is the number of features. For the patterns $e_i = n r_i/N$, where $r_i$ is the number of training examples explained by the $i$th patter, $N$ is the number of examples in the training set and $n$ is the number of examples in the test set. For numeric features $e_i$ is simply the value of that feature for the training set. The test statistic $q$ has a chi-squared distribution with $m-1$ independent degrees of freedom. If $q < \chi^2(m-1; \alpha)$, we conclude that at significance level $\alpha$ the two distributions are the same; otherwise, we conclude that they are different. Values of $\chi^2$ for different values of  $\alpha$ and $m$ can be looked up in a statistics table or calculated using an approximation formula. 

% features used
In order to use the test statistic reliably, it helps to use as many independent features as possible. In the series of verification experiments reported in \cite{KLerman00}, we used the starting and ending patterns and the average number of tuples-per-page feature when computing the value of $q$. We found that this method tended to overestimate the test statistic, because the features (starting and ending patterns) were not independent. In the experiments reported in this paper, we use only the starting patterns, but in order to increase the number of features, we added numeric features to the description of data.

\subsubsection{Results}
\label{sec:verification-results}

% experimental procedure
We monitored $27$ wrappers (representing $23$ distinct Web sources) over a period of ten months, from May 1999 to March 2000. The sources are listed in Table~\ref{tbl:sources}. For each wrapper, the results of $15$--$30$ queries were stored periodically, every 7--10 days. We used the same query set for each source, except for the $hotel$ source, because it accepted dated queries, and we had to change the dates periodically to get valid results. Each set of new results (test examples) was compared with the last correct wrapper output (training examples).

\begin{table}
\center{
\begin{tabular}{|l|l|l|}\hline
{\bf Source} & {\bf Type} & {\bf Data Fields} \\ \hline
$airport$ & tuple/list & airport code, name \\ \hline
$altavista$ & list & url, title \\ \hline
$Amazon$ & tuple & book author, title, price, availability, isbn \\ \hline
$arrowlist$ & list & part number, manufacturer, price, status, \\ & & description, url\\ \hline
$Bigbook$ & tuple & business name, address, city, state, phone\\ \hline
$Barnes\&Noble$ & tuple & book author, title, price, availability, isbn \\ \hline
$borders$ & list & book author, title, price, availability \\ \hline
$cuisinenet$ & list & restaurant name, cuisine, address, city, state, \\ & & phone, link \\ \hline
$geocoder$ & tuple & latitude, longitude, street, city, state \\ \hline
$hotel$ & list & name, price, distance, url \\ \hline
$mapquest$ & tuple & hours, minutes, distance, url \\ \hline
$northernlight$ & list & url, title \\ \hline
$parking$ & list & lotname, dailyrate \\ \hline
$Quote$ & tuple & stock ticker, price, pricechange, volume \\ \hline
$Smartpages$ & tuple & name, address, city, state, phone \\ \hline
$showtimes$ & list & movie, showtimes \\ \hline
$theatre$ & list & theater name, url, address \\ \hline
$Washington\ Post$ & tuple & taxi price \\ \hline
$whitepages$ & list & business name, address, city, state, phone \\ \hline
$yahoo\ people$ & list & name, address, city, state, phone \\ \hline
$Yahoo\ Quote$ & tuple & stock ticker, price, pricechange, volume \\ \hline
$yahoo\ weather$ & tuple & temperature, forecast \\ \hline
$cia\ factbook$ & tuple & country area, borders, population, \etc \\ \hline
\end{tabular}
\caption{List of sources used in the experiments and data fields extracted from them. Source type refers to how much data a source returns in response to a query --- a single tuple or a list of tuples. For $airport$ source, the type changed from a single tuple to a list over time. }}
\label{tbl:sources}
\end{table}


The verification algorithm used {\sc DataProG} to learn the starting patterns and numeric features for each field of the training examples and made a decision at a high significance level (corresponding to $\alpha = 0.001$) about whether the test set was statistically similar to the training set. If none of the starting patterns matched the test examples or if the data was found to have changed significantly for any data field, we concluded that the wrapper failed to  extract correctly from the source; otherwise, if all the data fields returned statistically similar data, we concluded that the wrapper was working correctly.

A manual check of the $438$ comparisons revealed $37$ wrapper changes attributable to changes in the source layout and data format.\footnote{Seven of these were, in fact, internal to the wrapper itself, as when the wrapper was modified to extract ``\$$22.00$'' instead of ``$22.00$'' for the price field. Because these actions were mostly outside of our control, we chose to classify them as wrapper changes.}  The verification algorithm correctly discovered $35$ of these changes and made $15$ mistakes. Of these mistakes, $13$ were {\em false positives}, which means that the verification program decided that the wrapper failed when in reality it was working correctly. Only two of the errors were the more important {\em false negatives}, meaning that the algorithm did not detect a change in the data source. The numbers above result in the following precision, recall and accuracy values:
\begin{eqnarray*}
P & = & {{true\  positives} \over {true\  positives + false\  positives}} = 0.73\,, \\
R & = & {{true\  positives} \over {true\  positives + false\  negatives}} = 0.95\,, \\
A & = & {{true\  positives + true\  negatives} \over {positives\  + negatives}} = 0.97\,. 
\end{eqnarray*} 

These results are an improvement over those reported in \cite{KLerman00}, which produced $P = 0.47, R=0.95, A=0.91$. The poor precision value reported in that work was due to $40$ false positives obtained on the same data set. We attribute the improvements both to eliminating the specificity bias in the patterns learned by {\sc DataProG} and to changing the feature set to include only the starting patterns and additional numeric features. Note that this improvement does not result simply from adding numeric features. To check this, we ran the verification experiments on a subset of data (the last $278$ comparisons) using only the global numeric features and obtained $P=0.92$ and $R=0.55$, whereas using both patterns and numeric features results in values of $P=0.71$ and $R=1.00$ for the same data set.

\comment{The URL field from two sources ($hotel$, $mapquest$) had the largest number of false positives. This is because on each day the sources were queried, the URL contained an alphanumeric  key, whose format sometimes changed, so that none of the new URLs matched the old patterns. On one occasion the server name in the URL had changed as well. A false positive in the $Quote$ source occurred because on the day the training data was retrieved, most of the stocks lost value, while on the day the test data was retrieved, most of the stocks had gained value. Using a more diverse data set should help reduce the error rate for both of these cases. The other false positives are attributed to variations in the distribution of the retrieved data.
}

\subsubsection{Discussion of Results}
Though we have succeeded in significantly reducing the number of false positives, we have not managed to eliminate them altogether. There are a number of reasons for their presence, some of which point to limitations in our approach. 


\begin{table}
\begin{description}
\item[hotel, mapquest] (5 cases): URL field contains alphanumeric keys, with embedded punctuation symbols. The tokenizer splits the field into many tokens. 
\indent The key or its format changes from:\\
\\http://$\ldots$\&Stamp=Q4aaiEGSp68*itn/hot\%3da11204,itn/agencies/newitn$\ldots$  
to 
\\http://$\ldots$\&Stamp=8$\sim$bEgGEQrCo*itn/hot\%3da11204,itn/agencies/newitn$\ldots$
\\\indent On one occasion, the server name inside the URL changed: from \\
http://enterprise.mapquest.com/mqmapgend?MQMapGenRequest=$\ldots$ to \\
http://sitemap.mapquest.com/mqmapgend?MQMapGenRequest=$\ldots$ 
\item[showtimes, arrowlist] (5 cases ): Instance of the showtimes field and part number and description fields (arrowlist) are very long. Many long, overly specific patterns are learned for these fields: \eg,  \\
\small
\indent \verb+<+( {\sc Number : 2digit AllCaps ) , ( Small : 2digit ) , ( Small : 2digit ) , ( 4 : 2digit ) , 6 : 2digit , 7 : 2digit , 9 : 2digit , 10 : 2digit} \verb+>+ 
\normalsize
\item[altavista] (1 case): Database of the search engine appears to have been updated. A different set of results is returned for each query.
\item[quote] (1 case): Data changed --- there were many more positive than negative price movements in the test examples
\item[factbook]  (1 case): Data format changed: \\
\indent $from$ \verb+<+{\sc Number} km2 \verb+>+ \\
\indent $to$ \verb+<+{\sc Number} sq km \verb+>+
\end{description}
\caption{List of sources of false positive results on the verification task}
\label{tbl:false-positives}
\end{table}

We can split the types of errors into roughly three not entirely independent classes: improper tokenization, incomplete data coverage, and data format changes. 
The URL field (Table~\ref{tbl:false-positives}) accounted for a significant fraction of the false positives, in large part due to the design of our tokenizer, which splits text strings on punctuation marks. If the URL contains embedded punctuation (as part of the alphanumeric key associated with the user or session id), it will be split into a varying number of tokens, so that it is hard to capture the regularity of the field. The solution is to rewrite the tokenizer to recognize URLs for which well defined specifications exist. We will address this problem in our ongoing work. Our algorithm also failed sometimes (\eg, $arrowlist$, $showtimes$) when it learned very long and specific descriptions. It is worth pointing out, however, that it performed correctly in over two dozen comparisons for these sources. These types of errors are caused by incomplete data coverage: a larger, more varied training data set would produce more general patterns, which would perform better on the verification task. A striking example of the data coverage problem occurred for the stock quotes source: the day the training data was collected, there were many more down movements in the stock price than up, and the opposite was true on the day the test data was collected. As a result, the price change fields for those two days were dissimilar. Finally, because {\sc DataProG} learns the format of data, false positives will inevitably result from changes in the data format and do not indicate a problem with the algorithm. This is the case for the factbook source, where the units of area changed from ``km2'' to ``sq km''. 


\subsection{Wrapper Reinduction}
\label{sec:reinduction}
If the wrapper stops extracting correctly, the next challenge is to rebuild it automatically~\cite{Cohen99}. The extraction rules for our wrappers~\cite{Muslea01}, as well as many others (cf.~\cite{Kushmerick97,Hsu98}), are generated by a machine learning algorithm, which takes as input several pages from a source and labeled examples of data to extract from each page. 
%% new content added
It is assumed that the user labeled all examples correctly.
If we  label at least a few pages for which the wrapper fails by correctly identifying examples of data on them, we can use these examples as input to the induction algorithm, such as {\sc STALKER},\footnote{It does not matter, in fact, matter which wrapper induction system is used. We can easily replace {\sc Stalker} with HLRT~\cite{Kushmerick97} to generate extraction rules.} to generate new extraction rules.\footnote{In this paper we will only discuss wrapper reinduction for information sources that return a single tuple of results per page, or a detail page. In order to create data extraction rules for sources that return lists of tuples, the {\sc Stalker} wrapper induction algorithm requires user to specify the first and last elements of the list, as well as at least two consecutive elements. Therefore, we need to be able to identify these data elements with a high degree of certainty.} 
Note that we do not need to identify the data on every page --- 
%%we only need to specify some of the examples for the wrapper induction system to learn correct extraction rules. 
depending on how regular the data layout is, {\sc Stalker} can learn extraction rules using a small number of correctly labeled pages.
Our solution is to bootstrap the wrapper induction process (which learns landmark-based rules) by learning content-based rules. We want to re-learn the landmark-based rules, because for the types of sites we use, these rules tend to be much more accurate and efficient than content-based rules.


We employ a method that takes a set of training examples, extracted from the source when the wrapper was known to be working correctly, and a set of pages from the same source, and uses a mixture of supervised and unsupervised learning techniques to identify examples of the data field on new pages. We assume that the format of data did not change. Patterns learned by {\sc DataProG}  play a significant role in the reinduction task. In addition to patterns, other features, such as the length of the training examples and structural information about pages are used. In fact, because page structure is used during a critical step of the algorithm, we discuss our approach to learning it in detail in the next paragraph.

% template algorithm
\subsubsection{Page Template Algorithm}
Many Web sources use templates, or page skeletons, to automatically generate pages and fill them with results of a database query. This is evident in the example in Fig.~\ref{fig:example}. The template consists of the heading ``RESULTS'', followed by the number of results that match the query, the phrase ``Click links associated with businesses for more information,'' then the heading ``ALL LISTINGS,'' followed by the anchors ``map,'' ``driving directions,'' ``add to My Directory'' and the bolded phrase ``Appears in the Category.'' Obviously, data is not part of the template --- rather, it appears in the {\em slots} between template elements. 

\begin{figure}[hbp]
\epsfxsize = 4.2in 
\center{\epsffile{figures/example.eps}
\caption{ Fragments of two Web pages from the same source displaying restaurant information.} \label{fig:example}}
\end{figure}



Given two or more example pages from the same source, we can induce the template used to generate them (Table~\ref{tbl:template}). The template finding algorithm looks for all sequences of tokens --- both HTML tags and text --- that appear exactly once on each page. The algorithm works in the following way: we pick the smallest page in the set as the template seed. Starting with the first token on this page, we grow a sequence by appending tokens to it, subject to the condition that the sequence appears on every page. If we managed to build a sequence that's at least three tokens long\footnote{The best value for the minimum length for the page template element was determined empirically to be three.}, and this sequence appears exactly once on each page, it becomes part of the page template. Templates play an important role in helping identify correct data examples on pages.


\begin{table}[htbp]
\center{
\begin{tabbing}
input: \= \\
\>  $P$ = set of $N$ Web pages \\
output: \\
\>  $T$ = page template \\
begin \\
\>  $p$ = shortest($P$) \\
\>  $T$ = null \\
\>  $s$ = null \\
\>  for $t$ \= = firsttoken($p$) to lasttoken($p$) \\
\>  \>  $s^\prime$ = concat($s, t$) \\
\>  \>  if \= ( $s^\prime$ appears on every page in $P$ ) \\
\>  \>  \>  $s = s^\prime$ \\
\>  \>  \>  continue \\
\>  \>  else \\
\>  \>  \>  $n = \sum_{page=1}^{N}{}$count($s$, page) \\
\>  \>  \>  if \= ( $n = N$ AND length($s$) $\ge 3$ ) \\
\>  \>  \>  \>  add-to-template($T, s$) \\
\>  \>  \>  end if \\
\>  \>  \>  $s$ = null \\
\>  \>  end if \\
\>  end for \\
end
\end{tabbing}
\vskip -0.1in
\caption {Pseudocode of the template finding algorithm}}
\label{tbl:template}
\end{table}


\subsubsection{Automatic Labeling Algorithm} 
Figure \ref{fig:reinduction} is a schematic outline of the reinduction algorithm, which consists of automatic data labeling and wrapper induction. Because the latter aspect is described in detail in other work~\cite{Muslea01}, we focus the discussion below on the automatic data labeling algorithm.



\begin{figure}[htbp]
\epsfxsize = 3.0in 
\center{\epsffile{figures/reinduction.eps}}
\caption{Schematic outline of the reinduction algorithm} \label{fig:reinduction}
\end{figure}

% details
First, {\sc DataProG} learns the starting and ending patterns that describe the set of training examples. These training examples have been collected during wrapper's normal operation, while it was correctly extracting data from the Web source. The patterns are used to identify possible examples of the data field on the new pages. In addition to patterns, we also calculate the mean (and its variance) of the number-of-tokens in the training examples. Each new page is then scanned to identify all text segments that begin with one of the starting patterns and end with one of the ending patterns. Text segments that contain significantly more or fewer tokens than expected based on the old number-of-tokens distribution, are eliminated from the set of candidate extracts. The learned patterns are often too general and will match many, possibly hundreds, text segments on each page. Among these spurious text segments is the correct example of the data field. The rest of the discussion is concerned with identifying the correct examples of data on pages.

We exploit some simple {\em a priori} assumptions about the structure of Web pages to help us separate interesting extracts from noise. We expect examples of the same data field to appear roughly in the same position  and in the same context on each page. 
For example, Fig.~\ref{fig:example} shows fragments of two Web pages from the same source displaying restaurant information. On both pages the relevant information about the restaurant appears after the heading ``ALL LISTINGS'' and before the phrase ``Appears in the Category:''. Thus, we expect the same field, \eg, address, to appear in the {\em same place}, or slot, within the page template. Moreover, the information we are trying to extract will not usually be part of the page template; therefore, candidate extracts that are part of the page template can be eliminated from consideration. Restaurant address always follows restaurant name (in bold) and precedes the city and zip code, \ie, it appears in the {\em same context} on every page. A given field is either visible to the user on every page, or it is  invisible (part of an HTML tag) on every page. In order to use this information to separate extracts, we describe each candidate extract by a feature vector, which includes positional information, defined by the (page template) slot number and context. The context is captured by the adjacent tokens: one token immediately preceding the candidate extract and one token immediately following it. We also use a binary feature which has the value one if the token is visible to the user, and zero if it is part of an HTML tag. Once the candidate extracts have been assigned feature vectors, we split them into groups, so that within each group, the candidate extracts are described by the same feature vector.

% clustering
 
% scoring
The next step is to score groups based on their similarity to the training examples. We expect the highest scoring group to contain correct examples of the data field. One scoring method involves assigning a rank to the groups based on how many extracts they have in common with the training examples. This technique generally works well, because at least some of the data usually remains the same when the Web page layout changes. Of course, this assumption does not apply to data that changes frequently, such as weather information, flight arrival times, stock quotes, {\em etc}. However, we have found that even in these sources, there is enough overlap in the data that our approach works.
If the scoring algorithm assigns zero to all groups, \ie, there exist no extracts in common with the training examples, a second scoring algorithm is invoked. This scoring method follows the wrapper verification procedure and finds the group that is most similar to the training examples based on the patterns learned from the training examples.

The final step of the wrapper reinduction process is to provide the extracts in the top ranking group to the {\sc Stalker} wrapper induction algorithm \cite{Muslea01} along with the new pages. {\sc Stalker} learns data extraction rules for the changed pages.
Note that examples provided to {\sc Stalker} are required to be the correct examples of the field. If the set of automatically labeled examples includes false positives, {\sc Stalker} will not learn correct extraction rules for that field. False negatives are not a problem, however. If the reinduction algorithm could not find the correct example of data on a page, that page is simply not used in the wrapper induction stage.


\subsubsection{Results}
\label{sec:reinduction-results}
To evaluate the reinduction algorithm we used only the ten sources (listed in Table~\ref{tbl:sources}) that returned a single tuple of results per page, a detail page.\footnote{ We did not use the $geocoder$ and $cia\ factbook$ wrappers in the experiments. The $geocoder$ wrapper accessed the source through another application; therefore, the pages were not available to us for analysis. The reason for excluding the $factbook$ is that it is a plain text source, while our methods apply to Web pages. Note also that in the verification experiments, we had two wrappers for the $mapquest$ source, each extracting different data. In the experiments described below, we used the one that contained more data for this time period.}
The method of data collection was described in Sec.~\ref{sec:verification-results}. Over the period between October 1999 and March 2000 there were eight format changes in these sources. Since this set is much too small for evaluation purposes, we created an artificial test set by considering all ten data sets collected for each source during this period. 
We evaluated the algorithm by using it to extract data from Web pages for which correct output is known. Specifically, we took ten tuples from a set collected on one date, and used this information to extract data from ten pages (randomly chosen) collected at a later date, regardless of whether the source had actually changed or not. We reserved the remaining pages collected at a later date for testing the learned {\sc Stalker} rules. 

The output of the reinduction algorithm is a list of tuples extracted from ten pages, as well as extraction rules generated by {\sc Stalker} for these pages. 
Though in most cases we were not able to extract every field on every pages, we can still learn good extraction rules with {\sc Stalker} as long as few examples of each field are correctly labeled. 
We evaluated the reinduction algorithm in two stages: first, we checked how many data fields for each source were identified successfully; second, we checked the quality of the learned {\sc Stalker} rules by using them to extract data from test pages.


\paragraph{Extracting with content-based rules}
We judged a data field to be successfully extracted if the automatic labeling algorithm was able to identify it correctly on at least two of the ten pages. This is the minimum number of examples {\sc Stalker} needs to create extraction rules. In practice, such a low success rate only occurred for one field each in two of the sources: $Quote$ and $Yahoo\ Quote$. For all other sources, if a field was successfully extracted, it was correctly identified in at least three, and in most cases almost all, of the pages in the set. A false positive occurred when the reinduction algorithm incorrectly identified some text on a page as a correct example of a data field. In many cases, false positives consisted of partial fields, \eg, ``Cloudy'' rather than ``Mostly Cloudy'' ($yahoo\ weather$). A false negative occurred when the algorithm did not identify any examples of a data field. 
We ran the reinduction experiment attempting to extract the fields listed in Table~\ref{tbl:rnd_sources}. The second column of the table lists the fractions of data sets for which the field was successfully extracted. We were able to correctly identify fields 277 times across all data sets making 61 mistakes, of which 31 were attributed to false positives and 30 to the false negatives. %, resulting in precision $P=0.90$ and recall $R=0.90$. 

\small
\begin{table}
\center{
\begin{tabular}{|l|l|l|l|l|l|}\hline
{\bf source/field} & {\bf ex \%} & {\bf p} & {\bf r} \\ \hline % \\ \hline % & {\bf f} & {\bf a} \\ \hline
$airport$ code  &  100 &  1.0  & 1.0  \\ % & 1.0 &  1.0 \\
$airport$ name  &  90  &  1.0  & 1.0  \\ % & 1.0 &  1.0 \\ \hline
$Amazon$ author &  100 &  97.3   & 0.92   \\ % & 0.94.7  &  90 \\
$Amazon$ title  &  70  &  98.8   & 0.81   \\ % & 0.88.9  &  0.80 \\
$Amazon$  price &  100 &  1.0  & 0.99   \\ % & 0.99.6  &  99.2 \\
$Amazon$  ISBN  &  100 &  1.0  & 0.91   \\ % & 0.95.2  &  90.8 \\
$Amazon$ availability & 60  &  1.0  & 0.86  \\ \hline %  & 0.92.5  &  86 \\ \hline
$Barnes\&Noble$ author & 100 &  0.93  &  0.96 \\ %  &  0.94.3 &   89.2 \\
$Barnes\&Noble$ title & 80   & 0.96   & 0.62   \\ % & 75.1  &  60.2 \\
$Barnes\&Noble$  price & 90  &  1.0 &  0.68   \\ % &  81.2 &   68.4 \\
$Barnes\&Noble$  ISBN & 100  & 1.0  & 0.95   \\ % & 97.4  &  95 \\
$Barnes\&Noble$ availability &  90   & 1.0  & 0.92  \\ \hline % &  95.7  &  91.7 \\ \hline
$Bigbook$ name   & 70  &  1.0 &  0.76  \\ % &  86.6   & 76.3 \\
$Bigbook$ street & 90  &  1.0 &  0.87  \\ % & 93   & 87 \\
$Bigbook$ city   & 70  &  0.91  &  0.98  \\ % &  94  &  88.6 \\
$Bigbook$ state  & 100 &  0.04 & 0.50 \\ % &   6.7 & 3.4 \\
$Bigbook$ phone  & 90  &  1.0  & 0.30  \\ \hline % &  46.2   & 30 \\ \hline
$mapquest$ time  & 100 &  1.0  & 0.98  \\ % &  99   & 98 \\
$mapquest$ distance &  100  & 1.0  & 0.98  \\ \hline % &  99  &  98 \\ \hline
$Quote$ pricechange  & 50   & 0.38   & 0.36  \\ % &  36.7  &  22.5 \\
$Quote$ ticker   & 63   & 0.93  &  0.87  \\ % &  89.7   & 81.3 \\
$Quote$ volume   & 100  & 1.0 &  0.88  \\ % &  93.3   & 87.5 \\
$Quote$ shareprice  &  38  &  0.46  &  0.60  \\ \hline %  & 52.2 &   35.3 \\ \hline
$Smartpages$ name & 80   & 1.0 &  0.82  \\ % &  89.9  &  81.7 \\
$Smartpages$ street &  80   &  1.0  & 0.52 \\ % &  68.7  &  52.3 \\
$Smartpages$ city & 0 & 0.68  &  0.58   \\ % & 62.4  &  45.4 \\
$Smartpages$ state  &  100  & 1.0  & 0.70  \\ %  & 82.8  &  70.6 \\
$Smartpages$ phone  &  100  & 0.99   & 1.0 \\ \hline %  & 99.5  &  99.1 \\ \hline
$Yahoo\ Quote$ pricechange & 100 &  1.0 &  0.41  \\ % &  57.7 &   40.6 \\
$Yahoo\ Quote$ ticker & 100  & 1.0 &  0.98  \\ %  & 99  &  98.1 \\
$Yahoo\ Quote$ volume & 100  & 1.0 &  0.99  \\ %  & 99.5  &  99.1 \\
$Yahoo\ Quote$ shareprice & 80  &  1.0  & 0.59 \\ \hline %  &  74.6  &  59.4 \\ \hline
$Washington\ Post$ price  & 100 &  1.0  & 1.0 \\ \hline % &  1.0  & 1.0 \\ \hline
$Weather$ temp   & 40  &  0.36  &  0.82  \\ %  & 50  &  33.3 \\
$Weather$ outlook   &  90  &  0.83   & 1.0 \\ \hline %  & 90.9  &  83.3 \\ \hline
average & 83 & 0.90 & 0.80 \\ \hline
\end{tabular}
}
\normalsize
\caption{Reinduction results on ten Web sources. The first column lists the fraction of the fields for each source that were correctly extracted by the pattern-based algorithm. We judged the field to be extracted if the algorithm correctly identified at least two examples of it. The last two columns list precision and recall on the data extraction task using the reinduced wrappers.}
\label{tbl:rnd_sources}
\end{table}

\normalsize
There are several reasons the reinduction algorithm failed to operate perfectly. In many cases the reason was the small training set.\footnote{Limitations in the data collection procedure prevented us from accumulating large data sets for all sources; therefore, in order to keep the methodology uniform across all sources, we decided to use smaller training sets.} We can achieve better learning for the yellow-pages-type sources $Bigbook$ and $Smartpages$ by using more training examples (see Fig.~\ref{fig:lc}). In two cases, the errors were attributable to changes in the format of data, which resulted in the failure of patterns to capture the structure of data correctly: \eg, the $airport$ source changed airport names from capitalized words to allcaps, and in the $Quote$ source in which the patterns were not able to identify negative price changes because they were learned for a data set in which most of the stocks had a positive price change. For two sources the reinduction algorithm could not distinguish between correct examples of the field and other examples of the same data type: for the $Quote$ source, in some cases it extracted opening price or high price for the stock price field, while for the $yahoo\ weather$ source, it extracted high or low temperature, rather than the current temperature. This problem was also evident in the $Smartpages$ source, where the city name appeared in several places on the page. In these cases, user intervention or meta-analysis of the fields may be necessary to improve results of data extraction. 




\begin{figure}[htbp]
\epsfxsize = 3.0in 
\center{\epsffile{figures/learning_curve.eps}
\caption{ Performance of the reinduction algorithm for the fields in the $Smartpages$ source as the size of the training set is increased } \label{fig:lc}}
\end{figure}


\paragraph{Extracting with landmark-based rules}
The final validation experiment consisted of using the automatically generated wrappers to extract data from test pages. The last three columns in Table~\ref{tbl:rnd_sources} list precision, recall and accuracy for extracting data from test pages. The performance is very good for most fields, with the notable exception of the {\em STATE} field of $Bigbook$ source. For that field, the pattern \verb+<+{\sc Allcaps}\verb+>+ was overly general, and a wrong group received the highest score during the scoring step of the reinduction algorithm. The average precision and recall values were $P=0.90$ and $R=0.80$. 

Within the data set we studied, five sources, listed in Table~\ref{tbl:changed_sources}, experienced a total of seven changes. In addition to these sources, the $airport$ source changed the format of the data it returned, but since it simultaneously changed the presentation of data from a detail page to a list, we could not use this data to learn {\sc Stalker} rules. 
Table \ref{tbl:changed_sources} shows the performance of the automatically reinduced wrappers for the changed sources. For most fields precision $P$, the more important of the performance measures, is close to its maximum value, indicating that there were few false positives. However, small values of recall indicate that not all examples of these fields were extracted. This result can be traced to a limitation of our approach: if the same field appears in a different context, more than one rule is necessary to extract it from a source. In such cases, we extract only a subset of the examples that share the same context, but ignore the rest of the examples.


\begin{table}
\small
\begin{tabular}{|l|c|c|c||l|c|c|c|}\hline
\comment{
{\bf source/field} & {\bf P} & {\bf R} & {\bf F} & {\bf A} & {\bf source/field} & {\bf P} & {\bf R} & {\bf F} & {\bf A} \\ \hline
$Amazon$ author  & 1.0 & 1.0 & 1.0 & 1.0 & $Smartpages$ name   & 1.0 & 0.9 & 0.9 & 0.9 \\
$Amazon$ title   & 1.0 & 0.7 & 0.8 & 0.7 & $Smartpages$ street & N/A & 0.0 & N/A & 0.0 \\
$Amazon$  price  & 0.9 & 0.9 & 0.9 & 0.9 & $Smartpages$ city   & 0.0 & 0.0 & N/A & 0.0 \\
$Amazon$  ISBN   & 1.0 & 0.9 & 0.9 & 0.9 & $Smartpages$ state  & 1.0 & 0.9 & 0.9 & 0.9 \\
$Amazon$ availability & 1.0 & 0.9 & 1.0 & 0.9 & $Smartpages$ phone  & N/A & 0.0 & N/A & 0.0\\
$Barnes\&Noble$ author & 1.0 & 0.5 & 0.7 & 0.5 & $Yahoo\ Quote$ pricechange & 1.0 & 0.2 & 0.3 & 0.2 \\
$Barnes\&Noble$ title  & 1.0 & 0.8 & 0.9 & 0.8 & $Yahoo\ Quote$ ticker    &  1.0 & 0.5 & 0.7 & 0.5 \\
$Barnes\&Noble$  price & 1.0 & 1.0 & 1.0 & 1.0 & $Yahoo\ Quote$ volume    &  1.0 & 0.7 & 0.8 & 0.7 \\
$Barnes\&Noble$  ISBN  & 1.0 & 1.0 & 1.0 & 1.0 & $Yahoo\ Quote$ shareprice & 1.0 & 0.7 & 0.8 & 0.7 \\
$Barnes\&Noble$ availability  &  1.0 & 1.0 & 1.0 & 1.0 & & & & & \\
$Quote$ pricechange   & 0.0 & 0.0 & N/A & 0.0 & $Quote$ volume    & 1.0 & 1.0 & 1.0 & 1.0\\
$Quote$ ticker    & 1.0 & 1.0 & 1.0 & 1.0 & $Quote$ shareprice  & 0.0 & N/A & N/A & 0.0 \\
}
{\bf source/field} & {\bf P} & {\bf R} & {\bf A} & {\bf source/field} & {\bf P} & {\bf R} & {\bf A} \\ \hline
$Amazon$ author  & 1.0 & 1.0 & 1.0 & $Smartpages$ name   & 1.0 & 0.9 & 0.9 \\
$Amazon$ title   & 1.0 & 0.7 & 0.7 & $Smartpages$ street & N/A & 0.0 & 0.0 \\
$Amazon$  price  & 0.9 & 0.9 & 0.9 & $Smartpages$ city   & 0.0 & 0.0 & 0.0 \\
$Amazon$  ISBN   & 1.0 & 0.9 & 0.9 & $Smartpages$ state  & 1.0 & 0.9 & 0.9 \\
$Amazon$ availability & 1.0 & 0.9 & 0.9 & $Smartpages$ phone  & N/A & 0.0 & 0.0\\
$Barnes\&Noble$ author & 1.0 & 0.5 & 0.5 & $Yahoo\ Quote$ pricechange & 1.0 & 0.2 & 0.2 \\
$Barnes\&Noble$ title  & 1.0 & 0.8 & 0.8 & $Yahoo\ Quote$ ticker    &  1.0 & 0.5 & 0.5 \\
$Barnes\&Noble$  price & 1.0 & 1.0 & 1.0 & $Yahoo\ Quote$ volume    &  1.0 & 0.7 & 0.7 \\
$Barnes\&Noble$  ISBN  & 1.0 & 1.0 & 1.0 & $Yahoo\ Quote$ shareprice & 1.0 & 0.7 & 0.7 \\
$Barnes\&Noble$ availability  &  1.0 & 1.0 & 1.0 & & & & \\
$Quote$ pricechange   & 0.0 & 0.0 & 0.0 & $Quote$ volume    & 1.0 & 1.0 & 1.0\\
$Quote$ ticker    & 1.0 & 1.0 & 1.0 & $Quote$ shareprice  & 0.0 & N/A & 0.0 \\
\hline
\end{tabular}
\normalsize
\caption{Precision, recall, and accuracy of the learned {\sc STALKER} rules for the changed sources}
\label{tbl:changed_sources}
\end{table}


\comment{The last column in Table~\ref{tbl:changed_sources} lists the percentage of $all$ data fields on the test pages that were correctly extracted by the automatically learned {\sc Stalker} rules, including those fields for which an insufficient number of examples was identified during the data extraction step. The recall and precision values for the changed sources were $P=0.90$ and $R=0.75$. These results can be substantially improved if we include more training examples in the set used by {\sc DataProG} to learn the patterns to describe the data (in the automatic data extraction step). Using fifteen rather than ten examples leads to the following percentage of the total number of data fields correctly extracted from the test pages: $amazon=90\%$, $Barnes\&Noble=88\%$, $Quote=50\%$, $Smartpages=60\%$, $Yahoo\ Quote=100\%$, with $P=0.94$, $R=0.86$.
}
As mentioned earlier, we believe we can achieve better performance for the yellow-pages-type sources $Bigbook$ and $Smartpages$ by using more training examples. Figure~\ref{fig:lc} shows the effect increasing the size of the training example set on the performance of the automatically generated wrappers for the $Smartpages$ source. As the number of training examples goes up, the accuracy of most extracted fields goes up. 


\subsubsection{Lists}
We have also applied the reinduction algorithm to extract data from pages containing lists of tuples, and, in many cases, have successfully extracted at least several examples of each field from several pages. However, in order to learn the correct extraction rules for sources returning lists of data, {\sc Stalker} requires that the first, last and at least two consecutive list elements be correctly specified. The methods presented here cannot guarantee that the required list elements are extracted, unless all the list elements are extracted. We are currently working on new approaches to data extraction from lists~\cite{Lerman-ATEM01} that will enable us to use {\sc Stalker} to learn the correct data extraction rules.



\section{Previous Work}
There has been a significant amount of research activity in the area of pattern learning. In the section below we discuss two approaches, grammar induction and relational learning, and compare their performance to {\sc DataProG} on tasks in the Web wrapper application domain. In Section~\ref{sec:maintenance} we review previous work on topics related to wrapper maintenance, and in Section~\ref{sec:ie} we discuss related work in information extraction and wrapper induction.

\subsection{Pattern Learning}
\label{sec:pattern-learning}
\subsubsection{Grammar induction}
Several researchers have addressed the problem of learning the structure, or patterns, describing text data.
In particular, grammar induction algorithms have been used in the past to learn the common structure of a set of strings. Carrasco and Oncina  proposed ALERGIA~\cite{ALERGIA}, a stochastic grammar induction algorithm that learns a regular language from positive examples of the language. ALERGIA starts with a finite state automaton (FSA) that is initialized to be a prefix tree that represents all the strings of the language. ALERGIA uses a state-merging approach~\cite{Angluin82,Stolcke94} in which the FSA is generalized by merging pairs of statistically similar (at some significance level) subtrees. Similarity is based purely on the relative frequencies of substrings encoded in the subtrees. The end result is a minimum FSA that is consistent with the grammar.

Goan et al.~\cite{GoanEtAl96} found that when applied to data domains commonly found on the Web, such as addresses, phone numbers, \etc, ALERGIA tended to merge too many states, resulting in an over-general grammar. They proposed modifications to ALERGIA, resulting in algorithm WIL, aimed at reducing the number of faulty merges. 
The modifications were motivated by the observation that each symbol in a string belong to one of the following syntactic categories: {\sc NUMBER, LOWER, UPPER} and {\sc DELIM}. When viewed on the syntactic level, data strings contain additional structural information that can be effectively exploited to reduce the number of faulty merges. WIL merges two subtrees if they are similar (in the ALERGIA sense) and also if, at every level, they contain nodes that are of the same syntactic type. WIL also adds a wildcard generalization step in which the transitions corresponding to symbols of the same category that are approximately evenly distributed over the range of that syntactic type (\eg, 0--9 for numerals) are replaced with a single transition corresponding to the type (\eg, {\sc NUMBER}). Goan {\em et al.} demonstrated that the grammars learned by WIL were more effective in recognizing new strings in several relevant Web domains.

We compared the performance of WIL to {\sc DataProG} on the wrapper verification task. 
We used WIL to learn the grammar on the token level using data examples extracted by the wrappers, not on the character level as was done by Goan \ea Another difference from Goan {\em et al.} was that, whereas they needed on the order of $100$ strings to arrive at a high accuracy rate, we have on the order of $20$--$30$ examples to work with. Note that we can no longer apply the wildcard generalization step to the FSA because we would need many more examples to decide whether the token is approximately evenly distributed over that syntactic type. Instead, we compare {\sc DataProG} against two versions of WIL: one without wildcard generalization (WIL1), and one in which every token in the initial FSA is replaced by its syntactic type (WIL2). In addition to the syntactic types used by Goan \ea, we also had to introduce another type {\sc ALNUM} to be consistent with the patterns learned by {\sc DataProG}. Neither version of WIL allows for multi-level generalization.

The algorithms were tested  
on data extracted by wrappers from $26$ Web sources on ten different occasions over a period of several months (see Sec.~\ref{sec:verification}). Results of $20$--$30$ queries were stored every time. For each wrapper, one data set was used as the training examples, and the data set extracted on the very next date was used as test examples. 
We used WIL1 and WIL2 to learn the grammar of each field of the training examples and then used the grammar to recognize the test examples. If the grammar recognized more than 80\% of the test examples of a data field, we concluded that it recognized the entire data field; otherwise, we concluded that the grammar did not recognize the field, possibly because the data itself has changed. This is the same procedure we used in the wrapper verification experiments, and it is described in greater detail in Section~\ref{sec:verification-results}. Over the period of time covered by the data, there were $21$ occasions on which a Web site changed, thereby causing the data extracted by the wrapper to change as well. The precision and recall values for WIL1 (grammar induction on specific tokens) were $P=0.20$, and $R=0.81$; for WIL2 (grammar induction on wildcards representing tokens' syntactic categories) the values were $P=0.55$ and $R=0.76$. WIL1 learned an overly specific grammar, which resulted in a high rate of false positives on the verification task, while WIL2 learned an overly general grammar, resulting in slightly more false negatives. The recall and precision value of {\sc DataProG} for the same data were $P=0.73$ and $R=1.0$. 

Recently Thollard \ea~\cite{Thollard00} introduced MDI, an extension to ALERGIA. MDI has been shown to generate better grammars in at least one domain by reducing the number of faulty merges between states . MDI replaces ALERGIA's state merging criterion with a more global measure that attempts to minimize the Kullback-Leibler divergence between the learned automaton and the training sample while at the same time keeping the size of the automaton as small as possible. It is not clear whether MDI (or a combination of MDI/WIL) will lead to better grammars for common Web data types. We suspect not, because regular grammars capture just a few of the multitude of data types found on the Web. For example, business names, such as restaurant names shown in Table~\ref{tbl:bigbook_examples} may not have a well defined structure, yet many of them start with two capitalized words and end with the word ``Restaurant'' --- which constitute patterns learned by {\sc DataProG}.


% foil
\subsubsection{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~\cite{Quinlan90} 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. 
% example encoding
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 
\begin{equation}
data\ field(A) := P(A)\ followed\_by(A,B)\ P(B)\,, \nonumber
\end{equation}
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 (\eg, $John(A)$) or a general type (\eg, ${\sc Upper}(A)$, ${\sc Alpha}(A)$), thus, allowing FOIL the same multi-level generalization capability as {\sc DataProG}.

We ran Foil.6 on the examples associated with the $Bigbook$  (see Tables~\ref{tbl:bigbook_examples}--\ref{tbl:bigbook_examples2}). The relational definitions learned by Foil.6 from these examples are shown in Table~\ref{tbl:foil-bigbook}.


\begin{table}
\tt{
\begin{tabbing}
*** \= tabbing only \kill
***  Warning: the following definition does not cover 23 tuples in the relation\\
\>{\small NAME}(A) := {\sc AllCaps}(A), followed\_by(A,B)\\
\>{\small NAME}(A) := {\sc Upper}(A), followed\_by(A,B), {\sc Number}(B)\\
\>{\small NAME}(A) := followed\_by(A,B), Venice(B)\\
\\
\>{\small STREET}(A) :=  {\sc Large}(A), followed\_by(A,B)\\
\>{\small STREET}(A) := {\sc Medium}(A), followed\_by(A,B), {\sc AlphaNum}(B)\\
\\
***  Warning: the following definition does not cover 9 tuples in the relation\\
\>{\small CITY}(A) := Los(A)\\
\>{\small CITY}(A) := Marina(A)\\
\>{\small CITY}(A) := New(A)\\
\>{\small CITY}(A) := Brooklyn(A)\\
\>{\small CITY}(A) := West(A), followed\_by(A,B), {\sc Alpha}(B)\\
\\
\>{\small STATE}(A) := CA(A)\\
\>{\small STATE}(A) := NY(A)\\
\\
\>{\small PHONE}(A) := ((A)
\end{tabbing}
\caption{Definitions learned by foil.6 for the $Bigbook$ source}}
\label{tbl:foil-bigbook}
\end{table}


In many cases, there were similarities between the definitions learned by FOIL and the patterns learned by {\sc DataProG}, though clauses learned by FOIL tended to be overly general. 
\comment {
For example, the algorithm learned that `(' was a good description of phone numbers for the $Bigbook$ source. 
The over-general description will result in poor performance on the reinduction task (Sec.~\ref{sec:reinduction}), where the patterns are used to recognize instances of the data field. We attribute over-generalization to the incompleteness of the set of negative examples presented to FOIL. }
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.

\subsection{Wrapper Maintenance}
\label{sec:maintenance}
% related research
Kushmerick \cite{Kushmerick99} addressed the problem of wrapper verification by proposing an algorithm {\sc 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, \ie, proportion of characters in the training examples that are of an HTML, alphabetic, or numeric type. 
{\sc 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, {\sc 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, {\sc Rapture} decides that the wrapper is correct; otherwise, that it has failed.
Kushmerick found that the HTML density alone can correctly identify almost all of the changes in the sources he monitored. 
In fact, adding other features in the probability calculation significantly reduced algorithm's performance. 
We compared {\sc Rapture}'s performance on the verification task to our approach, and found that {\sc Rapture} missed $17$ wrapper changes (false negatives) if it relied solely on the HTML density feature. 
\footnote{Although we use a different statistical test and cannot compare the performance of our algorithm to {\sc Rapture} directly, we doubt that it would outperform our algorithm on our data set if it used all global numeric features, because, as we noted in Section~\protect\ref{sec:verification-results}, using patterns as well as global numeric features in the verification task outperforms using numeric features only.}


%{Previous Work on Wrapper Reinduction}
There has been relatively little prior work on the wrapper reinduction problem. Cohen~\cite{Cohen99} adapted {\sc WHIRL}, a ``soft'' logic that incorporates a notion of statistical text similarity, to recognize page structure of a narrow class of pages: those containing simple lists and simple hotlists (defined as anchor-URL pairs). Previously extracted data, combined with page structure recognition heuristics, was used to reconstruct the wrapper once the page structure changed. Cohen conducted wrapper maintenance experiments using original data and corrupted data as examples for {\sc WHIRL}. However, his procedure for corrupting data was neither realistic nor representative of how data on the Web changes. Although we cannot at present guarantee good performance of our algorithm on the wrapper reinduction for sources containing lists, we handle the realistic data changes in Web sources returning detail pages. 

\subsection{Information Extraction}
\label{sec:ie}
Our system, as used in the reinduction task, is related in spirit to the many information extraction (IE) systems developed both by our group and others in that it uses a learned representation of data to extract information from specific texts. Like wrapper induction systems (see \cite{Muslea01,Kushmerick97,Freytag00}), it is domain independent and works best with semi-structured data, {\em e.g.}, Web pages. It does not handle free text as well as other systems, such as {\sc AutoSlog}~\cite{Riloff93} and {\sc Whisk}~\cite{Soderland99}, because free text has fewer non-trivial regularities the algorithm can exploit. Unlike wrapper induction, it does not extract data based on the features that appear near it in text, but rather based on the content of data itself. However, unlike {\sc Whisk}, which also learns content rules, our reinduction system represents each field independently of the other fields, which can be an advantage, for instance, when a web source changes the order in which data fields appear. Another difference is that our system is designed to run automatically, without requiring any user interaction to label informative examples. In the main part because it is purely automatic, the reinduction system fails to achieve the accuracy of other IE systems which rely on labeled examples to train the system; however, we do not see it as a major limitation, since it was designed to {\em complement} existing extraction tools, rather than supersede them. In other words, we consider the reinduction task to be successful if it can accurately extract a sufficient number of examples to use in a wrapper induction system. The system can then use the resulting wrapper to accurately extract the rest of the data from the source.

There are many similarities between our approach and that used by the {\sc RoadRunner} system, developed concurrently with our system and reported recently in \cite{RoadRunner1,Roadrunner2}. The goal of that system is to automatically extract data from Web sources by exploiting similarities in page structure across multiple pages. {\sc RoadRunner} works by inducing the grammar of Web pages by comparing several pages containing long lists of data. The grammar is expressed at the HTML tag level, so it is similar to the extraction rules generated by {\sc Stalker}. The {\sc RoadRunner} system has been shown to successfully extract data from several Web sites. The two significant differences between that work and ours are (i) they do not have a way of detecting changes to know when the wrapper has to be rebuilt and (ii) our reinduction algorithm works on detail pages only, while {\sc RoadRunner} works only on lists. We believe that our data-centric approach is more flexible and will allow us to extract data from more diverse information sources than the {\sc RoadRunner} approach that only looks at page structure. 


\section{Conclusion}
In this paper we have described the {\sc DataProG} algorithm, which learns structural information about a data field from a set of examples of the field. We use these patterns in two Web wrapper maintenance applications: (i) {\bf verification} --- detecting when a wrapper stops extracting data correctly from a Web source, and (ii) {\bf reinduction}  --- identifying new examples of the data field in order to rebuild the wrapper if it stops working. The verification algorithm performed with an accuracy of $97\%$, much better than results reported in our earlier work \cite{KLerman00}. In the reinduction task, the patterns were used to identify a large number of data fields on Web pages, which were in turn used to automatically learn {\sc Stalker} rules for these Web sources. The new extraction rules were validated by using them to successfully extract data from sets of test pages.


There remains work to be done on wrapper maintenance. Our current algorithms are not sufficient to automatically re-generate {\sc Stalker} rules for sources that return lists of tuples. However, preliminary results indicate~\cite{Lerman-ATEM01} that it is feasible to  combine information about the structure of data with {\em a priori} expectations about the structure of Web pages containing lists to automatically extract data from lists and assign it to rows and columns. We believe that these techniques will eventually eliminate the need for the user to mark up Web pages and enable us to automatically generate wrappers for Web sources. Another exciting direction for future work is using the {\sc DataProG} algorithm to automatically create wrappers for new sources in some domain given existing wrappers for other sources in the same domain. For example, we can learn the author, title and price fields for the $Amazon Books$ source, and use them to extract the same fields on the $Barnes\&Noble Books$ source. Preliminary results show that this is indeed feasible. 
Automatic wrapper generation is an important cornerstone of information-based applications, including Web agents.



\section{Acknowledgments}
We would like to thank Priyanka Pushkarna for carrying out the wrapper verification experiments.

The research reported here was supported in part by the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory under contract/agreement numbers  F30602-01-C-0197, F30602-00-1-0504, F30602-98-2-0109, in part by the Air Force Office of Scientific Research under grant number F49620-01-1-0053, in part by the Integrated Media Systems Center, a National Science 
Foundation (NSF) Engineering Research Center, cooperative agreement number EEC-9529152 and in part by the NSF under award number DMI-0090978. The U.S. Government is authorized to reproduce and distribute reports for Governmental purposes notwithstanding any copy right annotation thereon.
The views and conclusions 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.


% Bibliography
\vskip 0.2in
\bibliography{../../../tex/bib/ai,../../../tex/bib/agents,../../../tex/bib/lerman}
\bibliographystyle{theapa}
%
\end{document}
