{'fraction_non_alphanumeric': 0.024220739007775407, 'fraction_numerical': 0.009151586045551503, 'mean_word_length': 4.762886597938144, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An algorithm for word-level alignment of parallel dependency trees

Structural divergence presents a challenge to the use of syntax in statistical machine translation. We address this problem with a new algorithm for alignment of loosely matched non-isomorphic dependency trees. The algorithm selectively relaxes the constraints of the two tree structures while keeping computational complexity polynomial in the length of the sentences. Experimentation with a large Chinese-English corpus shows an improvement in alignment results over the unstructured models of (Brown et al., 1993).


Introduction
The statistical approach to machine translation, pioneered by (Brown et al., 1990(Brown et al., , 1993, estimates word to word translation probabilities and sentence reordering probabilities directly from a large corpus of parallel sentences. Despite their lack of any internal representation of syntax or semantics, the ability of such systems to leverage large amounts of training data has enabled them to perform competitively with more traditional interlingua based approaches. In recent years, hybrid approaches, which aim at applying statistical models to structural data, have begun to emerge. However, such approaches have been faced with the problem of pervasive structural divergence between languages, due to both systematic differences between languages (Dorr, 1994) and the vagaries of loose translations in real corpora.
Syntax-based statistical approaches to alignment began with (Wu, 1997), who introduced a polynomial-time solution for the alignment problem based on synchronous binary trees. (Alshawi et al., 2000) extended the tree-based approach by representing each production in parallel dependency trees as a finite-state transducer. Both these approaches learn the tree representations directly from parallel sentences, and do not make allowance for non-isomorphic structures. Knight, 2001, 2002) model translation as a sequence of operations transforming a syntactic tree in one language into the string of the second language, making use of the output of an automatic parser in one of the two parallel languages. This allows the model to make use of the syntactic information provided by treebanks and the automatic parsers derived from them. While we would like to use syntactic information in both languages, the problem of non-isomorphism grows when trees in both languages are required to match. The use of probabilistic tree substitution grammars for tree-to-tree alignment (Hajic et al., 2002) allows for limited non-isomorphism in that n-to-m matching of nodes in the two trees is permitted. However, even after extending this model by allowing cloning operations on subtrees, (Gildea, 2003) found that parallel trees overconstrained the alignment problem, and achieved better results with a tree-to-string model using one input tree than with a tree-to-tree model using two.
In this paper we present a new approach to the alignment of parallel dependency trees, allowing the tree structure to constrain the alignment at the high level, but relaxing the isomorphism constraints as necessary within smaller subtrees. The algorithm introduced in this paper addresses the alignment task on its own, rather than viewing it as a part of a generative translation model. The algorithm uses the parallel tree structure to iteratively add constraints to possible alignments between the two input sentences. In each iteration, the algorithm first estimates the word-to-word translation parameters, then computes the scores of a heuristic function for each partial alignment, fixes the more confident partial alignments, and re-estimates the translation parameters in the next iteration. We first give a formal definition of the alignment problem and introduce the iterative framework of the algorithm in section 2. Then we explain the usage of dependency trees and two heuristic functions in sections 3 and 4. The formal algorithm and an example for illustration are given in sections 5 and 6. The alignment results are evaluated in section 7.

Algorithm Outline
We introduce the framework of the alignment algorithm by first looking at how the IBM models handle alignment. In Model 1, all connections for each foreign position are assumed to be equally likely, which implies that the orders of the words in both sentences do not matter. Model 2 more realistically assumes that the probability of a connection depends on the position which it connects to and on the length of the two strings. In Models 3, 4 and 5, the foreign language string is developed by choosing for each word in the English sting, first the number of words in the foreign language string it will generate, then the identity of each foreign language word, and finally the positions that these foreign language words will occupy.
Briefly, Model 1 removes all the positioning information from the sentence pair and can be viewed as a "bag of words" model. And starting with Model 2, word positioning information is gradually added.

The Alignment Problem
Mathematically, the machine translation task can be viewed as a noisy channel. Given the task of translating a foreign language sentence to English, we have: where and are source and target language sentences. We want to find e . The conditional probability part of the right hand side is usually referred to as the translation model (TM). During the construction of a machine translation pipeline, the alignment problem is usually handled as part of the TM and P , where is any possible alignment between e and . This approach requires a generative translation model.
We do not have to model word positioning information the way Models 2 to 5 did if we can find an alternative source for positioning information. Syntactic structures offer a promising choice. We use automatic syntactic parsers to produce the parallel unaligned syntactic structures: (Collins, 1999) for English, (Bikel, 2002) for Chinese. The syntactic trees model the interaction between words within one language, instead of viewing them as a linear sequence. If two syntactic trees are partially aligned, the freedom of alignment for the rest of the unaligned nodes in the two trees is restricted by the aligned nodes, and these unaligned nodes are no longer free to be aligned to any position in the counterpart sentence.
However, when the alignment problem is viewed on its own, a generative model is not necessary. In other words, we can simply maximize using a conditional model. More straightforwardly, the alignment problem can be defined as Definition (1), which is equivalent to the alignment problem definition in (Och and Ney, 2000): Observing this, an iterative algorithm for MT alignment that bootstraps between statistical modeling and the parallel tree structures can be constructed. The following description of the Here, and are words in the source and target language sentences and , respectively. 0 j f j a e f e algorithm views the alignment problem as a labeling task as mentioned in Definition (1): In each iteration of the algorithm, some unfixed node pairs are fixed. As the algorithm walks through the iterations, we have an increasing number of fixed node pairs, together with increasingly fine-grained treelet pairs in step 4. The algorithm stops when enough labels are fixed. Overall, each foreign word is free to be aligned to any English word initially. As the algorithm continues, both the foreign and the English treelets get smaller in size and the complexity of labeling is reduced.
Step 0. Unfix all the labeling for except the root; initialize the two trees for e and as the only tree pair. j f f Step 1. Train a statistical translation model on all the tree pairs to acquire word-to-word translation probabilities. The tree pairs are used as "bags of words" in this step and a statistical model such as IBM Model 1 can be used.

Using Dependency Trees
Step 2. Compute the labeling for all unfixed nodes. Use a heuristic function to select confident labelings, and merge these labelings into the fixed labeling set.
This framework of alignment utilizes tree structures to provide the positioning information. At a glance, phrasal structure trees (treebank style trees) seem to be a natural choice. However, phrasal structure trees have two types of nodes, namely nonterminals and lexical items. The projected labelings always go to the lexical items while the domain information is stored in the nonterminals. It is difficult to determine how to partition a phrasal structure tree.
To solve this problem, we use dependency trees.
Step 3. Project the fixed labeling set back onto the English and foreign language tree structures as fixed nodes Step 4. Partition the both the English and foreign language trees with the fixed nodes, producing a set of "treelet" pairs.
Step 5. Go to Step 1 unless enough nodes fixed In addition, the dependency representation has the best phrasal cohesion properties. The percentage for head crossings per chance is 12.62% and that of modifier crossings per chance is 9.22%, according to (Fox, 2002).
We call the resulting trees from a tree partitioning operation "treelets" instead of "subtrees" since they do not necessarily go down to every leaf. An example of a tree partition operation is shown in Figures 1a and 1b.
Dependency trees can be constructed from phrasal structure trees using a head percolation table (Xia, 2001). Each node of a dependency tree dominates its descendents. If the dependency tree is stored with local word order information at its nodes, a tree traversal algorithm starting at any arbitrary node of the tree always generates a chunk in the original sentence. The sentence "The quick brown fox jumps over the lazy dog" is represented as a dependency tree in Figure 1a. When some of the nodes in a dependency tree are fixed, we can partition the tree with each of the fixed nodes as a new root for the resulting treelets. Figure 1b shows the resulting three treelets by fixing the words "jumps", "fox" and "dog". Algorithmically, fixing one node in a treelet will result in two subsequent treelets. The treelet rooted at the original root is called the "outside treelet" and the treelet rooted at the newly fixed node is called the "inside treelet". This is shown in Figure 2. As a result, if we have n fixed nodes in a dependency tree, we will always have n treelets (assuming the

Figure 1b
Partitioning by fixing "fox" "dog" and "jump" root of the whole tree is always fixed). This guarantees that whenever we fix a pair of nodes, the resulting partitioned treelets are always matched in pairs.

Figure 2 Inside and Outside Treelets
Partition "a recently built house" by fixing "built" The correctness of the algorithm lies in what we refer to as our partition assumption: This assumption is much looser than requiring the two dependency trees of the two languages to be isomorphic. A typical violation of this assumption is the set of crossing-dependency alignments between two structures shown in Figure 3 below: While such violations of the partition assumption exist in real language pairs (as reported by (Fox, 2002) to be around 10%), the hope is, if we only fix node pairs above and below such violations, the "bag of words" translation model will correctly align the words with crossing-dependency alignments.

Heuristics
The heuristic function in Step 2 takes a tentative node pair ( from the two treelets and outputs a certain value which corresponds to confidence in this labeling. Here we introduce two heuristic functions. ) , , we have . A reliable set of translation probabilities will provide a distribution with a high concentration of probabilities on the chosen labels. Intuitively, the conditional entropy of the translation probability distribution will serve as a good estimate of the confidence in the chosen labeling. Let and define e E ∈ as a random variable. Since we need to compute conditional entropy given , here the translation probabilities are normalized. The first heuristic function is defined as:

Inside-Outside Probability
Suppose we have two trees initially, T and . When we fix a pair of words , both trees will be partitioned into two treelets. Here we borrow the idea from PCFG parsing, and call the Step 0: Let   Step 2: The above two probabilities are derived using ideas from IBM Model 1. Similarly, define the second heuristic function as: Again, let us suppose we want to create two treelet pairs by fixing the node pair . In the first heuristic, the size and topology of the two resulting treelet pairs are not taken into consideration. If we are unlucky enough, we may well end up having a treelet pair with one node on one side and 9 nodes on the other. So we set a fertility threshold to make sure that the resulting treelet pairs have reasonable sizes on both sides. Currently it is set to be 2.0. Any labeling resulting in a treelet pair that the number of the nodes on one side is larger than twice the number of the nodes on the other will be discarded. Step 3: Here we present the formal algorithm. The following invariant holds at Step 1 of each iteration because every new treelet created by the tree partition operation in Step 3 is an inside treelet rooted by a fixed node. Hence it is guaranteed that each partition operation in Step 3 will create a new treelet pair.
} //if } // for each In Table 2, Models h1 and h2 are our models that use heuristic function h1 and h2, respectively. We find that with the current parameter settings, Models h1 and h2 tend to overfit after the second iteration. Table 2 shows results after one iteration of steps 2 through 4 of our algorithm, after successive iterations of IBM Model 1 in step 1 of the second iteration. The two iterations of the algorithm take less than two hours on a dual Pentium 1.2GHz machine for both heuristics. Error analysis showed that the overfitting problem is mainly caused by violation of the partition assumption in fine-grained dependency structures.

Conclusion
Our model, based on partitioning sentences according to their dependency structure, outperforms the unstructured IBM models on a large data set. The model can be thought of as in sense orthogonal to the IBM models in that it uses syntactic structure but no linear ordering information.
Possible future extensions to the model include adding information on linear order, allowing alignments that violate the partition assumption at some cost in probability, and conditioning alignment probabilities on part of speech tags.