\documentstyle[epsf,nlpbbl]{jnlp_e_b5_nodagger}

\setcounter{page}{3}
\setcounter{巻数}{5}
\setcounter{号数}{1}
\setcounter{年}{1998}
\setcounter{月}{1}
\受付{February}{4}{1997}
\再受付{May}{1}{1997}
\再々受付{July}{9}{1997}
\採録{July}{18}{1997}

\setcounter{secnumdepth}{2}

\title{}
\author{}
\jkeywords{}

\etitle{Reinventing Part--Of--Speech Tagging}

\eauthor{
	Ezra Black   \and
	Stephen Eubank   \and
	Hideki Kashioka   \and
	David Magerman   \and
	Jared Saia  \and
	Akira Ushioda}

\headauthor{Black,~E.~et~al.}
\headtitle{Reinventing Part--Of--Speech Tagging}

\affilabel{ATRITL}
          {Ezra Black, ATR Interpreting Telecommunications Laboratories, Japan}
          {Ezra Black, ATR Interpreting Telecommunications Laboratories, Japan}
\affilabel{LosNatinal}
          {Stephen Eubank, Los Alamos National Laboratory, US}
          {Stephen Eubank, Los Alamos National Laboratory, US}
\affilabel{ATRITL2}
          {Hideki Kashioka, ATR Interpreting Telecommunications Laboratories, Japan}
          {Hideki Kashioka, ATR Interpreting Telecommunications Laboratories, Japan}
\affilabel{Renaissance}
	{David Magerman, Renaissance Technologies Corp., US}
	{David Magerman, Renaissance Technologies Corp., US}
\affilabel{U_newMexico}
	{Jared Saia, Dept. Of Computer Science, University Of New Mexico, US}
	{Jared Saia, Dept. Of Computer Science, University Of New Mexico, US}

\affilabel{Fujitsu}
	{Akira Ushioda, Fujitsu Laboratories Ltd, Japan}
	{Akira Ushioda, Fujitsu Laboratories Ltd, Japan}


\eabstract{
Part--of--speech tagging methodology has succeeded, 
but on problems that may lack real--world application. Redirection of
the field is indicated, toward potentially more useful, but harder and
more sophisticated tagging tasks: (1) using much more detailed tagsets
(semantically {\em and} syntactically); (2) testing performance on
treebanks reflecting the huge gamut of domains, etc., characterizing
real--world applications; (3) understanding the magnitude of the
unknown--word and unknown--tag problems, then overcoming them.
Tagging results are presented on two versions of a new, highly
variegated treebank, featuring tagsets of 2720 and 443 tags,
respectively, and utilizing a dictionaryless, decision--tree tagger.}

\ekeywords{corpus--based language modeling; part--of--speech tagging}

\begin{document}

\maketitle

\section{Introduction: Building On The Successes To Date In Part--Of--Speech Tagging}

{\em Part--of--speech tagging}---using computers to automatically
associate the words of a text with\hspace{-0.2mm} their\hspace{-0.2mm}
grammatical\hspace{-0.2mm} parts\hspace{-0.2mm} of\hspace{-0.2mm}
speech---has\hspace{-0.2mm} been\hspace{-0.2mm} one\hspace{-0.2mm}
of\hspace{-0.2mm} the\hspace{-0.2mm} success\hspace{-0.2mm}
stories\hspace{-0.2mm} of\hspace{-0.2mm} the\hspace{-0.2mm}
Natural\hspace{-0.2mm} Language
Processing field to date. Computers have equalled human accuracy at
tagging the Wall Street Journal, Brown Corpus, Associated Press, and
Canadian Hansard
corpora\cite{Brill:advances,Weischedel+al:class,Merialdo:tagging,Black+al:tag,Marcus+al:class,Kucera+Francis:KF,Garside+McEnery:GM},
using the rudimentary, 45--tag UPenn
Tagset\cite{Marcus+al:class}, and stripped--down versions
of the fuller CLAWS
tagset\cite{Eyes+Leech:EL,Garside+al:comp,Garside+McEnery:GM}.

But what will the ability to tag with these relatively low--level
tagsets do for complex applications such as machine translation,
sophisticated document--searching, and open--vocabulary speech
recognition? The logical next move for part--of--speech tagging is to
build on its successes and undertake more complex and challenging
tagging tasks.

Three directions for expansion seem indicated: (1) tag using much
more detailed tagsets, including a large-scale semantic classification
as well as more syntactic detail; (2) test performance on treebanks
which reflect the huge gamut of domains, styles, functions, and usages
found among real--world applications; and (3) understand the
magnitude of the unknown--word and unknown--tag problems, then overcome
them.

One way to confront all these problems is to tag using the 700,000--word
{\em ATR/Lancaster Treebank of American English}
\cite{Black+al:treebank}.  Divided into roughly 950 documents of
length 30--3600 words, this treebank achieves a high degree of
document variation along many different scales---document length,
subject area, style, point of view, etc. (See Table 1 for titles of
nine typical documents.) Text is tagged and parsed using the {\em ATR
English Grammar} (2720 different tags). Each verb, noun, adjective and
adverb tag includes one of about 60 semantic categories intended for
any Standard American English text in any domain. Even the
syntax--only version of the tagset has 443 different tags. (Compare
45, 76, and 163 tags for the tagsets used in
\cite{Brill:advances,Weischedel+al:class,Merialdo:tagging,Black+al:tag}.)
The unknown--word and unknown--tag problems\footnote{viz., the word to
be tagged (a) has never been encountered in the training corpus
(unknown--word); or (b) is in the training corpus, but not with the
tag which it needs to be assigned in the case at hand (unknown--tag)}
are quantified below and turn out to be much more severe than one
might have thought. Unknown--tag difficulties are sufficiently acute
in ATR/Lancaster--Treebank test sets to form a spur to solving the
problem.

\begin{table}
\begin{center}
\caption{Nine Typical Documents From ATR/Lancaster Treebank}
\renewcommand{\arraystretch}{}
\begin{tabular}{|l|}
\hline
Empire Szechuan Flier (Chinese take--out food) \\
Catalog of Guitar Dealer \\
UN Charter: Chapters 1--5 \\
Airplane Exit--Row Seating: Passenger Information Sheet \\
Bicycles: How To Trackstand \\
Government: US Goals at G7 \\
Shoe Store Sale Flier \\
Hair--Loss Remedy Brochure \\
Cancer: Ewing's Sarcoma Patient Information \\
\hline
\end{tabular}
\renewcommand{\arraystretch}{}
\end{center}
\end{table}

\section{Real--World Part--Of--Speech Tagging}

In Section 2, we document the problems of tagging with larger, more
sophisticated tagsets (2.1), and of tagging unknown words and words
occurring with a given tag for the first time in test data (2.2), and
show why it is important to solve these problems. Section 3 describes
the solution we are attempting, using decision--tree modelling and
discarding the notion of a dictionary entirely (3.1); and presents
experimental results and future research plans (3.2).

\subsection{Tag Using Tagsets Of Increased Size And Complexity}

This subsection seeks to convey a ``feel'' for the increasing levels
of detail of the tagsets utilized so far in tagging work---including
the new ATR tagsets. Then, specific cases are discussed of syntactic
details captured in the ATR tagset but not in tagsets used for prior
tagging experiments, and it is shown why these details matter.

\subsubsection{Exemplifying The Tagsets Used So Far}

Tables 2 display a portion of a 1989 Wall Street Journal
article entitled, ``Enserch Tender Offer Results'', tagged using first
the full 2720--tag ATR tagset ({\em ATR--Full}); then the 443--tag
syntax--only version of the ATR tagset ({\em ATR--Syntax}); then the
163--tag mapped--down version of the CLAWS tagset which was used in
\cite{Black+al:tag}; then finally the 45--tag UPenn tagset used in
\cite{Brill:advances}.

(See appendix for glosses of ATR--Full, ATR--Syntax, mapped--down CLAWS,
and UPenn tagged versions.)

