

\documentstyle[epsf,nlpbbl]{jnlp_e_b5_old2}

\setcounter{page}{61}
\setcounter{巻数}{5}
\setcounter{号数}{4}
\setcounter{年}{1998}
\setcounter{月}{10}
\受付{January}{22}{1998}
\再受付{May}{18}{1998}
\採録{July}{10}{1998}

\setcounter{secnumdepth}{2}

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

\etitle{Symmetric Pattern Matching Analysis \\ for English Coordinate Structures}

\eauthor{Akitoshi Okumura\affiref{NEC}   \and
 Kazunori Muraki\affiref{NEC}}

\headauthor{Okumura, A.~et~al.}
\headtitle{Symmetric Pattern Matching Analysis}

\affilabel{NEC}
          {NEC Corp., C\&C Media Research Laboratories}
          {NEC Corp., C\&C Media Research Laboratories}

\newcounter{exctr}
\newcounter{EXCTR}
\newcounter{Algo}
\newcommand{\mylistin}{}
\newcommand{\mylistend}{}


\eabstract{
The authors propose a model for analyzing English sentences including
coordinate conjunctions such as ``and'',``or'',``but'' and 
equivalent words.
The syntactic analysis of English coordinate sentences is one of the
most difficult problems in machine translation (MT) systems.  The
problem is selecting, from all possible candidates, the correct
syntactic structure formed by an individual coordinate conjunction,
i.e. determining which constituents are coordinated by the conjunction.
Typically, so many possible structures are produced that MT systems
cannot select the correct one, even if the grammars allow us to write the
rules in simple notations.
This paper presents an English coordinate structure analysis model,
which provides top-down scope information on the correct syntactic
structure by taking advantage of the symmetric patterns of
parallelism.
The model is based on a balance-matching operation for two lists of
feature sets. It has four effects, namely: a reduction in
analysis costs, a decrease in word disambiguation, the
interpretation of ellipses, and robust analysis.
This model was practically implemented and incorporated into the
English-Japanese MT system, and it had about 70\% accuracy for 3215 Wall
Street Journal sentences.
}

\ekeywords{Syntactic Analysis, Coordinate Structure, Parallel Structure}


\begin{document}
\maketitle
\thispagestyle{headings}



\section{Introduction}

This paper presents a model for analyzing English sentences including
coordinate conjunctions such as ``and'',``or'',``but'' and 
equivalent words.

The syntactic analysis of English coordinate sentences is one of the most
difficult problems in machine translation (MT) systems.  The problem
is selecting, from all possible candidates, the correct syntactic
structure formed by an individual coordinate conjunction, i.e.,
determining which constituents are conjoined by the conjunction.
Although the conjunction appears to have a simple function in the
English language, it has been researched as a conjunct scope problem
by both theoretical and computational
linguists.
Theoretically, it is possible to describe the syntactic and semantic
constraints that govern the acceptability of a structure in which two
constituents are conjoined by the
conjunction\cite{Lesmo85,Gazdar81,Schachter77}.
Computationally, it is possible to describe the grammar and heuristic
rules for these constraints by ATN networks, logic grammars, HPSG, and
categorical
grammars\cite{Kosy86,Fong85,Huang84,Boguraev83,Blackwell81,Niimi86}.
However, it is not easy to apply these techniques to
large-scale MT systems, because there are a variety of conjoined
patterns, many word ambiguities, some unknown words and ellipses of
words which occur simultaneously, in real environments.
Also, there may be several conjunctions and equivalent
words, such as commas, in a single sentence.  Typically, the
methods produce so many possible structures that MT systems cannot
select the correct one, even if the grammars allow us to write the rules
in simple notations.

Often, conjunctions produce reading difficulty even for human readers.
However, they also give readers a kind of symmetry as a reading
indication.  They have a tendency to conjoin the same kind of
syntactic patterns, which has been called
``parallelism''\cite{Beaugrande81,Shinoda91}.  In Japanese, this
similarity has been used to analyze conjunctive structures and the
method was found to be effective\cite{Kurohashi92}.
Japanese functional words such as a postpositional particle
``ha'', conjunctive particles and modal-related auxiliary verbs can be
exploited for determining a logical preference of attachment between
predicates\cite{KM86,FS90,Doi91}. The infomration can be used for
reducing possible ambiguities of conjunctive structures.
While Japanese
language has several coordinate conjunctions according to the
syntactic levels (a noun phrase and a predicative clause), English
coordinate conjunctions are used at any structural level. 
Moreover, English words have lots of part of speech ambiguities.
Therefore, English coordinate conjunctions produce more structural
ambiguities.
This is why robust methods are necessary for dealing with English
conjunctive structures.
    
We propose here an English coordinate structure analysis model, which
can determine the correct syntactic structure in real environments by
taking advantage of the symmetric patterns of parallelism.
The model is based on a balance matching operation for two lists of
feature sets. The lists represent the left-side and right-side
structures of coordinate conjunctions, including word ambiguities.
Operation determines the most symmetric
structure by comparing both sides of the conjunction.

First, we will explain problems with English coordinate sentences.
Second, we point out that parallelism can provide useful information
for the top-down analysis of sentences.  Third, the balance
matching analysis model is introduced for problem solving.
This model, which was implemented in the practical English-Japanese MT system
with a dictionary of 100,000 words, was used in an analysis module.
Finally, the results obtained in the MT system are reported together with
a discussion on the MT system configuration. 

