%******************************************************************************
%*    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}{TRUE} % 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 Sentences}

\ifthenelse{\equal{\anonymous}{TRUE}}
{}
{
\author{Alon Lavie \\
  {\tt alavie@cs.cmu.edu} 
  Language Technologies Institute \\
  Carnegie Mellon University \\
  Pittsburgh, PA 15213, USA\\ \And
  Alok Parlikar \\
  {\tt aup@cs.cmu.edu} 
  Language Technologies Institute \\
  Carnegie Mellon University \\
  Pittsburgh, PA 15213, USA\\ \And
  Vamshi Ambati \\
  {\tt vambati@cs.cmu.edu} \\
  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 (which are assumed to be translation equivalents).  The sentence pairs are assumed to be annotated with phrase-structure parse trees, and with word alignments representing translation equivalence at the word-level between the sentences.  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.  Parse trees nodes are aligned if their constituent yields are likely translation equivalents of each other. In the second step, we extract all aligned sub-sentence syntactic constituents from the parallel sentences, and create a syntax-based phrase-table.  In the third and final step, we treat the node alignments as tree decomposition points and extract from the corpus all possible synchronous parallel subtrees.  The synchronous parallel subtrees are also converted into synchronous context-free rules.  The extracted syntax-based phrase tables and translation rules can then be used as resources for constructing broad-coverage syntax-based Machine Translation systems between the two languages.  We apply the approach and evaluate it on both a small manually word-aligned Chinese-English parallel treebank, and on large scale automatically derived Chinese-English parallel corpora.

\end{abstract}

\section{Introduction}
  \textbf{Alon}

\todo

\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}
Given a pair of parallel sentences, and their corresponding parse trees, our goal is to extract contiguous pieces of text that are translation equivalents of each other. Also, we require that these ``phrases'' should belong to constituent structures in their parse trees. In short, we are looking to find a pair of nodes between the source and target trees whose yields carry the same meaning. 

For the purpose of extracting constituent structures with like meaning, we use the word-alignment information of the underlying sentences. The assumption here is that if two words are aligned to each other, they carry the same meaning. In practice however, we know that automatically obtained word alignments are rather noisy. Hence, the algorithm should be robust to deal with such noisy word alignments. 

\subsection{Related Work}
Aligning nodes in parallel trees and extraction of phrasal lexicons has been done by Samuelsson et al.\cite{stockholm-treealigner}. Their approach involves manual alignment of the nodes in the tree. The manual approach is very well suited for generating very reliable treebanks, however automatic methods of aligning nodes and extracting lexicons are useful in accumulating resources from large parallel data.

Tinsley et al.\cite{tinsley-robust} have used statistical lexicons to align nodes between parallel trees. In our approach, we use word alignment information, which is more reliable than just a statistical lexicon\cite{wordalignment-reliable}.

Groves et al.\cite{groves-robust} have suggested a method of aligning nodes between parallel trees automatically, based on word alignments. Along with the word alignment information, they also use information of the labels of nodes in the trees, and the general structure of the tree. Our approach is different in the sense that we only look at the word alignments, thereby making the system robust to using any parser, even different parsers on different language pairs. However, in general terms, this approach is the closest to our approach. 


\subsection{Wellformedness constraints}
The \pfa\ node alignment algorithm produces as output node-pairs $(S_i,T_j)$. Each of this pair tells us which node in the source tree was aligned to which node in the target tree. The alignments are required to satisfy these wellformedness criteria:
\begin{itemize}
\item If a node $S_i$ is linked to a node $T_j$, then any node in the sub-tree of node $S_i$ can  be linked only to nodes in 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  be linked only to nodes that dominate the node $T_j$.
\item If a node $S_i$ is linked to a node $T_j$, then the following must hold good for the word-alignments of the underlying sentences:
	\begin{itemize}
	\item Every word in the yield of the node $S_i$ should either 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$ should either 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{itemize}
\end{itemize}

\subsection{Unaligned Words and Contiguity}
If we consider a phrase in one language, and its translation equivalent in another language, we often find that there are a few unaligned words. One common example is: some languages use determiners, while others don't. In cases like this, we could have a pair of constituents between parallel trees that contain unaligned words, but still carry the same meaning. The \pfa\ node-alignment algorithm allows for such ``extra words'' 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. The node-alignment algorithm should be robust to different word orders. As long as one piece of contiguous text dominated by a node carries the same meaning as the yield of a node in the parallel tree, the two nodes must be aligned. The \pfa\ algorithm satisfies this property.

\subsection{Mathematics and Meaning}
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. 

\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 \pfa\ algorithm thus assigns values to the leaf nodes, propogates the values up the tree, and finally compares the values across trees to align the nodes. 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 consider:
\begin{enumerate}
\item Leaf nodes corresponding to unaligned words are assigned the value $1$, and these words are considered to be ``don't cares'' of meaning.
\item There could be one-to-many word alignments. Each of these alignments is considered to carry the same meaning, and is assigned the same value. However, if a word has two alignments, the alignment is simply considered to be taken twice, and thus the corresponding leaf node would store the square of the alignment's prime value.
\end{enumerate}

Algorithm~\ref{algo:pfa} describes a way to implement the \pfa\ strategy. We implemented the algorithm in C++, and one small 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}[h!]
	\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{algorithm}

