


\documentstyle[epsf,nlpbbl]{jnlp_e}


\DeclareFontFamily{OT1}{pzc}{}
\DeclareFontShape{OT1}{pzc}{m}{it}
             {<-> s * [1.200] pzcmi7t}{}
\DeclareMathAlphabet{\mathscr}{OT1}{pzc}
                                 {m}{it}

\setcounter{page}{1}
\setcounter{巻数}{11}
\setcounter{号数}{5}
\setcounter{年}{2004}
\setcounter{月}{10}
\受付{xxx}{x}{xxxx}
\再受付{xxx}{x}{xxxx}
\採録{xxx}{x}{xxxx}

\setcounter{secnumdepth}{2}

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

\etitle{Paraphrasing as Machine Translation}

\eauthor{Andrew Finch\affiref{ATR}   \and
	Taro Watanabe\affiref{ATR}   \and
	Yasuhiro Akiba\affiref{ATR}  \and
	Eiichiro Sumita\affiref{ATR}}

\headauthor{Finch,~A.~et~al.}
\headtitle{Paraphrasing as Machine Translation}

\affilabel{ATR}
	  {Advanced Telecommunications Research Institute International, Spoken Language Research Laboratories, 2-2-2 Hikaridai, ``Keihanna Science City'', Kyoto 619-0224, Japan}
	  {Advanced Telecommunications Research Institute International, Spoken Language Research Laboratories, 2-2-2 Hikaridai, ``Keihanna Science City'', Kyoto 619-0224, Japan}

\eabstract
{
This article presents two statistically-based methods of 
automatically generating paraphrases for sentences; one based on direct
statistical machine translation, the other based on data-oriented techniques.
These paraphrasers are evaluated by human judges, and compared to both human 
paraphrases and those generated by a simple baseline model. The data-oriented
approach proved to be the most successful in this evaluation and a second
experiment was conducted to determine the usefulness of machine-generated
paraphrases when used to expand the reference set used for machine translation
evaluation. Varying numbers of synthetic paraphrases were mixed with varying numbers of real
references to determine the circumstances under which the addition of synthetic 
paraphrases might be useful. Nine different machine translation systems were evaluated in this
study using scores from nine human judges. Three machine translation evaluation schemes were
used to perform the machine translation evaluation: BLEU, NIST and mWER. 
The results show that the usefulness of the synthetic paraphrases depends on which of
the machine translation evaluation methods is used. The paraphrases degraded the NIST performance,
but improved the evaluation performance of both BLEU and mWER.
}

\ekeywords{Paraphrasing, Statistical Machine Translation, Data-Oriented, Hierarchical Phrase Alignment,
Agglomerative Clustering, Machine Translation Evaluation}


\begin{document}

\maketitle

\section{Introduction}

There are many problems in natural language processing for which having a paraphrase would be very useful
information. Tasks such as detailed parsing or  machine translation often fail or struggle on some sentences due
to a combination of their length and the nature of the sentence itself.  Having a paraphrase at hand would give
such systems a second chance, or  a chance to generate possibilities not considered using only the original
source sentence. Possible uses of a paraphraser include sentence summarization, corpus normalization and
improving automatic machine translation evaluation by expanding the reference set with paraphrases, one of the
main themes of this paper.

This article presents two automatic paraphrasers, one based on the principles of 
statistical machine translation, the other based on data-oriented translation methods.
We evaluate the performance of the paraphrasers using both human and automatic methods,
and apply the best paraphraser to the task of improving machine translation evaluation.
This article therefore is divided into two parts, 
the first part consisting of Sections~\ref{sec:smt} to \ref{sec:expt},
compares the quality of paraphrases produced by the automatic paraphrasers to those
produced by both humans, and a simple baseline model.
Section~\ref{sec:smt} introduces the concept of paraphrasing as machine translation. Section~\ref{sec:DOP}
explains the data-oriented approach to paraphrasing in detail. Section \ref{sec:expt} presents the experimental
evaluation of the automatic paraphrasers, and discusses these results.


In the second part of the article, Section \ref{sec:application}, we investigate the application of the
data-oriented paraphraser to the improvement of machine translation evaluation. We look at the effect of adding
automatically generated paraphrases to the reference sets used for machine translation evaluation. 
Section~\ref{sec:overview} gives a brief overview of these experiments. Section
\ref{sec:application:methodolody} explains the experimental methodology, describing the nature of the data, the
scoring methods, the machine translation systems involved in the experiments and the statistical methods
employed to evaluate the results. Section \ref{sec:application:results} presents the results. 
Section \ref{sec:application:analysis} describes an experiment designed to investigate the properties
of paraphrases that might make them  useful for machine translation evaluation. Finally, Section
\ref{sec:application:conclusion} offers some concluding remarks and directions for future research.

\section{Paraphrasing by Statistical Machine Translation}
\label{sec:smt}

It is possible to view the process of paraphrasing as a machine translation task.
This is the approach adopted throughout this paper. In this paradigm, a paraphrase of a textual segment
(in our case, a single sentence) is derived by a process of translation from the source language
{\em directly} into the same language. This process is direct in the sense that it is one-step, rather
than a ``round-trip'' translation from one language into the same language via an explicit second intermediate
interlingual stage.

\cite{finch:fit2002} evaluate a paraphraser (we will denote this SMTP) based on statistical machine translation 
(SMT) techniques \cite{Brown:93}. \cite{Quirk:04} use a similar technique, directly using SMT to generate
paraphrases with a phrase-based decoder. In our case, the publicly available GIZA++ software ~\cite{al-onaizan:99} was used
to build the models to be used for translation together with an in-house-developed multi-stack decoder. The
statistical machine translation technique learns to translate by  deriving statistics from a large corpus of
sentence pairs, one sentence in the pair being a sentence in the source language, the other sentence in the pair
being the translation of the source sentence in the target language (in our case this is a paraphrase of the
source sentence).  These statistics are then combined in a  reverse-channel model to provide the most probable
translation. In \cite{finch:fit2002}, a corpus of Japanese sentence pairs was prepared from a corpus consisting
of groups of paraphrases, by clustering the sentences within the group for similarity, and pairing similar
sentences from these clusters. The sentences in each pair being paraphrases of each other. The SMTP was then
trained directly from these sentence pairs.

The paraphrases from the SMTP system were compared to those generated by human annotators and also to those from
a simple baseline model based on maximum bi-gram probability used in~\cite{Knight:00}. The best paraphrase from
each of the sources was graded for adequacy according to the  scale defined in Section~\ref{sec:adequacy}
\cite{Doyon:98}. The results showed the paraphrases from the SMT-based system were superior to those of the
baseline model. We will use this system as the primary benchmark by which to judge the data-oriented paraphraser 
presented in the following sections.

\section{Data-Oriented Paraphrasing}
\label{sec:DOP}

Many alternative techniques are available for machine translation. This paper investigates the
application of data-oriented translation methods \cite{poutsma:98} to paraphrasing \cite{finch:ranlp2003}.
The basic principle is the same as the SMT-based approach, with only the underlying machine translation
methodology being different.

