%******************************************************************************
%*    Syntax Driven Learning of Sub-sentential Translation Equivalents and    *
%*               Translation Rules from Parsed Parallel Sentences             *
%*                                                                            *
%*                    Alon Lavie, Alok Parlikar, Vamshi Ambati                *
%*                                                                            *
%*  ACL SSST Workshop                                                   2008  *
%******************************************************************************

\documentclass[11pt]{article}
\usepackage{graphicx,acl08}
\usepackage{times}
\usepackage{latexsym}
\usepackage{ifthen}
\usepackage{algorithm}
\usepackage{algorithmic}
\setlength\titlebox{6.5cm}    % Expanding the titlebox

%%%
% Commands for easier "manipulation"
% -Alok

\newcommand{\pfa}{PFA} % Give me some name!

\newcommand{\anonymous}{FALSE} % or set it to FALSE

\newcommand{\todotext}{This section is not yet written down.}
\newcommand{\todo}{\todotext\todotext\todotext\todotext\todotext\todotext\todotext\todotext\todotext\todotext\todotext\todotext\todotext\todotext\todotext}


%%% End of custom commands

\title%
{Syntax-driven Learning of Sub-sentential Translation Equivalents and 
Translation Rules from Parsed Parallel Corpora}

\ifthenelse{\equal{\anonymous}{TRUE}}
{}
{
\author{Alon Lavie \\
  {\tt alavie@cs.cmu.edu}\\ 
  {\small Language Technologies Institute} \\
  Carnegie Mellon University \\
  Pittsburgh, PA 15213, USA\\ \And
  Alok Parlikar \\
  {\tt aup@cs.cmu.edu} \\
  {\small Language Technologies Institute} \\
  Carnegie Mellon University \\
  Pittsburgh, PA 15213, USA\\ \And
  Vamshi Ambati \\
  {\tt vambati@cs.cmu.edu} \\
  {\small Language Technologies Institute} \\
  Carnegie Mellon University \\
  Pittsburgh, PA 15213, USA\\
}
}
\date{}

\begin{document}
\maketitle
\begin{abstract}
We describe a multi-step process for automatically learning reliable
sub-sentential syntactic phrases that are translation equivalents of each
other and syntactic translation rules between two languages. The input to the
process is a corpus of parallel sentences, word-aligned and annotated with
phrase-structure parse trees.  We first apply a newly developed algorithm for
aligning parse-tree nodes between the two parallel trees.  Next, we extract
all aligned sub-sentential syntactic constituents from the parallel sentences,
and create a syntax-based phrase-table.  Finally, we treat the node alignments
as tree decomposition points and extract from the corpus all possible
synchronous parallel tree fragments.  These are then converted into
synchronous context-free rules.  We describe the approach and analyze its
application to Chinese-English parallel data.
\end{abstract}

\section{Introduction}
%  \textbf{Alon}
%\todo

% Modern state-of-the-art data-driven approaches to MT rely on machine learning
% methods of increasing complexity and sophistication in order to automatically
% acquire their underlying translation models from available data resources.
Phrase-based Statistical MT (PB-SMT) \cite{koehn:2003} has become the
predominant approach to Machine Translation in recent years.  PB-SMT requires
broad-coverage databases of phrase-to-phrase translation equivalents.  These
are commonly acquired from large volumes of automatically word-aligned
sentence-parallel text corpora.  
% The statistical word alignment
% correspondences provide estimates of the word level correspondences within 
% the
% sentence pairs.  Heuristic methods then extract likley larger 
% phrase-to-phrase
% correspondences based on the word-level alignments.  
Accurate identification of sub-sentential translation equivalents, however, is
a critical process in all data-driven MT approaches, including a variety of
data-driven syntax-based approaches that have been developed in recent years.
\cite{chiang:2005} \cite{ebmt-syntax} \cite{galley04}.
% Translations produced by
% PB-SMT systems are often disfluent and ungrammatical, since they are limited
% to exploring sequential ``chains'' of phrase translations.  Automatically
% acquired syntax-based models for MT carry the promise of addressing this
% problem, and have received increasing attention in the last few years
% \cite{chiang:2005} \cite{ebmt-syntax} \cite{galley04}.

In this paper, we describe a multi-step process for automatically learning
reliable sub-sentential syntactic phrases that are translation equivalents of
each other and syntactic translation rules between two languages. The input to
the process is a corpus of parallel sentences, word-aligned and annotated with
phrase-structure parse trees for both languages.  Our method consists of three
steps.  In the first step, we apply a newly developed algorithm for aligning
parse-tree nodes between the two parallel trees.  In the second step, we
extract all aligned sub-sentential syntactic constituents from the parallel
sentences, and create a syntax-based phrase-table.  Our syntactic phrases come
with constituent ``labels'' which can guide their syntactic function during
decoding.  In the final step, we treat the node alignments as tree
decomposition points and extract from the corpus all possible synchronous
parallel tree fragments.  These are then converted into synchronous
context-free rules.  Our methods do not depend on any specific properties of
the underlying phrase-structure representations or the parsers used, and were
designed to be applicable even when these representations are quite different
for the two languages.

The approach described is used to acquire the resources for a statistical
syntax-based MT approach that we have developed (Stat-XFER), briefly described
below.  The resulting resources can, however, be used in any syntax-based
data-driven MT approach other than our own.  The focus of this paper is on our
syntax-driven process for extracting phrases and rules from data.  We describe
the approach and analyze its effectiveness when applied to large-volumes of
Chinese-English parallel data.

\subsection{The Stat-XFER MT Framework}

