\documentstyle[epsf,nlpbbl]{jnlp_e_b5}

\setcounter{page}{3}
\setcounter{巻数}{5}
\setcounter{号数}{4}
\setcounter{年}{1998}
\setcounter{月}{10}
\受付{October}{30}{1997}
\再受付{February}{17}{1998}
\再々受付{April}{7}{1998}
\採録{July}{10}{1998}

\setcounter{secnumdepth}{2}

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

\etitle{A Hybrid Approach for Resolving Ambiguities \\ 
\hspace*{26mm}in Coordinate Structures}

\eauthor{Haodong Wu\affiref{ElecUniv}        \and
        Teiji Furugori\affiref{ElecUniv}}

\headauthor{Wu,~H. and Furugori,~T.}

\headtitle{Resolving Ambiguities in Coordinate Structures}

\affilabel{ElecUniv}
          {The University of Electro-Communications, Department of Computer Science}
          {The University of Electro-Communications, Department of Computer Science}

\eabstract{
This paper describes a  method  in determining syntactic structure 
for coordinate constructions.   It is based on  the information taken from semantic 
similarities, selectional restrictions, and  some other linguistic cues.
We discuss the role the information plays in resolving ambiguities that
appear in coordinate constructions, describe the means of acquiring the
necessary information automatically
from two on-line corpora and a lexical database, and devise two algorithms for
disambiguating coordinate constructions.  An experiment that follows 
shows effectiveness  of our  method and its applicability to  resolving
ambiguities in  some other syntactic structures.
}

\ekeywords{Coordinate Construction, Disambiguation,
Semantic Similarity, \\Selectional Restriction, Modification Relation}

\begin{document}

\maketitle


\section{Introduction}


Syntactic ambiguity appears, among others, in coordinate constructions.
It is an annoying problem in analyzing structure and meaning of a 
sentence.  A parser, for instance, is to detect the scope of a
coordinate structure and identify its inner modification relations. 
However, the current parsers (e.g., the Link parser) often fail to
handle the problem and/or produce a large number of parses.

    There are a few computational studies that have tried to resolve
ambiguities in coordinate constructions (e.g., Paritong, 1992; Cooper,
1991; Bayer, 1996). For example,  Kurohashi and Nagao (1994), in
analyzing long Japanese sentences, proposed a syntactic analysis
method for detecting conjunctive structures by using lexical similarity 
and structural parallelism.  
Mela and Fouquer\'e (1996) used a direct process to
determine the scope of a coordinate structure based on the concept of
functor, argument and subcategorization. Unfortunately, neither of them
 has sufficiently dealt with  the syntactic structure of a coordination
especially when a coordinator (such as {\it and, or} and comma) has two or
possibly more preceding and succeeding constituents.


We in this paper propose a method for determining the structure 
of a coordinate construction using information on
similarities, selectional restrictions, and other
linguistic cues. In Section 2 we identify the problem and describe the 
ideas behind our method in Section 3.  We give disambiguation
algorithms, show an disambiguation experiment,  and evaluate its
results in Section 4.  In Section 5  we suggest an 
applicability of our method to resolving other syntactic ambiguities.



\section {Modification Relation in Coordination}

 Resolving  ambiguities in a coordinate construction is to determine
the way of conjoining constituents (words, phrases, or clauses) and/or  to
determine the scope of coordination, i.e., immediacy relations among the
constituents involved.  For instance, in {\it sweet and sour pork}, the right
immediacy relation is {\it ((sweet and sour) pork)} rather than {\it (sweet and
(sour pork))}.

     Consider other examples.

 \vspace*{4mm}

 \hspace*{5mm} (1) Tom is a ((stock and estate) keeper).

 \hspace*{5mm} (2) John is a (student and (chess player)).

 \hspace*{5mm} (3) Old men and women were left at the village. 

 \hspace*{5mm} (4) The old lady bought ((fresh (meats, vegetables, flowers)) and 
                   some canned 

 \vspace*{-1mm} \hspace*{10.5mm}foods) at a discount store.  

\vspace*{4mm} 
In each of these sentences, a noun or an adjective that appears in the
left hand side of coordinator(s) has two (or more) modificant candidates: it may or 
may not modify the head noun in the right hand side.

In (1), {\it stock} and {\it estate} should be conjoined to modify
{\it keeper}\footnote{In this case, the coordination
of {\it stock and estate keeper} is considered to be the reduced form
of {\it stock keeper and estate keeper}.}. In (2),  no modification 
relation exists between {\it student} and {\it player} and its 
interpretation should be (student and (chess player)).

  We are able to make unique interpretation for (1), (2) and (4).