The data-oriented translation (DOT) model is based on data-oriented parsing (DOP) \cite{bod99beyond}. The principle
underlying data-oriented parsing is that parses for previously unseen sentences can be constructed in a
probabilistic manner by combining fragments (that are subtrees) of parse trees extracted from sentences of a
treebank corpus.  The fragments, in effect, form a grammar from which parse trees for unseen sentences can be
built.   Each parse may have many possible derivations, and the  parse probability is the sum of the
probabilities of each of its derivations. The latest incarnations of the DOP parser have performance comparable
to the state of the art in statistical parsers \cite{bod:01}.

The modus operandi of the data-oriented translation technique is similar to DOP. However, in this case, two
trees are constructed at the same time: a tree for the sentence in the source language, and the corresponding
tree for the sentence in the target language. The fragments in this case contain links between semantically
equivalent nodes in the source and target fragments, the idea being  that linked nodes can be interchanged
without loss of meaning.  A pair of linked trees is illustrated by the upper pair in Figure~\ref{fig:fragments}.
The following sections explain the nature of these fragments, their use in constructing new paraphrases, and 
the method used to extract them from the training corpus.



\subsection{Automatic Phrase Alignment}
\label{sec:phrasealign}

The process of fragment generation starts from a corpus of sentence pairs. The nature of the training data  is
the same as for the SMT approach. However, these sentence pairs are processed by a three-step process in order
to generate the fragments needed by the data-oriented paraphraser. The first step involves parsing the sentences
with a phrase-structure grammar. In the second step we automatically align the words of the sentences in each
pair. The third step is to align the non-leaf nodes in the parse trees, using an alignment of the words.


In contrast to \cite{poutsma:98}, we automatically label the links between equivalent nodes of the subtrees using a
technique based on \cite{Imamura:PhraseAlignment2001-2}. Hand labeling these links is extremely labor intensive, and 
being able to label them automatically gives us the ability create a large corpus without extensive human effort. 
The corpus used for the experiments reported in~\cite{poutsma:98} is only 266 tree pairs. We were able to use a corpus
of around 300,000 tree pairs for these experiments.  

Our aim is to map nodes in the source parse tree, denoted $\mathscr T^s=(\mathscr{V}^s, \mathscr{E}^s)$
to nodes in the  target tree, $\mathscr T^t=(\mathscr{V}^t, \mathscr{E}^t)$. Where $\mathscr{V}^s = \{v^s_1, v^s_2, \dots v^s_n\}$,
and $\mathscr{V}^t = \{v^t_1, v^t_2, \dots v^t_m\}$ are the vertex sets of the source and target trees respectively, and 
$\mathscr{E}^s$ and $\mathscr{E}^t$ are their edge sets.

The algorithm defines a mapping between a subset of the nodes of the source and target trees;
$\psi : \mathscr{V}^s \to \mathscr{V}^t$, and proceeds as follows:

\begin{enumerate}
\item  Parse the sentences --
For the purposes of these experiments we used the publicly available parser 
of~\cite{charniak99maximumentropyinspired}.

\item Align the words in the sentences --
We chose to use the word alignments output by the EGYPT machine translation 
software~\cite{al-onaizan:99}.
A set $\mathscr{L}$ of linked word pairs is produced.

\item Select $i$ ($0 < i < \vert\mathscr{L}\vert$) word links from among all of the links, collect all of the syntactic nodes (non-terminal symbols)
that include the links, and exclude all other word links in the leaves from the parsed trees.

\item Compare the syntactic categories of all nodes captured in process 3. When
identical node categories are found, regard the leaves of the nodes as equivalent
phrases. If candidates of a sentence or auxiliary verb phrase category are acquired,
the candidate which covers the maximum area is selected. In other ambiguous cases the
candidate which covers the minimum area is selected.

\item Repeat 3. and 4. for all word link combinations.

\end{enumerate}

\begin{figure}[t] 
\begin{center}
\epsfxsize=6cm
\mbox{\epsfbox{fragments_small.epsi}}
\end{center}
\vspace{-0.2in}
\caption{Examples of linked subtrees (fragments).}
\label{fig:fragments}
\end{figure}

\subsection{Linked Subtree Extraction}
\label{sec:fragments}

After the tree pairs have been linked, we extract linked subtrees (or fragments) of these pairs
that will be used as a grammar to derive the paraphrases (all of the tree pairs in Figure~\ref{fig:fragments}
are fragments). For each pair of linked trees, we collect all pairs of connected subtrees (and their
links), whose root nodes are linked, and  that satisfy all of the following conditions:

\begin{enumerate}
\item For each pair of linked nodes in the fragment, either; both nodes have no children, or all of the 
children from the corresponding original tree.
\item Every non-linked node in both subtrees of the fragment has all of the 
children from the corresponding original tree.
\item Both of the subtrees of the fragment consist of more than one node.
\end{enumerate}

The collection of all fragments from the corpus is termed the {\em bag of linked subtree pairs},  $\mathscr{B}$.
Each fragment $f_i$ has a count which represents the number of times that fragment occurred in the corpus.
When deriving a parse we use this count to compute the probability of selecting this fragment 
from the bag as the next step in a derivation, $P(f_i)$. The probability is simply its count, $\vert f_i \vert$,
divided by the sum of counts of all subtrees with the same root node label 
(the label of the root nodes of the trees in $f_i$ will be denoted $r(f_i)$)
in the bag of all linked subtrees. This probability is given by:

\begin{equation}
P( f_i ) = { \vert f_i \vert \over \sum_{f_j \in \mathscr{B}:r(f_j)=r(f_i)} \vert f_j \vert }
\end{equation}


\subsection{Paraphrase Derivation}

Derivations of paraphrases are constructed using the bag of linked subtree pairs by means of a composition operator.
Intuitively this operator defines the conditions for combining fragments, and is illustrated in
Figure~\ref{fig:derivations}. Formally, the operator is defined on two fragments $f_1 = \langle \mathscr{T}^{s_1},
\mathscr{T}^{t_1} \rangle$ and  $f_2 = \langle \mathscr{T}^{s_2}, \mathscr{T}^{t_2} \rangle$ iff. 
$r(f_2)$ is the same as the label of the leftmost non-word leaf node of $\mathscr{T}^{s_1}$. The result of this
composition is a linked tree pair $\langle \mathscr{T}^{s_3}, \mathscr{T}^{t_3} \rangle$ where $\mathscr{T}^{s_3}$ is
$\mathscr{T}^{s_1}$ with its leftmost non-word leaf node $v_{i}^{s_1}$ replaced by the source subtree of $f_2$,
$\mathscr{T}^{s_2}$.  By virtue of the manner in which fragments are constructed, this leftmost non-word leaf node,
will be linked to a node in the target subtree of the fragment; $\psi(v^{s_1}_i) = v^{t_1}_j$. Node $v^{t_1}_j$, is
replaced by the target subtree $\mathscr{T}^{t_2}$, to yield $\mathscr{T}^{t_3}$. We write this composition as
$\langle \mathscr{T}^{s_1}, \mathscr{T}^{t_1} \rangle \circ \langle \mathscr{T}^{s_2}, \mathscr{T}^{t_2} \rangle = \langle \mathscr{T}^{s_3}, \mathscr{T}^{t_3} \rangle$ 
or, more compactly, $f_1 \circ f_2 = f_3$. The probability a derivation $f_1 \circ f_2 \circ \cdots \circ f_N$ is given by:

