\subsection{Comprehensive Transfer Rule Formalism}

As was mentioned 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 comprehensive transfer rules for machine translation.  This section describes the transfer
rule formalism and transfer engine. 

 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 comprehensive transfer rule. In general, the x-side of a comprehensive 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 comprehensive 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 comprehensive 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
comprehensive 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
comprehensive 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 Comprehensive 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 comprehensive 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.
Thus, {\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 comprehensive 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 the learning process 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 comprehensive transfer rules contain a myriad of information,
including feature information about its constituents.

In many systems, comprehensive 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 comprehensive 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 comprehensive transfer rules are thus specifically designed
for the circumstances as well as for the learning task at hand.

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


\subsection{Modified Transfer Engine with Comprehensive Rules}
\textbf{Pull out parts from following section}

Like most modern translation sytems, the \textsc{Avenue} transfer
engine maintains a strict separation between the transfer algorithms
and linguistic data. 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 representation, given the
nature of the transfer rules, as described in the previous
section. The \textsc{Avenue} engine consequently is similar to the
`modified' transfer approach used in the early \textsc{Metal} system
\cite{Hutchins1992}.

When reading in rules, the engine will automatically match rules
together that have the same parsing constraints, both the production
rule and unification equations.  These sets of rules, called parse
groups, are then used during the parsing stage of translation.
Parsing is accomplished using a chart-parsing algorithm, producing a
packed representation of the possible parse trees for the input.
Even if a full parse for the input is not found, parses for sections
of the input can still be used to produce a partial translation.

Once analysis is complete and one or more full or partial parses for
the input have been found, transfer then begins.  Transfer begins at
the root node for the parse tree and then descends in a depth-first
traversal to the leaf nodes, or lexical items.  At each branch of the
tree the transfer unification equations (the XY-constraints mentioned
in the previous section) are run.  The subtrees of this branch are
then reordered as specified by the constituent alignments in the
transfer rule.  This process then occurs again on each of the subtrees
until the leaf/lexical nodes are encountered.  In the transfer engine,
syntactic and lexical transfer stages are separated, so when a lexical
node is encountered, it is noted for later processing, instead of
being immediately transfered.

At anytime during this process, if the XY-constraints of a particular
rule fail, transfer stops and the engine backs up to the most recent
point in the tree where an alternate transfer rule could have been
used.  Transfer then continues from this point using the alternate
rule.  If no such alternate was found, the engine stops and reports
that no full translation was possible.  Backing up rather than
starting again from the top saves much processing time.

When syntactic transfer has finished and the target language tree has
been fully generated, lexical transfer then commences.  For each
lexical node noted earlier in transfer, all of its possible
translations are produced.  The various combinations of these sets of
lexical translations are then used in the final step of checking
Y-side constraints.  Information needed for the Y-side constraints,
such as agreement features for subject and verb, is often not
available till after the target word translations are chosen.  For
each possible target lexical combination, a Y-side constraint checking
pass is run where features from the words can be passed up the tree to
point where they are needed for constraint unification equations to be
run.  This feature passing is not automatic, specific Y-side
unification rules must be written for this purpose.  For example, to
pass up the value ``num'' up to next highest node in the tree, an
equation such as ((Y0 num) = (Y2 num)) would be used.  If all the
Y-side constraints are satisfied, the successful lexical combination
is recorded and added to the list of translations to return.  This
continues until all the possible lexical combinations have been
tried.

If a full parse is not found or a complete translation is not
possible, the engine concatenates together the longest successful
translations of the sections of the sentence.  If a word does not have
an entry in the transfer lexicon, the grammar writer can specify what
open class parts of speech to use for the word in parsing.  The
original source word itself is then used in the translation.

