\documentclass[acmtocl,acmnow]{acmtrans2m}
\usepackage[dvips]{graphicx}
\usepackage{epsfig}
\usepackage{psfig}

%\documentclass[]{article}
%\usepackage{fullpage}
%\usepackage{11pt}

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{lemma}[theorem]{Lemma}
%\newdef{definition}[theorem]{Definition}
%\newdef{remark}[theorem]{Remark}

\newcommand{\xfer}{{\sc Xfer} }

\newcommand{\argmax}{\mathop{\mbox{argmax}}}

\newcommand{\BibTeX}{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}

           
\markboth{Alon Lavie et al.}{Experiments with a Hindi-to-English 
Transfer-based MT System}

\begin{document}

\title{Experiments with a Hindi-to-English Transfer-based MT System under
a Miserly Data Scenario}

\author{Alon Lavie, Stephan Vogel, Lori Levin, Erik Peterson, Katharina Probst,
	Ariadna Font Llitj\'{o}s, Rachel Reynolds, Jaime Carbonell\\
	Language Technologies Institute, Carnegie Mellon University,
	Pittsburgh, PA, 15213 \and Richard Cohen\\
        University Center for International Studies, University of Pittsburgh,
        Pittsburgh, PA, 15260}
            
\begin{abstract} 
We describe an experiment designed to evaluate the capabilities of our
trainable transfer-based (\xfer) machine translation approach, as applied to
the task of Hindi-to-English translation, and trained under an extremely
limited data scenario.  We compare the performance of the \xfer approach with
two corpus-based approaches -- Statistical MT (SMT) and Example-based MT
(EBMT) -- under the limited data scenario.  The results indicate that the
\xfer system significantly outperforms both EBMT and SMT in this scenario.
Results also indicate that automatically learned transfer rules are effective
in improving translation performance, compared with a baseline word-to-word
translation version of the system.  \xfer system performance with a limited
number of manually written transfer rules is, however, still better than the
current automatically inferred rules.  Furthermore, a ``multi-engine'' version
of our system that combined the output of the \xfer and SMT systems and
optimizes translation selection outperformed both individual systems.
\end{abstract}


\category{I.2.7}{Artificial Intelligence}{Natural Language Processing}[Machine
Translation]
            
\terms{Evaluation, Hindi, Machine Translation} 

\keywords{Example-based Machine Translation, Limited Data Resources,
Machine Learning, Multi-Engine Machine Translation, Statistical Translation, 
Transfer Rules}

            
\begin{bottomstuff} 
\end{bottomstuff}
            
\maketitle


%% OUTLINE:
%%
%% (1) Introduction
%%     - rationale for XFER approach
%%     - Hindi SLE and our role in it
%%     - why design miserly data scenario
%%     - the experiment and its results
%%     - structure of paper
%% (2) System Overview
%% (3) Elicited Data Collection
%% (4) The Hindi-to-English System
%%     - Morphology
%%     - Lexica
%%     - Grammars
%%     - Runtime Configuration
%% (5) The Experiment
%%     - Data Scenario
%%     - Testing Configuration
%%     - Evaluation Results
%%     - Discussion
%% (6) Conclusions and Future Work


\section{Introduction}

Corpus-based Machine Translation (MT) approaches such as Statistical Machine
Translation (SMT) \cite{BrownEtAl1990,BrownEtAl1993,VogelTribble2002,YamadaKnight2001,PapineniEtAl1998,OchNey2002} and Example-based Machine
Translation (EBMT) \cite{Brown1997,SatoNagao1990} have received much attention
in recent years, and have significantly improved the state-of-the-art of
Machine Translation for a number of different language pairs.  These
approaches are attractive because they are fully automated, and require orders
of magnitude less human labor than traditional rule-based MT approaches.
However, to achieve reasonable levels of translation performance, the
corpus-based methods require very large volumes of sentence-aligned parallel
text for the two languages -- on the order of magnitude of a million words or
more.  Such resources are only currently available for only a small number of 
language pairs.  While the amount of online resources for many languages
will undoubtedly grow over time, many of the languages spoken by smaller
ethnic groups and populations in the world will not have such resources
within the forseeable future.  Corpus-based MT approaches will therefore not be
effective for such languages for some time to come.