\begin{equation}
P( f_1 \circ f_2 \circ \cdots \circ f_N ) = \prod_{i=1,N} P(f_i)
\end{equation}

A single target sentence $w_t$ can have many possible derivations from a source sentence
$w_s$. Summing over all possible derivations yields the paraphrase probability. We select the best
paraphrase as the one with the highest $P(w_t \vert w_s)$.

\begin{figure*}[t] 
\begin{center}
\epsfxsize=\textwidth
\mbox{\epsfbox{derivations_small.epsi}}
\end{center}
\caption{One derivation of the paraphrase ``{\em I enjoy tennis}'' from ``{\em I like tennis}''.}
\label{fig:derivations}
\end{figure*}

\subsection{Disambiguation}

It is necessary to find the most probable paraphrase, given all of the derivations arising from
the source sentence. In practice, the source sentence is parsed using a chart parser according
to the grammar of tree fragments defined by the source subtrees of the fragments in the bag
of all linked subtrees, naturally producing a (not necessarily correct) parse tree for the target paraphrase.

Since many derivations for the same sentence are possible, it is not sufficient to find
the most probable derivation (for which efficient search algorithms exist e.g.~\cite{bod99beyond}), 
but rather we must search over the sums of all derivations for the target paraphrase.
We adopt a conventional approach (e.g. \cite{poutsma:98}) of Monte Carlo 
sampling of the derivations to estimate the paraphrase probabilities. The idea being that a sufficiently large sample will
approximate the underlying distribution accurately. For the experiments in this paper, 1500 samples were used.

\subsection{Practical Considerations}
\label{sec:practical}

The experiments described here represent the first large-scale test of the DOT technique,
and problems arose due to the size of the task. A significant problem was caused by the large
number of fragments it is possible to generate, both overall, and from long sentences.  To
overcome this, we arbitrarily imposed a limit of 10,000 fragments from any single sentence,
and we also discarded any fragments that occurred less than a threshold (in this case 5)
number of times in the corpus. 
We also used a two-step approach to deriving the
paraphrases; in the first step we parsed the sentence with Charniak's parser, in the second we
derived the paraphrase in a manner that was consistent with the parse from the parser.
This reduced the size of the chart needed to parse the sentence, and also reduced the size 
of the search space, however even with this strong constraint on the parsing the number of fragments involved
in the parse, and size of the chart can still be large.

To handle the case of unknown words, and also ensure the system would always output at least one
paraphrase, the set of fragments generated from pairing the source sentence with itself was
added to the training set before the sentence was paraphrased.

\section{Experiments}
\label{sec:expt}

\subsection{Training Data}

The data we used for these experiments is a subset of the ATR Paraphrase
Corpus \cite{shimohara:fit2003}. The corpus consists of about
50,000 sentences (500,000 words) of paraphrased sentences drawn from the kind of
phrase books produced to aid travelers. There are
approximately 1000 seed sentences that have been paraphrased to produce this
data. That is, on average each of these 1000 seed sentences gave rise to approximately
50 paraphrased sentences. The paraphrases were paraphrases on the syntactic structure level
as opposed to simple word-synonym-based paraphrases. In this domain the sentences length is fairly
short, the average length of sentences in the corpus being approximately 10 words.
For the purposes of these experiments we generated 
approximately 300,000 sentence pairs using the technique described in the next subsection, 
although a larger number of pairs could have been generated. 
These sentence pairs were then parsed with Charniak's parser~\cite{charniak99maximumentropyinspired}
and their parse trees were linked using the method set out in Section~\ref{sec:phrasealign}.

\subsubsection{Sentence Pair Generation}
\label{sec:sentpair}

The training data for the data-oriented paraphraser consisted of pairs of paraphrases. The 
number of possible pairings is prohibitively large, therefore we select sentence pairs
from the set of all possible pairings. We generate the training data for the machine
translation system by first clustering the paraphrased sentences.  Note that the clustering is done within
groups of sentences that are paraphrases of a single seed sentence, all sentences within a cluster will therefore have the same meaning. 
The purpose of the clustering is to reduce the size of the training set in a manner which ensures 
that the sentence pairs used for training are relatively similar to each other
in terms of edit distance: the number of insertion, deletion or
word-for-word substitution operations required to transform one sentence into
another. We employed the following agglomerative clustering algorithm:

\begin{enumerate}
\item Assign each sentence in the set of paraphrased sentences to its own cluster; 
\item For each possible pair of clusters, calculate the distance between them (the average edit distance between members of the clusters);
\item Merge the two closest clusters;
\item Repeat from 2. until there is only one cluster.
\end{enumerate}




The result of this clustering is a tree, or dendrogram, the leaf nodes of this tree are sentences. Leaves that
are close to each other in the tree, are also similar in terms of edit distance. Non-leaf nodes define sets of
similar sentences.  Clusters of similar sentences of varying granularity can be extracted from the dendrogram by
selecting clusters of sentences which are the leaves of subtrees of the dendrogram.  We selected such subtrees
according to a threshold of average intra-cluster edit distance of their leaf nodes. The idea behind this is to
be able to select clusters of specified granularity from the dendrogram. The threshold was set arbitrarily
to control the number of sentences from which to generate paraphrases by selecting them from clusters of sentences with
approximately the same similarity between the sentences within the clusters. From the resulting
clusters we generated training examples by pairing the sentences in the  cluster. It is important to note that
although the pairings are made between pairs of similar sentences, the sentences also must be paraphrases
because the clustering is performed within groups of paraphrases.  For example, although the sentences ``I do
love you'' and ``I do not love you''  are similar, they will not appear in the training/test data because they
are not paraphrases of one another.

The motivation behind this approach is that sentences that are similar in terms of edit distance should also make
a good sentence pair in the training of a machine translation device because the  transformation necessary to
transform one sentence into the other is simpler.
Approximately 3 million fragments (after thresholding)
were extracted (using the methods described in Section~\ref{sec:fragments}) from the aligned tree pairs derived from these sentence pairs. 

\begin{figure}
\begin{flushleft}
\small
\begin{center}
\begin{tabular} {lp{8cm}}
{\bf Source} &    could you have this sweater dry cleaned\\
{\bf Human} &     please dry clean this sweater \\
{\bf DOPP} &      could you have this sweater dry cleaned for me please \\
{\bf SMTP} &       you have this sweater \\
{\bf Baseline} &  could you have \\
\\[-2mm]
\hline
\\[-2mm]
\textbf{Source} &    congratulations i heard you had a baby girl\\
\textbf{Human} &     congratulations i hear it 's a girl \\
\textbf{DOPP} &      congratulations i heard you was a baby girl\\
\textbf{SMT} &       i had a baby girl \\
\textbf{Baseline} &  i had a baby girl \\
\end{tabular}
\end{center}
\end{flushleft}
\caption{Examples of Paraphrasing both good and bad}
\label{figure:examples}
\end{figure}