Stat-XFER is a search-based syntax-driven framework for building MT systems.
The underlying formalism is based on synchronous context-free grammars.  The
synchronous rules can optionally be augmented by unification-style feature
constraints.
% These transfer rules specify how phrase structures in a
% source-language correspond and transfer to phrase structures in a target
% language, and the constraints under which these rules should apply.  
The synchronous grammars can be acquired automatically from data, but also
manually developed by experts.  A simple example transfer-rule (for
Chinese-to-English) can be seen below:

\begin{small}
\begin{verbatim}
{NP,1062753}
NP::NP [DNP NP] -> [NP PP]
(
(*score* 0.946640316205534)
(X2::Y1)
(X1::Y2)
)
\end{verbatim}
\end{small}

Each rule has a unique identifier followed by a synchronous rule for both
source and target sides.  
% The source side of the production is used by the
% translation engine for analysis of the source language, while the target side
% of the production is used for target language generation.  
The alignment of source-to-target constituents is explicitly represented using
'X' indices for the source side, and 'Y' indices for the target side.  Rules
can also have lexical items on either side, in which case no alignment
information is required for these elements.  Feature constraints can
optionally be specified for both source and target elements of the rule.  We
do not address the learning of feature constraints in the work described here,
and concentrate only on the acquisition of the synchronous CFG rules. The
rules can be modeled statistically and assigned scores, which can then be used 
as decoding features.

The Stat-XFER framework also includes a fully-implemented transfer engine that
applies the transfer grammar to a source-language input sentence at runtime,
and produces collections of scored word and phrase-level translations
according to the grammar.  These are collected into a lattice data-structure.
Scores are based on a log-linear combination of several features, and a
beam-search controls the underlying parsing and transfer process.  A
second-stage monotonic decoder is responsible for combining translation
fragments into complete translation hypotheses \cite{xfer-lavie}

%\footnote{
%Lavie, A., Stat-XFER: A General Search-based Syntax-driven Framework
% for Machine Translation. Invited paper in Proceedings of
% CICLing-2008,   Haifa, Israel, February 2008. Gelbuch (ed.),
% Computational Linguistics and Intelligent Text Processing, LNCS 4919,
% Springer. Pages 362-375.
%}
% The Stat-XFER framework was
% originally developed to support rapid MT prototype development for 
% translation
% between low-resource source languages (such as Hebrew) and high resource
% target languages (such as English).  Major improvements in the underlying
% engine along with our new fully automatic acquistion methods from data have
% extended the capabilities of the framework to support the development of 
% fully data-driven systems from large volumes of data.

%\section{Our System}
%\subsection{Grammar Formalism}
% Cancel this later if not required 
%Our transfer rule formalism can be seen below. 
%\begin{verbatim}
%VP::VP[NP "the" VP]->[NP VP]
%(
%(*score* 0.054)
%(X1::X2)
%)
%\end{verbatim}
%
%Our transfer rule formalism is similar in spirit to the Lexicalized functional
%grammar. It was designed to capture not only the structural reordering but
%also the feature based constraints that can be used in the parsing stage of
%the Transfer Based MT.
%
%In brief, each rule has a unique identifier followed by the context-free form
%of the production rules for both source and target sides. The source side
%production is used in the analysis phase of the transfer engine and the target
%side production is used in the transfer phase. The alignments information that
%decides the ordering of the constituents in the production rule is provided
%with 'X' followed by index for source side and 'Y' followed by an index for
%the target side. The rule can also have lexicalized items on either sides, in
%which case no alignment information is required for those index position.
%Finally the rules also can have an under-specified feature structure that has
%both 'x' side constraints that get used in the analysis phase and 'y' side
%constraints that get used in the generation phase. There are also agreement
%constraints that involve both 'x' side and 'y' side, which help in resolving
%ambiguity during the transfer phase.  In this work we do not consider the
%learning of feature constraints as part of the rule learning framework.  We
%only concentrate on producing context-free style synchronous transfer rules.

%\subsection{Syntax based transfer engine}
%\todo


\section{\pfa\ Algorithm for Node Aligment}

%A phrase table typically used for Machine Translation, such as one built by
%the Moses\cite{moses} system, is a list of phrases on the source side, with
%their equivalent phrases on the target side, and sets of scores that tells how
%good the phrases are. What these tables do not tell us is whether a particular
%phrase is a noun-phrase, a verb-phrase, or something else. This information is
%very essential for using a phrase table in our Statistical Transfer-based MT
%approach. We thus wanted to build a phrase table that tells us the category of
%each phrase, both on the source side, and on the target side. We came up with
%the \pfa\ Algorithm that uses a parsed parallel corpus and information about
%word alignments to build such a phrase table.

\subsection{Objectives of the Algorithm}

Our objective of the first stage of our approach is to detect sub-sentential
constituent correspondences in parallel sentences, based on phrase-structure
parses for the two corresponding sentences.  Given a pair of parallel
sentences and their corresponding parse trees, our goal is to find pairings of
nodes in the source and target trees whose yields are translation equivalents
of each other.  Our current approach only considers complete constituents and
their contigious yields, and will therefore not align discontiguous phrases or
partial constituents.  Similar to phrase extraction methods in PB-SMT, we rely
on word-level alignments (derived manually or automatically) as indicators for
translation equivalence.  The assumption applied is that if two words are
aligned with each other, they carry the same meaning and can be treated as
translation equivalents.  Constituents are treated as compositional units of 
meaning and translation equivalence.
% and their alignments are inferred based
% on these underlying composition assumptions.  
% In practice, however, automatically obtained word
% alignments are often inaccurate, and our algorithm is designed to robustly
% tolerate expected levels of such noisy word alignments.  

\subsection{Related Work}

