%===========================================================
\documentclass[12pt,a4paper, fleqn, leqno, twoside]{article}

% The 'mathptmx' package will change the default roman font family to Times,
% and the virtual 'mathptmx' fonts will be used for math.
% In case of problems, use \usepackage{times}
% in place of \usepackage{mathptmx}

\usepackage{mathptmx}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
% \usepackage{graphicx}
\usepackage{longtable}

\usepackage{wac3}

\newcommand{\mysubsection}[1]{\subsection*{\bf #1}}

%===========================================================
% HEADER
%
% Please complete the \headertitle
% with a (short if necessary) version of your title
% and the \headerauthor with the author(s) :
% initial of the first name of the author(s) and name of the author(s)
%with commas between each author
%===========================================================

%\headertitle{Victor: The Ultimate Web Page Cleaner}
\headertitle{Web Page Cleaning with Conditional Random Fields}

\headerauthor{Michal Marek, Pavel Pecina, Miroslav Spousta}
%===========================================================
% DOCUMENT
%===========================================================

\begin{document}

%\title{Victor: The Ultimate Web Page Cleaner}
\title{Web Page Cleaning with Conditional Random Fields}

\author{Michal Marek\footnote{Institute of Formal and Applied Linguistics, Charles University, Prague, Czech Republic, \{marek,pecina,spousta\}@ufal.mff.cuni.cz},
Pavel Pecina\,\footnotemark[1], Miroslav Spousta\,\footnotemark[1] }

\maketitle

\abstract{This paper describes the participation of the Charles University in Cleaneval 2007, the shared task and competitive evaluation of automatic systems for cleaning arbitrary web pages with the goal of preparing web data for use as a corpus in the area of computational linguistics and natural language processing.
We try to solve this task as a sequence-labeling problem and our experimental system is based on Conditional Random Fields exploiting a set of features extracted from textual content and HTML structure of analyzed web pages for each block of text. Labels assigned to these blocks then discriminate between different types of \textit{\small content blocks} containing useful material that should be preserved in the document and \textit{\small noisy blocks} of no linguistics interest that should be eliminated.}

% The keywords in English
% Note that a period will be automatically added
% at the end of the keywords list.
\keywords{Web page cleaning, Sequence labeling, Conditional random fields}

% don't remove the \selectnormalfont
% \selectnormalfont set the size of normal font to 13pt
\selectnormalfont

%===========================================================

\section{Introduction}

The web with its enormous amounts of textual materials is a rich and easily accessible source of linguistic data that can be used to create extremely large corpora with relatively low cost and within a short period of time (compared to the traditional way of building text corpora which is an expensive and time-consuming process). The idea of having a corpus ``as large as the web'' recently attracted attention of many researchers in computational linguistics, natural language processing, and related areas, who would greatly benefit from such amount of data. Creating such a corpus comprises two steps: a) \textit{web crawling} - automatic browsing the web and keeping a copy of visited pages and b) \textit{cleaning} the pages to be included in the corpus. In this work we focus on the latter.

Apart from the main content, a typical web page contains other material of no linguistic interest, such as  navigation bars, panels, and frames, page headers and footers, copyright and privacy notices, advertisements and other data (often called \textit{boilerplate}). The goal is to detect and remove such parts from an arbitrary web page.

Although this task might seem too heterogeneous for methods based on supervised training to be appropriate, we solve it as a sequence-labeling problem with Conditional Random Fields trained on a manually cleaned set of web pages. Our primary goal is an attempt to explore whether supervised training methods can perform well enough to be successfully used in this task.

\section{Related Work}