\begin{table}
 \caption{Portion of WSJ Article ``Enserch Tender Offer Results'',\\
 Tagged Using ATR--Full,ATR--Syntax, Mapped--Down CLAWS, And UPenn Tagsets.\\
 Within ``ATR'' column, portions of a tag present in ATR--Full but not ATR--Syntax\\
 are parenthesized. \\
 Note tokenization (word--splitting) differences between ATR, CLAWS on one hand,\\
 and UPenn on other: 99\% and \$1 are one word for
 the former tagsets, two words\\
 for the latter.}

 \begin{center}
 \begin{minipage}{0.53\textwidth}
  \small
  \setlength{\tabcolsep}{0.5mm}
  \renewcommand{\arraystretch}{}
  \begin{tabular}{|l||l|l|l|} \hline
   WORD	& ATR			& Lanc 	& Upenn \\ \hline
   Enserch	& NP1(FRMNM)		& NP1 &  NNP \\
   said	& VVD(VERBAL-ACTSD)	& VVD &  VBD \\
   the	& AT			& AT  &  DT  \\
   tendered & JJVVN(INTER-ACT)	& JJ  &  VBN \\
   units	& NN2(ABS-UNIT)		& NN2 &  NNS \\
   will	& VMPRES		& VM  &  MD  \\
   raise	& VVI(ALTER)		& VVI &  VB  \\
   its	& APP\$			& APP\$ &  PRP\$\\
   ownership & NN1(PERS-ATT)	& NN1 &  NN  \\
   of	& II(OF)		& IO  &  IN  \\
   the	& AT			& AT  &  DT  \\
   partnership& NN1(SYSTEM-PT)	& NN1 &  NN  \\
   to	& II(TO)		& II  &  TO  \\
   more	& DAR			& DAR &  JJR \\
   than	& CSN			& CSN &  IN  \\
   99	&			&     &  CD  \\	
   \%	& NNUNUM		& NNU &  NN  \\
   from	& II(FROM)		& II  &  IN  \\
   87	&			&     &  CD  \\
   \%	& NNUNUM		& NNU &  NN  \\
   About	& RR(DEGREE)		& RG  &  RB \\
   900,000	& MC			& MC  &  CD \\
   units	& NN2(ABS-UNIT)		& NN2 &  NNS\\
   will	& VMPRES		& VM  &  MD \\
   continue & VVI(PROCESSIVE)	& VVI &  VB \\
   to	& TO			& TO  &  TO \\
   be	& VBI			& VBI &  VB \\
   publicly & RR(INTER-ACT)	& RR  &  RB \\
   traded	& VVN(INTER-ACT)	& VVN &  VBN\\
   on	& II(ON)		& II  &  IN \\
   the	& AT			& AT  &  DT \\
   New	& NP1(PREPLCNM)		& NP1 &  NNP\\
   York	& NP1(CITYNM)		& NP1 &  NNP\\
   Stock	& NN1(MONEY)		& NN1 &  NNP\\
   Exchange & NP1(INSTIT)		& NNL1&  NNP\\
   ,	& ,			& ,   &  ,  \\
   Enserch	& NP1(FRMNM)		& NP1 &  NNP\\
   said	& VVD(SAYING)		& VVD &  VBD\\
   .	& .			& .   &  .  \\ \hline
  \end{tabular}
 \renewcommand{\arraystretch}{}
 \end{minipage}
  \end{center}

\end{table}



\subsubsection{Expanded Syntactic Detail: The ATR--Syntax Tagset}

The ATR--Syntax tagset is a revised and expanded version of the CLAWS
tagset. Three areas of ATR--Syntax's increased syntactic detail
vis--a--vis previously--utilized tagsets are now discussed.

\paragraph{{\em\bf Ditto Tags} For Multiword Lexical Units}


The CLAWS tagset features so--called {\em ditto tags} for multiword
lexical units. For instance, ``well\_NN121 being\_NN122'' is a two--word
noun, ``in\_II31 response\_II32 to\_II33'' a three-word
preposition.\footnote{Obviously, only appropriate occurrences of these
word sequences are tagged as above.  E.g., ``He nodded in response to
indicate he was listening'' would not be so tagged.} Many more ditto
tags are contained in ATR--Syntax than in CLAWS, with 276 of the 443
ATR--Syntax tags being ditto tags.\footnote{Since this leaves only 167
tags, it might be thought that apart from ditto tags, the CLAWS and
ATR--Syntax tagsets are the same. This is far from true, however,
since 39 of these 167 non--ditto ATR--Syntax tags are absent from the
CLAWS tagsets, and 51 of the 179 tags of the CLAWS2a tagset, for
instance, \cite{Eyes+Leech:EL}, do not figure in the ATR--Syntax
tagset. Broad discussion of these differences is beyond the scope of
this article, but two important cases will be dealt with in the next
two subsections.}


All CLAWS ditto tags are mapped out of both the
\cite{Merialdo:tagging} and
\cite{Black+al:tag} experiments, so that no published experiments have appeared to date
with tagsets featuring ditto tags. In \cite{Black+al:tag}, the ``ditto
endings'' are dropped, so that e.g. ``well\_NN121 being\_NN122'' becomes
``well\_NN1 being\_NN1''. It is not clear how ditto tags were handled in
\cite{Merialdo:tagging}; in any case, the full mapped--down
76--tag tagset is exhibited in \cite{Merialdo:tagging}, and no ditto
tags are included.

What is the advantage of marking certain multiword lexical units, and
why is it more useful to have explicit ditto tags than mapped--down
ones as in \cite{Black+al:tag}? One answer concerns what happens when
one runs a parser\footnote{a device for automatically diagramming
sentences} on tagged text. Briefly, tagging e.g. ``in\_II31
response\_II32 to\_II33'', tells the parser to treat the three words as
a single preposition, and so to ignore possible breakdowns like: ``He
nodded (in response) (to show he was following)'', of the the
sentence containing the phrase when so tagged. This can turn out to be
a significant aid to parsing accuracy, if ditto tags appear frequently
in correctly--tagged text, since large numbers of mistaken parses are
eliminated which might otherwise be considered correct by the parser.

Dropping the ``ditto'' sequence markers, i.e. mapping the above 
to ``in\_II response\_II to\_II'', as was done in \cite{Black+al:tag},
goes part--way towards the above goal, in that it prevents
parsing mistakes like the one above. But it does nothing to block
errors such as partitioning the phrase, ``the comments he made
in response to this question'' as if it were of the form, ``the
options he chose from among (in this case)'' or, ``the
option he chose from (among (in this case) five possibilities)'', etc.

An extremely frequent and potentially havoc--wreaking ditto--tag
scenario occurs where a multiword adverb occurs at the end of a
sentence, especially a long sentence. Locutions like, ``as\_RR21
well\_RR21'', ``a\_RR21 lot\_RR22'', ``by\_RR31 and\_RR32
large\_RR33'' are common in this position. If we denature the ditto
tags into a series of two or three adverbs, the number of
otherwise--preventable spurious parses now open to an unsuspecting
parser can be huge. Even among short sentences there are many
variations: He (paid (\$5000 precisely) (wholly willingly)); (He (paid
(\$5000 precisely) unhesitatingly) sometimes); (He (spent money
(terribly freely)) always); etc.

\paragraph{Digit--Based And Number--Word--Based Lexical Units: Price, Time, Etc.}

Among the 276 ditto tags in the ATR tagset, 170 are for digit--based
or number--word--based lexical units, e.g. MPRICE31, MTIMEWORD22,
MZIP21. In addition, the set of standard (non--ditto--tag) ATR tags
contains 21 other tags for single--word lexical units of this type. 
All 191 of these tags are identical for the ATR--Full and ATR--Syntax
tagsets. That is, in both, a full panoply of tags for prices, times,
zipcodes, and the like, is included, along with a variety of tags for
``just plain numbers'', e.g. ``fifty\_MCWORD21 three\_MCWORD22'', ``1\_MC1'',
``next\_MDWORD'', ``325--92\_MC-MC'' (e.g. a 325--92 vote). The rationale here
is that it is feasible for a tagger to learn to demarcate
multiword price, time, zipcode, etc., expressions, and that specifying
the internal structure of these expressions is probably of lesser
utility in general. What {\em is} quite important is to locate the
boundaries of these wordstrings, which often include highly frequent
words which if not rendered harmless in this fashion, might encourage
significant numbers of misparses. For instance, the ``a'' of ``a
hundred fifty'', the ``the'' of ``Tuesday the 19th'', and the ``bits''
of ``two bits'',\footnote{American slang for 25 cents} need to be
identified as occurring inside numerical lexical items, if they are
not to sow confusion.