Aligning nodes in parallel trees has been investigated by a number of previous
researchers. \cite{stockholm-treealigner} describe a process for manual
alignment of nodes in parallel trees.  This approach is well suited for
generating reliable parallel treebanks, but is impractical for accumulating
resources from large parallel data.  \cite{tinsley-robust} use statistical
lexicons derived from automatic statistical word alignment for aligning nodes
in parallel trees.  In our approach, we use the word alignment information
directly, which we believe may be more reliable than the statistical lexicon.
\cite{groves-robust} propose a method of aligning nodes between parallel trees
automatically, based on word alignments.  In addition to the word alignment
information, their approach uses the constituent labels of nodes in the trees,
and the general structure of the tree. Our approach is more general in the
sense that we only consider the word alignments, thereby making the approach
applicable to any parser or phrase-structure representation, even ones that
are quite different for the two languages involved.  
% However, in general
% terms, The Groves approach is the most similar to our own method, described
% here.

\subsection{Unaligned Words and Contiguity}

Word-level alignment of phrase-level translation equivalents often leaves some
words unaligned.  For example, some languages have articles, while others do
not. It is thus reasonable to expect that constituent pairs in parallel trees
that are good translation equivalents of each other may contain some unaligned
words.  Our \pfa\ node-alignment algorithm allows for such constituents to be
matched.

Different languages have different word orders. In English, an adjective
always comes before a noun, while in French, in most cases, the adjective
follows its noun. Our node alignment algorithm allows aligning of constituents
regardless of the word order expressed by the linear precedence relation of
their sub-constituents.  As long as one piece of contiguous text dominated by
a node covers the same word-level alignments as the yield of a node in the
parallel tree, the two nodes can be aligned.

\subsection{Wellformedness constraints}

Given a pair of word-aligned sentences and their corresponding parse
trees $S$ and $T$, represented as sets of constituent nodes, our \pfa\ node 
alignment algorithm produces a collection of aligned node-pairs $(S_i,T_j)$.
The underlying assumptions of compositionality in meaning and word-level 
alignments being indicative of translation equivalence lead directly to
the following node alignment wellformedness criteria:
\begin{enumerate}
\item If a node $S_i$ is linked to a node $T_j$, then any node within the 
subtree of node $S_i$ can only be linked to nodes within the subtree of node 
$T_j$.
\item If a node $S_i$ is linked to a node $T_j$, then any node that dominates 
the node $S_i$ can only be linked to nodes that dominate the node $T_j$.
\item If a node $S_i$ is linked to a node $T_j$, then the word alignments of
the yields of the two constituents must satisfy the following:
\begin{enumerate}
\item Every word in the yield of the node $S_i$ must be aligned to one or more 
words in the yield of the node $T_j$, or it should be unaligned.
\item Every word in the yield of the node $T_j$ must be aligned to one or more 
words in the yield of the node $S_i$, or it should be unaligned.
\item There should be at least one alignment between the yields of nodes $S_i$ 
and $T_j$. Thus, the words in the yields can not all be unaligned.
\end{enumerate}
\end{enumerate}

\subsection{Arithmetic Representation}

Our \pfa\ algorithm uses a arithmetic mapping that elegently carries over the
constraints characterized by the wellformedness constraints elaborated above.
This mapping is designed to ensure that each aligned word, which carries a
distinct ``piece of meaning'' can be uniquely identified, and also inherently
reflects the compositional properties of constituent translation equivalence.
This is accomplished by assigning numerical values to the nodes of the two
parse trees being aligned, in a bottom-up fashion, starting from the leaf
nodes of the trees.  Leaf nodes that correspond to words that are aligned are
each assigned a unique prime number.  Unaligned leaf nodes are assigned a
value of ``1''.  Constituent nodes in the parse trees are then assigned a 
value that is the product of all its sub-constituent nodes.  Because of the
arithmetic property that any composite number can be uniquely factored into
primes, it should be evident that the value of every constituent node uniquely
identifies the aligned words that are covered by its yield.  Consequently, by
assigning {\em the same} prime values to the aligned words of both trees,
retrieving aligned constituent nodes is as simple as finding the set of nodes
in the two trees that carry the same numerical value.  Note that by assigning
values of ``1'' to unaligned words, these unaligned words do not influence the
numerical values assigned to constituent nodes, thus reflecting their
treatment as ``don't cares'' with respect to the translation equivalence of
constituent nodes.
 
%Assuming that natural language is infinite, there could be infinite sentences,
%and thus infinite possible `meanings' conveyed in text. In our approach, we
%have mapped all these meanings onto the set of natural numbers. One number
%represents one meaning.
%
%Number theory classifies the set of natural numbers into \{unity, primes, and
%composites\}. Because each number carries a meaning, we have the following:
%\begin{enumerate}
%\item Prime Numbers: They represent a unique meaning. In a particular context,
%the word `house' could mean just one thing. That meaning would be captured by
%a prime number.
%\item Composite Numbers: They can be written as the product of prime
%numbers. A composite number represents the composite meaning of the meaning of
%its prime factors. Thus, a number that represents the phrase `blue house'
%would be represented by a number that is a product of the numbers assigned to
%`blue' and to `house'.
%\item Unity: A number does not change when multiplied with unity. Hence, the
%number $1$ represents a ``don't care'' meaning.
%\end{enumerate}
%
%In a parse tree, the yields of all nodes are different texts. Thus, each node
%can be supposed to carry a different meaning. Since we can represent meaning
%as a number, we can store that number in the node.

\begin{figure*}[t]
\centering
\includegraphics[width=6.5in]{images/phrases.jpg}
\caption{Node-Aligned Parallel Sentences}
\label{fig:tree}
\end{figure*}

\subsection{Description of the \pfa\ Algorithm}