\section{Problems with conjunctions}

Coordinate conjunctions for MT systems present three
difficulties\cite{Kosy86,Huang83,Niimi86,Okumura87}.

\begin{itemize}
    \item Analysis cost:
English coordinate conjunctions have a variety of linguistic
functions. The conjunctions can syntactically conjoin any parts of
speech; nouns, adjectives, verbs, etc., and all sorts of
constituents; words, phrases and clauses.
They produce so many possible structures that MT systems cannot
select the correct one, even if some grammars provide
simple notations of the rules.
The complexity of the rules imposes a burden on the analysis process.

    \item Word ambiguities:
Most English words can serve as various parts of speech,
such as nouns and verbs, prepositions and conjunctions, auxiliary verbs and
others, and adjectives and nouns.  The complex rules governing conjunctions
make word disambiguation more complicated, which results in inefficient analysis.

    \item Word ellipses:
It is possible for a conjunction to contain ``gaps'' (elided elements)
which are not allowed if the conjunction is removed.
These gaps must be filled with elements from other conjunction for a
proper interpretation, as in (\ref{GAP}) and (\ref{GAP}').
\end{itemize}

  \mylistin
    \item  NO.2 landing gear selector valves should be closed to the
full position,{\bf and} {\sl NO.3 to the half}.\label{GAP} 
    \item[(\ref{GAP}')] \rm
NO.2 landing gear selector valves should be closed to the full position,
{\bf and} {\sl NO.3 [landing gear selector valves should be closed]
to the half [position]}.
  \mylistend

\section{Parallelism of conjunctions}
\subsection{Symmetric patterns of parallelism}

English coordinate conjunctions have a tendency to conjoin the same
kinds of syntactic patterns.  We have identified three levels of symmetric
pattern.

  \begin{itemize}
    \item Phrase(Clause) symmetric patterns: \\
Phrase(Clause)-level symmetric patterns such as [Verb-Phase AND
 Verb-Phase] in the conjunct scope of ``as well as '' in
(\ref{ASWELLAS}) below and the series of commas in (\ref{PS}).
  \end{itemize}

  \mylistin
    \item Such coupling is desirable because it enables a development
    engineer {\sl to move easily within this hierarchy} {\bf as well as}
    {\sl to exploit the distinctive features of each system}.
  \label{ASWELLAS}
  \item The add operators cause POSTSCRIPT to pick up
          the top two numbers from the stack\underline{,} remove
          them\underline{,} {\sl add
          them}\underline{,} 
          {\bf and} {\sl leave the sum on the stack}.
          \label{PS}
  \mylistend
  \begin{itemize}
    \item Word symmetric patterns:
       Word-level symmetric patterns such as [Quantifier
       Preposition Abstract-Noun AND Quantifier Preposition
       Abstract-Noun] in the conjunct scope of the ``and'' in
       (\ref{DEPTH}).
       Some patterns are represented by semantic features such as 
       [Instrument AND Instrument] in the ``$and_{1}$'' of
       (\ref{INSPECT}). 
  \end{itemize}
  \mylistin
  \item  The container need not be large; if it is {\sl 10cm in
           diameter} {\bf and} {\sl 12cm in depth}, that is enough.
          \label{DEPTH}
  \item
    Inspect the cockpit {\sl indicators}  {\bf $and_{1}$} {\sl levers}
    for cracked glass and missing control knobs.  
          \label{INSPECT}
  \mylistend
  \begin{itemize}
    \item Morphological symmetric patterns:
    Morphological symmetric patterns are recognized by the sorts of
    letters, uppercase or lowercase letters, as in (\ref{URAN}) and
(\ref{ORDER}) as well as the exact same morphological pattern [CIC ...
    hatches AND CIC ..., hatches] in (\ref{CIC}).  
  \end{itemize}
  \mylistin
  \item An atomic bomb is a device for producing an explosively
          rapid neutron chain reaction in {\sl uranium-235} {\bf or} {\sl
          plutonium-239} which is called a fissile material.
    \label{URAN}
  \item  Technical orders described in {\sl AFR 8-2} {\bf and} {\sl PFR
           7-2} are registered in the on-line file in the form of inspection
           workcards.  \label{ORDER} 
  \item  There are {\sl $CIC_{1}$ $ditching_{2}$ $hatches_{3}$} {\bf
         and} {\sl $CIC_{4}$ $escape_{5}$ $hatches_{6}$}
         in the compartment. \label{CIC}
  \mylistend

Some symmetric patterns may appear in combined form 
[Preposition Gerund Nominal-Phrase AND Preposition Gerund
Nominal-Phrase] as in (\ref{RADIO}). 
  \mylistin
    \item Radioisotopes have played an important part {\sl $in_{1}$
developing effective insecticides $in_{2}$ the country} {\bf and} {\sl
$in_{3}$ finding the best ways of applying them}. \label{RADIO}
  \mylistend

\subsection{Analysis by symmetric patterns} \label{NEAR}

The symmetric patterns can provide effective information for the
top-down analysis of the scope of the conjuncts.  For example, though (\ref{RADIO})
allows another counterpart (``$in_{2}$ the country'') as the conjoined
phrase (``$in_{3}$ finding ...''), the symmetric pattern information
makes it easy to to select the correct counterpart of the phrase
(``$in_{1}$ developing ....'' ).  Also, where other examples syntactically
allow other counterparts of conjoined noun phrases, symmetric
pattern information enables easy selection.
Often, the scope of each conjunct is explicitly demarcated with commas and
morphological patterns, as in (\ref{PS}) and (\ref{CIC}).
The symmetric patterns can also be effective in
word disambiguation.  For example, (\ref{CIC}) contains verb/noun
ambiguities for $escape_{5}$ and $hatches_{6}$.  The
symmetric patterning of \underline{$ditching_{2}$}
  \underline{$hatches_{3}$} facilitates their disambiguation. 

In the previous example sentences, the words immediately following the
conjunction play important roles in the detection of the structures, because
there is usually a strong similarity between the starting words of each
conjunct scope and the words following the conjunctions.
However, the following examples also contain
kinds of symmetric patterns,
though the words following the conjunctions are not similar to
the starting words of the conjunct scopes.
\mylistin
\item  In 1985 the government offered offshore registration to the
companies, and, \underline{in consequence,} in 1985 incorporation fees
generated about two million dollars. \label{CONSEQUENCE}
\item The damage of the landing gear selector valve caused the
      leakage of the hydraulic fluid, and \underline{completely}
      blockaded the return path.
\label{COMPLETELY}
\item Close the cockpit ditching hatches, and \underline{the cabin
     pressure} will be dumped to relieve the air loads on the hatches.
\label{IMPERATIVE}
\mylistend

In both (\ref{CONSEQUENCE}) and (\ref{COMPLETELY}), an adverbial
modifier is inserted at the start of the second conjunct; this is a
common pattern extension. In (\ref{IMPERATIVE}), there is no real
parallelism: the first conjunct clause is an imperative, and the
second its result. 


\section{Balance matching analysis model}

The balance matching analysis model determines the correct structure
by taking advantage of symmetric patterns.  In this section, we will first
present the representation of symmetric patterns.
Then balance matching operation will be presented.  Finally, we will describe
analysis by balance matching.


\subsection{Pattern representation}

Symmetric patterns are represented by a list of three feature
sets; phrase features, word features, and morphological features,
based on the symmetric pattern levels.

  \begin{itemize}
    \item Phrase feature [$\phi$]:
Values are predicative, nominal, nominal-premodifier,
nominal-postmodifier, predicate-modifier. These values are assigned to
all the constituents in the phrase.  For example, all the words in
``the effective insecticides'' have $\phi$.({\sl Nominal})

    \item Word feature [$\gamma$]:
This feature includes 120 values which subclasses
general parts of speech, according to their grammatical and
semantic functions. For example, some values are \{NounInstrument\},
\{NounHuman\}, \{NounAction\}, \{PredicateStatic\}, etc.

    \item Morphological feature [$\delta$]:
The values indicate the morphological attributes of the
words, which consist of the word itself and its morphological type.
For example, ``{\sl uranium-235}'' is represented by
$\delta$.({\sl uranium-235, alphabet\_hyphen\_arabic-numbers}) .
  \end{itemize}
Each word in the sentence is represented by the set of the three
features. $\phi$ and $\gamma$ can include ambiguous values.
The {\sl i}th word-feature set ${\cal W}_{i}$ and the {\sl
n}-word sentence
${\cal S}_{1}^{n}$ are respectively represented as follows.
  \begin{eqnarray*}
 {\cal W}_{i} = \left( \begin{array}{l}
\Phi_{i}\\
\Gamma_{i} \\ 
\Delta_{i} \end{array} \right) &  
\begin{array}{l}
\Phi_{i} = \{\phi_{i1},\cdots,\phi_{im}\} \\
\Gamma_{i} = \{\gamma_{i},\cdots,\gamma_{in}\}\\
\Delta_{i} = \{\delta_{i1},\delta_{i2}\}
\end{array}
  \end{eqnarray*}
\begin{eqnarray*}
 {\cal S}_{1}^{n} = ({\cal W}_{1},\cdots,{\cal W}_{n}) 
\end{eqnarray*}

When the conjunction is the {\sl m}th word of the {\sl n}-word
sentence, the left list ${\cal S}_{1}^{m-1}$ and the right
list ${\cal S}_{m+1}^{n}$ can respectively be represented as follows.
\begin{eqnarray*}
 {{\cal S}_{1}^{m-1}} =  ({\cal W}_{1},\cdots,{\cal W}_{m-1})
\end{eqnarray*}
\begin{eqnarray*}
 {{\cal S}_{m+1}^{n}} =  ({\cal W}_{m+1},\cdots,{\cal W}_{n}) 
\end{eqnarray*}

The goal of balance matching is to find the most symmetric
pair of ${\cal S}_{x}^{m-1} ( 1 \leq {\bf x} < m )$ and ${\cal S}_{m+1}^{y}
( m < {\bf y} \leq n )$, i.e., to find the values of {\bf x} and {\bf y}.

\subsection{Balance matching operation}

By definition, the most symmetric pair shares the maximum number of
word-feature sets in the lists. The pair is detected by three
operations: intersection for two features, matching
for two word-feature sets, and balancing for
two lists.

\subsubsection{Intersection operation}

Intersection operation is one of the normal set operations for the
features:

$\Phi_{m-1}$.\{uranium-235,alphabet\_hyphen\_arabic-numbers\} $\cap$ 
$\Phi_{m+1}$.\{plutonium-239, alphabet\_hyphen\_arabic-numbers\} 
$  = $ \{alphabet\_hyphen\_arabic-numbers\}

The mutual dependency information for the ${\phi}_{ij}$ and
${\gamma}_{ik}$ is managed by bi-directional lists in the
background.  If all ${\phi}_{ij}$ dependent on ${\gamma}_{ik}$ are
disambiguated by the operation, all ${\gamma}_{ik}$ are removed.

\subsubsection{Matching operation}

Matching operation $\cap$ for the the word-feature sets ${\cal V}$,
${\cal W}$ is defined as follows:
\[
{\cal V}_{i}\cap{\cal W}_{j} = {\cal V}_{i}{\cal W}_{j} =
\left( \begin{array}{lll}
\Phi_{i} \cap \Phi_{j}^{'} \\
\Gamma_{i} \cap \Gamma_{j}^{'} \\ 
\Delta_{i} \cap \Delta_{j}^{'} \end{array} \right) 
\]
The matching word-feature set ${\cal V}_{i}{\cal W}_{j}$ can exist,
when  $\Phi_{i} \cap
\Phi_{j}^{'} \neq NULL$ or $\Gamma_{i} \cap \Gamma_{j}^{'} \neq NULL$.


As mentioned in Section~\ref{NEAR}, in most conjoined
sentences, the word-feature sets of ${\cal W}_{m+1}$, which immediately
follow the conjunction, play an important role in detecting the
structure, because there is strong similarity between the starting
word-feature set of the conjunct scope and ${\cal W}_{m+1}$.

\subsubsection{Balancing operation}

Balancing $\otimes$ for the lists ${\cal L}_{1}^{n}$
,${\cal R}_{1}^{m}$ is defined as follows:

\vspace{-6mm}
\begin{eqnarray*}
\lefteqn{ {\cal L}_{1}^{n} \otimes {\cal R}_{1}^{m}  = }\\
& & \{({\cal V}_{i}{\cal W}_{j},\cdots,{\cal V}_{k}{\cal W}_{l},\cdots)|
{\cal V} \in {\cal L}_{1}^{n},{\cal W} \in {\cal R}_{1}^{m},  
  k > j, {\cal L}_{1}^{n} =  ({\cal V}_{1}, \cdots, {\cal V}_{n}),
{\cal R}_{1}^{m} =  ({\cal W}_{1}, \cdots, {\cal W}_{n})\}
\end{eqnarray*}



Every word-feature set in the list does not always match one on the
other list.  Some word-feature sets in ${\cal L}_{1}^{n}$ can find 
matching counterparts in ${\cal R}_{1}^{m}$ but others cannot.
In (\ref{ARITHMETIC}),
$The_{1}$ and $operations_{3}$ respectively match $the_{1}$ and
$results_{2}$. 
\mylistin
\item $The_{1}$ $arithmetic_{2}$ $operations_{3}$ and $the_{1}$ $results_{2}$.
\label{ARITHMETIC} 
\mylistend

Therefore, balancing creates a set of lists to
exhaust all possible combinations.  The lists consist of
matching word-feature sets ( ${\cal V}_{k}$${\cal W}_{l}$) which
has been selected to avoid crossing any existing lines when ${\cal
V}_{i}$ and ${\cal W}_{j}$ are connected by a line as in the following:

\[
\begin{array}{ccccccc}
({\cal V}_{1},&,,,,&{\cal V}_{i},&,,,,&{\cal V}_{k},&,,,,&{\cal
V}_{m}) \\ & \swarrow & \downarrow & \downarrow & \downarrow & \searrow
& \\ ({\cal W}_{1},&,,,,&{\cal W}_{j},&,,,,&{\cal W}_{l},&,,,,&{\cal
W}_{n})
\end{array}
\]

For example,${\cal L}_{1}^{3} \otimes {\cal R}_{1}^{2}$ is :

\vspace{-0.8cm}
\begin{eqnarray*}
\lefteqn{ {\cal L}_{1}^{3}   =  ({\cal V}_{1},{\cal V}_{2},{\cal V}_{3}) ~~~~
{\cal R}_{1}^{2}   =  ({\cal W}_{1}, {\cal W}_{2}) } \\
\lefteqn{ {\cal L}_{1}^{3} \otimes {\cal R}_{1}^{2}  = 
\{({\cal V}_{1}{\cal W}_{1}),({\cal V}_{1}{\cal W}_{2}),
({\cal V}_{2}{\cal W}_{1}),({\cal V}_{2}{\cal W}_{2}),  
 ({\cal V}_{3}{\cal W}_{1}),({\cal V}_{3}{\cal W}_{2}),}\\
& &
({\cal V}_{1}{\cal W}_{1},{\cal V}_{2}{\cal W}_{2}), 
({\cal V}_{1}{\cal W}_{1},{\cal V}_{3}{\cal W}_{2}), 
({\cal V}_{2}{\cal W}_{1},{\cal V}_{3}{\cal W}_{2})\} 
\end{eqnarray*}

The balancing degree $\theta$ for a list ${\cal I}$ is defined as
follows:
\begin{eqnarray*}
\theta_{\cal I} =  {w}_{0} + \sum_{k \in \{\Phi,\Gamma,\Delta\}} {w}_{k}{\cal N}(k)
& &
{\cal I} =  ({\cal V}_{i}{\cal W}_{j},\cdots,{\cal V}_{l}{\cal W}_{m})
\end{eqnarray*}

${\cal N}(\Phi)$ and ${\cal N}(\Gamma)$ respectively represent the
total number of each feature in the list ${\cal I}$.  ${\cal
N}(\Delta)$ is the total number of the values of $\Delta$ in the list
${\cal I}$.

In order to derive results by processing several kinds of numerical
data, multivariate techniques are established\cite{MVA}. In
this model, a discriminant function are used to calculate the
plausibility of coordinate structures by using
Excel95 programs\cite{ExcelMVA}.  The balancing degree
$\theta$ is regarded as a discriminant function of multi-variate
analysis. $\theta_{\cal I}$ is a criterion variable and ${\cal N}(k)$
are predictor variables. In this paper, the balancing weights,
${w}_{0}$ and ${w}_{k}$ have been assigned by the linear discriminant
analysis method based on English coordinate sentences with conjunct
scope tags given by people, approximately 5,000 ``and'' sentences were
extracted from computer software and aircraft maintenance technical
manuals.  Simply speaking, the higher balancing degree suggests the
more possibility of the coordinate phrases or clauses.

\subsection{Analysis by balance matching}

The {\sl n}-word sentence including a conjunction as the {\sl m}th
word is analyzed according to the following steps.

\begin{itemize}  \item[\sl I.] 
Collect the word-feature set $G({\cal W})$: $G({\cal W}) = \{{\cal
W}_{x} | {\cal W}_{x} \cap {\cal W}_{m+1} \neq NULL \}$\\
This step collects a set of words similar to ${\cal W}_{m+1}$.
The collection considers some definite concord markers and boundary
markers, such as ``and'', ``both'' , ``either'', commas, periods, and
colons. 
In order to deal with the cases of
(\ref{CONSEQUENCE}),(\ref{COMPLETELY}) and (\ref{IMPERATIVE}), the
starting words of the clause ${\cal W}_{k}$ are added to $G({\cal W})$
when a comma is preceded by a conjunction.
\item[\sl II.] Create the list set $H({\cal L})$: \\
$
H({\cal L}) =  \{{\cal W}_{j}| i \leq j \leq m-1, {\cal W}_{i} \in
G({\cal W})\}$
\item[\sl III.] Create the list ${\cal R}_{1}^{n-m}$: \\
$
{\cal R}_{1}^{n-m} =  \{{\cal W}_{m+1},{\cal W}_{m+2},\cdots,{\cal W}_{n}\}
$
 \item[\sl IV.] To create the list set $F({\cal LR})$ by balancing
operation. \\
$
F({\cal LR})  =  \{ {\cal L}_{i} \otimes {\cal R}_{1}^{n-m} |
{\cal L}_{i} \in H({\cal L})   \}
$
 \item[\sl V.]
Select the list $F({\cal LR})_{max}$ which has the highest balancing 
degree from all the possible lists in $F({\cal LR})$.
\end{itemize}

For example, (\ref{RADIO}) is analyzed using the following steps. Here,
to allow easy understanding, the word-feature set and the list have been
represented by a simplified expression.

\begin{itemize}
    \item[(\ref{RADIO})] Radioisotopes have played an important part
{\sl $in_{1}$ developing effective insecticides $in_{2}$ the country}
{\bf and} {\sl $in_{3}$ finding the best ways of applying them}.
\end{itemize}


\begin{itemize}
  \item[{\sl I.}] $G({\cal W}) =  \{ in_{1},in_{2} \}$
  \item[{\sl II.}] $H({\cal L}) = \\
				  \{(in_{1},developing,effective,$ 
$insecticides, in,the,country) ,(in_{2},the,country) \} $
  \item[{\sl III.}] ${\cal R}_{1}^{8}  =$\\
				  $(in_{3},finding,the, best,ways, of, applying, them )$ 
  \item[{\sl IV.}] $F({\cal LR}) =  \{ \cdots,(Preposition,Nominal),$  
                                     $(Preposition,Gerund,Nominal)\}$
  \item[{\sl V.}] 
$\begin{array}{l}
F({\cal LR})_{max} = (Preposition,Gerund,Nominal) \\
{\cal L} = (in_{1},developing,effective,\cdots,in,the,country) \\
{\cal R} = (in_{3},finding,the, best, ways, of, applying, them )
    \end{array}$
\end{itemize}

The $and_{5}$ in (\ref{STEP}) can be analyzed as the same way.

\mylistin
\item
 Use extreme care when using cleaning solvents $like_{1}$ acetone and methyl
ethyl ketone which are highly $flammable_{2}$ and shall be $used_{3}$
in areas $with_{4}$ adequate fire extinguishing devices $and_{5}$
$free_{6}$ of ignition sources.
\label{STEP}
\mylistend
$ G({\cal W}) = \{like_{1},flammable_{2},used_{3},with_{4},free_{6} \}$\\
$ F({\cal LR})_{max} =  (Nominal\-Postmodifier) $\\
$ {\cal L} = (with_{4}, adequate, fire, extinguishing,devices ) $\\
$ {\cal R} = (free_{6}, of, ignition, sources ) $


\section{Experiments and Discussion}

\subsection{Experimental environments}
The model was incorporated as a balance matching module into the
practical English-Japanese MT system shown in
Fig.\ref{SYSCONF}\cite{Muraki86,Okumura87,Okumura91}.
The system works in practical use together with a dictionary of
approximately 100,000 words. 

\vspace{-1.6cm}

  \begin{figure*}[hbtp]
    \setlength{\unitlength}{0.95mm}
    \begin{picture}(180,50)(0,0)
      \put(17.5,27.5){\oval(30,5)}
      \put(5,25){\makebox(25,5){input sentences}}
      \put(5,10){\framebox(25,10){\shortstack{morphological \\ analysis}}}
      \put(35,10){\framebox(30,10){\shortstack{syntactic-semantic \\ analysis}}}
      \put(70,10){\framebox(20,10){\shortstack{conceptual \\ analysis}}}
      \put(105,15){\oval(20,5)}
      \put(95,12.5){\makebox(20,5){\sl Interlingua }}
      \put(120,10){\framebox(25,10){\shortstack{\tt sentence \\ \tt generation}}}
      \put(130,27.5){\oval(30,5)}
      \put(117.5,25){\makebox(25,5){output sentences}}
      \put(5,0){\framebox(60,5){\bf balance matching module}}
      \put(17.5,25){\vector(0,-1){5}}
      \put(17.5,10){\vector(0,-1){5}}
      \put(50,5){\vector(0,1){5}}
      \put(132.5,20){\vector(0,1){5}}
      \put(30,15){\vector(1,0){5}}
      \put(65,15){\vector(1,0){5}}
      \put(90,15){\vector(1,0){5}}
      \put(115,15){\vector(1,0){5}}
    \end{picture}
    \caption{A MT system configuration including the balance matching module}
    \label{SYSCONF}
  \end{figure*}

The input sentences, represented by the list of the feature sets based
on the results of morphological analysis, are transferred to the
balance matching module. The module produces the conjunct scope
information as well as the results of balance matching. The scope
information given by the module is as useful as that given by
human pre-editors. The syntactic-semantic analysis module analyzes the
sentences according to this top-down scope information.  After
analysis, the conceptual analysis module creates an interlingua
representation.  Output sentences are generated from the interlingua,
\cite{Muraki86,Okumura91}.  In this paper, experiments are done
using morphological analysis and the balance matching module.

\subsection{Experimental results}

The balance matching module was used in experiments involving 3,215
conjunctive sentences randomly sampled from 1992 Wall Street Journal
articles. The conjunctive sentences contained coordinate conjunctions
such as ``and'',``or'',``but'' and conjunctive commas.
The sentence
number is individually counted according to the existence of each
conjunction.
The average process time is  0.11 second for
one conjunction by Sun Sparc Station10 (Super Sparc 40MHz.)
The results of analyzing four conjunctions are in Table~\ref{ALLPREC}.
The correct sentences got correct conjunct scope information assigned
by the module.

  \begin{table}
    \caption{Precision for ``and'', ``or'', ``comma''' and ``but''}
    \label{ALLPREC}
    \begin{center}
      \begin{tabular}{|r|r|r|r|}
        \hline
conjunctions & all sentences  & correct sentences & precision \\
        \hline
and & 1476 & 1047 & 0.71 \\
or & 944 & 661 & 0.70 \\
comma & 410 & 294 & 0.72 \\
but & 385 & 250 & 0.65 \\
        \hline
total & 3215 & 2252 & 0.70 \\
	\hline
      \end{tabular}
    \end{center}
  \end{table}

The relationships between precision and sentence length for ``and'',
``or'', conjunctive commas, and ``but'' are respectively shown in
Tables~\ref{ANDPREC}, ~\ref{ORPREC}, ~\ref{COMMAPREC}, and
~\ref{BUTPREC}.

  \begin{table}
    \caption{Precision and sentence length for ``and''}
    \label{ANDPREC}
    \begin{center}
      \begin{tabular}{|r|r|r|r|}
        \hline
sentence length & all sentences & correct sentences & precision\\
        \hline
1-10 & 91 & 78 & 0.86 \\
11-20 & 502 & 361 & 0.72 \\
21-30 & 594 & 413 & 0.70 \\
31-40 & 236 & 157 & 0.67 \\
more than 40 & 53 & 38 & 0.72 \\
	\hline
total & 1476 & 1047 & 0.71 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}

  \begin{table}
    \caption{Precision and sentence length for ``or''}
    \label{ORPREC}
    \begin{center}
      \begin{tabular}{|r|r|r|r|}
        \hline
sentence length & all sentences & correct sentences & precision\\
        \hline
1-10 & 36 & 30 & 0.83 \\
11-20 & 362 & 279 & 0.77 \\
21-30 & 399 & 268 & 0.67 \\
31-40 & 123 & 71 & 0.58 \\
more than 40 & 24 & 13 & 0.54 \\
	\hline
total & 944 & 661 & 0.70 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}

  \begin{table}
    \caption{Precision and sentence length for conjunctive commas}
    \label{COMMAPREC}
    \begin{center}
      \begin{tabular}{|r|r|r|r|}
        \hline
sentence length & all sentences & correct sentences & precision\\
        \hline
1-10 & 27 & 21 & 0.78 \\
11-20 & 157 & 120 & 0.76 \\
21-30 & 151 & 100 & 0.66 \\
31-40 & 51 & 37 & 0.73 \\
more than 40 & 24 & 16 & 0.67 \\
	\hline
total & 410 & 294 & 0.72 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}

  \begin{table}
    \caption{Precision and sentence length for ``but''}
    \label{BUTPREC}
    \begin{center}
      \begin{tabular}{|r|r|r|r|}
        \hline
sentence length & all sentences & correct sentences & precision\\
        \hline
1-10 & 11 & 6 & 0.55 \\
11-20 & 146 & 100 & 0.68 \\
21-30 & 175 & 116 & 0.66 \\
31-40 & 44 & 25 & 0.57 \\
more than 40 & 9 & 3 & 0.33 \\
	\hline
total & 385 & 250 & 0.65 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}

The relationships between precision and the coordinate structure for ``and'',
``or'', conjunctive commas, and ``but'' are respectively shown in the
Tables~\ref{ANDPREC2}, ~\ref{ORPREC2}, ~\ref{COMMAPREC2}, and
~\ref{BUTPREC2}.
The coordinate structures are divided into four categories;
A noun phrase category means noun phrase coordination such as in example
sentences (\ref{DEPTH}),
(\ref{INSPECT}), (\ref{URAN}), and (\ref{CIC}).
A clause category means sentence-level coordination such as in
example sentences (\ref{GAP}') and (\ref{IMPERATIVE}).
A verb phrase category is verb and adjective coordination such as in
example sentences (\ref{ASWELLAS}), (\ref{PS}) and (\ref{COMPLETELY}).
The other category means categories such as in
example sentences (\ref{RADIO}) and (\ref{CONSEQUENCE}).

  \begin{table}
    \caption{Precision and coordinate structure for ``and''}
    \label{ANDPREC2}
    \begin{center}
      \begin{tabular}{|c|r|r|r|}
        \hline
coordinate structures  & all sentences & correct sentences & precision\\
        \hline
Noun phrase & 997 & 761 & 0.76 \\
Clause & 143 & 88 & 0.62 \\
Verb phrase & 192 & 105 & 0.55 \\
Other & 144 & 93 & 0.65 \\
        \hline
total & 1476 & 1047 & 0.71 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}

  \begin{table}
    \caption{Precision and coordinate structure for ``or''}
    \label{ORPREC2}
    \begin{center}
      \begin{tabular}{|c|r|r|r|}
        \hline
coordinate structures  & all sentences & correct sentences & precision\\
        \hline
Noun phrase & 660 & 490 & 0.74 \\
Clause & 15 & 10 & 0.67 \\
Verb phrase & 122 & 77 &  0.63 \\
Other & 147 & 80 & 0.54 \\
        \hline
total & 944 & 661 & 0.70 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}

  \begin{table}
    \caption{Precision and coordinate structure for commas}
    \label{COMMAPREC2}
    \begin{center}
      \begin{tabular}{|c|r|r|r|}
        \hline
coordinate structures  & all sentences & correct sentences & precision\\
        \hline
Noun phrase & 340 & 262 & 0.77 \\
Clause & 18 & 9 & 0.50 \\
Verb phrase & 27 & 12 & 0.44 \\
Other & 25 & 11 & 0.44 \\
        \hline
total & 410 & 294 & 0.72 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}

  \begin{table}
    \caption{Precision and coordinate structure for ``but''}
    \label{BUTPREC2}
    \begin{center}
      \begin{tabular}{|c|r|r|r|}
        \hline
coordinate structures  & all sentences & correct sentences & precision \\
        \hline
Noun phrase & 31 & 23 & 0.74 \\
Clause & 207 & 152 & 0.73 \\
Verb phrase & 89 & 44 & 0.49 \\
Other & 58 & 31 & 0.53 \\
        \hline
total & 385 & 250 & 0.65 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}

\newpage

\subsection{Discussion}

\vspace{-0.5cm}
  \begin{itemize}

    \item  Analysis robustness

This model provides the correct top-down information about
conjunct scopes for about 70\% of the sentences. It results in
effective syntactic analysis suitable for machine translation.  Most of the
sentences had required backtracking for analysis without the
model. Backtracking is suppressed by the model.

This model is robust for long sentences because the model is based on
word features, not on syntactic structures.  More structural
ambiguities are produced by longer sentence analysis.  In order to
deal with the ambiguities, structual matching such as unification is
generally used. While the structual matching requires more process
cost for longer sentence analysis, the word feature operation does not
require much process cost for longer sentences because it is based on
intersection operation for three kinds of feature sets.
If anything, the
longer sentences can give the model more chances of finding a better
balancing pair.  The model sometimes produces higher precision for longer
sentences, as shown in Tables~\ref{ANDPREC} and ~\ref{COMMAPREC}.

The model is also robust against unknown words. More than 55\% of the
3215 sentences include unknown words, and the average ratio of
unknown words is 9\% in a sentence. In the situations, there is no
significant difference in the average accuracy. As the model is based
on lexical information, it is not able to deal with sentences
including lots of unknown words. However, the model is robust enough to
accept a few unknown words in a sentence. Robustness is achieved
because the morphological features in (\ref{URAN}),(\ref{ORDER}) and
(\ref{CIC}) have been considered as well as the other features.

  \item  Analysis errors

``But'' sentences are less correctly analyzed than other conjunctions,
as shown in Table~\ref{ALLPREC}.  This is because the balancing
weights were determined by 5000 ``and'' sentences.
Table~\ref{BUTPREC2} shows that ``but'' tends to produce a sentence-level
coordinate structure.  On the other hand, ``or'' and commas have the same
precision as ``and''. This may be related to the fact that they have
a similar frequency ratio for ``noun phrase'', ``verb phrase'', and
``clause'' coordinate structures, as shown in Tables~\ref{ANDPREC2},
~\ref{ORPREC2} and ~\ref{COMMAPREC2}. At least, the
balancing weights for ``but'' should be individually determined based
on ``but'' data. 

Analysis errors are rather due to syntactically ambiguous
words, because the model is based on lexical information. Therefore,
when many words provide too many feature ambiguities, the model cannot
always determine the correct structure.  Analysis errors concentrate on
when the next word to a conjunction will have a verb infinitive form and
a noun ambiguity. This is because verb phrase analysis is always
the worst of noun phrase, clause, and verb phrase categories in
Tables~\ref{ANDPREC2}, ~\ref{ORPREC2}, ~\ref{COMMAPREC2}, and
~\ref{BUTPREC2}.  In order to solve the syntactic ambiguity
problem, filtering rules or chunking rules are expected to be useful
before balance matching.  The rules are local constraint
rules, which check two or three words before a focused word to
remove various syntactic ambiguities in the focused word. The filtering
rules improve the model.

Most of the errors are syntactically acceptable, but semantically
unacceptable. There are a few semantic features in this model.  Some
conjunctive structures should be distinguished by more subdivided
semantic features and semantic similarity calculations.  We need to
introduce some semantic categories to the features based on semantic
taxonomies and the semantic distance measurement
algorithm\cite{BUILDING,OKUMURA,Resnik93}.  Then, the balancing
weights should be determined for each conjunction using the most
appropriate discriminant methods that can cover the most data sets.
Otherwise, decision tree techniques will be used instead of
discriminant methods.


    \item  Effects of Analysis 

Balance matching reduces word ambiguities and improves
the inferences of unknown words, because the ambiguities of each
word are intersected by the counterparts of the symmetric list. The
results provide top-down information for the analysis of ambiguous
and unknown words, as in (\ref{CIC}). 

The model also makes it easy to interpret elided elements, because
the balance matching results can suggest the missing elements.  In
sentences such as (\ref{GAP}), $\cal R$ completely includes $\cal
L$. The differences in $\cal L$ and $\cal R$ complement the missing
elements.

It might be possible to apply this model to Japanese coordinate
conjunctions. For 
this purpose, it is essential to scrutinize feature sets representing
symmetric patterns according to the conjunction forms.
Also, it is necessary to determine the balancing weights for each
feature through a series of experiments.


  \end{itemize}

\vspace{-0.5cm}

\section{Concluding Remarks}

We propose an English coordinate structure analysis model,
which provides top-down scope information on the correct syntactic
structure by taking advantage of the symmetric patterns of
parallelism.

This model was implemented and incorporated into the practical
English-Japanese MT system with a dictionary of 100,000 words. The
model ensured about 70\% accuracy for 3215 Wall Street Journal sentences
, which led to robust analysis in the MT system, as well as helping to
make rule-based analysis effective. In the future, we plan to improve
the model based on the previous discussion, and also to extend analysis
to other conjunctions and prepositions.

\vspace{-0.2cm}

\section{Acknowledgments}

The authors thank Prof. Hozumi Tanaka and Asscociate Prof. Takenobu
Tokunaga of Tokyo Institute of Technology for their constant
encouragement and valuable comments.

\vspace{-0.3cm}

\bibliographystyle{nlpbbl}
\bibliography{v05n4_04}

\begin{biography}

\biotitle{}

\bioauthor{Akitoshi Okumura}
{
Akitoshi Okumura received the B.S. degree and the M.S. degree in
precision engineering, from Kyoto University, Kyoto, Japan, in 1984
and 1986, respectively.  He joined NEC Corp. in 1986, and is currently
researching natural language prosessing at the NEC C\&C Media Research
Laboratories as a principal researcher.  From 1991 to 1993, he joined
DARPA machine translation project as a visiting scientist at
Information Science Institute of University of Southern California,
Los Angeles, USA.  He is a member of the Information Processing
Society of Japan, the Society of Artificial Intelligence, and the
Association for Computational Linguistics.  His current research
interests include cross-lingual information retrieval, information
extraction and summarization, and speech translation.
}

\bioauthor{Kazunori Muraki}
{
Kazunori Muraki received the B.E. and M.E. degrees in information
engineering at Kyoto University, Kyoto, Japan, in 1974,
and 1976 , respectively.
He joined NEC Corp. in 1979, and is currently leading
research and development of natural language prosessing at
the NEC Personal Software Diviosn as a group manager.  He is
a member of the Information Processing Society of Japan, the
Society of Artificial Intelligence, and the Association for
Computational Linguistics, and an ediotrial member of
Natural Language Engineering.
His current research interests include natural language
understanding and idea processing.
}

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


\end{biography}

\end{document}


