\documentclass{kluwer}    % Specifies the document style.
\usepackage[dvips]{graphicx}

\newdisplay{guess}{Conjecture}

\begin{document}                                                                                   
\begin{article}
\begin{opening}         
\title{Elicitation-Based Learning of Syntactic Transfer Rules for Machine Translation for Resource-Poor Languages}

\author{Katharina \surname{Probst}, Lori \surname{Levin}, Erik \surname{Peterson}, Alon \surname{Lavie}, Jaime \surname{Carbonell}}
\runningauthor{Katharina Probst et al.}
\runningtitle{Elicitation-Based MT}
\institute{Language Technologies Institute\\
Carnegie Mellon University\\
Pittsburgh, PA, U.S.A.}
\date{\today}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Please follow these conventions:
%% Use italics \it for words and sentences 
%% At the end of italics, use \/ (backslash frontslash) to leave extra
%% space to compensate for the slant of the italics so it doesn't bump
%% into the next character. {\it This is an example\/}.

%% Use teletype \tt for data objects in the text and in figures.  
%% Things like NP, x0, y0, x, y are data objects.
%% Not sure about xy-constraints, but I am inclined to use
%% {\tt xy}-constraints.

%% It will help ancient emacs users if you put two spaces after a
%% period.  That way we can use esc-a, esc-e, esc-k for go to
%% beginning of sentence, go to end of sentence, and kill sentence. 
%% But if you can't get used to using two spaces, that is ok.
%% (Anyone who learned to type on a typewriter uses two spaces after a
%% period.)

%% For referring to sections and figures.  Use a capital letter
%% because it is kind of like a proper name.  Use ~ so that there is
%% no line break before the section or figure number.  example: This
%% is discussed in Section~\ref{sectionlabel}.

%% Use {\sc Avenue} for the project name.  First letter will come out
%% full size capital, and the rest will come out in small caps.

%% Footnotes are almost never necessary.  If they are parenthetical
%% comments, you can put them in the main text in parentheses, or just
%% re-work the structure of your paragraph to fit the point in.  If
%% the footnote contains a large point, re-work the flow of the
%% argument to fit it in.  

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

\begin{abstract}
Elicitation-based Machine Translation is an approach to MT that can be
applied to language pairs where neither large bilingual corpora nor
other NLP resources are available.  In our approach, a bilingual
speaker translates and aligns a small elicitation corpus that serves
as training data for a rule learning system.  The elicitation corpus
is designed to cover major linguistic phenomena, so as to make the
training corpus as diverse as possible. We assume a resource-rich
elicitation language for which resources such
as a grammar and a parser are available.  The rule learning system
then uses the syntactic analysis of the sentence in the resource-rich
language, as well as any information given in the other language, to
infer syntactic {\it seed\/} transfer rules.  The seed rules
are generalized to increase their coverage of unseen
examples, using the bilingual elicitation corpus for validation.  
Rule generalization is accomplished by a learning mechanism, Seeded Version Space Learning, which similar in
nature to Version Space Learning. The approach bases on a partial ordering of transfer rules, which is defined in terms of their generality.  The seed rules provide an informed starting point, thus encouraging fast convergence.


\end{abstract}
\keywords{elicitation, learning, syntactic transfer rules, minority languages}

\end{opening}

\section{Introduction and Motivation}

In recent years, much of machine translation research has focused on
two issues: portability to new languages, and developing machine
translation systems rapidly.  Since human expertise on uncommon languages
may be in short supply, and human development time can be lengthy,
automated learning of statistics or rules has been critical to both
language portability and rapid development.  Automated methods have
typically been trained on large, uncontrolled parallel corpora
\cite{BrownEtAl1990, BrownEtAl1993, Brown1997, OchNey2002, YamadaKnight2001, PapineniEtAl1998, VogelTribble2002}.  However, a minority
of projects
\cite{Nirenburg1998,SherematyevaNirenburg2000,JonesHavrilla1998} have
addressed automated learning of translation rules from a controlled
corpus of carefully elicited sentences.

This article presents an elicitation-based approach to learning
transfer rules for machine translation.  The input to the rule
learning mechanism is a parallel corpus of elicitation sentences,
where each sentence pair is word-aligned (allowing multiple and zero
alignments).  The learning mechanism is a new technique called Seeded Version Space Learning (SVSL).  SVSL is based
on Version Space Learning \cite{Mitchell1982}, which involves
focusing in on a hypothesis in a space between specific and general
hypotheses.  In the case of translation rules, specific hypotheses are annotated with many feature constraints (such as `the subject of the sentence is in the singular'), so that they apply only to one or a few sentences.  More general hypotheses, on the other hand, generalize the feature constraints in an effort to make the rule applicable to a large set of sentences. For example, a more general constraint may be that the subject and main verb of a sentence agree in number, regardless of what the number is.  To make the approach more tractable, we use
seed rules as a starting point.  A seed rule is created automatically
from a bilingual word-aligned phrase or sentence and a lexicon.
Generalizations are hypothesized by comparing seed rules and are 
confirmed by checking the translations of the elicitation sentences.  

The work described here is part of the {\sc Avenue} project at
Carnegie Mellon University.\footnote{NSF grant number IIS-0121-631}  The overall
goal of {\sc Avenue} is to research methods for machine translation
that are suitable for languages with scarce electronic resources, and
possibly also a scarcity of humans trained in linguistic analysis.
{\sc Avenue} aims to develop ``omnivorous'' machine translation
techniques that can take advantage of whatever resources are
available.  This includes using large unconstrained corpora when they
are available and eliciting controlled corpora for training data.

This article is organized as follows: First, we present the transfer rule formalism and briefly the transfer engine.  Also, we describe and show the interface that is used for eliciting data.  We continue by discussing the general design of the elicitation corpus,  followed by an in-depth treatment of our rule learning algorithms, including preliminary evaluation results. Further, we discuss advantages and disadvantages of learning from a controlled, elicited corpus and list several challenges that we face in our work.  Finally, we mention several areas of future investigation and conclude.

\section{The Transfer Rule Formalism and Interpreter}\label{Formalism}

As was said above, our system uses a bilingual word-aligned corpus as training data. The output of the SVSL system is a set of unification-based syntactic transfer rules for machine translation.  This section describes the transfer
rule formalism and transfer rule engine.  Transfer engines typically
have separate rules for the three traditional stages of MT: analysis,
transfer, and generation.  The \textsc{Avenue}
rule formalism
combines the information for all three into a single rule.
The \textsc{Avenue} engine consequently is closer
to the `modified' transfer approach used in the early \textsc{Metal} system \cite{Hutchins1992}.

Like most modern translation sytems,
the \textsc{Avenue} transfer engine maintains a strict separation between the
transfer algorithms and linguistic data.  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.  

%% Questions: ARE ALIGNMENTS USED FOR LEXICAL LOOKUP AND/OR ARE ALIGNED ELEMENTS UNIFIED?
%% Answer: No, the alignments are not used for lexical lookup.  The lexical lookups
%%   are just from a TL dictionary (using the user's translation)
%%   They do play a role in what is unified: I unify only up to the maximal projection,
%%   and the constituents are defined by the c-structure on the SL side.  
%%   Note that the maximal projection unification approach is `conservative' in the sense
%%   that it won't unify everything that should (e.g. `the big man', adj won't be unified
%%   with n).  But this only results in some remaining ambiguities, and thus some more
%%   seed rules which are hopefully weeded out by the learning algorithm.  I prefer the
%%   conservative approach over another one that makes more assumptions about what should
%%   be unified in the TL.  Lori, if you have an idea that makes more sense from a 
%%   linguistic/typological point of view, please let me know.

\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 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}

