


\documentstyle[epsf,nlpbbl]{jnlp_e_b5_old2}

\def\atari(#1,#2){}

\setcounter{page}{27}
\setcounter{巻数}{2}
\setcounter{号数}{3}
\受付{September}{20}{1994}
\再受付{February}{13}{1995}
\採録{March}{3}{1995}
\setcounter{年}{1995}
\setcounter{月}{7}

\setcounter{secnumdepth}{2}

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

\etitle{Example-Based Machine Translation\\
using Associative Processors}

\eauthor{Eiichiro Sumita\affiref{ATRITL} \and
         Kozo Oi\affiref{ATRITL}         \and
         Osamu Furuse\affiref{ATRITL}    \and
         Hitoshi Iida\affiref{ATRITL}    \and
         Tetsuya Higuchi\affiref{ETL}}

\headauthor{Sumita,~E.~et~al.}
\headtitle{Example-Based Machine Translation using Associative Processors}

\affilabel{ATRITL}
          {ATR Interpreting Telecommunications Research Laboratories}
          {ATR Interpreting Telecommunications Research Laboratories}
\affilabel{ETL}
          {Electrotechnical Laboratory}
          {Electrotechnical Laboratory}

\eabstract{
This paper proposes an Example-Based Approach (EBA) 
using Associative Processors (APs) for machine translation, 
especially speech-to-speech translation, that  requires (1) high accuracy and 
(2) a quick response.
EBAs translate by mimicking the  best-match 
translation examples (hereafter, ``examples''), which are derived from corpora.
These approaches are known to perform structural disambiguation, target word
selection, and whole translation accurately.
Therefore, EBAs fulfill the first requirement.
The second requirement is also fulfilled by an EBA using APs as follows.
The central mechanism of EBAs, Example-Retrieval (ER), retrieves 
the examples most similar to the input expression from an example database. ER
becomes the dominant component
as the size of the example database increases.
We have parallelized
ER by using APs  consisting
of an Associative Memory and a 
Transputer.
Experimental results show that  ER can be
drastically accelerated by our method.
Moreover, a study of communication among APs and 
an extrapolation from  the sustained performance of 10 APs
demonstrate the scalability of our method against the  size of 
the example database.
Consequently, the EBA using APs meets the critical requirements of 
machine translation.
}

\ekeywords{machine translation, example-based approach,
parallel processing, associative memory,
speech-to-speech translation}


\renewcommand{\topfraction}{}
\renewcommand{\textfraction}{}


\begin{document}

\maketitle
\thispagestyle{bothstyle}

\section{Introduction}\label{sec-intro}

Machine translation requires (1) high accuracy and 
(2) a quick response.
First, there is no doubt that translation accuracy is 
important in almost any situation,
and it is desirable to minimize human intervention such as pre-, inter-, 
and post-interaction between user and machine, especially 
in real-time applications
such as interpreting telephony.
Second, a practical throughput is important for machine translation 
with a realistic domain 
not only for processing a large-scale text
but also for real-time applications.

This paper proposes an Example-Based Approach (EBA) 
using Associative Processors (APs).
EBAs translate by mimicking the best-match 
translation examples (hereafter, ``examples''), which are derived from corpora.
EBAs are known to  perform structural disambiguation, target expression
selection and  whole translation  accurately.
Therefore, these approaches fulfill the first requirement.
The second requirement is also fulfilled by an EBA using APs as follows.
The central mechanism of EBAs, Example-Retrieval (ER),  retrieves 
the examples most similar to the input expression from an example database.
ER becomes the dominant component
as  the size of the example database increases.
In this work, ER has been parallelized
by using APs consisting of an Associative Memory and a 
Transputer.
Experimental results show that ER can be
drastically accelerated by our method.
Moreover, a study of communication among APs and 
an extrapolation from  the sustained performance of 10 APs
demonstrate the scalability of our method against the size of 
the example database.
Consequently, {\bf the EBA using APs meets the critical requirements of 
machine translation}.

Section \ref{sec-outline} explains 
EBAs and a  sentence translation system 
using an EBA.
Section \ref{sec-comp-cost} analyzes
the computational cost of EBA systems.
Section \ref{sec-tdmt-ap} describes the acceleration achieved  by using APs. 
Section \ref{sec-scale} explains the scalability of our method.
Finally, Section \ref{sec-related} touches on related research.

\section{Example-Based Approach}\label{sec-outline}

First, the idea behind EBAs and their notable features are introduced. Then, 
a sentence translation model using an EBA is discussed.

\subsection{Idea and Features}\label{sec-feature}

Novel models for NLP have been studied in recent years.
These methods have been called Example-Based Approaches (EBAs)
because they rely
on linguistic examples, such as translation
pairs, derived from corpora.
In the early 1980s, Nagao gave the first proposal of an EBA
for machine translation, 
which  translates by mimicking 
the best-match translation examples,
based on the fact that  
a human translates according to
past translation experience \cite{Nagao84}.
Since the end of the 1980s, 
large corpora and powerful computational devices have allowed us to
achieve Nagao's model and to expand the model to deal with 
not only translation but also other tasks such as parsing.

EBAs surpass conventional approaches for NLP
in several aspects. 
The following is a summary of observations made in  previous papers.

First, {\bf EBAs are accurate} in a restricted domain, if sufficient examples
are prepared.
\footnote{
An observation that {\bf the translation quality improves as the number 
of examples increases}, was reported in our previous paper \cite{Sumita92b}.

As explained below, thesauri give an appropriate semantic granularity for 
problems of natural language processing.
In the pp-attachment problem, compared with a statistically-based approach 
utilizing the frequency of word co-occurrences, an EBA that utilizes 
word co-occurrences, i.e., examples and a thesaurus can achieve higher 
accuracy with a much smaller corpus.
This implies that {\bf best-match based on the thesaurus compensates for
the well known low-frequency data problem}. Namely, words themselves are too 
fine-grained to get sufficient amounts of data.
In the case-frame selection problem, Nagao \cite{Nagao92} compared 
an example-based method that utilizes a thesaurus with
a conventional method that utilizes semantic markers consisting of 
several categories. The former is significantly better than the latter.
Namely, semantic markers are too coarse-grained to resolve semantic ambiguity.}

These approaches can deal with such well known difficult problems as
target expression 
selection (e.g. function words \cite{Sumita92a,Sumita92b}, 
noun phrases \cite{Sato93a} and verb phrases \cite{Sato91}) 
and disambiguation of pp-attachment \cite{Sumita93a}.
EBAs achieve high accuracy not only for 
these subproblems in machine translation but also 
for sentence translation \cite{FuruseE94}.
We have trained our Japanese-to-English sentence translation system
with the translations of 825 sentences
in a conference registration domain.
These sentences cover basic expressions used in Japanese aptitude
tests conducted by the government. These sentences were
reviewed by Japanese linguists as well. 
The translation
success rate for these 825 sentences (trained data) is about 98\%. 
In addition, we have tested 
1,056 sentences (unseen data) in the same domain;
the translation success rate is about 71\%.

Second, {\bf EBAs are robust}. 
The best-match mechanism using the semantic distance
is robust against incompleteness of system knowledge. 
Moreover, some deviations  from conventional grammars, 
which are specific to spoken 
language, are handled well \cite{Furuse92}. 
For example, in spoken 
Japanese, particles such
as {\bf wa}, {\bf o}, and {\bf ni} are frequently omitted. The omission is 
recovered well by EBAs.

Third, {\bf EBAs can output a reliability score} (a number indicating
how much we 
can rely on the result) unlike conventional NLP.
EBAs provide a 
semantic distance
as a reliability score. In our previous experiment 
\cite{Sumita92b} on the relationship between semantic 
distance and success rate, we found 
the tendency that the smaller the semantic distance, the
better the quality.

Fourth, {\bf the central mechanism of EBAs is language-independent}.
So far, we have implemented Japanese-to-English translation and vice versa.
Not only example-retrieval but also the whole transfer process
is shared by both systems \cite{Sobashima94}.

\subsection{Mechanism of Sentence Translation using EBA}\label{sec-mec}

Here, we describe a sentence translation model featuring an EBA.
A sentence is translated by combining partial examples in such a way that 
they cover the sentence jointly.
Since the examples  have a primary role and the whole 
process is controlled by transfer, we call our model 
Transfer-Driven Machine Translation (TDMT) \cite{Furuse92,FuruseE94,Furuse94b}.

A translation example, which is a piece of the transfer knowledge, 
describes the correspondence between
a source language expression (SE) and target language expressions
(TEs) as follows:

\begin{center}
\def\arraystretch{}
\begin{tabular}{cccc}
  $SE$ & $=>$ & $TE_1$ & ($E_{11}$, $E_{12}$,...), \\
     &    &  :  &  :              \\
     &    & $TE_n$ & ($E_{n1}$, $E_{n2}$,...)
\end{tabular}
\end{center}
\vspace{1ex}

SE and TE are represented by patterns consisting of 
variables and surface expressions.
 $E_{ij}$ for $TE_i$ represents the $j$-th example word list
that embodies variables of the SE.
 For example, the correspondence between
typical Japanese noun phrases of the form, ``X {\bf no}
Y'' and English noun phrases
is described as follows\footnote{X and Y are variables for Japanese
nouns and X' and Y' are the English translations of X and Y,
respectively; ``{\bf no}'' is an adnominal particle that corresponds to
 English prepositions such as ``{\bf of},'' ``{\bf for},'' and ``{\bf in}.''
j[{\it e}] represents a Japanese word, j and the literal English 
translation word, {\it  e}.}:

\begin{center}
  \begin{tabular}{ccll}
   X~{\bf no}~Y & $=>$ & Y'~{\bf of}~X'  & ((ronbun$[paper]$,daimoku$[title]$),$\cdots$),\\
                &      & Y'~{\bf for}~X' & ((hoteru$[hotel]$,yoyaku$[reservation]$),$\cdots$), \\
                &      & Y'~{\bf in}~X'  & ((Kyooto$[Kyoto]$,kaigi$[conference]$),$\cdots$),\\
                &      & \hspace*{1.3em} \vdots
  \end{tabular}
\end{center}

When TDMT translates the Japanese noun phrase 
``Oosaka[Osaka] {\bf no} paatii[party],'' it retrieves 
the best-match  in the transfer knowledge, i.e.
 X~{\bf no}~Y~~$=>$~~Y'~{\bf in}~X'~~(Kyooto$[Kyoto]$,
kaigi$[conference]$). According to this ``best-match,''
TDMT generates ``party {\bf in} Osaka'' by substituting English nouns
for the Japanese nouns.

 TDMT utilizes the semantic distance calculation previously proposed  
\cite{Sumita92b} to retrieve the best-match examples.
 Let us suppose that an input, $I$, and each example, $E_{ij}$,
consist of $t$ words as follows: 

{
\abovedisplayskip=-0.5ex
\begin{eqnarray*}
 I &=& (I_{1}, \cdots , I_{t}) \\
 E_{ij} &=& (E_{ij1}, \cdots ,E_{ijt})
\end{eqnarray*}
}

 Then, the semantic distance between $I$ and $E_{ij}$ is calculated as 
follows:

{
\abovedisplayskip=-1.5ex
\belowdisplayskip=-0.5ex
\begin{eqnarray}
d (I, E_{ij}) & = & \sum^t_{k=1} d (I_{k}, E_{ijk})\times W_{k}
\end{eqnarray}
}

 The semantic distance between words, $d (I_{k}, E_{ijk})$, is 
defined according to 
a thesaurus (Section \ref{sec-cal-am}).
The weight $W_k$ is the degree to which the word influences the
target expression selection. \footnote{In the current prototype system of TDMT,
$W_k$ is assigned to  $1/t$.}

 The flow of transferring an SE to the most plausible $TE$ is as follows:

\begin{enumerate}
  \renewcommand{\labelenumi}{}
  \topsep = 0pt
  \partopsep = 0pt
  \parskip = 0pt
  \itemsep = 0pt
  \item The semantic distance from the input is calculated for all examples.
  \item The example with the minimum-distance from the input is retrieved.
  \item The corresponding $TE$ of the minimum-distance example is selected 
        as the most plausible one for the SE.
\end{enumerate}

Processes [a] and [b] combine to form
Example-Retrieval (ER), the focus of this paper.

The top-level TDMT algorithm is as follows:
first, it  produces possible source structures in which the SEs of the transfer
knowledge are combined to cover the input;
second, TDMT produces the target structures by 
transferring each SE of the source structures to the most 
appropriate TE using ER and [c] above.
 
For example, suppose the input Japanese sentence is as follows:

\begin{center}
  \tabcolsep=1mm
  \def\arraystretch{}
  \begin{tabular}{ccccccc}
    ``$kaigi$ &         {\bf no} &      $toorokuryou$ &         {\bf wa} &
        $annaisho$ &            {\bf ni} &      {\it kisaisa\ } {\bf re\ teimasu}''\\
    $[conference]$ &    $[of]$ &        $[registration fee]$ &  $[sub]$ &
        $[announcement]$ &      $[in]$ &        $[be\ listed]$  \\[1ex] 
  \end{tabular}
\end{center}

The source structure shown in Figure 
\ref{fig:fig-source-structure} is produced 
by  combining SEs such as (X
{\bf no} Y), (X {\bf wa} Y), and (X {\bf ni} Y).
The target structure shown in Figure \ref{fig:fig-target-structure} 
is produced according to the transfer knowledge.
Finally, the following translation  is obtained:

``The conference registration fee is listed {\bf in} the announcement.''

\begin{figure}[ht]
  \begin{center}
\epsfile{file=fig1.eps,width=95mm}
    \caption{Source structure}
    \label{fig:fig-source-structure}
  \end{center}
\end{figure}

\begin{figure}[ht]
  \begin{center}
\epsfile{file=fig2.eps,width=91mm}
    \caption{Target structure}
    \label{fig:fig-target-structure}
  \end{center}
\end{figure}

\section{Analysis of Computational Cost}\label{sec-comp-cost}

Example-Retrieval (ER), the key process of EBAs, retrieves
the most similar examples by calculating the semantic distance between the
 input and examples.
This section analyzes the computational cost of ER by 
using TDMT, a typical EBA system introduced in the previous subsection.
Although the analysis is done using TDMT, the findings are in general applicable 
to other EBA systems.
First, we will show that ER is predominant in EBAs. Second, 
we investigate the ER cost in detail.
Finally, we will present a rationale for using parallel machines to
accelerate the ER of a large-scale EBA system. 

\subsection{Example-Retrieval Cost of Prototype System}\label{sec-cost-prototype}
 Here, we show the timing figures of the 
prototype Japanese-to-English  TDMT 
on a sequential machine (SPARCstation2)
for 746 test sentences 
\footnote{The average sentence length is about 10 words.}
that are representative Japanese spoken sentences
\footnote{
Of 825 sentences (described in 
Section \ref{sec-feature}), 
we used 746 sentences (about 90\%) in this experiment 
excluding sentences translated by exact-match of whole sentences, 
e.g., ``arigatougozaimasu (Thank you very much).''
Because exact-match sentences are translated momentarily, there is no 
need to accelerate their translation.} .

Figure \ref{fig:fig-calc-time} shows that the increase in 
translation time
is strongly related to the increase in ER time.
The minimum, average and maximum
translation time (ER time) per sentence is about 
0.26 (0.001), 3.53 (2.49), and 23.28 (21.5) seconds, respectively.

\begin{figure}[t]
  \begin{center}
\epsfile{file=fig3.eps,width=68mm}
    \caption{ER time in sequential TDMT}
    \label{fig:fig-calc-time}
  \end{center}
\end{figure}


{\bf ER is the  dominant component in EBAs because:}

(1) Even a single ER call is time-consuming. The
ER time, $T$ (milliseconds), rises in proportion to
 the size of the example database, $N$, which is necessarily large. 
In the experiment, the following approximate relation was 
observed.

{
\abovedisplayskip=-3ex
\belowdisplayskip=-3ex
\begin{eqnarray}
T & = & 0.65N
\end{eqnarray}
}

(2) ER is called many times
in translating a single sentence.
The number of ER calls, $C$, 
rises according to the sentence length, $L$. 
In our experiments, the following approximate relation between 
the number of ER calls and the sentence length was observed. 

{
\abovedisplayskip=-3ex
\belowdisplayskip=-3ex
\begin{eqnarray}
C & = & 10^{\frac{L}{10}}
\end{eqnarray}
}

The minimum, average and maximum 
number of ER calls per sentence is 1, about 10 and 97, \vspace*{-0.7ex}
respectively.


\subsection{Investigation of Example-Retrieval}\label{sec-investigation}

\begin{table}[b]
  \begin{center}
    \caption{ER time rate per pattern}  
    \label{tbl-dist-time}
    \def\arraystretch{}
    \begin{tabular}{|ccc|c|c|} \hline
      \multicolumn{3}{|c|}{\strut Pattern} & Rate (\%) & Accumulative (\%) \\\hline
      \strut
       X & wa       & Y & 25.20         & 25.20 \\
       X & no       & Y & 20.60         & 45.80 \\
       X & o        & Y & 19.61         & 65.41 \\
       X & ni       & Y & 11.13         & 76.54 \\
       X & ga       & Y & ~8.90         & 85.44 \\[-0.8ex]
         & $\vdots$ &   & $\vdots$      & $\vdots$  \\ \hline
    \end{tabular}
  \end{center}
\end{table}

 Table \ref{tbl-dist-time}  shows that 
example-retrieval of frequent patterns, which include function words 
such as ``wa,'' ``no,'' ``o,'' ``ni'' and ``ga,''
takes up the majority of  ER time in the Japanese-to-English version of TDMT. 
A rough explanation is as follows.
The number of ER calls for a pattern is proportional to 
the frequency of the pattern.
Since possible translations of a frequent pattern are, in general,  
diversified,
the number of examples is roughly proportional to the frequency.
Consequently, the computational cost of retrieving examples
is proportional to the square of the frequency of the patterns.

In our experiment, the ER time for the top 10 patterns 
was found to account for nearly 96\% of the entire ER time.
There is little need to accelerate ER for other patterns.
 With this rationale, we decided to parallelize the ER
for the top 10 patterns
in the subsequent experiment.

 In the E-to-J TDMT, the frequencies of
patterns including
function words,  such as ``at,'' ``in,'' ``on,'' 
``by,'' ``to,'' and ``of'', are as large as
those of J-to-E TDMT. 
Since they consume most of the ER time, we can take the same strategy 
to parallelize only the ER of frequent patterns.

\subsection{Example-Retrieval Cost of Large-Scale System}\label{sec-limit}
We estimate the figures of a large-scale TDMT
on two sequential machines:
(1) the SPARC-station2 and (2) a future high-performance machine.

Let us estimate the size of the example database, $N$, for 
a large-scale system.
 In the prototype system, the vocabulary size is about 1,500,
and $N$ is  12,500.
Assuming that  $N$ is in direct proportion to 
the square of the vocabulary size, then   $N$ grows rapidly.
Hereafter, we take  into consideration 
the case  $N$=1,000,000, i.e. about  9*9 times larger 
than that of the prototype system.

For 14-word sentences
\footnote{To estimate more realistic figures than those using 
746 test sentences, we use average sentences in a corpus.
In our corpus \cite{Ehara90}, which contains about
13,000 sentences, the average 
sentence length is about 14 words.
The average number of ER calls for all patterns 
is about 15,
and the average number of ER calls for the top 10 patterns discussed in 
the previous subsection is about 6.
The translation time, ER time, and utterence time
are about 5.95, 4.32, and 4.04 seconds on average, respectively. 
}
we estimate figures of a 
large-scale TDMT based on those of the prototype TDMT.
{\bf The ER time is proportional to $N$, while the time of the 
other processes are independent of $N$}.
Therefore,  the expected translation time 
using a SPARCstation2 
in the worst case is about 347.2 (~=~\{ER time\}
 + \{time for the other processes\}~=~$\{4.32\times 1,000,000/12,500\} 
+ \{5.95-4.32\}~=~345.6+1.63$) seconds.
\footnote{
This may seem larger than that expected according to the 
algorithm explained in Section \ref{sec-cal-am}
because the algorithm is rather simplified in some points. For example, 
it neglects the case where words are polysemous, i.e. have 
several different thesaurus codes and computing all combinations 
of codes requires 
much larger time.}
ER consumes most of the CPU time, i.e. 99.5\%.
This is clearly unacceptable for real-time applications.

Let us consider a much faster workstation, a 4,000  MIPS  sequential machine
\footnote{
 A 4,000  MIPS  sequential machine will be available in 10 years;
this is based on the currently-available 200  MIPS  machine and
the current rate of increase for MIPS of about 35 \% 
per year \cite{Hennessy90}.
} instead of a SPARCstation2 (28.5 MIPS).
 The translation time
is expected to be about 2.474 $(\simeq 347.2\times
28.5/4,000)$ seconds.
Of the  2.474 seconds, 
(1) the ER is expected to take 2.462 seconds
$(\simeq 345.6\times 28.5/4,000)$, 
and (2) the other processes are expected to consume  0.012 
seconds $(\simeq 1.63\times 28.5/4,000)$.
Therefore, since it seems difficult to avoid
disturbing natural communication 
with a sequential speech-to-speech translation system, 
we have decided to utilize parallelism to accelerate the ER.

\section{Acceleration Using Associative Processors}\label{sec-tdmt-ap}

Example-Retrieval (ER) is predominant in EBAs as described 
in Section \ref{sec-cost-prototype}; it does, however, 
have a nature suitable for parallel processing.
We propose accelerating ER by 
using a parallel device, Associative Processor (AP).
This section explains (1) AP; (2) ER on a single AP; 
and (3) ER on multiple APs.

\subsection{Associative Processors}\label{mp-ebmt}

An Associative Processor (AP) is the processing element of the massively 
parallel
machine, IXM2 \cite{Higuchi91a}.
IXM2 has shown that a large Associative Memory (AM) 
works effectively as a SIMD device for AI 
applications where 
association and set operations dominate the total processing time.
 The AM not only features storage operations but also logical
operations such as retrieving by content. 
 Parallel search and parallel write are particularly
important operations because they are sources of the AP's parallelism
and are exploited in the ER algorithm, as will be 
explained in the next subsection. 
As specified in Table \ref{tbl-ap-component},
each AP has a 4K-word AM and an INMOS T801 Transputer (TP).
The AM is mapped into the memory space of the TP.
A single AP allows one to perform 4K search/write operations in parallel.
APs are used in parallel TDMT as follows:
(1) examples are loaded on the AM; (2) parallel communication 
and sequential process are done by the TP; (3) parallel search/write are 
triggered by the TP and executed by the AM.

\begin{table}[thb]
  \begin{center}
    \caption{Components of an Associative Processor (AP)}
    \label{tbl-ap-component}
    \def\arraystretch{}
    \begin{tabular}{|r@{\hspace*{0.5em}}l|} \hline
      \strut
      $\bullet$ & 4K × 40bit Associative Memory (AM), 375 ns \\
      $\bullet$ & INMOS T801 Transputer (TP), 25 MHz, 12.5 MIPS\\
                & 4KB on-chip RAM, 40 ns\\
                & 32K ×32bit SRAM, 80 ns\\
                & 4 serial links, 10 Mbits/sec\\ \hline
    \end{tabular}
  \end{center}
\end{table}

\subsection{ER on a Single Associative Processor}\label{sec-cal-am} 
First, we explain the distance calculation part (process
[a] in Section \ref{sec-mec}) of Example-Retrieval
for a single pattern on a single AP.
Suppose $n$ is the number of 
examples and $t$ is the example length.
The part can then be implemented as follows:
$t$-time repetition of $n$-time summation of 
the distances between the $t$-th words of the input and the $n$-th 
example, multiplied by the $t$-th weights (see expression (1) in Section \ref{sec-mec}).

\begin{table}[b]
  \begin{center}
    \caption{Semantic distance between thesaurus codes. }
    \label{tbl:tbl-sem-dist}
    \def\arraystretch{}
    \begin{tabular}{|rl|c|r|} \hline
    \multicolumn{2}{|l|}{\strut\ \ Condition} & Example & Distance \\ \hline
    \strut~[c1] & $CI_{1} CI_{2} CI_{3} = CE_{1} CE_{2} CE_{3}$       & {\bf 347} , {\bf 347} & 0 \\
    \strut~[c2] & $CI_{1} CI_{2} = CE_{1} CE_{2}, CI_{3} \neq CE_{3}$ & {\bf 34}7 , {\bf 34}6 & 1/3 \\
    \strut~[c3] & $CI_{1} = CE_{1}, CI_{2} \neq CE_{2}$               & {\bf 3}47 , {\bf 3}37 & 2/3 \\
    \strut~[c4] & $CI_{1} \neq CE_{1}$                                & 347 ,  247            & 1 \\ \hline
    \multicolumn{1}{r}{\strut\ NB:} &
    \multicolumn{3}{@{}p{85mm}}{\baselineskip=0.8\normalbaselineskip
      The input code and example code are $CI_1CI_2CI_3$ and $CE_1CE_2CE_3$.} 
    \end{tabular}
  \end{center}
\end{table}

The distance between words is reduced to the distance between codes in a 
thesaurus. 
Each word is assigned a $k$-digit $l$-scale code that clearly represents
the thesaurus hierarchy.
In the  thesaurus \cite{kado} used in our experiment, a 3-digit decimal
code is assigned.
The semantic distance between codes is calculated according to
Table \ref{tbl:tbl-sem-dist}.
Sequential implementation of the distance calculation  repeats
word-by-word, accumulating the partial sums by computing,
example-by-example, the conditions in Table \ref{tbl:tbl-sem-dist} to
yield 0, 1/3, 2/3 or 1.

Let us move on to the parallel implementation of the distance calculation part.
The number of examples, 
$n$, is much larger than the example length of a pattern, $t$,
so we have decided to parallelize the $n$-time summation.
Table \ref{tbl-cam-ebmt} outlines the elementary steps, i.e.
parallel $n$-summation of $t$-th partial sums.
[a1] to [a4] in Table \ref{tbl-cam-ebmt} correspond to [c1] to [c4]
in  Table \ref{tbl:tbl-sem-dist}. 
They are executed one-by-one  using steps  [i] to [iv].

\begin{table}[htb]
  \begin{center}
    \caption{Calculating semantic distance per word between input and
             all examples\\ on a single Associative Processor (AP)} 
    \label{tbl-cam-ebmt}
    \tabcolsep=1mm
    \begin{tabular}{|cp{130mm}@{\hspace*{2mm}}|} \hline
      \strut      & $X$ is the retrieval data and $Y$ is the distance. \\
      \strut~[a1] & {\dg\bf Retrieve the cells whose distance from the input is 0.} \\
      \strut      & Set $X$=``all three digits of the input code'' and $Y$=0, execute [i]--[iv].\\
      \strut~[a2] & {\dg\bf Retrieve the cells whose distance from the input is 1/3.} \\
      \strut      & Set $X$=``flag bit (0) and upper two digits of the input code'' and $Y$=1/3,
                execute [i]--[iv].\\ 
      \strut~[a3] & {\dg\bf Retrieve the cells whose distance from the input is 2/3.}\\
      \strut      & Set $X$=``flag bit (0) and upper one digit of the input code'' and $Y$=2/3, 
                execute [i]--[iv].\\ 
      \strut~[a4] & {\dg\bf Retrieve the cells whose distance from the input is 1.}\\
      \strut      & Set $X$=``flag bit (0)'' and $Y$=1, execute [i]--[iii].\\
      [-1ex]
      \multicolumn{2}{|c|}{\null\dotfill\null} \\
      \strut~[i]   & Mark all cells which matches $X$ simultaneously on the AM.\\  
      \strut~[ii]  & Write 1 at the flag bit of all marked
            cells simultaneously on the AM to mask them out in the 
            following retrieval.\\  
      \strut~[iii] & Get the address of a marked cell
            and add $Y\times weight$ to a
            semantic distance variable on the TP that corresponds to the
            address. Repeat this process until the
            marked cells run out.\\   
      \strut~[iv] & Clear all marks on the AM.\\[1ex] \hline
    \end{tabular}
  \end{center}
\end{table}

\begin{figure}[htb]
  \begin{center}
\epsfile{file=fig4.eps,width=62mm}
    \caption{Illustration of  semantic distance calculation using
      Associative Memory (AM)}
    \label{fig-cam-example-e}
  \end{center}
\end{figure}

Figure \ref{fig-cam-example-e} illustrates a portion of the AM;
the input data is 344, which is 
the thesaurus code of the word ``$uchiawase$[$meeting$].''
Each code of the examples is stored in the AM.
344, 316, 347 represent the codes for ``$kaigi$[$conference$],''
``$toochaku$[$arrival$],'' ``$kaisetsu$[$explanation$]'' of the
examples. 
Figure \ref{fig-cam-example-e} shows steps [i] to [iii] of [a2] 
after [a1] is  completed.
Step [i] marks the third cell, step 
[ii] writes 1  at the flag bit of the third cell,
and step [iii] gets 3, i.e. the address of the marked cell.
Steps [i], [ii] and [iv] are 
done for all cells by the parallel search/write operations
of the AM in a constant time.
Step [iii] is done in the 
TP and repeated 
by the number of marked cells.
{\bf Parallel implementation identifies examples not by
repeating but by executing the match and conditional branch simultaneously 
to perform step [iii]
with given values, i.e.  0, 1/3, 2/3 or 1.}

TP sequentially performs the process that finds the minimum of the distances 
between the input and examples and locates 
the examples whose distance is minimum (process [b] in Section 
\ref{sec-mec}) in Example-Retrieval.

We have already successfully conducted a preliminary experiment of ER 
for a single pattern on a single AP \cite{Sumita93b}. 
In the experiment, the AP outperformed state-of-the-art machines by
using the parallel search/write functions of the AM.
\footnote{
An investigation on a single ER call revealed that the 
AM consumes 
at most a minute order of time, i.e.  10 microseconds,
for 4K parallel operations and that
the TP consumes time on the order of 10 milliseconds. 
In other words, although ER is drastically accelerated by exploiting the 
AM's parallelism,
the remaining sequential processes  
of ER, i.e.  step [iii] of process [a] and process [b],
are predominant for ER on a single AP. 
We can achieve greater acceleration because 
improving the performance of the TP directly decreases the ER time.}

\subsection{ER on Multiple Associative Processors}\label{sec-config-mptdmt}

According to the performance analysis in subsection
\ref{sec-investigation}, we targeted 
only the 
top 10 patterns in the experiment for multiple patterns on multiple APs. 
The number of examples for each pattern of prototype system was
at most about 1,000, 
and in  our implementation each AP could load about 1,000 examples; thus,
10 APs were sufficient for the experiment.
 The 10 APs ($\rm AP_1, AP_2,\cdots, AP_{10}$) and the root TP,
which was built into the HOST (the SPARCstation2), were connected in a tree
configuration as shown in Figure \ref{fig:fig-config-mptdmt}.
 \footnote{The tree configuration is trinary because each TP has
four serial links, as shown in Table \ref{tbl-ap-component}. 
The root TP and the HOST are connected through an SBus.
The TDMT main program is written in Lisp
and is executed on the HOST (SPARCstation2). The ER routine is
programmed in Occam2 and executed on the APs and the root TP.}

\begin{figure}[h]
  \begin{center}
\epsfile{file=fig5.eps,width=57mm}
    \caption{Configuration of TDMT using 10 Associative Processors (APs)}
    \label{fig:fig-config-mptdmt}
  \end{center}
\end{figure}

The ER algorithm
using multiple APs\cite{Higuchi94,Oi94} is shown in Table \ref{tbl-algo-ebmt}.
This algorithm implements ER by distributing examples  onto multiple APs,
retrieving examples on each AP in parallel and merging all results.

\begin{table}[t]
  \begin{center}
    \caption{ER Algorithm using multiple Associative Processors (APs)}
    \label{tbl-algo-ebmt}
    \tabcolsep=1mm
    \begin{tabular}{|cp{130mm}@{\hspace*{2mm}}|} \hline
      \strut~[m1] & Send input data from the HOST to the root TP.\\
      \strut~[m2] & Send the input data sent from the upper  
                directly-connected processors 
                to the lower directly-connected APs in parallel.\\ 
      \strut~[m3] & Execute ER locally on each AP in parallel
            (the minimum
            distance and the examples whose
            distance is minimum in an AP are obtained).\\ 
      \strut~[m4] & Send the ER result, after merging 
            its own result and the results sent from lower directly-connected 
            APs in parallel,
            to the upper directly-connected processors.\\
      \strut~[m5] & Send the merged result from the root TP to the HOST.\\ \hline
    \end{tabular}
  \end{center}
\end{table}

\begin{figure}[t]
  \begin{center}
\epsfile{file=fig6.eps,width=73mm}
    \caption{Two methods of loading examples}
    \label{fig:fig-storing-method-e}
  \end{center}
\end{figure}

We compared two different methods of loading examples
as follows (see Figure \ref{fig:fig-storing-method-e}):

\begin{center}
  \tabcolsep=0mm
  \begin{tabular}{l@{\quad}p{97mm}}
    {\bf Homo-loading (HM)} & Each AP is loaded with examples of a pattern.\\
    {\bf Hetero-loading (HT)} & Each AP is loaded with examples
    that are equally distributed to all APs, of 10 different patterns.
  \end{tabular}
\end{center}

\begin{figure}[htb]
  \begin{center}
\epsfile{file=fig7.eps,width=73mm}
    \caption{Acceleration of ER (HM) over sequential TDMT}
    \label{fig:speedup-histo-er-hm}
  \end{center}
\end{figure}

\begin{figure}[htb]
  \begin{center}
\epsfile{file=fig8.eps,width=73mm}
    \caption{Acceleration of ER (HT) over sequential TDMT}
    \label{fig:speedup-histo-er-ht}
  \end{center}
\end{figure}

Figures \ref{fig:speedup-histo-er-hm} and \ref{fig:speedup-histo-er-ht} plot
the acceleration of ER
for TDMT using multiple APs over sequential TDMT with the two
methods. 
The acceleration with the HT method is greater
than that with the HM method because the sequential part, 
i.e.  step [iii] of process [a] and process [b],
is proportional to the number of examples of the pattern in question
on the APs
and because the numbers in 
HT are much less than those in HM.
The  sentence-by-sentence acceleration changes largely depending on  to 
what extent the sentence calls up ER for the top 10 patterns.
Needless to say, about 90 sentences are not accelerated
because they do not include
the ER for the top 10 patterns.
 With the HT method, the average acceleration of ER 
is about 16.4 ($\simeq
2.4897/0.1522$ = \{the average time (seconds) per sentence in the sequential
TDMT\}/\{the average time  (seconds) per sentence in the HT method\}).

Table \ref{tbl-condition-proto} summarizes the performance of prototype TDMTs 
(on the SPARCstation2 in Section \ref{sec-cost-prototype} and 
on APs with the SPARCstation2
in this section).
These results do not look so striking.
Because the prototypes are rather small-scale, there is no urgent need 
to achieve acceleration even by parallelizing TDMT.
However, sequential implementation cannot scale up,
as discussed in Section \ref{sec-limit}.
On other hand, parallel TDMT 
on multiple APs exhibits clear scalabilty as will be shown in the
next section.
Table \ref{tbl-ap-data} gives a time analysis of a single ER call on a 
prototype 
parallel TDMT using the HT 
method (referring to the algorithm of Table \ref{tbl-algo-ebmt}).
{\bf (a) and (b) are controlled not by the size of the example database
but by the depth of the AP tree}
because an AP can send data to those APs directly-connected in parallel 
(e.g.  {\small 
 $\rm AP_2\hspace{-0.3em}\to\hspace{-0.3em}{AP_6}$,
 $\rm AP_2\hspace{-0.3em}\to\hspace{-0.3em}{AP_7}$,
 $\rm AP_2\hspace{-0.3em}\to\hspace{-0.3em}{AP_8}$})
 and vice versa
\footnote{
This is because a TP can send data to those TPs directly-connected in parallel 
and the APs consist of an AM and a TP}.
Thus, (a) and (b) are the unit times between two APs ~$\times$ 
the tree depth, 2 (see Figure \ref{fig:fig-config-mptdmt}).
{\bf The unit times between two APs for (a) and (b) are fairly small, 
i.e.  several tens of microseconds}, 
because the data size is only several tens of  bytes 
and the bandwidth of the link between two TPs is 10 Mbits/sec.
Thus the sum, {\bf (c), communication time among APs, is controlled 
by the tree depth and a small coefficient}.
Step [m3] can be regarded as a constant operation because 
even if the total number of 
examples increases, the number of examples for  each AP
is  roughly invariant.
Step [m1] is of a constant-time because it only does 
operations related to input sending. 
Step [m5] can be regarded as a constant operation
because it depends on the size of the 
ER result, which does not sigificantly change.
Consequently, time {\bf (d)} is invariant.

\begin{table}[t]
  \begin{center}
    \caption{Time comparison of prototype TDMTs}
    \label{tbl-condition-proto}
    \begin{tabular}{|@{\hspace*{1em}}c@{\hspace*{1em}}|c|} \hline
         \multicolumn{2}{|c|}{number of examples: 12,500} \\ \hline
         sequential & parallel \\ \hline
         SPARCstation2 & 10AP+SPARCstation2 \\[-1ex]
          (28.5  MIPS) & \hspace*{3em}(28.5  MIPS) \\ \hline
         3.53 (2.49+1.04) & 1.19 (0.15+1.04) \\ \hline
    \multicolumn{2}{r}{\ NB: A (B+C): A=Translation, B=ER and C=Other}\\[-1ex]
    \multicolumn{2}{r}{Seconds per 10-word sentence}
    \end{tabular}
  \end{center}
\end{table}

{
\begin{table}[t]
  \begin{center}
    \caption{Time of steps in a single ER call}
    \label{tbl-ap-data}
    \tabcolsep=1mm
    \begin{tabular}{|lp{105mm}|c|} \hline
      \multicolumn{2}{|c|}{Steps in ER} & msec \\ \hline
      ~(a) & distribute the input data through all APs (step [m2])& \hspace{0.5em}0.10(0.05*2) \\
      ~(b) & merge \& collect the result from all APs (step [m4]) & \hspace{0.5em}0.12(0.06*2) \\
      ~(c) & communicate among APs  (=(a)+(b))& \hspace{0.5em}0.22(0.11*2) \\
      ~(d) &  (1) ER (step [m3]) and (2) communicate between the HOST and the root TP (steps [m1] and [m5])  & 13.15\\ \hline
       \multicolumn{3}{l}{
        \ NB: Each time is the average figure per ER call
        when translating 746 sentences.} 
    \end{tabular}
  \end{center}
\end{table}
}

\section{Scalability toward Large-Scale System using 
Associative Processors}\label{sec-scale}

The experiment in the previous section 
and the estimation in this section
show that ER on multiple APs is clearly scalable against 
 the size of the example database.
That is, 
even though  the size of the example database
increases by nearly two figures from the prototype 
system, the ER time increases slightly
and 
is applicable to real-time applications.

\subsection{Configuration}
Let us estimate the tree depth of the AP tree necessary to load
examples of a large-scale system (Section \ref{sec-limit}).
The tree depth is the minimum D satisfying
the inequality:

{
\abovedisplayskip=-0.5ex
\belowdisplayskip=-0.5ex
\begin{eqnarray}
\sum^{\rm D}_{x=1} 3^x \ge {\frac{N}{12,500}} \times 10
\end{eqnarray}
}

The right hand side is the  number of  APs. 
Because 
prototype TDMT ($N$=12,500) requires 10 APs,
a large-scale TDMT ($N$=1,000,000) requires 800 APs. 
Thus, the tree depth, D, is 6.
Figure \ref{fig-config-scale} shows 800 APs in a trinary tree structure.
We assume a 4,000 MIPS sequential workstation as the host here because
it is not conclusively determined whether those other than ER is
suitable for parallel computation. 
This is a hybrid acceleration in that (1) the predominant part, ER, is 
accelerated by APs; (2) the other part is accelerated by a high performance 
sequential machine (4,000 MIPS).

\begin{figure}[htb]
  \begin{center}
\epsfile{file=fig9.eps,width=73mm}
    \caption{Configuration of large-scale TDMT using 800 APs}  
    \label{fig-config-scale}
  \end{center}
\end{figure}

\subsection{Estimation}
We estimate the time for translating
the 14-word  sentences based on the extrapolated 
 figures for the 4,000  MIPS  machine shown in Section \ref{sec-limit}.
 The translation time is divided into parts (a) to (i), as shown in Table
\ref{tbl-estimation-result}.
(a) to (e) are explained according to Table \ref{tbl-ap-data}.
Recall that the tree depth of 800 APs is 6 (Figure \ref{fig-config-scale})
and the number of ER calls per 
14-word sentence is 6.

\begin{table}[t]
  \begin{center}
    \caption{Estimation of translation time on large-scale parallel TDMT}
    \label{tbl-estimation-result}
    \tabcolsep=1mm
    \begin{tabular}{|c|c|p{37mm}|p{32mm}|p{27mm}|} \hline
      \multicolumn{5}{|c|}{(i) translation}\\ \hline
      \multicolumn{5}{|c|}{193}\\ \hline
      \multicolumn{4}{|c|}{(g) ER} & (h) other on HOST\\ \hline
      \multicolumn{4}{|c|}{181} & \multicolumn{1}{|c|}{12}\\ \cline{1-4}
      \multicolumn{3}{|c|}{\raisebox{-1.3ex}[0pt]{(e) ER for top 10}} & (f) ER for other \vspace{-1ex} than top 10 on HOST & \\ \cline{1-4}
      \multicolumn{3}{|c|}{82.9} & \multicolumn{1}{|c|}{98} & \\ \cline{1-3}
      \multicolumn{2}{|c|}{\raisebox{-2.5ex}[0pt]{(c) comm. among APs}} & (d) (1) ER and \vspace{-1ex} (2) comm.\mbox{} between \vspace{-1ex} the HOST and the root TP & & \\ \cline{1-3}
      \multicolumn{2}{|c|}{4.0} & \multicolumn{1}{|c|}{78.9} & & \\ \cline{1-2}
      (a) distribute & (b) collect & & & \\ \cline{1-2}
       1.8 & 2.2 & & & \\ \hline
      \multicolumn{5}{r}{NB: Milliseconds  per 14-word sentence}
    \end{tabular}
  \end{center}
\end{table}


 The distribution time to all APs  {\bf (a)} is 
nearly
1.8 $(=0.05\times 6\times 6)$ milliseconds because
the average distribution time between directly-connected APs is about 0.05
milliseconds, the tree depth is 6, and the
average number of ER calls is about 6.
In the same way, the collection time from all APs {\bf (b)} is about
2.2 $(=0.06\times 6 \times 6)$ milliseconds.
Thus, the total communication time among APs {\bf (c)} is about $1.8+2.2=4.0$
milliseconds. 
The time {\bf (d)} 
involving (1) ER on each AP and 
(2) communication between the HOST and the root TP
is not related to the 
tree depth, so it is simply multiplied by the number of ER calls, 6, 
yielding 78.9=13.15*6 milliseconds.
Accordingly, the ER time for only the top 10 patterns {\bf (e)} is 82.9 
milliseconds.

(f) to (i) are estimated based on (e) and 
the 4,000  MIPS's estimation in Section \ref{sec-limit}.
The ER time for patterns other than the top 10 patterns 
{\bf (f)} is 98 milliseconds \footnote{
So far, we have assumed that only ER for the top 10 patterns is parallelized.
We can achieve more acceleration 
if we include other frequent patterns  to minimize (f) under the 
condition that the parallelizing overhead is not exceeded.}
because 
the entire ER time is estimated to be 
2462 milliseconds (in Section \ref{sec-limit}),
and ER for  other than the 
top 10 patterns consumes 4\% of the time (in Section \ref{sec-investigation}).
{\bf (g)} is the sum of (e) and (f).
{\bf (h)} is 12 milliseconds (Section \ref{sec-limit}).
The grand sum, i.e.  the translation time of  14-word sentences {\bf (i)},
is 193 milliseconds.

Table \ref{tbl-condition-large} summarizes the performance of
large-scale systems.

(1) The ER time of the 
SPARCstation2 in the worst case is unacceptably large (345.6 seconds).
The APs accelerated
ER from 345.6 seconds to  0.18 seconds.

(2) The time for processes other than ER  
is effectively reduced from 1.63 sec to 0.01 
inversely 
proportional to the increase in  MIPS.
This part is not necessarily suitable for APs and is tractable with 
a high-performance sequential machine.

\begin{table}[htb]
  \begin{center}
    \caption{Time comparison of large-scale TDMTs}
    \label{tbl-condition-large}
    \begin{tabular}{|c|c|} \hline
                 \multicolumn{2}{|c|}{number of examples: 1,000,000} \\ \hline
                 \multicolumn{1}{|c|}{sequential} & parallel \\ \hline
                 SPARCstation2  & 800AP+sequential machine\\[-1ex]
                 (28.5  MIPS)  & \hspace*{3em}(4,000  MIPS)\\ \hline
                 347.2 (345.6+1.63) & 0.19 (0.18+0.01) \\ \hline
    \multicolumn{2}{r}{NB: A (B+C): A=Translation, B=ER and C=Other}\\[-1ex]
    \multicolumn{2}{r}{Seconds per 14-word sentence}
    \end{tabular}
  \end{center}
\end{table}


\section{Related Research}\label{sec-related}

\subsection{Massively Parallel Natural Language Processing}
 Up to now, some systems using a massively parallel machine in the
field of natural language processing, such as a parsing system
\cite{Kitano91b} and translation systems, e.g.  
ASTRAL \cite{Kitano91a}, MBT3n \cite{Sato93b}, have
been proposed. 
 They have demonstrated good performance; nonetheless,
they differ from our proposal.
The first two systems, although they use APs, 
use a different mechanism for their natural language tasks, i.e. 
they do not calculate the semantic distance
but propagate markers through a semantic network.
The last system deals with a translation subproblem, i.e.  translating 
not sentences but noun phrases (technical terms),
using a different mechanism based on matching and similarity
on a MIMD machine.

\subsection{Speech-to-Speech Translation}

Challenging research on speech-to-speech translation began in the mid-1980s.
 Such research has brought about several prototype systems
\cite{Morimoto93,Kitano91d,Waibel91,Rayner93,HatazakiE92}.
However, no large-scale system capable of  responding
in real-time has emerged.
 Speech-to-speech translation consists of three processes,
i.e.  speech recognition, spoken language translation and speech
synthesis. 
There are two possible models for  speech-to-speech translation:
(1) a simultaneous model where subsequent processes start after a slight 
delay and 
overlap each other; and (2) a 
sequential model where processes start after their 
preceding process is completed. 
Unfortunately, state-of-the-art NLP technologies do not
allow us to adopt the  simultaneous model; thus, each component in the 
sequential 
model should be accelerated as much as possible.

\section{Concluding Remarks}

An EBA using APs has been proposed.
The translation quality of EBAs is high
according to our previous experiment. 
Using APs, EBAs have been drastically accelerated
with a good scalability against the size of the example database.
Consequently, an EBA using APs meets the critical requirements necessary to
break through the limitations of conventional machine 
translation, especially for spoken language translation. 

The acceleration and scalability of our method  using APs are due to 
the following: 
(1) ER strongly dominates EBAs;
(2) The AM's parallelism is employed for ER on a single AP;
(3) the  communication time among APs is controlled by the 
tree depth, which is fairly shallow.

EBAs using APs have desirable features 
suitable for integration with speech recognition:
(a) high accuracy; (b) robustness; 
(c)  output of a reliability score;
and (d) a quick response.
Tightly coupling our model and speech recognition might make possible
real-time speech-to-speech translation in the future.


\acknowledgment

The authors wish to acknowledge the help received from 
Dr. Yasuhiro YAMAZAKI (the President of ATR-ITL),  
Dr. Sakutaro TOMIYAMA (the Director of ETL), 
Dr. Hiroaki KITANO (CMU), and 
Kadokawa-shoten (the publisher of Ruigo-Shin-Jiten).

\bibliographystyle{nlpbbl}
\bibliography{epaper}

\newpage

\begin{biography}

\biotitle{}

\bioauthor{Eiichiro Sumita}
{
Eiichiro Sumita received the B.E. and M.E. degrees in computer science
from University of Electro-Communications, in Tokyo, in 1980 and 1982
respectively. He is a senior researcher of ATR Interpreting
Telecommunications Research Laboratories. His research interests include
natural language processing, information retrieval and parallel
processing. He is a member of IPSJ and IEICE.
}

\bioauthor{Kozo Oi}
{
Kozo Oi received the B.E. degree in electronic engineering from Doshisha
University, Kyoto, Japan, in 1984. He joined SANYO Electric Co., Ltd. in
1984. He has been on loan to ATR since 1992. He is now a researcher of
ATR Interpreting Telecommunications Research Laboratories. His research
interests are natural language processing and parallel processing. He is
a member of IPSJ.
}

\bioauthor{Osamu Furuse}
{
Osamu Furuse received the B.E. and M.E. degrees in information
engineering from Kyushu University, Fukuoka, Japan, in 1982 and 1984
respectively. From 1984 to 1990, he worked at NTT Electrical
Communication Laboratories. He has been on loan to ATR since 1990.
He is now a senior researcher of ATR Interpreting Telecommunications
Research Laboratories. He has been engaged in natural language
processing research.
}

\bioauthor{Hitoshi Iida}
{
Hitoshi Iida received a BS and an MS in mathematics in 1972 and 1974
from Waseda University. He joined the Electorical Communication\mbox{}
Laboratories of Nippon Telegaraph and Telephone in 1974 and has
temporarily moved to ATR Interpreting Telecommunications Research
Labs. His interests are dialogue comprehension and speech translation.
}

\bioauthor{Tetsuya Higuchi}
{
Tetsuya Higuchi received his BS, ME, and PhD degress in 1978, 1980, and
1984 from Keio University. He heads the computational models section at
Electrotechnical Laboratory. His research interests include parallel
processing and associative processing. He is a member of IPSJ.
}

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

\end{biography}

\end{document}