But we may have two interpretations for (3).

 \vspace*{4mm}

 \hspace*{5mm} (3a) {\it Women} are left at the village and
 {\it old men} were left at the village.


 \hspace*{5mm} (3b) {\it Old men} were left at the village and
 {\it old women} were left at the village.


 \vspace*{4mm}

    Later in the paper, we try to resolve the ambiguities by determining the modification
relation in the coordinate constructions (CCs) such as in (1) to (4). 


\section{Identifying Modification Relation in Coordination}

We have found through linguistic observations that a variety of
information supplies important cues for disambiguation.  Some of them
are computable and effectively used in a computer model of
disambiguation. The ones we thought most important include:
similarities  in syntactic forms and/or meanings, selectional restrictions,  and
orthographic forms.

\subsection{Linguistic Observations}


\hspace*{-5mm}{\bf Similarities in Syntactic Forms and Meanings}   \hspace*{4mm}We see
that similarities on forms and meanings are crucial to determine the
structure of a coordinate construction.

     If the modifier is not an adjective, for instance, it is likely
that two constituents before and after the coordinator are conjoined 
when they belong to the same subcategory and match in number: 

\vspace*{4mm}

 \hspace*{5mm} (5) ((business and management) sections)


 \hspace*{5mm} (6) (businesses and (culture activities))


\vspace*{4mm}

In the  following examples, 

\vspace*{4mm}
 \hspace*{5mm} (7) ((research and development) section)



 \hspace*{5mm} (8) (researcher and (system engineer))

\vspace*{4mm}
\hspace*{-5mm}it is obvious that the {\it research} and {\it development} have more
in common in meaning than {\it research} and {\it section}, and that
{\it researcher} and  {\it engineer} are semantically
more similar than {\it researcher} and {\it system}.  Likewise, we see:


\vspace*{3mm}

 \hspace*{5mm}    (9) (lovely (cats and dogs))

 \hspace*{9mm}      *((lovely cats ) and dogs)


 \hspace*{5mm}    (10) ((Lovely pets) and books) are his best friends.

 \hspace*{11mm}       *(Lovely (pets and books)) are his best friends.

\vspace*{3mm}	
\hspace*{-5mm}{\bf Selectional Restrictions} \hspace*{4mm}Consider the sentence:


 \vspace*{4mm}

 \hspace*{5mm}(11) Peter likes ((green vegetables) and (music)).


 \vspace*{4mm}
\hspace*{-5mm}We know in (11) that {\it green} as a color can be used to modify 
concrete entities like {\it vegetables}, but not abstract one like
{\it music}. This means that selectional restriction (SR),  a
semantic restriction imposed on lexical items when
forming a sentence, is an important factor to determining the structure
of coordinate constructions.  In this paper, we discuss SR in the
context of adj+n1+and+n2 and its extension (e.g.,
adj $n_{1}, \ldots, n_{k}$)\footnote{Hereafter, {\it and} in adj+n1+and+n2 and 
in n1+and+n2+n3 represents
a coordinator such as {\it and, or,} comma, and the like.}.

\vspace*{3mm}
\hspace*{-5mm}{\bf Other Linguistic Cues}　\hspace*{4mm}Orthographic forms often play
an important role in disambiguating the structures of coordinate
constructions.  It is likely that all nouns can be conjoined when  they are in capital 
forms. An example:  


\vspace*{4mm}

\hspace*{5mm}(12) ((Research and Development) Section)

\vspace*{4mm}

When the conjoined nouns in a coordinate structure are preceded 
by a determiner, the usual
interpretation is that the determiner applies to the conjoins:


\vspace*{4mm}

\hspace*{5mm}(13) {\it Old men and women} were left to organize the community.


\vspace*{4mm}
\hspace*{-5mm}The structure (old (men and women)) is more likely
than ((old men) and women) because there is a tendency that the determiner
is not repeated in the noninitial conjoins, e.g., {\it the
(man and women)}(Quirk et al. 1985). 


\subsection{Computational Measurements of Similarities}

Semantic similarity has been  measured in a number of ways (e.g., Resnik
1993; Kozima and Furugori, 1994; Dagan et al., 1994). Many researchers
opt to investigate methods for deriving measures of semantic 
similarity among words based on distributional behavior observed in corpora or 
machine-readable dictionaries. We however employ a hybrid 
method for combining the quantitative method with an existing
broad-coverage source of lexical knowledge.  
 
