



\documentstyle[epsf,nlpbbl]{jnlp_e}

\setcounter{page}{25}
\setcounter{巻数}{5}
\setcounter{号数}{2}
\setcounter{年}{1998}
\setcounter{月}{4}
\受付{July}{2}{1997}
\再受付{October}{15}{1997}
\採録{January}{23}{1998}

\setcounter{secnumdepth}{2}

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

\etitle{A Method for Syntactic Behavior Analysis}

\eauthor{Wide R. Hogenhout\affiref{NaraSentanCanon} \and
         Yuji Matsumoto\affiref{NaraSentan}}

\headauthor{Hogenhout and Matsumoto}
\headtitle{A Method for Syntactic Behavior Analysis}

\affilabel{NaraSentanCanon}
          {This work was carried out while the first author was affiliated to
the Nara Institute of Science and Technology. Starting April 1998 the first author
will join the Canon Research Centre Europe (CRE) in the U.K.}
          {This work was carried out while the first author was affiliated to
the Nara Institute of Science and Technology. Starting April 1998 the first author
will join the Canon Research Centre Europe (CRE) in the U.K.}
\affilabel{NaraSentan}
          {Nara Institute of Science and Technology}
          {Nara Institute of Science and Technology}

\eabstract{
    We show how a treebank can be used to cluster words on the basis of their
    syntactic behavior. By extracting statistics on the structures in which
    words appear it is possible to discover similarities and differences in usage 
    between words with the same part-of-speech.
    This clustering is compared to the conventional clustering based on
    co-occurrences. While conventional clustering can discover semantical 
    similarities or the tendency to appear together, the method we present
    ignores these factors and places the focus on syntactical usage,
    in other words the sort of structures it appears in.
    We present a case study on prepositions, showing how they can be 
    automatically subdivided by their syntactic behavior and we discuss the 
    appropriateness of such a subdivision.
    We have also carried out experiments to compare the quality of clusters
    quantitatively. For this goal we used clusters based on syntactic behavior
    for improving the estimation of the distribution of the dependency relation
    between words. Since such a distribution is necessarily estimated with
    sparse data, an entropy test can show how informative the classes are
    about syntactic usage.
    Finally, we discuss a number of ways in which a classification of words 
    can contribute to applications of natural language processing.
}

\ekeywords{Statistical Natural Language Processing, 
   Word Clustering, Syntactic Disambiguation, Syntactic Behavior}


\begin{document}

\maketitle


\section{Introduction}

The construction of classes of words, or calculation of distances between words,
has frequently drawn the interest of researchers in natural language processing.
Many of these studies aimed at finding classes based on co-occurrences, often
combined with the aim of establishing semantic similarity between words
\cite{mcmahon96,brown:clust,dagan:context,dagan:sym,pereira:distr,gref:adj}.

We suggest a method for clustering words purely on the basis of syntactic
behavior. We show how the necessary data for such clustering can easily be drawn
from a publicly available treebank, and how distinct types of behavior can be
discovered. The resulting clusters do not reflect semantic similarity nor a
tendency to co-occur. They do reflect that, for example, a particular noun is
often the object of a prepositional phrase, or that a particular verb is often
used transitively. Although a part of speech tag set can be thought of as a
classification based on syntactic behavior, we can construct an arbitrary number
of clusters, or a binary tree of words that share their part of speech.

In this paper two evaluations of the resulting clusters are presented. First, we
present a case study of prepositions. We discuss in detail a binary word tree
for prepositions that was created by syntactic-behavior based clustering, to
show what sort of properties are revealed by the clustering and what one can
learn from this about language. Many of the separations made by the algorithm
are natural divisions, which can often be felt by intuition, but which could not
be quantified before.

We also present an experiment, in order to obtain more quantitative
evaluation of clusters and to compare clusters made in a different
way.  For this goal experiments were carried out in which the clusters
were used for estimation of a probabilistic distribution. The idea
behind this experiment is that when the words within clusters are
similar with respect to their syntactic behavior, these clusters
should also give more information about their behavior in a somewhat
different context. \footnote{More recently, after this article was written,
\cite{ik:phd} demonstrated how the clusters do in fact
improve the accuracy and precision of a general statistical parsing
system for English.}

Finally, we describe a number of ways in which these methods can be applied in
Natural Language Processing applications. In particular, a binary tree of words
can be used to supply efficient questions to a decision tree based system that
predicts, for example, syntactical structure. Other applications are to be found
in Information Retrieval and Lexicography. The main contribution of this method
over previous methods is the possibility to quantify a property that every word
has, but which is not revealed by traditional clustering methods.

\section{Headwords and Dependencies} \label{hadsec}

The data we extract are based on the concept of {\em headwords}.  Such
headwords are chosen for every constituent in the parse tree by means
of a simple set of rules. These have been used in various studies in
this field, see
\cite{charniak97,collins96,magerman:acl,ik:boek,jelinek94}.  Every
headword is propagated up through the tree such that every parent
receives a headword from the head-child.  Figure~\ref{treesam} gives
an example of a parse tree with headwords.

\begin{figure}[t]
\begin{center}
\atari(72,42)
\caption{Sentence with Parse Tree and Headwords}
\label{treesam}
\end{center}
\end{figure}

Following the techniques suggested by \cite{collins96}, a parse tree
can subsequently be described as a set of dependencies.  Every word
except the headword of the sentence depends on the lowest headword it
is covered by. The syntactic relation is then given by the triple of
nonterminals: the modifying nonterminal, the modified nonterminal, and
the nonterminal that covers the joint phrase. Table~\ref{examp} gives
an example of such a description.

The scheme for choosing headwords necessarily introduces some
arbitrary choices, for example in the case of coordinate structures
such as ``John and Mary,'' but in most cases the choice is not
difficult and we believe that these arbitrary choices do not pose a
great problem to frequently occurring words.

On one point our method is different from the method suggested by Collins.
Collins uses a {\em reduced sentence} in which every basic noun phrase (i.e., a
noun phrase that has no noun phrase as a child) is reduced to its headword.  For
example, the phrase ``a car'' is reduced to ``car'', and ``his resignation'' is
reduced to ``resignation.''  The reason for this is that it improves
co-occurrence counts and adjacency statistics. We however do not reduce the
sentence since we do not need to consider adjacency statistics or unresolved
ambiguities, and therefore never face the problem that a word in a basic noun
phrase, that is not the headword, is adjacent to or modifies something outside
of the basic noun phrase.

Table~\ref{examp} gives the relations for one sentence, but instead of
considering one sentence we collect such patterns for the whole corpus and study
statistics for individual words. In this way it can be discovered that, for
example, a particular verb is often used transitively, or that a particular
preposition is mostly used to produce locative prepositional phrases. Words can
be distinct or similar in this respect, but note that this is not related to
semantic similarity.  Words such as {\em eat} and {\em drink} have a semantic
similarity, but may be completely different in their syntactic behavior, whereas
{\em tend} and {\em appear} do not have an obvious semantic relation, but they
do have a similarity since they can both be used as raising verbs, as will be
exemplified later.