Are these tags ``syntactic''? Merely to pose this question suggests a
need for at least ten years of ``Wittgensteinian therapy''. If anyone
wishes, we can change the name ``ATR--Syntax tagset'' to
``ATR--Syntax--With--Some--Semantics tagset''. The point about
numbers, prices, times, etc., is that in many kinds of document, they
are devilishly {\em frequent}. Hence one could conceive of uses for a
tagger which accurately assigns this class of tag, within applications
such as document scanning and information retrieval, among other
places.

\paragraph{Verbal vs. Ordinary Adjectives And Nouns}

Arguably a problem with the tagsets which have been used so far in
large--scale tagging experiments, has been the lack of an adequate
treatment of {\em verbal} (as opposed to {\em ordinary}) {\em
adjectives} and {\em nouns} (forms 1,5,9 of Table 3; contrast forms
2,6,10).\footnote{Terminology of \cite{Kruisinga:handbook}. 
\cite{Long:sentence} uses {\em participial adjectives} and {\em gerundial
nouns} vs. {\em adjectives}, {\em nouns}.} CLAWS conflates forms 1 and
2; 5 and 6; and 9 and 10. UPenn conflates 5 and 6. It assigns two
different tags to 1 and 2, and to 9 and 10; however, the tag chosen
for 1 is also the tag for 3,4,7,8; and the tag chosen for 9 is also
the tag for 11 and 12.  In contrast, the ATR tagsets feature different
tags for cases 1 and 2; 5 and 6; and 9 and 10; the tag for case 1
differs from all of tags 2--12; and the tag for case 9 differs from
all other cases 1--12.


\begin{table}
\begin{center}
\caption{Tagging Verbal Adjectives and Nouns With ATR, CLAWS and UPenn Tagsets}
\renewcommand{\arraystretch}{}
\begin{tabular}{|l||l|l|l|} \hline
-ing/-ed Form & ATR			& CLAWS 	& UPENN \\ \hline
(1) The {\em sleeping} baby	& JJVVG	& JJ   &  VBG  \\
(2) An {\em interesting} idea & JJ	& JJ   &  JJ  \\
(3) Ed is {\em running} away & VVG	& VVG   &  VBG  \\
(4) The man {\em running} away & VVG	& VVG   &  VBG  \\
(5) A {\em sleeping} pill  & NVVG	& NN1   &  NN  \\
(6) He makes a good {\em living} & NN1	& NN1   &  NN  \\
(7) {\em Finding} gold is hard & VVG	& VVG   &  VBG  \\
(8) {\em Speaking} softly helps & VVG	& VVG   &  VBG  \\ 
(9) The {\em offered} amendment	& JJVVN	& JJ   &  VBN  \\
(10) A {\em forced} smile & JJ	& JJ   &  JJ  \\
(11) Ed has {\em sold} his farm & VVN	& VVN   &  VBN  \\
(12) The man {\em given} \$5 & VVN	& VVN   &  VBN  \\ \hline
\end{tabular}
\renewcommand{\arraystretch}{}
\end{center}
\end{table}


Thus ATR can, but the other tagsets cannot, distinguish between ``of a
retiring\_JJVVG employee'' and ``of a retiring\_JJ nature''; between
``a forced\_JJVVN march'' and ``a forced\_JJ smile'';\footnote{Again,
the UPenn tagset does make these two distinctions, but then throws
away their utility by using for case 1 the same tag as for cases
3,4,7,8, and for case 9 the same tags as for cases 11, 12, causing
much potential confusion to a parser, e.g. with the Chomskian chestnut
quoted below.} and between ``Hog calling\_NVVG is a dying art'' and
``Bill has found his calling\_NN1''. Further, both senses of Chomsky's
sentence ``Flying planes can be dangerous'' receive the same tagging
by UPenn, but not by ATR (nor by CLAWS).


Further, UPenn tags identically all {\em three} senses of
e.g. ``Singing lessons can be fun.'' In practice, the UPenn WSJ
Treebank apparently fails to consistently capture any patterns over 
-ed and -ing adjectives and nouns. There is only mild correspondance
between the tagging decisions prescribed for these forms in the UPenn
Tagging Guidelines (1995 edition; contact
sparnum@unagi.cis.upenn.edu), and
those actually made in the WSJ
Treebank. What \mbox{results} is relatively
patternless labelling.  For
instance, in a 14,900--word sample of latest--version (2.00) WSJ
Treebank, taken from three widely separated places in the corpus, only
93 of 159 -ed and -ing adjectives and nouns (58\%) were correctly
labelled with respect to the Tagging Guidelines.

Why does this matter? One place it matters is in machine translation. 
It makes sense that cases 1 and 9 should be translated differently
from cases 2 and 10, since the former can be thought of as reflecting
``regular lexical processes'', whereas the latter are the result of
``lexicalization'', hence highly idiosyncratic. It would be absurd, in
a process as complex as translation, to claim that ``form $x$ in English
is translated via form $y$ in French''. But what we do find is a
tendency to translate the two forms using a different gamut of
structures.

Informant work in French, Japanese, and Korean suggests a tendency to
translate case--1 forms (JJVVGs) via participles, and case--2 forms
(JJs ending in --ing, often ``lexicalized'') with adjectives. Further,
one author conducted an informal test using the 1986 Canadian Hansard
French/English database,\footnote{supplied by the Linguistic Data
Consortium (sparnum@unagi.cis.upenn.edu)} in which 10 JJVVGs
and 10 JJs ending in -ing were selected at random from the ATR
Treebank. The first ``adjectival'' occurrence of each of these words
in the 1986 Hansards was located, along with its French translation.
The structural types of the translations were noted and tabulated.
The ``translation profile'' which emerged of the -ing--form JJs was
very different from that of the JJVVGs. Whereas in 4 cases, the JJs
were translated via unambiguous adjectives, this never occurred for
the JJVVGs. In both cases, 3 words were translated via present
participles (-ing forms); but other than that, the entire profile was
totally different for the two cases.



\subsection{Confront The Unknown--Word And --Tag Problems}

We know of no attempts to date to quantify the unknown--word and
unknown--tag problems (viz., the word to be tagged (a) has never been
encountered in the training corpus (unknown--word); or (b) is in the
training corpus, but not with the tag which it needs to be assigned in
the case at hand (unknown--tag).)


\begin{table}
\begin{center}
\caption{Mutual Coverage Statistics For ATR and UPenn Treebanks}
\renewcommand{\arraystretch}{}
\begin{tabular}{|l|l|l|l|l|}
\hline
Covering Database    & Covered Database   & Category of Coverage & Coverage  \\ \hline
UPenn WSJ Treebank   & ATR Treebank       & wordlist             & 75\%      \\ \cline{1-2} \cline{4-4}
ATR Treebank         & UPenn WSJ Treebank &                      & 75\%      \\ \hline
UPenn WSJ Treebank   & ATR Treebank       & running words        & 94\%      \\ \cline{1-2} \cline{4-4}
ATR Treebank         & UPenn WSJ Treebank &                      & 94\%      \\ \hline
UPenn WSJ Treebank   & ATR Treebank       & sentences            & 69\%      \\ \cline{1-2} \cline{4-4}
CUVOALD92 Dictionary & ATR Treebank       &                      & 60\%      \\ \cline{1-2} \cline{4-4}
CUVOALD92 Dictionary & ATR Treebank       &                      & 80\%      \\ 
+ UPenn WSJ Treebank &                    &                      &           \\ \hline
\end{tabular}
\renewcommand{\arraystretch}{}
\end{center}
\end{table}