The \pfa\ algorithm uses the concept of `composite meaning as prime
factorization', and hence the name (Prime Factorization and Alignments). 
% The principal idea of the algorithm can be summarized in three points:
% \begin{enumerate}
% \item If we have a node in the tree $P \rightarrow C_1 C_2 \ldots C_k$, then
% we assume that the meaning captured by the node $P$ is the composite meaning
% that is captured by its children. Thus, the value that node $P$ would get
% would be the product of values of its child nodes.
% \item Leaf nodes can be assumed to carry unique meaning, hence they would be
% assigned distinct prime numbers, based on the word stored at the leaf.
% \item Consider that a node $S_i$ in the source tree gets the same value as 
% the node $T_j$ in the target tree. We have defined that every number carries 
% a distinct meaning of its own. Since the values are same, the yields of the 
% two nodes must be translation equivalents of each other, and hence the nodes 
% must be aligned. (Sometimes, the parse trees contain unit productions. In 
% that case, the values of both the nodes in that production come out to be 
% the same, and for purposes of alignment, we break the tie by taking the node 
% closer to the bottom of the tree.)
% \end{enumerate} 
The algorithm assigns values to the leaf nodes, propogates the values up the
tree, and then compares the node values across the trees to align the
nodes. As described above, leaf nodes which have word alignments are assigned
unique prime numbers, and the same prime is assigned to the corresponding
aligned words in the parallel sentences.
% To assign the values to the leaf nodes, we take the help of
% word-alignment information. Earlier, we stated the assumption that two 
% aligned words are said to carry the same meaning. Thus, those two words 
% would be represented by the same prime number. In general, we would use as 
% many distinct prime numbers as the number of alignments. Leaves representing
% aligned words would be assigned the prime number corresponding to that
% alignment. 
% There are two exceptions to the above.  
Leaf nodes corresponding to unaligned words are assigned the value ``1''.
% which
% treats them as ``don't cares'' for the purpose of translation equivalence.
The treatment of ``one-to-many'' word alignments is a special case.  Such
alignments are considered to carry the same meaning, and should thus be
assigned the same value.  To accomplish this, if a single word is aligned to
multiple words in the other language, we assign the same prime number to all
words on the ``multiple'' side, and assign the product of these to the single
word equivalent.

Another special case is when the parse trees contain unary productions.
In this case, the values of both nodes involved in this production are the 
same. Our node alignment algorithm breaks this ``tie'' by selecting the node
that is ``lower'' in the tree (the daughter node of the unary production).
A similar situation with two nodes being assigned identical values can arise
when one or more unaligned words are attached directly to the parent node.
Here too, our algorithm aligns the ``lower'' node and leaves the ``higher''
node unaligned.  These decisions reflect our desire to be conservative with
respect to such ambiguous cases, and their implications on the notion of
translational equivalence.  This also provides some robustness against noisy 
alignments.

% Algorithm~\ref{algo:pfa} is an abstract description of our implementation of
% the \pfa\ approach.  Our implementation is in C++.  One minor issue that came
% up when dealing with products of prime numbers is that for large trees, the
% value of the root node becomes a large product, and can no longer be stored 
% as
% a built-in C data type. Using the GMP library solved this problem.

% \newcommand{\Value}{\hbox{Value}}
% \begin{algorithm}[t]
% \begin{small}
%	\caption{\pfa\ Algorithm for Node-Alignment}
%	\label{algo:pfa}
%	\begin{algorithmic}[1]
%		\REQUIRE Source-Tree, Target-Tree,\\ Word-Alignments
%		\medskip
%		\FORALL{nodes $n$ in source, target trees}
%			\STATE $\Value(n) \leftarrow 1$
%		\ENDFOR
%		\STATE Initialize Prime-number generator with $2$.
%		\FORALL{$A$ in Word-Alignments}
%			\STATE $\Value(A) \leftarrow $ next prime number.
%			\FORALL{word $w$ that alignment $A$ refers to}
%				\STATE $L \leftarrow$ Leaf node corresponding to $w$. 
%				\STATE $\Value(L) \leftarrow \Value(L) * \Value(A)$.
%			\ENDFOR
%		\ENDFOR
%		\FORALL{node $n$ in source tree, traversed bottom up}
%			\STATE $\Value(n) \leftarrow \prod{\Value(Child(n))}$.
%		\ENDFOR
%		\FORALL{node $n$ in target tree, traversed bottom up}
%			\STATE $\Value(n) \leftarrow \prod{\Value(Child(n))}$.
%		\ENDFOR
%		\STATE Find unaligned nodes $n$ in source tree and $m$ in target tree with matching values, but not the value $1$. If multiple nodes in the same tree have the same value, choose the node closer to the bottom of the tree. Align the node $n$ to node $m$. Repeat this step.
%	\end{algorithmic}
%\end{small}
%\end{algorithm}

It is straightfoward to verify that the \pfa\ algorithm satisfies the
wellformedness constraints described above. Also, since multiplication is
commutative, the algorithm is not effected by differing word orders within
parallel constituent structures. 

% Unaligned words act as ``don't cares'', unaligned words (such as determiners)
% are incorporated into their governing aligned constituents, reflecting 
% closest translation equivalence between the given sentences. We said that in 
% case of a tie between values of two nodes, we choose the node closer to the
% bottom. Earlier, we claimed that this happens in case of unit
% productions. However, this could also happen if there was a set of unaligned
% words attached directly to the top-node, which is why its value was the same
% as the bottom-node. In that case, we do not align the top node, thereby 
% making the system robust against noisy alignments.

The \pfa\ algorithm run on a sample Chinese-English parallel sentence is shown
in Figure~\ref{fig:tree}. The value of each node as shown as a part of its
label. The aligned nodes are marked by shapes. A triangle aligns to a
triangle, and squares to squares.

\section{Syntax-based Sub-sentential Phrase Extraction}

The alignment of nodes as described in the previous section allows us to build
a comprehensive syntax-based phrase-to-phrase translation lexicon from a
parallel corpus.  
% The criteria we use for establishing constituent node
% alignments were designed such that the yields of these nodes form
% sub-sentential translation equivalents.  
To build a syntax-based ``phrase table'', we simply extract all aligned
constituent nodes along with their yields and enter them into a database,
while accumulating frequency counts.  In addition to the source-to-target
phrase correspondences, we record the constituent labels of the aligned
constituent nodes on both the source and target sides (which may be
different).  These labels ``connect'' the phrases with synatactic transfer 
rules during decoding.
% We could add an entry
% to our lexicon, where $y_1$ maps onto $y_2$. The syntactic category of the
% source-phrase would be the label on the node $S$, and similarly the category
% of the target-phrase would be the label on the node $T$. By considering all
% aligned pairs generated from a parallel corpus, we can extract many such
% entries for our lexicon.
The set of phrases extracted from the example sentence in
Figure~\ref{fig:tree} is shown in Figure~\ref{fig:phrases}.

\begin{figure}[t]
\centering
\includegraphics[width=3in]{images/phrases-table.jpg}
\caption{Phrases extracted from Aligned Nodes}
\label{fig:phrases}
\end{figure}

The process of building syntax-based ``phrase tables'' from large corpora of
sentence-parallel data is quite similar to the corresponding process in
phrase-based SMT systems. Our phrase correspondences, however, only reflect
contiguous and complete constituent correspondences.
% In PB-SMT, the process involves word alignment,
% followed by heuristic phrase alignment and extraction.  In our approach, we
% start with a parsed parallel corpus, perform word alignment, and then apply
% the \pfa\ approach to the parse trees for syntax-based phrase alignment and
% extraction.  
We also note that the extracted phrase tables in both approaches can be
modeled statistically in similar ways.  Similar to common practice in PB-SMT,
we currently use the frequency counts of the phrases to calculate relative
likelihood estimates and use these as features in our Stat-XFER decoder.  
%We are considering using more sophisticated scoring strategies in future work.

\section{Evaluation of the \pfa\ algorithm}
The accuracy of our node alignment algorithm depends on both the quality of
the word alignments as well as the accuracy of the parse trees.  We performed
several experiments to assess the effects of these underlying resources on the
accuracy of our approach.  
% Our goal was to assess node alignment accuracy as
% reflected by the quality of the resulting syntactic phrases under different
% conditions.  
The most accurate condition is when the parallel sentences are manually
word-aligned, and when verified correct parse trees are available for both
source and target sentences.  Performance is expected to degrade when word
alignments are produced using automatic methods, and when correct parse trees
are replaced with automatic parser output.  In these experiments, we used a
manually word-aligned parallel Chinese-English TreeBank consisting of 3342
parallel sentences.

% We evaluated the performance of the \pfa\ algorithm under
% several different settings. The description of the experiments and the 
% results
% obtained are given below. In these results, we are reporting the Precision,
% Recall, F-1 and F-0.5 scores.

\subsection{Manual Constituent Node Alignments}

We first investigated the accuracy of our approach under the most accurate
condition.  We sampled 30 sentences from the Chinese-English treebank corpus.
A bilingual expert from our group then manually aligned the nodes in these
trees.  These node alignments were then used as a ``gold standard''.  We then
used the accurate parse trees and the manually created word alignments for
these sentence pairs, and ran the \pfa\ node algorithm, and compared the
resulting node alignments with the gold standard alignments.  The Precision,
Recall, F-1 and F-0.5 results are reported in Table~\ref{tab:eval-manual}.

\begin{table}[t]
\centering
\begin{tabular}{|c|c|c|c|}
\hline
Precision & Recall & F-1 & F-0.5 \\\hline
0.8129 & 0.7325 & 0.7705 & 0.7841 \\\hline
\end{tabular}
\caption{Accuracy of \pfa\ Node Alignments against Manual Node Alignments}
\label{tab:eval-manual}
\end{table}

We manually inspected cases where there was a mismatch between the manual and
automatic node alignments, and found several trends.  Many of the alignment
differences were the result of one-to-many or many-to-many word alignemnts.
%In most of these cases, the differences were quite minor.  
For example, in
some cases a verb in Chinese was word-aligned to an auxiliary and a head verb
on the english side (e.g. {\tt have} and {\tt put}).  The \pfa\ algorithm in
this case node-aligns the {\tt VP} that governs the Chinese verb to the {\tt
VP} that contains both auxiliary and head verbs on the English side.  The gold
standard human alignments, however, in some cases, aligned the {\tt VP} of the
Chinese verb to the English {\tt VP} that governs just the main verb.  Other
mismatches were attributed to errors or inconsistencies in the manual word
alignment and to the treatment of traces and fillers in the parse trees.

% \begin{itemize}
% \item One chinese word aligns to more than one english word. In some 
% examples,
% one chinese verb was word-aligned to both the auxiliary and head verb on the
% english side (e.g. have and put). In this case, the algorithm assumes that 
% the
% meaning of the chinese word is incomplete without the presence of the
% auxiliary, thus aligns only the VP that contains both verbs on the english
% side. Human alignments however use more relaxed alignment, and arguably, the
% same chinese word could mean just the head verb, thus the alignment may or 
% may
% not include the auxiliary as its constituent on the English side.
% \item The word alignments for the treebank are very dense. A chinese word 
% that
% could mean just `the entire region' is aligned to `in the entire
% region'. Thus, the algorithm makes an alignment from the chinese side to a PP
% on the english side. Human aligments tend to leave out the preposition, 
% making
% an alignment to an NP on the english side.
% \item The treebank has traces and fillers. The automatic alignments prefer
% exclusion of traces. Human alignments preferred inclusion of traces in the
% alignments.
% \end{itemize}