Throughout this paper we will use the term ``word'' to refer to words
for which the part of speech has already been disambiguated. In tables
and figures we emphasize this by indicating the part of speech
together with the word.

\begin{table}[thbc]
\begin{center}
\caption{Dependencies for the sentence {\em John Smith works fast}}
\begin{tabular}{|l|l|lll|} \hline
\multicolumn{1}{|c|}{dependent word} & 
       \multicolumn{1}{|c|}{head word} & 
       \multicolumn{3}{|c|}{relation} \\ \hline
John & Smith &  - & NP & - \\ 
(proper noun) & (proper noun) & & & \\  \hline
Smith & works & NP & S & VP \\ 
(proper noun) & (verb) & & & \\ \hline
fast & works & - & VP & - \\ 
(adverb) & (verb) & & & \\ \hline
\end{tabular}
\label{examp}
\end{center}
\end{table}

\section{Collecting Statistics for Individual Words} \label{statsec}

The next step we take, is eliminating one of the two words in this
table of dependencies. Consider tables~\ref{elimdep}
and~\ref{elimhead}. These show we can take three ``observations''
from the sentence by eliminating either the headword or the dependent
word. If headwords are eliminated we obtain three observations, for
the words {\em John}, {\em Smith} and {\em fast}. If dependent words are
eliminated we also obtain three observations, two for {\em works} and
one for {\em Smith.}

By collecting the observations over the entire corpus we can see to/by
what sort of words and with what kind of relations a word modifies or
is modified. We consider the following distributions:
\begin{eqnarray}
p(R,t_{h}|w_{d}t_{d}) \label{depdis} \\
p(R,t_{d}|w_{h}t_{h}) \label{headdis}
\end{eqnarray}
where $R$ indicates the triple representing the syntactic relation,
$w_{d}$ a dependent word that modifies headword $w_{h}$, and $t_{d}$
and $t_{h}$ their respective part of speech tags. For example, in the second
line of table~\ref{elimhead}, which corresponds to distribution~\ref{depdis},
$R$ is (NP,S,VP), $t_{h}$ is ``verb'', $w_{d}$ is ``Smith'' and $t_{d}$ is
``proper noun''.

Statistics of the distributions (\ref{depdis}) and (\ref{headdis}) can
easily be taken from a treebank. We took such data from the Wall
Street Journal Treebank, calculating the probabilities with the Maximum
Likelihood Estimator:
\[
p(R, t_{h}|w_{d} t_{d}) = \frac{f(R, t_{h}, w_{d} t_{d})}
                               {\sum_{R',t'}f(R',t',w_{d} t_{d})}
\]
where $f$ stands for frequency. This equation shows how the ML estimation is
calculated for distribution (\ref{depdis}). The ML estimation for distribution
(\ref{headdis}) is calculated likewise. Note that we only extract the dependency
relations, and ignore the structure of the sentence beyond these relations.

Compare the dependency behavior of the proper nouns {\em Nippon} and
{\em Rep.} in table~\ref{nippon}. The word {\em Nippon} is Japanese
for {\em Japan}, and mainly occurs in names of companies. The word
{\em Rep.} is the abbreviation of {\em Representative}, and obviously
occurs mainly with names of politicians.  As can be seen, the word
{\em Rep.}  occurs far more frequently, but the distributions are
highly similar. Both always modify another proper noun, about 33\% of
the time forming an NP-SBJ and 67\% of the time an NP. Both are a
particular kind of proper noun that almost always modifies other
proper nouns and almost never appears by itself.

It also became clear that the noun {\em company} is very different from a noun
such as {\em hostage}, since {\em company} often is the subject of a verb, while
{\em hostage} is rarely in the subject position. Both are also very different
from the noun {\em year}, which is frequently used as the object of a
preposition.

The present participle {\em including} has an extremely strong tendency to produce
prepositional phrases, as in {\em ``Safety advocates, including some
members of Congress, ...''}, making it different from most other present participles.
A past tense such as {\em fell} has an unusual high frequency as the
head of a sentence rather than a verb phrase, which is probably a
peculiarity of the Wall Street Journal ({\em ``Stock prices
fell...''}).

Our observation is that among words which have the same part of
speech, some word groups exhibit behavior that is extremely similar,
while others display large differences. The method we suggest aims at
making a clustering based on such behavior.  By using this technique
any number of clusters can be obtained, sometimes far beyond what
humans can be expected to recognize as distinct categories.

\begin{table}[thbc]
\begin{center}
\caption{Dependencies with dependent words eliminated.}
\begin{tabular}{|l|l|lll|} \hline
dependent word & 
       \multicolumn{1}{|c|}{head word} & 
       \multicolumn{3}{|c|}{relation} \\ \hline
* & Smith         & - & NP & - \\ 
(proper noun)     & (proper noun) & & & \\ \hline
* & works  & NP & S & VP \\
(proper noun) & (verb) & & &\\ \hline
* & works &  - & VP & - \\
(adverb) & (verb) & & & \\ \hline
\end{tabular}
\label{elimdep}
\end{center}
\end{table}

\begin{table}[thbc]
\begin{center}
\caption{Dependencies with headwords eliminated.}
\begin{tabular}{|l|l|lll|} \hline
\multicolumn{1}{|c|}{dependent word} & 
     head word & 
       \multicolumn{3}{|c|}{relation} \\ \hline
John & * & - & NP & - \\
(proper noun) & (proper noun) & & & \\ \hline
Smith & * & NP & S & VP \\ 
(proper noun) & (verb) & & & \\ \hline
fast & * & - & VP & - \\ 
(adverb) & (verb) &  & & \\ \hline
\end{tabular}
\label{elimhead}
\end{center}
\end{table}

\begin{table}[thbc]
\vspace*{-5mm}
\begin{center}
\caption{Distribution of dependencies of the words {\em Nippon} and 
{\em Rep.}, as proper nouns.}
\begin{tabular}{|l|l|lll|l|} \hline 
\multicolumn{1}{|c|}{dep. word} & headword tag & 
     \multicolumn{3}{|c|}{relation} & freq. \\ \hline \hline
{\em Nippon} &  proper noun & - & NP-SBJ & - &3 \\ \cline{2-6}
proper n.  &  proper noun  & - & NP & - & 6 \\ \hline  \hline
{\em Rep.} &  proper noun  & - & NP-SBJ & - & 23 \\ \cline{2-6}
proper n. & proper noun  & - & NP & - & 45  \\ \hline
\end{tabular}
\label{nippon}
\end{center}
\end{table}

\section{Comparison with Co-Occurrence Based Clustering}

Clustering of words based on syntactic behavior has to our knowledge not been
carried out before, but clustering has been applied with the goal of obtaining
classes based on co-occurrences. Such clusters were used in particular for
interpolated $n$-gram language models.

