\documentclass[runningheads]{llncs}
\usepackage[dvips]{graphicx}

%\input{psfig.sty}

\begin{document}

\pagestyle{headings}
%In order to omit page numbers and running heads
%please change this line to
%\pagestyle{empty}
%and change the first command line too, see above.

\mainmatter

\title{Automatic Rule Learning for Resource-Limited MT}

\titlerunning{{\sc Resource-Limited MT}}

\author{Jaime Carbonell \and Christian Monson
\and Erik Peterson \and Katharina Probst \and
Ralf Brown \and Alon Lavie \and Lori Levin}

\authorrunning{Carbonell et al.}

\institute{Language Technologies Institute\\
Carnegie Mellon University\\
Pittsburgh, PA 15213\\
\email{\{jgc, cmonson, eepeter, kathrin, alavie, ralf, lsl\}@cs.cmu.edu}}

\maketitle

\begin{abstract}

Machine Translation of minority languages presents unique challenges,
including the paucity of bilingual training data and the unavailability
of linguistically-trained speakers.  This paper focuses on a machine
learning approach to transfer-based MT, where data in the form of
translations and lexical alignments are elicited from bilingual 
speakers, and a seeded version-space learning algorithm formulates
and refines transfer rules.  A rule-generalization lattice is defined
based on LFG-style f-structures, permitting generalization and specialization
operators in the search for the most general rules consistent with the elicited
data.  Additionally, unsupervised learning of morphology reduces the
potential rule version space.  The paper presents these methods and
illustrates examples.

\end{abstract}

\section{Introduction}

Machine Translation (MT) for minority languages offers significant potential
benefits, but also presents serious scientific and economic challegens.
Among the benefits are: communication between isolated, often economically
disadvantaged groups (i.e. multiple indigenous groups in Latin America)
and the speakers of majority languages, and the potential preservation of
endangered languages -- over half of the 6,000 presently existing languages
worldwide.  The primary scientific challenge is the creation of MT systems 
for languages of little economic importance at very low cost per language,
including the acquisition of linguistic information with minimal pre-existing
bilingual corpora and little or no previous linguistic analysis of the
minority language.

In order to address these needs, we are investigating omnivorous MT
systems, including statistical and example-based MT when some parallel
training corpora can be acquired, and machine learning of transfer-based 
MT rules when access to a native non-linguist informant permits 
partial elicitation of linguistic information, such as translations
of model sentences and lexical-level bilingual alignments. Both 
methods benefit from morphological analysis of the minority language.
But, since we assume the morphology (as well as grammar) is unknown
at the outset, we address methods for morphological paradigm discovery.
This paper focuses on the last two objectives of our project:
unsupervised morphology learning from monolingual corpora, and
and supervised learning of transfer rules with the aid of an
elicitation interface to a bilingual native speaker without any
assumptions regarding his or her linguistic sophistication.
First, we detail the elicitaiton phase.  Then, we discuss our 
transfer engine, followed by the seeded-version-space learning
method to aquire and refine the transfer rules. Subsequently,
we present a first version of our morphology learning module,
and conclude with directions of future investigation.

\section{The Elicitation Corpus}

Since there is usually little or no bilingual translated
data available for minority languages, we elicit the minimal
amount of information required from a bilingual informant.  The
informant translates a set of sentences constructed prior to
learning -- the same set all languages -- designed to elicit all
the basic grammatical constructions, for the principles
of field linguistics. The informant supplies lexical alignments as 
well as translations, as illustrated in figure 1.

\vspace{1.2in}
\begin{figure}
   \includegraphics[scale=.55]{elicitationinterface.eps}
  \label{ElicitationInterface}
  \caption{AVENUE elicitation interace}
\end{figure}