Table 4 shows the findings of a detailed exploration of the
unknown--word problem involving the ATR Treebank and the UPenn WSJ
Treebank. It just happens that the UPenn WSJ and ATR vocabularies each
have 75\% coverage of the other. (I.e. 75\% of the different words
({\em types}) occurring in ATR figure on the list of types occurring
in the UPenn WSJ Treebank.) We took great care to make the comparison
as meaningful as possible, by (a) mapping all words to lowercase
before comparing the two wordlists; (b) omitting consideration of
plain numbers and digit sequences, digit--based words except
meaningful ones like 9--foot, ``non--words'' of many stripes (e.g. 
black@itl.atr.co.jp, hellooooooo); and (c) compensating for any
``tokenization'' differences between the two treebanks (e.g. UPenn
converts ``\$500'' into ``\$ 500'', while ATR leaves it as is). Still,
for various reasons, we can only guarantee the first two figures cited
to within 5\%.

We were even more careful in calculating the coverage for running
words.  I.e. what percent of all the word occurrences ({\em tokens})
in the UPenn WSJ Treebank (over 1 million) figure on the list of types
in the ATR Treebank? And vice--versa. Here our answer, 94\%, is
estimated to within 1\%. And here again, it just happened that the
same answer applied in both directions.  Thus, if one selects a word
at random from, say, the UPenn WSJ Treebank, the chances are 94 in 100
that it is in the list of words occurring in the ATR Treebank.

So far, the unknown--word problem may appear fairly harmless. However,
a further finding remains. We calculated the distribution of unknown
words among sentences in the ATR Treebank. I.e. we calculated the
percentage of ATR--Treebank sentences within which one or more words
are unknown to the UPenn WSJ Treebank.  (To ensure that the
non--covered words were ``real words'', we also removed from
consideration in this test all last names and names of cities. This
represents a decision that e.g. ``Martin'' and ``Nevada'' are
``words'', whereas, say, ``Hogsbristle'' and ``Oshkosh'' are not.) 
That percentage, estimated to within 1\%, was 69\%! That is, about 3
of every 10 ATR--Treebank sentences are not ``covered'' by the UPenn
WSJ Treebank! This suggests that in real--world tagging, the
unknown--word problem is a serious one.

Further, we tested the coverage provided by a ``dictionary'', in a
more conventional sense of the term than the one often used in tagging
research.\footnote{viz., a list of all words in some tagged corpus,
and the tags with which each word is associated once or more} That is,
we tested the sentence--wise coverage of the ATR Treebank, by the
CUVOALD92 Dictionary,\footnote{produced by Roger Mitton; available
from: ftp://black.ox.ac.uk/ota/dicts/710} an expanded,
computer--usable version, containing inflected forms, etc., of the
Oxford Advanced Learner's Dictionary Of Current English\footnote{Third
Edition, Oxford University Press, 1974.} Again we omitted all last and
city names, and again we verified carefully that only ``real words''
were counted in the comparison process.  Results were that 60\% of
ATR--Treebank sentences were covered by CUVOALD92. Finally, even when
we used both the UPenn--WSJ Treebank and the CUVOALD92 Dictionary,
coverage of ATR--Treebank sentences was still only 80\%. One in five
sentences is not covered using this ``dictionary''.


\begin{figure}
\begin{center}
\epsfile{file=kashioka1.eps,width=3.0in}
\end{center}
\caption{Percentage of sentences in ATR and UPenn test corpora\\
with one or more unknown words or with one or more words\\
having tags not used in the training set,\\
as a function of training--set vocabulary size.\\
Words consisting entirely of digits or punctuation are ignored.\\
ATR training set, thus purged, contains 331,770 running words\\
and a vocabulary of 33,946; UPenn, 885,010 and 51,064, respectively.
\label{unknowns}}
\vspace{3mm}
\end{figure}
 

We have carried out a similar analysis of the unknown--tag problem;
our results are shown in Figure 1, which shows the percentage of
sentences in the ATR and UPenn test corpora with one or more
words having tags not used in the training set, as a function of
training--set vocabulary size.\footnote{The percentage of sentences in
the ATR and UPenn test corpora with one or more unknown words is also
shown in Figure 1.} The incidence of this phenomenon is non--trivial
even for the UPenn WSJ Treebank; about a fifth of ATR Syntax test
sentences contain one or more unknown tags, and the firgure is almost
half for ATR Full.


\section{The Non--Dictionary}

We have attempted to tag using a more--detailed tagset, on a
comprehensive treebank, and to confront the unknown--word and
unknown--tag issues. What tools did we use, and how far did we get?

We call our approach the Non--Dictionary, or dictionaryless
tagger. Our tagger does not use a ``dictionary'' in the sense of a
list of all words in a training corpus, together with the various tags
with which each word of the training corpus is associated once or
more. Nor does it use an online dictionary, such as CUVOALD2 (see 2.2)
or of any other sort.

Why throw away the dictionary? Given the magnitude of the
unknown--word and unknown--tag problems, well--developed means are
necessary {\em anyway} of dealing with these cases of dictionary
failure. More generally, the wider--ranging the treebank being tagged,
and the larger and more detailed the tagset employed, the more
quixotic it is to think that the universe of tags can be listed for a
given word: ``pumpkin'' becomes an adjective when it is listed as the
color of a sweater in the L.L. Bean catalog; ``The'' and ``An'' turn
out to be first names in a text discussing the teaching of English As
A Second Language in Southeast Asia; ``As'' shows up as a plural
proper noun, on the sports page, as the name of a baseball team. It
does not follow that the dictionary is a hindrance; but by pushing a
dictionaryless approach as far as possible, we can concentrate on
unknown--word and --tag issues, and later factor in a dictionary if we
wish.


So, we in effect consider every word for tagging to be an unknown
word. Instead of asking which tags have been seen for the word being
tagged---in our training set, in an online dictionary, or in either
place---we ask about: parts of words (sometimes formal affixes,
sometimes not); certain ``whole words''; the words surrounding the
word being tagged; characteristics of the overall sentence; tags (or
features of tags) which the tagger has already assigned; etc.  We
attempt to capture ``trends'' in a tagged treebank, trends which have
to do with groups of words but which are much more varied and 
subtle than the tendency of specific part-of--speech trigrams to
occur, or of a given word to have been tagged a certain way a certain
percent of the time.\footnote{as is relied upon in e.g.
\cite{Merialdo:tagging}} \cite{Brill:advances,Black+al:tag} exploit 
somewhat similar trends, but, in the first case, a different modeling
approach is used, and in the second case, while a similar model to
ours is used, crucially, (a) a dictionary is employed, (b) only
self--organized questions are asked of the data (see below), and (c) a
simpler tagset (mapped--down CLAWS) is employed.
 
So far the questions we have utilized are mainly aimed at doing
syntactic tagging. We are at work, however, on many additional
questions for use in syntactic--plus--semantic tagging. We generate
questions both by hand and via self--organized methods, and we apply
these questions to our training data by means of statistical decision
trees. The outcome of the tagging process is essentially a probability
distribution for each tag sequence for a sentence, over all tags in
the tagset.


\subsection{The Model}

\subsubsection{Mutuatl Information (MI) Bits}
\label{questions}

In addition to asking about affixes, capitalization, etc. of words in
isolation, we can ask whether a given word is a member of a particular
class of words.\footnote{In asking both manually--created and
self--organized questions, we follow \cite{Magerman:thesis}.} We
define word classes using the self--organizing approach of
\cite{Brown+al:class}---automatic clustering on large, untagged
corpora, in this case 20,000,000 words of Wall--Street--Journal text.
We assign each of the 70,000 most frequent words in this
database to its own class, then iteratively merge the two classes
which are most often used in similar situations.  Specifically, 
if $c_i$ represents the $i$th class, the mutual information
of class bigram pairs is:
\begin{equation}
I \equiv \sum_{c_1,c_2} p(c_1,c_2) \log \frac{p(c_1,c_2)}{p(c_1)p(c_2)}.
\end{equation}
We find the pair of classes whose merger into a single class will least
decrease the mutual information \cite{Ushioda96}.
By keeping track of the order in which
classes are merged, we can define a binary tree which spans all levels
of detail from one class per word to a single class for all words.
The binary tree is equivalent to a set whose element is a pair
of a word and the corresponding bit string.
This bits string for each word is called MI bits.
When these classes are utilized for constructing a decision--tree
tagging model (see below), the decision tree can determine what level
of detail to exploit.  