% We consider that these differences in alignments are not all errors, but
% mostly disagreement on what nodes to prefer alignments for. Hence, we believe
% that the precision and recall of the algorithm are much higher than what is
% reflected in Table~\ref{tab:eval-manual}

\subsection{Effect of Using Automatic Word Alignments}
We next tested how sensitive the \pfa\ algorithm is to errors in automatic
word alignment.  We use the entire 3342 sentences in the parallel treebank for
this experiment.  We first ran the algorithm with the correct parse trees and
manual word-alignments as input.  We use the resulting node alignments as the
gold standard in this case.  We then used GIZA++ to get bidirectional word
alignments, and combined them using various strategies.  In this scenario, the
trees are high-quality (from the treebank), but the alignments are noisy. The
results obtained are shown in Table~\ref{tab:eval-mtree}.  Unsurprisingly, the
``Union'' combination method has the best precision but worst recall, while
the ``Intersection'' combination method has the best recall but worst
precision.  The four other methods for combining word alignments fall in
between.  Three of the four (all except ``grow-diag-final'') behave quite
similarly.  We generally believe that precision is somewhat more important
than recall for this task, and have thus used the ``sym2'' method \cite{thot}
(which has the best F-0.5 score) for our translation experiments.

% Since we were using the node
% alignment for generating phrase table, we wanted them to be as precise as
% possible, and used the F-0.5 measure to select which of the Viterbi
% combination strategies to use. The sym2 combination, as implemented in the
% Thot toolkit\cite{thot} gave us the best results.
\begin{table}[t]
\centering
\begin{footnotesize}
\begin{tabular}{|l|c|c|c|c|}
\hline
Comb Method & Prec & Rec & F-1 & F-0.5 \\\hline
Intersection & 0.6382 & 0.5395 & 0.5846 & 0.6014 \\\hline
Union & 0.8114 & 0.2915 & 0.4288 & 0.5087 \\\hline
Sym1 & 0.7142 & 0.4534 & 0.5546 & 0.5992 \\\hline
Sym2 & 0.7135 & 0.4631 & 0.5616 & 0.6045 \\\hline
Grow-Diag-Final & 0.7777 & 0.3462 & 0.4790 & 0.5493 \\\hline
Grw-Diag-Fin-And & 0.6988 & 0.4700 & 0.5619 & 0.6011 \\\hline
\end{tabular}\
\end{footnotesize}
\caption{Manual Trees, Automatic Node Alignments}
\label{tab:eval-mtree}
\end{table}