\subsection{Evaluation}

We evaluated paraphrases from four sources: human paraphrases, a data-oriented paraphraser (DOPP), a statistical
machine translation based paraphraser (SMTP), and a simple baseline model.  The human paraphrases were a sample
of unseen human paraphrased sentences from the corpus. In the case of automatically generated output, we 
evaluated the highest probability sentence that differed from the original input sentence. The test data
consisted of unseen sentences drawn from the same sample as the  training data. Following \cite{Knight:00}, we
included a baseline model based on maximum word-bigram probability of the target sentence. The maximum
word-bigram probability baseline generates a necessarily shorted paraphrase of the original sentence by word
deletion, and therefore perhaps it is a little unfair to call it a baseline. We consider the direct SMT-based
system to be a superior baseline for paraphrasing because it provides higher quality true
paraphrases~\cite{finch:fit2002}.


\subsubsection{Statistical Machine Translation}

In \cite{finch:fit2002} paraphrases are generated for sentences directly using a statistical machine translation 
system trained on Japanese sentence pairs from a paraphrase corpus \cite{Sugaya:02}. We implemented a similar system based on IBM Model 3 to 
paraphrase English directly. The system consisted of the publicly available EGYPT software,
and an in-house-developed multi-stack decoder. The system was trained on the same data 
as the DOPP system. The sentences in Figure~\ref{figure:examples} show examples
of the input and output of the systems. 

The evaluation of machine translation output is always a controversial undertaking, therefore we have 
evaluated in three ways, using both automatic and human evaluation methods. These evaluation
methods are set out in the following sections.

\subsubsection{Adequacy Score}
\label{sec:adequacy}

We scored the paraphrases as machine translation
output using an adequacy test \cite{Doyon:98}. Sentences were
graded (from 1 to 5) by three independent native English speaking evaluators according to the following scale:
\begin{description}
\item[(Grade 5)] All meaning expressed in the source sentence is
present in the paraphrased sentence.
\item[(Grade 4)] Most of the meaning expressed in the source sentence
is present in the paraphrased sentence.
\item[(Grade 3)] Much of the meaning expressed in the source
sentence is present in the paraphrased sentence.
\item[(Grade 2)] Little of the meaning expressed in the source
sentence is present in the paraphrased sentence.
\item[(Grade 1)] None of the meaning expressed in the source
sentence is present in the paraphrased sentence.
\end{description}


40 sentences from each of the sources were mixed randomly and graded at the same time by
the three human judges who were told the sentences were all 
generated automatically.  The results are shown in Table~\ref{table:results}.
All annotators scored the systems in the order: baseline~$<$~SMTP~$<$~DOPP~$<$~human.
The results were
subjected to a $T$-test to determine whether all of the differences between the scores of the techniques were
significant. The tests show that at $p < 0.05$ this is the case.
All three annotators assigned the same score to a paraphrase in 47\% of cases. The
average inter-annotator agreement measured by the Kappa statistic was 0.63, only a moderate
level of agreement, pointing to the ambiguity of the classification task. 

\begin{table*}[ht]
\begin{center}
\begin{tabular}{l|c|c|c|c|}
&{\bf Grammaticality}&{\bf Adequacy}&{\bf NIST}&{\bf BLEU}\\
\hline
{\bf Human}&10&4.47&7.13&0.87\\
\hline
{\bf DOPP}&15&3.84&8.74&0.48\\
\hline
{\bf SMTP}&17&3.53&2.85&0.52\\
\hline
{\bf Baseline}&21&2.55&2.19&0.51\\
\hline
\end{tabular}
\end{center}
\caption{Experimental Results}
\label{table:results}
\end{table*}



\subsubsection{BLEU and NIST Scores}

In a second evaluation, we scored the output from the four paraphrase sources (i.e. human paraphrases, DOPP,
SMTP, and the simple baseline model) against a set of reference paraphrases consisting of 13 different
alternative human paraphrases for each test sentence. For this evaluation a 200-sentence superset of the test
set used for the adequacy evaluation was used.  The source sentences themselves were excluded from the reference
set. The output was scored using version 0.9c of the publicly available MTEVAL-KIT evaluation 
software~\cite{Doddington:02} 
for both NIST and BLEU scores.  These scores are shown in
Table~\ref{table:results}. All three automatic systems had considerably lower BLEU scores than the human.
However, the DOPP system had the highest NIST score. 



\subsubsection{Grammaticality}

In a final evaluation to measure the syntactic correctness of the paraphrases, we
used a novel technique based on Charniak's parser~\cite{charniak99maximumentropyinspired}.

Test sentences were parsed using the parser, and the number of incomplete sentence fragments (labeled with FRAG) in the parses was
counted. The underlying hypothesis being that the parser will have more difficulty
assigning syntactic structure to ungrammatical word sequences than to grammatical ones.

A simple experiment was performed to investigate this hypothesis. The evaluation set was gradually degraded by
interchanging words at random.  Each word in the 200 sentence test set was exchanged with a different
randomly-selected word from the same sentence with probability $P_i$. For each value of $P_i$, 20 different
random runs were conducted to get an estimate of the variance of the results. The results are shown in
Figure~\ref{fig:gramaticality} and show a clear relationship between sentence degradation and FRAG count. The
results for the four paraphrasing systems (shown in Table~\ref{table:results}) indicate that the
data-oriented paraphraser produces more grammatical output than both the SMTP system and the simple baseline model.

\begin{figure} 
\begin{center}
\epsfxsize=10.6cm
\mbox{\epsfbox{grammaticality_95_confidence.ps}}
\end{center}
\caption{Effect of gradual sentence degradation on parser failure. \\
         Error bars represent 95\% confidence interval of the mean.}
\label{fig:gramaticality}
\end{figure}


\subsection{Discussion}
\label{sec:conclusion1}

The DOPP paraphrasing system differs subjectively from the other systems in that the most probable paraphrase is
almost always the original sentence itself, and  many of the highly probable paraphrase candidates are similar
to the source sentence. The SMTP system by contrast seems to be more aggressive,  producing paraphrases that
often differ substantially from the source sentence. The DOPP system exhibits reasonable behavior for a
probabilistic system trained on this data. However, it does beg the question:  ``What do we mean by a good
paraphrase?''. For some applications, a sentence with significantly different structure  to the original source
will be desirable. The DOPP system is capable of producing such paraphrases, but they are not the most probable
candidates.

The results presented here are very promising. The DOPP system performed well; its score significantly better than the
baseline model, and as good as, or better than the output from the SMT-based system.  The clustering algorithm we employed, allowed us to
select a useful subset from the potentially huge training data, and by using an automatic method for aligning phrasal
structures in parse trees together with a purpose-made paraphrase corpus, we were able to generate sufficient data to
conduct the first large-scale evaluation of the DOT method. 

