A Machine Learning Approach to POS Tagging.
We have applied the inductive learning of statistical decision trees and relaxation labeling to the Natural Language Processing (NLP) task of morphosyntactic disambiguation (Part Of Speech Tagging). The learning process is supervised and obtains a language model oriented to resolve POS ambiguities, consisting of a set of statistical decision trees expressing distribution of tags and words in some relevant contexts. The acquired decision trees have been directly used in a tagger that is both relatively simple and fast, and which has been tested and evaluated on the Wall Street Journal (WSJ) corpus with competitive accuracy. However, better results can be obtained by translating the trees into rules to feed a flexible relaxation labeling based tagger. In this direction we describe a tagger which is able to use information of any kind (n-grams, automatically acquired constraints, linguistically motivated manually written constraints, etc.), and in particular to incorporate the machine-learned decision trees. Simultaneously, we address the problem of tagging when only limited training material is available, which is crucial in any process of constructing, from scratch, an annotated corpus. We show that high levels of accuracy can be achieved with our system in this situation, and report some results obtained when using it to develop a 5.5 million words Spanish corpus from scratch.
Introduction
Part of Speech (pos) Tagging is a very basic and well known Natural Language
Processing (nlp) problem which consists of assigning to each word of a text the
proper morphosyntactic tag in its context of appearance. It is very useful for a
number of nlp applications: as a preprocessing step to syntactic parsing, in information
extraction and retrieval (e.g. document classification in internet searchers),
text to speech systems, corpus linguistics, etc.
The base of pos tagging is that many words being ambiguous regarding their
pos, in most cases they can be completely disambiguated by taking into account
an adequate context. For instance, in the sample sentence presented in table 1,
the word shot is disambiguated as a past participle because it is preceded by the
auxiliary was. Although in this case the word is disambiguated simply by looking
at the preceding tag, it must be taken into account that the preceding word could
be ambiguous, or that the necessary context could be much more complicated
than merely the preceding word. Furthermore, there are even cases in which the
ambiguity is non-resolvable using only morphosyntactic features of the context,
and require semantic and/or pragmatic knowledge.

Table

