\documentclass[11pt]{article}
%\usepackage[dvips]{graphicx}
\title{AVENUE}
\author{
\begin{tabular}[t]{c}
all of us\\
Language Technologies Institute\\
Carnegie Mellon University\\
Pittsburgh, PA, USA, 15213 
\end{tabular}
}
\date{\today}

\begin{document}
\maketitle


\section{Introduction}

\section{The Elicitation Corpus}
As for low-density language there is usually little or no bilingual data available, we elicit data from a bilingual informant.  The informant translates a set of sentences that we construct prior to learning, and once for all languages. 
An interface was designed that presents the user with on sentence at a time.  The user enters the translation and specifies how the words in both language align.  Below is a picture of our elicitation interface.
\textbf{[add picture of interface here]}

The elicitation corpus contains sentences that are carefully constructed based on linguistic features and phenomena.  We wish to obtain as much information as possible about typologically prevalent features (such as number) and their possible values in the target language (such as singluar, 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 elicitaion corpus adheres to a number of design principles. To begin with, it is constructed based on compositionality.  First, the informant is asked to translate noun phrases.  Then noun phrases are used in simple sentences, etc.  In this way, the learning module can learn transfer rules for noun phrases first, and can then utilize the learned rules in constructing rules for sentences.  Similarly, it can use the learned rules in constructing adjective rules.

Furthermore, the corpus is organized in minimal pairs, i.e. sentences that differ only in one feature.  Consider the following example:

\begin{enumerate}
\item \textit{The man saw the young girl.}
\item \textit{The men saw the young girl.}
\item \textit{The woman saw the young girl.}
\end{enumerate}

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 two and three also form minimal pair.  They differ only in the gender of the subject. The organization into minimal pairs is used by a module called feature detection.  Feature detection precedes the version space learning module.  Its goal is to obtain as much information as possible about the use of linguistic features in the target language.  For instance, feature detection strives to determine whether specific features (such as number) are marked on specific groups of words or parts of speech (such as noun).  Feature detection will be described briefly below in section \ref{The Learning Module}.

In designing a corpus, we strive maximize coverage while minimizing the size of the corpus 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 uses 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, many important phenomena may not occur in the training corpus, or the user may be required to translate a much larger corpus to achieve the same coverage.  Therefore, we believe that a controlled corpus is making the best use of the informant's time while creating a diverse set of training examples for the learning module.


 For more detail on the elicitation process, please refer to \cite{ProbstLevin2002}.

\section{Transfer Rule Learning}

Transfer Rule Learning can be divided into three steps.  The first step, feature detection, is really a seperate steps that proceeds the learning, but provides the learning module with additional 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 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 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, we now present an example of a seed rule as it was produced by the seed generation algorithm:
\begin{footnotesize}
$;;SL: THE\ WOMAN\\
;;TL: DIE\ FRAU\\
NP::NP [DET\ N] -> [DET\ N]\\
(;;alignments:\\
(X1::Y1)\\
(X2::Y2)\\
;;x-side\ constraints:\\
((X1\ AGR) = *3-SING)\\
((X1\ COUNT) = +)\\
((X2\ AGR) = *3-SING)\\
((X2\ COUNT) = +)\\
;;y-side\ constraints:\\
((Y1\ GENDER) = *F)\\
((Y1\ CASE) = (*NOT*\ *GEN\ *DAT))\\
((Y1\ AGR) = *3-SING)\\
((Y1\ DEFINITENESS) = *+)\\
((Y2\ GENDER) = *F)\\
((Y2\ AGR) = *3-SING)\\
((Y2\ COUNT) = *+))$
\end{footnotesize}

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.  This means that if the algorithm cannot unambiguously determine what part of speech a target language word is, it is assumed that it has the same part of speech as the source language word that it aligns to. 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.

\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.  First, seed rules are grouped by their part of speech sequences, 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 of 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{footnotesize}
$;;SL: THE\ WOMAN\\
;;TL: DIE\ FRAU\\
NP::NP [DET\ N] -> [DET\ N]\\
(;;alignments:\\
(X1::Y1)\\
(X2::Y2)\\
;;x-side\ constraints:\\
((X1\ AGR) = *3-SING)\\
((X1\ COUNT) = +)\\
((X2\ AGR) = *3-SING)\\
((X2\ COUNT) = +)\\
;;y-side\ constraints:\\
((Y1\ GENDER) = *F)\\
((Y1\ CASE) = (*NOT*\ *GEN\ *DAT))\\
((Y1\ AGR) = *3-SING)\\
((Y1\ DEFINITENESS) = *+)\\
((Y2\ GENDER) = *F)\\
((Y2\ AGR) = *3-SING)\\
((Y2\ COUNT) = +))$\\
\end{footnotesize}

\begin{footnotesize}
$;;SL: THE\ MAN\\
;;TL: DER\ MANN\\
NP::NP [DET\ N] -> [DET\ N]\\
(;;alignments:\\
(X2::X2)\\
(X1::X1)\\
;;x-side\ constraints:\\
((X1\ AGR) = *3-SING)\\
((X1\ COUNT) = +)\\
((X2\ AGR) = *3-SING)\\
((X2\ COUNT) = +)\\
;;y-side\ constraints:\\
((Y1\ AGR) = *3-SING)\\
((Y1\ CASE) = *NOM)\\
((Y1\ DEFINITENESS) = *+)\\
((Y1\ GENDER) = *M)\\
((Y2\ AGR) = *3-SING)\\
((Y2\ CASE) = *NOM)\\
((Y2\ COUNT) = *+)\\
((Y2\ GENDER) = *M))$
\end{footnotesize}


\end{document}