It can be verified that the \pfa\ algorithm satisfies the wellformedness constraints. Also, since the product of numbers is commutative, the algorithm is robust to differing word orders within parallel constituent structures. Since unaligned words act as don't cares, the system allows for extra words (such as determiners) to be included in the constituent phrase, thereby finding the 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. 

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


\section{Syntax-based Sub-sentential Phrase Extraction}
The alignment of nodes as described in the previous section allows us to build a comprehensive phrasal lexicon out of the parallel corpus. As previously described, nodes are aligned only if the meaning that the carry under them in the trees is nearly identical. Clearly, if two nodes $S$ and $T$ are aligned to each other, the yield $y_1$ of node $S$ must be same in meaning as the yield $y_2$ of node $T$. 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 sentence from Figure~\ref{fig:tree} is shown in Figure~\ref{fig:phrases}.

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

The approach of building such a phrase table from large corpora of data is quite similar to the phrase tables traditionally built for phrase-based SMT methods. There, one starts with parallel corpus, aligns the words, extracts the phrase table and assigns scores to each phrase. In our approach too, we start with a parallel corpus, align the words, and then use the parse trees to extract a syntax based phrase table. In our initial experiments for using this phrase table in the Statistical Transfer-based decoder, we have na\"{i}vely used the relative frequency of the phrases as a scoring function. We are considering using more sophisticated scoring strategies in our upcoming experiments. 

\section{Evaluation of the \pfa\ algorithm}
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 Node-Alignments as Gold Standard}
We sampled 30 representative sentences from the Chinese-English treebank corpus. We then manually aligned the nodes in these trees. These node alignments were used as the gold standard. We used the manually created word-alignments for these sentence pairs, and ran the \pfa\ node algorithm, to get results as in Table~\ref{tab:eval-manual}.
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|}
\hline
Precision & 0.8129 \\\hline
Recall & 0.7325 \\\hline
F-1 & 0.7705 \\\hline
F-0.5 & 0.7841 \\\hline
\end{tabular}
\caption{Manual Node-Alignments as Gold Standard}
\label{tab:eval-manual}
\end{table}

We inspected cases where there was a mismatch between the manual and automatic alignments, and found examples like the following:
\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 Alignments}
We wanted to test how sensitive the algorithm is to noise in word alignments. As the gold standard, we ran the algorithm with the treebank corpus and manual word-alignments as input. The corpus that we used here has 3342 sentences. We 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}. 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}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline
Viterbi Combination Strategy & Precision & Recall & 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
Grow-Diag-Final-And & 0.6988 & 0.4700 & 0.5619 & 0.6011 \\\hline
\end{tabular}
\caption{Manual Trees, Automatic Node Alignments}
\label{tab:eval-mtree}
\end{table}

