{'fraction_non_alphanumeric': 0.045673897148427976, 'fraction_numerical': 0.013404825737265416, 'mean_word_length': 4.497320471596999, 'pattern_counts': {'":': 0, '<': 1, '<?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}}
A Syntax-Directed Translator with Extended Domain of Locality

A syntax-directed translator first parses the source-language input into a parse-tree, and then recursively converts the tree into a string in the target-language. We model this conversion by an extended tree-to-string transducer that have multi-level trees on the source-side, which gives our system more expressive power and flexibility. We also define a direct probability model and use a linear-time dynamic programming algorithm to search for the best derivation. The model is then extended to the general log-linear framework in order to rescore with other features like n-gram language models. We devise a simple-yet-effective algorithm to generate non-duplicate k-best translations for n-gram rescoring. Initial experimental results on English-to-Chinese translation are presented.


Introduction
The concept of syntax-directed (SD) translation was originally proposed in compiling (Irons, 1961;Lewis and Stearns, 1968), where the source program is parsed into a tree representation that guides the generation of the object code. Following Aho and Ullman (1972), a translation, as a set of string pairs, can be specified by a syntax-directed translation schema (SDTS), which is essentially a synchronous context-free grammar (SCFG) that generates two languages simultaneously. An SDTS also induces a translator, a device that performs the transformation from input string to output string. In this context, an SD translator consists of two components, a sourcelanguage parser and a recursive converter which is usually modeled as a top-down tree-to-string transducer (Gécseg and Steinby, 1984). The relationship among these concepts is illustrated in Fig. 1. This paper adapts the idea of syntax-directed translator to statistical machine translation (MT). We apply stochastic operations at each node of the source-language parse-tree and search for the best derivation (a sequence of translation steps) that converts the whole tree into some target-language string with the highest probability. However, the structural divergence across languages often results in nonisomorphic parse-trees that is beyond the power of SCFGs. For example, the S(VO) structure in English is translated into a VSO word-order in Arabic, an instance of complex reordering not captured by any SCFG (Fig. 2).
To alleviate the non-isomorphism problem, (synchronous) grammars with richer expressive power have been proposed whose rules apply to larger fragments of the tree. For example, Shieber and Schabes (1990) introduce synchronous tree-adjoining grammar (STAG) and Eisner (2003) uses a synchronous tree-substitution grammar (STSG), which is a restricted version of STAG with no adjunctions. STSGs and STAGs generate more tree relations than SCFGs, e.g. the non-isomorphic tree pair in Fig. 2. This extra expressive power lies in the extended domain of locality (EDL) (Joshi and Schabes, 1997), i.e., elementary structures beyond the scope of onelevel context-free productions. Besides being linguistically motivated, the need for EDL is also supported by empirical findings in MT that one-level rules are often inadequate (Fox, 2002;Galley et al., 2004). Similarly, in the tree-transducer terminology, Graehl and Knight (2004) define extended tree transducers that have multi-level trees on the source-side.
Since an SD translator separates the sourcelanguage analysis from the recursive transformation, the domains of locality in these two modules are orthogonal to each other: in this work, we use a CFGbased Treebank parser but focuses on the extended domain in the recursive converter. Following Galley et al. (2004), we use a special class of extended tree-to-string transducer (xRs for short) with multilevel left-hand-side (LHS) trees. 1 Since the righthand-side (RHS) string can be viewed as a flat onelevel tree with the same nonterminal root from LHS ( Fig. 2), this framework is closely related to STSGs: they both have extended domain of locality on the source-side, while our framework remains as a CFG on the target-side. For instance, an equivalent xRs rule for the complex reordering in Fig. 2 would be S(x 1 :NP, VP(x 2 :VB, x 3 :NP)) → x 2 x 1 x 3 While Section 3 will define the model formally, we first proceed with an example translation from English to Chinese (note in particular that the inverted phrases between source and target): 1 Throughout this paper, we will use LHS and source-side interchangeably (so are RHS and target-side). In accordance with our experiments, we also use English and Chinese as the source and target languages, opposite to the Foreign-to-English convention of Brown et al. (1993). (1) the gunman was killed by the police . Figure 3 shows how the translator works. The English sentence (a) is first parsed into the tree in (b), which is then recursively converted into the Chinese string in (e) through five steps. First, at the root node, we apply the rule r 1 which preserves the toplevel word-order and translates the English period into its Chinese counterpart: (r 1 ) S (x 1 :NP-C x 2 :VP PUNC (.) ) → x 1 x 2 • Then, the rule r 2 grabs the whole sub-tree for "the gunman" and translates it as a phrase: (r 2 ) NP-C ( DT (the) NN (gunman) ) → qiangshou Now we get a "partial Chinese, partial English" sentence "qiangshou VP • " as shown in Fig. 3 (c). Our recursion goes on to translate the VP sub-tree. Here we use the rule r 3 for the passive construction: which captures the fact that the agent (NP-C, "the police") and the verb (VBN, "killed") are always inverted between English and Chinese in a passive voice. Finally, we apply rules r 4 and r 5 which perform phrasal translations for the two remaining subtrees in (d), respectively, and get the completed Chinese string in (e).

Previous Work
It is helpful to compare this approach with recent efforts in statistical MT. Phrase-based models (Koehn et al., 2003;Och and Ney, 2004) are good at learning local translations that are pairs of (consecutive) sub-strings, but often insufficient in modeling the reorderings of phrases themselves, especially between language pairs with very different word-order. This is because the generative capacity of these models lies within the realm of finite-state machinery (Kumar and Byrne, 2003), which is unable to process nested structures and long-distance dependencies in natural languages.
Syntax-based models aim to alleviate this problem by exploiting the power of synchronous rewriting systems. Both Yamada and Knight (2001) and Chiang (2005) use SCFGs as the underlying model, so their translation schemata are syntax-directed as in Fig. 1, but their translators are not: both systems do parsing and transformation in a joint search, essentially over a packed forest of parse-trees. To this end, their translators are not directed by a syntactic tree. Although their method potentially considers more than one single parse-tree as in our case, the packed representation of the forest restricts the scope of each transfer step to a one-level contextfree rule, while our approach decouples the sourcelanguage analyzer and the recursive converter, so that the latter can have an extended domain of locality. In addition, our translator also enjoys a speedup by this decoupling, with each of the two stages having a smaller search space. In fact, the recursive transfer step can be done by a a linear-time algorithm (see Section 5), and the parsing step is also fast with the modern Treebank parsers, for instance (Collins, 1999;Charniak, 2000). In contrast, their decodings are reported to be computationally expensive and Chiang (2005) uses aggressive pruning to make it tractable. There also exists a compromise between these two approaches, which uses a k-best list of parse trees (for a relatively small k) to approximate the full forest (see future work).
Besides, our model, as being linguistically motivated, is also more expressive than the formally syntax-based models of Chiang (2005) and Wu (1997). Consider, again, the passive example in rule r 3 . In Chiang's SCFG, there is only one nonterminal X, so a corresponding rule would be which can also pattern-match the English sentence: and translate it into Chinese as a passive voice. This produces very odd Chinese translation, because here "was A by B" in the English sentence is not a passive construction. By contrast, our model applies rule r 3 only if A is a past participle (VBN) and B is a noun phrase (NP-C). This example also shows that, one-level SCFG rule, even if informed by the Treebank as in (Yamada and Knight, 2001), is not enough to capture a common construction like this which is five levels deep (from VP to "by").
There are also some variations of syntax-directed translators where dependency structures are used in place of constituent trees (Lin, 2004;Ding and Palmer, 2005;Quirk et al., 2005). Although they share with this work the basic motivations and similar speed-up, it is difficult to specify re-ordering information within dependency elementary structures, so they either resort to heuristics (Lin) or a separate ordering model for linearization (the other two works). 2 Our approach, in contrast, explicitly models the re-ordering of sub-trees within individual transfer rules.

Extended Tree-to-String Tranducers
In this section, we define the formal machinery of our recursive transformation model as a special case of xRs transducers (Graehl and Knight, 2004) that has only one state, and each rule is linear (L) and non-deleting (N) with regarding to variables in the source and target sides (henth the name 1-xRLNs). Definition 1. A 1-xRLNs transducer is a tuple (N, Σ, ∆, R) where N is the set of nonterminals, Σ is the input alphabet, ∆ is the output alphabet, and R is a set of rules. A rule in R is a tuple (t, s, φ) where: 1. t is the LHS tree, whose internal nodes are labeled by nonterminal symbols, and whose frontier nodes are labeled terminals from Σ or variables from a set X = {x 1 , x 2 , . . .}; 2. s ∈ (X ∪ ∆) * is the RHS string; 3. φ is a mapping from X to nonterminals N .
We require each variable x i ∈ X occurs exactly once in t and exactly once in s (linear and non-deleting). We denote ρ(t) to be the root symbol of tree t. When writing these rules, we avoid notational overhead by introducing a short-hand form from Galley et al. (2004) that integrates the mapping into the tree, which is used throughout Section 1. Following TSG terminology (see Figure 2), we call these "variable nodes" such as x 2 :NP-C substitution nodes, since when applying a rule to a tree, these nodes will be matched with a sub-tree with the same root symbol.
We also define |X | to be the rank of the rule, i.e., the number of variables in it. For example, rules r 1 and r 3 in Section 1 are both of rank 2. If a rule has no variable, i.e., it is of rank zero, then it is called a purely lexical rule, which performs a phrasal translation as in phrase-based models. Rule r 2 , for instance, can be thought of as a phrase pair the gunman, qiangshou .
Informally speaking, a derivation in a transducer is a sequence of steps converting a source-language 2 Although hybrid approaches, such as dependency grammars augmented with phrase-structure information (Alshawi et al., 2000), can do re-ordering easily. tree into a target-language string, with each step applying one tranduction rule. However, it can also be formalized as a tree, following the notion of derivation-tree in TAG (Joshi and Schabes, 1997): Definition 2. A derivation d, its source and target projections, noted E(d) and C(d) respectively, are recursively defined as follows: 1. If r = (t, s, φ) is a purely lexical rule (φ = ∅), then d = r is a derivation, where E(d) = t and C(d) = s; 2. If r = (t, s, φ) is a rule, and d i is a (sub-) derivation with the root symbol of its source projection matches the corresponding substitution node in r, i.e., ρ(E(d i )) = φ(x i ), then d = r(d 1 , . . . , d m ) is also a derivation, where Note that we use a short-hand notation [x i → y i ]t to denote the result of substituting each x i with y i in t, where x i ranges over all variables in t.
For example, Figure 4 shows two derivations for the sentence pair in Example (1). In both cases, the source projection is the English tree in Figure 3 (b), and the target projection is the Chinese translation. Galley et al. (2004) presents a linear-time algorithm for automatic extraction of these xRs rules from a parallel corpora with word-alignment and parse-trees on the source-side, which will be used in our experiments in Section 6.

Direct Model
Departing from the conventional noisy-channel approach of Brown et al. (1993), our basic model is a direct one: where e is the English input string and c * is the best Chinese translation according to the translation model Pr(c | e). We now marginalize over all English parse trees T (e) that yield the sentence e: Rather than taking the sum, we pick the best tree τ * and factors the search into two separate steps: parsing (4) (a well-studied problem) and tree-to-string translation (5) (Section 5): In this sense, our approach can be considered as a Viterbi approximation of the computationally expensive joint search using (3) directly. Similarly, we now marginalize over all derivations that translates English tree τ into some Chinese string and apply the Viterbi approximation again to search for the best derivation d * : Assuming different rules in a derivation are applied independently, we approximate Pr(d) as where the probability Pr(r) of the rule r is estimated by conditioning on the root symbol ρ(t(r)): Pr(r) = Pr(t(r), s(r) | ρ(t(r))) = c(r) r :ρ(t(r ))=ρ(t(r)) c(r ) where c(r) is the count (or frequency) of rule r in the training data.

Log-Linear Model
Following Och and Ney (2002), we extend the direct model into a general log-linear framework in order to incorporate other features: where Pr(c) is the language model and e −λ|c| is the length penalty term based on |c|, the length of the translation. Parameters α, β, and λ are the weights of relevant features. Note that positive λ prefers longer translations. We use a standard trigram model for Pr(c).

Search Algorithms
We first present a linear-time algorithm for searching the best derivation under the direct model, and then extend it to the log-linear case by a new variant of k-best parsing.

Direct Model: Memoized Recursion
Since our probability model is not based on the noisy channel, we do not call our search module a "decoder" as in most statistical MT work. Instead, readers who speak English but not Chinese can view it as an "encoder" (or encryptor), which corresponds exactly to our direct model. Given a fixed parse-tree τ * , we are to search for the best derivation with the highest probability. This can be done by a simple top-down traversal (or depth-first search) from the root of τ * : at each node η in τ * , try each possible rule r whose Englishside pattern t(r) matches the subtree τ * η rooted at η, and recursively visit each descendant node η i in τ * η that corresponds to a variable in t(r). We then collect the resulting target-language strings and plug them into the Chinese-side s(r) of rule r, getting a translation for the subtree τ * η . We finally take the best of all translations.
With the extended LHS of our transducer, there may be many different rules applicable at one tree node. For example, consider the VP subtree in Fig. 3 (c), where both r 3 and r 6 can apply. As a result, the number of derivations is exponential in the size of the tree, since there are exponentially many decompositions of the tree for a given set of rules. This problem can be solved by memoization (Cormen et al., 2001): we cache each subtree that has been visited before, so that every tree node is visited at most once. This results in a dynamic programming algorithm that is guaranteed to run in O(npq) time where n is the size of the parse tree, p is the maximum number of rules applicable to one tree node, and q is the maximum size of an applicable rule. For a given rule-set, this algorithm runs in time linear to the length of the input sentence, since p and q are considered grammar constants, and n is proportional to the input length. The full pseudocode is worked out in Algorithm 1. A restricted version of this algorithm first appears in compiling for optimal code generation from expression-trees (Aho and Johnson, 1976). In computational linguistics, the bottom-up version of this algorithm resembles the tree parsing algorithm for TSG by Eisner (2003). Similar algorithms have also been proposed for dependency-based translation (Lin, 2004;Ding and Palmer, 2005).

Log-linear Model: k-best Search
Under the log-linear model, one still prefers to search for the globally best derivation d * : However, integrating the n-gram model with the translation model in the search is computationally very expensive. As a standard alternative, rather than aiming at the exact best derivation, we search for top-k derivations under the direct model using Algorithm 1, and then rerank the k-best list with the language model and length penalty.
Like other instances of dynamic programming, Algorithm 1 can be viewed as a hypergraph search problem. To this end, we use an efficient algorithm by Huang and Chiang (2005, Algorithm 3) that solves the general k-best derivations problem in monotonic hypergraphs. It consists of a normal forward phase for the 1-best derivation and a recursive backward phase for the 2nd, 3rd, . . . , k th derivations.
Unfortunately, different derivations may have the same yield (a problem called spurious ambiguity), due to multi-level LHS of our rules. In practice, this results in a very small ratio of unique strings among top-k derivations. To alleviate this problem, determinization techniques have been proposed by Mohri and Riley (2002) for finite-state automata and extended to tree automata by May and Knight (2006). These methods eliminate spurious ambiguity by effectively transforming the grammar into an equivalent deterministic form. However, this transformation often leads to a blow-up in forest size, which is exponential to the original size in the worst-case.
So instead of determinization, here we present a simple-yet-effective extension to the Algorithm 3 of Huang and Chiang (2005) that guarantees to output unique translated strings: • keep a hash-table of unique strings at each vertex in the hypergraph • when asking for the next-best derivation of a vertex, keep asking until we get a new string, and then add it into the hash-table This method should work in general for any equivalence relation (say, same derived tree) that can be defined on derivations.

Experiments
Our experiments are on English-to-Chinese translation, the opposite direction to most of the recent work in SMT. We are not doing the reverse direction at this time partly due to the lack of a sufficiently good parser for Chinese.

Data Preparation
Our training set is a Chinese-English parallel corpus with 1.95M aligned sentences (28.3M words on the English side). We first word-align them by GIZA++, then parse the English side by a variant of Collins (1999) parser, and finally apply the rule-extraction algorithm of Galley et al. (2004). The resulting rule set has 24.7M xRs rules. We also use the SRI Language Modeling Toolkit (Stolcke, 2002) to train a Chinese trigram model with Knesser-Ney smoothing on the Chinese side of the parallel corpus.
Our evaluation data consists of 140 short sentences (< 25 Chinese words) of the Xinhua portion of the NIST 2003 Chinese-to-English evaluation set. Since we are translating in the other direction, we use the first English reference as the source input and the Chinese as the single reference. to 1 against the reference. The results are summarized in Table 1. The rescored translations are better than the 1-best results from the direct model, but still slightly worse than Pharaoh.

Conclusion and On-going Work
This paper presents an adaptation of the classic syntax-directed translation with linguisticallymotivated formalisms for statistical MT. Currently we are doing larger-scale experiments. We are also investigating more principled algorithms for integrating n-gram language models during the search, rather than k-best rescoring. Besides, we will extend this work to translating the top k parse trees, instead of committing to the 1-best tree, as parsing errors certainly affect translation quality.