Although web page cleaning is a crucial step in the procedure of building a web corpus, only a relatively little work has been done in this area. Most of it originated in the area of web mining and search engines, e.g. \cite{Cooley1999} or \cite{Lee2000}. In \cite{Bar2002}, a notion of pagelet determined by the number of hyperlinks in the HTML element is employed to segment a web page; pagelets whose frequency of hyperlinks exceeds a threshold are removed. \cite{Lin2002} extract keywords from each block content to compute its entropy, and blocks with small entropy are identified and removed. In  \cite{Yi2003a} and \cite{Yi2003b}, a tree structure is introduced to capture the common presentation style of web pages and entropy of its elements is computed to determine which element should be removed.  In \cite{Chen2006}, a two-stage web page cleaning method is proposed. First, web pages are segmented into blocks and blocks are clustered according to their style features. Second, the blocks with similar layout style and content are identified and deleted. As far as the authors know, none of the published method was based on sequence labeling or a similar learning algorithm.

%
% TODO (Pavel): \textit{zminka o pristupu ostatnich metod, odkaz na WAC. Toto je pomerne nezavisle a nechal bych to az na konec}.
% 

% A description of our system in Section 2 is followed by detailed overview of features a
% In Section 2, we give an overview of our system

\section{System Overview}

% \cite{crf}

% The units being labeled by Condition Random fields


% This
% approach has two potential problems:
% 
% \begin{itemize}
% \item A given block is classified as whole, there is no way to classify
% a part of a block differently that the rest. In practice, this turned
% out to be a significant problem only for text inside the {\tt <pre>}
% element.  Therefore, inside the {\tt <pre>} element, each line of text
% is separated with a {\tt <br>} tag, splitting the content into multiple
% blocks. This allows each line to be classified separately.
% 
% \item Some text rendered on web pages is contained in tag attributes,
% which are ignored by the parser. This is especially true for the {\tt
% alt} attribute of the {\tt <img>} tag and the {\tt value} attribute of
% the {\tt <input>} tag. Fir {\tt <img>}, this is solved by copying the
% alternative text into an artificial text child the of {\tt <img>}
% element in the preclean stage.  We believe that most {\tt <input>} tags
% on the Web don't carry any useful information in their {\tt value}
% attributes, therefore we ignore them (although the workaround would be
% the same).
% 
% \end{itemize}
% 

The system for web page cleaning presented in this paper is based on sequence labeling with CRF++\footnote{http://crfpp.sourceforge.net/} implementation of Conditional Random Fields \cite{Lafferty2001}. It is aimed at cleaning arbitrary web pages as specified in the Cleaneval shared task
description\footnote{http://cleaneval.sigwac.org.uk/}.  The cleaning process consists of several steps:

\mysubsection{1) Standardizing HTML code}

The raw HTML input is passed through Tidy\footnote{http://tidy.sourceforge.net/}
%(either via pipes to the tidy binary, or using the {\tt HTML::Tidy} Perl module),
in order to get a valid and parsable HTML tree. During development, we found only
one significant problem with Tidy, namely interpreting JavaScript inside the {\tt <script>} element, and employed a simple  workaround for it in our system. Except for this particular problem which occurred only once in our training data, Tidy has proved to be a good choice.

\mysubsection{2) Precleaning}

Afterwards, the HTML code is parsed  and parts that are guaranteed not to carry any useful text (e.g. scripts, style definitions, embedded objects, etc.) are removed from the HTML structure. The result is a valid HTML code.

\mysubsection{3) Text block identification}
\enlargethispage{2mm}

%\subsubsection{\label{split}Parsing Precleaned HTML}

In this step, the precleaned HTML text is again parsed with a HTML parser and interpreted as a sequence of text \textit{blocks} separated by one or more HTML tags. For example, the snippet
% \begin{verbatim}
        {\tt ``<p>Hello <b>world</b>!</p>''}
% \end{verbatim}
would be split into three blocks, {\tt ``Hello''}, {\tt ``world''}, and {\tt ``!''}.  Each of the blocks is then a subject of the labeling task and cleaning.

% % denoted by the {\tt
% %<span>} tags added in the preclean.
% %
% Also, while traversing the HTML
% tree, the {\it containers}, {\it distance}, {\it td\_group} and {\it
% div\_group} fields are filled for use by the feature extraction modules
% later. Currently, these fields are always generated, even when
% running the annotation tool (which doesn't need any feature
% vectors)\footnote{On a 2.40GHz Pentium 4 machine, not generating these
% fields would save only about 0.06 seconds when parsing a 150 Kb HTML
% file, so optimizing here is not worth it.}.