\subsection{Effect of Using Automatic Parses}
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 howmuch 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 Sub-tree and CFG Rule Extraction}

Synchronous reordering rules have been used to improve Machine Translation \cite{xiamccord2004,yamadaknight01}. Recent success
of syntactic and hierarchical machine translation systems have inspired the research in the 
automatic learning of transfer rules from corpus \cite{galley04} \cite{yamadaknight01}. 
While on one end we have grammar formalisms like ITG \cite{dekaiwu_sitg} that enforce a particular 
reordering constraint to induce reordering rules from corpus, some more syntactic formalisms like Lexical Functional Grammar have also been used \cite{kathrinprobst} \cite{xiamccord2004} \cite{yamadaknight01} . 
For more details on the formalisms and approaches, readers are encouraged to refer \cite{ahmedhanneman06}.
In almost all the approaches syntactic information is used on one side of the parallel corpus, typically the target side, in the form of a syntactic parsed tree. 
Then using word alignment information, a target side reordering rule is induced, that is typically
hierarchical in nature. 
Our work is different from the above in the sense that we use syntactic trees on both sides to 
learn synchronous transfer rules, directly applicable in MT. 
However the process of extraction of rules and flattening them as CFG style rules is similar 
in nature 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. 
\cite{dotway} also discuss using syntactic information on the source side,
but they use the extracted rules without flattening in their MT system, which is 
similar in framework to \cite{poutsma-DOT}. 

In this section we discuss our syntactic rule extraction process. We treat the node alignments extracted in the previous section as tree decomposition points and extract from the corpus all possible synchronous parallel subtrees.  The synchronous parallel subtrees are also converted into synchronous context-free rules. 

\subsection{Parallel sub-tree fragment pair extraction}
The input to the rule extraction is the parallel trees along with the node alignment information. 
A node in the source tree and its equivalent node on the target side syntax tree
as aligned by the node alignment algorithm forms a synchronous decomposition point. 
This means two things. At each such decomposition point if one splits both the trees then 
the sub-trees extracted for both languages will be equivalent in translation, and the 
remaining tree fragment with the detached node will also be equivalent in translation to its
counter part.
This should remind the reader of the visual similarity to an 'inside-outside' style division 
of the trees in a synchronous manner. The tree fragments thus obtained are 
similar in formalism to the Synchronous Tree Insertion Grammar \cite{synchronoustag1990}.

Given the synchronous decomposition information, our sub-tree fragment extraction algorithm proceeds
as follows. We start the extraction by traversing the source side tree, but it can equivalently 
be done starting with the target tree, depending upon the direction of interest.
Starting from the top node of the source tree we traverse in a top down fashion from the root 
to the leaves. For a source node $s$, we traverse the subtree below it 
% and in the process extract all the sub-tree fragments 
%along the synchronous decomposition points. 
only until we find all the immediately next decomposition point dominated by that node.
If the node in traversal is not a decomposition point, the traversal continues all the way 
to the leaves of the tree. 
The same is simultaneously performed on the target sub-tree rooted at $t$ that is the aligned node for $s$. 
The two tree fragments thus obtained form a synchronous sub-tree fragment pair, which will
later be used to as transfer rules. We perform this method on all the decomposition points 
to obtain all possible tree-fragments from the trees. 
Since we restrict going beyond a decomposition point in every traversal, we obtain 
minimal sub-tree fragment pairs that explain both the trees. 
It can also be seen that all the tree-fragment pairs either only contain non-terminal types 
corresponding to the node labels at the decomposition points or 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{trees} provides sample sub-tree fragment pairs that were obtained from the example
discussed in Figure~\ref{fig:tree}