To capture the similarity between two words in context, we consider 
two kinds of semantic relations useful and effective: {\it taxonomic 
relation} and {\it co-occurrence relation}. 

Computationally, one way of measuring semantic similarity is to
use the taxonomic relations in the WordNet (Miller, 1990),
a widely used lexical database.
The WordNet has a thesaurus-like structure in which lexical information 
about nouns, verbs, adjectives 
and adverbs is put in terms of word meanings, rather than word forms. 
The most important part is a word sense network. A word sense node in this network is a group
of strict synonyms called ``synset'' which is regarded as a basic object in 
the WordNet. Each sense of a word is mapped onto a synset and all word sense 
nodes in the WordNet are linked by a variety of semantic relationships like IS-A (
hypernymy$/$hyponymy), PART-OF(meronymy$/$holonymy) and {\it antonymy}.
The IS-A relationship being dominant, ``synset's'' are grouped into hierarchies as is
shown in Figure 1. 

\vspace*{-2mm}
\begin{figure}[hbp]
 \begin{center}
  \epsfile{file=fig3_2.eps,scale=0.6}
 \end{center}
\end{figure}
\vspace*{-8mm}
\hspace*{1cm}Figure 1: Semantic Relations among Lexical Concepts in WordNet


\vspace*{5mm}

We found that the {\it antonymy} relationship appears often in CCs 
(e.g., {\it brother and sister, man and woman,} and {\it boy and girl}) and
shows a strong tie between two nouns in the coordinate structure like (14). 

 \vspace*{4mm}

 \hspace*{5mm}(14) (cheerful (boys and girls))

 \vspace*{4mm}
Another way of measuring semantic  similarity is to use the  mutual
information(MI) (Church and Hanks, 1990). It may be taken from the co-occurrence
relations using two corpora: the EDR English Corpus and Brown
Corpus\footnote{EDR English Corpus, compiled by Japan Electronic Dictionary Research
Institute, Ltd., contains 160,000 sentences with annotated morphological, 
syntactic and semantic information. The Brown Corpus was compiled in the
early 1960s at Brown University, USA, under the direction of W. Nelson
Francis and Henry Kucera. It contains 500 text samples representing 15 categories 
of American English texts printed in 1961.}. 

To decide the syntactic structure of any CC in the form of n1+and+n2+n3, we need to
determine the degree of similarity between n1 and n2, and the similarity between n1 and n3.
Here we use the method similar to the one proposed by Dagan, Marcus and 
Markovitch (1995) and consider that two words are similar if they have similar average 
mutual information values with other words in the lexicon.

We define the similarity between two words $w_1$ and $w_2$ when appearing with an
adjacent word $w$. In an example,

\vspace*{4mm}

\hspace*{5mm}(15) {\it new} books and hamburgers

\vspace*{4mm}
\hspace*{-5mm}where  $w_1$, $w_2$, and $w$ are {\it book, hamburger} and
{\it new}, respectively.  We can measure two similarities the
{\it left side similarity} and {\it right side similarity}. {\it w} comes to
the left of $w_1$ and $w_2$ in the former  and
the right side of $w_1$ and $w_2$ in the latter as are shown for {\it young}
in (16) and {\it investigation} in (17).

\vspace*{4mm}

\hspace*{5mm}(16) {\it young} nations and superpowers

\hspace*{5mm}(17) finance and market {\it investigation}

\vspace*{4mm}

The {\it left side similarity} and the {\it right side similarity} are defined as:

\vspace*{2mm}
\begin{equation}
  sim_L(w_1,w_2,w) =
\frac{min(I(w,w_1),I(w,w_2))}{max(I(w,w_1),I(w,w_2))} 
\end{equation} 


\begin{equation}
  sim_R(w_1,w_2,w) =
\frac{min(I(w_1,w),I(w_2,w))}{max(I(w_1,w),I(w_2,w))} 
\end{equation} 


\vspace*{4mm}
\hspace*{-5mm}here, for two words x and y, I(x,y) is MI between x and y,
where x is on the left side of y, and I(y,x) is MI between y and x, where x is on the
right side of y.  I(x,y) is defined as:

\vspace*{2mm}
\begin{equation}  
I(x,y) = log_2 \frac{N*f(x,y)}{f(x)f(y)}
\end{equation}