The elicitation corpus contains sentences and sub-sentential constituents 
carefully constructed to obtain as much information as possible about 
typologically prevalent features (such as tense and number) and their 
possible values in the target language (such as singular, dual, plural).  
To this end, we rely on research done in field linguistics, and use lists 
that were designed for this task, such as \cite{ComrieSmith1977} and
\cite{BouquiauxThomas1992}. The corpus exploits compositionality, 
starting with smaller constituents and recycling them in higher
level ones, paralleling the compositional machine learning for
Version Spaces discussed below.

In designing the corpus, we strive to maximize coverage while minimizing 
size by targeting specific constructions. For instance, we wish for 
the system to develop transfer rules for relative clauses.  Therefore, 
we developed a set of sentences that exhibit different types of 
relative clauses, such as subject relative clauses, object relative 
clauses, relative clauses with a singular antecedent, etc.  
This way, we ensure that the system has training data for a wide 
variety of phenomena.  If an uncontrolled corpus was used, it would
need to be several orders of magnitude larger to cover a comparable
range of linguistic variability, and therefore it would impose a much
larger burden on the bilingual informant.
For more detail on the elicitation process, please refer to \cite{ProbstEtAl2001} and \cite{ProbstLevin2002}.

\section{AVENUE Translation Engine}

Rule-based translation is done in AVENUE through a custom-built translation
engine using an integrated transfer approach with analysis, transfer, and
generation stages.  In the AVENUE engine, as in the early METAL
system \cite{hutchins1992}, each analysis rule is also coupled with a
corresponding transfer action.  While this leads
to some duplication of effort during analysis, since a particular
parse could possibly be transferred in several different ways, it
reduces search at transfer time and permits transfer-rule learnability,
because credit (or blame) assignment for correct (or incorrect) translations
becomes more deterministic.

The transfer rule formalism is able to handle a variety of common
translation divergences, including head-switching, thematic changes
such as an object in one language being expressed as a subject in the
target language, structural changes such as having an NP become a PP
in another language, and lexical gaps where one target word replaces
an entire source phrase \cite{trujillo1999}.  Though the transfer engine does
not currently have a component for deep semantic analysis or discourse
processing, leaving some ambiguities unresolvable, it is sufficient for state-of-the-practice MT.

\begin{figure}
\caption{\label{rule1}  Sample Transfer Rules}
\small
\parbox[t]{5.5cm}{
; Rule to handle non-auxiliary verb\\
; question transfer from Chinese to\\
; English\\
\{S,3\}\\
S::S : [NP VP MA] -$>$ [V NP VP "?"]\\
(;; Constituent alignments\\
  (X1::Y2)\\
  (X2::Y3)\\
;; x-side constraints
;; (parsing)\\
  ((x0 subj) == x1)\\
  ((x0 subj case) = nom)\\
  (x0 = x2)\\
  ((x0 act) = quest)\\
;; xy-constraints
;; (transfer)\\
  (y0 = x0)\\
  ((y0 act) =c quest)\\
;; y-side constraints
;; (generation)\\
  ((y1 form) = do)\\
  ((y1 agr) = (y2 agr))\\
  (y2 == (y0 subj))\\
  (y3 = y0))
}
\hfill
\parbox[t]{5.5cm}{
; Sample lexical transfer rules
 AUX::AUX $|$: [zuo4] -$>$ [do]\\
 ((x1::y1)\\
 ((y0 form) = do)\\
 ((y0 agr) = (*or* 1sg 2sg pl))\\
 ((y0 tense) = present)\\
 )\\
 \\
 AUX::AUX $|$: [zuo4] -$>$ [does]\\
 (\\
 (x1::y1)\\
 ((y0 form) = do)\\
 ((y0 agr) = 3sg)\\
 ((y0 tense) = present))
}
\end{figure}

