\documentclass[twoside,11pt]{article}
%\usepackage{/home/osborne/latex/colacl,lscape,graphics}
%\usepackage{epsfig}
%\usepackage{/home/osborne/latex/jmlr2e}
%\usepackage{/home/miles/latex/jmlr2e}
\usepackage{jmlr2e}
\jmlrheading{1}{2002}{695-719}{9/01}{3/02}{Miles Osborne}
\ShortHeadings{Shallow Parsing and Noise}{Osborne}
\firstpageno{695}
\begin{document}


\title{Shallow Parsing using  Noisy and Non-Stationary Training Material}
\author {\name Miles Osborne \email osborne@cogsci.ed.ac.uk \\ 
\addr
 Division of Informatics \\  University of
  Edinburgh \\ 2
    Buccleuch Place \\ Edinburgh EH8 9LW,  Scotland.
 }

\editor{James Hammerton, Miles Osborne, Susan Armstrong  and Walter Daelemans}

\maketitle
\newtheorem{sent}{}
\newcommand{\labelRule}[2]{\begin{center}\begin{tabular}{ll} #1 & (#2) \end{tabular} \end{center}}
\newcommand{\lexical}[2]{\begin{tabular}{l} #1 $\mapsto$ #2 \end{tabular}}
\newcommand{\numberSentence}[1]{\begin{sent} \small #1 \end{sent}}
\newcommand{\cat}[1]{$\mbox{#1}$}
\newcommand{\lcat}[1]{$\backslash \mbox{#1}$}
\newcommand{\rcat}[1]{$/ \mbox{#1}$}
\newcommand{\psr}[2]{$#1 \rightarrow #2$}
%\setcounter{page}{61}
%
% Displayed natural-language sentence
%
\newcommand{\sentence}[1]
     {\begin{flushleft}{\it #1}\end{flushleft}}


\begin{abstract}
Shallow parsers are usually assumed to be trained on {\it noise-free}
material, drawn from the same distribution as the testing
material. However, when either the training set is {\it noisy} or else
drawn from a {\it different} distributions,
performance may be degraded.  Using the parsed Wall Street Journal, we 
investigate the performance of four shallow parsers (maximum entropy,
memory-based learning, N-grams and ensemble learning)  trained using 
various types of artificially noisy material.  Our first set of results show that shallow parsers
are surprisingly robust to synthetic noise, with performance gradually
decreasing as the rate of noise increases.  Further
results show that no single shallow parser performs best in all noise
situations. Final results show that simple, parser-specific extensions
can improve noise-tolerance.
Our second set of results addresses the question of whether naturally
occurring disfluencies undermines performance more than does a change
in distribution.  Results using the parsed Switchboard corpus suggest 
that, although naturally
occurring disfluencies might harm performance, differences in
distribution between the training set and the testing set are more
significant. 
\end{abstract}

\section{Introduction}


Shallow parsers are usually automatically 
constructed  using a training set of annotated  examples \citep{Rams95,Skut98,Dael99a}. 
 Without
loss of generality, let $X$ be a set of word sequences  and $Y$ be a set
of syntactic labels.  The training set will then be a sequence of
pairs of the form $\langle x_1, y_1 \rangle, \ldots ,\langle x_n, y_n
\rangle$, where $x_i \in X, y_i \in Y$.  Such a sequence would be
generated by some process $Q$. On the basis of such a
training set, a shallow parser would make predictions about 
future, unlabelled examples.



Arguably, significant progress in shallow parsing performance will only come from having
access to massive quantities of annotated training material \citep{Bank01}.
 Unsupervised
approaches (which do not require annotated material, and so can make
use of  unlimited quantities of raw text), by contrast, 
are unlikely to yield comparable levels of 
performance. Now, producing  annotated material on an industrial scale
is highly likely to result in the introduction of  significant {\it noise} levels and/or
{\it distributional differences} into the training set. Therefore,
successfully dealing
with lower-quality (but voluminous) annotated training material will
hinge upon the ability of shallow parsers to tolerate high noise levels.  
Until now, the need to deal with noise has not been 
identified as a potential problem within the 
 shallow parsing literature. Furthermore, issues involved with 
distributional differences  in the training set 
have not been dealt with either.
In this paper, we consider both of these issues -noise in the training set and
distribution differences- when training a variety of
shallow parsers. 

Our first set of results shows that a variety of shallow parsers
are surprisingly robust to synthetic noise, and only show a marked
decrease in performance when the noise rates are high.
Further
results show that no single shallow parser performs best in all noise
situations. Final results show that simple, parser-specific extensions
can improve noise-tolerance.

Our second set of results addresses the question of whether naturally
occurring disfluencies undermines performance more than does a change
in distribution.  Our results suggest that, although naturally
occurring disfluencies might harm performance, differences in
distribution between the training set and the testing set are more
significant. Note that this conclusion is only true for noise levels
that are natural, and not, for example when noise levels are higher (as
might be produced when quickly trying to create large volumes of
annotated material).

 
The rest of this paper is as follows.  Section \ref{shallow} briefly
surveys shallow parsers from the perspective of
noise-tolerance. Afterwards (Section \ref{parsers}) we introduce the
shallow parsers used in our experiments.  Next (Section \ref{noise}) 
we present a set of
simple, artificial noise models.  This then leads onto a set of
experiments (Section \ref{exp}) where we show what happens when various parsers are
trained upon noisy material, and how our various parsers can be made
more noise tolerant. Section \ref{swbd} deals with naturally occurring
disfluencies and distributional differences.  Finally, Section \ref{comments} summarises the paper.

We now look more closely at noise tolerance in a variety of shallow parsers.

\section{Noise and shallow parsing \label{shallow}}

%As was mentioned in the introduction, shallow parsers are usually
%trained on annotated examples. 
% Now, producing such a training set is both expensive and
%error-prone (as for example when the training set is derived from
%parsed corpora \citep{Marc93}). Errors (or {\it noise}) can occur in 
%the examples
%(as for example when phrases are {\it disfluent}) or in the labels (as for example when 
%phrases are mislabelled).\footnote{We tend to use the terms {\it
%noise} and {\it disfluency} interchangeable. This does not imply, for
%example, that naturally occurring disfluencies are uniformly
%distributed.} 
%Since the training set is used to specify
%the parser, noise in the training set may undermine
%performance.   

%Quite apart from noise in the training set, when the training set is
%generated by a {\it different} process to that which generates future,
%unseen examples, performance may also be reduced.  Such a mismatch
%occurs either when the training set is {\it non-stationary} (as 
%for example when the training set consists of material uttered by a
%variety of people, or when different genre are included).  

Shallow parsers (as reported in the literature)
usually do not have explicit mechanisms for dealing
with noise.  This is probably because they are assumed to be trained
upon relatively noise-free material.  However, this does not mean to
say that 
shallow parsers cannot deal with noise.  For example, we see that 
shallow parsing 
systems  can be made more noise tolerant 
either by {\it smoothing}, selection of a model which
is `simple', with post-processing of parsed output, or else with some
combination of all three methods. Such approaches potentially might
also tackle the problem of non-stationary training material. 

Smoothing refers to  a general
set of techniques whereby a model estimated from a training set is
modified in some way, such that performance upon material unlike the
training material improves.  Such modification is motivated on {\it a
priori} grounds (meaning information outside of  the training set is
brought to bear). 
Since noise typically manifests as a model
having a complex surface, making it smoother may remove some of the
effects of noise.  Note that because smoothing is motivated on an {\it
  a
priori} basis,  smoothing may in some circumstances actually 
reduce performance.  
We shall see two different examples of
dealing with noise through smoothing in Sections \ref{mbl} and 
\ref{tnt}.  

Selecting a model which is `simple' can also be seen as a technique
for dealing with noise.  For example, maximum entropy will select a
model (from the set of possible maximum likelihood models) that has
parameters which are maximally compressible.  This is therefore a
preference for simplicity, which in turn is similar to explicit
smoothing. However, unlike smoothed maximum likelihood models (which are really maximum a posteriori models),
 maximum entropy is still maximum
likelihood estimation, and so (in principle) nothing need be lost
about the training material.  Note that a preference for simplicity is
nothing more than a noise-avoidance strategy, which may or may not
work, depending upon the nature of the sample \citep{Schaf93}.
Section \ref{maxent} describes a shallow
parser based upon maximum entropy.


Post-processing the test material, in the context of shallow parsing,
was advocated by \cite{Card98}.  They manually created a set of rules
to correct the output of their parser.  Whilst they were able to show
an improvement in performance, in general, such a technique is
arguably ad-hoc
and cannot
guarantee that all error patterns are treated. In subsequent work,
\cite{card99} automated the construction of these postprocessing rules.

Given the (open) question of whether some single noise-tolerance strategy works
in all domains, short of finding such an approach, an alternative
method is to `average' over whatever noise-avoidance 
methods one has available. The
general idea is that no  single approach will always work, but that
when taken together, an {\it ensemble} of approaches can work better
than any single method within that ensemble \citep{diet99}. 

Ensemble approaches have
been shown to be successful in a number of domains.  For example, the
current best parse selection results using the Wall Street Journal
were obtained using ensemble techniques \citep{hend00}; POS
tagging is improved by ensemble methods \citep{Brill98}, and for the
 shallow parsing domain that
we consider, ensemble methods enjoy a clear advantage over single
learners \citep{kudo00}.  

The two key
ideas  behind
 ensemble approaches
is that the individual models should be better than chance (they are
`weak' learners) and that errors made by the learners are
uncorrelated. Under such circumstances, the ensemble will provably be
better than any of the component models. 
\cite{Asla93} have 
proved that when the appropriate assumptions are met, 
ensemble learning can reduce errors, even when the
training material is noisy.  
Ensemble learning does not always guarantee a performance
improvement. Should errors be correlated (or the component learners
be worse than chance) then the performance of the ensemble can be
worse than the performance of the components.  An example of an
ensemble shallow parser is given in Section \ref{ep}.


We now  describe what we mean by shallow parsing, and introduce 
the shallow parsers used in our experiments.
\section{Four shallow parsers \label{parsers}}

In this paper, we deal with the recovery of base phrases from the
(parsed) Wall Street Journal (henceforth called WSJ). 
Base phrasal recovery is a well-known
task, and various results exist for it.  See
\cite{Sang00} for an overview.

In brief, the task is to
annotate part-of-speech (POS) tagged sentences with 
non-overlapping phrases.  Words in
sentences are marked with a `chunk' label, which can be either an {\it O}
label
(meaning the word is not in a phrase), a {\it B} label (meaning the
associated word is the first word of a given phrase) or an {\it I}
label (meaning the word is within some given phrase).  Both {\it B}
and {\it I} labels are further divided into Verbal, Nominal,
Adjectival, Adverbial, Prepositional and a small variety of other
minor phrasal categories. In total, there are $22$ possible chunk
labels. Figure \ref{exsent} shows
 an example labelled sentence.
\begin{figure}[!htb]
\begin{center}
\begin{tabular}{lllllllll}
He & reckons & the & current & account & deficit & will & narrow & to \\
B-NP & B-VP & B-NP & I-NP & I-NP &  I-NP &  B-VP &    I-VP & I-VP \\
\\ \\
 only & \# & \$ &  1.8 & billion & in & September &  &  \\
I-VP & B-PP & B-NP & I-NP & I-NP   & B-PP & B-NP & & 
\end{tabular}
\end{center}
\caption{An example annotated Wall Street Journal sentence \label{exsent}}
\end{figure}
    Note that POS
labels have been suppressed.


We now present the shallow parsers used in our experiments.  The
motivation for using these  parsers is that they are broadly
representative of shallow parsers, and furthermore, help deal with a
potential criticism that any results obtained from a single parser
might reflect idiosyncrasies of that approach, and not more general
findings. 



\subsection{The maximum entropy-based shallow parser \label{maxent}}

We used Ratnaparkhi's maximum entropy-based POS tagger 
as the basis of our maximum entropy-based shallow parser \citep{Ratn96}.
In brief, the tagger   uses the following exponential model:
\begin{eqnarray*} 
P(h,t) = \pi \mu \prod_{j=1}^{k} \alpha_{j}^{f_{j}(h,t)}
\end{eqnarray*}
$\pi$ is a normalising constant, $\mu,\alpha_1 \ldots \alpha_k$ are
parameters and $f_1 \ldots f_k$ are `features'.  Each parameter
$\alpha_j$ corresponds to a feature $f_j$.  Each feature takes an integer
values representing how many times that feature was active on an example.
$h_i$ is the {\it history} available when predicting POS tag $t_i$.

Features capture aspects of the tagging task that are deemed important when
modelling.  Here, features  are in terms of the current word to be tagged, the
previous two words, the next two words and the previous two tags.  The
tagger also uses features such as prefixes of words, word suffixes,
etc. The interested reader should consult the original paper for a
description of the features used in the tagger \citep{Ratn96}.



The parameters $\mu,\alpha_1 \ldots \alpha_k$ are chosen to maximise
the probability of the training set:
\begin{eqnarray*}
P(D \mid M) = \prod^{n}_{i=1}P(h_i,t_i) \label{gislike}
\end{eqnarray*}
$D$ is the training set (tags and their respective histories), and $M$ is
the model (parameters and their associated weights). 
Parameters are estimated using {\it Generalised Iterative Scaling}
(GIS).

The tagger is trained by taking a set of sentences, and 
 for each word in each sentence, labelling that word with an
 intended POS tag.  Afterwards, the
tagger uses GIS to find the best set of weights to maximise the
probability of seeing this data. GIS is an iterative training method,
 and after each iteration, the likelihood probability (equation
 \ref{gislike}) increases up to a maximum.  

When tagging, the model tries to recover the most likely (unobserved) tag sequence,
given a sequence of observed words. 


When shallow parsing using this approach, consider the following fragment of the training set:
\begin{center}
\begin{tabular}{l|llll}   \hline 
Word & $w_1$ & $w_2$ & $w_3$  & $w_4$  \\
POS Tag & $t_1$ & $t_2$ & $t_3$  & $t_4$  \\ 
Chunk  & $c_1$ & $c_2$ & $c_3$ & $c_4$  \\ \hline  
\end{tabular}
\end{center}
Words are $w_1, w_2,w_3$ and $w_4$, 
tags are $t_1, t_2, t_3$ and $t_4$ and  chunk
labels are $c_1, c_2, c_3$ and $c_4$. The task is to predict the chunk
label for word $w_2$ (the current word).

In order to convince the part-of-speech tagger to shallow parse, we 
  concatenate together the POS
label of the current word, the POS label of the next word ($t_3$),
that of the following word ($t_4$), and finally the last four letters of the
current word ($w_2$).  This concatenation is then used in place of a more
conventional word (as expected by the tagger). In place of the
tagger's POS labels, we use chunk labels. The training set is then a
  sequence of concatentation-chunk label pairs. The motivation
for encoding shallow parsing information in this way comes from a
tradeoff between context and accuracy.  The more context we encode,
the greater our accuracy; the more context, the sparser our features
will be.  \cite{Osbo00c} gives a more detailed description of some of the
issues involved with shallow parsing using this tagger.
Our experiments were all
 run for $100$ iterations of GIS (unless specified otherwise).

\subsection{The memory-based shallow parser \label{mbl}}
Our memory-based shallow parser was constructed using the
publically-available {\it TiMBL} system \citep{Dael00}.  Memory-based 
learning stores all training examples in memory.  Examples are vectors
of features and an associated label.  At run time, an unseen example
is classified in terms of how similar it is to seen examples.  The $k$
most similar  training examples are retrieved from memory, and
the label of the unseen example is then some function of these seen examples.

In more detail, let $D(X,Y)$ be the `distance' between vector $X$ and
vector $Y$. There are many possible distance metrics, but in this work
we used the
default {\it overlap} metric:
\begin{eqnarray*}
D(X,Y) = \sum_{i=1}^{n} w_i \sigma(x_i,y_i) \\
\sigma(x_i,y_i) = \left\{ \begin{array}{ll} 0 &\mbox{if}~ x_i = y_i \\
                                            1 & \mbox{otherwise}
                          \end{array} \right.
\end{eqnarray*}
Here, $x_i$ and $y_i$ are the $i^{th}$ components of the vectors $X$ and
$Y$. $w_i$ is a weighting which can bias matching in various
ways. We used the {\it gain ratio} weighting scheme (as it produced
reasonable results). Together, the similarity metric and weighting
scheme is called IB1-IG \citep{dael92b}.

This overlap metric prefers examples which have a minimal number
of (weighted) mismatches. We find the $k$ examples that minimise the
overlap metric, and select the final label as being the label that is
most common within the $k$ examples.


Throughout our main experiments (Section \ref{mainexp}), we used the
IB1-IG  similarity metric (as it produced acceptable results for our
task; the choice of metric is not crucial for our experiments),
and used $k=3$. We also experimented with various values of $k$ in our
secondary experiments (Section \ref{extensions}).  

When shallow parsing, we created vectors consisting of the current
word to be labelled, the current POS tag, the previous four POS
tags, and the POS tag of the next word. Better results can
be obtained by using even more context (at the expense of slower
testing).  Since we were more concerned with running large numbers of
experiments than with obtaining the best possible results, we 
were prepared to accept a reduced performance level
(that is, our approach was about $1\%$ less than that of \cite{Veen00}).
Note that this shallow parser uses different information from the
maximum entropy parser.  However, when there is no noise, both models
yield very similar performance levels to each other.  

\subsection{The N-gram shallow parser \label{tnt}}

We use Brant's Markov-based POS tagger  as the basis of
our N-gram shallow parser \citep{brant00}.  Brant's tagger selects the most likely tag
sequence $t_1 \ldots t_n$ as follows:
\begin{eqnarray*}
\mbox{argmax}_{t_1 \ldots t_n} P(t_{n+1} \mid t_{n}) \prod_{i=1}^{n}
P(t_i \mid t_{i-1}, t_{i-2}) P(w_i \mid t_i)
\end{eqnarray*}
Here, $w_i$ is a word and  $t_{n+1}$ is a tag denoting the end of a
sentence.

The components of the previous equation are estimated using
N-grams. The  model uses linear interpolation as a smoothing
device (smoothing over the term $P(t_i \mid t_{i-1}, t_{i-2})$).  There is a mechanism for dealing with unknown words, based
upon suffixes.
The model is trained using maximum likelihood estimation, whilst the
weights for linear interpolation are found using deleted interpolation.

We used the default settings of the system.  In particular, this
means:  using statistics from singleton words when dealing with unknown
words, using linear
interpolation to smooth and using trigrams. Note that at times we used
unigrams and bigrams instead of trigrams.  These cases are clearly
marked in the paper.

When shallow parsing, we used the same training set (words as
concatenations of POS tags, etc) as was used when
training the maximum entropy shallow parser (mentioned in Section \ref{maxent}).

Later in this paper, whenever we refer to the `N-gram parser', as
should be obvious, we mean Brant's tagger retrained as a shallow parser. 


\subsection{The ensemble parser \label{ep}}

Our ensemble shallow parser used all three previously mentioned
parsers, and arbitrated between them using a simple majority vote.
That is, we use all parsers to label material. For each word, we
count the number of times a label was predicted 
 by the various parsers.  If a label is predicted by a majority,
then we use that as the label predicted by the ensemble parser.
Otherwise, we default to the decision made by one of the component
parsers.  As alluded to in  Section \ref{exp}, varying the default decision
yields (marginally) different performance. 
Note  we have not used weighted majority voting as at least one
of our shallow parsers is non-probabilistic. 





\section{Noise models \label{noise}}


In this Section, we introduce the four noise models that were used in
our experiments.  Although our models are not claimed to be realistic
accounts of disfluencies as found in naturally occurring language (nor
of errors made by annotators), they
do allow us to  introduce various types
of noise into the training set, such that the parsers are stressed in
different ways.   Our noise models furthermore are  parameterised, so we can
also vary the amount of noise.
Note that training on disfluent corpora (such as {\it
  Switchboard}, see Section \ref{swbd}) would allow us to observe the effects of realistic,
naturally occurring noise, but
only at a fixed rate.  


Our first model ({\tt white}) simulates classification errors (called the  {\it
  classification noise} model) \citep{Angl88}.  Within the {\tt white}
  noise model, when training, each example
received by the learner is mislabelled randomly and independently
with some fixed probability.  For example, the fragment shown in
  Figure \ref{exfrag} might become corrupted as shown in Figure \ref{exwhite}.
\begin{figure}[!htb]
\begin{center}
\begin{tabular}{lllll} 
He & reckons & the & current & account \\
B-NP & B-VP & B-NP & I-NP & I-NP 
\end{tabular}
\end{center}
\caption{Example sentence fragment, without noise \label{exfrag}}
\end{figure}

\begin{figure}[!htb]
\begin{center}
\begin{tabular}{lllll} 
He & reckons & the & current & account \\
I-NP & B-VP & O & I-NP & I-NP 
\end{tabular}
\end{center}
\caption{An example annotated sentence with white noise in the labels
  (as produced by the {\tt white} noise model)\label{exwhite}}
\end{figure}

Mislabelling is within the set of possible labels, and no account is
taken whether the corrupted example is a well-formed example (a phrase
is introduced by an appropriate beginning phrasal marker).  This means
that examples corrupted in this manner pose a harder learning problem than do
examples which are mislabelled, yet still well-formed.

This model has been studied theoretically, and various
noise-tolerant learners are known to exist for it.  From a linguistic
perspective, this model is artificial, and it is unlikely that any
real training set would be corrupted in this manner. However, it is 
a useful baseline.

The second model ({\tt filled}) introduces `filled-pauses' into
sentences \citep{Shri94}.  A
filled-pause is an interjection, with no semantic content, which can
occur anywhere in a sentence.  For example, Figure \ref{exfp} shows
the insertion of a filled pause into the  fragment shown in
Figure \ref{exfrag}.

\begin{figure}[!htb]
\begin{center}
\begin{tabular}{llllll} 
He & reckons &  uh & the & current & account \\
B-NP & B-VP & B-VP & B-NP & I-NP & I-NP 
\end{tabular}
\end{center}
\caption{A sentence containing a filled pause (as produced by the {\tt
    filled} noise model)\label{exfp}}
\end{figure}
Filled pauses are introduced at a fixed  and independent rate. They
are assumed to simply have the same chunk label as the previous
word (this adds extra noise to the sequence of labels and to the
sequence of words). As such, a training set with filled-pauses
contains well-formed phrases. 


The third model ({\tt repeat}) 
introduces simple `repetitions' into sentences \citep{Shri94}.  Figure
\ref{exrep} shows an example repetition.
\begin{figure}[!htb]
\begin{center}
\begin{tabular}{llllll} 
He & reckons &  reckons & the & current & account \\
B-NP & B-VP & I-VP & B-NP & I-NP & I-NP 
\end{tabular}
\end{center}
\caption{A sentence containing a repetition (as produced by the {\tt
    repeat} noise model)\label{exrep}}
\end{figure}
Like filled-pauses, repetitions are introduced randomly, at a fixed
rate.  Repetitions are assumed to be in the same phrase as that of the
previous word (this prevents the introduction of illegal sequences)
and  are assumed to only occur once (as multiple occurrences of the
same symbol can easily be eliminated by post-processing).
They are  also constrained to only occur before function
words.\footnote{Constraining repetitions in this way is an attempt to
  model the fact that $40\%$ of disfluencies in natural text 
  behave in this manner \citep{Shri94}.}
Since repetitions
depend upon the surface form of a sentence, they will be distributed
differently from the changes made by our other models.  

The final noise model ({\tt all}) used all three previous models. In
more detail, we applied the {\tt repeat} model, then the {\tt filled}
model, and finally the {\tt white} model to the training set.  

As can be expected, our noise models are simple, and so arguably
create unrealistic training scenarios. For example, our 
approach largely predicts that disfluencies are linearly
distributed. \cite{Shri94} found that
the rate of disfluencies in some texts were best described
exponentially.   The filled pause and repetition models
 should assign part-of-speech
tags by running a part-of-speech tagger over the corrupted material. 


The noise models are not that closely tied to the types of noise one
might expect when manually annotating material on a massive
scale. Instead, they are largely inspired by the disfluency
literature. In lieu of a study of the kinds of errors made when
annotating material, we conjecture that the {\it white} noise model
might be seen as crudely approximating annotation errors. That 
is, the examples are noise-free, but the actual 
labels will be at times wrong. The other noise models may be
appropriate when training on material from another genre. For example, when moving from speech to edited newswire text.
Interesting future work should attempt to characterise the classes of
errors made when annotating very large quantities of material, capture
such errors in noise models, and then study their effects.

In their defence, the noise models even if unrealistic, do  allow  
experiments to be carried-out whereby  noise-rates  can be
varied. Varying the noise rate cannot be done so easily using
naturally occurring material. 

We now present our experiments using synthetic noise in the training
sets.

\section{Experiments using artificial noise \label{exp}}

Throughout these experiments, we
used a training set consisting of $8,885$ sentences.  This was
automatically extracted from the parsed Wall Street Journal \citep{Marc93}.  We also
used a disjoint testing set ($2,011$ sentences), also drawn from the parsed Wall Street Journal. This training and testing
set was the same one as used by the CoNLL00 shared task.\footnote{The  
site {\tt http://lcg-www.uia.ac.be/conll2000/chunking/}  describes the task and contains all the training, testing
  and evaluation material used here.} 

Note that the training and testing set was re-tagged using the Brill
tagger \citep{bril92b}. This means that the data (with respect to the
original parsed Wall Street Journal) contains tagging errors (noise). 
 However, as  both the training and testing sets
were tagged in this manner, the effects of tagging errors will be
factored-out. Whenever we say `uncorrupted' material, we really mean
the material as used in the CoNLL00 shared task.  Future work should repeat our
experiments using training and testing material as originally tagged
in the Wall Street Journal.

When shallow parsing (as was previously mentioned in Section \ref{parsers}),
 the task was to assign chunk labels to tagged
sentences. Evaluation was in terms of an `f-score'.  This is the (harmonic)
average of recall and precision, where {\it recall} is the percentage of
exactly matching phrases in the testing set found by the system, and 
{\it precision} is the percentage of detected phrases that are
 correct.  Shallow parsers are usually measured using f-scores, and
 not in terms of tagging accuracy.  For the purposes of our
 experiments, the actual choice of metric is not that important.


 The best
reported system (an ensemble) achieved an f-score of $93.84$ \citep{kudo00}.  
In
general, shallow parsing is harder than POS tagging since
the correct assignment of chunk labels can depend upon much larger
contexts than those that are used by POS taggers.  For example,
shallow parsing typically needs a context of five words and/or
POS labels.  POS taggers usually operate in
terms of three words and/or POS tags.

As a baseline, a system which made decisions according to
the most likely chunk label given a POS tag (using an
uncorrupted training set) achieved an f-score of $77.07$.  For all
noise models, and varying the rate of noise, this baseline mainly held
(as shown in Figure \ref{baseline}). These results are the averages of
$10$ runs. That is, we used the same training and testing set on each
run, but because our noise models make decisions on a  random basis, they
produced different sets of disfluencies after each run.

 All other experiments were single runs (as there were so
many of them). Note that at times, performance using noisy material is
marginally 
better (at least for our baseline model) than for performance using
`clean' material.  This is probably an artifact.

\begin{figure}
\begin{center}
\begin{tabular}{c c c c  c c }
Noise Model & Rate    & F-Score &   Noise Model  & Rate & F-Score \\ 

{\tt White} & 25 & 77.10 & {\tt White} & 50 & 77.11 \\ 
{\tt Repeat} & 25 & 77.16 & {\tt Repeat} & 50 & 77.96 \\ 
{\tt Filled} & 25 & 77.06 &  {\tt Filled} & 50 & 77.06 \\ 
{\tt All} & 25 & 77.10 & {\tt All} & 50 & 77.98 \\ 
{\tt White} & 75 & 77.15 & {\tt White} & 100 & 2.93 \\ 
{\tt Repeat} & 75 & 78.27 & {\tt Repeat} & 100 & 78.27 \\ 
{\tt Filled} & 75 & 77.06 & {\tt Filled} & 100 & 77.06 \\ 
{\tt All} & 75 & 78.23 & {\tt All} & 100 & 3.57 
\end{tabular}
\end{center}
\caption{Baseline performance using various noise models.  {\it Rate}
  shows the percentage chance of a corruption occurring \label{baseline}}
\end{figure}

The reason for our baseline system having  high levels of performance, even when the noise
rates are high, follows from the highly peaked nature of the underlying
distributions. Figure \ref{d2} shows an example 
distribution from the baseline parser.  As can be seen, a few points
in this distribution accounts for the majority of the 
probability mass.  When noise is introduced by our models, these
distributions become flatter.  However, because the distributions are
so peaked, even with a large amount of noise, these peaks are still
prominent, and so performance is maintained.


\begin{figure}
\begin{center}
\begin{tabular}{lll} 
Label & $P(\mbox{label} \mid \mbox{VBN})$ & Count \\
B-ADVP & 0.0002 & 1 \\
I-ADVP & 0.0002 & 1 \\
O & 0.0015 & 7 \\
I-ADJP & 0.0092 & 44 \\
B-PP & 0.0164 & 78 \\
B-ADJP & 0.0193 & 92 \\
B-NP & 0.0393 & 187 \\
I-NP & 0.0951 & 453 \\
B-VP & 0.2297 & 1094 \\
I-VP & 0.5891 & 2806 \\
\end{tabular}
\end{center}
\caption{Distribution of chunk labels for
  $P(\mbox{label} \mid \mbox{VBN})$, trained upon uncorrupted WSJ \label{d2}}
\end{figure}




\subsection{Performance using noise models \label{mainexp}}

Here we show the performance of our  shallow parsers in the
presence of various kinds of noise.  Section \ref{ind} analyses these results.

Figure \ref{white} shows the
results using the {\tt white} noise model.  Here, as in graphs
\ref{filled}, \ref{repeat} and \ref{all}, we show the performance of
all single-model parsers, and the performance of the best ensemble
parser, as the noise rate increases. We have not shown all ensemble
parsers as, by-and-large, they are all quite similar to each
other. It should be clear which parser relates to which curve from the labels.

\begin{flushleft} 
\begin{figure}[!hbt] 
\begin{center} 
\epsfxsize=.5\linewidth 
\rotatebox{270}{\epsfbox{gnuplot/white.ps}} 
\end{center} 
\caption{Results using {\tt White} Noise Model \label{white}}
\end{figure} 
\end{flushleft} 

%\begin{figure}[!thb]
%\begin{center}
%\begin{tabular}{c|cccccc}
%Rate & Max & MBL & TNT & Vote (Max) & Vote (MBL) & Vote (TNT) \\ \hline
%0 & 90.87 & 90.22 & 84.08 & 91.63 & 91.57 & 91.44 \\ 
%5 & 90.32 & 89.11 & 82.42 & 91.12 & 91.27 & 91.09 \\ 
%10 & 89.79 & 88.3 & 81.21 & 90.73 & 90.96 & 90.59 \\ 
%15 & 89.21 & 87.27 & 79.71 & 90.29 & 90.72 & 90.18 \\ 
%20 & 88.47 & 85.96 & 78.81 & 89.86 & 90.38 & 89.78 \\ 
%25 & 88.02 & 84.52 & 77.39 & 89.51 & 90.01 & 89.32 \\ 
%30 & 87.21 & 82.58 & 75.48 & 88.88 & 89.34 & 88.6 \\ 
%35 & 85.95 & 80.73 & 73.77 & 88.09 & 88.67 & 87.59 \\ 
%40 & 85.05 & 78.15 & 71.42 & 87.38 & 87.72 & 86.61 \\ 
%45 & 83.44 & 75.24 & 69.61 & 86.01 & 85.9 & 84.8 \\ 
%50 & 81.83 & 72.01 & 67.59 & 84.56 & 84.19 & 83.16 \\ 
%55 & 79.15 & 67.84 & 64.37 & 82.2 & 81.8 & 80.3 \\ 
%60 & 76.52 & 63.52 & 62.02 & 80.15 & 79.29 & 77.5 \\ 
%65 & 72.84 & 57.89 & 59.35 & 76.64 & 75.08 & 73.44 \\ 
%70 & 66.5 & 53.1 & 55.42 & 71.29 & 70.23 & 68.31 \\ 
%75 & 59.82 & 46.67 & 50.53 & 65.34 & 64.54 & 62.21 \\ 
%80 & 50.49 & 38.53 & 44.85 & 56.24 & 56.05 & 54.17 \\ 
%85 & 40.07 & 29.87 & 38.51 & 45.21 & 45.33 & 44.8 \\ 
%90 & 25.36 & 20.6 & 28.93 & 29.59 & 31.35 & 32.05 \\ 
%95 & 11.49 & 11.61 & 18.4 & 13.88 & 16.04 & 18.99 \\ 
%100 & 3.5 & 3.08 & 3.74 & 3.55 & 3.33 & 3.7 \\ 
%\end{tabular}
%\end{center}
%\caption{Results using {\tt White} Noise Model \label{white}}
%\end{figure}

As can be seen, increasing the noise rate decreases the performance of
all our parsers.  Furthermore, we see that this degradation is
relatively graceful: no parser exhibits a catastrophic performance
drop as noise is introduced into the training set. 
When there is noise in the labels, we see that the maximum entropy
parser is more robust than the memory-based parser.  The N-gram
parser is mid-way between the two other single-model parsers.  

Turning now to the ensemble parsers (only the ensemble parser
defaulting to maximum entropy is shown), firstly, we find that all three
parsers usually outperform the single-model parsers.  Ensemble
learning can make shallow parsing more robust in the presence of white
noise.  Secondly, we see that
defaulting to maximum entropy usually produces the best results. 
Finally, at $100\%$ noise
the training set cannot be distinguished from the results of flipping a
coin, and so performance is minimal for all parsers.


%\begin{figure}[!thb]
%\begin{center}
%\begin{tabular}{c|cccccc}
%Rate & Max & MBL & TNT & Vote (Max) & Vote (MBL) & Vote (TNT) \\ \hline
%0 & 90.88 & 90.22 & 84.08 & 91.63 & 91.58 & 91.45 \\ 
%5 & 90.54 & 90.11 & 83.51 & 91.31 & 91.32 & 91.19 \\ 
%10 & 89.94 & 90.13 & 82.45 & 90.8 & 90.95 & 90.76 \\ 
%15 & 89.46 & 89.67 & 82.04 & 90.57 & 90.72 & 90.53 \\ 
%20 & 88.71 & 89.76 & 81.18 & 90.07 & 90.35 & 89.99 \\ 
%25 & 87.81 & 89.47 & 80.28 & 89.48 & 89.82 & 89.49 \\ 
%30 & 87.1 & 89.34 & 79.02 & 89.06 & 89.39 & 89.01 \\ 
%35 & 86 & 88.93 & 77.89 & 88.34 & 88.76 & 88.38 \\ 
%40 & 84.94 & 88.89 & 76.71 & 88 & 88.44 & 88.12 \\ 
%45 & 83.87 & 88.26 & 75.18 & 87.11 & 87.66 & 87.31 \\ 
%50 & 82.39 & 87.44 & 73.69 & 85.8 & 86.69 & 86.15 \\ 
%55 & 80.34 & 86.95 & 70.45 & 84.53 & 85.45 & 84.95 \\ 
%60 & 78.83 & 86.73 & 69.04 & 83.95 & 84.98 & 84.28 \\ 
%65 & 76.34 & 86.11 & 66.7 & 82.63 & 83.69 & 83.14 \\ 
%70 & 73.54 & 85.64 & 64.14 & 80.57 & 82.13 & 81.25 \\ 
%75 & 70.79 & 84.66 & 61.42 & 78.64 & 80.25 & 79.33 \\ 
%80 & 67.47 & 83.89 & 58.32 & 75.85 & 77.96 & 76.39 \\ 
%85 & 62.02 & 81.76 & 55.24 & 72.23 & 74.72 & 72.93 \\ 
%90 & 56.21 & 79.54 & 52.39 & 68.15 & 71.27 & 68.85 \\ 
%95 & 46.06 & 76.77 & 47.09 & 60.46 & 64.86 & 60.84 \\ 
%100 & 6.93 & 52.61 & 8.33 & 14.22 & 38.93 & 12.76 \\ 
%\end{tabular}
%\end{center}
%\caption{Results using {\tt Filled} Noise Model \label{filled}}
%\end{figure}

\begin{flushleft} 
\begin{figure}[!hbt] 
\begin{center} 
\epsfxsize=.5\linewidth 
\rotatebox{270}{\epsfbox{gnuplot/fill.ps}} 
\end{center} 
\caption{Results using {\tt Filled} Noise Model \label{filled}}
\end{figure} 
\end{flushleft} 

Looking now at the results using our {\tt filled} noise model (Figure
\ref{filled}), we see a different picture.  The main difference from
the previous results is that the memory-based parser is now the clear
winner, even generally outperforming the ensemble parsers.  With the
various ensemble parsers, we find that again, defaulting to the
behaviour of the best single parser yields marginally the best
ensemble parsing results.  However, we also found that the results for
the other two ensemble parsers (maximum entropy default and n-gram
default) produce results that are similar to each other.  

%\begin{figure}[!thb]
%\begin{center}
%\begin{tabular}{c|cccccc}
%Rate & Max & MBL & TNT & Vote (Max) & Vote (MBL) & Vote (TNT) \\ \hline
%0 & 90.87 & 90.22 & 84.08 & 91.63 & 91.57 & 91.45 \\ 
%5 & 90.88 & 90.16 & 83.87 & 91.58 & 91.52 & 91.42 \\ 
%10 & 90.75 & 90.08 & 83.72 & 91.48 & 91.41 & 91.3 \\ 
%15 & 90.51 & 90.14 & 83.49 & 91.3 & 91.33 & 91.16 \\ 
%20 & 90.45 & 90.11 & 83.23 & 91.17 & 91.13 & 90.97 \\ 
%25 & 90.24 & 90.22 & 82.95 & 90.97 & 91.01 & 90.83 \\ 
%30 & 90.18 & 89.99 & 82.83 & 90.91 & 90.95 & 90.83 \\ 
%35 & 90 & 90.03 & 82.39 & 90.75 & 90.78 & 90.64 \\ 
%40 & 89.71 & 90.17 & 82.28 & 90.68 & 90.86 & 90.65 \\ 
%45 & 89.36 & 89.76 & 81.62 & 90.15 & 90.39 & 90.17 \\ 
%50 & 89.34 & 89.98 & 81.58 & 90.26 & 90.43 & 90.2 \\ 
%55 & 89.13 & 89.6 & 81.4 & 89.98 & 90.22 & 90.1 \\ 
%60 & 88.7 & 89.73 & 81.04 & 89.62 & 89.93 & 89.71 \\ 
%65 & 88.55 & 89.76 & 80.79 & 89.58 & 89.9 & 89.77 \\ 
%70 & 88.11 & 89.79 & 80.36 & 89.19 & 89.63 & 89.48 \\ 
%75 & 87.33 & 89.51 & 80.13 & 88.64 & 89.32 & 89.01 \\ 
%80 & 86.73 & 89.43 & 79.58 & 88.16 & 88.84 & 88.69 \\ 
%85 & 85.99 & 89.19 & 79.03 & 87.6 & 88.41 & 88.3 \\ 
%90 & 85.15 & 88.84 & 78.28 & 86.91 & 87.84 & 87.63 \\ 
%95 & 83.02 & 88.63 & 76.98 & 85.12 & 86.62 & 86.41 \\ 
%100 & 76.4 & 87.87 & 75.17 & 80.67 & 83.61 & 82.99 \\ 
%\end{tabular}
%\end{center}
%\caption{Results using {\tt Repeat} Noise Model \label{repeat}}
%\end{figure}

\begin{flushleft} 
\begin{figure}[!hbt] 
\begin{center} 
\epsfxsize=.5\linewidth 
\rotatebox{270}{\epsfbox{gnuplot/repeat.ps}} 
\end{center} 
\caption{Results using {\tt Repeat} Noise Model.  Note the change of scale. \label{repeat}}
\end{figure} 
\end{flushleft} 

The results using the {\tt repeat} noise model
 (Figure \ref{repeat}) are different again
from the previous two sets of results.  Generally, we see that
performance is much less affected than before.  

%\begin{figure}[!thb]
%\begin{center}
%\begin{tabular}{c|cccccc}
%Rate & Max & MBL & TNT & Vote (Max) & Vote (MBL) & Vote (TNT) \\ \hline
%0 & 90.86 & 90.23 & 84.12 & 91.63 & 91.57 & 91.45 \\ 
%5 & 89.58 & 89.03 & 82 & 90.65 & 90.93 & 90.69 \\ 
%10 & 88.26 & 87.73 & 79.92 & 89.82 & 90.16 & 89.86 \\ 
%15 & 86.65 & 86.63 & 78.01 & 88.76 & 89.45 & 88.86 \\ 
%20 & 85.24 & 85.19 & 75.63 & 87.69 & 88.54 & 87.74 \\ 
%25 & 83.09 & 84.23 & 72.92 & 86.46 & 87.55 & 86.28 \\ 
%30 & 80.95 & 82.29 & 69.44 & 85.01 & 86.38 & 84.69 \\ 
%35 & 77.49 & 80.54 & 67.17 & 82.99 & 84.8 & 83.07 \\ 
%40 & 74.36 & 77.35 & 63.91 & 80.69 & 82.81 & 80.45 \\ 
%45 & 71.04 & 75.27 & 60.49 & 78.62 & 80.83 & 78.09 \\ 
%50 & 65.64 & 71.59 & 57 & 74.28 & 77.61 & 74.72 \\ 
%55 & 59.2 & 67.91 & 53.45 & 69.75 & 73.83 & 70.32 \\ 
%60 & 54.87 & 63.45 & 49.22 & 65.6 & 70.57 & 65.99 \\ 
%65 & 46.42 & 58.64 & 45.51 & 57.73 & 64.73 & 59.99 \\ 
%70 & 38.6 & 53.09 & 41.29 & 50.43 & 59.93 & 54.13 \\ 
%75 & 32.86 & 48.93 & 36.99 & 43.81 & 54.26 & 47.54 \\ 
%80 & 24.88 & 42.25 & 30.89 & 34.53 & 46.21 & 39.36 \\ 
%85 & 15.56 & 34.25 & 26.3 & 23.73 & 36.44 & 30.82 \\ 
%90 & 9.33 & 25.17 & 17.19 & 13.9 & 24.84 & 19.24 \\ 
%95 & 5.53 & 17.77 & 8.95 & 7.47 & 16.08 & 9.48 \\ 
%100 & 3.11 & 3.04 & 3.23 & 3.14 & 3.18 & 3.06 \\ 
%\end{tabular}
%\end{center}
%\caption{Results using {\tt All} Noise Model \label{all}}
%\end{figure}  

\begin{flushleft} 
\begin{figure}[!hbt] 
\begin{center} 
\epsfxsize=.5\linewidth 
\rotatebox{270}{\epsfbox{gnuplot/all.ps}} 
\end{center} 
\caption{Results using {\tt All} Noise Model \label{all}}
\end{figure} 
\end{flushleft} 


Our final set of results, as produced by the {\tt all} noise model  (shown
in Figure \ref{all}) reveals behaviour that is again different from
the other results.  As shown previously in Figure \ref{filled}, the memory-based
parser does best out of the single model parsers.  However, like the
results shown in Figure \ref{white}, the ensemble parsers mainly do
better than the single-model parsers. Unlike the previous results, we
see that defaulting to the N-gram parser, for high noise levels,
yields better results than when defaulting to the maximum entropy parser.

Figure \ref{bestsum} summaries which parser is best, for selected noise models.


\begin{figure}[!htb]
\begin{center}
\begin{tabular}{c|cccccccc}
Rate & model & Best  &  model & Best  & model & Best  &  model & Best \\
25 & {\tt white} &  vote (MBL)     & {\tt filled} & vote (MBL)   &
{\tt repeat} & vote (MBL)& {\tt
all} & vote(MBL) \\
50 & {\tt white} &  vote (maxent)     & {\tt filled} & MBL  & {\tt
repeat} & vote (MBL)& {\tt
all} & vote (MBL)\\
75 & {\tt white} &   vote (maxent)    & {\tt filled} &  MBL  & {\tt
repeat} & MBL& {\tt all} & baseline\\
\end{tabular}
\end{center}

\caption{Summary of results \label{bestsum}}
\end{figure}


\subsection{Analysis \label{ind}}

Here we analyse the results.  The most important point to be made is that no
parser is uniformly best.  For example, the ensemble parser
(defaulting to maximum entropy) generally yields the best results with respect
to the {\tt white} noise model.  However, for the {\tt filled} noise
model, we see that the memory-based parser is usually best.  The reason that
we get this variation in performance is due to properties of the
noise-avoidance strategies used, and, in the case of ensemble parsers,
to a violation of errors not being correlated.  In more detail, we see
that for white noise, because the ensemble learners beat all the
single model parsers, we can conclude that the errors made are
uncorrelated.  Hence, the individual parsers all deal with white-noise
suboptimally (otherwise, there would be no gain to be made using
ensemble learning).  For filled pauses, we see that both maximum entropy and
N-grams make correlated errors (as the ensemble parser, defaulting to
memory-based learning, is worse than the single memory-based parser),
and so ensemble learning does not help.  

The results using noise in the labels (the {\tt white} model) on
average are worse than the results obtained using disfluencies in the
examples (the {\tt filled} and {\tt repeat} models).  This might be
because  the {\tt white} model introduces more randomness 
into the training set than does the other models.\footnote{An
  anonymous reviewer made the point that because this noise model does
  not guarantee that examples are well-formed, the  performance
  drop may be also due to the fact that the hypothesis space is
  potentially much
  larger. Hence, it would be possible to reduce this drop by making
  sure that examples are well-formed, possibly by some post-processing.} Another
reason might be that supervised learners are more sensitive to noise
in labels  than to noise in examples.

The noise-avoidance 
story which appears to have  emerged is that, out of a space of possible
noise-reduction techniques,  and for the set of parsers considered in
this paper, no single method appears to work 
uniformly well.  Theoretical support for this position is given
by \cite{Wolp95}.  Their {\it No Free Lunch} theorem (informally) states
that no single algorithm will work uniformly well across all problems.  In
 terms of noise, this means that an algorithm which
can deal well with (for example) errors in the labels of examples may
not do well with (for example) errors in the examples themselves. This
also suggests that a parser which does well in the noise-free case may
not do well in a noisy situation, and that some other parser may do better.

We do not conclude that any one technique is better than any other
approach. For example, we see that memory-based learning is closely
related to smoothing using backing-off \citep{Zavr97}.  Hence, we could
probably emulate the noise-tolerance of memory-based learning within
an N-gram parser that used backing-off. This is equivalent to using
some other model better suited to noise-tolerance than the one we did
use.  %Furthermore, all our parsers
%used different models (features), and as an anonymous reviewer
%mentioned, it is entirely possible that our results are a property of
%the particular model used (and not necessarily of the
%technique).\footnote{To control for this effect, one would need to
%  make sure that each parser used the same model. However, to repeat,
%  we are not trying to make statements about the relative merits of
%  any particular parser.  We are more interested in performance
%  differences for a given parser when confronted by various kinds of
%  noise.}


However, 
returning to the {\it No Free Lunch
  Theorem}, we conjecture
that no single parser will be uniformly superior in all noise
scenarios. So, if we made the N-gram parser tolerant to filled-pauses,
we would expect it to perform worse on some other problem.  Section
\ref{extensions} illustrates this point.



In summary, we see that robustness to noisy training material is a
many-faceted problem, and it is unlikely that any single strategy will
work well uniformly. Instead, we advocate understanding the properties
of the noise-avoidance strategy used by the parser and determining
whether it is suitable for some particular domain.  We do not believe
in a silver-bullet algorithm which will work well for any given problem.


\subsection{Parser-specific extensions \label{extensions}}

Here we consider, in the light of our previous experiments, whether we
can make our parsers more robust to noise.  We restrict ourselves to 
what can be easily achieved within the framework of a particular
parser. So, we do not build new parsers from scratch; instead we vary 
any available parameters that might improve results.  This restriction
is natural in that one is more likely to try to get the best results
from a given off-the-shelf parser than try to build one from scratch.

Note that we are not primarily interested in trying to maximise
 the performance
of a system for a given noisy training set. Instead, we wish to gain
an insight into how parser-specific extensions behave across a variety
of settings. As such, we report system performances for a variety of
noise models and  for different noise levels. We therefore have not
used a held-out set to optimise the various parser extensions. Clearly
however, in a practical setting, one would want to do this.

Turning to the maximum entropy parser, within the confines of the
implementation, the only parameter we can vary
is the number of training iterations allowed to fit the model.
As was mentioned in Section \ref{maxent}, after each iteration the
model fits the training material more closely. In general (modulo
overfitting),  after each iteration, performance also increases.  Now,
roughly speaking, after a few iterations, the model fits aspects of the
data of which there is ample evidence.  
  As the number of iterations increases, the model fits more
specific `patterns'.  Should    it be  possible to differentiate
noise from the
underlying, uncorrupted  machinery producing the data in this manner, then it is
possible that early stopping (running for only a few iterations rather
than for many iterations) would yield better performance than when
halting after carrying out many iterations.


Figure \ref{maxentk} shows 
the results we obtained when varying the number of iterations
(using the  {\tt all} noise model). The columns marked  `Iter'
refer to the number of iterations used to train a model.

\begin{figure}[!htb]
\begin{center}
\begin{tabular}{c|  c c c c c c c c c c}
Rate   & Iter & F-score  & Iter & F-score  & Iter &
F-score  & Iter & F-score  & Iter & F-score  \\ \hline
0 & 20 & 89.89   & 40 & 90.54   & 60 & 90.67   & 80 & 90.81   & 100 & 90.87   \\ 
 10  & 20 & 88   & 40 & 88.54   & 60 & 88.62   & 80 & 88.44   & 100 & 88.32   \\ 
 20  & 20 & 85.56   & 40 & 85.81   & 60 & 85.7   & 80 & 85.46   & 100 & 85.24   \\ 
 30  & 20 & 82.1   & 40 & 82.01   & 60 & 81.37   & 80 & 80.83   & 100 & 80.75   \\ 
 40  & 20 & 75.47   & 40 & 75.54   & 60 & 74.94   & 80 & 74.64   & 100 & 74.51   \\ 
 50  & 20 & 68.25   & 40 & 67.44   & 60 & 66.86   & 80 & 66.7   & 100 & 66.42   \\ 
 60  & 20 & 57.26   & 40 & 55.38   & 60 & 54.62   & 80 & 54.31   & 100 & 54.12   \\ 
 70  & 20 & 45.22   & 40 & 40.81   & 60 & 39.55   & 80 & 39.23   & 100 & 39.2   \\ 
 80  & 20 & 30.89   & 40 & 25.38   & 60 & 23.74   & 80 & 23.14   & 100 & 22.9   \\ 
 90  & 20 & 14.34   & 40 & 11.73   & 60 & 10.94   & 80 & 10.62   & 100 & 10.47   \\ 
 100  & 20 & 3.19   & 40 & 3.29   & 60 & 3.33   & 80 & 3.46   & 100 & 3.56 
\end{tabular}
\end{center}
\caption{Results for the maximum entropy parser, using early stopping,
  with the {\tt all} noise model \label{maxentk}}
\end{figure}
As can be seen, early stopping does improve results: as the noise rate
increases, it is better to use fewer and fewer iterations. 

Next, we considered whether we could make the memory-based parser more
resistant to noise in the labels. The TiMBL implementation allows one to
vary the number of nearest neighbours that are used when
classifying unseen examples.  When $k=1$, the system does no
smoothing over labels, and bases its decision upon just the single
best matching example.  As $k$ increases, the system becomes less
sensitive to individual labels.  So, varying $k$ ought to make the
parser more robust to labelling errors.

\begin{figure}[!htb]
\begin{center}
\begin{tabular}{c|c c  c c c c c c c c c c}
Rate & $k$ & F-score & $k$ & F-score & $k$ & F-score & $k$ & F-score &
$k$ & F-score & $k$ & F-score 
\\ \hline
0 & 1 & 89.44 & 3 & 90.22   & 5 & 89.78   & 7 & 88.96   & 9 & 88.16   & 11 & 87.58   \\ 
 10 & 1 & 78.26 & 3 & 87.74   & 5 & 87.79   & 7 & 87.36   & 9 & 86.56   & 11 & 86.09   \\ 
 20 & 1 & 66.86 & 3 & 84.97   & 5 & 85.94   & 7 & 85.86   & 9 & 85.83   & 11 & 85.42   \\ 
 30 & 1 & 57.51 & 3 & 82.93   & 5 & 85.14   & 7 & 85.02   & 9 & 84.65   & 11 & 84.04   \\ 
 40 & 1 & 46.96 & 3 & 77.89   & 5 & 82.92   & 7 & 83.89   & 9 & 84.14   & 11 & 83.61   \\ 
 50 & 1 & 36.46 & 3 & 71.35   & 5 & 80.48   & 7 & 82.13   & 9 & 82.19   & 11 & 81.77   \\ 
 60 & 1 & 29.67 & 3 & 64.6   & 5 & 77.18   & 7 & 80.81   & 9 & 80.73   & 11 & 80.37   \\ 
 70 & 1 & 22.44 & 3 & 52.97   & 5 & 70.86   & 7 & 77.05   & 9 & 78.69   & 11 & 78.17   \\ 
 80 & 1 & 16.99 & 3 & 42.89   & 5 & 61.93   & 7 & 71.84   & 9 & 75.28   & 11 & 75.18   \\ 
 90 & 1 & 11.09 & 3 & 25.18   & 5 & 41.38   & 7 & 54.18   & 9 & 63.22   & 11 & 65.75   \\ 
 100 & 1 & 2.93 & 3 & 2.77   & 5 & 2.62   & 7 & 2.74   & 9 & 2.09   & 11 & 1.8 
\end{tabular}
\end{center}
\caption{Results for the memory-based parser, varying $k$ and using
  the {\tt all} noise model \label{mblk}}
\end{figure}

Figure \ref{mblk} shows the results obtained when training over
material again corrupted by the {\tt all} noise model.  For each noise level, we
varied $k$ and recorded the results.  


Clearly, varying the number of nearest neighbours ($k$) improves
results as the amount of noise increases. 
Note that what is best when training upon material with 
no added noise (a rate of 0) is not best when training upon material
that is noisy.  Also, we see that with no noise, the best value of
$k$ is not 1.  This suggests that the Wall Street Journal is noisy (a
well known result).  Another possible reason %is that the Brill tagger
%introduced even more noise into the data than was present initially.
is that this is some strange  result of the particular choice of features we
used. 

Our results can be seen as being largely contrary to the related work
of \cite{Dael99}. They also varied $k$ for a range of language
problems.  In general, they found that increasing $k$ (from $1$)
decreased performance.  Partly on the basis of this, they concluded
that one should not abstract (smooth) from the data.  Clearly we see
that this argument only holds when using clean training material.

 
Finally, we considered whether we could improve the results of the
N-gram parser.  The implementation we use allows one to vary the order
of the Markov model.\footnote{Note that it is also possible to use
  less specific features in an N-gram model.  This would also simplify
 the resulting model, and so make it less sensitive to noise.  An
 interesting set of experiments would be to see how this approach
 compares with varying the order of the model.} That is, we can use either unigrams (order 1),
bigrams (order 2) or else trigrams (order 3).  Clearly, the lower the
order, the simpler the model.  Simple models can sometimes help deal
with the effects of noise (as was argued in Section \ref{shallow}).

As before, we corrupted the training set with varying rates of noise
(using the {\tt all} model) and estimated models using these corrupted
training sets.  We also varied the order of the model.  Figure
\ref{ngramres} summarises our results.

\begin{figure}
\begin{center}
\begin{tabular}{c | c c c c c c c}
Rate & Model order & F-score & Model order & F-score  & Model order &
F-score \\ \hline
0 & 1              & 75.45 & 2 & 83.86 & 3 & 84.10 \\
10 & 1             & 74.20 & 2 & 80.21 & 3 & 80.23 \\
20 & 1             & 71.52 & 2 & 76.22 & 3 & 75.44 \\
30 & 1             & 69.21 & 2 & 71.52 & 3 & 69.86 \\
40 & 1             & 65.98 & 2 &     66.37  & 3 &     64.04 \\
50 & 1             & 60.35 & 2 &     59.48  & 3 &     56.64 \\
60 & 1             & 54.14 & 2 &     52.54  & 3 &     49.85 \\
70 & 1             & 46.43 & 2 &     43.71  & 3 &     41.42 \\
80 & 1             & 36.77 & 2 &     33.77  & 3 &     31.81 \\
90 & 1             & 20.88 & 2  &    17.79  & 3 &     17.03 \\
100 & 1            &  2.15  & 2  &   2.42  & 3 &      2.61 
\end{tabular}
\end{center}
\caption{Results for the N-gram-based parser, varying the model order
  and using {\tt All} noise model \label{ngramres}}
\end{figure}
As expected, we see that with increasing amounts of noise, it becomes
better to use simpler models. Note that we could have further
simplified our models by reducing the information present within a
`word'.  If we recall, the N-gram parser is trained using words which
are concatenations of (for example) POS tags.  By reducing
the information content of a word, we would also simplify the model,
and so presumably improve upon our results.  The baseline parser
(which only considers POS tags of a unigram model) can be
seen as being such a simplified approach.

In summary, we see that in theory, all of our single-model parsers can be made
more noise-resistant.  Furthermore, we see that tackling noise means
abstracting from the training material. For example, early stopping
prevents maximum entropy from modelling all regularities in the data;
increasing the size of $k$ in memory-based learning forces the system
to abstract away from actual examples; reducing the order of a Markov
model means making the parser ignore more and more of the context in
the training set.  In practice (trying to optimise a parser for noise
in realistic setting), our noise-avoidance strategies may become less
useful. Clearly this is an empirical matter.


In the next Section, we look at what happens 
when  the training set contains  naturally occurring disfluencies.

\section{Experiments using Switchboard \label{swbd}}

Since our previous experiments all used naturally occurring language
corrupted by artificial noise, we also trained our shallow parsers
using realistically disfluent text.  This allows us to investigate
naturally occurring noise. We did not have
access to (noisy) material produced by people annotating large
quantities of text and so could not carry out experiments measuring
noise related to annotator errors.

   The WSJ is not disfluent (being
edited newswire material) so studying the effects of naturally
occurring disfluencies requires non-edited  material.
The parsed {\it Switchboard Corpus}
(henceforth called SWBD) 
consists of manually parsed 
telephone conversations between pairs of people.  Since it
is composed of 
conversational speech, it contains numerous disfluencies (such as
interruptions, incomplete sentences etc).  Training upon SWBD would
therefore provide complementary results to those found using synthetic
noise. However, SWBD is a
different genre from WSJ, and so phrasal distributions will be different
between these two domains.  We therefore have to differentiate between
the effects of disfluencies and distributional variations before we
can come to any conclusions about the effects of naturally occurring
disfluencies on shallow parsing. 

For 
the experiments here, we used all files in section $2$ of the SWBD distribution.  
Using the same script (from the CoNLL website), we created a
training set that consisted of utterances marked with POS
tags and chunk labels.  Figure \ref{exswb} shows an example SWBD utterance annotated in this manner (POS
labels have been suppressed).  There were $35,706$ sentences in our
SWBD training set.  


\begin{figure}[!htb]
\begin{center}
\begin{tabular}{cccccccc}
And & , & um & , & she & had & a & fall \\ 
O & O & B-INTJ & O  & B-NP & B-VP & B-NP & I-NP
\end{tabular}
\caption{An example SWBD annotated utterance \label{exswb}}
\end{center}
\end{figure}


Using the same parser configurations described in Section \ref{exp},
and when testing using the same testing material (namely uncorrupted
parsed WSJ material), we obtained the 
results shown in Figure \ref{swbres1}.
Unsurprisingly, these results are all worse than when training upon
uncorrupted WSJ material (as shown, for example, in
the top row of Figure \ref{white}). 

\begin{figure}[!htb]
\begin{center}
\begin{tabular}{cc c c}
Parser & F-score & Parser & F-score \\ 
 Max & 82.97 & Vote (Max) & 84.62 \\
TNT & 70.73  & Vote (TNT) & 84.33 \\
MBL & 83.20  & Vote (MBL) & 85.08 \\
Baseline & 65.86 & - & - \\
\end{tabular}
\end{center}
\caption{Results when training upon SWBD \label{swbres1}}
\end{figure}

In order to determine whether this performance drop was due to disfluencies, 
or else due to a change in domain (or both), we ran further
experiments. The next Section (\ref{swbd1}) examines the influence of
disfluencies, whilst Section \ref{swbd2} looks at distributional
differences between SWBD and WSJ.  
 
\subsection{Estimating the influence of noise  \label{swbd1}}

The first experiment tried to see if we could reduce noise using one
of the techniques mentioned previously in Section \ref{extensions}. 
If we could reduce the effects of noise, then this would suggest that
SWBD contained significant levels of noise, which in turn was
contributing towards the performance drop.  This assumes that there is a connection between the
experimental setup in Figure \ref{mblk} and \ref{mblvaryk}.  
Figure
\ref{mblvaryk} shows the results obtained when training the
memory-based parser and varying $k$.  As can be seen, the best
performance occurs when $k$ is $3$.  Comparing these results with 
those obtained using artificial noise (and the WSJ),
Figure \ref{mblk}, we see evidence that the noise rate is less than
$10\%$.\footnote{As an anonymous reviewer pointed out, caution should
  be exercised here.  We do not know for sure the relationship between
  Switchboard noise and our noise models. This means that it still
  remains to be seen exactly how the $k$ level relates to  noise
  levels. One way of dealing with this issue would be to try and model
  naturally occurring noise more closely and then see whether, for
  varying levels of noise, there was a relationship with $k$.}
   That is, for Figure \ref{mblk}, $k$ being $3$ is best when the noise rate is less than $10\%$. Noise may therefore not be the significant factor why
there is a performance drop.

\begin{figure}[!htb]
\begin{center}
\begin{tabular}{ccccccc}
$k$ & 1 & 3 & 5 & 7 & 9 & 11 \\
F-score & 80.35 & 83.20 & 82.63 & 81.68 & 80.94 & 80.32
\end{tabular}
\caption{Results when training upon SWBD, using the
  memory-based parser, varying $k$ \label{mblvaryk}}
\end{center}
\end{figure}

These results are not sufficient in themselves, so we also looked at what happened when annotated disfluencies were
removed from SWBD. If these
disfluencies  were significantly
contributing towards errors, then we might expect that this `cleaning' of
the data would improve our results.  We removed any words that were
marked as being an interjection from the training material.   As can
be seen in Figure \ref{swbdres3}, if anything, removing
interjections harms performance.  The reason for this lack of
improvement is that after
removing interjections, phrases are made contiguous that otherwise
would have been separated by interjections.

\begin{figure}[!htb]
\begin{center}
\begin{tabular}{cc c c}
Parser & F-score & Parser & F-score \\ 
 Max & 81.90 & Vote (Max) & 83.77 \\
TNT & 70.47  & Vote (TNT) & 83.57 \\
MBL & 82.70  & Vote (MBL) & 84.58 \\
Baseline & 72.24 & - & - \\
\end{tabular}
\end{center}
\caption{Results when training upon  SWBD with some disfluencies
removed \label{swbdres3}}
\end{figure}

Figure \ref{d6} shows a  distribution
 of the baseline parser (when trained upon the usual SWBD
 training set).  Comparing this distribution with the one obtained
 when the baseline parser was trained on WSJ
 material (Figure \ref{d2}), we see that
 there are differences. For example, in Figures \ref{d2} and \ref{d6},
 we see that in SWBD, words tagged with the POS label VBN  are more
 likely to be within a verbal chunk than to start a verbal chunk in
 WSJ (as was the case in the WSJ corpus).  Furthermore, we see
 that the distribution for SWBD is  not significantly more spread-out (more uniform)
 than the distributions for  WSJ.  If
 disfluencies were strongly present, and were uniformly distributed,
 then we might expect to see this.  



\begin{figure}[!htb]
\begin{center}
\begin{tabular}{lll} 
Label & $P(\mbox{label} \mid \mbox{VBN})$ & Count \\
I-CONJP & 0.0002 & 1 \\
B-NP & 0.0035 & 18 \\
O & 0.0037 & 19 \\
B-PP & 0.0066 & 34 \\
I-NP & 0.0072 & 37 \\
I-ADJP & 0.0093 & 48 \\
B-ADJP & 0.0231 & 119 \\
B-VP & 0.2936 & 1512 \\
I-VP & 0.6527 & 3361 
\end{tabular}
\end{center}
\caption{Distribution of chunk labels for 
  $P(\mbox{label} \mid \mbox{VBN})$, trained upon SWBD \label{d6}}
\end{figure}

In summary, we are lead to believe that naturally occurring
disfluencies are not that harmful to performance.  The next set of
experiments reinforces this opinion.

\subsection{Estimating the effects of distributional differences \label{swbd2}}


In order to determine whether the performance drop was due to
distributional differences,  we  considered the issue of what
happened when the SWBD training material was augmented
with various amounts of WSJ training
material. If SWBD simply lacked phrasal patterns found in WSJ, then we
would expect to find a significant improvement should we simply add
that missing information.

Figure \ref{ratiorecovery} shows what happens when various
randomly selected amounts of WSJ training are
added to the SWBD material.  There were $120k$ tokens (words or
punctuation marks) in the SWBD material.  The total WSJ training set
consisted of $211k$ tokens.

Here, the column marked
`level' shows the number  of WSJ tokens added (in thousands).  So,
a level of $0$ indicates that the training material is entirely SWBD, whilst a level of $211$ shows that the training material
consisted of all of SWBD and the WSJ material. As can be seen, with
only a small amount of WSJ  material, performance significantly
increases. Also, when using all material, we see that performance is
very close to the performance obtained when using just the 
uncorrupted WSJ material (as shown in Figure
\ref{white}).  

Now, these results may suggest that SWBD simply
lacks phrases found in WSJ, and that even a
moderate amount of material containing such information is better than
nothing. 
  However, it is also
possible that performance may simply be increasing due to more
accurate statistics.  To deal with this issue, we also used, in
addition to section $2$,  section
$3$ of SWBD.  Figure \ref{swbdres2} shows our results.
The training set roughly doubled in size, and 
now consisted of $61,515$ SWBD  sentences.



\begin{figure}[!thb]
\begin{center}
\begin{tabular}{c|cccccc}
Level & Max & MBL & TNT & Vote (Max) & Vote (MBL) & Vote (TNT) \\ \hline
0   &   82.31 & 82.83 & 69.99 & 84.15 &  84.66 &  83.89 \\
21  & 86.80 & 86.14 &  77.60 & 87.84  & 88.24 & 87.81 \\
42   & 87.91 & 87.45 & 79.46 & 88.80 &  89.18 & 88.87 \\
63   & 89.01 & 88.07 & 80.49 & 89.80 &  90.07 &  89.79 \\
84   & 89.27 & 88.29 & 81.11 & 89.96 &  90.08 &  89.89 \\
105   & 89.76 & 88.80 & 81.73 & 90.27 &  90.31 & 90.23 \\
126   & 90.19 & 89.02 & 82.02 & 90.65 &  90.71 & 90.61 \\
147   & 90.17 & 89.00 & 82.92 & 90.68 &  90.68 & 90.56 \\
168   & 90.55 & 89.39 & 82.91 & 91.01 &  91.05 &  90.92 \\
189   & 90.72 & 89.43 & 83.41 & 91.03 &  91.02 & 90.93 \\
211  & 90.84 & 89.63 & 83.65 & 91.03 &  91.03 & 90.92
\end{tabular}
\caption{Results when training upon SWBD and varying
  randomly sampled quantities of {\it WSJ} \label{ratiorecovery}}
\end{center}
\end{figure}


\begin{figure}[!htb]
\begin{center}
\begin{tabular}{cc c c}
Parser & F-score & Parser & F-score \\ 
 Max & 83.35 & Vote (Max) & 84.16 \\
TNT & 71.37  & Vote (TNT) & 84.98 \\
MBL & 83.39  & Vote (MBL) & 85.16 \\
Baseline & 63.71 & - & - \\
\end{tabular}
\end{center}
\caption{Results when training upon double the quantity of SWBD material\label{swbdres2}}
\end{figure}

As can be seen (by comparing Figures \ref{swbdres2} and \ref{swbres1}), our results only marginally increase, and so the
results obtained in Figure \ref{ratiorecovery} are not due to more
accurate estimation of models due to training upon more
material. 




An error analysis of the mistakes made when training just on SWBD
material (using the best ensemble parser), and not made when training
upon WSJ material,  found that:
\begin{center}
\begin{itemize}
\item Noun phrases in the WSJ are predicted as being too short. For example, we see:
\begin{center}
\begin{tabular}{cccccccc}
Rockwell & International & Corp. & 's & Tulsa & unit & said & \ldots\\ 
         & I-NP / B-NP              &   I-NP / B-NP    &    &       &      &  
\end{tabular}
\end{center}
Here, the words {\it International} and {\it Corp} are labelled as
being the start of a base noun phrase, when in reality they should all
be within the same base noun phrase.
\item Base noun phrases with non-nominal premodifiers are seen as
being phrases other than base noun phrases:
\begin{center}
\begin{tabular}{ccccccccc}
\ldots & it & had & operating & profit & of & \$ & 10 & million \\
       &    &     &  B-NP / I-VP         &  I-NP / B-NP      &    &   &    &      
\end{tabular}
\end{center}
\item There was little evidence of `strange' parsing decisions, as one
would expect if disfluencies were responsible for parsing errors.
\end{itemize}
\end{center}

In conclusion then, we believe  that the disfluencies in SWBD, whilst
still a factor, are less harmful to performance than the
change of domain (speech to edited text).  Alternatively, this means
that even if SWBD was edited and all disfluencies were
removed, should we train upon that, we would not expect to obtain a
significant performance increase.  When the task is shallow parsing
newswire material, it is better to annotate more newswire material
than to train upon material drawn from a significantly different
distribution. \cite{gild01} made a related point when training full-scale
parsers using the Brown and WSJ parsed treebanks.

\section{Comments \label{comments}}
We mentioned in the introduction that shallow parsing could in
principle  be
undermined by either noise in the training set, or else by
distributional differences between the training set and the testing
set. The first set of results showed that the underlying distributions
are such that shallow parsing is inherently noise-tolerant, and that
only large quantities of noise will significantly undermine
performance. However, should one wish to improve performance when
noise was present, then simple extensions of our basic parsers help.
  Our experiments
showed that different kinds of noise favoured different parsers, and
that in general, no single technique emerged as being best in all
situations.  When dealing with a new problem
(with unknown noise), the best strategy is probably to consider a
range of techniques, optimise them using a held-out set, and then
decide which one to use on the basis of results.  The alternative, of
taking a favourite approach and then hoping that is will perform well
is almost certainly likely to lead to suboptimal results.

We do not wish to comment upon the individual parsers (for example,
arguing that memory-based learning is better than maximum entropy).
The reason for abstaining follows from our results, which tells us
that even if some parser appeared to do well in many situations, we
should not conclude that it would do well in some future  situation.
However, we were pleased with the performance of memory-based
learning, and suggest that it might be well suited  for domains such as
discourse parsing, which is known to be noisy.

The experiments with SWBD suggested that a mismatch in
distribution between examples in the training set and the testing set
undermined performance more than did disfluencies.  Furthermore, we
concluded that should one want to improve upon the performance of
shallow parsing, it is better to annotate more examples, drawn from
the target distribution (which in this case is the WSJ) than to train upon additional material drawn from other
distributions. Language is non-stationary, and pretending otherwise is
ill-advised.  

Drawing together the results from WSJ and SWBD, and with the caveat
that the noise models we used are artificial and so not necessarily
indicative of realistically found noise, one might conclude
that naturally occurring noise is not that much of an issue, and that instead, making sure
that the training set and testing sets are both drawn from the same
distribution is the key factor.  With current treebanks, this is
almost certainly true.  However, should one want to greatly increase
the amount of annotated material in some industrial manner, then
undoubtedly
 such newly created material would become noisier.  Under such
circumstances, and again given the caveat regarding the relationship
between our noise models and naturally occurring noise, the techniques mentioned in this paper would become relevant.



In this paper, we only considered shallow parsing using base
phrases. Further work should consider what happens when parsing is
deeper. We conjecture that the distributions associated with deep
parsing would continue to be sharply peaked.  Consequently, we would
expect similar noise-performance relationships to those reported here.

\acks{We would like to thank Maria Wolters and Mark Core for
  discussions about disfluencies,  the authors of the various
  systems used in this work, and the three anonymous reviewers for
  very helpful comments.}
%\bibliographystyle{plain}

\bibliography{/home/osborne/docs/bib/mdl,/home/osborne/docs/bib/references,/home/osborne/docs/bib/rf,/home/osborne/docs/bib/noise,/home/osborne/docs/bib/np}

%\bibliography{/home/miles/docs/bib/mdl,/home/miles/docs/bib/references,/home/miles/docs/bib/rf,/home/miles/docs/bib/noise,/home/miles/docs/bib/np}
\end{document}