\vspace*{4mm}
\hspace*{-5mm}here $N$  is the size of the corpus used in the estimation,
$f(x,y)$ is the frequency of the co-occurrence, and
$f(x)$ and $f(y)$ those of individual words.


The context word $w$ may appear in either side $w_1$, or in either side of $w_2$. We 
define the similarity between $w_1$ and $w_2$ by:


\vspace*{2mm}

\begin{equation}
  sim(w_1,w_2) = \frac{\sum_{w \in lexicon}(min(I(w,w_1),I(w,w_2))+
min(I(w_1,w),I(w_2,w)))}{\sum_{w \in lexicon}(max(I(w,w_1),I(w,w_2))+
max(I(w_1,w),I(w_2,w)))}
\end{equation} 

\vspace*{4mm}
\hspace*{-5mm}here, $w$ may be a verb, a noun, an
adjective, or a phrase like {\it agree with} which is adjacent to $w_1$ or $w_2$.

\clearpage
Often the word pairs from $w$, $w_1$ and $w_2$ are unobserved in the
corpus being used.  This problem is known as the sparse data problem.   
There are a number of methods for dealing with this problem  
(e.g., Resnik, 1993; Dagan et al., 1995).  
Our solution in this paper is to use word class in a thesaurus to
deal with this problem. We use the synonym sets $C_1$ and $C_2$
in the WordNet to replace $w_1$ and $w_2$.
In this case, the similarity between them is estimated by:

\vspace*{2mm}    

\begin{equation}
  sim(w_1,w_2) = \frac{\sum_{w \in lexicon}(min(I(w,C_1),I(w,C_2))+
min(I(C_1,w),I(C_2,w)))}{\sum_{w \in lexicon}(max(I(w,C_1),I(w,C_2))+
max(I(C_1,w),I(C_2,w)))}
\end{equation}


\vspace*{4mm}
\hspace*{-4mm}here the mutual information, take $I(w,C_1)$ for example, is estimated
by:

\vspace*{2mm}
\begin{equation}
I(w,C_1)\approx log_2 \frac{N*f(w,C_1)}{f(w)f(C_1)}
\end{equation}

\vspace*{4mm}
\hspace*{-5mm}$C_1$ is the word class that respectively contains $w_1$, $f(C_1)$ the
number of occurrences of all the words included in the word class $C_1$, 
and $f(w,C_1)$ is the number of
co-occurrences between the word $w$ and the word class $C_1$. 


\subsection{Selectional Restrictions as Constraints}

   Selectional restrictions(SRs) are often defined on an empirical basis 
using AI(artificial intelligence) techniques. Recently research
efforts have turned to corpus-based methods to define and acquire them. 
Along the line, we search a new approach for finding SRs using on-line corpora and 
a lexical database. 

   We view SR as negative information, a constraint between two
words. The information on SRs may be computed from  corpora: for a particular
adjective and a particular noun, we try to find 'similar' words and then check if they
co-occur in the corpora.  If no co-occurrences are observed in the
corpora, we assume that there is a SR between the adjective and the noun.

A problem we encounter here  is how to find 'similar' words. It has
been proven by an experiment that
similar words generated by corpus-based clustering methods does not
work well (Grefenstette 1993). We choose to
acquire similar words from a taxonomy (the WordNet).



It seems to be reasonable for a noun to use its direct 
hypernym (father node in IS-A hierarchy in the WordNet) and
hyponyms of the hypernym (the siblings of the noun) as similar
words. But it does not work for an adjective. 
A compromising measure for an adjective is to use synonyms rather than hypernyms as
similar words, e.g., \{pure,unmixed,undiluted\} for {\it pure}.

Thus, if n2 or its similar words co-occur with adj or its synonyms (in the WordNet)
in the corpora (the EDR English corpus and the Brown corpus), we may conclude
that the CC has the structure (adj (n1 and n2)). Otherwise, it would be
((adj n1) and n2) as there is a SR between adj and n2. Take (18) for an example,


\vspace*{4mm}

\hspace*{5mm}(18) ((Fresh air) and sunshine) bring me health and
feelings of joy.

\vspace*{4mm}
\hspace*{-4mm}We are sure that {\it fresh air and sunshine} has the structure 
{\it ((fresh air) and sunshine)} as no co-occurrence between 
the synonyms of {\it fresh} and the similar words of
{\it sunshine} is found.



\section{Disambiguation for Structure of Coordinate Constructions}

We have devised disambiguation algorithms based on what we have described in section 3.
Algorithm 1 below is for CCs in the form adj+n1+and+n2 and algorithm 2 is for CCs in the form
n1+and+n2+n3. 