By looking at co-occurrences it is possible to find groups of words such as
[{\em director, chief, professor, commissioner, commander, superintendent}].
The most prominent method for discovering their similarity is by finding words
that tend to co-occur with these words. In this case they may for example
co-occur with words such as {\em decide} and {\em lecture}.

The group of verbs [{\em tend, plan, continue, want, need, seem, appear}] also
share a similarity, but one has to look at structures rather than meaning or
co-occurrences to see why. All these verbs tend to occur in the same kind of
structures, as can be seen in the following examples from the Wall Street
Journal.

\hspace*{4mm}
{\tt The funds' share prices tend to swing more than the broader market.}

\hspace*{4mm}
{\tt Investors continue to pour cash into money funds.}

\hspace*{4mm}
{\tt Cray Research did not want to fund a project that did not include}

\hspace*{4mm}
{\tt Seymour.}

\hspace*{4mm}
{\tt No one has worked out the players' average age, but most appear to be}

\hspace*{4mm}
{\tt in their late 30s.}

What these verbs share is the property that they often modify an entire clause
(marked as 'S' in the Wall Street Journal Treebank) rather than noun phrases or
prepositional phrases, usually forming a subject raising construction.  This is
only a tendency, since all of them can be used in a different way as well, but
the tendency is strong enough to make their usage quite similar. Co-occurrence
based clustering ignores the structure in which the word occurs, and would
therefore not be the right method to find related similarities.

As mentioned, co-occurrence based clustering methods often also aim at producing
semantically meaningful clusters. Various methods are based on Mutual
Information between classes, see
\cite{brown:clust,mcmahon96,kneser,jardino,martin,ueberla}. This measure cannot
be applied in our case since we look at structure and ignore other words, and
consequently algorithms using that measure cannot be applied to the problem we
deal with.

The mentioned studies use word-clusters for interpolated $n$-gram language
models. Another application of hard clustering methods (in particular bottom-up
variants) is that they can also produce a binary tree, which can be used for
decision-tree based systems such as the SPATTER parser \cite{magerman:acl} or
the ATR Decision-Tree Part-Of-Speech Tagger \cite{black:dtm,ushioda96}. In this
case a decision tree contains binary questions to decide the properties of a
word.

We present a {\em hard} clustering algorithm, in the sense that every word
belongs to exactly one cluster (or is one leaf in the binary word-tree of a
particular part of speech). Besides {\em hard} algorithms there have also been
studies to {\em soft} clustering \cite{pereira:clust,dagan:sym} where the
distribution of every word is smoothed with the nearest $k$ words rather than
placed in a class which supposedly has a uniform behavior. In fact, in
\cite{dagan:context} it was argued that reduction to a relatively small number
of predetermined word classes or clusters may lead to substantial loss of
information. On the other hand, when using soft clustering it is not possible to
give a yes/no answer about class membership, and binary word trees cannot be
constructed.

\section{Similarity Measure and Algorithm}

The choice of the clustering algorithm is to some extent independent from the
way data is collected, but as mentioned clustering is carried out on the basis
of distributional similarity, and methods using Mutual Information are not
applicable. The algorithm we present here is meant to demonstrate how
syntactic behavior can be used for clustering. However, we feel the optimal
choice for the clustering method depends on the application it will be used for.

Studies in distribution based clustering often use the Kullback-Leibler (KL)
distance, see for example \cite{pereira:clust,dagan:sym}. However, this distance
is not symmetrical, and since we are (for the time being) interested in {\em
  hard clustering} it is desirable to have a symmetrical measure. We could
possibly use Jeffery's Information, i.e. the sum of the KL-distances:
\begin{eqnarray}
J(p,q) & = & KL(p \| q) + KL(q \| p) \nonumber \vspace*{2mm} \\ 
       & = & \sum_{x}p(x)\log\left(\frac{p(x)}{q(x)}\right) + 
                     q(x)\log\left(\frac{q(x)}{p(x)}\right) . \label{diverg}
\end{eqnarray}

We have tried this distance measure, but in many cases we have found
it to have undesirable effects, primarily because the goal of our
algorithm is joining words (and their statistics) together to make one
cluster, and a distorted image results from this measure when words
have different total frequencies.  Furthermore, Jeffery's Information is
undefined if either distribution has a value of 0 and the other not. 
For this reason they would have to be smoothed with, for example, a
part of speech based distribution, such as
\begin{eqnarray}
\hat{p}(R, t_{h}|w_{d}t_{d}) & = & \lambda p(R, t_{h}|w_{d}t_{d}) +
                   (1-\lambda) p(R, t_{h}|t_{d}) , \label{divsm}
\end{eqnarray}
but we wanted to avoid using an unlexical distribution since we
believe lexical information is more valuable.

Instead we suggest a different measure. What we would like to use
is the sum of the KL-distances between a hypothetical word that would
be created if the observations were joined and the respective words, i.e.
\[
M(p,q) \stackrel{\rm def}{=} KL(p \| p \uplus q) + KL(q \| p \uplus q)
\]
which reflects the result of the used operation more closely. We will explain
how the symbol $\uplus$ should be understood. Assume there are a number of
patterns $i=1...n$, and observed frequencies $a_{1}...a_{n}$ for word
$w_{a}t_{a}$, and $b_{1}...b_{n}$ for word $w_{b}t_{b}$. Also, let $A =
\sum_{i}a_{i}$ and $B = \sum_{i}b_{i}$. The Maximum-Likelihood estimates for
$w_{a}$ are thus calculated as $p_a(x) = a_{x}/A$ and likewise for $w_{b}$.

Using the notation $p_{a+b}(i) = \frac{a_{i}+b_{i}}{A+B}$, we define the
distance between words as
\begin{eqnarray*}
M(w_{a}t_{a},w_{b}t_{b}) & = &
KL(w_{a}t_{a}\| w_{a}t_{a} \uplus w_{b}t_{b}) + 
     KL(w_{b}t_{b}\| w_{a}t_{a} \uplus w_{b}t_{b})  \vspace*{2cm} \\
& = & \sum_{i} p_{a}(i)\log\left(\frac{p_{a}(i)}{p_{a+b}(i)}\right) +
               p_{b}(i)\log\left(\frac{p_{b}(i)}{p_{a+b}(i)}\right)
\end{eqnarray*}
which can be interpreted as the sum of KL-distances between a hypothetical word
that would be created if the observations of the words $w_{a}t_{a}$ and
$w_{b}t_{b}$ would be joined together, and $w_{a}t_{a}$ and $w_{b}t_{b}$
respectively. Like Jeffery's Information, this measure is symmetrical, although
not a true distance since it does not obey the triangle inequality.

This measure is more appropriate for two reasons. First, this
distribution is better tailored toward making clusters where
observations will be joined together. Second, we take this sum to be
zero for values of $i$ when $a_{i} = b_{i} = 0$ (no observations for
either word), therefore pre-smoothing is not necessary.

The equation can easily be transformed into the form
\begin{eqnarray}
M(w_{a}t_{a},w_{b}t_{b}) & = & \log\left(\frac{A+B}{A}\right) + 
                 \log\left(\frac{A+B}{B}\right) +  \nonumber \\
& &      \sum_{i} \frac{a_{i}}{A}\log\left(\frac{a_{i}}{a_{i}+b_{i}}\right) +
         \frac{b_{i}}{B}\log\left(\frac{b_{i}}{a_{i}+b_{i}}\right) 
\label{newm}
\end{eqnarray}
which makes calculation significantly faster since patterns for which
only one word has a non-zero frequency do not need to be calculated within
the summation, as they always becomes zero.

\paragraph{The Algorithm}

The algorithm initially regards every word as a 1-element cluster, and works
{\em bottom up} towards a set of clusters. Clusters are {\em merged}, which
means that they are considered to be one new cluster. The observations are
combined; i.e. (using the notation from the previous paragraph)
\[
p_{wa+wb}(i) = \frac{a_{i}+b_{i}}{A+B} .
\]

The strategy of a {\em greedy algorithm} is followed, every time finding the two
clusters that have the least distance between them and merging them until the
desired number of clusters is reached. However, only words with the same part of
speech may be merged, so distances between words that have different parts of
speech are never calculated. Words can therefore receive a 'combined tag'
consisting of their part of speech tag, and a syntactic behavior tag.  This is
similar to what \cite{mcmahon96} refer to as a {\em structural
  tag.}

The algorithm is actually applied {\em twice}, once to clustering for
dependent-context (\ref{depdis}) and once to clustering for
head-context (\ref{headdis}).

An obvious problem with this sort of clustering is low frequency words.  For
many words only one or a few observations are available, which may give some
information about what sort of word it is, but which does not give a reliable
estimate of the distributions. We will mention a solution to this problem later.
In the example we present only words for which at least 25 observations are
available.

One problem with co-occurrence based clustering that has been pointed
out in the past is that of almost-linear dendrograms, i.e. such that
it forms a very unbalanced tree, caused by the properties of Mutual
Information.  In this case the set of words can not be divided in
subsets of roughly equal size.

\section{A Case Study of Prepositions}

We present a binary word tree that was produced by the algorithm described in
the previous section. The main goal of this is to show what sort of properties
are revealed by this clustering, and what kind of words are problematic.  Even
in situations where words are clustered by syntactic behavior without making a
binary tree, it can be useful to study the type of properties that decide
syntactic behavior.  The data for this clustering were taken from the Wall
Street Journal Corpus, using a total of around 800,000 patterns as data.

Please refer to figures~\ref{dendro1} and~\ref{dendro2} for an example of the
results obtained with clustering. This is a dendrogram that reflects the
clustering process from loose words until the point were they are all merged
into one cluster. The dendrogram shows the result for prepositions, although
only those prepositions were considered for which at least 25 observations were
available. In the division of words over the parts of speech we follow the
tagging scheme of the Wall Street Journal Treebank, and for example
subordinators such as {\em while, if} and {\em because} are included in the
prepositions.  Of course it is possible to use a more fine grained tag set, when
available. On the other hand, as will be shown later, the algorithm does decide
to classify most subordinators into one cluster.

We will discuss the major distinctions made by the algorithm. At first it may
not be clear why words should be divided in this way, but inspection of the data
from the corpus shows that many of these choices are very natural. We also
discuss in which cases the dendrogram does not form natural categories.

\begin{figure}[!thbm]
\begin{center}
\atari(77,141)
\caption{Clustering Result for Dependency Behavior of Prepositions (Upper Part)}
\label{dendro1}
\end{center}
\vspace*{1cm}
\end{figure}

\begin{figure}[!thbm]
\begin{center}
\atari(80,90)
\caption{Clustering Result for Dependency Behavior of Prepositions (Lower Part)}
\label{dendro2}
\end{center}
\end{figure}

The first partition, marked A, is a quite natural division. The upper
branch (from {\em off} through {\em About}) are prepositions that usually cover
some phrase themselves, whereas the prepositions in the lower branch usually
do not cover any phrase.

The preposition {\em whether} occurs, for example, in structures such as
\begin{quote}
{\tt `` We have no useful information on (SBAR {\bf whether} (S users 
are at \newline
risk)),'' said James A. Talcott of Boston's Dana- Farber Cancer \newline
Institute.}
\end{quote}
where in our headword-selection scheme {\em whether} depends on the headword
{\em are.} (Even if this is changed, they still become one cluster because of
the typical patterns with S and SBAR.)

For comparison, the preposition {\em below} usually occurs in structures such as

\hspace*{4mm}
{\tt Magna recently cut its quarterly dividend in half and the company's}

\hspace*{4mm}
{\tt Class A shares are (VP wallowing (PP-LOC far {\bf below} their 52-week high}

\hspace*{4mm}
{\tt of 16.125 Canadian dollars (US\$ 13.73)))}.

\noindent
where it is the headword of a prepositional phrase before it modifies
the verb.

The partition marked with B is not a natural division; it rather separates a set
of prepositions that do not fit in elsewhere. The prepositions from {\em per}
through {\em About} are not similar to each other or to other prepositions in their
behavior.

Partition C again resembles to groups that can be characterized easily.  The
prepositions {\em by} through {\em After}, the lower branch of C, depended almost
exclusively on verbs. The prepositions from {\em off} through {\em about}, the upper
branch of C, depend on more varied headwords. Most of these frequently depend on
both nouns and verbs. The following example shows {\em around} depending on a
noun, although {\em around} also tends to depend on cardinal numbers.

\hspace*{4mm}
{\tt You now may drop by the Voice of America offices in Washington and 
read}

\hspace*{4mm}
{\tt the text of what the Voice is broadcasting to those 130 million 
people}

\hspace*{4mm}
{\tt (PP-LOC {\bf around} the world) who tune in to it each week.}

An example for the lower branch of C is

\hspace*{4mm}
{\tt A plan to bring the stock to market before year end apparently} 

\hspace*{4mm}
{\tt (VP was upset (PP {\bf by} the recent weakness of Frankfurt share prices)).}

The prepositions at the upper branch of partition D tend to form a higher
amount of PP-TMP type phrases, as in
\begin{quote}
{\tt And in each case, he says, a sharp drop in stock prices (VP began \newline
(PP-TMP {\bf within} a year)).}
\end{quote}
although, while this is strongly the case for the prepositions {\em within} and
{\em throughout,} it is not the case for {\em behind.}

At partition E prepositions with a preference for verbs are at the
upper branch. Prepositions that almost exclusively deal with verbs
were separated at C, but here the distinction is less absolute. The
prepositions at the upper branch of E have a chance of about two
thirds to depend on a verb, whereas this is only one third at the
lower branch.

Partition F is once again a very clear, natural division. The prepositions
{\em in}, {\em on} and {\em at} have a strong tendency to form phrases of the type
PP-LOC as in

\hspace*{4mm}
{\tt Mr. Nixon is traveling (PP-LOC {\bf in} China) as a private citizen, but}

\hspace*{4mm}
{\tt he has made clear that he is an unofficial envoy for the Bush}

\hspace*{4mm}
{\tt administration.}

\noindent
while the prepositions at the lower branch, {\em of} through {\em about} have
much lower frequencies for these locative phrases.

The division at G is also very clear when the data are inspected. The
upper branch reflects prepositions for which the covering phrase (the
middle part of the triple representing the grammatical relation) is
mostly VP or NP. The prepositions {\em For} through {\em After} at the
lower branch of G are mainly covered by phrases of type S. A preposition
such as {\em during} is found in structures such as

\hspace*{4mm}
{\tt Fujitsu said it (VP bid the equivalent of less than a U.S. penny on}

\hspace*{4mm}
{\tt three separate municipal contracts (PP-TMP {\bf during} the past two years)).}

\noindent
while a preposition such as {\em without} is usually found in the
PP-S-VP pattern:

\hspace*{4mm}
{\tt (S In fact, (PP {\bf without} Wall Street firms trading for their own}

\hspace*{4mm}
{\tt accounts), the stock-index arbitrage trading opportunities for the big}

\hspace*{4mm}
{\tt funds (VP may be all the more abundant).)}

At H this is further divided in words that tend more to depend on
loose words, PP type phrases (such as {\em without} in the last example)
or S type phrases, at the lower branch, and those that usually depend
on heads of a VP.

As for the division at point I, the prepositions {\em next} through
{\em Although} share the property that their covering phrase (the middle
part of the triple representing the grammatical relation) is often of
the type SBAR-ADV or SBAR-PRP.  The prepositions at the upper branch,
{\em whether} through {\em down,} mainly share not having this property. 

While the status of the upper branch of J is somewhat unclear, the lower branch
of J is a perfectly clear and intuitive group. All of the words from {\em
  though} through {\em Although} appear almost exclusively in the patterns
(--,SBAR-ADV,S), (--,S,S), (--,SBAR-PRP,S) and (--,SBAR-PRP,--). An example is

\hspace*{4mm}
{\tt The group says standardized achievement test scores are greatly inflated}

\hspace*{4mm}
{\tt because teachers often ``teach the test'' as Mrs. Yeargin did,}

\hspace*{4mm}
{\tt (SBAR-ADV {\bf although} (S most are never caught)). }

\noindent
where in our headword scheme {\em are} becomes the headword of the SBAR-ADV type
phrase.

Concluding, many of the divisions made by the algorithm are quite natural. There
are some parts of speech (such as nouns and verbs) were a much larger number of
words is included in the hierarchy, while some other parts of speech, for
example personal pronouns, produce very small hierarchies. In general the
hierarchy is more interesting for parts of speech that are used in a varied way,
and less interesting for, for example, symbols such as the percentage sign, that
are used in a monotone way.

It is interesting to see that capitalization turns out to be a meaningful
predictor about the way a word will be used for some words, but not for others.
The word pair {\em so} and {\em So}, and the pair {\em because} and {\em
  Because} are clustered next to each other, which indicates that they modify
the same kind of structures, independent of whether they are at the beginning of
the sentence.  The word pair {\em under} and {\em Under}, and the pair {\em
  after} and {\em After} on the other hand are rather far apart, indicating that
their usage changes substantially when they become the first word of the
sentence.

Co-occurrence-based clustering algorithms tend to make different
choices. Although the exact choices depend on the algorithm chosen, we
mention some general tendencies. The preposition "since" tends to be
clustered close to "of" and "from" as all of them often occur next to
or near year-indications ("1986"), month-names ("January") and
weekdays ("Friday"). Also, "next", "on", "before" and "by" tend to
form a group because of their high co-occurrence with weekdays.

Also, "as" tends to come close to words such as "so" and "if" because
of their high co-occurrence with personal pronouns.

Another difference is that we found little influence of
capitalization.  Being at the start of a sentence appeared to have
little effect on the surrounding words. The words that are harder to
classify also tend to differ; there are for example fixed patterns
such as "along with", "among others", "at least" and "under pressure"
that are not shared by other prepositions.

\section{Quantitative Evaluation: Dependency Relations}

The distribution of types of dependency relations between words is of
importance to natural language processing, partly because of the
direct practical application in parsing systems, but even more so
because it can show fundamental properties of language. At the same
time it is clear that good estimation techniques will be important due
to the enormous number of parameters.

Consider the distribution of the dependency relation between two
words, given that there is some dependency relation between them, and
given their respective parts of speech:
\begin{eqnarray}
p(R|w_{d}t_{d},w_{h}t_{h}) . \label{basiceq}
\end{eqnarray}

The used symbols carry the same meaning as in section~\ref{statsec}.  Our
conjecture is that the classes we obtained will also indicate similarity within
the distribution (\ref{basiceq}).

A distribution similar to this is used in \cite{collins96} for English and in
\cite{fujio97eng} for Japanese, in both cases with the goal of carrying out
syntactical analysis. We use this for a more quantitative evaluation of the
clusters that can be produced in the way mentioned earlier. The distribution
showed here is clearly different from that used for clustering, but it is also
related to the syntactic structures in which words occur. If words tend to occur
in the same sort of structures, we expect a tendency of their marginals with
respect to this distribution to share similarities as well.

The baseline model we use is the regular model smoothed with part of
speech based probabilities using a method suggested by \cite{bahl83}. 
To be exact,
\begin{eqnarray*}
\hat{p}_{lexical}(R|w_{d}t_{d}, w_{h}t_{h}) 
 & = & \lambda_{1}(w_{d}t_{d}, w_{h}t_{h})p(R|w_{d}t_{d}, w_{h}t_{h}) + \\
      &  & \lambda_{2}(w_{d}t_{d}, w_{h}t_{h})p(R|t_{d}, w_{h}t_{h}) + \\
      &  & \lambda_{3}(w_{d}t_{d}, w_{h}t_{h})p(R|w_{d}t_{d}, t_{h}) + \\
      &  & \lambda_{4}(w_{d}t_{d}, w_{h}t_{h})p(R|t_{d}, t_{h}) \\
\end{eqnarray*}
which we refer to in the table as {\bf lexical}. The basic
probabilities are found with the Most-Likelihood estimator, and the
interpolation parameters are estimated from data held out for this
goal, but not separately for every word pair. As suggested by 
\cite{bahl83} they are divided into buckets based on 
their count, so that all
word pairs with the same frequency have the same interpolation
parameters. The frequencies were also joined into one bucket when
there was too little data to estimate them. We used the same technique
for all other models.

The class-based model we compare this with is
\begin{eqnarray*}
\hat{p}_{classes}(R|w_{d}t_{d}, w_{h}t_{h}) 
 & = & \lambda_{1}(c_{d}, c_{h})p(R|c_{d}, c_{h}) + \\
      &  & \lambda_{2}(c_{d}, c_{h})p(R|t_{d}, c_{h}) + \\
      &  & \lambda_{3}(c_{d}, c_{h})p(R|c_{d}, t_{h}) + \\
      &  & \lambda_{4}(c_{d}, c_{h})p(R|t_{d}, t_{h})
\end{eqnarray*}
where $c_{d}$ is the class of $w_{d}t_{d}$ (using the dependent-word
clustering), and $c_{h}$ the class of $w_{h}t_{h}$ (using the
headword clustering). These classes were made with the new 
measure (\ref{newm}). In the table this model is identified as {\bf classes}.

Since test data was not used for clustering, the test data contained a
certain percentage of words that were never clustered by the
algorithm. For this reason an imaginary extra cluster is assumed,
containing all such ``unseen'' words. Probabilities conditioned on
this class are always zero.

Exactly the same model has also been applied to the model identified
as {\bf divergence}. This model is completely identical to {\bf classes},
but with the clusters produced using divergence (\ref{diverg}) as the
distance measure (equation (\ref{divsm}) was used for smoothing word
distributions), instead of our measure (\ref{newm}).

We also present results of a combined model using both lexical
and class-based probabilities. This is calculated with the equation
\begin{eqnarray*}
\hat{p}_{comb}(R|w_{d}t_{d}, w_{h}t_{h}) 
 & = & \lambda_{1}(w_{d}t_{d}, w_{h}t_{h})p(R|w_{d}t_{d}, w_{h}t_{h}) + \\
      &  & \lambda_{2}(w_{d}t_{d}, w_{h}t_{h})p(R|c_{d}, c_{h}) + \\
      &  & \lambda_{3}(w_{d}t_{d}, w_{h}t_{h})p(R|t_{d}, c_{h}) + \\
      &  & \lambda_{4}(w_{d}t_{d}, w_{h}t_{h})p(R|c_{d}, t_{h}) + \\
      &  & \lambda_{5}(w_{d}t_{d}, w_{h}t_{h})p(R|t_{d}, t_{h}) \\
\end{eqnarray*}
and identified as {\bf combined}.

\section{Experimental Results}

The experiments were carried out with data from the Wall Street
Journal Corpus. A set of about 740,000 patterns was used as training
data, for clustering words, and to optimize smoothing parameters. A
separate group of 60,000 patterns was used for testing.  In order to
assess statistical significance of results this experiment was carried
out 5 times, each time using different test data.

In all clustering methods different sets of classes were made for the
dependent position and the headword position. The number of classes we
found to be optimal was about 3000 for both dependent position and
headword position.

Table~\ref{mainres} shows the results for the given models. The
cross entropy of predicting the relation of all patterns is given in the
first column. The second column gives the entropy on patterns that
occurred at least once in the training data
($f(R,w_{d}t_{d},w_{h}t_{h})>0$). The third column indicates entropy on
patterns that did not occur in the training data
($f(R,w_{d}t_{d},w_{h}t_{h}) = 0$). 
All differences between models were found to be
significant with a so-called paired t-test ($p<0.001$), except the
difference between the pair marked with the symbol ``$\star$.''  A
paired t-test is a method for analyzing the differences between pairs
of scores, on a number of data sets. As mentioned, the values in the
table are averaged results of five samples. A paired t-test takes into
consideration the separate sample scores rather than the average.

The classes produced with the distance measure (\ref{newm}) display a
cross entropy of only about 2\% more than the lexical model. The size
of the tables needed for the class-based probabilities is about one
third of that of lexical tables. As expected, the performance is not
as good as the lexical model for the more common patterns.

The classes that were produced with divergence (\ref{diverg}) did not
perform as well, illustrating the problems we mentioned earlier.

Since the lexical probabilities perform better on more frequent events
and class-based probabilities better on infrequent events, a logical
next step is combining them. The score of {\bf combined} illustrates
that this creates a gain in entropy of about 2.7\%.

\begin{table}[thbc]
\begin{center}
\caption{Cross Entropy on Test Data}
\begin{tabular}{|l|l|l|l|} \hline
method & All Data & Occurred & Not Occurred \\ \hline
lexical    &  1.862    &   0.729   &   3.178   \\
classes  &  1.899    &  0.988    &  2.958  \\
divergence &  2.198   &   1.423   &   3.098 $\star$  \\
combined   & 1.811 & 0.707   &   3.093 $\star$ \\ \hline
\end{tabular}
\label{mainres}
\end{center}
\end{table}


\section{Applications}

A first application of this work, of which we carried out a first step in this
article, is the lexicographical one of studying word behavior. Some properties
of words, such as the peculiar behavior of the present participle {\em including} or the
similarities between prepositions such as {\em though} and {\em while} only becomes
clear once the corpus data is analyzed in the way we described. When inspecting
manually, the binary word tree representation appears to be the most easy to
understand.

A second application of the binary word tree can be found in decision-tree based
systems such as the SPATTER parser \cite{magerman:acl} or the ATR Decision-Tree
Part-Of-Speech Tagger, as described by Ushioda \cite{ushioda96}. In this case it
is necessary to use a hard-clustering method, such that a binary word tree can
be constructed by the clustering process, as we did in the example in the
previous sections. 

A decision tree classifies data according to its properties by asking successive
(often binary) questions.  In the case of a part of speech tagger or a parsing
system, it is particularly important for the system to ask lexicalizing
questions.  However, questions about individual words such as ``Is this the word
{\em display}?'' are not efficient on a large scale since it would easily
require thousands of questions. A binary tree allows one to separate the
vocabulary into two parts at every question, which is efficient when these two
parts are maximally different.  In that case it is possible to obtain as much
information as possible with a small number of questions.  A condition for this
application is that trees may not be very unbalanced, as the extreme case of a
linear tree becomes equal to asking word-by-word. As mentioned, the method we
suggest did not produce a very unbalanced tree for the parts of speech in the
Wall Street Journal Treebank.

A third application can be found in Information Retrieval. This can be seen from
the example of {\em including}: words with such behavior have little content
because they have a rather functional role in the sentence. This can be seen in
the sentence {\em ``Safety advocates, including some members of Congress,...''}
where terms such as {\em Safety advocates} or {\em members of Congress} indicate
much more about the topic of the sentence than the relatively empty word
{\em including.} It is possible to cluster words and decide which clusters are
likely to indicate the topic, and which are not likely to do so.  For this
application a wider variety of algorithms can be applied; words can for example
be {\em exchanged} or {\em shuffled} between classes to improve the entire
model.

A fourth application is class-based smoothing of interpolated $n$-gram models.
The co-occurrence based classes described in the literature are, of course,
created with this as objective function, but on the other hand the classes we
suggest clearly contain information that is inaccessible to co-occurrence based
classes. It is possible that a combination of co-occurrence based classes and
classes of syntactic behavior would give better results, but this would have
to be demonstrated experimentally.

In some of these applications words with a low frequency cannot be ignored
because of their quantity, but at the same time the algorithm cannot rely too
heavily on their observations. A possible solution is to carry out clustering
without these words, and distribute the low-frequency words over the leaves of
the tree afterwards. A solution along this line was chosen for co-occurrence
based clustering in \cite{mcmahon96}, where a first algorithm handles more
frequent words, and a second algorithm adds the low-frequency words afterwards.

It must be added that the classes are based on words with disambiguated
part of speech. The correct class can only be decided unambiguously after the
part of speech tag has been decided. Otherwise, the possible classes will have
to be combined in some way.

\section{Conclusion}

We have presented a method which constructs classes of words with
similar syntactic behavior, or binary trees that reflect word
similarity, by clustering words using treebank data. In this way it is
possible to discover particular types of behavior, such as the
peculiar behavior of the present participle {\em including}, verbs
that modify an entire clause (raising verbs), nouns that prefer either
subject position or object position, or prepositions that prefer
locative phrases.

Most of the classes found in this way would not be found if clustering were
performed on the basis of co-occurrences, as has been described in the
literature. For example, the verbs [{\em tend, plan, continue, want, need, seem,
  appear}] share a particular sentence structure rather than, say, the sort of
noun that becomes the object. On the other hand, semantical similarities such as
the one in the group [{\em director, chief, professor, commissioner, commander,
  superintendent}], are ignored.

As became clear from the case study of prepositions, the clustering process
reveals similarities in the syntactic structure in which words appear which in
some cases can be clearly felt by intuition. For example, the words {\em in},
{\em on} and {\em at} often are the head of locative prepositional phrases, and
a preposition such as {\em within} usually is the head of a temporal
prepositional phrase. Using this method these intuitions can be quantified.

The experiment based on parameter estimation also indicated that the
classification of words into groups based on syntactical behavior results in
classes that reflect their behavior, and can to some extent add to the
information available about the bigram distribution we described, in the face of
sparse data.

The applications of this work are to be found in the possibility to
create groups of words that share a desired property. The most typical
one is that of decision-trees, which need to have a pool of questions
about the properties of the words that are being considered. For
example, if the word {\em including} is encountered, the chance that
this is the start of a prepositional phrase increases
dramatically. The contribution of this work is in giving a way to
quantify these properties. \footnote{We refer to \cite{ik:phd}
for more recent work showing how this can improve a practical system.}



\acknowledgment

We would like to express our appreciation to the reviewers. This article has
benefited greatly from their valuable comments and criticisms.

\bibliographystyle{nlpbbl}

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Bahl, Jelinek, \BBA\ Mercer}{Bahl et~al.}{1983}]{bahl83}
Bahl, L.~R., Jelinek, F., \BBA\ Mercer, R.~L. \BBOP 1983\BBCP.
\newblock \BBOQ A maximum likelihood approach to continuous speech
  recognition\BBCQ\
\newblock {\Bem IEEE Transactions on Pattern Analysis and Machine
  Intelligence}, {\Bem PAMI-5\/}(2), 179--190.

\bibitem[\protect\BCAY{Black, Jelinek, Mercer, \BBA\ Roukos}{Black
  et~al.}{1992}]{black:dtm}
Black, E., Jelinek, F., Mercer, R., \BBA\ Roukos, S. \BBOP 1992\BBCP.
\newblock \BBOQ Decision Tree Models Applied to the Labeling of Text with
  Parts-of-Speech\BBCQ\
\newblock In {\Bem Proceedings DARPA Speech and Natural Language Workshop},
  \BPGS\ 117--121.

\bibitem[\protect\BCAY{Brown, {Della Pietra}, {d}e{S}ouza, Lai, \BBA\
  Mercer}{Brown et~al.}{1992}]{brown:clust}
Brown, P.~F., {Della Pietra}, S.~A., {d}e{S}ouza, P.~V., Lai, J.~C., \BBA\
  Mercer, R.~L. \BBOP 1992\BBCP.
\newblock \BBOQ Class-Based n-gram Models of Natural Language\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bem 18\/}(4), 467--479.