For illustration purposes, Figure~\ref{rule1} shows an example of a
transfer rule for translating Chinese {\it yes/no\/}-questions into
English.  Chinese {\it yes/no\/}-questions use the same word order as
declarative sentences, but end in the particle {\it ma\/}.  The
transfer rule shown in  Figure~\ref{rule1} adds the auxiliary verb {\it
do\/}, makes it agree with the subject, and constrains the {\tt VP} to
be infinitive.  

\begin{figure}[t]
\renewcommand{\baselinestretch}{1} 
\footnotesize
\begin{verbatim}
{S,2}  ; Rule identifier
S::S : [NP VP MA] -> [AUX NP VP]
(
   (x1::y2) ; set constituent alignments
   (x2::y3)

   ; Build Chinese sentence f-structure
   ((x0 subj) = x1) ; NP supplies subj. f-structure
   ((x0 subj case) = nom)
   ((x0 act) = quest) ; speech act is question
   (x0 = x2)

   ((y1 form) = do) ; base form of AUX is "do"

   ((y3 vform) =c inf) ; verb must be infinitive
   ((y1 agr) = (y2 agr)) ; "do" must agree with subj.
)
\end{verbatim}
\caption{Sample Transfer Rule}
\label{rule1}
\end{figure}

\normalsize

In Figure~\ref{rule1}, the notation {\tt S::S} indicates that a
sentence (dominated by an {\tt S} node) on the source side translates
into another sentence in the TL.  The production rules (constituent
sequences) are {\tt[NP VP MA] -$>$ [AUX NP VP]}.  The remaining
portion of the transfer rule specifies alignments and constraints.
Following a basic unification-based approach, we assume that each
constituent structure node may have a corresponding feature structure.
The feature structure holds syntactic features (such as number,
person, and tense) so that they can be checked for agreement and other
constraints.  The feature structure may also specify the grammatical
relations that hold between the nodes.

The feature unification equations used in the rules follow the
formalism from the Generalized LR Parser/Compiler \cite{Tomita1988}.
The {\tt x} and {\tt y} variables used in the alignments and
constraints correspond to the feature structures of the elements of
the production rules.  {\tt x0} is the feature structure of the source
language parent node {\tt S}.  {\tt y0} is the feature structure of
the target language parent node {\tt S}.  The source constituents are
referred to with x followed by the constituent index, starting at one.
So {\tt NP} is referenced as {\tt x1}, {\tt VP} as {\tt x2}, and {\tt
MA} is referenced as {\tt x3}.  On the target side the production rule
order is {\tt AUX NP VP}, referred to with {\tt y1}, {\tt y2}, and {\tt
y3}, respectively.

The body of the rule begins with one or more constituent alignments
that describe which constituents on the source side should transfer to
which constituents on the target side.  Not all constituents need to
have an alignment to the other side.  A doub\-le-quote-en\-closed
string may also be used on the target side, directing the transfer
engine to always insert this exact word into the translation in
relative position to the rule's other target constituents.

The constituent alignments are followed by a set of feature
unification constraints, to be used in each of the analysis, transfer,
and generation stages.  Transfer unification equations are generally
divided into three types: {\tt x}-side constraints, which refer to
source language constituents and are used during analysis; {\tt
xy}-constraints, used during transfer to selectively move feature
structures from the source to the target language structures; and {\tt
y}-side constraints, used during generation to distribute target
language feature structures and to check agreement constraints between
target constituents.