In the next section we investigate the usefulness of a paraphraser when used to expand machine translation
evaluation sets. We chose to use the data-oriented paraphraser as the automatic paraphraser for the following
experiments because it was the most successful automatic paraphraser in the initial study.




\section{Application to Machine Translation Evaluation}
\label{sec:application}

\subsection{Overview}
\label{sec:overview}

In machine translation (MT), the wide diversity of possible correct target translations of a single source
sentence makes it desirable to have as many references as possible when using automatic machine translation
evaluation. We examine the usefulness of applying an automatic paraphraser to augment the references in
the reference sets used for automatic MT evaluation. 

A data-oriented paraphraser was trained on a corpus of English sentence pairs which are paraphrases of each
other. Given an input English sentence, the paraphraser is able to probabilistically generate a large set of
paraphrases. Reference sets containing between 1 and 116 references were generated by mixing 1 to 16
human-produced references and up to 100 of their most probable paraphrases. The output from nine different MT
systems was then evaluated using these reference sets using three automatic scoring systems. The scored
sentences were then analyzed using Spearman Rank Correlation with the categorical scores assigned by the human
judges. The aim is to determine whether the additional synthetic paraphrases increase the correlation of the
automatic evaluation scheme's ranks to the human ranking. An increase in correlation indicating that the
automatic system is more similar to a human in ranking the MT output.

\subsection{Experimental Methodology}
\label{sec:application:methodolody}

\subsubsection{Test Data}

Our test data consisted of a set of 345 English sentences that have been translated from Japanese by nine
different machine translation systems (see later in this section).  These 345 English sentences have been randomly
selected from the Basic Travel Expression Corpus (BTEC) \cite{Takezawa:02}. Each output from the machine
translation systems was scored by nine independent native English speaking human evaluators who were also
familiar with the source language, Japanese. Each sentence was assigned a grade in accordance with the a
five-point scale for adequacy and grammaticality. A single grade was derived for each sentence by selecting the
median grade from the nine grades assigned by the human judges. Test sets of 1000 pseudo-documents were
constructed by taking random samples of 30 sentences from the 345 test sentences in the manner of
\cite{Turian:03}. This is because statistics based on short translations of a single sentence proved to be
unreliable.


\subsubsection{Reference Data}

For each of the 345 test sentences, 16 different reference
translations were prepared by human annotators.
These references were then paraphrased by
the data-oriented paraphraser, and the results ordered
according to the probability assigned by the
data-oriented paraphraser. Reference sets were
prepared with varying mixtures of paraphrased
and human references. The paraphrases being selected
according to probability. In the event that
insufficient paraphrases were produced by the
paraphraser for a particular sentence, the first human
reference was used in place of the missing
references, though this rarely occurred in practice.

\subsubsection{Automatic Scoring Methods}

We used three different automatic scoring systems for these
experiments: BLEU, NIST and mWER. These are described briefly below:

\begin{description}
\item[BLEU.] \cite{Papineni:01},
scores translation output by measuring the precision
of the component n-grams (1, 2, 3 and 4-
grams) of the sentences, with respect to a set of
reference translations. The score also includes a
brevity penally that penalizes differences in length
between the translation output and the references.

\item[NIST.] \cite{Doddington:02},
is based on weighted n-gram precision with a different
brevity penalty and different overall characteristics
to BLEU.

\item[mWER.] \cite{Niessen:02},
is based on edit distance. The score is the minimum edit distance between the
target sentence and the sentences in the reference
set.
\end{description}

\subsubsection{Corrected Spearman Rank Correlation}

Following \cite{Turian:03}, we chose to use Spearman Rank Correlation to evaluate how similar our automatic MT
evaluations were to human evaluations. Instead of correlating the absolute values of the scores themselves, the
scored test data is ordered by score, and assigned a rank indicating its position in this ordering. The ranks
themselves are then analyzed for correlation. By using this scheme we are placing importance on ensuring our
automatic scoring system ranks translations in the same way that a human judge would rank them, rather than
examining correlations in the absolute values assigned by the scoring methods. We chose to use a variant called
Corrected Spearman Rank Correlation which corrects for cases where tied ranks occur. Tied ranks can occur
in the human grading since there are only 5 categories.

\subsubsection{The Machine Translation Systems Used}
\label{sec:mtsystems}
The output from nine Japanese to English machine
translation systems was used for this study, these
consisted of three different releases, spaced at six
month intervals, of three types of MT system:
\begin{description}
\item[SMT (Statistical Machine Translation).] Using
the publicly domain GIZA++ software \cite{och00:isa} together with a multi-stack decoder.
\item[TDMT (Transfer Driven Machine Translation).]
A pattern-based MT system using hand-coded
syntactic transfer rules \cite{furuse:1996}.
\item[\boldmath{$D^3$} (DP-match Driven Transducer).] An example based
MT system using online-generated translation
patterns \cite{sumita:2001}.
\end{description}

\subsection{Results}
\label{sec:application:results}

\begin{figure} 
\begin{center}
\epsfxsize=0.7\textwidth
\mbox{\epsfbox{BLEU_vs_NIST_vs_EDIT_95_confidence.eps}}
\end{center}
\caption{
Correlation of human ranking with the automatic scoring techniques varying numbers of\\
human-created references only. Additional lines indicate the improved performance of\\
BLEU and mWER with optimal numbers of added paraphrases. \\
Error bars represent 95\% confidence interval of the mean.}
\label{fig:blue_nist_edit}
\end{figure}

\begin{figure} 
\begin{center}
\epsfxsize=0.7\textwidth
\mbox{\epsfbox{score_vs_numpara_BLEU.eps}}
\end{center}
\caption{
The correlation of the BLEU ranking with human ranking as the number of paraphrases\\
is increased. Increasing the number of references is always helpful, as is adding\\
up to 30 paraphrases.}
\label{fig:para_bleu}
\end{figure}

\begin{figure} 
\begin{center}
\epsfxsize=0.7\textwidth
\mbox{\epsfbox{score_vs_numreal_BLEU.eps}}
\end{center}
\caption{
The correlation of the BLEU ranking with human ranking as the number of \\
human-generated references is increased.}
\label{fig:real_bleu}
\end{figure}

\begin{figure} 
\begin{center}
\epsfxsize=0.7\textwidth
\mbox{\epsfbox{score_vs_numpara_NIST.eps}}
\end{center}
\caption{
The correlation of the NIST ranking with human ranking as the number of paraphrases is \\
increased. Adding paraphrases decreases the correlation with the human scoring.}
\label{fig:para_nist}
\end{figure}

\begin{figure} 
\begin{center}
\epsfxsize=0.7\textwidth
\mbox{\epsfbox{score_vs_numreal_NIST.eps}}
\end{center}
\caption{
The correlation of the NIST ranking with human ranking as the number of \\
human-generated references is increased.}
\label{fig:real_nist}
\end{figure}