\bibitem[\protect\BCAY{Charniak}{Charniak}{1997}]{charniak97}
Charniak, E. \BBOP 1997\BBCP.
\newblock \BBOQ Statistical Parsing with a Context-free Grammar and Word
  Statistics\BBCQ\
\newblock In {\Bem Proceedings of the Fourteenth National Conference on
  Artificial Intelligence, AAAI}, \BPGS\ 598--603.

\bibitem[\protect\BCAY{Collins}{Collins}{1996}]{collins96}
Collins, M.~J. \BBOP 1996\BBCP.
\newblock \BBOQ A New Statistical Parser Based on Bigram Lexical
  Dependencies\BBCQ\
\newblock In {\Bem Proceedings of the 34th Annual Meeting of the Association
  for Computational Linguistics}, \BPGS\ 184--191.

\bibitem[\protect\BCAY{Dagan, Markus, \BBA\ Markovitch}{Dagan
  et~al.}{1993}]{dagan:context}
Dagan, I., Markus, S., \BBA\ Markovitch, S. \BBOP 1993\BBCP.
\newblock \BBOQ Contextual Similarity and Estimation from Sparse Data\BBCQ\
\newblock In {\Bem Proceedings of the 31st Annual Meeting of the Association
  for Computational Linguistics}, \BPGS\ 164--171.

