\section{Transfer Rule Learning}

Transfer Rule Learning can be divided into three steps.  The first
step, feature detection, is really a seperate step that proceeds the
learning, but provides the learning module with information
to guide its search. The second step is Seed Generation, where first
guesses at transfer rules are constructed from training examples.
Seed Generation produces transfer rules that are very specific to the
training example.  The third step, Version Space Learning, alleviates
this problem by generalizing the seed rules in order to produce
transfer rules that can be used to translate unseen examples.

\subsection{Feature Detection}
Feature detection is a process whose goal it is to obtain information
on the usage of linguistic features and their values in the target
language.  It is based on the minimal pairs of training sentences.  As
explained above, the elicitation corpus is organized into minimal
pairs, i.e. sentences that differ in only one feature. 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 wish to find out whether the
target language marks number on nouns, we compare the translation of
the two nouns, one of which is in the singular, and one of which is in
the plural, where the number of this noun is the only feature that
differs between the two languages, such as in sentences 1 and 2 in the
previous example in section \ref{The Elicitation Corpus}. If they are
different, we assume that the difference is caused by the number of
the subject.  Feature detection has a number of robustness mechanisms
built in, so that we make no hard decisions based on few training
examples.  For more information on feature detection, please refer to
\cite{ProbstEtAl2001}.

\subsection{Seed Generation}\label{SeedGeneration}
The first part of the transfer rule 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
English sentences have been 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
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 features' values can be assumed to transfer into
the target language, so that we assume, for example, that a plural
noun will be translated as a plural noun.  One field of ongoing work
is the explicit incorporation of the information gathered during
feature detection in the seed generation and seeded version space
learning algorithms.

To make these concepts more concrete, consider an example of a seed rule as produced by our algorithm.  The seed rule can be found in the first column of figure 1 below.
Everything that is preceeded by two semicolons is ignored by the
transfer engine. This transfer 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 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
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 for example for a sentence, we can make use of NP rules that have already been learned.  The produced seed rule is then no longer a flat rule, but will consist of constituents such as NPs.   We will describe compositionality in more detail in a future paper.

\section{Seeded Version Space learning}

After producing a seed rule for each sentence in the training corpus,
the seeded version space learning algorithm is executed.\footnote{In it current version, the seeded version space learning algorithm is not affected by compositionality - that is, the algorithm will execute in the same way if the input rules are compositional.}  First, seed
rules are grouped 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 their constraints. The learning algorithm is run on
each group separately.  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:

\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}$ and vice versa. 
\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 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 done 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 then boils to repeatedly
merging two transfer rules in a group and checking whether the merged
rule is still specific enough to translate all those sentences that
the unmerged rules could translate.  If this is the case, a merge is
accepted.  Note that this represents a greedy approach, which is
necessary due to the size of the search space (i.e. the version space
for each group). Merging continues until no two transfer rules in the
cluster can be merged any more.

Below 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.\\

\begin{table*}
\begin{tabular}{|l|l|l|}\hline
\textbf{SeedRule1} & \textbf{SeedRule2} & \textbf{Generalized Rule} \\ \hline
;;SL: THE WOMAN & ;;SL: THE WOMAN & ;;SL: THE WOMAN \\
;;TL: DIE FRAU & ;;TL: DIE FRAU & ;;TL: DIE FRAU \\
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 COUNT) = +) & ((X1 COUNT) = +) & ((X1 COUNT) = +) \\
((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 GENDER) = *F) & ((Y1 GENDER) = *F) & ((Y1 GENDER) = *F) \\
((Y1 CASE) = & ((Y1 CASE) = & ((Y1 CASE) = \\
 \ \ (*NOT*\ *GEN\ *DAT)) & \ \ (*NOT*\ *GEN\ *DAT)) & \ \ (*NOT*\ *GEN\ *DAT)) \\
((Y1 AGR) = *3-SING) & ((Y1 AGR) = *3-SING) & ((Y1 AGR) = *3-SING) \\
((Y1 DEFINITENESS) = *+) & ((Y1 DEFINITENESS) = *+) & ((Y1 DEFINITENESS) = *+)\\
((Y2 GENDER) = *F) & ((Y2 GENDER) = *F) & ((Y2 GENDER) = *F) \\
((Y2 AGR) = *3-SING) & ((Y2 AGR) = *3-SING) & ((Y2 AGR) = *3-SING)\\
((Y2 COUNT) = *+)) & ((Y2 COUNT) = *+)) & ((Y2 COUNT) = *+)) \\ \hline
\end{tabular}
\caption{Seed Rules and Generalized Transfer Rule}
\end{table*}




Also necessary is a parser for the elicitation sentences, an example 
being LCFlex for English \cite{rose2001}.