Our MT research group at Carnegie Mellon, under DARPA and NSF funding, has
been working on a new MT approach that is specifically designed to enable
rapid development of MT for languages with limited amounts of online
resources.  Our approach assumes the availability of a small number of
bi-lingual speakers of the two languages, but these need not be linguistic
experts.  The bi-lingual speakers create a comparatively {\it small} corpus of
word aligned phrases and sentences (on the order of magnitude of a few
thousand sentence pairs) using a specially designed elicitation tool.  From
this data, the learning module of our system automatically infers hierarchical
syntactic transfer rules, which encode how constituent structures in the
source language transfer to the target language.  The collection of transfer
rules is then used in our run-time system to translate previously unseen
source language text into the target language.  We refer to this system as the
``Trainable Transfer-based MT System'', or in short the \xfer system.

The DARPA-sponsored ``Surprise Language Exercise'' (SLE) of June 2003 provided
us with a golden opportunity to test out the capabilities of our approach.
The Hindi-to-English system that we developed in the course of this exercise
was the first large-scale open-domain test for our system.  Our goal was to
compare the performance of our \xfer system with the corpus-based SMT and EBMT
approaches developed both within our group at Carnegie Mellon, and by our
colleagues elsewhere.  Common training and testing data were used for the
purpose of this cross-system comparison.  The data was collected throughout
the SLE during the month of June 2003.  As data resources became available, it
became clear that the Hindi-to-English was in fact not a ``limited-data''
situation.  By the end of the SLE, over 1.5 million words of parallel
Hindi-English text had been collected, which was sufficient for development of
basic-quality SMT and EBMT systems.  In a common evaluation conducted at the
end of the SLE, the SMT systems that participated in the evaluation
outperformed our \xfer system, as measured by the NIST automatic MT evaluation
metric \cite{Doddington2002}. Our system received a NIST score of 5.47, as
compared with the best SMT system, which received a score of 7.61.

Our intention, however, was to test our \xfer system under a far more
limited data scenario than the one that had developed by the end of
the SLE
(\cite{Nirenburg1998,SherematyevaNirenburg2000,JonesHavrilla1998}).
We therefore designed an ``artificial'' extremely limited data
scenario, where we limited the amount of available training data to
about 50 thousand words of word-aligned parallel text that we had
collected during the SLE.  We then designed a controlled experiment in
order to compare our \xfer system with our in-house SMT and EBMT
systems under this limited data scenario.  The design, execution and
results of this experiment are the focus of this paper.  The results
of the experiment indicate that under these extremely limited training
data conditions, when tested on unseen data, the \xfer system
significantly outperforms both EBMT and SMT.  Several different
versions of the \xfer system were tested.  Results indicated that
automatically learned transfer rules are effective in improving
translation performance, compared with a baseline word-to-word
translation version of our system.  System performance with a limited
number of manually written transfer rules was, however, still better
than the current automatically inferred rules.  Furthermore, a
``multi-engine'' version of our system that combined the output of the
\xfer and SMT systems and optimizes translation selection outperformed
both individual systems.

The remainder of this paper is organized as follows.  Section~\ref{sys}
presents an overview of the \xfer system and its components.
Section~\ref{data} describes the elicited data collection for Hindi-English
that we conducted during the SLE, which provided the bulk of training data for 
our limited data experiment.  Section~\ref{hindi} describes the specific
resources and components that were incorporated into our Hindi-to-English
\xfer system.  Section~\ref{exp} then describes the controlled experiment for
comparing the \xfer, EBMT and SMT systems under the limited data scenario,
and the results of this experiment.  Finally, Section~\ref{conc} describes our
conclusions and future research directions.

\section{Trainable Transfer-based MT Overview}
\label{sys}

\begin{figure}[t]
\begin{center}
\includegraphics[scale=.5]{SystemDiagram.eps}
\end{center}
\caption{Architecture of the \xfer MT System and its Major Components}
\label{SystemArchitecture}
\end{figure}



The fundamental principles behind the design of our \xfer approach for MT are
that it is possible to automatically learn syntactic transfer rules from
limited amounts of word-aligned data, that such data can be elicited from
non-expert bilingual speakers of the pair of languages, and that the rules
learned are useful for machine translation between the two languages.  We
assume that one of the two languages involved is a ``major'' language (such as
English or Spanish) for which significant amounts of linguistic resources and
knowledge are available.  

The \xfer system consists of four main sub-systems: elicitation of a word
aligned parallel corpus; automatic learning of transfer rules; the run time
transfer system; and a statistical decoder for selection of a final
translation output from a large lattice of alternative translation fragments
produced by the transfer system.  Figure~\ref{SystemArchitecture} shows how
the four sub-systems are used in a configuration in which the translation is
from a limited-resource source language into a major target language, such
as English.

