\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, Mitchell96, 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 in 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 probabilistic measure.

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, than 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 used during the Seeded Version Space Learning}.  \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
SL part-of-speech sequence & English c-structure\\ \hline
TL part-of-speech sequence & 1) from the TL dictionary \\ 
& 2) from the English POS sequence \\ \hline
Alignments & from the user\\ \hline
x-side constraints & from the English f-structure\\ \hline
y-side constraints & from the TL dictionary\\
& 2) from the corresponding English words\\ \hline
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 1 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 for example 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 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): \\pagebreak


\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}
\end{table*}

\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 is the repeated application
merging two transfer rules in a group and checking whether the merged
rule is still specific enough to translate correctly all those sentences 
that the unmerged rules could 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.

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


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