\vspace*{4mm}

\hspace*{-5mm}{\bf Algorithm 1: Disambiguation of CCs in the form adj+n1+and+n2}

\vspace*{2mm}
{\small
\begin{enumerate}
\vspace*{-1mm}
 \item Check adj+n2 in the corpora. If it is observed, produce 
(adj (n1 and n2)).

\vspace*{-1mm}
 \item Otherwise, if there is a synonym of adj and a synonym of
n2 and if they co-occur in the corpora, produce (adj (n1 and n2)).

\vspace*{-1mm}
 \item Otherwise, create a class which includes n2, its
parent (hypernym), and its siblings (the hyponyms of the hypernym) in
IS-A hierarchies of the WordNet; If no member in this class  
co-occurs with adj and any of its synonyms, produce ((adj n1) and n2).

\vspace*{-1mm}
 \item Otherwise, produce (adj (n1 and n2)) as a statistics-based
default.

\end{enumerate}
}


\vspace*{5mm}

\hspace*{-5mm} {\bf Algorithm 2: Disambiguation of CCs in the form n1+and+n2+n3}

\vspace*{2mm}
{\small
 \begin{enumerate}

\vspace*{-1mm}
 \item If all of the three nouns are capitalized, produce ((n1 and n2) n3).

\vspace*{-1mm}
 \item Otherwise,

(a) if n1 and n2 match in number and n1 and n3 do not,
 produce ((n1 and n2) n3).

\vspace*{-1mm}
 (b) if n1 and n3 match in number and n1 and n2 do not,
 produce (n1 and (n2 n3)).

\vspace*{-1mm}
 \item Otherwise,

 (a) if n1 is the antonym of n2, produce ((n1 and n2) n3);

\vspace*{-1mm}
 (b) if n1 is the antonym of n3, produce (n1 and (n2 n3)).

	
\vspace*{-1mm}
 \item Otherwise,


 (a) if sim(n1,n2)$>=$sim(n1,n3), produce ((n1 and n2) n3).


 (b) if sim(n1,n2)$<$sim(n1,n3), produce (n1 and (n2 n3)).
 \end{enumerate}
}

\vspace*{4mm}
\hspace*{-5mm}{\bf Experimental Results} \hspace*{4mm}To evaluate the performance of 
the disambiguation algorithm, we randomly selected two sets of
300 coordinate structures of the
form adj+n1+and+n2 and n1+and+n2+n3 from on-line CNN news using the
method proposed by  Mela and Fouquer\'e (1996)  and ran
the algorithms on a computer.


Table 1 shows the result for disambiguating CCs of adj+n1+and+n2.
Here, the first column lists each step in Algorithm 1. The second column 
indicates the recall rate of coordinations resolved in each step.
The third column shows the number of coordinations processed
and the fourth column shows success rates. As is shown here, the overall 
success rate is 87.7\%. 



\vspace*{4mm}

 \hspace*{15mm}Table 1: Experimental Results on Testing adj+n1+and+n2
 \vspace*{2mm}
 \begin{quote}
 \begin{tabular}{|l|r|r|r|} \hline
   \makebox[50mm]{Step} & \makebox[19.8mm]{Recall} & \makebox[16mm]{Number} & \makebox[20mm]{Accuracy} \\ \hline \hline
    (1) directly observed pattern & 38.0\% & 114 & 100.0\% \\ \hline
    (2) indirectly observed pattern & 40.3\% & 75 & 86.7\% \\ \hline
    (3) selectional restriction & 46.8\% & 52 & 86.5\% \\ \hline
    (4) default & 100.0\% & 59 &  66.7\% \\ \hline \hline
    \hspace*{20mm}Total & 100.0\% & 300 & 87.7\% \\ \hline
 \end{tabular}
 \end{quote}

\vspace*{8mm}
Table 2 shows the result for disambiguating CCs of n1+and+n2+n3. The meaning of each column
is same as those in Table 1. The overall success rate of Algorithm 2 is 85.0\%.

 \vspace*{4mm}
 \hspace*{15mm}Table 2: Experimental Results on Testing
 \vspace*{2mm}
 n1+and+n2+n3\begin{quote}
 \begin{tabular}{|l|r|r|r|} \hline
   \makebox[46mm]{Step} & \makebox[20mm]{Recall} &
 \makebox[16mm]{Number} & \makebox[20mm]{Accuracy} \\ \hline \hline
    (1) orthographic form & 3.7\% & 11 & 100.0\% \\ \hline
    (2) antonym & 8.3\% & 24 & 95.8\% \\ \hline
    (3) similarity in form  & 38.8\% & 104 & 91.4\% \\ \hline
    (4) semantic similarity & 100.0\% & 159 & 79.2\% \\ \hline \hline
    \hspace*{18mm}Total & 100.0\% & 300 & 85.0\% \\ \hline
 \end{tabular}
 \end{quote}

 \vspace*{7mm}