Translation starts with a bottom-up unification-based chart parser
that produces an ambiguity-packed representation of the source language
input.  Rules are currently applied in the order they appear when read
in, but work is underway to order the rule application by the
complexity of the rule and the specificity of its constraint
equations.  Analysis builds both a syntactic constituent structure and
an associated feature structure.  For example, in the structural
transfer rule in figure \ref{rule1}, which handles the transfer of
some types of interrogative sentences from Mandarin to English, the feature
structure for the S constituent (represented by x0) is built by
setting the value of 'subj' to the NP's feature structure (referenced
as x1), setting the subject's case to nominative, its speech act (act)
to `quest' for question, and finishing by copying over the feature
structure of the VP (x2).

Transfer is done from the top down, starting at the top node in the
chart created during parsing.  Transfer rules explicitly state the
alignment of source and target constituents through equations such as
(X1::Y2) and (X2::Y3) in the example rule, which says that the first
source constituent maps to the second target constituent, and the
second source constituent maps to the third target constituent.  Not
all source constituents need map to the target (such as the Chinese
question particle MA at X3 in this rule which is deleted during
transfer).  Target constituents that are not aligned to a source
constituent will be created based upon the feature structure assigned
to them in the transfer and generation equations.  During transfer,
the engine uses these alignments to reorder constituents to fit the
target language grammar.  Features may also be passed from source to
target, such as the (y0 = x0) equation in the example which copies the
entire source sentence feature structure to the target. More pinpoint
feature transfers (such as transferring only number or tense) are also
supported.

During generation, the target side feature structures are built and
target constituent agreement constraints are checked.  In the example
rule, the first constituent V (Y1) has its form set to `do', which is
used later to choose the correct verb to insert.  To enforce that the
form of `do' agrees with the subject NP at Y2, the ((y1 agr) = (y2
agr)) is used. 

Once a selected transfer rule is applied, transfer and generation
continues by recursively running applicable transfer rules on the
sub-constituents of the rule until the lexical level is reached.
Lexical transfer rules then apply to select the appropriate
translation.  In the example, the auxiliary 'do' is inserted at the
start of the sentence.  The appropriate form of 'do' is selected based
upon the agreement constraint between the subject NP and initial V in
the sentence rule and the agreement features in the individual lexical
rules.

\section{Seeded Version Spaces for Transfer Rule Learning}

Transfer-rule learning can be divided into three steps.  The first
step is feature detection that determines which lingustic features are 
present in the new language.  For instance, does the language have
a number-agreement feature?  If so, is the distinction between
singular and plural, or between, singular, dual and plural?
For details on feature detection, please refer to \cite{ProbstEtAl2001}.
The second step is seed-rule generation, where preliminary transfer
rules are generated based on lexically-aligned translated constituents.
Seed generation produces transfer rules that are very specific to the
training examples, essentially defining the operational {\em S-boundary}
for Version-Space learning \cite{Mitc78} \cite{Mitchell96} \cite{Hirsh91}.
The third step, Seeded Version Space Learning, alleviates this problem by 
generalizing the seed rules in order to produce transfer rules that can 
be used to translate larger classes of unseen examples.
Version spaces require well-defined generalization operators that
define a lattice among concepts (i.e. among transfer rules in our 
application), as presented below.

\subsection{Seed Generation}\label{SeedGeneration}

Version Space learning suffers worst-case exponential behavior as
a function of the number of generalization (or specialization) steps
required from initial instances.  But, if the initial instances
are already generalized and the number of additional generalization
steps k-bounded -- or limited to a greedy-search, the process is
at worst a k-degree polynomial.  Hence, to ensure a measure of computational
tractability, we first build generalized rule-instances called ``seed rules,''
to the extent that we can build first-level deterministic error-free 
generalization.  Future work will relax the error-free assumption by
substituting a retractable S-boundary.

Seed rules represent generalizations over the lexical level, but are 
still very specific to the lexically-aligned sentence pair from which
they are derived.  The major-language (English) sentences in the
training corpus have been pre-parsed and disambiguated in advance, so
that the system has access to a correct feature (or for short
f-)structure and a correct phrase or constituent (c-)structure for
each sentence.  The seed generation algorithm can proceed in different
settings based on how much information is available about the target
(unknown, minority) language.  In one extreme case, we assume that we 
have a fully-inflected target language dictionary.  The other extreme is the
absence of any information, in which case the system makes assumptions
about what linguistic feature values that transfer to
the target language. For example, we assume, that number and 
definiteness transfer across languages, but not gender or case.
This information is either defaulted or extracted in the earlier
feature detection phase.

During seed generation, all transfer rule components are produced from the sentence pair, with the exception of xy-constraints.\footnote{xy-constraints are inferred during the Seeded Version Space Learning}.  Table \ref{SummarySeedGeneration} below summarizes how each part of the seed rule is produced.
%, while Table 2 spells out the seed generation algorithm in pseudo-code.  In this current version, the source language is always English. 

\begin{table}[h]
\caption{Summary of Seed Generation}
\begin{tabular}{|l|l|} \hline
\textbf{SL part-of-speech sequence} & English c-structure\\ \hline
\textbf{TL part-of-speech sequence} & 1) from the TL dictionary \\ 
& 2) from the English POS sequence \\ \hline
\textbf{Alignments} & from the user\\ \hline
\textbf{x-side constraints} & from the English f-structure\\ \hline
\textbf{y-side constraints} & from the TL dictionary\\
& 2) from the corresponding English words\\ \hline
\textbf{xy-constraints} & Not produced during seed generation \\ \hline
\end{tabular}
\label{SummarySeedGeneration}
\end{table}

To make these concepts more concrete, consider an example of a 
seed rule as produced by our algorithm for simple NPs in English-German 
(for expositionary simplicity), as illustrated in figure \ref{SampleVS} below.
Everything preceded by two semicolons is ignored by the
transfer engine. This rule was produced from the simple noun
phrase `THE WOMAN', translated into German as `DIE FRAU'. The English
part-of-speech sequence was obtained from the English parse.  The
German part-of-speech sequence was obtained from a combination of the
target language dictionary and the assumption that in the absence of
unambiguous target language information, parts of speech transfer into
the target language for aligned words.  The lexical alignments were 
given by the bilingual informant.  The x-side constraints came 
directly from the English c- and f-structures.  The y-side constraints 
were again obtained by a combination of target language information and
``safe'' transfer heuristics.  If feature information is given in the target 
language, it is used.  If no such information is available, features such as
agreement and count project their values onto the target language.
This means that target language words obtain their feature values from
their corresponding words in the source language. No xy-constraints
are produced during seed generation.