In a further distinction, {\tt x}-side and {\tt y}-side constraints
can be either \textit{value constraints} or \textit{agreement
constraints}.  Value constraints are of the format
$(X_{n}\ attribute) = value))$ or $(Y_{n}\ attribute) = value))$, while agreement constraints are of the format $((X_{n}\ attribute) = (Y_{m}\ attribute))$.  Agreement constraints can also be between two x-incides (xx-constraints) or two y-indices (yy-constraints).
%$((\Phi_{i}\gamma_{m}\ \alpha_{j}) = \beta_{kj})$, while agreement
%constraints are of the format $((\Phi_{i}\gamma_{m}\ \alpha_{j}) =
%(\Phi_{i}\gamma_{n}\ \alpha_{j}))$, where
%\begin{footnotesize}
%\begin{itemize}
%\item $\Phi_{i} \in \{X,Y\}$
%\item $\gamma_{i} \in \Big\{\begin{array}{ll} 
%\{0 \dots number\ of\ SL\ words\} & if \Phi_{i} = X\\ 
%\{0 \dots number\ of\ TL\ words\} & if \Phi_{i} = Y\\
%\end{array}$
%\item $\alpha_{i} \in \{linguistic\ features\ such\ as\ number,\\definiteness,\ agreement,\ tense,\ \dots\},$
%\item $\beta_{ki} \in \{x|x\ is\ a\ valid\ value\ of\ feature\ \alpha_{i}\}$
%\end{itemize}
%\end{footnotesize}
An example of a value constraint is {\tt ((X2 AGR) = *3PLU)}, where an
agreement constraint example is {\tt ((X2 AGR) = (X3 AGR))}.  This
distinction is used during learning.  Initial seed hypotheses
contain value constraints, which are then generalized
to agreement constraints where possible.

Since the transfer rules are comprehensive (in the sense that they
incorporate parsing, transfer, and generation information all in the
rules), the set of rules that results from learning in effect represents a transfer grammar.  The transfer engine uses it exclusively to
translate, and no additional parsing and/or generation grammars are
available.  Hence, the transfer rules contain a myriad of information,
including feature information about its constituents.

In many systems, transfer rules contain merely the mapping, i.e.,
alignment, between the source and target language constituents.  This
is the obvious choice if an additional parsing and an additional
generation grammar are available.  Our system, however, learns the
parsing, transfer, and generation grammars at once, encoding all the
necessary information in each rule.  There are two main reasons for
this.  First, the rules are learned from bilingual sentence pairs, so
that it makes intuitive sense to build a transfer rule for each
sentence pair.  The second reason is the discrepancy between the
amount of information available on the source language and the target
language sides.  The less information is available in the TL, the more
assumptions are made, using the SL information. For instance, if no
number information is available for the TL, we assume that it is the
same as in the SL. Our transfer rules are thus specifically designed
for the circumstances as well as for the learning task at hand.

The fact that each transfer rule contains parsing, transfer, and
generation information should however not be confused with the way
translation is achieved. The transfer engine does indeed first parse
the sentence, then transfer and generation are achieved in an
integrated pass.  In other words, while each transfer rule contains
parsing, transfer, and generation constraints as if there was no
difference between them, the transfer engine keeps a strict
distinction between them \cite{Peterson2002}.

%ERIK'S SECTION
\input{mtetsection-Kathrin-011403}
%% Elicitation Interface
%END ERIK'S SECTION

\section{General Design of the Elicitation Corpus}

The elicitation corpus is a list of sentences in a major language like
English or Spanish.  It is designed to cover major linguistic
phenomena in typologically diverse languages.  In realizing that it is
a hard undertaking to be typologically complete, we start by eliciting
simple structures that are likely to be present in a wide
variety of languages, such as noun phrases and basic transitive and
intransitive sentences.  Currently, the source language is a major
language such as English or Spanish. The target language can in
principle be any language. 

The current pilot elicitation corpus has about 2,000 sentences (in
English, some of which have been translated into Spanish), though we
expect it to grow to at least the number of sentences in
\cite{BouquiauxThomas1992}, which includes around 6,000 to 10,000
sentences, and to ultimately cover most of the phenomena in the Comrie
and Smith \cite{ComrieSmith1977} checklist for descriptive grammars.
The phenomena covered in the pilot corpus include number, person, and
definiteness of noun phrases; case marking of subject and object;
agreement with subjects and objects; differences in sentence structure
due to animacy or definiteness of subjects and objects; possessive
noun phrases; and some basic verb subcategorization classes.

The elicitation corpus has two organizational properties: it is
organized into minimal pairs; and it is compositional, i.e. starting with smaller phrases and combining them into
larger phrases.  In the future, we also plan for it to be dynamic, so that the elicitation takes a
different path depending on what features have been found so far.

A minimal pair can be defined as two sentences that differ only in one
feature.  Each sentence can be associated with a feature vector.
Consider, for instance, the following three sentences:

\begin{it}
\begin{small}
\begin{tabbing}
1. The man saw the young girl.\\
2. The men saw the young girl.\\
3. The woman saw the young girl.
\end{tabbing}
\end{small}
\end{it}

The first and the second sentence differ merely in one feature, namely
the number of the subject.  Thus, they represent a minimal
pair. However, sentence one and three also form minimal pair.  They
differ only in the gender of the subject.

The reason that we decided to organize the corpus in minimal pairs is
specific to our use of the elicited data.  One component of the
transfer rule learning is feature detection. If we define linguistic
phenomena (such as number, gender, subject-verb agreement, etc.) as a
set of features, we want to determine what subset of these features is
instantiated in a given language.  This is achieved by defining the
features such that they can be tested using a minimal pair of
sentences.  For instance, if we want to find out whether target
language verbs inflect depending on the number of the subject, we can
use sentences 1 and 2 above: they differ only in the number of their subject, while all other features are kept
constant.  Determining whether the target language verbs agree in
number with their subjects is then reduced to comparing the verbs in
the elicited target language versions of sentences 1 and 2.

However, we have to careful to make the opposite conjecture.  If the
two verbs do not differ, then this could be an indication that target
language verbs do not agree with their subjects in number.  However,
it could also mean that the verb used for comparison represents an
exception to a more common rule.  We approach this problem in two
ways.  First, we never rule out the existence of a feature based on
only one example (i.e., one minimal pair).  Second, the results from
feature detection are interpreted not as absolutes, but as tendencies,
which guide our search through the space of possible transfer rules
and give more preference to those rules that use features that were
detected over those that use features that were not detected. Feature detection is not yet integrated with the rest of the learning module.  A detailed discussion is beyond the scope of this paper, but can be found in \cite{ProbstEtAl2001}.
The second design principle, compositional build-up, was chosen in order to aid the learning module.  The system first learns flat, unstructured rules.  Structure can be added by using previously learned rules for simpler constituents.  This principle will be discussed in detail below.

\section{The Rule Learning System}

In this section we introduce the rule learning system for learning
syntactic transfer rules from elicitation examples.  Commonly,
rule-based systems are developed by human experts writing grammar
rules that map structures from the source onto the target language.
Our goal is to automate this process.  The reader is reminded that in the current state of the system, the source language is the resource-rich language (such as English), whereas the
target language is the resource-poor language. We have begun
investigating the reversal of translation direction with some success.
The results will be reported in a future publication.

The system architecture (Figure~\ref{SystemArchitecture}) is divided
into a learning module and a run-time translation module.  The elicitation process, drawing from user input as well as the elicitation corpus, falls into the learning module.  The other major part of the learning module is the rule learner itself, using the output of the elicitation process as training data.  The rule learner interacts frequently with the transfer engine, as will become clearer in the discussion on how the rules are learned.  The output of the rule learner is a set of rules which during run-time serves as the transfer grammar.

At run time, the translation module translates a source language sentence into a target language sentence. This is achieved by the transfer engine using the output of the rule learning module, the learned transfer grammar. 



% Within the
%learning module, data is collected and rules are learned from the
%bilingual data.  The elicitation phase presents a bilingual user with
%a set of sentences (the elicitation corpus), who translates the corpus
%and aligns the words in each sentence pair (as described in
%Section~\ref{mtet}).  The rule learning system takes as input the
%elicited and hand-aligned data, and infers transfer rules. During the
%learning process, each proposed rule is immediately validated, meaning
%that the transfer engine, using the new rule, translates the bilingual
%example that the rule was derived from.  At the end of the learning
%process stands the learned transfer grammar, i.e. the set of rules
%that was derived from the training corpus.  At run-time (i.e. when
%translating unseen examples), the transfer engine uses this grammar to
%produce a TL sentences from SL input sentences. In
%Figure~\ref{SystemArchitecture}, this step is represented in the
%translation module.

\begin{figure}[htb]
  \begin{center}
   \includegraphics[scale=.6]{System.eps}
  \end{center}
  \caption{\textsc{Avenue}'s rule learning and translation system architecture}
  \label{SystemArchitecture}
\end{figure}

Figure~\ref{SystemArchitecture} further shows two optional sources of
information.  During the learning phase, the rule learning system can
also use an uncontrolled corpus.  Further, the learned transfer
grammar can at any point be supplemented by human-written rules.

%% \subsection{Learning With Elicited Data}

Learning from elicited data proceeds in three main stages: the first
phase, Seed Generation, produces initial `guesses' at transfer rules.
The rules that result from Seed Generation are `flat'---they transfer
part of speech sequences.  This is clearly not desirable for syntactic
transfer rules.  For this purpose, the second phase, Compositionality
Learning, adds structure using previously learned rules.  For
instance, in order to learn a rule for a PP, it is useful to recognize
the NP that is contained in it, and to reuse NP rules that were
learned previously.  The third stage of learning, Seeded Version Space
Learning, adjusts the generality of the rules.  In particular, the
rules that are learned during Seed Generation and structuralized
during Compositionality Learning are very specific to the sentence
pair that they were derived from.  In order to make the rules
applicable to a wider variety of unseen examples at run-time, Seeded
Version Space Learning makes the rules more general.  The following
sections will explain all three stages in detail.

\subsection{Seed Generation}\label{SeedGeneration}

The first part of the automated learning process is seed generation,
i.e., the production of preliminary transfer rules that will be
refined during Seeded Version Space Learning.  The seed generation
algorithm takes as input a pair of parallel, word-aligned sentences.
The SL sentences are parsed and disambiguated in advance, so that the
system has access to a correct feature structure (f-structure) and a
correct phrase or constituent (c-)structure for each sentence.  

The seed generation algorithm can proceed in different settings
depending on how much information is available about the target
language.  In one extreme case, we assume that we have a fully
inflected target language dictionary, complete with feature-value
annotations. The other extreme is the absence of any information, in
which case the system makes assumptions about what linguistic
feature values can be assumed to transfer into the target language.
In such a case we assume, for example, that a plural noun will be
translated as a plural noun.  

%% We haven't mentioned feature detection yet. 
%% One field of future work is the explicit incorporation of the
%% information gathered during feature detection, so that more educated
%% guesses can be made.

%% Answer: It's mentioned below.  Should it be moved up?


With the information available, how can we construct a transfer rule
of the format described in Section~\ref{Formalism}?  All of the x-side
information can be gathered directly from the English f- and
c-structures.  This includes part of speech information, x-side
constraints, and type information, while the word alignment is given
directly by the user.  However, the system also needs to construct
constraints for the target language, the y-side.  By default, the
target language part of speech sequence is determined by assuming that
English words transfer into words of the same part of speech on the
target side. If more information is available about the target
language, e.g. a dictionary with part of speech information, this
information overrides the assumption that parts of speech transfer
directly.

%% Check the Bantu-Japanese example. 

For y-side constraints, we make a similar assumption as with parts of
speech: in absence of any information, we assume that linguistic
features and their values transfer from SL words to the corresponding
TL words.  However, we are more selective about this type of
projection.  Some features, like gender (e.g., masculine, feminine,
neuter) and noun class (e.g., Bantu nominal classifiers or Japanese
numerical classifiers), will not generally have the same values in
different languages.  The Japanese classification of a window as a
sheet, like paper, will not be relevant to a Bantu language that
classifies it as a manmade artifact, or to French, which classifies it
as feminine.  Other features may tend to have the same values across
languages.  For example, if a language has plural nouns in common
usage, it will probably use one in the translation of {\it The
children were playing\/}, because using a singular noun ({\it
child\/}) would change the meaning.  The decision of which features to
transfer is necessarily based on heuristics that are less than
perfect.  For example, we will transfer past tense for a sentence like
{\it The rock fell\/} because it is part of the meaning, even though
we are aware that tense systems vary widely and that English past
tense will not always correspond to past tense in another language. 

If an inflected TL dictionary is available, the y-side constraints are
determined by extracting all the information about the given TL words
from the dictionary, and disambiguating and unfying if TL words have
more than one entry in the target language dictionary.  For example,
the definite article {\it der\/} in German can be either masculine
nominative or else feminine dative, so that the appropriate entry can
only be determined by considering the other words in the sentence. 

Lastly, no xy-constraints are constructed during seed generation. This
arises from the fact that the seed rules are quite specific to the
sentence pair that they are produced from.  In some cases, a y-side
constraint could equivalently also be expressed as an xy-constraint.
The difference does, however, become apparent during Seeded Version
Space Learning.  From a procedural point of view, y-side constraints
are more specific than the equivalent xy-constraints.  For instance, the constraints {\tt ((x1 num)
= pl) and ((y2 num) = pl)} are, on the surface, equivalent to {\tt
((x1 num) = pl) ((y2 num) = (x1 num))}.  There is, however, a
difference: in the first case, changing {\tt ((x1 num) = pl))} to {\tt ((x1 num) = (*OR* sg pl))} does not have any impact on the value of {\tt y2}'s number, but
in the second case it does.  As Seeded Version Space Learning
manipulates constraints in such a fashion, there is actually a
difference between the two forms.  As the goal is to start Seeded
Version Space Learning at a specific level, we produce
y-side constraints rather than xy-constraints. An example of a seed rule
can be found in the left-most column in Table~\ref{SampleCompositionality}.

After a seed rule is produced, it is added to a tentative translation grammar.  Using this rule, the transfer engine then tries to translate the bilingual sentence pair that the rule was derived from.  Only if the rule can be used to translate the pair correctly (if the rule \textit{covers\/} the sentence pair) is the rule acceptable and is passed on to further learning steps.  

%% Should we include a little more of an algorithm for seed
%% generation? 

%% Answer: Could include a bit about unifying up to maximal projection. Let me know. -> final version.

\subsection{Compositionality}

In order to scale to more complex examples, the system learns
compositional rules: when producing a rule e.g. for a sentence, we can
make use of sub-constituent transfer rules already learned.

Compositional rules are learned by first producing a flat rule in Seed
Generation.  Then the system traverses the c-structure parse of the SL
sentence.  Each node in the parse is annotated with a label such as
{\tt NP}, which is the root of a subtree.  The system then checks if
it has learned a lower-level transfer rule that can be used to
correctly translate the words in the source language subtree.

The left-most column in Table~\ref{SampleCompositionality} contains the flat seed rule for the bilingual sentence pair \textit{The highly qualified applicant did not accept the offer.---Der \"au{\ss}erst qualifizierte Bewerber nahm das Angebot nicht an.}.  In order to add structure to the flat rule, the system performs a top-down traversal of the c-structure tree.  For each node, such as {\tt S}, {\tt NP}, {\tt
NBAR}, etc., it extracts the part of the sentence that is rooted at this
node.  For example, in the following part of a c-structure tree, the top node {\tt NP} covers the chunk {\it the highly qualified applicant\/}.  

\begin{footnotesize}
\begin{quote}
($<$NP$>$ ($<$DET$>$ ((ROOT $*$THE)) THE)\\
($<$NBAR$>$\\
($<$ADJP$>$ ($<$ADVP$>$ ($<$ADV$>$ ((ROOT *HIGHLY)) HIGHLY))\\
($<$ADJP$>$ ($<$ADJ$>$ ((ROOT *QUALIFIED)) QUALIFIED)))\\
($<$NBAR$>$ ($<$N$>$ ((ROOT *APPLICANT)) APPLICANT))))\\
\end{quote}
\end{footnotesize}

The question is now if there already exists a learned
transfer rule that can correctly translate this chunk.  Before this can be determined, the system first needs to 

\begin{enumerate}
\item find the TL reference translation that corresponds to the SL chunk. For this information, the system consults the user-specified alignments and the given target language translation.
\item find the category of the rule. This is obtained simply from the label of the top node of the sentence chunk.  In this example, the category would be {\tt NP\/}.  Compositionality is only added to the rule if a previously learned rule \textit{of the desired type}, (here {\tt NP\/}) can account for the bilingual chunk.  This is done in order to preserve the integrity of the original c-structure.
\end{enumerate}

The next step is to call the transfer engine to translate the chunk
{\it the highly qualified applicant\/}.  The transfer engine returns zero or more
translations together with the f-structures that are associated with
each translation.  The f-structures are stored as constraints of the same format as the y-side constraints in the transfer rules.  In case there exists a transfer rule that can
translate the sentence chunk in question, the system takes note of
this and traverses the rest of the c-structure, excluding the subtree that corresponds to the chunk.
The goal of traversing the c-structure is to find the \textit{maximal\/} subtrees that can be translated by lower-level rules, hence the top-down traversal.  

After traversal is completed and one or more compositional sub-constituents have been found, the initial flat seed
rule must be revised.  Table~\ref{SampleCompositionality} presents an example of how the flat rule
is modified to reflect the existence of an {\tt NP} rule that can
translate the chunk {\it the highly qualified applicant\/}.  The flat transfer rule (left-most column) and the lower-level rule (middle column) are combined to form the structured rule that can be seen in the right-most column.  Several adjustments are made to the flat seed rule:
 First, the part-of-speech
sequence from the flat rule is turned into a constituent sequence on
both the SL and the TL sides, where those chunks that are translatable
by lower-level rules are represented by the category information of
the lower-level rule, in this case {\tt NP}.  The alignments are
adjusted to the new sequences.  Lastly, the constraints must be
changed. The x-side constraints are mostly retained (with the indices
adjusted to the new sequences). However, those constraints that
pertain to the sentence/phrase part that is accounted for by the
lower-level rule are eliminated, as can be seen in Table~\ref{SampleCompositionality}. Note that for the rules in the two rightmost colums no specific sentences can be given since the rules are compositional and thus must have been learned from a combination of at least two training examples.

\begin{table*}[!ht]
\begin{tabular}{|l|l|l|}\hline
\textbf{Uncompositional rule} & \textbf{Lower-level Rule} & \textbf{Compositional Rule} \\ \hline
;;SL: {\it The highly qualified applicant\/} & &\\ 
 {\it did not accept the offer.\/} & & \\ % ;;SL: the very tall woman & ;;SL: the very tall woman \\
;;TL: {\it Der \"au{\ss}erst qualifizierte\/} & & \\
\it{Bewerber nahm das Angebot nicht an.\/} & & \\ %;;TL: die sehr grosse Frau & ;;TL: die sehr grosse Frau \\

S::S & NP::NP & S::S \\
$[$det adv adj n aux neg v det n$]$ & $[$det ADJP n$]$  & $[$NP aux neg v det n$]$ \\
$[$det adv adj n v det n neg vpart$]$ & $[$det ADJP n$]$ & $[$NP v det n neg vpart$]$ \\
(;;alignments: & ;;alignments:  & ;;alignments: \\
(x1:y1) & (x1::y1) & (x1::y1) \\
(x2::y2) & (x2::y2) & (x3::y5) \\
(x3::y3) & (x3::y3) & (x4::y2) \\
(x4::y4) & (x4::y4) & (x4::y6) \\
(x6::y8) & & (x5::y3) \\
(x7::y5) & & (x6::y4) \\
(x7::y9) & & \\
(x8::y6) & & \\
(x9::y7) & & \\
;;x-side constraints: & ;;x-side constraints: & ;;x-side constraints: \\
((x1 def) = *+) &  ((x3 agr = *3-sing)) & ((x2 tense) = *past)\\
((x4 agr) = *3-sing) & & \\
((x5 tense) = *past) & & \\
;;y-side constraints: & ;;y-side constraints: & ;;y-side constraints: \\
((y1 def) = *+) & ((y3 agr) = *3-sing) & ((y1 def) = *+) \\
((y3 case) = *nom) & & ((y1 case) = *nom)) \\
((y4 agr) = *3-sing)) & & \\ \hline 
\end{tabular}
\caption{Example of Compositionality}
\label{SampleCompositionality}
\end{table*}

Finally, the y-side constraints are adjusted.  For each new
sub-constituent that was detected, the transfer engine may return
multiple translations, some of which are correct and some of which are
wrong.  The compositionality module compares the f-structures (constraints) of the correct translation and the incorrect translations.  This is done so
as to determine what constraints need to be added to the higher level
rule in order to produce the correct translation in context. 
For each constraint in the correct translation, the system checks if
this constraint appears in \textit{all} other translations.  If this
is not the case, a new constraint is constructed and inserted into the
compositional rule. Before simply inserting the constraint, however,
the indices need to be adjusted to the higher-level constituent
sequence.

\subsection{Seeded Version Space Learning}

Seeded Version Space Learning follows the construction of
compositional rules.  The learning goal is to transform the set of
seed rules into more general transfer rules.  This transformation is
done by merging rules, which in effect represents a generalization.
Each rule is associated with a set of training sentences that it
`covers', i.e. is able to translate correctly.  This is called the
CSet of a rule.  After seed generation, each transfer rule's CSet
contains exactly one element, namely the index of the sentence that it
was produced from. When two rules are merged into one, their CSets are
also merged.

The algorithm can be divided into two steps: the first step groups
sets of similar seed rules, where each group effectively defines a
separate version space.  The second step is then run on each version
space separately.  It involves exploring the search space that is
delimited by a set of rules.

\subsubsection{Grouping Similar Rules}

In order to minimize the search space, the learning algorithm should
only merge two rules if there is a chance that the resulting rule will
correctly cover the CSets of both unmerged rules.  We group together
rules that have the same 1) type information, 2) constituent
sequences, and 3) alignments.  The rules in a group may have different
feature constraints, for example some may have singular nouns and some
may have plural nouns.  Merges are only attempted within a group, thus
simplifying the merging process.

From a theoretical standpoint, each such group of rules effectively
defines a version space.  Each version space has a boundary of
specificness (the specific boundary) marked by the seed rules, and a
boundary of generality (the general boundary), marked by a virtual
rule with the same part of speech sequences, alignments, and type
information as the other rules in the group, but no constraints.
The goal of version space learning is to pinpoint the right level of
generality between the specific boundary and the general boundary.  

\subsubsection{Exploring the search space}\label{Exploring}

%% *****
%% It would be good to state some of this in terms of a subsumption
%% hierarchy of feature structures, since that is something that some
%% people are familiar with. 

%% Answer: I'm not. :) Please explain.  Maybe I do know it.

Our Seeded Version Space Learning algorithm is based loosely on~\cite{Mitchell1982}.  We view the space of transfer rules as organized
in a partial ordering, where some rules are strictly more general than
others, but not all rules can be compared directly.  The partial order is defined almost identically to the definition of subsumption in formalisms such as HPSG \cite{Shieber1986}. The goal of the
Seeded Version Space Learning is to adjust the generality of rules.
If the process is successful, the resulting rules should be much like
those a human grammar-writer would design.

At the moment, we view the rules that the seed generation algorithm
produced as the most specific possible rules.  However, the seed rules
already present a generalization over sentences, generalizing to the
part of speech or constituent level.  It can happen that words that
are of the same part of speech behave differently.  For instance, some
French adjectives appear before, others after the noun they modify.
In these cases, the algorithm will have to explore the space `below'
the seed rules.  The issue is left for future investigation.

The major goal of the seeded version space algorithm is then to
generalize over specific feature values if this is possible. Consider
the following examples:

\begin{small}
\begin{tabular}{ll} 
\textit{Transfer Rule 1:} & \textit{Transfer Rule 2:} \\ 
$\dots$ & $\dots$\\
$((X1\ AGR) = *3SING)$ & $((X1\ AGR) = *3SING)$\\
$((X2\ DEF) = *DEF)$ & \\
$\dots$ & $\dots$\\ 
\end{tabular}
\end{small}

Here, the second tranfer rule is more general than the first, as the
first has more restrictive constraints.  We shall now formalize the
notion of partial ordering of transfer rules in our framework.

%% ***This has to be related to partial ordering of f-structures in a
%% subsumption hierarchy as in HPSG, unless it's not the same ... but I
%% think it is the same.

%% Answer: As insinuated above, I can't help you with that other than discussing exactly what
%% the partial order means here.

\begin{footnotesize}
\begin{quote}
\textbf{Definition:} A transfer rule $tr_{1}$ is strictly more general
than another transfer rule $tr_{2}$ if all f-structures that are
satisfied by $tr_{2}$ are also satisfied by $tr_{1}$.  The two rules 
are equivalent if and only if all f-structures that are satisfied by 
$tr_{1}$ are also satisfied by $tr_{2}$.
\end{quote}
\end{footnotesize}

Based on this definition, we can define operations that will turn a
transfer rule $tr_{1}$ into a strictly more general transfer rule
$tr_{2}$. More precisely, we have defined three operations:

\begin{footnotesize}
\begin{enumerate}
\item Deletion of value constraint\\
$(X_{n}\ attribute) = value))$ or $(Y_{n}\ attribute) = value))$
$\to$
$NULL$
\item Deletion of agreement constraint\\
$((X_{n}\ attribute) = (Y_{m}\ attribute))$
$\to$
$NULL$
(similarly for an xx-agreement constraint or a yy-agreement constraint.)
\item Merging of two value constraints into one agreement constraint.  Two value constraints can be merged if they are of the following format:
$(X_{n}\ attribute) = value1))$
$(X_{m}\ attribute) = value2))$
$((X_{n}\ attribute) = (X_{m}\ attribute))$
(similarly for an x- and a y-constraint or two y constraints.)
For example, the two value constraints ((X1 AGR) = *3PLU) and ((X2 AGR) = *3PLU) can be generalized to an agreement constraint of the form ((X1 AGR) = (X2 AGR)).
\end{enumerate}
\end{footnotesize}