\mysubsection{4) Feature extraction}

In this step, a feature vector is generated for each block. The list of features and their detailed description is presented in the next section. The features must have a finite set of values\footnote{This is a limitation of the CRF tool used.}. The mapping of integers and real numbers into finite sets was chosen empirically and is specified in the configuration.
%  
% are represented as integers  number and. To fulfill
% this criterium, those features that are based on natural
% numbers (e.g. number of words in a block) or fractions (e.g. relative
% position in the document) are mapped into finite sets as specified in
% configuration.
% 
%This step of the system is designed in a way that
Most features are generated separately by independent modules. This allows for adding other features and switching between them for different tasks.
% (e.g. for different languages).

\mysubsection{5) Learning}

In accordance to the Cleaneval annotation guidelines and definition of the markup tags, each \textit{content block} occurring in our training data was manually assigned one of the following labels: {\it header}, {\it paragraph}, {\it list}, and {\it continuation} for blocks that are in fact continuations of preceding content blocks of any type. Other blocks are considered as \textit{noisy blocks} and are assigned the label \textit{other}.

The sequence of feature vectors including labels extracted for all blocks from the training data are then transformed into the actual features used for training the CRF model according to offset specification described in a \textit{template} file.

\mysubsection{6) Cleaning}

Having estimated parameters of the CRF model, an arbitrary HTML file can be passed through steps 1--4, and its blocks can be labeled with the same set of labels as described above. These automatically assigned labels are then used to produce a cleaned output. Blocks labeled as {\it header}, {\it paragraph}, or {\it list} remain in the document and are marked by a corresponding markup tag ({\tt <h>}, {\tt <p>}, {\tt <l>}), blocks labeled as {\it continuation} remains in the document as they are (no  tag is inserted) and blocks labeled as {\it other} are deleted.



% The CRF++ works with documents to have the following tabular
% format:
% 
% \begin{verbatim}
%     feature1 feature2 ... featureN tag
%     feature1 feature2 ... featureN tag
% \end{verbatim}
% 
% that is a table with rows representing {\it words} (text blocks in our
% case), columns representing features and the last column being the
% answer tag.. Given
% the amount of features used, we generate this template from another
% template, where features are referred to by their names for readability.
% 

\section{Features}

Features recognized by the system can be divided by their scope into three subsets:
features based on the HTML markup,  features based on textual content of the blocks, and features related to the document.

% features of individual text blocks, features of groups of blocks and
% features of the whole document. Furthermore, features can be divided by
% their source into features based on the HTML markup and features based
% on the text content of the blocks.

\mysubsection{Markup-based Features}

\begin{description}
%\enlargethispage{2mm}

\item{\it container.p, container.a, container.u,
container.img, container.class-header,}\\[-4.5ex]
\item{\it
container.class-bold, container.class-italic,
container.class-list, container.class-form}

For each parent element of a block, a corresponding {\it container.*}
feature will be set to 1, e.g. a hyperlink inside a paragraph will
have the features \textit{container.p} and \textit{container.a} set to 1. This feature is
especially useful for classifying blocks: For instance a block contained
in one of the {\tt <h{\emph x}>} elements is likely to be a header, a
{\it container.li} feature suggests a list item, etc. % In order to reduce
%the length of the feature vector \footnote{and therefore be able to train
%on a smaller set of documents.},
The {\it container.class-*} features refer to classes of similar elements rather than to
elements themselves.

\item{\it split.p, split.br, split.hr,
split.class-inline, split.class-block}

For each opening or closing tag encountered since the last block, we
generate a corresponding {\it split.*} feature. This is needed to
decide, whether a given block connects to the text of the previous block
(classified as {\it continuation}) or not. Also, the number of encountered tags
of the same kind is recorded in the feature. This is mainly because of the
{\tt <br>} tag; a single line break does not usually split a paragraph, while
two or more {\tt <br>} tags
usually do. The {\it split.class-*} features again refer to classes of similar elements.