We are currently investigating the important issue of compositionality:  
when producing a compositional rule e.g. for a sentence, 
we can make use of sub-constituent transfer rules already learned.  
Then, the new seed rule is then no longer a flat rule, but consists of previously learned transfer constituents such as NPs. 

\subsection{Seeded Version Space learning}

The first step in Seeded Version Space Learning is to group the seed
rules  by their part of speech sequences (constituent sequences 
in the compositional case), alignments, and
type information.  This means that in each group, the seed rules
differ only in the constraint equations. The learning algorithm is run on
each group separately, as each group corresponds to a target concept
(i.e. a target generalized transfer rule).
At the heart of the version space learning is
the merging of two transfer rules to a more general transfer rule.  To
this end, it is necessary to clearly define the partial order by which
the generality of transfer rules can be assessed (i.e. how the implicit
generalization lattice is constructed): 

\begin{table*}[h]
\caption{Seed Rules and Generalized Transfer Rule}
\begin{tabular}{|l|l|l|}\hline
\textbf{SeedRule1} & \textbf{SeedRule2} & \textbf{Generalized Rule} \\ \hline
;;SL: THE MAN & ;;SL: THE WOMAN & ;;SL:  \\
;;TL: DER MANN & ;;TL: DIE FRAU & ;;TL: \\
NP::NP [DET N] $\rightarrow$ [DET N] & NP::NP [DET N] $\rightarrow$ [DET N] & NP::NP [DET N] $\rightarrow$ [DET N] \\
(;;alignments: & (;;alignments: & (;;alignments: \\
(X1::Y1) & (X1::Y1) & (X1::Y1) \\
(X2::Y2) & (X2::Y2) & (X2::Y2) \\
;;x-side constraints: & ;;x-side constraints: & ;;x-side constraints: \\
((X1 AGR) = *3-SING) & ((X1 AGR) = *3-SING) & ((X1 AGR) = *3-SING) \\
((X1 DEF) = *DEF) & ((X1 DEF) = *DEF) & ((X1 DEF) = *DEF) \\
((X2 AGR) = *3-SING) & ((X2 AGR) = *3-SING) & ((X2 AGR) = *3-SING) \\
((X2 COUNT) = +) & ((X2 COUNT) = +) & ((X2 COUNT) = +) \\
;;y-side constraints: & ;;y-side constraints: & ;;y-side constraints: \\
((Y1 AGR) = *3-SING) & ((Y1 AGR) = *3-SING) & ((Y1 AGR) = *3-SING) \\
((Y1 CASE) = *NOM) & ((Y1 CASE) =  &  \\
& (*NOT* *GEN *DAT)) &  \\
((Y1 DEF) = *DEF) & ((Y1 DEF) = *DEF) & ((Y1 DEF) = *DEF)\\
((Y2 GENDER) = *M) & ((Y2 GENDER) = *F) & ((Y2 GENDER) = *F) \\
((Y2 AGR) = *3-SING) & ((Y2 AGR) = *3-SING) & ((Y2 AGR) = *3-SING)\\
((Y2 CASE) = *NOM) &  &  \\
((Y2 GENDER) = *M) & ((Y2 GENDER) = *F) & ((Y2 GENDER)\\ 
& &  = (Y1 GENDER))\\ \hline
\end{tabular}
\label{SampleVS}
\end{table*}

\newtheorem{mydefinition}{Definition}
\begin{mydefinition}
  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
transfer rules are equivalent if and only if all f-structures that are
satisfied $tr_{1}$ are also satisfied by $tr_{2}$.
\end{mydefinition}

%\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
%transfer rules are equivalent if and only if all f-structures that are
%satisfied $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}$. In particular, three generalization operations have been identified:

\begin{small}
\begin{enumerate}
\item Deletion of a value constraint
\item Deletion of an 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_{i}\  feature_{k}) = value_{l})\\
((X_{j}\  feature_{k}) = value_{l})\\
\to
((X_{i}\  feature_{k}) = (X_{j}\  feature_{k}))$,