If we were to rely {\em only} or even mostly on word classes, whether
self--organized or manually--created, and, crucially, if there were
also a transparent relationship between word--class membership and tag
assignment, then our approach would be rightfully accused of utilizing
an inverse dictionary. However, it is not the case that information
exclusively involving word classes does most of the work in our
approach. And it is also not the case that there is any direct linkup,
in many cases, between the membership of a word in one of our classes,
and any particular tag or set of tags. Therefore, we are not employing
a dictionary in a disguised manner, as might perhaps be thought prima
facie.

\subsubsection{Decision Trees}

Decision trees are a formalization of the game of ``20 questions''
\cite{CART,Black+al:tag}.  The model consists of a tree--structured set
of questions, with a probability distribution associated with each
leaf of the tree. To estimate a conditional distribution using the
tree, follow a path from the root to a leaf based on answers to the
questions at each node. The leaf's associated distribution is the
estimator.  Training a decision tree model requires two steps: first,
picking a question to ask at each node; and second, determining a
probability distribution for each leaf, using the distribution of
events in the training set which reach each node.  As discussed in
\cite{Black+al:tag}, at each node we choose from among all possible
questions (that is, all possible bits describing the current word and
its context) that question which maximizes entropy reduction.

To avoid overtraining, we use a type of backoff smoothing to 
estimate probability distributions. If $p(tag | n)$ represents
the sample distribution of tags in the training data which reach
the node $n$, we define the {\em smoothed} probability
$$
\tilde{p}(tag|n) = \lambda_{n} p(tag|n) + 
		 (1-\lambda_{n})\tilde{p}(tag|parent(n)),
$$
which interpolates linearly between the sample distribution at node $n$ 
and the smoothed distribution at $n$'s parent node. The value of
lambda is chosen to optimize performance on a ``smoothing'' data set 
which is distinct from both the training and test sets.