\end{description}

\mysubsection{Content-based Features}

\begin{description}

\item{\it char.alpha-rel, char.num-rel, char.punct-rel, char.white-rel, char.other-rel}

These features represent the absolute and relative counts of characters
of different classes (letters, digits, punctuation, whitespace and
other) in the block.

\item{\it token.alpha-rel, token.num-rel, token.mix-rel, token.other-rel
token.alpha-abs},\\[-4.5ex]
\item{\it token.num-abs, token.mix-abs, token.other-abs}

These features reflect counts distribution of individual classes of
tokens\footnote{Tokens being sequences of characters separated by
whitespace for this purpose.}. The classes are words, numbers, mixture of
letters and digits, and other.

\item{\it sentence.count}

Number of sentences in a block. We use a naive algorithm basically
counting periods, exclamation marks and question marks, without trying to
detect abbreviations. Given that the actual count is mapped into a small
set of values anyway, this does not seem to be a problem.
%\footnote{For
%Czech language, we use a module, developed by one of our colleagues, that
%also detects abbreviations. But we didn't think it's worth the effor
%creating a new module for English}
          
\item{\it sentence.avg-length}

Average length of a sentence, in words.

\item{\it sentence-begin, sentence-end}

These identify text blocks that start or end a sentence.  This helps
recognizing headers and list items (as these usually do not end with a
period) as well as continuation blocks ({\it sentence-end=0} in the
previous blocks and {\it sentence-start=0} in the current block suggest
a continuation).
          
\item{\it first-duplicate, duplicate-count}

The {\it duplicate-count} feature counts the number of blocks with the same content
(ignoring white space and non-letters). The first block of a group of
twins is then marked with {\it first-duplicate}. This feature serves two
purposes: On pages where valid text interleaves with noise (blogs, news
frontpages, etc), the noise often consists of some phrases like ``read
more...'', ``comments'', ``permalink'', etc, that repeat multiple times
on the page. The second purpose of this feature is to identify quotes in
discussions, which are deleted in the Cleaneval development set. The
{\it first-duplicate} feature is then used to recognize the original post.
% Especially for the second use case, there is room for improvement in
% being able to express different levels of text similarity among the
% blocks, to be able to also detect quotes of parts of the original text.

\item{\it regexp.url, regexp.date, regexp.time}

While we try to develop a tool that works independently of the human
language of the text, some language-specific features are needed
nevertheless. The configuration defines each {\it regexp.*} feature as
an array of regular expressions. The value of the feature is the number
of the first matching expression (or zero for no match).  We use three
sets of regular expressions: to identify times and dates (lines with
creation date/time are marked as {\it header} in Cleaneval data) and URLs (these
are usually cleaned away in the Cleaneval data).

\item{\it bullet}

This is a specialized version of the {\it regexp.* } features, matching different
patterns that suggest a list item (number or a single letter, closing
parenthesis, dash, etc). Each combination of matches results in a
different value of the feature, so that lists can be recognized as a
sequence of blocks with the same {\it bullet} value.

\item{\label{td-group}\it div-group.word-ratio, td-group.word-ratio}

The layout of many web pages follows a similar pattern: The main content
is enclosed in one big {\tt <div>} or {\tt <td>} element, as are the
menu bars, advertisements etc. To recognize this feature and express it
as a number, the parser groups blocks that are direct descendants of the
same {\tt <div>} element ({\tt <td>} element respectively). A direct
descendant in this context means that there is no other {\tt <div>}
element ({\tt <td>} element respectively) in the tree hierarchy between
the parent and the descendant. For example in this markup

\begin{verbatim}
    <div> a <div> b c </div> d <div> e f </div> g </div>
\end{verbatim}

the {\it div-group}s would be (a, d, g), (b,c) and (e, f). The {\it
div-group.word-ratio} and {\it td-group.word-ratio} express the
relative size of the group in number of words. To better distinguish
between groups with noise (e.g. menus) and groups with text, only words
not enclosed in {\tt <a>} tags are considered.