or similarly for y-side constraints.
\end{enumerate}
\end{small}

Generalization is achieved by merging transfer rules, which in turn
is based on the three generalization operations defined above.
Suppose we wish to merge two transfer 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{small}
\begin{enumerate}
\item Insert all constraints that appear in $tr_{1}$ and $tr_{2}$ into $tr_{merged}$ and subsequently eliminate them from $tr_{1}$ and $tr_{2}$.
\item Consider $tr_{1}$ and $tr_{2}$ separately.  Perform all instances of operation 3 that are possible given the constraints. 
\item Repeat step 1.
\end{enumerate}
\end{small}

The seeded version space algorithm itself is the repeated application
merging two transfer rules in a group and checking whether the merged
rule is specific enough to translate correctly all those sentences 
that the unmerged rules could also translate.  If this is the case, a merge is
accepted.   Merging continues until no two transfer rules in the
cluster can be merged any more. Note that this method is a greedy approach
to generalization, without guaranteeing that the optimal (most general)
transfer rule will be found.  However, the method is sound with
respect to allowable generalizations and computationally tractable.

Figure \ref{SampleVS} is an example of a very simple version space, seeded with only
two transfer rules, a rule produced by `THE MAN' and one produced by
`THE WOMAN'.  We show the seed rules as well as the merged rule.  In
this case, the merged rule can be used to translate both `THE MAN' and
`THE WOMAN', whereas each of the seed rule can only be used to
translate the NP they were produced from.