\subsection{Elicitation of Word-Aligned Parallel Data}

The purpose of the elicitation sub-system is to collect a high quality, word
aligned parallel corpus.  A specially designed user interface was developed to
allow bilingual speakers to easily translate sentences from a corpus of the
{\em major language} (i.e. English) into their native language (i.e. Hindi),
and to graphically annotate the word alignments between the two sentences.
Figure~\ref{E-tool} contains a snap-shot of the elicitation tool, as used in
the translation and alignment of an English sentence into Hindi.  The
informant must be bilingual and literate in the language of elicitation and
the language being elicited, but does not need to have knowledge of
linguistics or computational linguistics.  

The word-aligned elicited corpus is the primary source of data from which
transfer rules are inferred by our system.  In order to support effective rule
learning, we designed a ``controlled'' English elicitation corpus.  
The design of this corpus was based on elicitation principles from field
linguistics, and the variety of phrases and sentences attempts to cover
a wide variety of linguistic phenomena that the minor language may or may
not possess.  The elicitation process is organized along ``minimal pairs'',
which allows us to identify whether the minor languages possesses specific 
linguistic phenomena (such as gender, number, agreement, etc.).  The sentences 
in the corpus are ordered in groups corresponding to constituent types of
increasing levels of complexity.  The ordering supports the goal of learning
compositional syntactic transfer rules.  For example, simple noun phrases are
elicited before prepositional phrases and simple sentences, so that during
rule learning, the system can detect cases where transfer rules for NPs can
serve as components within higher-level transfer rules for PPs and sentence
structures.  The current controlled elicitation corpus contains about 2000 
sentences.  It is by design very limited in vocabulary.  A more detailed
description of the controlled elicitation corpus, the elicitation process and
the interface tool used for elicitation can be found in \cite{ProbstEtAl2001},
\cite{ProbstLevin2002}.

\begin{figure}[t]
\begin{center}
\includegraphics[scale=.4]{E-tool-Hindi.orig.epsi}
\end{center}
\caption{The Elicitation Interface as Used to Translate and Align an English
Sentence into Hindi}
\label{E-tool}
\end{figure}

\subsection{Automatic Transfer Rule Learning}

The rule learning system takes the elicited, word-aligned data as input.
Based on this information, it then infers syntactic transfer rules.  The
learning system also learns the composition of transfer rules.  In the
compositionality learning stage, the learning system identifies cases where
transfer rules for ``lower-level'' constituents (such as NPs) can serve as
components within ``higher-level'' transfer rules (such as PPs and sentence
structures).  This process generalizes the applicability of the learned
transfer rules and captures the compositional makeup of syntactic
correspondences between the two languages.  The output of the rule learning
system is a set of transfer rules that then serve as a transfer grammar in the
run-time system.  The transfer rules are comprehensive in the sense that they
include all information that is necessary for parsing, transfer, and
generation.  In this regard, they differ from `traditional' transfer rules
that exclude parsing and generation information.  Despite this difference, we
will refer to them as transfer rules.

The design of the transfer rule formalism itself was guided by the
consideration that the rules must be simple enough to be learned by an
automatic process, but also powerful enough to allow manually-crafted
rule additions and changes to improve the automatically learned rules.

The following list summarizes the components of a transfer rule. In
general, the x-side of a transfer rules refers to the source language
(SL), whereas the y-side refers to the target language (TL).

\begin{itemize} 
\item{\textbf{Type information:}}
This identifies the type of the transfer rule and in most cases corresponds to
a syntactic constituent type.  Sentence rules are of type {\tt S}, noun phrase 
rules of type {\tt NP}, etc.  The formalism also allows for SL and TL type 
information to be different.

\item{\textbf{Part-of speech/constituent information:}} 
For both SL and TL, we list a linear sequence of components that constitute an 
instance of the rule type.  These can be viewed as the `right-hand sides' of 
context-free grammar rules for both source and target language grammars. The 
elements of the list can be lexical categories, lexical items, and/or phrasal 
categories.

\item{\textbf{Alignments:}}
Explicit annotations in the rule describe how the set of source language 
components in the rule align and transfer to the set of target language 
components.  Zero alignments and many-to-many alignments are allowed.

\item{\textbf{X-side constraints:}} 
The x-side constraints provide information about features and their values in 
the source language sentence.  These constraints are used at run-time to 
determine whether a transfer rule applies to a given input sentence.