Assigning a tag is a two--stage process. First, a decision tree
assigns one of 20 ``generalized parts--of--speech''\footnote{actually
a value for the feature ``pos'' for the tag, as our tagset is
feature--based; sample values for the feature ``pos'' include: n
(noun), v (verb), cd (subordinating conjunction).} ({\em GPOS's}) to
the word based on a large set of word(--part) and context questions.
Second, a separate decision tree assigns a tag to the word based on an
additional large set of word(--part) and context questions as well as
its predicted GPOS.  In this second stage, there is a separate
decision tree for each GPOS.  Breaking the process up this way allows
us to concentrate on different word characteristics and different
aspects of the context for different classes of tag. In other words,
we use separate models for predicting the details of noun tags, verb
tags, adjective tags, etc.

\subsubsection{The Tagging Process}

Tagging proceeds from left to right, with the goal of maximizing the
joint probability of the tag sequence for the entire sentence. That
is, we find the set of tags $\{\hat{t}_1, \hat{t}_2, ...,
\hat{t}_N\}$, where $\hat{t}_i$ is the predicted tag for the $i$th
word of the $N$ word sentence $w_1\ w_2\ ...\ w_N$, which maximizes
\begin{eqnarray}
P &\equiv& p(\hat{t}_1, \hat{t}_2, ... \hat{t}_N | w_1, w_2, ... w_N) \\
&=&\prod_{i=1}^N p(\hat{t}_i | w_1, ..., w_N, \hat{t}_1, ..., \hat{t}_{i-1})
\end{eqnarray}
Decision trees are used to extract relevant features from the conditions in these distributions.
Note that we have not invoked the Markov assumption here---the predicted tag
for even the last word of the sentence can, in principle, depend on the first word
and its predicted tag.
Whether this dependence in fact shows up in our models depends on 
whether the decision trees find it to be important for the training set.
If we represent the deterministic process of using the answers to context-dependent
questions to find a leaf in the tree as:
\begin{equation}
L_i \equiv leaf\ to\ which\ the\ context\ w_1, ..., w_N, \hat{t}_1, ..., \hat{t}_{i-1}\ leads,
\end{equation}
and the probability distribution associated with leaf $L$ as $\hat{p}_L$,
then the decision trees approximate the required conditional
distributions by
\begin{equation}
p(\hat{t}_i | w_1, ..., w_N, \hat{t}_1, ..., \hat{t}_{i-1}) \approx
\hat{p}_{L_i}(\hat{t}_i)
\end{equation}
and the function our search procedure tries to maximize is,
\begin{equation}
\prod_{i=1}^N \hat{p}_{L_i}(\hat{t}_i) \approx P
\end{equation}
One final technicality is that, as stated in the last subsection, we
split the tagging process into two parts, first assigning a GPOS using
one decision tree, then a tag using a separate decision tree
specialized for the predicted GPOS.  Thus in practice, the GPOS
prediction uses the conditions above, while tag prediction uses these
conditions plus the GPOS predicted for the current word.

When the first word of a sentence is considered, the context consists
of the words and their arrangement in the sentence. The decision tree
predicts the probability of each GPOS for this word in this context. 
Next, for each predicted ``generalized part--of--speech'', the
appropriate decision tree is used to evaluate the probability of each
possible tag.  A search over this space determines the overall ranking
for each tag.  Then, the next word is considered. Relevant questions
now include both the tag-independent questions used for the first word
of the sentence, and questions which depend on the tag of the first
word. For each different tag assigned to the first word, a set of
GPOS's and then a set of tags are predicted. A search over the space
of first--and--second--word tag--pairs determines overall ranking. 
This procedure continues until every word in the sentence has been
tagged.

Our overall choice of the ``best'' tag for each word is intended to
maximize the joint probability of the entire set of tags.  This means
we must evaluate the probability for a set of tag sequences which
grows exponentially with the length of the sentence.  We can either
exhaustively enumerate and score all the cases (which is reasonable
for a small tagset such as UPenn), or use a stack decoder algorithm
\cite{Bahl+al:max,Jelinek:fast,Paul:algorithms} to search through the
most probable candidates (as is necessary for the ATR--Full tagset).

 
\subsubsection{Example Questions}

Here is a sampling of decision--tree questions created by our team
grammarian. Most of them are useful on both tiers of the tagging
process, i.e. tier 1, where GPOS is predicted, as well as in tier 2,
where the rest of the tag is predicted.

Context Questions: (1) For the word being tagged: (a) position within
sentence; (b) quadrant of sentence; (2) Final word of sentence: (a)
question mark; (b) period or exclamation point; (3) Anywhere in
sentence: (a) by (b) than; (4) For word sequences including word being
tagged: (a) Specific ditto--tag words; (b) Any of large list of likely
contexts for particular tag or GPOS; (c) Any of list of likely
contexts for particular word used in particular sense---this for many
words which share a semantic identity.

Word Questions: (asked of all words within two positions of the word
being tagged, plus the word itself): (1) How many letters long (2)
Contains ``at--sign'' (for email addresses, etc.) (3) any kind of
determiner, article, pronoun; (4) ends in probable adjective suffix,
yet not on exception list; (5) adjective in --wide (complex set of
conditions: either the word ``wide''; or word ending in --wide, and
having either a hyperbolic prefix, or a number in digits or words as a
substring); (6) on list of words, signalling start of subject noun
phrase (and not on exception list); (7) has ``time--adverb'' prefix;
(8) contains hyphenated preposition as ``midstring''; (9) on list of
synonyms for ``remember''; (10) contains name of wild animal.


\pagebreak

\subsection{Experimental Results}

\begin{sloppypar}
The\hspace{0.3mm} focus\hspace{0.3mm} of\hspace{0.3mm}
the\hspace{0.3mm} research\hspace{0.3mm} being\hspace{0.3mm}
reported\hspace{0.3mm} her\hspace{0.3mm}e\hspace{0.3mm}
is\hspace{0.3mm} tagging\hspace{0.3mm} with\hspace{0.3mm}
the\hspace{0.3mm} ATR\hspace{0.3mm}
tagsets,\hspace{0.3mm} on\hspace{0.3mm} the ATR/Lancaster Treebank.\hspace{1mm} As a point of reference for
our results, however, we have also tagged the one publicly--available
corpus, the UPenn Wall-Street--Journal Treebank, for which there are
results utilizing various tagging approaches.
\end{sloppypar}


UPenn training and testing sets used consist of random sentences from
the UPenn WSJ Treebank\footnote{Version 0.75;
annotated by the Penn Treebank Project; copyright University of
Pennsylvania} (1,072,755 words of training, 133,293 smoothing, 49,624
testing data).\footnote{ This includes every token that receives a
tag.  Approximately 200,000 of these are punctuation tags.} The
random--document sets consist of randomly--selected documents from the
ATR Treebank (319,903 words of training, 38,667 smoothing, 60,667
testing data).  ATR random--sentence sets consist of
randomly--selected sentences from the ATR Treebank (388,058 words of
training, 43,189 smoothing, 12,150 testing data).  Clearly, the
random--document sets represent a fairer approximation of real--world
tagging tasks.

\begin{figure}
\begin{center}
\epsfile{file=kashioka2.eps,width=3.0in}
\end{center}
\caption{Histograms showing relative frequency of occurrence of words\\
as function of number of distinct tags with which word is associated.\\
Not shown: $>$25 (ATR--Full).
\label{tagsperword}}
\vspace{3mm}
\end{figure}

Obviously, it is harder to tag with the ATR--Full tagset than with the
UPenn tagset, but how much harder? We have tried to quantify the
inherent difficulty of the various tasks for comparison.
Table~\ref{perplexity.table} displays the results of a ``trivial
tagger'', which uses the most frequently seen tag for each known word,
and the most frequent overall tag for every unknown word.\footnote{ We
considered using a Hidden Markov Model for these comparisons, but felt
it would not be informative because of the complexity of the task.}
This provides a convenient baseline for judging the difficulty of the
tagging tasks.  The first column\hspace{0.4mm} of\hspace{0.4mm}
Table~\ref{perplexity.table}\hspace{0.4mm} gives\hspace{0.4mm}
the\hspace{0.4mm} tagging\hspace{0.4mm} accuracy\hspace{0.4mm}
for\hspace{0.4mm} this\hspace{0.4mm} trivial\hspace{0.4mm}
tagger;\hspace{0.4mm} the\hspace{0.4mm} second\hspace{0.4mm}
and\hspace{0.4mm} third

\noindent show the perplexity of the training and testing data with respect to
this model.  We interpret the difference between perplexities for the
training and testing sets to mean that we are still in\hspace{0.4mm}
a\hspace{0.4mm} data--limited\hspace{0.4mm}
regime.\hspace{0.4mm}  In\hspace{0.4mm} other\hspace{0.4mm}
words,\hspace{0.4mm} the\hspace{0.4mm} estimates\hspace{0.4mm}
differ\hspace{0.4mm} in\hspace{0.4mm} the\hspace{0.4mm}
case\hspace{0.4mm} of\hspace{0.4mm}
ATR--Syntax

\noindent and ATR--Full because the sample sizes are not large
enough to provide stable estimates, whereas for UPenn they are. As a
final means of comparing tagging difficulty among the three tagsets,
we display Figure~\ref{tagsperword}, which shows relative frequency of
words with N tags, for each of the tagsets.  The largest number of
tags for a single word in the UPenn training set is 7, accounting for
0.1\% of the running words. By contrast, 21.9\% of the running words
in the ATR--Syntax training set and 33.5\% of the running words in the
ATR--Full training set have more\hspace{0.15mm} than\hspace{0.15mm} 7\hspace{0.15mm} tags.\hspace{0.15mm}  The\hspace{0.15mm} maximum\hspace{0.15mm} for\hspace{0.15mm}
ATR--Syntax\hspace{0.15mm} is\hspace{0.15mm} 19\hspace{0.15mm} tags\hspace{0.15mm} (1.9\%\hspace{0.15mm} of\hspace{0.15mm} running\hspace{0.15mm} words; 8.3\%

\noindent for ATR--Full).

\begin{table}
\begin{center}
\caption{``Trivial tagger'': results}
\renewcommand{\arraystretch}{}
\begin{tabular}{||l|l|*{3}{r|}|}
\hline
tagset      & corpus     & trivial     & perplexity      & perplexity   \\
            &            & \% correct  & training set    & testing set \\ \hline
UPenn       & UPenn      & 89.6         & 1.18         & 1.16    \\ \hline

ATR         & sentence   & 82.4         & 1.30         & 1.19    \\ \cline{2-5}
Syntax      & document   & 83.6         & 1.30         & 1.26    \\ \hline

ATR         & sentence   & 69.3         & 1.73         & 1.36    \\ \cline{2-5}
Full        & document   & 69.3         & 1.72         & 1.57    \\ \hline
\end{tabular}
\renewcommand{\arraystretch}{}
\label{perplexity.table}
\end{center}
\end{table}



Results are shown in Table~\ref{tagging.table}, in several categories:
For ``\% correct'' the set is every word in the test set; for KWT,
only known words---those words which also appeared in the training
set; for KWKT, only known words with known tags; for KWUT, only known
words with an unknown tag; for UW, only unknown words.  The results
indicate that our methods work reasonably well on unknown words, and
unknown tags for known words, although not on unknown tags for the
ATR--Full tagset.  To date, our efforts have largely concentrated on
the ATR syntax tagset; we expect that work on questions suitable for
the semantic parts of the ATR tagset will improve performance there.

\begin{table}
\begin{center}
\caption{Non--Dictionary tagger: results}
\renewcommand{\arraystretch}{}
\begin{tabular}{||l|l|*{5}{r|}|}
\hline
tagset      & corpus     & \% correct  & KWT  & KWKT & KWUT & UW          \\
            &            &             &      &      &      &             \\ \hline
UPenn       & UPenn      & 96.0        & 96.7 & 99.6 & 61.0 & 91.9        \\ \hline

ATR         & sentence   & 92.6        & 94.7 & 95.2 & 52.2 & 82.9        \\ \cline{2-7}
Syntax      & document   & 90.8        & 93.8 & 94.6 & 41.2 & 79.6        \\ \hline

ATR         & sentence   & 76.5        & 79.4 & 83.6 & 8.5  & 63.7        \\ \cline{2-7}
Full        & document   & 71.8        & 76.8 & 81.7 & 8.2  & 53.9        \\ \hline
\end{tabular}
\renewcommand{\arraystretch}{}
\label{tagging.table}
\end{center}
\end{table}

All the results shown here use the mutual information bits described
in \ref{questions}.  As shown in Table~\ref{MIBITS.table}, we have
found that incorporating these bits yields a statistically significant
improvement, even though the vocabulary they use is specific to the
WSJ corpus.\footnote{The WSJ data from which our MI bits were created
included the million words corresponding to the UPenn WSJ Treebank. 
Hence the 0.7\% contribution of the MI bits to UPenn Treebank tagging
results should be interpreted cautiously. However, the performance of
these bits on ATR--Treebank tasks, e.g. the 0.9\% contribution to our
ATR--Syntax score, suggests that most or all of the 0.7\% contribution
to the UPenn score would stand if we reclustered omitting these
million words from the 20--million--word dataset used.}

\begin{table}
\caption{Percentage of running words tagged correctly\\
for models which ignore mutual information bits\\
or which use {\em only} mutual information bits.\\
Results using both mutual--information \\
and human--created questions shown for comparison.\\
The ATR results are for the document-random test set.
}
\begin{center}
\renewcommand{\arraystretch}{}
\begin{tabular}{||l|*{3}{r|}|}
\hline
tagset      & full model  & w/o MI bits  & only MI bits\\ \hline
UPenn       & 96.0        & 95.3         & 94.6        \\ \hline
ATR Syntax  & 90.8        & 89.9         & 86.1        \\ \hline
ATR Full    & 71.8        & 68.8         & 69.4        \\ \hline
\end{tabular}
\renewcommand{\arraystretch}{}
\label{MIBITS.table}
\end{center}
\end{table}


Our plans for further research include exploring methods of factoring
``dictionary'' information (i.e. tag distribution by word in
training data) into our models; manual question--creation for ATR--Full,
while improving ATR--Syntax questions; and possibly clustering a much
larger dataset for improved MI questions.

\section{Appendix}

\subsubsection*{Gloss: ATR--Full, ATR--Syntax tagged versions}
ATR--Full in italics; ATR--Syntax in boldface; tags common to both in boldface:

\renewcommand{\arraystretch}{}
\begin{tabular}{lll}
{\bf .} & & period;\\ 
{\bf ,} & & comma;\\ 
{\bf APP\$} & & possessive pronoun, pre--nominal: my, our;\\ 
{\bf AT} & & article, either singular or plural: the, no;\\ 
{\bf CSN} & & ``than'' as conjunction: nicer than I thought;\\ 
{\bf DAR} & & comparative after--determiner: more, less;\\ 
{\bf II} & & preposition;\\
\multicolumn{2}{r}{\em IIFROM} & ``from'';\\ 
\multicolumn{2}{r}{\em IIOF} & ``of'';\\ 
\multicolumn{2}{r}{\em IION} & ``on'';\\ 
\multicolumn{2}{r}{\em IITO} & ``to'';\\ 
{\bf JJVVN} & & past participle used as adjective;\\ 
\multicolumn{2}{r}{\em JJVVNINTER-ACT} & ``inter\_action'': the deposed Shah, the stolen car;\\
{\bf MC} & & digital cardinal number: 2, 3;\\ 
{\bf NNUNUM} & & number followed by unit of measurement: 6cc, 8in.;\\ 
{\bf NN1} & & singular common noun;\\ 
\multicolumn{2}{r}{\em NN1MONEY} & ``money'': grant, fine;\\ 
\multicolumn{2}{r}{\em NN1PERS--ATT} & ``personal\_attribute'': ability, nose;\\ 
\multicolumn{2}{r}{\em NN1SYSTEM-PT} & ``system\_part'': cabinet (meeting), precinct (caucuses);\\ 
{\bf NN2} & & plural common noun;\\ 
\multicolumn{2}{r}{\em NN2ABS--UNIT} & ``abstract\_unit'': alternates, breaks;\\ 
{\bf NP1} & & singular proper noun;\\ 
\multicolumn{2}{r}{\em NP1CITYNM} & ``cityname'': Toronto;\\ 
\multicolumn{2}{r}{\em NP1FRMNM} & ``firmname'': GE, Hitachi;\\ 
\multicolumn{2}{r}{\em NP1INSTIT} & ``instit'': School, Club;\\ 
\multicolumn{2}{r}{\em NP1INSTITNM} & ``institname'': Harvard, 4--H;\\ 
\multicolumn{2}{r}{\em NP1PREPLCNM} & ``preplacename'': St. (Louis), Los (Alamos);\\ 
{\bf RR} & & general adverb;\\ 
\multicolumn{2}{r}{\em RRDEGREE} & ``degree'': absolutely, approximately;\\
\multicolumn{2}{r}{\em RRINTER-ACT} & ``inter\_action'': jointly, closely;\\ 
{\bf TO} & & pre--infinitival element: to (walk), to (go);\\ 
{\bf VBDR} & & were;\\ 
{\bf VBI} & & infinitive form of verb ``be'': be;\\ 
{\bf VMPRES} & & ``present'' modal auxiliary: can, will;\\ 
{\bf VVD} & & simple past verb;\\ 
\multicolumn{2}{r}{\em VVDVERBAL-ACTSD} & ``verbal-act'', takes sentential complement:\\
 & & implied, mentioned;\\ 
{\bf VVI} & & infinitive verb;\\
\multicolumn{2}{r}{\em VVIALTER} & ``alter'': adjust, slacken;\\ 
{\bf VVN} & & past participle;\\ 
\multicolumn{2}{r}{\em VVNINTER--ACT} & ``inter\_action'': (It was) sold, (They were) arrested.
\end{tabular}
\renewcommand{\arraystretch}{}

\subsubsection*{Gloss: mapped--down CLAWS tagged versions}
non--obvious tags only:\\
\renewcommand{\arraystretch}{}
\begin{tabular}{ll}
{\bf NNL1} & singular locative noun;\\ 
{\bf NNU} & unit of measurement, neutral for number;\\ 
{\bf RG} & degree adverb.
\end{tabular}
\renewcommand{\arraystretch}{}

\subsubsection*{Gloss: UPenn tagged versions}
non--obvious tags only: \\
\renewcommand{\arraystretch}{}
\begin{tabular}{ll}
{\bf CD} & Cardinal number;\\ 
{\bf IN} & Preposition or subordinating conjunction;\\ 
{\bf MD} & Modal;\\ 
{\bf NN} & Noun, singular or mass;\\ 
{\bf NNP} & Proper noun, singular;\\ 
{\bf NNS} & Noun, plural;\\ 
{\bf PRP\$} & Possessive pronoun;\\ 
{\bf RB} & Adverb;\\ 
{\bf TO} & to;\\ 
{\bf VB} & Verb, base form.
\end{tabular}
\renewcommand{\arraystretch}{}

\begin{thebibliography}{99}

\bibitem[\protect\BCAY{Ushioda}{Ushioda}{1996}]{Ushioda96}
A.~Ushioda \BBOP 1996\BBCP.
\newblock Hierarchical clustering of words.
\newblock {\em Proceedings, COLING 96, Copenhagen}.

\bibitem[\protect\BCAY{Merialdo}{Merialdo}{1994}]{Merialdo:tagging}
B. Merialdo \BBOP 1994\BBCP.
\newblock Tagging English Text with a Probabilistic Model.
\newblock {\em Computational Linguistics}, 20.2:155-171.

\bibitem[\protect\BCAY{Magerman}{Magerman}{1994}]{Magerman:thesis}
D. Magerman \BBOP 1994\BBCP.
\newblock {\em Natural Language Parsing As Statistical Pattern Recognition}.
\newblock Ph.D. Thesis, Stanford University.

\bibitem[\protect\BCAY{Paul}{Paul}{1990}]{Paul:algorithms}
D. Paul \BBOP 1990\BBCP.
\newblock Algorithms for an optimal $a^*$ search and linearizing the search in th
e stack decoder.
\newblock {\em Proceedings of the June 1990 DARPA Speech and Natural Language Work
shop}.

\bibitem[\protect\BCAY{Black \bgroup et al.\egroup }{Black \bgroup et al.\egroup }{1992}]{Black+al:tag}
E. Black, F. Jelinek, J. Lafferty, R. Mercer, S. Roukos \BBOP 1992\BBCP.
\newblock Decision tree models applied to the labelling of text with parts--of--speech.
\newblock In {\em Proceedings, DARPA Speech and Natural Language Workshop}, Arden House, Morgan Kaufman Publishers.

\bibitem[\protect\BCAY{Black \bgroup et al.\egroup }{Black \bgroup et al.\egroup }{1993}]{Black+al:stat}
E. Black, R. Garside, and G. Leech, Editors \BBOP 1993\BBCP.
\newblock {\em Statistically--Driven Computer Grammars Of English: The IBM/Lancaster Approach}.
\newblock Rodopi Editions.
\newblock Amsterdam.

\bibitem[\protect\BCAY{Black \bgroup et al.\egroup }{Black \bgroup et al.\egroup }{1996}]{Black+al:treebank}
E. Black, S. Eubank, R. Garside, H. Kashioka, G. Leech, D. Magerman \BBOP 1996\BBCP.
\newblock Beyond Skeleton Parsing: Producing A Comprehensive Large--Scale General--English Treebank With Full Grammatical Analysis.
\newblock In {\em Proceedings, COLING 96, EACL, Copenhagen}.

\bibitem[\protect\BCAY{Brill}{Brill}{1994}]{Brill:advances}
E. Brill \BBOP 1994\BBCP.
\newblock Some Advances in Transformation--Based Part of Speech Tagging.
\newblock In {\em Proceedings of the Twelfth National Conference on Artificial Intelligence}, pages 722-727, Seattle, Washington. American Association for Artificial Intelligence.

\bibitem[\protect\BCAY{Eyes and Leech}{Eyes and Leech}{1993}]{Eyes+Leech:EL}
E. Eyes and G. Leech \BBOP 1993\BBCP.
\newblock Syntactic Annotation: Linguistic Aspects of Grammatical Tagging and Skeleton Parsing.
\newblock Chapter 3 of Black et. al. 1993.

\bibitem[\protect\BCAY{Kruisinga}{Kruisinga}{1931}]{Kruisinga:handbook}
E. Kruisinga \BBOP 1931\BBCP.
\newblock {\em A Handbook Of Present--Day English}.
\newblock P. Noordhoff.
\newblock Groningen.

\bibitem[\protect\BCAY{Jelinek}{Jelinek}{1969}]{Jelinek:fast}
F. Jelinek \BBOP 1969\BBCP.
\newblock A fast sequential decoding algorithm using a stack.
\newblock {\em IBM Journal of Research and Development}, 13:675--685.

\bibitem[\protect\BCAY{Kucera and Francis}{Kucera and Francis}{1967}]{Kucera+Francis:KF}
H. Kucera and W. N. Francis \BBOP 1967\BBCP.
\newblock {\em Computational Analysis of Present--Day American English}.
\newblock Brown University Press.
\newblock Providence, RI.

\bibitem[\protect\BCAY{Bahl \bgroup et al.\egroup }{Bahl \bgroup et al.\egroup }{1983}]{Bahl+al:max}
L. Bahl, F. Jelinek, R. Mercer \BBOP 1983\BBCP.
\newblock A maximum likelihood approach to continuous speech recognition.
\newblock {\em IEEE Transactions on Acoustics, Speech, and Signal Processing}, PAMI--5, 2:179--190.

\bibitem[\protect\BCAY{Breiman \bgroup et al.\egroup }{Breiman \bgroup et al.\egroup }{1984}]{CART}
L.~Breiman, J.~Friedman, R.~Olshen, and C.~Stone \BBOP 1984\BBCP.
\newblock {\em Classification and Regression Trees}.
\newblock Wadsworth \& Brooks/Cole, Monterey, CA.

\bibitem[\protect\BCAY{Marcus \bgroup et al.\egroup }{Marcus \bgroup et al.\egroup }{1993}]{Marcus+al:class}
M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz \BBOP 1993\BBCP.
\newblock Building a Large Annotated Corpus of English: The Penn Treebank.
\newblock {\em Computational Linguistics}, 19.2:313-330.

\bibitem[\protect\BCAY{Brown \bgroup et al.\egroup }{Brown \bgroup et al.\egroup }{1992}]{Brown+al:class}
P. Brown, V. Della Pietra, P. de Souza, J. Lai, R. Mercer \BBOP 1992\BBCP.
\newblock Class--Based n--Gram Models of Natural Language.
\newblock {\em Computational Linguistics}, 18.4:467--479.

\bibitem[\protect\BCAY{Garside \bgroup et al.\egroup }{Garside \bgroup et al.\egroup }{1987}]{Garside+al:comp}
R. Garside, G. Leech, G. Sampson, Editors \BBOP 1987\BBCP.
\newblock {\em The Computational Analysis of English}.
\newblock London, Longman.

\bibitem[\protect\BCAY{Garside and McEnery}{Garside and McEnery}{1993}]{Garside+McEnery:GM}
R. Garside and A. McEnery \BBOP 1993\BBCP.
\newblock Treebanking: The Compilation of a Corpus of Skeleton--Parsed Sentences.
\newblock Chapter 2 of Black et. al. 1993.

\bibitem[\protect\BCAY{Long}{Long}{1961}]{Long:sentence}
R. Long \BBOP 1961\BBCP.
\newblock {\em The Sentence and Its Parts}.
\newblock University of Chicago Press.
\newblock Chicago.

\bibitem[\protect\BCAY{Weischedel \bgroup et al.\egroup }{Weischedel \bgroup et al.\egroup }{1993}]{Weischedel+al:class}
R. Weischedel, M. Meteer, R. Schwartz, L. Ramshaw, and J. Palmucci \BBOP 1993\BBCP.
\newblock Coping with Ambiguity and Unknown Words through Probabilistic Models.
\newblock {\em Computational Linguistics}, 19.2:359-382.


\end{thebibliography}


\begin{biography}

\biotitle{}

\bioauthor{Ezra W. Black}
{
B.A. 1971 (French) City College of New York; M.A. 1972
(French) Columbia University; Ph.D. 1987 (Theoretical Linguistics) 
City University of New York Graduate Center. Research Staff Member,
IBM T.J. Watson Research Center, Continuous Speech Recognition Group,
1987-1992. Since 1993, Manager, Statistical Parsing Group, Natural
Language Processing Department, ATR Interpreting Telecommunications
Laboratories, Kyoto, Japan. 
His research has concentrated on statistically-driven
broad-coverage parsing of English.
}

\bioauthor{Stephen G. Eubank}
{
B.A. 1979 (Physics), Swarthmore College;
Ph.D. 1986 (Theoretical Particle Physics), University of Texas at
Austin.. His post-doctoral work at the La Jolla Institute and Los
Alamos National Laboratory was in the fields of fluid dynamics,
nonlinear dynamics, and chaos.  He applied time series modelling and
prediction techniques developed there to financial markets as a
founder of Prediction Company in Santa Fe, New Mexico. As an Invited
Researcher at ATR he developed decision tree models for the ATR
English Grammar. He is currently a Staff Member at Los Alamos National
Laboratory, where he simulates metropolitan vehicular traffic flow.
}

\bioauthor{Hideki Kashioka}
{
B.E. 1988 (Computer Science Engineering),
M.E. 1990 (Computer Science Engineering),
Ph.D.1993 (Computer Science),
Osaka University, School of Engineering Science.
Since 1993, Researcher, ATR Interpreting Telecommunications Laboratories,
Kyoto, Japan. His current interest is in natural language processing.
}

\bioauthor{David Magerman}
{
B.S.E. 1990 (Computer Science Engineering),
B.A. 1990 (Mathematics), University of Pennsylvania, School of
Engineering and Applied Sciences; Ph.D. 1994 (Computer Science),
Stanford University, School of Engineering. Research Associate, SRI
International, 1990-92; IBM T.J. Watson Research Center, Continuous
Speech Recognition Group, 1991-94; ATR Interpreting Telecommunications
Laboratories, 1994; Bolt Beranek and Newman Inc. 1995. Since 1995, he
has been employed at Renaissance Technologies, Inc., a New York
investment firm, where he is applying statistical modelling techniques
to the prediction of changes in the value of equities and similar
financial instruments.
}

\bioauthor{Jurad Saia}
{
M.S. 1996 (Computer Science), University of New Mexico.
Currently a Ph.D. candidate at the University of Washington.
ATR Interpreting Telecommunications Laboratories, 1993. 
}

\bioauthor{Akira Ushioda}
{
B.S. 1983 (Physics)\hspace{0.2mm} Tokyo\hspace{0.2mm} University;\hspace{0.2mm} M.S. 1988
(Electronic Materials) Massachusetts Institute of Technology.
Currently Ph.D. candidate, School of Computer Science, Carnegie Mellon
University. Researcher, Fujitsu Laboratories Ltd. , 1983-present.
Researcher, ATR Interpreting Telecommunications Laboratories, 1995.
His research focused on laser optics and magneto-optic disks from 1983
to 1990, and since 1990 has concerned natural language processing.
}


\bioreceived{Received}
\biorevised{Revised}
\biorerevised{Rerevised}
\bioaccepted{Accepted}

\end{biography}

\end{document}