\subsection{Effect of Using Automatic Parses}
We evaluated the effect of parsing errors (as reflected in automatically derived parse trees)
on the quality of the node alignments. We parsed the treebank corpus on both English and Chinese 
using the Stanford parser, and extracted phrases using manual word alignments. Compared to 
the phrases extracted from the manual trees, we obtained a precision of $0.8749$, and a recall of
$0.7227$, that is, an F-0.5 measure of $0.8174$. 
We then evaluated the most `noisy' condition that involves both automatic word alignments 
and automatic parse trees. We evaluated the phrase extraction with different Viterbi combination 
strategies. The `sym2' combination gave the best results, with a precision of $0.6251$, 
recall of $0.3566$, thus an F-0.5 measure of $0.4996$.

%We also plan to test the effect of parsing errors (as reflected in
%automatically derived parse trees) on the quality of our node alignments.  We
%will also evaluate the most ``noisy'' condition that involves both automatic
%word alignments and automatic parse trees.  These experiments are still in
%progress and will be reported in the final version of the paper.

% Since the treebank corpus is quite limited in size, and we wanted to learn 
% the
% syntactic phrase table from as much data as possible, we evaluated how much
% the node alignments change when we use automatic parses. Evaluating the
% precision and recall of `node alignments' is difficult in this case, since 
% the
% tree structures of manual and automatic parses are very different.  To 
% evaluate
% the performance of the algorithm, we extracted the phrase tables from both 
% the
% `manual-tree node alignments' and the `automatic-tree node alignments', and
% calculated the precision and recall of the extracted phrases. The gold
% standard here is the automatic node alignments of the treebank trees with
% manual trees and manual word alignments. The results are shown in
% Table~\ref{tab:eval-atree}

% \begin{table}[ht]
% \centering
% \begin{tabular}{|c|c|c|c|c|}
% \hline
% Viterbi Combination Strategy & Precision & Recall & F-1 & F-0.5 \\\hline
% Intersection & 0.4696 & 0.0380 & 0.0701 & 0.0978 \\\hline
% Union & 0.6451 & 0.0220 & 0.0422 & 0.0612 \\\hline
% Sym1 & 0.5579 & 0.0331 & 0.0622 & 0.0884 \\\hline
% Sym2 & 0.5594 & 0.0340 & 0.0640 & 0.0908 \\\hline
% Grow-Diag-Final & 0.6226 & 0.0260 & 0.0496 & 0.0714 \\\hline
% Grow-Diag-Final-And & 0.5466 & 0.0345 & 0.0647 & 0.0916 \\\hline
% \end{tabular}
% \caption{Automatic Trees, Automatic Node Alignments}
% \label{tab:eval-atree}
% \end{table}

% The low recall numbers here are not surprising. The manual trees differ from
% the automatic parses quite greatly, thus causing nodes to have different
% yields. Bilingual chinese speakers looked at the produced phrase table from
% the sym-2 algorithm with automatic parses, and asserted that the phrase
% alignments are reasonably precise.


\section{Synchronous Tree Fragment and CFG Rule Extraction}

\subsection{Related Work}