\item{\textbf{Y-side constraints:}}
The y-side constraints are similar in concept to the x-side constraints, but 
they pertain to the target language. At run-time, y-side constraints serve to 
guide and constrain the generation of the target language sentence.

\item{\textbf{XY-constraints:}} 
The xy-constraints provide information about which feature values transfer 
from the source into the target language.  Specific TL words can obtain 
feature values from the source language sentence.
\end{itemize}


%% It turned out to be harder than I expected to get an example of a
%% sentence that our rules can handle.

%% From Richard:
%% ab tak patr .dAk se bheje jAte hai.m (Letters continue to be sent
%% by mail.) This sentence uses the passive in the present habitual
%% tense. 

%% In order to make this fit our rule, I had to change the translation
%% to "Letters are still being sent by mail").

%% I checked the word-for-word gloss with Richard, but I did not check
%% with Richard "Letters are still being sent by mail" is a valid way
%% to express that. 

%% I also had to change rule 25: (1) to be for only present tense, (2)
%% took out verb agreement because Hindi verbs do not always agree
%% with the subject, (3) to include "being".

For illustration purposes, Figure~\ref{rule1} shows an example of a
transfer rule for translating the verbal elements of a present tense
sentence in the passive voice.  This rule would be used in translating
the verb sequence {\it bheje jAte h\~{ai}\/} (``are being sent,''
literally, {\it sent going pre\-sent-tense-aux\-il\-iary\/}) in a
sentence such as {\it Ab-tak patr .dAk se bheje jAte h\~{ai}.\/}
(``Letters still are being sent by mail'', literally {\it up-to-now
letters mail by sent going pre\-sent-tense-aux\-il\-iary\/}).  The
{\tt x}-side constraints in Figure~\ref{rule1} show that the Hindi
verb sequence consists of a perfective participle ({\tt x1}), the
passive auxiliary ({\it jAnA\/}, ``go'') inflected as an imperfective
participle ({\tt x2}), and an auxiliary verb in the present tense
({\tt x3}).  The {\tt y}-side constraints show that the English verb
sequence starts with the auxiliary verb {\it be\/} in the present tense
({\tt y1}).  The second element in the English verb sequence is {\it
being\/}, whose form is invariant in this context.  The English verb
sequence ends with a verb in past participial form ({\tt y3}).  The
alignment ({\tt X1::Y3}) shows that the first element of the Hindi
verb sequence corresponds to the last verb of the English verb
sequence.

\begin{figure}[t]
\renewcommand{\baselinestretch}{1}
\footnotesize
\begin{verbatim}
;; PASSIVE SIMPLE PRESENT 
VP::VP : [V V Aux] -> [Aux being V]
(
  (X1::Y3)
  ((x1 form) = part)
  ((x1 aspect) = perf)
  ((x2 form) = part)
  ((x2 aspect) = imperf)
  ((x2 lexwx) = 'jAnA')
  ((x3 lexwx) = 'honA')
  ((x3 tense) = pres)
  ((x0 tense) = (x3 tense))
  (x0 = x1)
  ((y1 lex) = be)
  ((y1 tense) = pres)
  ((y3 form) = part) 
)
\end{verbatim}
\caption{A transfer rule for present tense verb sequences in the
passive voice}
\label{rule1}
\end{figure}

\normalsize

Rules such as the one shown in Figure~\ref{rule1} can be written by
hand or learned automatically from elicited data.  Learning from
elicited data proceeds in three stages: the first phase, Seed
Generation, produces initial `guesses' at transfer rules.  The rules
that result from Seed Generation are `flat' in that they specify a
sequence of parts of speech, and do not contain any non-terminal or
phrasal nodes.  The second phase, Compositionality Learning, adds
structure using previously learned rules.  For instance, it learns
that sequences such as {\tt Det N P} and {\tt Det Adj N P} can be
re-written more generally as {\tt NP P} as an expansion of PP in
Hindi.  This generalization process can be done automatically based on
the flat version of the rule, and a set of previously learned transfer
rules for NPs.

The first two stages of rule learning result in a collection of
structural transfer rules that are context-free -- they do not contain
any unification constraints that limit their applicability.  Each of
the rules is associated with a collection of elicited examples from
which the rule was created.  The rules can thus be augmented with a
collection of unification constraints, based on specific features that
are extracted from the elicited examples.  The constraints can then
limit the applicability of the rules, so that a rule may ``succeed''
only for inputs that satisfy the same unification constraints as the
phrases from which the rule was learned.  A constraint relaxation
technique known as ``Seeded Version Space Learning'' attempts to
increase the generality of the rules by identifying unification
constraints that can be relaxed without introducing translation
errors. Detailed descriptions of the rule learning process can be
found in \cite{ProbstEtAl2003}.


