{'fraction_non_alphanumeric': 0.03656984145353547, 'fraction_numerical': 0.01643328318481657, 'mean_word_length': 4.567976804123711, '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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Well-Formed Dependency to String translation with BTG Grammar

This paper proposes a well-formed dependency to string translation model with BTG grammar. By enabling the usage of wellformed sub-structures and allowing flexible reordering of them, our approach is effective to relieve the problems of parsing error and flatness in dependency structure. To utilize the well-formed dependency rules during decoding, we adapt the tree traversal decoding algorithm into a bottom-up CKY algorithm. And a lexicalized reordering model is used to encourage the proper combination of two neighbouring blocks. Experiment results demonstrate that our approach can effectively improve the performance by more than 2 BLEU score over the baseline.


Introduction
Due to the merits of holding shallow semantic information and cross-lingual consistency (Fox, 2002), dependency grammar has attracted much attention in the field of machine translation (Lin, 2004;Quirk et al., 2005;Ding and Palmer, 2005;Shen et al., 2008;Xie et al., 2011).
The dependency-to-string model (Xie et al., 2011) falls into the paradigm of "translation after understanding", which tries to understand the structure and meaning of source text. However, there are two typical problems for this approach. One is that the model is prone to be affected by parsing errors. Dependency-to-string model adopts a unique source side tree structure as fixed input and constructs the output by converting each sub-structure into target side. If there is some errors in the source dependency tree, for example, a prepositional subtree is attached to a wrong head, the model can hardly recover the error. Figure 1(a) shows another parsing error, in the correct parsing result, "与北韩...国家" should forms a subtree with "国家" as the head, and then this subtree is dominant by "之一".
The other problem is that dependency structure is too flat for the translation task. Since dependencyto-string model requires a head and all its dependents to be translated as a whole, the flatness of the structure will make rules difficult to be matched during decoding. Furthermore, it will also lower the robustness of translation rules, since many giant and low-frequency rules will be extracted. Figure 1 (b) shows an example of the flat structure. The head word "提供" has five dependents in the structure. If no rule can be matched, only the glue rule can be applied. As a result, the prepositional subtree "为 了...义务" cannot be correctly reordered to the end in the target side.
Existing solutions for the above problems include (Meng et al., 2013;Xie et al., 2014). The formmer incorporates phrasal nodes of constituency trees in the source side of translation rules, and the latter modifies translation rules during decoding to allow the usage of phrases which are compatible with well-formed structures. Since these two approaches still adopt head-dependent structure as the backbone of the translation rule, the freedom of generating translation candidates is limited.
On the contrary, we propose to use BTG grammar to combine the translations of two adjacent wellformed structures. To incorporate the BTG rules into the model, we adapt the tree traversal decoding algorithm into a bottom-up CKY algorithm. Large scale experiments show that our approach can improve the performance by more than 2 BLEU score over the baseline, and it is also superior to the two approaches mentioned above.

Background
We briefly review the dependency to string model and the BTG grammar in this section, which are the bases of our proposed model.

Dependency-to-String Model
The dependency-to-string model proposed by (Xie et al., 2011) translates a source dependency tree by applying head-dependents translation rule at each head node in a recursive way. A head-dependents translation rule consists of a head-dependents fragment in the source side and its translation correspondence in the target side. The rule r1 in Figure 2 is an example of their translation rule. This rule specifies the translation of the head node "提供" and leaf nodes "布 什", and also the reordering relation of the non-terminal nodes, including the internal node "为" and the generalized internal node "优惠". The word or POS tag at each non-terminal node in the rule describes its matching condition. For example, X2:NN in r1 means the second non-terminal must be a noun while matching this rule. In principle, all nodes, i.e., head, internal and leaf nodes in the dependency tree, can be generalized to their POS tags (or other categories) to relieve data sparsity. By including a head and all its dependents into one rule, the dependency-to-string model is good at long distance reordering. However, this structure is not robust enough due to parsing errors and flatness.

BTG Grammar
Bracketing transduction grammar (BTG) (Wu, 1997) is a special case of synchronous context free grammar. There are only two types of rules in this grammar: The first type of rule is used to merge the translations of two neighbouring blocks X 1 and X 2 with monotone or swap order, and the second type of rule is used to translate source phrase x in to target phrase y. Due to its simplicy and effectiveness of modeling bilingual correspondence, BTG grammar is widely used translation modeling (Xiong et al., 2006;Li et al., 2013), word alignment (Zhang and Gildea, 2005;Haghighi et al., 2009;Pauls et al., 2010), translation system combination (Karakos et al., 2008), etc.

Well-Formed Dependency to String Model
In this section, we describe our well-formed dependency to string model with BTG grammar, and explain how it relieves the problems of parsing error and flatness.

Modified Well-formed structure
Similar to (Shen et al., 2008), we define two kinds of well-formed dependency structures, i.e., fixed structure and floating structure. Fixed structure consists of the heads of a sequence of sibling trees and the common head of these trees; and floating structure consists of the heads of a sequence of sibling trees without their common head. The difference between 提供 布什 为 优惠

为民众 减税优惠
Bush provides tax relief to the pepole Head node in the rules are marked with bold face. NN is the POS tag of the source word "优惠". our definition and that in Shen et al., 2008 is that we only include the heads of subtrees in our structure, while they include the whole subtrees. The shadowed part with red box in Figure 1(b) is an example of fixed structure, which consists of a head "提供" and the heads of two continuous sibling trees "为 了" and "报酬". And the shadowed part with green box in Figure 1(b) is an example of floating structure, which consists of the heads of three continuous sibling trees "美国", "不" and "会". Given a sentence w 1 w 2 ...w n , let d i denote the head index of w i , our fixed and floating structure can be formally defined as follows, Definition 1 A fixed structure f h,C with head h and children C, where h ∈ [1, n] and C ⊆ {1, ..., n}, is a two-level tree fragment which satisfies the following conditions: .., n}, is a one level tree fragment which satisfies the following conditions:

Well-Formed Dependency-to-String Rule
Our well-formed dependency to string translation rule consists of a well-formed dependency structure in the source side and its translation correspondence in the target side. This definition extends the rule proposed in (Xie et al., 2011) to cover all wellformed dependency structures in the source side, rather than using complete head-dependents structures only. The rule r2 is an examples of our translation rule. Compared with r1, this rule does not contain "布什" in the source side (and its translation in the target side). Since it contains less context, this rule is more flexible to be applied during decoding. For example, if "布什" is replaced with a pronoun "他" in a testing sentence, this rule can still be applied. However, r1 cannot be applied in this case even if it is generalized, since the POS tag of "他" does not match that of "布什".
Our translation rules can be extracted from aligned dependency tree and string pair by traversing the tree and enumerating the well-formed structure at each node. Following previous work (Koehn et al., 2003;Galley et al., 2004;Chiang, 2005), we impose alignment constraint for rule extraction. The intuition is that words in the one side (source/target) cannot be aligned to words outside the other side, and the word alignment within non-terminals also need to satisfy this constraint.
Formally, for a non-terminal node n, we define node span nsp(n) as the closure of the indexes of those words that n is alinged to, and sub-tree span ssp(n) as the closure of node spans of all the nodes in the subtree rooted with n. These two spans are set to φ for terminals. In addition, we use N s to denote the set of all the terminal indexes in the source side, and N t to denote the set of all the terminal indexes in the target side. Function a(·) is used to get the indexes of the aligned words for a give word. Then the alignment constraint can be described as follows, A minor difference in our constraint with (Xie et al., 2011) is that we allow the alignment of terminals to be overlaped. For example, in Figure 1(b), if the two terminals "不" and "会" align to a single target word "won't", we consider the alignment constraint is satisfied, while they consider it as invalid.

Apply Dependency to String Rules with BTG Rules
We use the examples in Figure 1 to illustrate how the well-formed dependency to string rules together with BTG rules can be used to overcome the problems of parsing error and flatness. A plausible derivation for the example in Figure 1(a) is shown in Figure 3, in which the subtree "与...的", the floating structure "少数国家" and the head node is translated first, then the translations of the first two parts can be combined with a BTG rule of swap order. The final translation can be achieved by applying another BTG rule of swap order to the translation just obtained and the translation of "之一". Note that this is not the only derivation that can lead to a correct translation. We can also combine the translation of floating structure "少数国家" and the head node first, then combine with the translation of the first subtree. Similarly, for the example in Figure  1(b), we can first translate the floating structure "美 国不会" and the fixed structure "为了...提供...报 酬", then combine them with an BTG rule of monotone order to produce the final translation.

Model
We use the standard log-linear model (Och and Ney, 2002) to score the translation hypothesis during decoding. For a specific derivation d that converts a source dependency tree T into a target string s, the score of d will be, where φ i are features defined on derivations and λ i are corresponding weight for each feature. The features adopted in this paper include bidirectional translation probabilities, bidirectional lexical weights, language model, rule penalty, word penalty and reordering probability for BTG rules.
For the last feature, we use a maximum entropy model to estimation the probability and the same  Figure 3: a plausible derivation with well-formed dependency to string and BTG grammar for the example in Figure 1(a) features in (Xiong et al., 2006) are adopted, including beginning and ending words in the two blocks to be reordered, from both the source and target side. So there are eight activated features in total for each instance.