\bibitem[\protect\BCAY{Dagan, Pereira, \BBA\ Lee}{Dagan
  et~al.}{1994}]{dagan:sym}
Dagan, I., Pereira, F., \BBA\ Lee, L. \BBOP 1994\BBCP.
\newblock \BBOQ Similarity-Based Estimation of Word Cooccurrence
  Probabilities\BBCQ\
\newblock In {\Bem Proceedings of the 32nd Annual Meeting of the Association
  for Computational Linguistics}, \BPGS\ 272--278.

\bibitem[\protect\BCAY{Fujio \BBA\ Matsumoto}{Fujio \BBA\
  Matsumoto}{1997}]{fujio97eng}
Fujio, M.\BBACOMMA\  \BBA\ Matsumoto, Y. \BBOP 1997\BBCP.
\newblock \BBOQ Japanese Dependency Structure Analysis based on
  Statistics\BBCQ\
\newblock In {\Bem Information Processing Society Japan, SIG Notes 97-NL-117},
  \BPGS\ 83--90.

\bibitem[\protect\BCAY{Grefenstette}{Grefenstette}{1992}]{gref:adj}
Grefenstette, G. \BBOP 1992\BBCP.
\newblock \BBOQ Finding Semantic Similarity in Raw Text: the {D}eese
  Antonyms\BBCQ\