\begin{figure} 
\begin{center}
\epsfxsize=0.7\textwidth
\mbox{\epsfbox{score_vs_numpara_EDIT.eps}}
\end{center}
\caption{
The correlation of the mWER ranking with human ranking as the number of paraphrases\\
is increased. Increasing the number of references is always helpful, as is adding \\
up to 10 paraphrases.
}
\label{fig:para_edit}
\end{figure}

\begin{figure} 
\begin{center}
\epsfxsize=0.7\textwidth
\mbox{\epsfbox{score_vs_numreal_EDIT.eps}}
\end{center}
\caption{
The correlation of the mWER ranking with human ranking as the number of \\
human-generated references is increased.
}
\label{fig:real_edit}
\end{figure}

Our results support the findings of ~\cite{Turian:03,Doddington:02}, showing that adding
more references to the references set improves the
MT evaluation performance, except in
the case of NIST where more than 4 references degrades
the evaluation performance (shown in Figure~\ref{fig:blue_nist_edit}). For NIST, 16
references offers a comparable level of performance
to just a single reference. A similar effect
was reported in~\cite{Doddington:02}.
Our main results (shown in Figures~\ref{fig:para_bleu} to \ref{fig:real_edit}),
show that (with the exception of NIST scoring) it
is possible for references generated by an automatic
paraphraser to improve machine translation
evaluation performance.
Results for BLEU are shown in Figures~\ref{fig:para_bleu} and
~\ref{fig:real_bleu}. Figure~\ref{fig:para_bleu} shows that the correlation with
the human ranking is increased by adding (up to about 30) paraphrases
for all numbers of human references. From
the graph it is apparent that adding more than 30
paraphrases does not result in improved evaluation
performance, and for larger numbers of human references
these additional references degrade evaluation
performance. When adding more than 30
paraphrases, the set of added paraphrases contains
many lower probability paraphrases which are incorrect,
or even nonsense sentences, however, although the
evaluation performance can be degraded, the effect
is small, the process being quite robust to the addition
of this noise. A possible explanation is that it
is unlikely for an incorrectly translated sentence to
be close to any of these noise paraphrases. The primary
factor determining the usefulness of the
added paraphrases being the number of correct
paraphrases added.
Figure~\ref{fig:real_bleu} shows the same result looking at the
effect of increasing the number of real references
with a fixed number of paraphrases. The bottom
line shows the effect of increasing the number of
references in the absence of any paraphrases. As
would be expected, the evaluation performance
steadily improves with the addition of more references.
The difference between the top and bottom
lines on the graph indicates the amount of improvement
due to adding varying numbers of paraphrases.
This is positive in all cases, but the
amount of improvement diminishes with increasing
numbers of references.
Analogous results for NIST are shown in Figures
~\ref{fig:para_nist} and~\ref{fig:real_nist}. These figures show that adding paraphrases
only degrades the performance of the
NIST scoring. This degradation was understandable,
since performance can be degraded even
when adding only human generated references
(Figure~\ref{fig:blue_nist_edit}).


It is difficult to explain why increasing the number of references to the NIST score does not result in better
correlation with the human ranking. One would expect that since the counts used in the estimates of information
contribution in the score were based on more data, the estimate would become more accurate, thereby improving
the effectiveness of the score. One possible contributing factor might be the composition of the n-gram's
influence. We observed that as the number of references increased, so did the proportion of the score that was
contributed by higher-order n-grams. Furthermore, we also observed that decreasing the maximum n-gram size used
by the scoring improved the correlation with human ranking on this data.

The results for mWER are shown in Figures~\ref{fig:para_edit} and~\ref{fig:real_edit}. 
Figure~\ref{fig:para_edit} shows that the performance is improved for all numbers of human references by adding
up to 10 paraphrases, but adding more than 10 results in degraded performance. For larger numbers of references
the degradation can give lower performance than that without added paraphrases. This effect is also shown in
Figure~\ref{fig:real_edit}, the line representing only human references cutting up though the lines for 15, 20
and 30 paraphrases as the number of references increases. However, Figure~\ref{fig:real_edit} also shows that
the performance of a single human reference augmented by 10 paraphrases is roughly equivalent to that with 4
human references.

\section{Further Analysis}
\label{sec:application:analysis}

This section describes an experiment to investigate what type of paraphrases might be the most useful to add.
There are many possible candidates to consider as factors which might influence a paraphrase's usefulness. For
example the criteria might  range from a method as simple as a sentence-length-based score, to something
involving a detailed syntactic or semantic analysis of the paraphrases. We investigate the effect of perhaps the
most obvious factor, that is how ``common'' the paraphrase is in the language. The assumption here being that a
paraphrase in the reference set is likely to be useful if it is a commonly used expression in the target
language. Put another way, obscure or infrequently used expressions are unlikely to be generated by the machine
translation system, and therefore references of this type cannot be expected to be as useful as commonly used
language. To test this hypothesis we performed an experiment where references were selected from the set of 16
human-produced references according to a language model probability. We built a simple unigram language model
from all 16 reference sentences for each individual translation, and then scored the reference sentences
themselves using this small language model. Since language models have a tendency to favour shorter sentences,
we used the average log probability per word to score the references rather than the true language model
probability. 

We constructed two separate reference sets for each experiment; one consisted of the top $N$ references
according to the language model, the other consisted of the bottom $N$ references according to the language
model. We ran experiments for the BLEU, NIST and mWER scoring systems, and we ran separate experiments using $N
=$ 1, 2, 4 and 8 references.  The results which are shown in Figures~\ref{fig:mini_lm} and
\ref{fig:mini_lm_evil} partially confirm the original hypothesis.  For all scoring systems and all numbers of
references it is the case that choosing the highest-ranked references according to the language model yields a
better machine translation evaluation than choosing the lowest-ranked references. However, both of these methods
for choosing paraphrases are worse than simply selecting paraphrases randomly. Choosing paraphrases ranked
highly by the language model being only slightly worse than random, and using low-ranked paraphrases being
considerably worse. One interpretation of these results is that the best strategy for selecting paraphrases no
strategy at all. When choosing references randomly we are sampling randomly from a set of 16 human-generated
paraphrases. When selecting high-scoring paraphrases using a language model, we are biasing our sample to
exclude rarer examples which (in appropriately small quantities) do improve evaluation performance. Perhaps the
old adage that the best type of data is more data holds true here. There may be other factors that do identify
specific charateristics of paraphrases as being more useful than others, but we leave this as an open topic for
future research.

\begin{figure} 
\begin{center}
\epsfxsize=0.9\textwidth
\mbox{\epsfbox{mini_lm_95_confidence.eps}}
\end{center}
\caption{
The correlation with human scoring using references selected to have a high language \\
model score. Error bars represent 95\% confidence interval of the mean.}
\label{fig:mini_lm}
\end{figure}

\begin{figure} 
\begin{center}
\epsfxsize=0.9\textwidth
\mbox{\epsfbox{mini_lm_evil_95_confidence.eps}}
\end{center}
\caption{
The correlation with human scoring using references selected to have a low language \\
model score. Error bars represent 95\% confidence interval of the mean.}
\label{fig:mini_lm_evil}
\end{figure}