\section{Morphology}
Morphology is a requisite pre- and post-processing step for virtually
any MT system.  However, the rules governing morphology for many minority
languages are either unknown or uncodified.  Hence, the ability to learn
inflectional and derivational morphology from data is of value, especially
if the learning requires only monolingual text, rather than the much scarcer
bilingual sentence alignable required for statistical or example-based MT.

Whereas the goal of morphology learning in AVENUE is a synthesis of data-driven
automatic learning methods and active learning methods relying on a 
bilingual informant, the current system is restricted to learning
suffixes and suffix-substitutions based on unsupervised learning over
a monolingual corpus.
 
In recent work Gaussier \cite{gaussier} investigated learning
inflectional morphology and common derivational patterns.
In AVENUE our first steps are similar to Gaussier:
specifically, we define p-similarity between words 
and the notions of a suffix pair:
 
%\newtheorem{mydefinition}{Definition}
\begin{mydefinition}
Two words $w_{1}$ and $w_{2}$ are \emph{p-similar} if and only if:
\begin{itemize}
\item $trunc(w_{1}, p) = trunc(w_{2}, p)$ where $trunc(w, k)$ is composed 
of the first $k$ characters of $w$
\item there is no $q$ such that: $q>p$ and $trunc(w_{1}, q) = 
trunc(w_{2}, q)$
\end{itemize}
\end{mydefinition}
\pagebreak
\begin{mydefinition}
A \emph{suffix pair} is a pair of strings obtained after truncation of the first 
p characters from two p-similar words which 
\begin{itemize}
\item occur more than once in the corpus and 
\item are at least k-similar.  (Where we set k equal to some small 
number, such as 4 or 5).
\end{itemize}
\end{mydefinition}
 
Using these definitions we construct a data
structure in which each suffix pair indexes the set of all
strings which, when concatenated to either suffix of the pair,
produces a word in the vocabulary.  Each suffix pair can then
be ranked by the size of the set of stems it contains.  For example, we have
derived this data structure for the Brown Corpus.  Table 
\ref{commonMorphPairs} contains the fifteen suffix pairs with the largest
associated stem sets, along with a small sample of stems for each pair.  