The algorithms have adopted a back-off form to integrate different cues in the
disambiguation process and the reliable cues with certainty are used first 
to achieve a better overall performance. 
As we can see from the results, the cues (orthographic forms, syntactic
constraints, antonymy relation, observed patterns) with high success rates 
have comparatively low recall rates (from 3.7\% to 40.3\%); 
other cues, such as selectional restriction and semantic similarity, on the other hand,
have comparatively high recall rates with lower success rates.


\vspace*{4mm}
\hspace*{-5mm}{\bf Evaluation}  \hspace*{4mm}Table 3 shows the results of the 
performance achieved by our method and those by others for the structure of
n1+and+n2+n3. All these methods use the same data.
Here, (1) shows the result obtained from attaching the modifier to
the nearest head (Kimball, 1973), i.e., (n1 and
(n2 n3)); (2) shows the result of the
method proposed by Resnik (1993) in which class-based similarity
and a measure of noun-noun modification estimated from corpora are used in resolving
ambiguous coordinations; (3) shows the performance of our method;
and  (4) is the performance  of human judgment by three native
speakers who were just presented the words of n1, coordinator, 
n2 and n3 without surrounding contexts.


\vspace*{5mm}

\hspace*{12mm}Table 3: Comparison with Other Work for Determining n1+and+n2+n3

\vspace*{3mm}

\begin{quote}
\begin{center}
\begin{tabular}{|l|c|} \hline
  \makebox[52mm]{Method} & \makebox[36mm]{Success Rate}  \\ \hline
\hline
    (1) Closest attachment & 65.3\%  \\ \hline
    (2) Resnik's method & 80.7\% \\ \hline
    (3) Our method & 85.0\% \\ \hline
    (4) Average human  & 91.3\% \\ \hline
\end{tabular}
\end{center}
\end{quote}



\vspace*{7mm}

  The lower bound and the upper bound on the performance of our method
seem to be 65.3\% scored by the  simple heuristics of closest
attachment (1) and 91.3\% by  human beings (4). We can clearly see here that 
the performance of our method (3) is better than those of (1) and (2), and
is close to that of human beings. 

Table 4 shows the results achieved by our method and those by others for the structure of
adj+n1+and+n2. Here, each row of (1), (3), and (4) is analogous
to that in Table 3. (2) shows the result  from estimating the
strength of association between adj and n2 using the maximum mutual
information over their  classes (Resnik, 1993; Alves, 1996).

The performance by the closest attachment (1) is so poor that it would be
unusable in any real applications. The method (2) using maximum MI performed better.
But again ours is much better.
 
This is not to say our method is perfect, however. Selectional restrictions
do not work well in idiomatic or 
fixed expressions (e.g., {\it green peace}) or when the adjective has multiple
senses. 


\clearpage
\hspace*{10mm}Table 4: Comparison with Other Work for Determining adj+n1+and+n2

\vspace*{3mm}

\begin{quote}
\begin{center}
\begin{tabular}{|l|c|} \hline
  \makebox[54mm]{Method} & \makebox[34mm]{Success Rate}  \\ \hline
\hline
    (1) Closest attachment & 64.7\%  \\ \hline
    (2) Maximum MI & 82.3\% \\ \hline
    (3) Our method & 87.7\% \\ \hline
    (4) Average human  & 93.3\% \\ \hline
\end{tabular}
\end{center}
\end{quote}


\vspace*{8mm}


\hspace*{-5mm}Take (19), for instance,

\vspace*{3mm}

 (19) I bought some {\it soft balls and drinks} in a drugstore.

\vspace*{4mm}

The algorithm 1 produces the parse  (soft (balls and drinks)), but the
correct one should be ((soft balls) and drinks).


The judgment made by semantic similarity succeeded in about 80\% of the
cases (Table 2), but often failed when the co-occurrences are low and 
especially when the words involved are polysemous. 
We see that we need to use a larger corpus to overcome this problem.