\newblock In {\Bem Working Notes, Fall Symposium Series, AAAI}, \BPGS\ 61--68.

\bibitem[\protect\BCAY{Hogenhout \BBA\ Matsumoto}{Hogenhout \BBA\
  Matsumoto}{1996}]{ik:boek}
Hogenhout, W.~R.\BBACOMMA\  \BBA\ Matsumoto, Y. \BBOP 1996\BBCP.
\newblock \BBOQ Training Stochastical Grammars on Semantical Categories\BBCQ\
\newblock In Stefan~Wermter, E.~R.\BBACOMMA\  \BBA\ Scheler, G.\BEDS, {\Bem
  Connectionist, Statistical and Symbolic Approaches to Learning for Natural
  Language Processing}, \BPGS\ 160--172. Springer.

\bibitem[\protect\BCAY{Hogenhout}{Hogenhout}{1998}]{ik:phd}
Hogenhout, W.~R. \BBOP 1998\BBCP.
\newblock {\Bem Supervised Learning of Syntactic Structure}.
\newblock Ph.D.\ thesis, Nara Institute of Science and Technology.
\newblock NAIST-IS-DT9451207.

\bibitem[\protect\BCAY{Jardino \BBA\ Adda}{Jardino \BBA\ Adda}{1993}]{jardino}
Jardino, M.\BBACOMMA\  \BBA\ Adda, G. \BBOP 1993\BBCP.
\newblock \BBOQ Automatic Word Classification Using Simulated Annealing\BBCQ\
\newblock In {\Bem ICASSP 93}, \BPGS\ II 41--44.