\subsection{Synchronous Transfer Rule Creation}
The transfer rules are extracted from the synchronous sub-tree pairs rules extracted above. 
As can be seen from Section 2, the rule formalism as supported by our Statistical Transfer MT 
system requires Context Free Grammar style synchronous rules. We do not currently make use of the 
tree structure information on both sides of the rules and so 
Each of the extracted sub-tree pairs needs to be flattened into a synchronous context free style rule. 

The flattening of the sub-tree fragments is a 'in-order' traversal on each of the sub-tree fragments
 to produce a string representation. 
Each decompsition point in the sub-tree is output as its node label in the string.
Similarly each leaf of the sub-tree fragment is represented as a lexical item in the output string. 
The same is performed on the target side of the sub-tree fragment pair.
Also, node positions in the output string are numbered to keep track of alignment of the nodes,
which may not always be monotonic due to reordering in language pairs. 
Finally the parent label of the source sub-tree becomes the source side parent category of the rule 
and the parent label of the target sub-tree becomes the target side parent category. 

Our approach to learning synchronous transfer rules is to obtain precise rules that are generic
in nature. Automatic transfer rule learning requires accurate word alignments
and parse structures. We therefore only learn rules from controlled data with manual alignments. 
However, such data
is quite scarce and difficult to create. Therefore, in our rule learning process, we generalize as 
much as possible on top of the rules learnt. Apart from generalizing to the constituent level, 
we also generalize to part-of-speech category, any lexical item in the source side of the rule that is 
one-to-one aligned with a lexical item in the target side of the rule. Since in this scenario, 
we have access to the part-of-speech information of both source and target side, we retain the 
information in the process of generalization. Any lexical item, that is unaligned is retained as lexicalized in the final rule. 

The phrase table extracted from the corpus and the rules are scored together to be consistent 
before they are used in our translation system.  
We use relative frequency estimates of the rule, conditioned on the 'source side' of the 
synchronous rule. We could also use symmetric estimates by conditiong on the 'target side' of the
synchronous rule, and other variations of conditioning on the parent type etc. 
For all experiments in this paper we have stuck to the source side conditiong 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(source/target) = \frac{count(stype,ttype,s,t)} { count(s) + k } 
\end{equation}

\begin{figure}[htb]
\centering
\includegraphics[width=3in]{images/treepairs.jpg}
\caption{Sample sub-tree pairs extracted from aligned nodes}
\label{fig:treepairs1}
\end{figure}

\begin{figure}[htb]
\centering
\includegraphics[width=3in]{images/rules.jpg}
\caption{Rules extracted from the Treepairs}
\label{fig:treepairs2}
\end{figure}

\begin{figure}[htb]
\centering
\includegraphics[width=3in]{images/rulestats.jpg}
\caption{Rule statistics extracted from Chinese-English Corpora}
\label{fig:rules}
\end{figure}

\section{Analysis of Chinese-English System}
We used the pipeline of node-alignment followed by rule-extraction to build resources for the Statistical Transfer-based translation system from Chinese to English. The syntax-based phrase table was constructed from two large corpora. One of them was a corpus of about 1.2M sentences. Using these sentences, we built a syntax-based phrase table of about 9.2M entries. The other data source was about 2.6M sentences, but many of its entries were from a Chinese-English lexicon. For this corpus, we extracted 8.75M entries in the phrase-table.

For our experiments we ran the rule learning on 10K corpus that was released as part of the 
LDC English Chinese parallel tree bank. The corpus was node aligned as described in Section 3. Rules
were then extracted and flattened out to form synchronous context free rules. An example of the 
synchronous tree pairs extracted from example in Figure~\ref{fig:treepairs1} is shown below 
in Figure~\ref{fig:tree}. After generalization and flattening, we obtain rules as shown in Figure~\ref{fig:treepairs2}. 


\section{Conclusions}
 \textbf{?}

\todo

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


\end{document}