\subsection{The Runtime Transfer System}

At run time, the translation module translates a source language
sentence into a target language sentence.  The output of the run-time
system is a lattice of translation alternatives.  The alternatives
arise from syntactic ambiguity, lexical ambiguity, multiple synonymous
choices for lexical items in the dictionary, and multiple competing
hypotheses from the rule learner.

The runtime translation system incorporates the three main processes involved
in transfer-based MT: parsing of the SL input, transfer of the parsed
constituents of the SL to their corresponding structured constituents on the
TL side, and generation of the TL output.  All three of these processes are
performed based on the transfer grammar -- the comprehensive set of transfer
rules that are loaded into the runtime system.  In the first stage, parsing is
performed based solely on the ``x'' side of the transfer rules.  The
implemented parsing algorithm is for the most part a standard bottom-up Chart
Parser, such as described in \cite{Allen-book}.  A chart is populated with all
constituent structures that were created in the course of parsing the SL input
with the source-side portion of the transfer grammar.  Transfer and generation
are performed in an integrated second stage.  A dual TL chart is constructed
by applying transfer and generation operations on each and every constituent
entry in the SL parse chart.  The transfer rules associated with each entry in
the SL chart are used in order to determine the corresponding constituent
structure on the TL side.  At the word level, lexical transfer rules are
accessed in order to seed the individual lexical choices for the TL word-level
entries in the TL chart.  Finally, the set of generated TL output strings that
corresponds to the collection of all TL chart entries is collected into a TL
lattice, which is then passed on for decoding.  A more detailed description of
the runtime transfer-based translation sub-system can be found in
\cite{Peterson2002}.


\subsection{Target Language Decoding}
\label{decoding}

In the final stage, a statistical decoder is used in order to select a single
target language translation output from a lattice that represents the complete
set of translation units that were created for all substrings of the input
sentence.  The translation units in the lattice are organized according the
positional start and end indices of the input fragment to which they
correspond.  The lattice typically contains translation units of various sizes
for different contiguous fragments of input. These translation units often
overlap.  The lattice also includes multiple word-to-word (or word-to-phrase)
translations, reflecting the ambiguity in selection of individual word
translations.

The task of the statistical decoder is to select a linear sequence
of adjoining but non-overlapping translation units that maximizes
the probability of $p(e|f)$, where $f = f_1 ... f_J$ is the source
sentence and $e = e_1 ... e_I$ is the sequence of target language
words.  According to Bayes decision rule we have to search for
\begin{eqnarray}
\hat{e} = \argmax_e{p(e \vert f)} = \argmax_e{p(f \vert e)p(e)}
\quad .
\end{eqnarray}
The language model $p(e)$ describes how well-formed a target
language sentence $e$ is.  We use a standard trigram model:
\begin{eqnarray}
p(e) = \prod_1^I p(e_i \vert e_{i-2} e_{i-1} ) \quad .
\end{eqnarray}
The translation probability $p(f \vert e)$ for the entire target
sentence is the product of the translation probabilities of the
individual translation units.  We use the so-called ``IBM-1'' alignment
model \cite{BrownEtAl1993} to train a statistical lexicon.  Phrase-to-phrase
translation probabilities are then calculated using this lexicon:
\begin{eqnarray}
p(\tilde{f} \vert \tilde{e}) = \prod_j \sum_i p(f_j \vert e_i)
\quad ,
\end{eqnarray}
where the product runs over all words in the source phrase and sum
over all words in the target phrase. For any possible sequence $s$
of non-overlapping translation units which fully cover the source
sentence, the total translation model probability is then:
\begin{eqnarray}
p(f \vert e ) &=& \prod_s p(\tilde{f} \vert \tilde{e}) = \prod_s
\prod_j \sum_i p(f^s_j \vert e^s_i) \quad .
\end{eqnarray}

The search algorithm considers all possible sequences $s$ in the
lattice and calculates the product of the language model
probability and the translation model probability for the
resulting sequence of target words. It then selects the sequence which 
has the highest overall probability.