\begin{table}[h]
\caption{The 15 Most Common Suffix Pairs from the Brown Corpus}
\begin{tabular}{|c|c|c|}
\hline
Suffix Pair & \verb+ Count + & Examples            \\ \hline \hline
-NULL:-s   & 5048 & discourse- navigator- halfway- \\ \hline
-NULL:-\texttt{''}  & 3264 & kings- peaceful- thereof-      \\ \hline
-ed:-ing   & 1851 & conclud- reappear- demonstrat- \\ \hline
-NULL:-\texttt{'}s  & 1553 & smith- cicero- china-          \\ \hline
-NULL:-ed  & 1467 & slim- reappear- munch-         \\ \hline
-NULL:-ing & 1275 & reappear- munch- respond-      \\ \hline
-\texttt{''}:-s	   & 1123 & risk- cook- proprietorship-    \\ \hline
-NULL:-ly  & 1051 & slim- remote- peaceful-        \\ \hline
-NULL:-d   & 998  & lodge- delude- scare-          \\ \hline
-ed:-s	   & 903  & bother- patent- barb-          \\ \hline
-d:-s	   & 810  & lodge- relate- discusse-       \\ \hline
-ing:-s	   & 775  & bother- patent- brief-         \\ \hline
-e:-ing	   & 709  & conclud- stifl- demonstrat-    \\ \hline
-NULL:-\texttt{'}   & 576  & louis\texttt{'}- rogues- that-          \\ \hline
-\texttt{'}:-s	   & 549  & soul\texttt{'}- golf\texttt{'}- well\texttt{'}-           \\ \hline
\end{tabular}
\label{commonMorphPairs}
\end{table}

The suffix pairs are useful because they determine the morphological paradigms
present in the language.  In the English example the suffix pairs indicate
that many words take the suffix '-s'.  Using our knowledge of English, we know
that most nouns are pluralized by adding '-s' and also that verbs take '-s'
when they agree with third person singular subjects.  Similarly, and more
interestingly, we also learn from the suffix pairs that many words can take
both an '-ed' as well as an '-ing' suffix (namely verbs).  Thus, morphological 
paradigms surface in the suffix pairs.  Derivational morphology begins
to appear in lower-frequency suffix pairs than those included in the table.

The current aim of morphology learning is twofold: first, to 
use the suffix pairs to correctly analyze a surface string into its 
constituent morphemes, and second, to extend this approach to languages 
with richer morphology than English, such as Mapudungun.  Next, we
expect to examine data-driven morphological learning beyond suffix-chain
additions or substitutions.

\section{Conclusions and Future Work}

We presented a novel approach to learning in machine translation, a method
that we hope will open MT up to a variety of languages in which little
training data are available.  We realize that our system presents a
large undertaking: it requires a specially adapted transfer engine, a
system that infers transfer rules, as well as a morphology learning
module.  This paper presents the current
state of our system.  Over the next months, we hope to develop
each part of the system further.  In particular, we wish to complete
compositionality aspect of our seed-transfer-rule generation algorithm.
Further, we plan to refine the search through the seeded version space by
definining a function that determines what merge is the best at any one
step, given that there is more than one possible merge.  The transfer
engine will be extended to output partial translations if no full
translation can be given.  This will be especially important as our
system will be integrated into a multi-engine system, together with
statistical and example-based MT methods. 

\begin{thebibliography}{10}
%
\bibitem{BouquiauxThomas1992}
Luc Bouquiaux and Jacqueline M.C. Thomas:
Studying and Describing Unwritten Languages.
The Summer Institute of Linguistics. (1992)
%
\bibitem{ComrieSmith1977}
Bernard Comrie and Norval Smith:
Lingua Descriptive Series: Questionnaire.
In: Lingua. {\bf 42} (1977) 1--72
%
\bibitem{gaussier}
Gaussier, E.:
Unsupervised learning of derivational morphology from inflectional lexicons.
In: Proceedings of the Workshop on Unsupervised Learning in Natural Language Processing.
Association for Computational Linguistics. (1999) 24--30
%
\bibitem{Hirsh91}
Hirsh Haym:
Theoretical Underpinnings of Version Spaces.
In: Proceedings of the Twelfth International Joint Conference on Artificial 
Intelligence (IJCAI91).
Morgan Kaufmann Publishers. (1991) 665--670
%
\bibitem{hutchins1992} 
Hutchins, W. John and Somers, Harold L.:
An Introduction to Machine Translation.  
Academic Press, London. (1992)
% 
\bibitem{Mitchell96}
Tom Mitchell:
Machine Learning.
McGraw Hill (1996)
%
\bibitem{Mitc78}
Mitchell, T. M.:
Version Spaces: An Approach to Concept Learning.
Stanford University. {\bf December} (1978)
%
\bibitem{ProbstEtAl2001}
Katharina Probst and Ralf Brown and Jaime Carbonell and Alon Lavie and Lori Levin and Erik Peterson:
Design and Implementation of Controlled Elicitation for Machine Translation of Low-density Languages.
Workshop MT2010, Machine Translation Summit 2001. (2001)
%
\bibitem{ProbstLevin2002}
Katharina Probst and Lori Levin:
Challenges in Automated Elicitation of a Controlled Bilingual Corpus.
TMI 2002. (2002)
%
\bibitem{trujillo1999} 
Trujillo, A.: 
Translation Engines: Techniques for Machine Translation.  
Springer-Verlag
London Limited, London. (1999) 
%
\end{thebibliography}


\end{document}