\subsubsection{Merging Two Transfer Rules}\label{Merging}

At the heart of the learning algorithm is the merging of two
rules. Generalization is achieved by merging, which in turn is done
based on the three generalization operations defined above.
Suppose we wish to merge two rules $tr_{1}$ and $tr_{2}$ to produce
the most specific generalization of the two, stored in $tr_{3}$.  The
algorithm proceeds in three steps:

\begin{footnotesize}
\begin{enumerate}
\item Insert all constraints that appear in both $tr_{1}$ and $tr_{2}$
into $tr_{3}$ and subsequently eliminate them from $tr_{1}$ and $tr_{2}$.
\item Consider $tr_{1}$ and $tr_{2}$ separately.  Perform all
instances of operation 3 (see Section~\ref{Exploring} above) that are possible. 
\item Repeat step 1.
\end{enumerate}
\end{footnotesize}

After performing the merge, the system uses the new transfer rule,
$tr_{3}$ to translate the CSets of $tr_{1}$ and $tr_{2}$.  The merged
rule, $tr_{3}$, is accepted if it can correctly tranlate all of the
items in both CSets.  In the example in Table~\ref{SampleVS}, the
system can verify that this is the case.\footnote{Note that in the example, the source and target language sentences are not given with the rule in the middle column.  The reason again is that the rules are compositional, so that they must have been learned from at least two training examples. However, the example is given in reference to the previous example, where are rule was learned from {\it The highly qualified applicant did not accept the offer\/}, which translates into {\it Der \"au{\ss}erst qualifizierte Bewerber nahm das Angebot nicht an.\/}.} 
Given the way the partial order is defined, this sequence of steps
ensures that $tr_{3}$ does not have any constraints that would violate
this partial order, and that it lacks no constraints.  To return
to the example in Table~\ref{SampleVS}, the result of a merging
operation can be seen. The first two columns contain the unmerged
rules, the last column the merged rule.

\subsubsection{The learning algorithm and evaluation of merged rules}

The ultimate goal of the learning algorithm is to maximize coverage of
a rule set with respect to the language pair, meaning that a rule set
can correctly translate as many unseen sentences as possible.
Currently, we estimate the coverage of a rule set by the generality of
the rules.  Since merges always provide a generalization of the two
unmerged rules, we assume that they will increase coverage with
respect to the language pair.  Therefore, the learning algorithm seeks
to minimize the size of the rule set. It iteratively merges two rules,
until no more acceptable merges can be found and the rule set is as
general as possible.  Note again that a merge is only acceptable if
there is no loss in coverage over the more specific rules, and if it
produces no incorrect translations.  When no more merges are found,
the final rule set is output.  Cross-validation as an alternative
evaluation metric is currently under investigation.

\begin{table*}[!ht]
\begin{tabular}{|l|l|l|}\hline
\textbf{Seed Rule 1} & \textbf{Seed Rule 2} & \textbf{Generalized Rule} \\ \hline
S::S  & S::S &  S::S \\
$[$NP aux neg v det n$]$ $\rightarrow$ &  $[$NP aux neg v det n$]$ $\rightarrow$ & $[$NP aux neg v det n$]$ $\rightarrow$ \\
$[$NP v det n neg vpart$]$ &  $[$NP v det n neg vpart$]$ & $[$NP n det n neg vpart$]$ \\
(;;alignments: & (;;alignments: & (;;alignments: \\
(x1::y1) & (x1::y1) & (x1::y1) \\
(x3::y5) & (x3::y5) & (x3::y5) \\
(x4::y2) & (x4::y2) & (x4::y2) \\
(x4::y6) & (x4::y6) & (x4::y6) \\
(x5::y3) & (x5::y3) & (x5::y3) \\
(x6::y4) & (x6::y4) & (x6::y4) \\
;;constraints: & ;;constraints: & ;;constraints: \\
((x2 tense) = *past) 
\dots & \dots & \dots \\
((x2 tense) = *past) & ((x2 tense) = *past) & ((x2 tense) = *past)\\
((y1 def) = *+) & ((y1 def) = *+) & ((y1 def) = *+) \\
 ((y1 case) = *nom) & ((y1 case) = *nom) & ((y1 case) = *nom) \\
\dots & \dots & \dots \\
((y4 agr) = *3-sing)) &  ((y4 agr) = *3-plu)) & ((y4 agr) = (y3 agr))) \\ \hline
\end{tabular}
\caption{Example of Version Space Generalization}
\label{SampleVS}
\end{table*}

%preliminary experimental results
\input{Experiment.tex}
%end preliminary experimental results


%discussion on controlled vs. uncontrolled corpus and elicitation
\input{ControlledDiscussion}
%end discussion on controlled vs. uncontrolled corpus and elicitation

%% Challenges of elicitation based MT
\input{challenges}

\section{Conclusions and Future Work}

We have presented a novel approach to learning syntactic transfer
rules for machine translation.  We emphasize again that the learning
algorithms are not designed to work exclusively for structured data.
However, learning is facilitated in a variety of ways when the
translated and aligned elicitation corpus is available, for example
because we can create relatively noise-free data on the resource-rich
language side.

Our long-term plan is to expand the existing elicitation corpus to
have reasonable coverage of linguistic phenomena that occur across
languages and language families.  In practice, we first have to focus
on the more common features, so that the informant's time is used as
efficiently as possible and a preliminary rough translation can be
produced.

The elicitation corpus as well as the learning system are
continually being expanded to handle more structures and more
structurally complex sentences. As the elicitation corpus and the
leearning algorithms are developed in conjunction, scaling them up is
also achieved in parallel.

\acknowledgements
The authors would like to thank Ralf Brown, Ariadna Font Llitj\'os, and Christian Monson for their support and their useful comments.

%\section{References in the THEBIBLIOGRAPHY Environment}
%The first reference in the list below has the key \{BrownAndBurton\}.
%Together with the bibitem option $\backslash$citeauthoryear\{Brown and
%Burton\}\{1978\} the follwing cross-references can be used:\\
%$\backslash$cite\{BrownAndBurton\} produces: \cite{BrownAndBurton}\\
%$\backslash$shortcite\{BrownAndBurton\}  produces: \shortcite{BrownAndBurton}\\  
%$\backslash$citeauthor\{BrownAndBurton\}  produces: \citeauthor{BrownAndBurton}\\  
%$\backslash$citeyear\{BrownAndBurton\}  produces: \citeyear{BrownAndBurton}\\  


%\appendix

%In the appendix, we can give additional examples of transfer rules and/or sentences from the elicitation corpus.


%\acknowledgements
%Thanks to everybody on the project -- also grant acknowledgement?

% The endnotes section will be placed here.
%\theendnotes

\begin{thebibliography}{}

\bibitem[\protect\citeauthoryear{Bouquiaux and Thomas}{1992}]{BouquiauxThomas1992}
Bouquiaux, Luc and Thomas, Jacqueline M.C.
\newblock{Studying and Describing Unwritten Languages.}
\newblock The {S}ummer {I}nstitute of {L}inguistics, Dallas, TX, 1992.

\bibitem[\protect\citeauthoryear{Brown et al.}{1990}]{BrownEtAl1990}
Brown, Peter and Cocke, John and Della Pietra, Vincent J. and Della Pietra, Stehen A. and Jelinek, Fredrick and Lafferty, John and Mercer, Robert L. and Roossin, Paul S.
\newblock{A statistical approach to {M}achine {T}ranslation.}
\newblock{In: Computational Linguistics, Vol. 16, No. 2, pages 79--85, 1990}

\bibitem[\protect\citeauthoryear{Brown et al.}{1993}]{BrownEtAl1993}
Brown, Peter and Della Pietra, Stephen A. and Della Pietra, Vincent J., and Mercer, Robert L.
\newblock{The mathematics of statistical {M}achine {T}ranslation: Parameter estimation}
\newblock{In: Computational Linguistics, Vol. 19, No. 2, pages 263--311, 1993}

\bibitem[\protect\citeauthoryear{Brown}{1997}]{Brown1997}
Brown, Ralf.
\newblock{Automated Dictionary Extraction for `Knowledge-Free' Example-Based Translation}
\newblock{In: Proceedings of the 7th International Conference on Theoretical and Methodological Issues in Machine Translation (TMI-97), 1997}.

\bibitem[\protect\citeauthoryear{Calendino}{2001}]{Calendino2001}
Calendino, P. Francisco.
\newblock{Selecci\'on de verbos mapuches. Estructura general del verbo mapuche.}
\newblock Instituto Superior Juan XXIII, Bah\'ia Blanca, Argentina, 2001.

\bibitem[\protect\citeauthoryear{Carbonell et al.}{2002}]{CarbonellEtAl2002}
Carbonell, Jaime and Probst, Katharina and Peterson, Erik and Monson, Christian and Lavie, Alon and Brown, Ralf and Levin, Lori
\newblock{Automatic Rule Learning for Resource-Limited MT.}
\newblock In: Proceedings of the 5th Biennial Conference of the Association for Machine Translation in the Americas (AMTA-02), 2002.

\bibitem[\protect\citeauthoryear{Comrie}{1981}]{Comrie1981}
Comrie, Bernard.
\newblock{Language Universals \& Linguistic Typology.}
\newblock The University Chicago Press, Chigaco, IL, 1981, 2nd edition.

\bibitem[\protect\citeauthoryear{Comrie and Smith}{1977}]{ComrieSmith1977}
Comrie, Bernard and Smith, Noah.
\newblock{Lingua Descriptive Series: Questionnaire.}
\newblock In: Lingua, 42, pages 1--72, 1977.

\bibitem[\protect\citeauthoryear{Dorr}{1992}]{Dorr1992}
Dorr, Bonnie.
\newblock{{M}achine {T}ranslation: A View from the Lexicon.}
\newblock Cambridge, MA: MIT Press, 1992.

\bibitem[\protect\citeauthoryear{Eskenazi}{1999}]{Eskenazi1999}
Eskenazi, Maxine.
\newblock{Using Automatic Speech Processing For Foreign Language Pronunciation Tutoring: Some Issues and a Prototype.}
\newblock In: Language Learning \& Technology, Vol. 2, No. 2, pages 62--69, 1999.

\bibitem[\protect\citeauthoryear{Gaussier}{1999}]{Gaussier1999}
Gaussier, Eric.
\newblock{Unsupervised Learning of Derivational Morphology from Inflectional Lexicons.}
\newblock In: Proceedings of the Workshop on Unsupervised Learning in Natural Language Processing at the 37th Annual Meeting of the Assosication for Computational Linguistics (ACL-99), 1999.

\bibitem[\protect\citeauthoryear{Goldsmith}{2001}]{Goldsmith2001}
Goldsmith, John.
\newblock{Unsupervised Learning of the Morphology of a Natural Language.}
\newblock In: Computational Linguistics, Vol. 27, Np. 2, pages 153--198, 2001.

\bibitem[\protect\citeauthoryear{Greenberg}{1966}]{Greenberg1966}
Joseph H. Greenberg.
\newblock{Universals of language}
\newblock Cambridge, MA: MIT Press, 1966, 2nd edition.

\bibitem[\protect\citeauthoryear{Han}{2001}]{Han2001} 
Han, Benjamin and Lavie, Alon
\newblock{UKernel: A Unification Kernel.}
\newblock Available at http://www-2.cs.cmu.edu/\~~benhdj/c\_n\_s.html.
\newblock{2001.}

\bibitem[\protect\citeauthoryear{Hutchins}{1992}]{Hutchins1992} 
Hutchins, W. John and Somers, Harold L.  
\newblock {\em An Introduction to Machine Translation.}
\newblock Academic Press, London. 1992.

\bibitem[\protect\citeauthoryear{Jones and Havrilla}{1998}]{JonesHavrilla1998}
Jones, Douglas and Havrilla, R.
\newblock{Twisted Pair Grammar: Support for Rapid Development of Machine Translation for Low Density Languages.}
\newblock In: Proceedings of the Third Conference of the Association for Machine Translation in the Americas (AMTA-98), 1998.

\bibitem[\protect\citeauthoryear{Levin et al.}{1998}]{LevinEtAl1998}
Levin, Lori and Gates, Donna and Lavie, Alon and Waibel, Alex.
\newblock{An Interlingua Based on Domain Actions for Machine Translation of Task-Oriented Dialogues.}
\newblock In: Proceedings of the 5th International Conference on Spoken Language Processing (ICSLP-98), Vol. 4, pages 1155--1158, 1998.

\bibitem[\protect\citeauthoryear{Levin et al.}{2002}]{LevinEtAl2002}
Levin, Lori and Vega, Rodolfo and Carbonell, Jaime and Brown, Ralf and Lavie, Alon and Ca\~nulef, Eliseo and Huenchullan, Carolina.
\newblock{Data Collection and Language Technologies for Mapudungun.}
\newblock In: Proceedings of the Third International Conferences on Language Resources and Evaluation (LREC-02), 2002.

\bibitem[\protect\citeauthoryear{Melamed}{1998}]{Melamed1998}
Melamed, Dan I.
\newblock{Manual Annotation of Translational Equivalence: The {B}linker Project.}
\newblock IRCS Technical Report, Num. 98-07, 1998.

\bibitem[\protect\citeauthoryear{Mitchell}{1982}]{Mitchell1982}
Mitchell, Tom.
\newblock{Generalization as Search}
\newblock In: {\em Artificial Intelligence}, Vol. 18, pages 203--226, 1982.

\bibitem[\protect\citeauthoryear{Nirenburg}{1998}]{Nirenburg1998}
Nirenburg, Sergei.
\newblock{Project Boas: A Linguist in the Box as a Multi-Purpose Language.}
\newblock In: Proceedings of the First International Conference on Language Resources and Evaluation (LREC-98), 1998.

\bibitem[\protect\citeauthoryear{Nirenburg and Raskin}{1998}]{NirenburgRaskin1998}
Nirenburg, Sergei and Raskin, V.
\newblock{Universal Grammar and Lexis for Quick Ramp-Up of {MT} Systems.}
\newblock In: Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and the 17th International Conference on Computation Linguistics (COLING-ACL-98), 1998.

\bibitem[\protect\citeauthoryear{Och and Ney}{2002}]{OchNey2002}
Och, Franz Josef and Ney, Hermann.
\newblock{Discriminative Training and Maximum Entropy Models for Statistical Machine Translation.}
\newblock In: Proceedings of the 40th Anniversary Meeting of the Association for Computational Linguistics (ACL-02), 2002.

\bibitem[\protect\citeauthoryear{Papineni et al.}{1998}]{PapineniEtAl1998}
Papineni, Kishore and Roukos, Salim and Ward, Todd. 
\newblock{Maximum Likelihood and Discriminative Training of Direct Translation Models.}
\newblock{In: Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP-98), 1998, 189-192.}

\bibitem[\protect\citeauthoryear{Peterson}{2002}]{Peterson2002}
Peterson, Erik.
\newblock{Adapting a Transfer Engine for Rapid Machine Translation Development}.
\newblock Masters Research Paper, Georgetown University. 2002.

\bibitem[\protect\citeauthoryear{Probst et al.}{2001}]{ProbstEtAl2001}
Probst, Katharina and Brown, Ralf and Carbonell, Jaime and Lavie, Alon and Levin, Lori and Peterson, Erik
\newblock{Design and Implementation of Controlled Elicitation for Machine Translation of Low-density Languages.}
\newblock Workshop MT2010 at Machine Translation Summit VIII, 2001.

\bibitem[\protect\citeauthoryear{Sherematyeva and Nirenburg}{2000}]{SherematyevaNirenburg2000}
Sherematyeva, Svetlana and Nirenburg, Sergei.
\newblock{Towards a Unversal Tool for {NLP} Resource Acquisition.}
\newblock In: Proceedings of the 2nd International Conference on Language Resources and Evaluation (LREC-00), 2000.

\bibitem[\protect\citeauthoryear{Shieber}{1986}]{Shieber1986}
Shieber, Stuart M.
\newblock{An Introduction to Unification-Based Approaches to Grammar.}
\newblock Center for the Study of Language and Information, Lecture Notes Number 4, 1986.

\bibitem[\protect\citeauthoryear{Tomita}{1988}]{Tomita1988} 
Tomita, Masaru, Editor and Mitamura, Teruko and Musha, Hiroyuki and Kee, Marion.   
\newblock {The Generalized LR Parser/Compiler Version 8.1: User's Guide.}
\newblock CMU Center for Machine Translation Technical Report. April, 1988.

\bibitem[\protect\citeauthoryear{Trujillo}{1999}]{Trujillo1999}
Trujillo, Arturo.
\newblock{\em Translation Engines.}
\newblock Springer Verlag, 1999.

\bibitem[\protect\citeauthoryear{Wheeler}{1981?}]{Wheeler1981}
Wheeler, Alvaro.
\newblock{\em Dictionary of Siona.}
\newblock unpublished, 1981?.

\bibitem[\protect\citeauthoryear{Vogel and Tribble}{2002}]{VogelTribble2002}
Vogel, Stephan and Tribble, Alicia.
\newblock{Improving Statistical Machine Translation for a Speech-to-Speech Translation Task.}
\newblock{In: Proceedings of the 7th International Conferenc on Spoken Language Processing (ICSLP-02).}

\bibitem[\protect\citeauthoryear{Yamada and Knight}{2001}]{YamadaKnight2001}
Yamada, Kenji and Knight, Kevin.
\newblock{A Syntax-Based Statistical Translation Model.}
\newblock{In: Proceedings of the 39th Anniversary Meeting of the Association for Computational Linguistics (ACL-01).}

\end{thebibliography}

\end{article}
\end{document}