As part of the decoding search, the decoder can also perform a
limited amount of re-ordering of translation units in the lattice,
when such reordering results in a better fit to the target
language model.  Reordering is performed by skipping over several
words in the source sentence, i.e. leaving a gap, translating the
word or phrase further towards the end of the sentence, and
filling in the gap afterwards.  The word re-orderings are scored
using a Gaussian probability distribution, i.e. longer movements
are less likely than shorter ones, with mean zero and a variance
optimized on a development test set.  To keep decoding time
limited, we use a beam search, i.e. partial translation
hypotheses which are low scoring compared to the best scoring
hypothesis up to that point are pruned from further consideration.
%Details on the decoder are described in \cite{Vogel_NLP_KE_2003}.
%SMT Decoder Dissected: Word Reordering
%Stephan Vogel
%Proc. of NLP-KE, Beijing, China, Oct 2003.



%%%%%%%%%%%%%%%%%%%

\section{Elicited Data Collection}
\input{data-collection.tex}

%%%%%%%%%%%%%%%%%%%%

\section{Hindi-to-English Transfer MT System}
\label{hindi}

\subsection{Morphology and Grammars}
\input{morpho-gra}

\subsection{Lexical Resources}
\input{Lexicon}

\subsection{Runtime Configuration}
\input{TranslationStrategies}

%%%%%%%%%%%%%%%%%%

\section{The Limited Data Scenario Experiment}
\label{exp}

\subsection{Training and Testing Data}

In order to compare the effectiveness of the \xfer system with
data-driven MT approaches (SMT and EBMT) under a scenario of truly
limited data resources, we artificially crafted a collection of
training data for Hindi-to-English translation, that intentionally
contained extremely limited amounts of parallel text.  The training
data was extracted from the larger pool of resources that had been
collected throughout the SLE by our own group as well as the other
participating groups in the SLE.  The limited data consisted of the
following resources:

\begin{itemize}

\item {\bf Elicited Data Corpus:} 17,589 word-aligned phrases and
sentences from the elicited data collection described in
section~\ref{data}.  This includes both our translated and aligned
{\em controlled} elicitation corpus, and also the translated and
aligned {\em uncontrolled} corpus of noun phrases and prepositional
phrases extracted from the Penn Treebank.  

%% The training examples in Figures~\ref{ElicitationTrEx}
%% and~\ref{UncontrolledTrEx} show a few sample elicited phrases. 

\item {\bf Small Hindi-to-English Lexicon}: 23,612 ``clean''
translation pairs from the LDC dictionary (as described in
Section~\ref{Lexicon}). 

\item {\bf Small Amount of Manually Acquired Resources}:  (As
described in Section~\ref{Lexicon}) --- 500 most common Hindi
bigrams, 72 manually written phrase transfer rules, 105 manually
written postposition rules, and 48 manually written time expression
rules. 
\end{itemize}

The limited data setup includes no additional parallel Hindi-English
text.  The total amount of bilingual training data was estimated to
amount to about 50,000 words.

A small, previously unseen, Hindi text was selected as a test-set for this
experiment.  The test-set chosen was a section of the data collected at Johns
Hopkins University during the later stages of the SLE, using a web-based
interface \cite{JHU-data}.  The section chosen consists of 258 sentences, for
which four English reference translations are available.  An example test
sentence can be seen in Figure~\ref{TestEx}.

\begin{figure}
  \begin{center}
%    \includegraphics{TestEx.eps}
    \includegraphics[scale=.8]{TestEx.eps}
  \end{center}
  \caption{Example of a Test Sentence and Reference Translations}
  \label{TestEx}		
\end{figure}

\subsection{Experimental Testing Configuration}

The experiment was designed to evaluate and compare several different
configurations of the \xfer system, and the two corpus-based systems
(SMT and EBMT), all trained on the same limited-data resources, and
tested on the same test set.

The transfer engine was run in a setting that finds all possible
translations that are consistent with the transfer rules.  The
transfer engine produces a complete lattice of all possible partial
translations.  The lattice is then input into a statistical decoder.
Decoding is performed as described in Section~\ref{decoding}. We used
an English language model that was trained on 70 million English
words.  As an additional functionality, the decoder can perform a
limited reordering of arcs during decoding.  At any point in the
decoding, arcs that have a start position index of up to {\em four}
words ahead are considered, and allowed to be ``moved'' to the current
position in the output if this improves the overall score of the
resulting output string according to the English language model.

The following systems were evaluated in the experiment:

\begin{enumerate}
\item The following versions of the \xfer system:
\begin{enumerate}
\item {\bf \xfer with No Grammar:} \xfer with no syntactic transfer rules
(i.e. only phrase-to-phrase matches and word-to-word lexical transfer rules,
with and without morphology).
\item {\bf \xfer with Learned Grammar:} \xfer with automatically learned 
syntactic transfer rules, as described in section~\ref{AutomaticGrammar}.
\item {\bf \xfer with Manual Grammar:} \xfer with the manually developed 
syntactic transfer rules, as described in section~\ref{ManualGrammar}.
\end{enumerate}
\item {\bf SMT:} The CMU Statistical MT (SMT) system \cite{VogelEtAl2003}, 
trained on the limited-data parallel text resources.
\item {\bf EBMT:} The CMU Example-based MT (EBMT) system \cite{Brown1997}, 
trained on the limited-data parallel text resources.
\item {\bf MEMT:} A ``multi-engine'' version that combines the lattices
produced by the SMT system and the \xfer system with manual grammar.  The
decoder then selects an output from the joint lattice.
\end{enumerate}

\subsection{Experimental Results}

Performance of the systems was measured using the NIST scoring metric
\cite{Doddington2002}, as well as the {\sc Bleu} score
\cite{PapineniEtAl2002}.  In order to validate the statistical significance of
the differences in NIST and {\sc Bleu} scores, we applied a commonly used
sampling technique over the test set:  we randomly draw 258 sentences 
independently from the set of 258 test sentences (thus sentences can appear
zero, once, or more in the newly drawn set).  We then calculate scores for all
systems on the randomly drawn set (rather than the original set).  This
process was repeated 10,000 times.  Median scores and 95\% confidence
intervals were calculated based on the set of scores.