Decoding Algorithm
The decoding algorithm is described in Algorithm 1. The algorithm begins by translating each word in the sentence, then proceed to translate larger spans in an bottom up manner. When translating a span compatible with a well-formed structure, there are two ways to generate translation candidates. One is based on fixed or floating rules which covers the whole span, and the other is combining the translation candidates in two sub-spans with BTG rule of monotone or swap order. The two sub-spans also need to be compatible with well-formed structure. The cube prunning algorithm (Chiang, 2007;Huang and Chiang, 2007) is used to expand the initial candidates until Kbest candidates have been generated. Finally, the top candidate over the whole sentence will be returned as output.

Experiments
We evaluate the performance of our model on Chinese to English translation. And we re-implement the dependency to string model for performance comparison.

Data preparation
Two sets of training data are adopted in our experiments. The smaller one consists of 270k sentence pairs, and the larger one consists of 2.1M sentence pairs. All the training data comes from the LDC corpus 1 . And we use NIST 02 test set as our development set, NIST 03 and 04 test set as our test 1 Including LDC2000T50, LDC2002E18, LDC2003E07, LDC2003E14, LDC200407, LDC2005T06, LDC2002L27, LDC2005T10 and LDC 2005T34. set. The case insensitive NIST BLEU-4 metric (Papineni et al., 2002) is adopted for evaluation. We use the SRILM toolkit to train a 5-gram language model with Kneser-Ney smoothing on the Xinhua portion of the Gigaword corpus.
The source side of the training and dev/test set are segmented with our in house segmentation tool (Wang et al., 2010).And they are parsed with Stanford Parser (De Marneffe et al., 2006), which also generates POS tag for each word. The dependency relations on edges are not used in this work.
Word alignments are obtained with our in house tool (Wang and Zong, 2013), which takes dependency cohesion constraints into consideration while doing word alignments. And we use the MaxEnt toolkit 2 to to estimate the context sensitive reordering probability for BTG rules. The weights of the features are tuned with MERT (Och, 2003) to maximize the BLEU score on the development set.

Results
The strength of our model lies in two aspects. First, our translation unit is more fine-grained than that in the original dependency to tree model, which enables the translation of many linguistically plausible phrases; second, we allow flexible reorderings for adjacent blocks under the guide of context information.  we only allow BTG rule with monotone order, i.e. translation of each well-formed structure are concatenated sequentially, which is equivalent to glue rule. Then BTG rules with both orders are enabled, with context sensitive reordering module. We conduct the experiments with the small training data set. The results are shown in Table 1. Compared with dependency to string rules, applying well-formed dependency to string rules significantly improves the performance by more than 1.5 BLEU score on average. If flexible reordering is further allowed, additional improvement of 0.7 BLEU score can be achieved. Table 2 shows the performance of our model with large training set. Experiment results show that our model keeps its edge even with large training data. On average, more than 2 point in BLEU score are gained over the baseline. This improvement is much larger than (Meng et al., 2013) and (Xie et al., 2014). Both of them report improvement of about 0.9 point in BLEU score over the baseline on their dataset.

Related Work
The work that is most similar to ours is (Xie et al., 2014). However, there are several significant differences between these two work. First They incorporate well-formed dependency rules during decoding by modify the matched dependency rules "on the fly". For example, assume there is a matched rule "X1:NR X2:AD X3:VV X1:为了提 提 提供 供 供 X2:报 酬||| X1 X2 X3 provide X5 X4" for the headdependents structure in Figure 1 (b). in order to use the phrase "美国不会||| us won't" during decoding, they will compress the three nodes into one pseudo node "NR AD VV". Then the above rule will become "X1:NR AD VV X2:为了 * 提 提 提供 供 供 X3:报酬||| X1 provide X3 X2". This new rule will inherit the translation probabilities from the original rule. In the case that there is no matched rule or the probability estimation is unreliable due to sparsity, this method won't work well. Another difference is that they only use phrasal rules corresponding to well formed dependency structures, while we allow variables to be contained in the well-formed dependency rules.
The two problems of parsing error and flatness also exist in constituency tree . In order to make full use of the sub-structures, there have been a lot of work, including tree sequence to string translation (Liu et al., 2007), tree binarization (Zhang et al., 2006), forest-based translation (Mi et al., 2008) and fuzzy rule matching (Zhang et al., 2011).

Conclusion and Future Work
In this work, we propose a well-formed dependency to string model to address the problems of parsing error and flatness. By introducing translation rules corresponding to well-formed sub-structures, we are able to learn more reliable translation equivalents. During decoding, we propose to use BTG grammar with lexicalized reordering to combine translations of two neighbouring well-formed structures, which is more flexible than previous work. Experiment results demonstrate that our model can significantly improve translation performance.
Although our model is more flexible to generate translation candidates, it also brings more challenges to model translation quality. In the future, we will explore more powerful features to better score the translation candidates.