% There has been an increasing interest in recent years in methods that
% incorporate syntax and syntactic knowledge into MT.  
Syntax-based reordering rules can be used as a pre-processing step for PB-SMT
(and other approaches), to decrease the word-order and syntactic distortion
between the source and target languages \cite{xiamccord2004}. A variety of
hierarchical and syntax-based models, which are applied during decoding, have
also been developed.  Many of these approaches involve automatic learning and
extraction of the underlying syntax-based rules from data.  The underlying
formalisms used has been quite broad and include simple formalisms such as
ITGs \cite{dekaiwu_sitg}, hierarchical synchronous rules \cite{chiang:2005},
string to tree models by \cite{galley04} and \cite{galley06}, synchronous CFG
models such \cite{xiamccord2004} \cite{yamadaknight01}, synchronous Lexical
Functional Grammar inspired approaches \cite{kathrinprobst} and others.
% For more
% details on the formalisms and approaches, readers are encouraged to refer
% \cite{ahmedhanneman06}.  

Most of the previous approaches for acquiring syntactic transfer or reordering
rules from parallel corpora use syntactic information from only one side of
the parallel corpus, typically the target side.  
% By using word alignment
% information, corresponding syntactic structures for the other language
% (i.e. the source side) can be inferred, and reordering rules can then be
% extracted.  
\cite{away-DOT} describes an approach that uses syntactic information from the
source side to derive reordering subtrees, which can then be used within a
``data-oriented translation'' (DOT) MT system, similar in framework to
\cite{poutsma-DOT}.  Our work is different from the above in that we use
syntactic trees for both source and target sides to infer constituent node
alignments, from which we then learn synchronous trees and rules.  Our process
of extraction of rules as synchronous trees and then converting them to
synchronous CFG rules is most similar to that of \cite{galley04}.

%We use syntactic information from both the languages in the
% form of syntactic parses, and extract much precise rules at the cost of some
% recall.

\subsection{Synchronous Tree Fragment Pair Extraction}

The main concept underlying our syntactic rule extraction process is that we
treat the node alignments discovered by the \pfa\ algorithm (described in
previous sections) as synchronous tree decomposition points.  This reflects
the fact that these nodes denote points in the synchronous parse trees where
translation correspondences can be put together compositionally.  Using the
aligned nodes as decomposition points, we break apart the synchronous trees
into collections of minimal synchronous tree fragments.  Finally, the
synchronous fragments are also converted into synchronous context-free rules.
These are then collected into a database of synchronous rules.  
% The collected
% rule database can be modeled statistically, and can be used within a variety
% of syntax-based MT approaches.

The input to our rule extraction process consists of the parallel parse trees
along with their node alignment information.  The constituent nodes in the
parallel trees that were aligned by the \pfa\ node alignment algorithm are
treated as tree decomposition points.  At each such decomposition point,
spliting the two parallel trees results in two partial trees or tree
fragments.  One synchronous pair consists of the subtrees that are headed by
the aligned nodes where the decomposition took place.  Since the subtrees are
rooted at aligned nodes, their yields are translation equivalents of each
other.  The other synchronous tree fragment pair consists of the remaining
portions of the trees.  The translation equivalence of the complete tree (or
subtree) prior to decomposition implies that these tree fragments (which
exclude the detached subtrees) also correspond to translation equivalents.
% This property is similar to the general 'inside-outside' division of
% monolingual context-free parse trees, but is applied in the synchronous case
% only to nodes where translation equivalence across the two parse trees has
% been established via the node alignment process.  
The tree fragments that are obtained by decomposing the synchronous trees in
this fashion are similar to the Synchronous Tree Insertion Grammar of
\cite{synchronoustag1990}.

We developed a tree traversal algorithm that decomposes parallel trees into
all minimal tree fragments.  Given two synchronous trees and their node
alignment decomposition information, our tree fragment extraction algorithm
operates by an ``in-order'' traversal of the trees top down, starting from the
root nodes. The traversal can be guided by either the source or target parse
tree.  Each node in the tree that is marked as an aligned node triggers a
decomposition.  The subtree that is rooted at this node is removed from the
currently traversed tree.  A copy of the removed subtree is then recursively
processed for top-down decomposition.  If the current tree node being explored
is not an aligned node (and thus is not a decomposition point), the traversal
continues down the tree, possibly all the way to the leaves of the tree.
Decomposition is performed on the corresponding parallel tree at the same
time.  We apply this process on all the aligned constituent nodes
(decomposition points) to obtain all possible decomposed synchronous tree
fragment pairs from the original parallel parse trees.  This results in a
collection of all minimal synchronous subtree fragments.  These synchronous
subtree fragments are minimal in the sense that they do not contain any
internal aligned nodes.
% Since we restrict going beyond a decomposition point in every traversal, we 
% obtain minimal sub-tree fragment pairs that explain both the trees.  
Another property of the synchronous subtree fragments is that their frontier
nodes 
% (the nodes that form the yield of the subtree fragment) 
are either aligned nodes from the original tree or leaf nodes (corresponding
to lexical items).
%Work elsewhere \cite{galley04} has discussed the transduction of 
% comprehensive set of 
%composite rules by composing these minimal sub-tree fragments obtained. 
Figure~\ref{fig:treepairs1} shows some sample tree fragment pairs that were
obtained from the example discussed earlier in Figure~\ref{fig:tree}.
\begin{figure}[t]
\centering
\includegraphics[width=3in]{images/treepairs.jpg}
\caption{Tree Fragment Pairs Extracted from Aligned Nodes}
\label{fig:treepairs1}
\end{figure}

\subsection{Synchronous Transfer Rule Creation}

In the last step, we convert the synchronous tree fragment pairs obtained as
described above into synchronous context-free rules.  This creates rules in a
format that is compatible with the Stat-XFER formalism that was described in
Section~1.  Our system currently does not use the internal tree structure
information that is contained in the synchronous tree fragments.  Therefore,
only the syntactic category labels of the roots of the tree fragments, and the
nodes on the fragment frontier are relevant to decoding.  This in essense
corresponds to a ``flattening'' of the synchronous tree fragment into a
synchronous context free style rule.