Table~\ref{ComparisonResults} compares the results of the different systems
(with the decoder's best reordering window), along with the 95\% confidence
intervals.  Figures~\ref{NISTResults} and~\ref{BleuResults} show the effect of
different systems with different reordering windows in the decoder.  For
clarity, confidence intervals are graphically shown only for the NIST scores
(not for {\sc Bleu}), and only for SMT, \xfer with no grammar, and MEMT.

\begin{table}
\begin{footnotesize}
\begin{center}
\begin{tabular}{|l|l|l|}\hline
\textbf{System} & \textbf{BLEU}	& \textbf{NIST} \\ \hline
EBMT & 0.058 & 4.22 \\ \hline
SMT & 0.102 (+/- 0.016) & 4.70 (+/- 0.20) \\ \hline
\xfer no grammar & 0.109 (+/- 0.015) & 5.29 (+/- 0.19) \\ \hline
\xfer learned grammar & 0.112 (+/- 0.016) & 5.32 (+/- 0.19) \\ \hline
\xfer manual grammar & 0.135 (+/- 0.018) & 5.59 (+/- 0.20) \\ \hline
MEMT (\xfer+SMT) & 0.136 (+/- 0.018) & 5.65 (+/- 0.21) \\ \hline
\end{tabular}
\caption{System Performance Results for the Various Translation Approaches}
\label{ComparisonResults}
\end{center}
\end{footnotesize}
\end{table}


\begin{figure}
  \begin{center}
    \includegraphics[scale=.5,angle=270]{NIST-chart-new.epsi}
%     \centerline{\psfig{file=./NIST-chart-new.epsi,width=16.5cm,angle=90}}
  \end{center}
  \caption{Results by NIST score}
  \label{NISTResults}
\end{figure}


\begin{figure}
  \begin{center}
    \includegraphics[scale=.5,angle=270]{BLEU-chart-new.epsi}
  \end{center}
  \caption{Results by BLEU score}
  \label{BleuResults}
\end{figure}


\subsection{Discussion of Results}

The results of the experiment clearly show that under the specific miserly data
training scenario that we constructed, the \xfer system, with all its
variants, significantly outperformed the SMT system.  While the scenario of
this experiment was clearly and intentionally more favorable towards our \xfer
approach, we see these results as a clear validation of the utility and
effectiveness of our transfer approach in other scenarios where only very
limited amounts of parallel text and other online resources are available.  In
earlier experiments during the SLE, we observed that SMT outperformed the
\xfer system when much larger amounts of parallel text data were used for
system training.  This indicates that there exists a data ``cross-over point''
between the performance of the two systems: given more and more data, SMT will
outperform the current \xfer system.  Part of future work will be to first
determine this cross-over point and then to attempt to push this point further
toward scenarios where more data is given, thus making the \xfer system
applicable to a wider variety of conditions.

The use of morphology within the \xfer system was also a significant factor in
the gap in performance between the \xfer system and the SMT system in the
experiment.  Token word coverage of the test-set without morphology is about
70\%, whereas with morphology, token coverage increases to around 79\%.
We acknowledge that the availablility of a high-coverage morphological
analyzer for Hindi worked to our favor, and a morphological analyzer of
such quality may not be available for many other languages.  Our \xfer
approach, however, can function even with partial morphological information, 
with some consequences on the effectiveness and generality of the rules
learned.

The results of the comparison between the various versions of the \xfer system
also show interesting trends, although the statistical significance of some of
the differences is not very high.  \xfer with the manually developed transfer
rule grammar clearly outperformed (with high statistical significance) \xfer
with no grammar and \xfer with automatically learned grammar.  \xfer with
automatically learned grammar is slightly better than \xfer with no grammar,
but the difference is statistically not very significant.  We take these
results to be highly encouraging, since both the manually written and
automatically learned grammars were very limited in this experiment.  The
automatically learned rules only covered NPs and PPs, whereas the manually
developed grammar mostly covers verb constructions.  While our main objective
is to infer rules that perform comparably to hand-written rules, it is
encouraging that the hand-written grammar rules result in a big performance
boost over the no-grammar system, indicating that there is much room for
improvement.  If the learning algorithms are improved, the performance of the
overall system can also be improved significantly.

The significant effects of decoder reordering are also quite interesting.  On
one hand, we believe this indicates that various more sophisticated rules
could be learned, and that such rules could better order the English output,
thus reducing the need for re-ordering by the decoder.  On the other hand, the
results indicate that some of the ``burden'' of reordering can remain within
the decoder, thus possibly compensating for weaknesses in rule learning.

Finally, we were pleased to see that the consistently best performing system
was our multi-engine configuration, where we combined the translation
hypotheses of the SMT and \xfer systems together into a common lattice and
applied the decoder to select a final translation.  The MEMT configuration
outperformed the best purely \xfer system with reasonable statistical
confidence.  Obtaining a multi-engine combination scheme that consistently
outperforms all the individual MT engines has been notoriously difficult in
past research.  While the results we obtained here are for a unique data
scenario, we hope that the framework applied here for multi-engine integration
will prove to be effective for a variety of other scenarios as well.  The
inherent differences between the \xfer and SMT approaches should hopefully
make them complementary in a broad range of data scenarios.


\section{Conclusions and Future Work}
\label{conc}

The DARPA-sponsored SLE allowed us to develop and test an open-domain
large-scale Hindi-to-English version of our \xfer system.  This experience was
extremely helpful for enhancing the basic capabilities of our system.  The
lattice-based decoding was added to our system at the very end of the
month-long SLE, and proved to be very effective in boosting the overall
performance of our \xfer system.

The experiments we conducted under the extremely limited Hindi data resources
scenario were very insightful.  The results of our experiments indicate that
our \xfer system in its current state outperforms SMT and EBMT when the amount
of available parallel training text is extremely small.  The \xfer system with
manually developed transfer-rules outperformed the version of the system with
automatically learned rules.  This is partly due to the fact that we only
attempted to learn rules for NPs and VPs in this experiment.  We see the
current results as an indication that there is significant room for improving
automatic rule learning.  In particular, the learning of unification
constraints in our current system requires significant further research.

In summary, we feel that we have made significant steps towards the
development of a statistically grounded transfer-based MT system with: (1)
rules that are scored based on a well-founded probability model; and (2)
strong and effective decoding that incorporates the most advanced techniques
used in SMT decoding.  Our work complements recent work by other groups on
improving translation performance by incorporating models of syntax into
traditional corpus-driven MT methods.  The focus of our approach, however, is
from the ``opposite end of the spectrum'': we enhance the performance of a
syntactically motivated rule-based approach to MT, using strong statistical
methods.  We find our approach particularly suitable for languages with very
limited data resources.


\section*{Acknowledgements}

This research was funded in part by the DARPA TIDES program and by NSF grant 
number IIS-0121-631.  We would like to thank our team of Hindi-English
bilingual speakers in Pittsburgh and in India that conducted the data 
collection for the research work reported in this paper.



\bibliographystyle{acmtrans}
\bibliography{xfer-paper}

%\begin{thebibliography}{acmtrans}
%\bibliography{xfer-paper}
%\end{thebibliography}

%\begin{received}

%\end{received}

\end{document}