\end{description}

\mysubsection{Document-related features}

\begin{description}

\item{\it position}

This feature reflects a relative position of the block in the document
(counted in blocks, not bytes). The rationale behind this feature is
that parts close to the beginning and the end of documents usually
contain noise.

\item{\it document.word-count, document.sentence-count, document.block-count}

This feature represents the number of words, sentences and text blocks in the
document. 

\item{\it document.max-div-group, document.max-td-group}

The maximum over all {\it div-group.word-ratio} and a maximum over all
{\it td-group.word-ratio} features. This allows us to express
``fragmentation'' of the document -- documents with a low value of one of these features are composed of small chunks of text (e.g. web bulletin boards).

\end{description}

% {%\small
% \setlength\LTleft{0pt}
% \setlength\LTright{0pt}
% 
% \begin{longtable}{p{3.5cm}p{11.75cm}}
% \hline
% {\small \bf Features } & {\small \bf Description }\\
% \hline
% {\it \small
% container.p\vfil
% container.a\vfil
% container.u\vfil
% container.img
% } & {%
% For each parent element of a block, a corresponding {\tt container.*}
% feature will be set to {\tt 1}. E.g. a hyperlink inside a paragraph will
% have the features container.p and container.a set to 1. This feature is
% especially useful for classifying blocks: For instance a block contained
% in one of the {\tt <h{\emph x}>} elements is likely to be a header, a
% {\tt container.li} feature suggests a list item, etc. } \\
% \hline
% {\it \small
% container.class-header\vfil
% container.class-bold\vfil
% container.class-italic\vfil
% container.class-list\vfil
% container.class-form
% } & {%
% } \\
% \hline
% {\it \small
% split.p\vfil
% split.br\vfil
% split.hr\vfil
% split.class-inline\vfil
% split.class-block
% } & {%
% 
% } \\
% 
% \end{longtable}
 

\section{Data and Evaluation}

For our development purposes we had 104 manually cleaned HTML documents available: 51 of them were provided by Cleaneval and the rest was randomly selected, downloaded, and cleaned following the same guidelines by a volunteer. In this development data set, 22\,501 blocks were identified and assigned appropriate labels. Their distribution is shown in the following table.

\begin{table}[h]
  
\begin{center}
\begin{tabular}{|l|r|}
\hline
label & count \\
\hline
header & 1\,996 \\
list  & 1\,149 \\
paragraph  &  3\,419 \\
continuation &   3\,380 \\
\hline
total (\textit{content}) & 9\,944 \\
\hline
other (\textit{noise})  & 12\,557 \\
\hline
\end{tabular}
\end{center}
\caption{Labels distribution in the development data set.}
\label{tab2}
\end{table}

The data set was randomly split into six subsets and for better estimation of performance measures used in a six-fold crossvalidation. Evaluation measures were of two types: \\
\noindent \textbf{a) labeling accuracy} -- the  ratio of correctly assigned block labels {\small(1)} from the full label set and {\small(2)} distinguishing only between \textit{content} and \textit{noisy} blocks;\\
\noindent \textbf{b) cleaning performance} -- the official Cleaneval scoring measures based on {\small(3)} edit distance and the extent to which the markup tags indicate blocks of text starting and ending in the same place and {\small(4)} alignment of text alone, ignoring the markup tags plus {\small (5)} a combination of the latter two referred as the total score.

\section{Experiments and Results}

First, we have performed a series of experiments where we disabled each of the 46 features one by one with the following observations:

The variance among the results on the six crossvalidation subsets was relatively high in all experiments; the total score ranged from 66\% to 80\%. This is partially caused by the relatively small amount of training and test data in each run but it also proves the heterogenous character of the task.

In contrast, the difference among the results of all experiments was relatively low. The total scores ranged from 71.9\% to 74.5\%. A possible explanation is a certain redundancy in the feature set.