\section{Conclusion}
\label{sec:application:conclusion}

The experiments reported here examine two different ways to automatically paraphrase text: by statistical
machine translation, and by data-oriented translation. The results show that according to a human assessment
of adequacy, the data-oriented method was the superior of the two methods. We presented experiments to determine
whether synthetic paraphrases generated by the data-oriented technique could improve automatic machine
translation evaluation. Synthetic paraphrases and human-generated paraphrases were mixed in varying proportions
and added to the reference sets for three automatic evaluation scoring methods. The correlation of the ranking
defined by these automatic scores with human ranking was used as a way of evaluating the evaluation. The results
were very encouraging, for BLEU and mWER scoring the performance was enhanced until the number of paraphrases
reached an optimal value. Preparing references by hand is an expensive process and the ability to obtain similar
evaluation performance using fewer human references is very desirable. In the future, we plan to develop the
paraphraser further. By improving the quality of the paraphrases we expect to increase the potency of this
technique.

\acknowledgment

This research was supported in part by the Telecommunications Advancement
Organization of Japan.


\newpage

\bibliographystyle{nlpbbl}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Al-Onaizan, Curin, Jahr, Knight, Lafferty, Melamed, Och,
  Purdy, Smith, \BBA\ Yarowsky}{Al-Onaizan et~al.}{1999}]{al-onaizan:99}
Al-Onaizan, Y., Curin, J., Jahr, M., Knight, K., Lafferty, J., Melamed, I.,
  Och, F., Purdy, D., Smith, N., \BBA\ Yarowsky, D. \BBOP 1999\BBCP.
\newblock \BBOQ Statistical machine translation\BBCQ\
\newblock In {\Bem Final report}\ JHU Workshop.

\bibitem[\protect\BCAY{Bod}{Bod}{2001}]{bod:01}
Bod, R. \BBOP 2001\BBCP.
\newblock \BBOQ {What is the Minimal Set of Fragments that Achieves Maximal
  Parse Accuracy?}\BBCQ\
\newblock In {\Bem Proceedings of ACL-2001}\ Toulouse, France.

\bibitem[\protect\BCAY{Bod}{Bod}{1999}]{bod99beyond}
Bod, R. \BBOP 1999\BBCP.
\newblock {\Bem Beyond Grammar---An Experience-Based Theory of Language}.
\newblock Cambridge University Press, Cambridge, England.

\bibitem[\protect\BCAY{Brown, Pietra, Pietra, \BBA\ Mercer}{Brown
  et~al.}{1993}]{Brown:93}
Brown, P., Pietra, S.~D., Pietra, V.~D., \BBA\ Mercer, R. \BBOP 1993\BBCP.
\newblock \BBOQ {The Mathematics of Statistical Machine Translation: Parameter
  Estimation}\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bem 19\/}(2), 263--311.

\bibitem[\protect\BCAY{Charniak}{Charniak}{1999}]{charniak99maximumentropyinsp
ired}
Charniak, E. \BBOP 1999\BBCP.
\newblock \BBOQ A Maximum-Entropy-Inspired Parser\BBCQ\
\newblock \BTR\ CS-99-12, {Brown University}.

\bibitem[\protect\BCAY{Doddington}{Doddington}{2002}]{Doddington:02}
Doddington, G. \BBOP 2002\BBCP.
\newblock \BBOQ {Automatic Evaluation of Machine Translation Quality Using
  N-gram Co-Occurrence Statistics}\BBCQ\
\newblock In {\Bem Proceedings of the HLT Conference}\ San Diego, California.

\bibitem[\protect\BCAY{Doyon, Taylor, \BBA\ White}{Doyon
  et~al.}{1998}]{Doyon:98}
Doyon, J., Taylor, K., \BBA\ White, J. \BBOP 1998\BBCP.
\newblock \BBOQ {The DARPA MT Evaluation Methodology: Past and Present}\BBCQ\
\newblock In {\Bem Proceedings of the ATMA Conference}\ Philadelphia, PA.

\bibitem[\protect\BCAY{Finch, Watanabe, \BBA\ Sumita}{Finch
  et~al.}{2002}]{finch:fit2002}
Finch, A., Watanabe, T., \BBA\ Sumita, E. \BBOP 2002\BBCP.
\newblock \BBOQ Paraphrasing by Statistical Machine Translation\BBCQ\
\newblock In {\Bem Proceedings of FIT2002}\ Tokyo, Japan.

\bibitem[\protect\BCAY{Finch, Watanabe, \BBA\ Sumita}{Finch
  et~al.}{2003}]{finch:ranlp2003}
Finch, A., Watanabe, T., \BBA\ Sumita, E. \BBOP 2003\BBCP.
\newblock \BBOQ Data-Oriented Paraphrasing\BBCQ\
\newblock In {\Bem Proceedings of RANLP2003}\ Borvets, Bulgaria.

\bibitem[\protect\BCAY{Furuse \BBA\ Iida}{Furuse \BBA\
  Iida}{1996}]{furuse:1996}
Furuse, O.\BBACOMMA\  \BBA\ Iida, H. \BBOP 1996\BBCP.
\newblock \BBOQ Incremental translation utilizing constituent boundary
  patterns\BBCQ\
\newblock In {\Bem Proceedings of COLING96}, \BPGS\ 412--417\ Copenhagen,
  Denmark.

\bibitem[\protect\BCAY{Imamura}{Imamura}{2001}]{Imamura:PhraseAlignment2001-2}
Imamura, K. \BBOP 2001\BBCP.
\newblock \BBOQ Hierarchical Phrase Alignment Harmonized with Parsing\BBCQ\
\newblock In {\Bem The 6th Natural Language Processing Pacific Rim Symbopium
  (NLPRS-2001)}, \BPGS\ 377--384.

\bibitem[\protect\BCAY{Knight \BBA\ Marcu}{Knight \BBA\
  Marcu}{2000}]{Knight:00}
Knight, K.\BBACOMMA\  \BBA\ Marcu, D. \BBOP 2000\BBCP.
\newblock \BBOQ {Statistics-Based Summarization - Step One: Sentence
  Compression}\BBCQ\
\newblock In {\Bem National Conference on Artificial Intelligence (AAAI)},
  \BPGS\ 703--710\ Texas, USA.

\bibitem[\protect\BCAY{Niessen, Och, \BBA\ Ney}{Niessen
  et~al.}{2000}]{Niessen:02}
Niessen, S., Och, F., \BBA\ Ney, H. \BBOP 2000\BBCP.
\newblock \BBOQ {An evaluation tool for machine translation: Fast evaluation
  for machine translation research}\BBCQ\
\newblock In {\Bem Proceedings of the LREC Conference}\ Athens, Greece.