\section{Discussion}

\hspace*{-5mm}{\bf Applications to Complex Coordinations and Nomial Compounds}
 \hspace*{4mm}The method presented in this paper can
be directly used for resolving complicated cases of coordinate structures (e.g., 
{\it freshman training and personal management system}). 
The coordinate structure 
of $n\_left_{1}+\dots+n\_left_{l}+and+n\_right_{1}+\ldots+n\_right_{k}$ can be quite complex. 
Theoretically, {\it l} or {\it k} may be a big number.
We found that in the most of the cases ($>$99.3\%), {\it l} 
is not greater than 2 and {\it k} is not greater than 3 in real texts, however. 
For a complex CC in form of n1+n2+and+n3+n4+n5, for
instance, we can use semantic similarity defined in formula (5)
 in Section 3 to 
find the word in the right hand side of the coordinator 
that is most similar to n2. Supposing n2 is similar 
to n4\footnote{in this case, sim(n2,n4)$>$sim(n2,n3) and sim(n2,n3)$>$sim(n2,n5) are
satisfied.}, 
we then check whether n1 co-occurs with n3 in pattern {\it n1 n3} in the corpora, 
if the answer is yes, then produce (n1 (n2 and (n3 n4)) n5), otherwise produce
(((n1 n2) and (n3 n4)) n5). Using this method, the analysis for CC
{\it freshman training and personal management system} is 
{\it (((freshmen training) and (personal management)) system)}; while for 
{\it food handling and storage procedure} the result turns to be
{\it ((food (handling and storage)) procedure)}. 
 
The method can also be applied to analyzing structures 
of nominal compounds. Consider the phrase {\it novice song bird feeder kit}, for instance.
Selectional restriction may play an important role in judging which constituent the
 adjective {\it novice} refers to in
 the candidates {\it song, bird, feeder, kit} and their combinations. 
Co-occurrence relation, on the other hand, is crucial to determining the structure 
of a nominal compound like {\it song bird feeder}. We may collect statistics to see if 
{\it song bird} is observed more often than {\it song feeder}.

\vspace*{3mm}
\hspace*{-5mm}{\bf Conclusion} \hspace*{4mm}
Resolving ambiguities in coordinate structure has a great importance for its applications
to text understanding and machine translation. It is crucial to information
retrieval, too (e.g., internet information retrieval).  
Given ``training system'' as a conjoined retrieval condition, for example, the phrase {\it
freshman training and personal management system} in the target text can be 
retrieved using the method presented in this paper, but it can hardly be found with
the current retrieval techniques.

   The disambiguation method proposed is scalable since it does not depend on any
handcrafted rules. It is strong at the sparse data 
problem also as
we use co-occurrences between semantic classes, rather than words,
extracted from a lexical database. 

   The disambiguation experiment has proven that our method for
disambiguating syntactic structures  is valid, effective, and useful
in practical applications. The performance of our method is significantly
better than those of other work.
We are certain that the performance can be improved further by
using a larger corpora that contribute to the precision for  estimating  semantic 
similarities and/or selectional restrictions. 

   The applicability of our method has an obvious limitation, however. It may not