\bibitem[\protect\BCAY{Jelinek, Lafferty, Magerman, Mercer, Ratnaparkhi, \BBA\
  Roukos}{Jelinek et~al.}{1994}]{jelinek94}
Jelinek, F., Lafferty, J., Magerman, D., Mercer, R., Ratnaparkhi, A., \BBA\
  Roukos, S. \BBOP 1994\BBCP.
\newblock \BBOQ Decision Tree Parsing Using a Hidden Derivation Model\BBCQ\
\newblock In {\Bem ARPA: Proceedings of the Human Language Technology
  Workshop}, \BPGS\ 272--277.

\bibitem[\protect\BCAY{Kneser \BBA\ Ney}{Kneser \BBA\ Ney}{1993}]{kneser}
Kneser, R.\BBACOMMA\  \BBA\ Ney, H. \BBOP 1993\BBCP.
\newblock \BBOQ Improved Clustering techniques for Class-Based Statistical
  Language Modelling\BBCQ\
\newblock In {\Bem Proceedings of European Conference on Speech Communication
  and Technology}, \BPGS\ 973--976.

\bibitem[\protect\BCAY{Magerman}{Magerman}{1995}]{magerman:acl}
Magerman, D.~M. \BBOP 1995\BBCP.
\newblock \BBOQ Statistical Decision-Tree Models for Parsing\BBCQ\
\newblock In {\Bem Proceedings of the 33d Annual Meeting of the Association for
  Computational Linguistics}, \BPGS\ 276--283.