Disabling some of the features slightly improved the
results. The total score with all features enabled was 73.9\%, while
disabling the {\it document.word-count} feature resulted in a score of
74.6\%. Although this difference is probably not statistically significant we used
this criterion and disabled some features for cleaning the evaluation
data.

We also performed two other experiments: one with only the content-based
features enabled and one with only the markup-based features enabled.
Surprisingly, the results only dropped to 65.3\% for markup-only and
66.5\% for content-only features. This gives us an idea how much information is taken from these two types of features and how much we gain from their combination.

% TODO: nejake moudro co zo toho plyne? :)

For the Cleaneval evaluation, we have chosen three experimental settings: Exp-1
with all features enabled, Exp-2 with the features {\it word-ratio}, {\it
numeric-count}, {\it mixed-count} and {\it nonword-count} disabled, and Exp-3 with two more additionally disabled features {\it regexp.url} and {\it document.word-count}.
The cross-validated results on the development data set for these experiments are displayed in Table 2.

\begin{table}[ht]
\begin{center}
\begin{tabular}[c]{|l|c|c|c|c|c|}

\hline  & \multicolumn{2}{c|}{labeling accuracy (\%)} & \multicolumn{3}{c|}{cleaning performance (\%)}\\
\cline{2-6}  & ~ {\small (1)} full set ~ &{\small(2)} content-noise&{\small(3)} markup-only& ~ {\small (4)} text-only ~ & ~ ~ {\small (5)} total ~ ~ \\
\hline
Exp-1  & 74.45 &  82.60 &  66.71 & 81.11 & 73.92 \\
Exp-2  & 75.09 &  83.09 & 67.31  & 81.68 & 74.50\\
Exp-3 & 75.01 &  82.88  & 68.46 & 81.83 & 75.15\\
\hline
\end{tabular}
\end{center}
\caption{Labeling accuracy and cleaning performance on the development data.}

\end{table}


\section{Conclusion}
We proposed a method for web page cleaning based on sequence labeling with Conditional Random Fields and presented a few initial experiments evaluated on the development data for Cleaneval 2007. With very limited costs and manual work we were able to achieve encouraging results. Using supervised training methods seems as a reasonable approach and we believe that a better set of features can bring additional performance improvement.

% You can use sections, subsections and subsubsections.
% 
% You must use the English quotes (\verb|``| and \verb|''|). Latex inserts
% automatically a double space after a period. So, if you use a period in
% other contexts (in an abreviation, for example), make use of \verb|\@| to
% insert a single space in place of a double space.
% 
% Use the ``cite'' command to insert citations in the document. For example : 
% 
% \cite{lorem1}, \cite[12--14]{lorem2},
% \cite{lorem3,lorem4,lorem5,lorem6,lorem7,lorem8,lorem9,lorem10} and
% \cite{lorem11,lorem12,lorem13}.
% 
% This is a table (table \ref{table}).
% 
% \begin{table}[ht]
% \begin{center}
% \begin{tabular}[c]{|r|c|l|}
% \hline Lorem ipsum & dolor & sit amet \\ 
% \hline consectetuer & adipiscing & elit \\
% \hline
% \end{tabular}
% \end{center}
% \caption{Lorem ipsum table}\label{table}
% \end{table}
% 
% And this is a figure (figure \ref{figure}).
% 
% \begin{figure}[ht]
% \begin{center}
% \includegraphics[width=5cm]{cicero.eps}
% \end{center}
% \caption{Marcus Tullius Cicero}
% \label{figure}
% \end{figure}


%====================================================================
\section*{Acknowledgments}
This work has been supported by the Ministry of Education of the Czech Republic, projects MSM 0021620838 and the Czech Science Foundation, project  201/05/H014.


%We would like to thank our advisor Jan Haji\v{c}, our colleagues for their valuable comments.

%====================================================================
% BIBLIOGRAPHY
% See biblio.bib for examples
%====================================================================
\bibliographystyle{wac3}
\bibliography{biblio}

%===================================================================
\end{document}

% vim: et tw=72