be direct usable for
complicated coordinations of heavy NPs, VPs, Ss and the coordinations of different
categories (e.g., {\it I know his address and that he will come here tomorrow.}). 
To deal with various types of coordinations, we need to build a hybrid
disambiguation model which uses, beside what we have employed, more syntactic and
semantic constraints on coordinate structures that include
subcategorization, functor and argument (Mela and Fouquer\'e, 1996).    


\section*{Acknowledgments}

We gratefully thank the referee(s) for their acute comments and suggestions. They helped
us a lot to improve the quality of the manuscript.

\begin{thebibliography}{18}


\bibitem{alves96}

Alves, E.  (1996). ``The Selection of 
the Most Probable Dependency Structure in Japanese Using Mutual
Information.'' {\it Proceedings of the 34th Annual Meeting of ACL}, 372-374.

\bibitem{bayer} Bayer, S. (1996). ``The Coordination of Unlike
Categories.'' {\it Language,} 72(3):579-616.

\bibitem{church} Church, K. W. and  Hanks, P. (1990).  ``Word
 Association Norms, Mutual Information, and Lexicography.'' 
{\it Computational Linguistics}, 16(1):22-29.

\bibitem{cooper} Cooper, R. P. (1991). ``Coordination in
Unification-based Grammars.'' {\it
Proceedings of the 29th Annual Meeting of ACL,} 167-172.

\bibitem{dagan} Dagan, I.; Marcus, S.; and Markovitch S. (1995).
``Contextual Word Similarity and 
Estimation from Sparse Data.'' {\it Computer Speech and Language},
9:123-152.

\bibitem{grefen} Grefenstette, G. (1993). ``Evaluation Techniques for Automatic
Semantic Extraction: Comparing Syntactic and Window-based Approaches.''
Technical Report, Department of Computer Science, University of
Pittsburgh. 

\bibitem{hindle} Hindle, D. and Rooth, M. (1993). ``Structural Ambiguity
and Lexical Relations.'' {\em Computational Linguistics}, 19(1):103-120.


\bibitem{kimball} Kimball, J. (1973). ``Seven Principles of Surface
Structure Parsing in Natural Language.'' {\it Cognition}, 2:15-47.


\bibitem{kozi} Kozima, H. and Furugori, T. (1994). ``Segmenting
Narrative Text into Coherent Scenes.'' {\it Literary and Linguistic
Computing}, 9(1):13-19.


\bibitem{kuro} Kurohashi, S. and Nagao, M. (1994). ``A Syntactic Analysis
Method of Long Japanese Sentences Based on the Detection of Conjunctive
Structures.'' {\it Computational Linguistics}, 20(4):507-534.


\bibitem{mela} Mela, A. and Fouquer\'e, C. (1996). ``Coordination as a
Direct Process.'' {\it Proceedings of the 34th ACL Meeting}, 124-130. 


\bibitem{miller} Miller, G. (1990). ``WordNet: An On-Line Lexical
Database.'' {\it International 
Journal of Lexicograph,} 3(4) (special issue).


\bibitem{pari} Paritong, M. (1992). ``Constituent Coordination in HPSG.''
{\it KONVENS 92}, 228-237, Springer Verlag.

\bibitem{resnik} Resnik, P. S. (1993). ``Selection and Information: A
Class-Based Approach to Lexical Relationships.'' Doctoral Dissertation, 
University of Pennsylvania, Philadelphia, P.A.


\bibitem{slea} Sleater, D. and Temperly, D. (1991). ``Parsing English
with a Link Grammar.'' Carnegie Mellon University Computer Science 
technical report CMU-CS-91-196.


\bibitem{wu96} Wu, H. and  Furugori, T. (1996). ``A Hybrid Disambiguation
Model for Prepositional Phrase Attachment.'' {\it Literary and Linguistic 
Computing}, 11(4):187-192.


\bibitem{wu97} Wu, H. (1997). ``A Hybrid Model for Resolving Syntactic
Ambiguities in Natural Language Processing.'' Doctoral Dissertation, 
the University of Electro-Communications, Tokyo, Japan.

\bibitem{wu98} Wu, H., Furugori, T. (1998). ``A Computational Method for 
Resolving Ambiguities in Coordinate Structures.'' {\it Proceedings
of the 12th Pacific Asia Conference on Language, Information and Computation.} 
Singapore, 263-270. 

\end{thebibliography}

\begin{biography}

\biotitle{}

\bioauthor{Haodong Wu}
{
Haodong Wu received the B.S.  and M.A. degree in 
Computer Science 
from Chongqing University, Chongqing, China, in 1983 and 1986, respectively.
He received the Ph.D. degree from the University of Electro-Communications, Tokyo, Japan
, in 1997. He joined the staff of Chongqing University's Department of Computer
Science as a research associate in 1986 and a lecturer in 1988. From 1992 to
1994, he worked for the Tama Engineering Co. Ltd., Tokyo, Japan. He is currently
a research associate at the University of Electro-Communications. 
His current research interests include Computational Linguistics,
Artificial Intelligence, and Information Management System. He is
a member of the Association of Computational Linguistics, 
the Information Processing Society of Japan and the 
Association for Natural Language Processing of Japan.
 
}

\bioauthor{Teiji Furugori}
{
Teiji Furugori is a professor in the Department of Computer Science at the University of
Electro-Communications, Tokyo, Japan. He has a Ph.D. in Computer Science from SUNY at
Buffalo. His research interests include Computational Linguistics, Natural Language
Processing, Computer Aided Instruction, and Cognitive Science. He is a member of ACM,
the Information Processing Society of Japan, the Institute of Electronics, Information 
and Communication Engineers of Japan, the Association for Natural Language Processing
of Japan, Mathematical Linguistic Society of Japan. 

}


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

\end{biography}

\end{document}