\bibitem[\protect\BCAY{Martin, Liermann, \BBA\ Ney}{Martin
  et~al.}{1995}]{martin}
Martin, M., Liermann, J., \BBA\ Ney, H. \BBOP 1995\BBCP.
\newblock \BBOQ Algorithms for Bigram and Trigram Word Clustering\BBCQ\
\newblock In {\Bem Proceedings of European Conference on Speech Communication
  and Technology}, \BPGS\ 1253--1256.

\bibitem[\protect\BCAY{McMahon \BBA\ Smith}{McMahon \BBA\
  Smith}{1996}]{mcmahon96}
McMahon, J.~G.\BBACOMMA\  \BBA\ Smith, F.~J. \BBOP 1996\BBCP.
\newblock \BBOQ Improving Statistical Language Model Performance with
  Automatically Generated Word Hierarchies\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bem 22\/}(2), 217--247.

\bibitem[\protect\BCAY{Pereira \BBA\ Tishby}{Pereira \BBA\
  Tishby}{1992}]{pereira:distr}
Pereira, F.\BBACOMMA\  \BBA\ Tishby, N. \BBOP 1992\BBCP.
\newblock \BBOQ Distributional Similarity, Phase Transitions and Hierarchical
  Clustering\BBCQ\
\newblock In {\Bem Working Notes, Fall Symposium Series, AAAI}, \BPGS\
  108--112.

\bibitem[\protect\BCAY{Pereira, Tishby, \BBA\ Lee}{Pereira
  et~al.}{1993}]{pereira:clust}
Pereira, F., Tishby, N., \BBA\ Lee, L. \BBOP 1993\BBCP.
\newblock \BBOQ Distributional Clustering of {E}nglish Words\BBCQ\
\newblock In {\Bem Proceedings of the 31st Annual Meeting of the Association
  for Computational Linguistics}, \BPGS\ 183--190.

\bibitem[\protect\BCAY{Ueberla}{Ueberla}{1995}]{ueberla}
Ueberla, J. \BBOP 1995\BBCP.
\newblock \BBOQ More Efficient Clustering of N-Grams for Statistical Language
  Modeling\BBCQ\
\newblock In {\Bem Proceedings of European Conference on Speech Communication
  and Technology}, \BPGS\ 1257--1260.

\bibitem[\protect\BCAY{Ushioda}{Ushioda}{1996}]{ushioda96}
Ushioda, A. \BBOP 1996\BBCP.
\newblock \BBOQ Hierarchical Clustering of Words and Application to NLP
  Tasks\BBCQ\
\newblock In {\Bem Proceedings of the Fourth Workshop on Very Large Corpora}.

\end{thebibliography}


\begin{biography}

\biotitle{}

\bioauthor{Wide R. Hogenhout}
{ Wide R. Hogenhout received his first degree in computer science from
the Free University in Amsterdam in 1993. In 1995 he received his
master degree from the Nara Institute of Science and Technology.
Currently he is enrolled in the Ph.D. course at the Nara Institute of
Science and Technology. From April 1998 he will join the Canon Research
Centre Europe (CRE). He is a member of the Information Processing
Society of Japan and the Association of Natural Language Processing.
His current interests include broad coverage parsing and corpus based
language analysis.}

\bioauthor{Yuji Matsumoto} { Yuji Matsumoto received his first and master
  degrees in information science from Kyoto University in 1977 and 1979. He
  joined the Electrotechnical Laboratory (ETL) in 1979. While affiliated to the
  ETL, he was an academic visitor at the Imperial College of Science and
  Technology (England), and head of the first laboratory of the ICOT research
  center.  He moved to Kyoto University as associate professor in 1988. In 1990
  he received a doctoral degree in engineering from Kyoto University.  He has
  been a professor at Nara Institute of Science and Technology since 1993.  His
  current interests include linguistic knowledge acquisition.  }

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

\end{biography}

\end{document}