\bibitem[\protect\BCAY{Och \BBA\ Ney}{Och \BBA\ Ney}{2000}]{och00:isa}
Och, F.~J.\BBACOMMA\  \BBA\ Ney, H. \BBOP 2000\BBCP.
\newblock \BBOQ Improved Statistical Alignment Models\BBCQ\
\newblock In {\Bem ACL00}, \BPGS\ 440--447\ Hong Kong, China.

\bibitem[\protect\BCAY{Papineni, Roukos, Ward, \BBA\ Zhu}{Papineni
  et~al.}{2001}]{Papineni:01}
Papineni, K., Roukos, S., Ward, T., \BBA\ Zhu, W. \BBOP 2001\BBCP.
\newblock {\Bem {Bleu: a Method for Automatic Evaluation of Machine
  Translation}}.
\newblock IBM Research Report rc22176 (w0109022), Thomas J. Watson Research
  Center.

\bibitem[\protect\BCAY{Poutsma}{Poutsma}{1998}]{poutsma:98}
Poutsma, A. \BBOP 1998\BBCP.
\newblock \BBOQ {Data-Oriented Translation}\BBCQ\
\newblock In {\Bem Ninth Conference of Computational Linguistics in the
  Netherlands}\ Leuven, Belgium.

\bibitem[\protect\BCAY{Quirk, Brockett, \BBA\ Dolan}{Quirk
  et~al.}{2004}]{Quirk:04}
Quirk, C., Brockett, C., \BBA\ Dolan, W. \BBOP 2004\BBCP.
\newblock \BBOQ {Monolingual Machine Translation for Paraphrase
  Generation}\BBCQ\
\newblock In {\Bem Proceedings of the 2004 Conference on Empirical Methods in
  Natural Language Processing}\ Barcelona, Spain.

\bibitem[\protect\BCAY{Shimohata, Takezawa, \BBA\ Kikui}{Shimohata
  et~al.}{2003}]{shimohara:fit2003}
Shimohata, M., Takezawa, T., \BBA\ Kikui, G. \BBOP 2003\BBCP.
\newblock \BBOQ Construction and Analysis of English Synonymous Expression
  Corpus\BBCQ\
\newblock In {\Bem Proceedings of FIT2003}\ Tokyo, Japan.

\bibitem[\protect\BCAY{Sugaya, Takezawa, \BBA\ Kikui}{Sugaya
  et~al.}{2002}]{Sugaya:02}
Sugaya, F., Takezawa, T., \BBA\ Kikui, G. \BBOP 2002\BBCP.
\newblock \BBOQ {Proposal of a very-large-corpus acquisition method by
  cellformed registration}\BBCQ\
\newblock In {\Bem Proceedings of the LREC Conference}\ Las Palmas, Gran
  Canaria.

\bibitem[\protect\BCAY{Sumita}{Sumita}{2001}]{sumita:2001}
Sumita, E. \BBOP 2001\BBCP.
\newblock \BBOQ Example-based machine translation using DP-matching between
  word sequences\BBCQ\
\newblock In {\Bem Proceedings of the ACL 2001 Workshop on DDMT}, \BPGS\ 1--8\
  Toulouse, France.

\bibitem[\protect\BCAY{Takezawa, Sumita, Sugaya, Yamamoto, \BBA\
  Yamamoto}{Takezawa et~al.}{2002}]{Takezawa:02}
Takezawa, F., Sumita, E., Sugaya, F., Yamamoto, H., \BBA\ Yamamoto, S. \BBOP
  2002\BBCP.
\newblock \BBOQ {Toward a Broad-coverage Bilingual Corpus for Speech
  Translation of Travel Conversations in the Real World}\BBCQ\
\newblock In {\Bem Proceedings of the LREC Conference}\ Las Palmas, Gran
  Canaria.

\bibitem[\protect\BCAY{Turian, Shen, \BBA\ Melamed}{Turian
  et~al.}{2003}]{Turian:03}
Turian, J., Shen, L., \BBA\ Melamed, I. \BBOP 2003\BBCP.
\newblock \BBOQ {Evaluation of Machine Translation and its Evaluation}\BBCQ\
\newblock In {\Bem Proceedings of MT Summit IX}\ New Orleans, LA.

\end{thebibliography}

 \begin{biography}
 
\biotitle{}

\bioauthor{Andrew Finch}  
{  
Andrew FINCH received the B.S. degree in mathematics  and the M.Sc. degree in
cognition, computing and psychology, both from the University of Warwick, England, in 1984 and 1990,
respectively. He received a Ph.D. in computer science in 1995 from the University of York, England. From 1995 to
1997 he worked as a postdoctoral researcher in the computer vision research group at the University of York. In
1997 he received an Honorable Mention of the Pattern Recognition Society Award for Outstanding Contribution to
the Pattern Recognition journal. From 1997 to the present day, he is a researcher at ATR Spoken Language
Translation Research Laboratories, Kyoto, Japan. His current research interests include tagging, parsing,
machine translation, and automatic paraphrasing.  
}

\bioauthor{Taro Watanbe}
{
Taro WATANABE received B.E., M.E. and Ph.D. degrees in information science from Kyoto
University, Kyoto, Japan in 1994, 1997 and 2004, respectively. He received a Master of
Science degree in language and information technologies from the School of
Computer Science, Carnegie Mellon University in 2000.
Now a researcher at ATR Spoken Language Translation
Laboratories. Current interests are natural language processing,
machine learning and statistical machine translation.
}

\bioauthor{Yasuhiro Akiba}
{
Yasuhiro AKIBA received the degrees of B.Sc. and M.Sc. in mathematics
from  Waseda University, Tokyo, Japan in 1988 and 1990, respectively.
In April 1990, he joined NTT (Nippon Telegraph ad Telephone Corporation)
From May 1990 to September 2000, he worked as a researcher of NTT
Research and Development, Japan. In October 2000, He moved to ATR
(Advanced Telecommunications Research Institutes International), Kyoto
Japan. He is currently with ATR Spoken Language Translation Research
Laboratories as a Senior Researcher and with graduate school of
Infomatics, Kyoto University, as a Ph.D candidate.
His research interests include machine learning, knowledge
acquisition, natural language learning, machine translation, 
and automatic evaluation.
He received the best paper award of the Ninth Annual Conference
of the Japan Society for Artificial Intelligence in 1995 and 
the CV Ramamoorthy best paper award of the Twelfth IEEE International
Conference on Tools with Artificial Intelligence in 2000. 
He is a member of the Information Processing Society of Japan. 
From April 1999 to March 2001, he was a member of the editorial board
of IPSJ magazine. 
}

\bioauthor{Eiichiro Sumita}
{
Eiichiro SUMITA received B.E. and M.E. degrees in computer science both
from University of Electro-Communications, Japan,  in 1980 and 1982
respectively.
He received  a Ph.D in engineering from Kyoto University, Japan, in 1999.
He is a Senior Researcher of ATR Spoken Language Translation Research
Laboratories, Kyoto, Japan.
His research interests include natural language processing, machine
translation,
information retrieval, automatic evaluation, e-Learning and parallel
processing.
He is a member of the IEICE and the IPSJ, and the ACL.
}

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

\end{biography}

\end{document}