1. A sentence and its pos ambiguity -appearing tags, from the
Penn Treebank corpus, are described in appendix A-.
The DT first JJ time NN he PRP was VBD shot VBN in IN the DT
hand NN as IN he PRP chased VBD the DT robbers NNS outside RB .
first time shot in hand as chased outside
JJ NN NN IN NN IN JJ IN
VBN RP VBN NN
1.1. Existing Approaches to POS Tagging
Starting with the pioneer tagger Taggit (Greene & Rubin 1971), used for an initial
tagging of the Brown Corpus (bc), a lot of effort has been devoted to improving the
quality of the tagging process in terms of accuracy and efficiency. Existing taggers
can be classified into three main groups according to the kind of knowledge they
use: linguistic, statistic and machine-learning family. Of course some taggers are
difficult to classify into these classes and hybrid approaches must be considered.
Within the linguistic approach most systems codify the knowledge involved as a
set of rules (or constraints) written by linguists. The linguistic models range from
a few hundreds to several thousand rules, and they usually require years of labor.
The work of the Tosca group (Oostdijk 1991) and more recently the development
of Constraint Grammars in the Helsinki University (Karlsson et al. 1995) can be
considered the most important in this direction.
A MACHINE LEARNING APPROACH TO POS TAGGING 3
The most extended approach nowadays is the statistical family (obviously due
to the limited amount of human effort involved). Basically it consists of building
a statistical model of the language and using this model to disambiguate a word
sequence. The language model is coded as a set of co-occurrence frequencies for
different kinds of linguistic phenomena.
This statistical acquisition is usually found in the form of n-gram collection, that
is, the probability of a certain sequence of length n is estimated from its occurrences
in the training corpus.
In the case of pos tagging, usual models consist of tag bi-grams and tri-grams
(possible sequences of two or three consecutive tags, respectively). Once the n-gram
probabilities have been estimated, new examples can be tagged by selecting the tag
sequence with highest probability. This is roughly the technique followed by the
widespread Hidden Markov Model taggers. Although the form of the model and
the way of determining the sequence to be modeled can also be tackled in several
ways, most systems reduce the model to unigrams, bi-grams or tri-grams. The
seminal work in this direction is the Claws system (Garside et al. 1987), which
used bi-gram information and was the probabilistic version of Taggit. It was
later improved in (DeRose 1988) by using dynamic programming. The tagger by
(Church 1988) used a trigram model. Other taggers try to reduce the amount of
training data needed to estimate the model, and use the Baum-Welch re-estimation
algorithm (Baum 1972) to iteratively refine an initial model obtained from a small
hand-tagged corpus. This is the case of the Xerox tagger (Cutting et al. 1992)
and its successors. Those interested in the subject can find an excellent overview
in (Merialdo 1994).
Other works that can be placed in the statistical family are those of (Schmid 1994a)
which performs energy-function optimization using neural nets. Comparisons between
linguistic and statistic taggers can be found in (Chanod & Tapanainen 1995,
Other tasks are also approached through statistical methods. The speech recognition
field is very productive in this issue -actually, n-gram modelling was used
in speech recognition before being used in pos tagging-. Recent works in this
field try to not to limit the model to a fixed order n-gram by combining different
order n-grams, morphological information, long-distance n-grams, or triggering
pairs (Rosenfeld 1994, Ristad & Thomas 1996, Saul & Pereira 1997). These are
approaches that we may see incorporated to pos tagging tasks in the short term.
Although the statistic approach involves some kind of learning, supervised or un-
supervised, of the parameters of the model from a training corpus, we place in the
machine-learning family only those systems that include more sophisticated information
than a n-gram model. Brill's tagger (Brill 1992, Brill 1995) automatically
learns a set of transformation rules which best repair the errors committed by a
most-frequent-tag tagger, (Samuelsson et al. 1996) acquire Constraint Grammar
rules from tagged corpora, (Daelemans et al. 1996) apply instance-based learning,
and finally, the work that we present here -based on (M'arquez & Rodr'iguez 1997,
uses decision trees induced from tagged corpora,
and combines the learned knowledge in a hybrid approach consisting of applying
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
relaxation techniques over a set of constraints involving statistical, linguistic and
machine-learned information (Padr'o 1996, Padr'o 1998).
The accuracy reported by most statistic taggers surpasses 96-97% while linguistic
Constraint Grammars surpass 99% allowing a residual ambiguity of 1.026 tags per
word. These accuracy values are usually computed on a test corpus which has not
been used in the training phase. Some corpora commonly used as test benches are
the Brown Corpus, the Wall Street Journal (wsj) corpus and the British National
Corpus (bnc).
1.2. Motivation and Goals
Taking the above accuracy figures into account one may think that pos tagging
is a solved and closed problem this accuracy being perfectly acceptable for most
systems. So why waste time in designing yet another tagger? What does an
increase of 0.3% in accuracy really mean?
There are several reasons for thinking that there is still work to do in the field of
automatic pos tagging.
When processing huge running texts, and considering an average length per sentence
of 25-30 words, if we admit an error rate of 3-4% then it follows that, on
average, each sentence contains one error. Since pos tagging is a very basic task
in most nlp understanding systems, starting with an error in each sentence could
be a severe drawback, especially considering that the propagation of these errors
could grow more than linearly. Other nlp tasks that are very sensitive to pos
disambiguation errors can be found in the domain of Word Sense Disambiguation
(Wilks & Stevenson 1997) and Information Retrieval (Krovetz 1997).
Another issue refers to the need of adapting and tuning taggers that have acquired
(or learned) their parameters from a specific corpus onto another one -which may
contain texts from other domains- trying to minimize the cost of transportation.
The accuracy of taggers is usually measured against a test corpora of the same
characteristics as the corpus used for training. Nevertheless, no serious attempts
have been made to evaluate the accuracy of taggers corpora with different charac-
teristics, or even domain-specific.
Finally, some specific problems must be addressed when applying taggers to languages
other than English. In addition to the problems derived from the richer
morphology of some particular languages, there is a more general problem consisting
of the lack of large manually annotated corpora for training.
Although a bootstrapping approach can be carried out -using a low-accurate
tagger for producing annotated text that could be used then for retraining the
tagger and learning a more accurate model- the usefulness of this approach highly
relies on the quality of the retraining material. So, if we want to guarantee low noisy
retraining corpora, we have to provide methods able to achieve high accuracy, both
on known and unknown words, using a small high-quality training corpus.
In this direction, we are involved in a project for tagging Spanish and Catalan
corpora (over 5M words) with limited linguistic resources, that is, departing from
A MACHINE LEARNING APPROACH TO POS TAGGING 5
a manually tagged core of a size around 70,000 words. For the sake of comparability
we have included experiments performed over a reference corpus of English.
However, we also report the results obtained applying the presented techniques to
annotate the LexEsp Spanish corpus, proving that a very good accuracy can be
achieved at a fairly low human cost.
The paper is organized as follows: In section 2 we describe the application domain,
the language model learning algorithm and the model evaluation. In sections 3 and
4 we describe the language model application through two taggers: A decision tree
based tagger and a relaxation labelling based tagger, respectively. Comparative
results between them in the special case of using a small training corpus and the
joint use of both taggers to annotate a Spanish corpus are reported in section 5.
Finally, the main conclusions and an overview of the future work can be found in
section 6.
2. Language Model Acquisition
To enable a computer system to process natural language, it is required that language
is modeled in some way, that is, that the phenomena occurring in language
are characterized and captured, in such a way that they can be used to predict or
recognize future uses of language: (Rosenfeld 1994) defines language modeling as
the attempt to characterize, capture and exploit regularities in natural language,
and states that the need for language modeling arises from the great deal of variability
and uncertainty present in natural language.
As described in section 1, language models can be hand-written, statistically
derived, or machine-learned. In this paper we present the use of a machine-learned
model combined with statistically acquired models. A testimonial use of hand-written
models is also included.
2.1. Description of the Training Corpus and the Word Form Lexicon
We have used a portion of 1; 170; 000 words of the wsj, tagged according to the
Penn Treebank tag set, to train and test the system. Its most relevant features are
the following.
The tag set contains 45 different tags 1 . About 36:5% of the words in the corpus are
ambiguous, with an ambiguity ratio of 2:44 tags/word over the ambiguous words,
1:52 overall.
The corpus contains 243 different ambiguity classes, but they are not all equally
important. In fact, only the 40 most frequent ambiguity classes cover 83.95% of
the occurrences in the corpus, while the 194 most frequent cover almost all of them
(?99.50%).
The training corpus has also been used to create a word form lexicon -of 49,206
entries- with the associated lexical probabilities for each word. These probabilities
are estimated simply by counting the number of times each word appears in the
corpus with each different tag. This simple information provides a heuristic for
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
a very naive disambiguation algorithm which consists of choosing for each word
its most probable tag according to the lexical probability. Note that such a tagger
does not use any contextual information, but only the frequencies of isolated words.

Figure

1 shows the performance of this most-frequent-tag tagger (mft) on the wsj
domain for different sizes of the training corpus.
The reported figures refer to ambiguous words and they can be taken as a lower
bound for any tagger. More particularly, it is clear that for a training corpus bigger
than 400,000 words, the accuracy obtained is around 81-83%. However it is not
reasonable to think that it could be significantly raised simply by adding more
training corpus in order to estimate the lexical probabilities more effectively.657585
% of Training
%accuracy
MFT Tagger

Figure

1. Performance of the "most frequent tag" heuristic related to the training set size
Due to errors in corpus annotation, the resulting lexicon has a certain amount
of noise. In order to partially reduce this noise, the lexicon has been filtered by
manually checking the entries for the most frequent 200 words in the corpus -note
that the 200 most frequent words in the corpus represent over half of it-. For
instance the original lexicon entry (numbers indicate frequencies in the training
corpus) for the very common word the was:
the
since it appears in the corpus with the six different tags: CD (cardinal), DT (de-
(proper noun) and VBP (verb-personal
form). It is obvious that the only correct reading for the is determiner.
2.2. Learnig Algorithm
From a set of possible tags, choosing the proper syntactic tag for a word in a particular
context can be stated as a problem of classification. In this case, classes are identified
with tags. Decision trees, recently used in several nlp tasks, such as speech
recognition (Bahl 1989), POS tagging (Schmid 1994b, M'arquez & Rodr'iguez 1995,
Daelemans et al. 1996), parsing (McCarthy & Lehnert 1995, Magerman 1996),
A MACHINE LEARNING APPROACH TO POS TAGGING 7
sense disambiguation (Mooney 1996) and information extraction (Cardie 1994), are
suitable for performing this task.
2.2.1. Ambiguity Classes and Statistical Decision Trees It is possible to group
all the words appearing in the corpus according to the set of their possible tags (i.e.
adjective-noun, adjective-noun-verb, adverb-preposition, etc. We will call these
sets ambiguity classes. It is obvious that there is an inclusion relation between
these classes (i.e. all the words that can be adjective, noun and verb, can be, in
particular, adjective and noun), so the whole set of ambiguity classes is viewed as a
taxonomy with a dag structure. Figure 2 represents part of this taxonomy together
with the inclusion relation, extracted from the wsj.
2_ambiguity
4_ambiguity
JJ-NN-RB-VB
JJ-NN-RB-RP-VB
IN-JJ-NN-RB
JJ-NN-RB
JJ-NN-NP-RB JJ-NN-RB-UH

Figure

2. A part of the ambiguity-class taxonomy for the wsj corpus
In this way we split the general pos tagging problem into one classification problem
for each ambiguity class.
We identify some remarkable features of our domain, comparing with common
classification domains in Machine Learning field. Firstly, there is a very large
number of training examples: up to 60,000 examples for a single tree. Secondly,
there is quite a significant noise in both the training and test data: wsj corpus
contains about 2-3% of mistagged words.
The main consequence of the above characteristics, together with the fact that
simple context conditions cannot explain all ambiguities (Voutilainen 1994), is that
it is not possible to obtain trees to completely classify the training examples. In-
stead, we aspire to obtain more adjusted probability distributions of the words over
their possible tags, conditioned to the particular contexts of appearance. So we will
use Statistical decision trees, instead of common decision trees, for representing this
information.
The algorithm we used to construct the statistical decision trees is a non-incremental
supervised learning-from-examples algorithm of the tdidt (Top Down Induction
of Decision Trees) family. It constructs the trees in a top-down way, guided
by the distributional information of the examples (Quinlan 1993).
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
2.2.2. Training Set and Attributes For each ambiguity class a set of examples is
built by selecting from the training corpus all the occurrences of the words belonging
to this ambiguity class. The set of attributes that describe each example refer to the
part-of-speech tags of the neighbour words and to the orthography characteristics
of the word to be disambiguated. All of them are discrete attributes.
For the common ambiguity classes the set of attributes consists of a window
covering 3 tags to the left and 2 tags to the right -this size as well as the final set of
attributes has been determined on an empirical basis- and the word-form. Table 2
shows real examples from the training set for the words that can be preposition and
adverb (IN-RB ambiguity class).

Table

2. Training examples of the preposition-adverb ambiguity
class
tag \Gamma3 tag \Gamma2 tag \Gamma1 !word,tag? tag +1 tag +2
RB VBD IN !"after",IN? DT NNS
JJ NN NNS !"below",RB? VBP DT
A new set of orthographic features is incorporated in order to deal with a particular
ambiguity class, namely unknown words, that will be introduced in following
sections. See table 3 for a description of the whole set of attributes.

Table

3. List of considered attributes
Attribute Values Number of values
tag \Gamma3 any tag in the Penn Treebank 45
tag
tag
tag
tag
word form any word of the ambiguity class !847
first character any printable ASCII character !190
last character " "
other capital
has
Attributes with many values (i.e. the word-form and pre/suffix attributes used
when dealing with unknown words) are treated by dynamically adjusting the number
of values to the N most frequent, and joining the rest in a new otherwise value.
The maximum number of values is fixed at 45 (the number of different tags) in
order to have more homogeneous attributes.
A MACHINE LEARNING APPROACH TO POS TAGGING 9
2.2.3. Attribute Selection Function After testing several attribute selection functions
-including Quinlan's Gain Ratio (Quinlan 1986), Gini Diversity Index by
(Breiman et al. 1984), Relief-f (Kononenko 1994), - 2 Test, and Symmetrical Tau
1991)-, with no significant differences between them, we used an
attribute selection function proposed by (L'opez de M'antaras 1991), belonging to
the information-theory-based family, which showed a slightly higher stability than
the others and which is proved not to be biased towards attributes with many values
and capable of generating smaller trees, with no loss of accuracy, compared with
those of Quinlan's Gain Ratio (L'opez de M'antaras et al. 1996). Roughly speaking,
it defines a distance measurement between partitions and selects for branching the
attribute that generates the closest partition to the correct partition, namely the
one that perfectly classifies the training data.
Let X be a set of examples, C the set of classes and P C (X) the partition of X
according to the values of C. The selected attribute will be the one that generates
the closest partition of X to P C (X). For that we need to define a distance measurement
between partitions. Let PA (X) be the partition of X induced by the values
of attribute A. The average information of such partition is defined as follows:
where p(X; a) is the probability for an element of X belonging to the set a which
is the subset of X whose examples have a certain value for the attribute A, and
it is estimated by the ratio jX" aj
jXj . This average information measurement reflects
the randomness of distribution for the elements of X between the classes of the
partition induced by A. If we now consider the intersection between two different
partitions induced by attributes A and B we obtain:
Conditioned information of PB (X) given PA (X) is: I(PB (X)jPA
p(X;a)
It is easy to show that the measurement
is a distance. Normalizing, we obtain
with values in [0;1]. So, finally, the selected attribute will be that one that minimizes
the normalized distance: dN (P C (X); PA (X)).
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
2.2.4. Branching Strategy When dealing with discrete attributes, usual tdidt
algorithms consider a branch for each value of the selected attribute. However there
are other possibilities. For instance, some systems perform a previous recasting of
the attributes in order to have binary-valued attributes (Magerman 1996). The
motivation could be efficiency (dealing only with binary trees has certain advan-
tages), and avoiding excessive data fragmentation (when there is a large number of
values). Although this transformation of attributes is always possible, the resulting
attributes lose their intuition and direct interpretation, and explode in number. We
have chosen a mixed approach which consists of splitting for all values, and subsequently
joining the resulting subsets into groups for which we have insufficient
statistical evidence for there being different distributions. This statistical evidence
is tested with a - 2 test at a 95% confidence level, with a previous smoothing of
data in order to avoid zero probabilities.
2.2.5. Pruning the Tree In order to decrease the effect of over-fitting, we have
implemented a post pruning technique. In a first step the tree is completely expanded
and afterwards is pruned following a minimal cost-complexity criterion
(Breiman et al. 1984), using a comparatively small fresh part of the training set.
The alternative, of smoothing the conditional probability distributions of the leaves
using fresh corpus (Magerman 1996), has been left out because we also wanted to
reduce the size of the trees. Experimental tests have shown that in our domain,
the pruning process reduces tree sizes up to 50% and improves their accuracy by
2-5%.
2.2.6. An Example Finally, we present a real example of a decision tree branch
learned for the class IN-RB which has a clear linguistic interpretation.
word form
IN
1st right tag
IN
IN
2nd right tag
IN
"as" "As"
others
IN
others
others

Figure

3. Example of a decision tree branch
We can observe in figure 3 that each node in the path from the root to the
leaf contains a question on a concrete attribute and a probability distribution. In
the root it is the prior probability distribution of the class. In the other nodes it
represents the probability distribution conditioned to the answers to the questions
preceding the node. For example the second node says that the word as is more
commonly a preposition than an adverb, but the leaf says that the word as is
A MACHINE LEARNING APPROACH TO POS TAGGING 11
almost certainly an adverb when it occurs immediately before another adverb and
a preposition (this is the case of as much as, as well as, as soon as, etc.
3. TreeTagger: A Tree-Based Tagger
Using the model described in the previous section, we have implemented a reductionistic
tagger in the sense of Constraint Grammars (Karlsson et al. 1995). In a
initial step a word-form frequency dictionary constructed from the training corpus
provides each input word with all possible tags with their associated lexical
probability. After that, an iterative process reduces the ambiguity (discarding low
probable tags) at each step until a certain stopping criterion is satisfied. The whole
process is represented in figure 4. See also table 4 for the real process of disambiguation
of a part of the sentence presented in table 1.
Raw Text Classify Update Filter
Tagging Algorithm
Tree Base
Tagged Text
Tokenizer
Frequency lexicon
Language Model

Figure

4. Architecture of TreeTagger
More particularly, at each step and for each ambiguous word the work to be done
in parallel is:
1. Classify the word using the corresponding decision tree. The ambiguity of the
context (either left or right) during classification may generate multiple answers
for the questions of the nodes. In this case, all the paths are followed and the
result is taken as a weighted average of the results of all possible paths.
2. Use the resulting probability distribution to update the probability distribution
of the word (the updating of the probabilities is done by simply multiplying
previous probabilities per new probabilities coming from the tree).
3. Discard the tags with almost zero probability, that is, those with probabilities
lower than a certain discard boundary parameter.
After the stopping criterion is satisfied, some words could still remain ambigu-
ous. Then there are two possibilities: 1) Choose the most probable tag for each
still-ambiguous word to completely disambiguate the text. 2) Accept the residual
ambiguity (for successive treatment).
Note that a unique iteration forcing the complete disambiguation is equivalent
to use the trees directly as classifiers, and results in a very efficient tagger, while
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ

Table

4. Example of disambiguation
. as he chased the robbers outside .
it.1 IN:0.96 PRP:1 VBD:0.97 DT:1 NNS:1 IN:0.01 .:1
it.2 IN:1 PRP:1 VBD:1 DT:1 NNS:1 RB:1 .:1
stop
performing several steps progressively reduces the efficiency, but takes advantage
of the statistical nature of the trees to get more accurate results.
Another important point is to determine an appropriate stopping criterion -since
the procedure is heuristics, the convergence is not guaranteed, however this is not
the case in our experiments-. First experiments seem to indicate that the performance
increases up to a unique maximum and then softly decreases as the number
of iterations increases. This phenomenon is studied in (Padr'o 1998) and the noise
in the training and test sets is suggested to be the major cause. For the sake of sim-
plicity, in the experiments reported in following sections, the number of iterations
was experimentally fixed to three. Although it might seem an arbitrary decision,
broad-ranging experiments performed seem to indicate that this value results in a
good average tagging performance in terms of accuracy and efficiency.
3.1. Using TreeTagger
We divided the wsj corpus in two parts: words were used as a train-
ing/pruning set, and 50; 000 words as a fresh test set. We used a lexicon -described
in section 2.1- derived from training corpus, containing all possible tags for each
word, as well as their lexical probabilities. For the words in the test corpus not
appearing in the training set, we stored all the tags that these words have in the
test corpus, but no lexical probability (i.e. assigning uniform distribution). This
approach corresponds to the assumption of having a morphological analyzer that
provides all possible tags for unknown words. In following experiments we will treat
unknown words in a less informed way.
From the 243 ambiguity classes the acquisition algorithm learned a base of 194
trees (covering 99.5% of the ambiguous words) and requiring about 500 Kb of
storage. The learning algorithm (in a Common Lisp implementation) took about
cpu-hours running on a Sun SparcStation-10 with 64Mb of primary memory.
The first four columns of table 5 contain information about the trees learned for the
ten most representative ambiguity classes. They present figures about the number
of examples used for learning each tree, their number of nodes and the estimation
of their error rate when tested on a sample of new examples. This last figure could
A MACHINE LEARNING APPROACH TO POS TAGGING 13
be taken as a rough estimation of the error of the trees when used in TreeTagger,
though it is not exactly true, since here learning examples are fully disambiguated
in their context, while during tagging both contexts -left and right- can be
ambiguous.

Table

5. Tree information and number and percentages of error for the most
difficult ambiguity classes
Amb. class #exs #nodes %error tt-errors(%) mft-errors(%)
JJ-VBD-VBN 11,346 761 18.75% 95 (16.70%) 180 (31.64%)
JJ-NN 16,922 680 16.30% 122 (14.01%) 144 (16.54%)
NNS-VBZ 15,233 688 4.37% 44 (6.19%) 81 (11.40%)
JJ-RB 8,650 854 11.20% 48 (10.84%) 73 (16.49%)
Total 179,601 5,871 787 1,806
The tagging algorithm, running on a Sun UltraSparc2, processed the test set at
a speed of ?300 words/sec. The results obtained can be seen at a different levels
of granularity.
ffl The performance of some of the learned trees is shown in last two columns of
table 5. The corresponding ambiguity classes concentrate the 62.5% of the errors
committed by a most-frequent-tag tagger (mft column). tt column shows the
number and percentage of errors committed by our tagger. On the one hand
we can observe a remarkable reduction in the number of errors (56:4%). On the
other hand it is useful to identify some problematic cases. For instance, JJ-NN
seems to be the most difficult ambiguity class, since the associated tree obtains
only a slight error reduction from the mft baseline tagger (15.3%) -this is not
surprising since semantic knowledge is necessary to fully disambiguate between
noun and adjective-. Results for the DT-IN-RB-WDT ambiguity reflect an over-estimation
of the generalization performance of the tree -predicted error rate
(6.07%) is much lower than the real (12.08%)-. This may be indicating a
problem of over pruning.
ffl Global results are the following: when forcing a complete disambiguation the
resulting accuracy was 97:29%, while accepting residual ambiguity the accuracy
rate increased up to 98:22%, with an ambiguity ratio of 1.08 tags/word over the
ambiguous words and 1.026 tags/word overall. In other words, 2.75% of the
words remained ambiguous (over 96% of them retaining only 2 tags).
In (M'arquez & Rodr'iguez 1997) it is shown that these results are as good (and
better in some cases) as the results of a number of the non-linguistically motivated
state-of-the-art taggers.
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
In addition, we present in figure 5 the performance achieved by our tagger with
increasing sizes of the training corpus. Results in accuracy are computed over all
words. The same figure includes mft results, which can be seen as a lower bound.9092949698
%accuracy
TreeTagger
MFT Tagger

Figure

5. Performance of the tagger related to the training set size
Following the intuition, we see that performance grows as the training set size
grows. The maximum is at 97.29%, as previously indicated.
One way to easily evaluate the quality of the class-probability estimates given
by a classifier is to calculate a rejection curve. That is to plot a curve showing
the percentage of correctly classified test cases whose confidence level exceeds a
given value. In the case of statistical decision trees this confidence level can be
straightforwardly computed from the class probabilities given by leaves of the trees.
In our case we calculate the confidence level as the difference in probability between
the two most probable cases (if this difference is large, then the chosen class is clearly
much better than the others; if the difference is small, then the chosen class is nearly
tied with another class). A rejection curve that increases smoothly, indicates that
the confidence level produced by the classifier can be transformed into an accurate
probability measurement.
The rejection curve for our classifier, included in figure 6, increases fairly smoothly,
giving the idea that that the acquired statistical decision trees provide good confidence
estimates. This is in close connection with the aforementioned positive results
of the tagger when disambiguation in the low-confidence cases is not required.
3.2. Unknown words
Unknown words are those words not present in the lexicon (i.e. in our case, the
words not present in the training corpus). In the previous experiments we have not
considered the possibility of unknown words. Instead we have assumed a morphological
analyzer providing the set of possible tags with a uniform probability dis-
tribution. However, this is not the most realistic scenario. Firstly, a morphological
analyzer is not always present (due to the morphological simplicity of the treated
A MACHINE LEARNING APPROACH TO POS
rejection
accuracy

Figure

6. Rejection curve for the trees acquired with full training set
language, the existence of some efficiency requirements, or simply the lack of re-
sources). Secondly, if it is available, it very probably has a certain error rate that
makes it necessary to considered the noise it introduces. So it seems clear that we
have to deal with unknown words in order to obtain more realistic figures about
the real performance of our tagger.
There are several approaches to dealing with unknown words. On the one hand,
one can assume that unknown words may potentially take any tag, excluding those
tags corresponding to closed categories (preposition, determiner, etc.), and try to
disambiguate between them. On the other hand, other approaches include a pre-process
that tries to guess the set of candidate tags for each unknown word to feed
the tagger with this information. See (Padr'o 1998) for a detailed explanation of
the methods.
In our case, we consider unknown words as words belonging to the ambiguity
class containing all possible tags corresponding to open categories (i.e. noun, proper
noun, verb, adjective, adverb, cardinal, etc. The number of candidate tags come to
20, so we state a classification problem with 20 different classes. We have estimated
the proportion of each of these tags appearing naturally in the wsj as unknown
words and we have collected the examples from the training corpus according to
these proportions. The most frequent tag, NNP (proper noun), represents almost
30% of the sample. This fact establishes a lower bound for accuracy of 30% in this
domain (i.e. the performance that a most-frequent-tag tagger would obtain).
We have used very simple information about the orthography and the context
of unknown words in order to improve these results. In particular, from an initial
set of 17 potential attributes, we have empirically decided the most relevant, which
turned out to be the following: 1) In reference to word form: the first letter, the last
three letters, and other four binary-valued attributes accounting for capitalization,
whether the word is a multi-word or not, and for the existence of some numeric
characters in the word. 2) In reference to context: only the preceding and the
following pos tags. This set of attributes is fully described in table 3.
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ

Table

6 shows the generalization performance of the trees learned from training
sets of increasing sizes up to 50,000 words. In order to compare these figures with a
close approach we have implemented Igtree system (Daelemans et al. 1996) and
we have tested its performance exactly under the same conditions as ours.
Igtree system is a memory-based pos tagger which stores in memory the whole
set of training examples and then predicts the part of speech tags for new words in
particular contexts by extrapolation from the most similar cases held in memory
(k-nearest neighbour retrieval algorithm). The main connection point to the work
presented here is that huge example bases are indexed using a tree-based formalism,
and that the retrieval algorithm is performed by using the generated trees as classi-
fiers. Additionally, these trees are constructed on the base of a previous weighting
of attributes (contextual and orthographic attributes used for disambiguating are
very similar to ours) using Quinlan's Information Ratio (Quinlan 1986).
Note that the final pruning step applied by Igtree to increase the compression
factor even more has also been implemented in our version. The results of Igtree
are also included in table 6. Figures 7 and 8 contain the plots corresponding to the
same results.

Table

6. Generalization performance of the trees for
unknown words
TreeTagger Igtree
#exs. accuracy(#nodes) accuracy(#nodes)
2,000 77.53% (224) 70.36% (627)
5,000 80.90% (520) 76.33% (1438)
10,000 83.30% (1112) 79.18% (2664)
20,000 85.82% (1644) 82.30% (4783)
30,000 87.32% (2476) 85.11% (6477)
50,000 88.12% (4056) 87.14% (9554)
Observe that our system produces better quality trees than those of Igtree -we
measure this quality in terms of generalization performance (how well these trees fit
new examples) and size (number of nodes)-. On the one hand, we see in figure 7
that our generalization performance is better. On the other hand, figure 8 seems
to indicate that the growing factor in the number of nodes is linear in both cases,
but clearly lower in ours.
Important aspects contributing to the lower size are the merging of attribute
values and the post pruning process applied in our algorithm. Experimental results
showed that the tree size is reduced by up to 50% on average without loss in
accuracy (M'arquez 1998).
The better performance is probably due to the fact that Igtrees are not actually
decision trees (in the sense of trees acquired by a supervised algorithm of top-down
induction, that use a certain attribute selection function to decide at each step
which is the attribute that best contributes to discriminate between the current
set of examples), but only a tree-based compression of a base of examples inside
A MACHINE LEARNING APPROACH TO POS TAGGING
%accuracy
TreeTagger
IGTree

Figure

7. Accuracy vs. training set size for unknown words
a kind of weighted nearest-neighbour retrieval algorithm. The representation and
the weighting of attributes allows us to think of Igtrees as the decision trees that
would be obtained by applying the usual top-down induction algorithm with a very
naive attribute selection function consisting of making a previous unique ranking of
attributes using Quinlan's Information Ratio over all examples and later selecting
the attributes according to this ordering. Again, experimental results show that it
is better to reconsider the selection of attributes at each step than to decide on an
a priori fixed order (M'arquez 1998).2006001000
#nodes
TreeTagger
IGTree

Figure

8. Number of nodes of the trees for unknown words
Of course, these conclusions have to be taken in the domain of small training sets
-the same plot in figure 8 suggests that the difference between the two methods
decreases as the training set size increases-. Using bigger corpora for training
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
might improve performance significantly. For instance, (Daelemans et al. 1996)
report an accuracy rate of 90.6% on unknown words when training with the whole
wsj (2 million words). So our results can be considered better than theirs in the
sense that our system needs less resources for achieving the same performance.
Note that the same result holds when using the whole training set: Daelemans et
al. report a tagging accuracy of 96.4%, training with a 2Mwords training set, while
our results, slightly over 97%, were achieved using only 1.2Mwords 2 .
4. Relax: A Relaxation Labelling Based Tagger
Up to now we have described a decision-tree acquisition algorithm used to automatically
obtain a language model for pos tagging, and a classification algorithm
which uses the obtained model to disambiguate fresh texts.
Once the language model has been acquired, it would be useful that it could be
used by different systems and extended with new knowledge. In this section we
will describe a flexible tagger based on relaxation labelling methods, which enables
the use of models coming from different sources, as well as their combination and
cooperation.
Algorithm
Bigrams
Trigrams
Manually
constraints
Tagged Corpus
Labelling
constraints
Tree-based
Relaxation
Raw Corpus
Lexicon
Language Model
Tagging Algorithm

Figure

9. Architecture of Relax tagger
The tagger we present has the architecture described in figure 9: A unique algorithm
uses a language model consisting of constraints obtained from different
knowledge sources.
Relaxation is a generic name for a family of iterative algorithms which perform
function optimization, based on local information. They are closely related to
neural nets (Torras 1989) and gradient step (Larrosa & Meseguer 1995b).
Although relaxation operations had long been used in engineering fields to solve
systems of equations (Southwell 1940), they did not achieve their breakthrough
success until relaxation labelling -their extension to the symbolic domain- was
applied by (Waltz 1975, Rosenfeld et al. 1976) to constraint propagation field, especially
in low-level vision problems.
Relaxation labelling is a technique that can be used to solve consistent labelling
problems (clps) -see (Larrosa & Meseguer 1995a)-. A consistent labelling probA
lem consists of, given a set of variables, assigning to each variable a value compatible
with the values of the other ones, satisfying -to the maximum possible extent- a
set of compatibility constraints.
In the Artificial Intelligence field, relaxation has been mainly used in computer
vision -since it is where it was first used- to address problems such as corner and
edge recognition or line and image smoothing (Richards et al. 1981, Lloyd 1983).
Nevertheless, many traditional AI problems can be stated as a labelling prob-
lem: the traveling salesman problem, n-queens, or any other combinatorial problem
(Aarts & Korst 1987).
The utility of the algorithm to perform nlp tasks was pointed out in the work
by (Pelillo & Refice 1994, Pelillo & Maffione 1994), where pos tagging was used
as a toy problem to test some methods to improve the computation of constraint
compatibility coefficients for relaxation processes. Nevertheless, the first application
to a real nlp problems, on unrestricted text is the work presented in (Padr'o 1996,
Voutilainen & Padr'o 1997, M`arquez & Padr'o 1997, Padr'o 1998).
From our point of view, the most remarkable feature of the algorithm is that,
since it deals with context constraints, the model it uses can be improved by writing
into the constraint formalism any available knowledge. The constraints used
may come from different sources: statistical acquisition, machine-learned models or
hand coding. An additional advantage is that the tagging algorithm is independent
of the complexity of the model.
4.1. The Algorithm
Although in this section the relaxation algorithm is described from a general point
of view, its application to pos tagging is straightforwardly performed, considering
each word as a variable and each of its possible pos tags as a label.
be a set of variables (words).
g be the set of possible labels (pos tags) for variable v i
(where m i is the number of different labels that are possible for v i ).
Let C be a set of constraints between the labels of the variables. Each constraint
is a compatibility value for a combination of pairs variable-label.
binary constraint (e.g. bi-gram)
ternary constraint (e.g. tri-gram)
The first constraint states that the combination of variable v 1 having label A,
and variable v 3 having label B, has a compatibility value of 0:53. Similarly, the
second constraint states the compatibility value for the three pairs variable-value
it contains.
Constraints can be of any order, so we can define the compatibility value for
combinations of any number of variables.
The aim of the algorithm is to find a weighted labelling such that global consistency
is maximized.
A weighted labelling is a weight assignment for each possible label of each variable:
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
is a vector containing a weight for each
possible label of v i , that is: p
Since relaxation is an iterative process, the weights vary in time. We will note
the weight for label j of variable i at time step n as p i
j (n), or simply p i
j when the
time step is not relevant.
Maximizing global consistency is defined as maximizing for each variable v i , (1 -
the average support for that variable, which is defined as the weighted sum
of the support received by each of its possible labels, that is:
ij is the support received by that pair from the context.
The support for a pair variable-label how compatible is the assignation
of label j to variable i with the labels of neighbouring variables, according
to the constraint set.
Although several support functions may be used, we chose the following one,
which defines the support as the sum of the influence of every constraint on a label.
Inf(r)
are defined as follows:
R ij is the set of constraints on label j for variable i, i.e. the constraints formed
by any combination of variable-label pairs that includes the pair (v
k1
kd (m), is the product of the current weights for
the labels appearing in the constraint except (v
(representing how applicable
the constraint is in the current context) multiplied by C r which is the constraint
compatibility value (stating how compatible the pair is with the context).
Although the C r compatibility values for each constraint may be computed in
different ways, performed experiments (Padr'o 1996, Padr'o 1998) point out that the
best results in our case are obtained when computing compatibilities as the mutual
information between the tag and the context (Cover & Thomas 1991). Mutual
information measures how informative is an event with respect to another, and is
computed as
If A and B are independent events, the conditional probability of A given B will
be equal to the marginal probability of A and the measurement will be zero. If
the conditional probability is larger, it means than the two events tend to appear
together more often than they would by chance, and the measurement yields a
positive number. Inversely, if the conditional occurrence is scarcer than chance,
the measurement is negative. Although Mutual information is a simple and useful
way to assign compatibility values to our constraints, a promising possibility still to
be explored is assigning them by Maximum Entropy Estimation (Rosenfeld 1994,
The pseudo-code for the relaxation algorithm can be found in table 7. It consists
of the following steps:
A MACHINE LEARNING APPROACH TO POS TAGGING 21
1. Start in a random labelling P 0 . In our case, we select a better-informed starting
point, which are the lexical probabilities for each word tag.
2. For each variable, compute the support that each label receives from the current
weights from other variable labels (i.e. see how compatible is the current
weighting with the current weightings of the other variables, given the set of
constraints).
3. Update the weight of each variable label according to the support obtained
by each of them (that is, increase weight for labels with high support -greater
than zero-, and decrease weight for those with low support -less than zero-).
The chosen updating function in our case was:
4. iterate the process until a convergence criterion is met. The usual criterion is
to wait for no significant changes.
The support computing and weight changing must be performed in parallel, to
avoid that changing a weight for a label would affect the support computation of
the others.
We could summarize this algorithm by saying that at each time-step, a variable
changes its label weights depending on how compatible is that label with the labels
of the other variables at that time-step. If the constraints are consistent, this
process converges to a state where each variable has weight 1 for one of its labels
and weight 0 for all the others.
The performed global consistency maximization is a vector optimization. It does
not maximize -as one might think- the sum of the supports of all variables, but it
finds a weighted labelling such that any other choice would not increase the support
for any variable, given -of course- that such a labelling exists. If such a labelling
does not exist, the algorithm will end in a local maximum.
Note that this global consistency idea makes the algorithm robust: The problem
of having mutually incompatible constraints (there is no combination of label
assignations which satisfies all the constraints) is solved because relaxation does
not necessarily find an exclusive combination of labels -i.e. a unique label for each
variable-, but a weight for each possible label such that constraints are satisfied to
the maximum possible degree. This is especially useful in our case, since constraints
will be automatically acquired, and different knowledge sources will be combined,
so constraints might not be fully consistent.
The advantages of the algorithm are:
ffl Its highly local character (each variable can compute its new label weights
given only the state at previous time-step). This makes the algorithm highly
parallelizable (we could have a processor to compute the new label weights for
22 LLU' iS M '
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
1.
2. repeat
3. for each variable v i
4. for each t j possible label for v i
Inf(r)
6. end for
7. for each t j possible label for v i
8.
9. end for
10. end for
11. until no more changes

Table

7. Pseudo code of the relaxation labelling algorithm.
each variable, or even a processor to compute the weight for each label of each
variable).
Its expressiveness, since we state the problem in terms of constraints between
variable labels. In our case, this enables us to use binary (bigram) or ternary
(trigram) constraints, as well as more sophisticated constraints (decision tree
branches or hand-written constraints).
Its flexibility, we do not have to check absolute consistency of constraints.
Its robustness, since it can give an answer to problems without an exact solution
(incompatible constraints, insufficient data, . )
ffl Its ability to find local-optima solutions to np problems in a non-exponential
time (only if we have an upper bound for the number of iterations, i.e. convergence
is fast or the algorithm is stopped after a fixed number of iterations).
The drawbacks of the algorithm are:
Its cost. N being the number of variables, v the average number of possible
labels per variable, c the average number of constraints per label, and I the
average number of iterations until convergence, the average cost is N \Theta v \Theta c \Theta I,
that is, it depends linearly on N , but for a problem with many labels and
constraints, or if convergence is not quickly achieved, the multiplying terms
might be much bigger than N . In our application to pos tagging, the bottleneck
A MACHINE LEARNING APPROACH TO POS TAGGING 23
is the number of constraints -which may be several thousand-. The average
number of tags per ambiguous word is about 2.5, and an average sentence
contains about 10 ambiguous words.
ffl Since it acts as an approximation of gradient step algorithms, it has their typical
convergence problems: Found optima are local, and convergence is not guaran-
teed, since the chosen step might be too large for the function to optimize.
ffl In general relaxation labelling applications, constraints would be written manu-
ally, since they are the modeling of the problem. This is good for easy-to-model
domains or reduced constraint-set problems, but in the case of pos tagging,
constraints are too many and too complicated to be easily written by hand.
ffl The difficulty of stating by hand what the compatibility value is for each con-
straint. If we deal with combinatorial problems with an exact solution (e.g.
traveling salesman), the constraints will be either fully compatible (e.g. stating
that it is possible to go to any city from any other), fully incompatible (e.g.
stating that it is not possible to be twice in the same city), or will have a value
straightforwardly derived from the distance between cities. But if we try to
model more sophisticated or less exact problems (such as pos tagging), we will
have to establish a way of assigning graded compatibility values to constraints.
As mentioned above, we will be using Mutual Information.
ffl The difficulty of choosing the most suitable support and updating functions for
each particular problem.
4.2. Using Machine-Learned Constraints
In order to feed the Relax tagger with the language model acquired by the
decision-tree learning algorithm, the group of the 44 most representative trees
(covering 83.95% of the examples) were translated into a set of weighted context
constraints. Relax was fed not only with that constraints, but also with bi/tri-
gram information.
The Constraint Grammars formalism (Karlsson et al. 1995) was used to code the
tree branches. CG is a widespread formalism used to write context constraints.
Since it is able to represent any kind of context pattern, we will use it to represent
all our constraints, n-gram patterns, hand-written constraints, or decision-tree
branches.
Since the CG formalism is intended for linguistic uses, the statistical contribution
has no place in it: Constraints can state only full compatibility (constraints that
select a particular reading) or full incompatibility (constraints that remove a
particular reading). Thus, we slightly extended the formalism to enable the use
of real-valued compatibilities, in such a way that constraints are not assigned a
REMOVE/SELECT command, but a real number indicating the constraint compatibility
value, which -as described in section 4.1- was computed as the mutual
information between the focus tag and the context.
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
The translation of bi/tri-grams to context constraints is straightforward. A left
prediction bigram and its right prediction counterpart would be:
The training corpus contains 1404 different bigrams. Since they are used both for
left and right prediction, they are converted in 2808 binary constraints.
A trigram may be used in three possible ways (i.e. the abc trigram pattern
generates the constraints: c, given it is preceded by ab; a, given it is followed by
bc; and b, given it is preceded by a and followed by c):
2:16 (VB) 1:54 (NN) 1:82 (DT)
The 17387 trigram patterns in the training corpus produce 52161 ternary constraints

The usual way of expressing trees as a set of rules was used to construct the context
constraints. For instance, the tree branch represented in figure 3 was translated
into the two following constraints:
\Gamma5:81 (IN) 2:366 (RB)
(0 "as" "As") (0 "as" "As")
which express the compatibility (either positive or negative) of the tag in the first
line with the given context (i.e. the focus word is "as", the first word to the
right has tag RB and the second has tag IN). The decision trees acquired for the 44
most frequent ambiguity classes result in a set of 8473 constraints.
The main advantage of Relax is its ability to deal with constraints of any kind.
This enables us to combine statistical n-grams (written in the form of constraints)
with the learned decision tree models, and even with linguistically motivated hand-written
constraints, such as the following,
which states a high compatibility value for a VBN (participle) tag when preceded
by an auxiliary verb, provided that there is no other participle, adjective nor any
phrase change in between.
Since the cost of the algorithm depends linearly on the number of constraints,
the use of the trigram constraints (either alone or combined with the others) makes
the disambiguation about six times slower than when using bc, and about 20 times
slower than when using only b.
A MACHINE LEARNING APPROACH TO POS TAGGING 25
The obtained results for the different knowledge combination are shown in table
8. The results produced by two baseline taggers -mft: most-frequent-tag tag-
ger, hmm: bi-gram Hidden Markov Model tagger by (Elworthy 1993)- are also
reported. b stands for bi-grams, t for trigrams, and c for the constraints acquired
by the decision tree learning algorithm. Results using a sample of 20 linguistically-motivated
constraints (h) can be found in table 9.
Those results show that the addition of the automatically acquired context constraints
led to an improvement in the accuracy of the tagger, overcoming the bi/tri-
gram models and properly cooperating with them. See (M'arquez & Padr'o 1997)
for more details on the experiments and comparisons with other current taggers.

Table

8. Results of baseline tagger and of the Relax tagger using every combination of constraint
kinds
ambiguous 85:31% 91:75% 91:35% 91:82% 91:92% 91:96% 92:72% 92:82% 92:55%
overall 94:66% 97:00% 96:86% 97:03% 97:06% 97:08% 97:36% 97:39% 97:29%

Table

9. Results of our tagger using every combination of constraint kinds plus hand
written constraints
h bh th bth ch bch tch btch
ambiguous 86:41% 91:88% 92:04% 92:32% 91:97% 92:76% 92:98% 92:71%
overall 95:06% 97:05% 97:11% 97:21% 97:08% 97:37% 97:45% 97:35%

Figure

shows the 95% confidence intervals for the results in table 8. The main
conclusions that can be drawn from those data are described below.
ffl Relax is slightly worse than the HMM tagger when using the same information
(bi-grams). This may be due to a higher sensitivity to noise in the training
corpus.
ffl There are two significantly distinct groups: Those using only statistical infor-
mation, and those using statistical information plus the decision trees model.
The n-gram models and the learned model belong to the first group, and any
combination of a statistical model with the acquired constraint belongs to the
second group.
ffl Although the hand-written constraints improve the accuracy of any model,
the size of the linguistic constraint set is too small to make this improvement
statistically significant.
ffl The combination of the two kinds of model produces significantly better results
than any separate use. This indicates that each model contains information
which was not included in the other, and that relaxation labelling combines
them properly.
26 LLU' iS M '
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZHMMBTBTCBCTCBTCTCH
96.50 97.00 97.50
97.00 97.50
Figure

10. 95% confidence intervals for the Relax tagger results
5. Using Small Training Sets
In this section we will discuss the results obtained when using the two taggers
described above to apply the language models learned from small training corpus.
The motivation for this analysis is the need for determining the behavior of our
taggers when used with language models coming from scarce training data, in order
to best exploit them for the development of Spanish and Catalan tagged corpora
starting from scratch.
5.1. Testing Performance on WSJ
In particular we used 50,000 words of the wsj corpus to automatically derive a
set of decision trees and collect bi-gram statistics. Tri-gram statistics were not
considered since the size of the training corpus was not large enough to reasonably
estimate the big number of parameters for the model -note that a 45-tag tag set
produces a trigram model of over 90,000 parameters, which obviously cannot be
estimated from a set of 50,000 occurrences-.
Using this training set the learning algorithm was able to reliably acquire over
trees representing the most frequent ambiguity classes -note that the training
data was insufficient for learning sensible trees for about 150 ambiguity classes-.
Following the formalism described in the previous section, we translated these trees
into a set of about 4,000 constraints to feed the relaxation labelling algorithm.
The results in table 10 are computed as the average of ten experiments using
randomly chosen training sets of 50,000 words each. b stands for the bi-gram
A MACHINE LEARNING APPROACH TO POS TAGGING 27

Table

10. Comparative results using different models acquired from small training
corpus
mft TreeTagger Relax(c) Relax(b) Relax(bc)
ambiguous 75.35% 87.29% 86.29% 87.50% 88.56%
overall 91.64% 95.69% 95.35% 95.76% 96.12%Tree-based (C)Relax (C)Relax (B)Relax (BC)
Figure

11. 95% confidence intervals for both tagger results
model and c for the learned decision tree (either in the form of trees or translated
to constraints). The corresponding confidence intervals can be found in figure 11.
The presented figures point out the following conclusions:
ffl We think this result is quite accurate. In order to corroborate this statement
we can compare our accuracy of 96.12% with the 96.0% reported by
(Daelemans et al. 1996) for the Igtree Tagger trained with a double size corpus
(100 Kw).
ffl TreeTagger yields a higher performance than the Relax tagger when both
use only the c model. This is caused by the fact that, due to the scarceness
of the data, a significant amount of test cases do not match any complete
tree branch, and thus TreeTagger uses some intermediate node probabilities.
Since only complete branches are translated to constrains -partial branches
were not used to avoid excessive growth in the number of constraints-, the
tagger does not use intermediate node information and produces lower
results. A more exhaustive translation of tree information into constraints is an
issue that should be studied in the short run.
ffl The Relax tagger using the b model produces better results than any of the
taggers when using the c model alone. The cause of this is related with the
aforementioned problem of estimating a big number of parameters with a small
sample. Since the model consists of six features, the number of parameters to
28 LLU' iS M '
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
be learned is still larger than in the case of tri-grams, thus the estimation is
not as complete as it could be.
ffl The Relax tagger using the bc model produces better results (statistically
significant at a 95% confidence level) than any other combination. This suggests
that, although the tree model is not complete enough on its own, it contains
different information than the bi-gram model. Moreover this information is
proved to be very useful when combined with the b model by Relax.
5.2. Tagging the LexEsp Spanish Corpus
The LexEsp Project is a multi-disciplinary effort headed by the Psychology Department
at the University of Oviedo. It aims to create a large database of language
usage in order to enable and encourage research activities in a wide range of fields,
from linguistics to medicine, through psychology and artificial intelligence, among
others. One of the main issues of this database of linguistic resources is the LexEsp
corpus, which contains 5.5 Mw of written material, including general news, sports
news, literature, scientific articles, etc.
The corpus has been morphologically analyzed with the maco+ system, a fast,
broad-coverage analyzer (Carmona et al. 1998). The tagset contains 62 tags. The
percentage of ambiguous words is 39.26% and the average ambiguity ratio is 2.63
tags/word for the ambiguous words (1.64 overall).
From this material, 95 Kw were hand-disambiguated to get an initial training
set of 70 Kw and a test set of 25 Kw. To automatically disambiguate the rest
of the corpus, we applied a bootstrapping method taking advantage of the use
of both taggers. The procedure applied starts by using the small hand-tagged
portion of the corpus as an initial training set. After that, both taggers are used to
disambiguate further fresh material. The tagger agreement cases of this material
are used to enlarge the language model, incorporating it to the training set and
retraining both taggers. This procedure could be iterated to obtain progressively
better language models.
The point here is that the cases in which both taggers coincide present a higher
accuracy, and thus can be used as new retraining set with a lower error rate than
that obtained using a single tagger. For instance, using a single tagger trained with
the hand-disambiguated training set, we can tag 200,000 fresh words and use them
to retrain the tagger. In our case, the best tagger would tag this new set with 97.4%
accuracy. Merging this result with the previous hand-disambiguated set, we would
obtain a 270Kw corpus with an error rate of 1.9%. On the other hand, given that
both taggers agree in 97.5% of the cases in the same 200Kw set, and that 98.4%
of those cases are correctly tagged, we get a new corpus of 195Kw with an error
rate of 1.6%. If we add the manually tagged 70Kw we get a 265Kw corpus with an
1.2% error rate, which is significantly lower than 1.9%.
The main results obtained with this approach are summarized below: Starting
with the manually tagged training corpus, the best tagger combination achieved an
accuracy of 93.1% on ambiguous words and 97.4% overall. After one bootstrapping
A MACHINE LEARNING APPROACH TO POS TAGGING 29
iteration, using the coincidence cases in a fresh set of 800 Kw, the accuracy was
increased up to 94.2% for ambiguous words and 97.8% overall. It is important to
note that this improvement is statistically significant and that it has been achieved
in a completely automatic re-estimation process. In our domain, further iterations
did not result in new significant improvements.
For a more detailed description we refer the reader to (M'arquez et al. 1998),
where experiments using different sizes for the retraining corpus are reported, as
well as different combination techniques, such as weighted interpolation and/or
previous hand checking of the tagger disagreement cases.
From the aforementioned results we emphasize the following conclusions:
ffl A 70 Kw manually-disambiguated training set provides enough evidence to allow
our taggers to get fairly good results. In absolute terms, results obtained
with the LexEsp Spanish corpus are better than those obtained for wsj English
corpus. One of the reasons contributing to this fact may be the less noisy training
corpus. However it should be investigated if the part of speech ambiguity
cases for Spanish are simpler on average.
ffl The combination of two (or more) taggers seems to be useful to:
- Obtain larger training corpora with a reduced error rate, which enable the
learning procedures to build more accurate taggers.
- Building a tagger which proposes a single tag when both taggers coincide
and two tags when they disagree. Depending on user needs, it might be
worthwhile to accept a higher remaining ambiguity in favour of a higher
recall. With the models acquired from the best training corpus, we get a
tagger with a recall of 98.3% and a remaining ambiguity of 1.009 tags/word,
that is, 99.1% of the words are fully disambiguated and the remaining 0.9%
keep only two tags.
6. Conclusions
In this work we have presented and evaluated a machine-learning based algorithm
for obtaining statistical language models oriented to pos tagging.
We have directly applied the acquired models in a simple and fast tree-based
tagger obtaining fairly good results. We also have combined the models with n-gram
statistics in a flexible relaxation-labelling based tagger. Reported figures
show that both models properly collaborate in order to improve the results.
Both model learning and testing have been performed on the wsj corpus of English

Comparison between the results obtained using large training corpora (see section
4.2) with those obtained with fairly small training sets (see section 5) points
out that the best policy in both cases is the combination of the learned tree-based
model with the best n-gram model.
When using large training corpora, the reported accuracy (97.36%) is, if not
better, at least as good as that of a number of current non-linguistic based taggers
ARQUEZ, LLU' iS PADR '
O AND HORACIO RODR' iGUEZ
-see (M'arquez & Padr'o 1997) for further details-. When using small training
corpora, a promising 96.12% was obtained for English.
Deeper application of the techniques, together with the collaboration of both
taggers in a voting approach was used to develop from scratch a 5.5Mw annotated
corpus (LexEsp) with an estimated accuracy of 97.8%. This result confirms
the validity of the the proposed method and shows that a very high accuracy
is possible for Spanish tagging with a relatively low manual effort. More details
about this issue can be found in (M'arquez et al. 1998).
However, further work is still to be done in several directions. Referring to the
language model learning algorithm, we are interested in testing more informed
attribute selection functions, considering more complex questions in the nodes and
finding a good smoothing procedure for dealing with very small ambiguity classes.
See (M'arquez & Rodr'iguez 1997) for a first approach.
In reference to the information that this algorithm uses, we would like to explore
the inclusion of more morphological and semantic information, as well as more
complex context features, such as non-limited distance or barrier rules in the style
of (Samuelsson et al. 1996).
We are also specially interested in extending the experiments involving combinations
of more than two taggers in a double direction: first, to obtain less noisy
corpora for the retraining steps in bootstrapping processes; and second, to construct
ensembles of classifiers to increase global tagging accuracy. We plan to apply these
techniques to develop taggers and annotated corpora for the Catalan language in
the near future.
We conclude by saying that we have carried out first attempts (Padr'o 1998) in
using the same techniques to tackle another classification problem in the nlp area,
namely Word Sense Disambiguation (wsd). We believe, as other authors do, that
we can take advantage of treating both problems jointly.

Acknowledgments

This research has been partially funded by the Spanish Research Department (CI-
CYT's ITEM project TIC96-1243-C03-02), by the EU Commission (EuroWordNet
and by the Catalan Research Department (CIRIT's quality research group
1995SGR 00566).
A MACHINE LEARNING APPROACH TO POS TAGGING 31


Appendix

A
We list below a description of the Penn Treebank tag set, used for tagging the wsj
corpus. For a complete description of the corpus see (Marcus et al. 1993).
CC Coordinating conjunction
CD Cardinal number
DT Determiner
EX Existential there
FW Foreign word
IN Preposition
JJ Adjective
JJR Adjective, comparative
JJS Adjective, superlative
LS List item marker
MD Modal
NN Noun, singular
NNP Proper noun, singular
NNS Noun, plural
NNPS Proper noun, plural
POS Possessive ending
PRP Personal pronoun
Possessive pronoun
RB Adverb
RBR Adverb, comparative
RBS Adverb, superlative
RP Particle
TO to
UH Interjection
VB Verb, base form
VBD Verb, past tense
VBN Verb, past participle
VBP Verb, non-3rd ps. sing.
present
VBZ Verb, 3rd ps. sing.
present
WDT wh-determiner
WP wh-pronoun
WP$ Possessive wh-pronoun
WRB wh-adverb
. End of sentence
, Comma
" Straight double quote
' Left open single quote
" Left open double quote
' Right close single quote
" Right close double quote
Notes
1. The size of tag sets differ greatly from one domain to another. Depending on the contents,
complexity and level of annotation they move from 30-40 to several hundred different tags. Of
course, these differences have important effects in the performance rates reported by different
systems and imply difficulties when comparing them. See (Krenn & Samuelsson 1996) for a
more detailed discussion on this issue.
2. Nevertheless, recent studies on tagger evaluation and comparison (Padr'o and M'arquez 1998)
show that the noise in test corpora -as is the case of wsj- may significantly distort the
evaluation and comparison of tagger accuracies, and may invalidate even an improvement such
as the one reported here when the test conditions of both taggers are not exactly the same.



--R

Boltzmann machines and their applications.

An inequality and associated maximization technique in statistical estimation for probabilistic functions of a Markov process.
Classification and Regression Trees.

Unsupervised Learning of Disambiguation Rules for Part-of-speech Tagging
Domain Specific Knowledge Acquisition for Conceptual Sentence Analysis.
PhD Thesis

and Turmo J.
Tagging French - comparing a statistical and a constraint-based method
A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text.

Elements of Information Theory.
A Practical Part-of-Speech Tagger
Grammatical Category Disambiguation by Statistical Optimization.

MTB: A Memory-Based Part-of-Speech Tagger Generator
The Computational Analysis of English.
Automatic Grammatical Tagging of English.
Constraint Grammar.
Estimating Attributes: Analysis and Extensions of RELIEF.
The Linguist's Guide to Statistics.
Constraint Satisfaction as Global Optimization.
An Optimization-based Heuristic for Maximal Constraint Satisfaction
An optimization approach to relaxation labelling algorithms.


Learning Grammatical Structure Using Statistical Decision-Trees
Building a Large Annotated Corpus of English: The Penn Treebank.
Towards Learning a Constraint Grammar from Annotated Corpora Using Decision Trees.
A Flexible POS Tagger Using an Automatically Acquired Language Model.



Some Experiments on the Automatic Acquisition of a Language Model for POS Tagging Using Decision Trees.
Using Decision Trees for Coreference Resolution.
Tagging English Text with a Probabilistic Model.
Comparative Experiments on Disambiguating Word Senses: An Illustration of the Role of Bias in Machine Learning.
Corpus Linguistic and the automatic analysis of English.
A Hybrid Environment for Syntax-Semantic Tagging
Llenguatges i Sistemes Inform'atics
On the Evaluation and Comparison of Taggers: the Effect of Noise in Testing Corpora.
Learning Compatibility Coefficients for Relaxation Labeling Processes.
Using Simulated Annealing to Train Relaxation Labelling Processes.
Induction of Decision Trees.

A Simple Introduction to Maximum Entropy Models for Natural Language Processing.
On the accuracy of pixel relaxation labelling.
Models.
Maximum Entropy Modeling for Natural Language.
Scene labelling by relaxation operations.
Adaptive Statistical Language Modeling: A Maximum Entropy Approach.
PhD Thesis.
Inducing Constraint Grammars.
Comparing a Linguistic and a Stochastic Tagger.
Aggregate and mixed-order Markov models for statistical language processing

Probabilistic Part-of-Speech Tagging Using Decision Trees
Relaxation Methods in Engineering Science.
Relaxation and Neural Learning: Points of Convergence and Divergence.
Journal of Parallel and Distributed Computing 6
Three Studies of Grammar-Based Surface Parsing on Unrestricted English Text
Developing a Hybrid NP Parser.
Understanding line drawings of scenes with shadows: Psychology of Computer Vision.
Combining Independent Knowledge Sources for Word Sense Disambiguation.
A Statistical-Heuristic Feature Selection Criterion for Decision Tree Induction
Contributing Authors Llu'is M'arquez
--TR

--CTR
Wenjie Li , Kam-Fai Wong , Guihong Cao , Chunfa Yuan, Applying machine learning to Chinese temporal relation resolution, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, p.582-es, July 21-26, 2004, Barcelona, Spain
Ferran Pla , Antonio Molina, Improving part-of-speech tagging using lexicalized HMMs, Natural Language Engineering, v.10 n.2, p.167-189, June 2004
decision trees induction;part of speech tagging;constraint satisfaction;corpus-based and statistical language modeling;relaxation labeling