The flattening of the tree fragments is accomplished by an ``in-order''
traversal on each of the tree fragments to produce a string representation.
Frontier nodes in the fragment are either labeled constituent nodes or leaf
nodes of the original parse tree.  These form the right-hand sides of the
flattened rule.  The positions of the constituent nodes in the output string
are numbered to keep track of alignment of the nodes, which is often
non-monotonic due to reordering between the source and target languages.
Finally the root constituent label of the source tree fragment becomes the
source-side parent category of the rule, while the root label of the target
tree fragment becomes the target side parent category.

% Our approach to learning synchronous transfer rules has been to focus on
% obtaining high-precision rules that are as general as possible.  
Accurate automatic transfer rule learning requires accurate word alignments
and parse structures.  Thus, to favor high precision (at the expense of some
loss of recall), in our work to date on Chinese and other languages, while we
extract syntactic phrases from all available parallel data, we extract rules
only from manually word-aligned parsed parallel data.  To compensate for the
limited amount of data, we generalize the rules as much as possible.  Elements
in the rules that originate from leaf nodes in the parse trees are generalized
to their part-of-speech categories, if the corresponding words were one-to-one
aligned in the parallel sentences.  Unaligned words and words that are part of
one-to-many alignments are not generalized to the POS level and remain
lexicalized in the final rule.

%We currently use relative likelihood scores to ``score'' both rules and syntactic phrases.  
The phrase table extracted from the corpus and the rules
are scored together to ensure that they are consistent when used in our
translation system.  
%We use the relative frequency estimates of the rule,conditioned on either the source side or target side of the synchronous rule. 
% Other possible
% scoring features include the symmetric score obtained by conditiong on the
% 'target side' of the synchronous rule, as well as other variations of
% conditioning on the parent type etc.  
For all Stat-XFER experiments to date, we have used just the source side
conditionig with a constant smoothing factor for robustness to noise. 
%We will be experimenting with other mechanisms for scoring in future. 
% The rule scores are calculated as below:
% \begin{equation}
% P(rule) = \frac{count(stype,ttype,s,t)} { count(s) + k } 
% \end{equation}
\section{Extraction Applied to Chinese-English Parallel Data}

We used the pipeline of \pfa\ node alignment followed by rule extraction to
build resources for a Stat-XFER Chinese-to-English MT system.  The
syntax-based phrase table was constructed from two large parallel corpora
released by LDC for the DARPA/GALE program.  The parallel sentences for both
English and Chinese were parsed using the Stanford parser.  The first corpus
consists of about 1.2 million sentence pairs.  Our extraction process applied
to this corpus resulted in a syntax-based phrase table of about 9.2 million
entries.  The other data source used was a parallel corpus of about 2.6
million sentences, but many of its entries were from a Chinese-English
lexicon.  From this corpus, we extracted 8.75 million phrases.

Rule learning was performed on a 10K-sentence parallel corpus that was
manually word-aligned, released by LDC for the DARPA/GALE program.  This
manually word-aligned corpus includes the parallel Chinese-English treebank of
3,343 sentence pairs.  The treebank sentences come with verified correct parse
trees for English and Chinese.  The rest of the 10K corpus was parsed by the
Stanford parser.
% as part of the LDC English Chinese parallel tree bank. About
% 3K sentences from the corpus had manual alignments and manual parsed trees,
% which was quite ideal for our rule learning process. We also used another 6K
% of the corpus which had manual alignments but automatically parsed
% trees. Finally we also used about 1K corpus which was automatically parsed 
% and manually aligned by a bilingual speaker. 
The complete 10K parallel corpus was node aligned and rules were extracted as described in Section~5.
%Tree fragments were then extracted and flattened out to form synchronous rules.  
Figure~\ref{fig:treepairs1} shows two synchronous tree fragments that
were extracted from the example node-aligned sentence pair in
Figure~\ref{fig:tree}.  After generalization and flattening, we obtain rules
such as those shown in Figure~\ref{fig:treepairs2}.  The above process
resulted in a collection of almost 100K rules.  Some statistics on this rule
set are shown in Table~\ref{fig:rules}.  Analysis of this rule set indicates
that only about 4\% of these rules were observed more than once in the data.
These include the most general and useful rules for mapping Chinese syntactic
structures to their corresponding English structures.  Most of the
``singleton'' rules are highly lexicalized.  A large portion of the singleton
rules are noisy rules, but many of them are good and useful rules.
Experiments indicate that removing all singleton rules hurts translation
performance.

\begin{figure}[t]
\centering
\includegraphics[width=3in]{images/rules.jpg}
\caption{Rules Extracted from Tree Pairs}
\label{fig:treepairs2}
\end{figure}

\begin{table}[t]
\centering
\includegraphics[width=3in]{images/rulestats.jpg}
\caption{Statistics for Chinese-English Rules}
\label{fig:rules}
\end{table}

\section{Conclusions}

The process described in this paper provides a fully automated solution for
extracting large collection of reliable syntax-based phrase tables and
syntactic synchronous transfer rules from large volumes of parsed parallel
corpora.  In conjunction with the Stat-XFER syntax-based framework, this
provides a fully automated solution for building syntax-based MT systems.
The current performance of this approach still lags behind state-of-the-art
phrase-based systems when trained on the same parallel data but is showing
encouraging improvements.  Furthermore, the resources extracted by our 
process can be used by various other syntax-based MT approaches.

% \textbf{?}
%
%\todo

\bibliography{acl08,rules}
%\bibliographystyle{alpha}
\bibliographystyle{acl}


\end{document}
