{'fraction_non_alphanumeric': 0.035825388861013545, 'fraction_numerical': 0.015805318615153035, 'mean_word_length': 4.844868035190616, '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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Machine Translation System Combination by Confusion Forest

The state-of-the-art system combination method for machine translation (MT) is based on confusion networks constructed by aligning hypotheses with regard to word similarities. We introduce a novel system combination framework in which hypotheses are encoded as a confusion forest, a packed forest representing alternative trees. The forest is generated using syntactic consensus among parsed hypotheses: First, MT outputs are parsed. Second, a context free grammar is learned by extracting a set of rules that constitute the parse trees. Third, a packed forest is generated starting from the root symbol of the extracted grammar through non-terminal rewriting. The new hypothesis is produced by searching the best derivation in the forest. Experimental results on the WMT10 system combination shared task yield comparable performance to the conventional confusion network based method with smaller space.


Introduction
System combination techniques take the advantages of consensus among multiple systems and have been widely used in fields, such as speech recognition (Fiscus, 1997;Mangu et al., 2000) or parsing (Henderson and Brill, 1999). One of the state-of-the-art system combination methods for MT is based on confusion networks, which are compact graph-based structures representing multiple hypotheses (Bangalore et al., 2001).
Confusion networks are constructed based on string similarity information. First, one skeleton or backbone sentence is selected. Then, other hypotheses are aligned against the skeleton, forming a lattice with each arc representing alternative word candidates. The alignment method is either model-based (Matusov et al., 2006;He et al., 2008) in which a statistical word aligner is used to compute hypothesis alignment, or edit-based (Jayaraman and Lavie, 2005;Sim et al., 2007) in which alignment is measured by an evaluation metric, such as translation error rate (TER) (Snover et al., 2006). The new translation hypothesis is generated by selecting the best path through the network.
We present a novel method for system combination which exploits the syntactic similarity of system outputs. Instead of constructing a string-based confusion network, we generate a packed forest (Billot and Lang, 1989;Mi et al., 2008) which encodes exponentially many parse trees in a polynomial space. The packed forest, or confusion forest, is constructed by merging the MT outputs with regard to their syntactic consensus. We employ a grammar-based method to generate the confusion forest: First, system outputs are parsed. Second, a set of rules are extracted from the parse trees. Third, a packed forest is generated using a variant of Earley's algorithm (Earley, 1970) starting from the unique root symbol. New hypotheses are selected by searching the best derivation in the forest. The grammar, a set of rules, is limited to those found in the parse trees. Spurious ambiguity during the generation step is further reduced by encoding the tree local contextual information in each non-terminal symbol, such as parent and sibling labels, using the state representation in Earley's algorithm.
Experiments were carried out for the system combination task of the fifth workshop on statistical machine translation (WMT10) in four directions, {Czech, French, German, Spanish}-to-English (Callison-Burch et al., 2010), and we found comparable performance to the conventional confusion network based system combination in two language pairs, and statistically significant improvements in the others.
First, we will review the state-of-the-art method which is a system combination framework based on confusion networks ( §2). Then, we will introduce a novel system combination method based on confusion forest ( §3) and present related work in consensus translations ( §4). Experiments are presented in Section 5 followed by discussion and our conclusion.

Combination by Confusion Network
The system combination framework based on confusion network starts from computing pairwise alignment between hypotheses by taking one hypothesis as a reference. Matusov et al. (2006) employs a model based approach in which a statistical word aligner, such as GIZA++ (Och and Ney, 2003), is used to align the hypotheses. Sim et al. (2007) introduced TER (Snover et al., 2006) to measure the edit-based alignment.
Then, one hypothesis is selected, for example by employing a minimum Bayes risk criterion (Sim et al., 2007), as a skeleton, or a backbone, which serves as a building block for aligning the rest of the hypotheses. Other hypotheses are aligned against the skeleton using the pairwise alignment. Figure 1 (b) illustrates an example of a confusion network constructed from the four hypotheses in Figure 1(a), assuming the first hypothesis is selected as our skeleton. The network consists of several arcs, each of which represents an alternative word at that position, including the empty symbol, ϵ.
This pairwise alignment strategy is prone to spurious insertions and repetitions due to alignment errors such as in Figure 1(a) in which "green" in the third hypothesis is aligned with "forest" in the skeleton. Rosti et al. (2008) Figure 1: An example confusion network construction skeleton hypothesis. In our example, "green trees" is aligned with "blue forest" in Figure 1(c).
The confusion network construction is largely influenced by the skeleton selection, which determines the global word reordering of a new hypothesis. For example, the last hypothesis in Figure 1(a) has a passive voice grammatical construction while the others are active voice. This large grammatical difference may produce a longer sentence with spuriously inserted words, as in "I saw the blue trees was found" in Figure 1(c). Rosti et al. (2007b) partially resolved the problem by constructing a large network in which each hypothesis was treated as a skeleton and the multiple networks were merged into a single network.

Combination by Confusion Forest
The confusion network approach to system combination encodes multiple hypotheses into a compact lattice structure by using word-level consensus. Likewise, we propose to encode multiple hypotheses into a confusion forest, which is a packed forest which represents multiple parse trees in a polynomial space (Billot and Lang, 1989;Mi et al., 2008)   ments among parse trees. The forest is represented as a hypergraph which is exploited in parsing (Klein and Manning, 2001;Huang and Chiang, 2005) and machine translation (Chiang, 2007;Huang and Chiang, 2007). More formally, a hypergraph is a pair ⟨V, E⟩ where V is the set of nodes and E is the set of hyperedges. Each node in V is represented as X @p where X ∈ N is a non-terminal symbol and p is an address (Shieber et al., 1995) that encapsulates each node id relative to its parent. The root node is given the address ϵ and the address of the first child of node p is given p.1. Each hyperedge e ∈ E is represented as a pair ⟨head(e), tails(e)⟩ where head(e) ∈ V is a head node and tails(e) ∈ V * is a list of tail nodes, corresponding to the left-hand side and the right-hand side of an instance of a rule in a CFG, respectively. Figure 2 presents an example packed forest for the parsed hypotheses in Figure 1(a). For example, VP @2 has two hyperedges, ⟨VP @2 , ( VBD @3 , VP @4 ) ⟩ and ⟨VP @2 , ( VBD @2.1 , NP @2.2 ) ⟩, leading to different derivations where the former takes the grammatical construction in passive voice while the latter in active voice.
Given system outputs, we employ the following grammar based approach for constructing a confusion forest: First, MT outputs are parsed. Second, Initialization: Figure 3: The deductive system for Earley's generation algorithm a grammar is learned by treating each hyperedge as an instance of a CFG rule. Third, a forest is generated from the unique root symbol of the extracted grammar through non-terminal rewriting.

Forest Generation
Given the extracted grammar, we apply a variant of Earley's algorithm (Earley, 1970) which can generate strings in a left-to-right manner from the unique root symbol, TOP. Figure 3 presents the deductive inference rules (Goodman, 1999) for our generation algorithm. We use capital letters X ∈ N to denote non-terminals and x ∈ T for terminals. Lowercase Greek letters α, β and γ are strings of terminals and non-terminals (T ∪ N ) * . u and v are weights associated with each item. The major difference compared to Earley's parsing algorithm is that we ignore the terminal span information each non-terminal covers and keep track of the height of derivations by h. The scanning step will always succeed by moving the dot to the right. Combined with the prediction and completion steps, our algorithm may potentially generate a spuriously deep forest. Thus, the height of the forest is constrained in the prediction step not to exceed H, which is empirically set to 1.5 times the maximum height of the parsed system outputs.

Tree Annotation
The grammar compiled from the parsed trees is local in that it can represent a finite number of sentences translated from a specific input sentence. Although its coverage is limited, our generation algorithm may yield a spuriously large forest. As a way to reduce spurious ambiguities, we relabel the nonterminal symbols assigned to each parse tree before extracting rules.
Here, we replace each non-terminal symbol by the state representation of Earley's algorithm corresponding to the sequence of prediction steps starting from TOP. Figure 4(a) presents an example parse tree with each symbol replaced by the Earley's state in Figure 4 (Klein and Manning, 2003). We define the vertical order v in which the label is limited to memorize only v previous prediction steps. For instance, setting v = 1 yields NP : •VP + •VBD : NP in our example. Likewise, we introduce the horizontal order h which limits the number of sibling labels memorized on the left and the right of the dotted label. Limiting h = 1 implies that each deductive step is encoded with at most three symbols.
No limits in the horizontal and vertical Markovization orders implies memorizing of all the deductions and yields a confusion forest representing the union of parse trees through the grammar collection and the generation processes. More relaxed horizontal orders allow more reordering of subtrees in a confusion forest by discarding the sibling context in each prediction step. Likewise, constraining the vertical order generates a deeper forest by ignoring the sequence of symbols leading to a particular node.

Forest Rescoring
From the packed forest F , new k-best derivations are extracted from all possible derivations D by efficient forest-based algorithms for k-best parsing (Huang and Chiang, 2005). We use a linear combi- where h(d, F ) is a set of feature functions scaled by weight vector w. We use cube-pruning (Chiang, 2007;Huang and Chiang, 2007) to approximately intersect with non-local features, such as n-gram language models. Then, k-best derivations are extracted from the rescored forest using algorithm 3 of Huang and Chiang (2005).

Related Work
Consensus translations have been extensively studied with many granularities. One of the simplest forms is a sentence-based combination in which hypotheses are simply reranked without merging (Nomoto, 2004). Frederking and Nirenburg (1994) proposed a phrasal combination by merging hypotheses in a chart structure, while others depended on confusion networks, or similar structures, as a building block for merging hypotheses at the word level (Bangalore et al., 2001;Matusov et al., 2006;He et al., 2008;Jayaraman and Lavie, 2005;Sim et al., 2007). Our work is the first to explicitly exploit syntactic similarity for system combination by merging hypotheses into a syntactic packed forest. The confusion forest approach may suffer from parsing errors such as the confusion network construction influenced by alignment errors. Even with parsing errors, we can still take a tree fragment-level consensus as long as a parser is consistent in that similar syntactic mistakes would be made for similar hypotheses. Rosti et al. (2007a) describe a re-generation approach to consensus translation in which a phrasal translation table is constructed from the MT outputs aligned with an input source sentence. New translations are generated by decoding the source sentence again using the newly extracted phrase table. Our grammar-based approach can be regarded as a regeneration approach in which an off-the-shelf monolingual parser, instead of a word aligner, is used to annotate syntactic information to each hypothesis, then, a new translation is generated from the merged forest, not from the input source sentence through decoding. In terms of generation, our approach is an instance of statistical generation (Langkilde and Knight, 1998;Langkilde, 2000). Instead of generating forests from semantic representations (Langkilde, 2000), we generate forests from a CFG encoding the consensus among parsed hypotheses. Liu et al. (2009) present joint decoding in which a translation forest is constructed from two distinct MT systems, tree-to-string and string-to-string, by merging forest outputs. Their merging method is either translation-level in which no new translation is generated, or derivation-level in that the rules sharing the same left-hand-side are used in both systems. While our work is similar in that a new forest is constructed by sharing rules among systems, although their work involves no consensus translation and requires structures internal to each system such as model combinations (DeNero et al., 2010).  (Klein and Manning, 2003), and lower-cased. We implemented our confusion forest system combination using an in-house developed hypergraph-based toolkit cicada which is motivated by generic weighted logic programming (Lopez, 2009), originally developed for a synchronous-CFG based machine translation system (Chiang, 2007). Input to our system is a collection of hypergraphs, a set of parsed hypotheses, from which rules are extracted and a new forest is generated as described in Section 3. Our baseline, also implemented in cicada, is a confusion network-based system combination method ( §2) which incrementally aligns hypotheses to the growing network using TER (Rosti et al., 2008) and merges multiple networks into a large single network. After performing epsilon removal, the network is transformed into a forest by parsing with monotone rules of S → X, S → S X and X → x. k-best translations are extracted from the forest using the forest-based algorithms in Section 3.3.

Features
The feature weight vector w in Equation 1 is tuned by MERT over hypergraphs (Kumar et al., 2009).
We use three lower-cased 5-gram language mod-els h i lm (d): English Gigaword Fourth edition 1 , the English side of French-English 10 9 corpus and the news commentary English data 2 . The count based features h t (d) and h e (d) count the number of terminals and the number of hyperedges in d, respectively. We employ M confidence measures h m s (d) for M systems, which basically count the number of rules used in d originally extracted from mth system hypothesis (Rosti et al., 2007a).
Following Macherey and Och (2007), BLEU (Papineni et al., 2002) correlations are also incorporated in our system combination. ) where e = yield(d) is a terminal yield of d, BP (·) and ρ n (·) respectively denote brevity penalty and n-gram precision. Here, we use approximated unclipped n-gram counts (Dreyer et al., 2007) for computing ρ n (·) with a compact state representation (Li and Khudanpur, 2009). Our baseline confusion network system has an additional penalty feature, h p (m), which is the total edits required to construct a confusion network using the mth system hypothesis as a skeleton, normalized by the number of nodes in the network (Rosti et al., 2007b).

Results
Table 2 compares our confusion forest approach (CF) with different orders, a confusion network (CN) and max/min systems measured by BLEU (Papineni et al., 2002). We vary the horizontal orders, h = 1, 2, ∞ with vertical orders of v = 3, 4, ∞. Systems without statistically significant differences from the best result (p < 0.05) are indicated by bold face. Setting v = ∞ and h = ∞ achieves comparable performance to CN. Our best results in three languages come from setting v = ∞ and h = 2, which favors little reordering of phrasal structures. In general, lower horizontal and vertical order leads to lower BLEU.
org/wmt10/.    Table 3 presents oracle BLEU achievable by each combination method. The gains achievable by the CF over simple reranking are small, at most 2-3 points, indicating that small variations are encoded in confusion forests. We also observed that a lower horizontal and vertical order leads to better BLEU potentials. As briefly pointed out in Section 3.2, the higher horizontal and vertical order implies more faithfulness to the original parse trees. Introducing new tree fragments to confusion forests leads to new phrasal translations with enlarged forests, as presented in Table 4  of hyperedges 3 . The larger potentials do not imply better translations, probably due to the larger search space with increased search errors. We also conjecture that syntactic variations were not captured by the n-gram like string-based features in Section 5.2, therefore resulting in BLEU loss, which will be investigated in future work. In contrast, CN has more potential for generating better translations, with the exception of the German-to-English direction, with scores that are usually 10 points better than simple sentence-wise reranking. The low potential in German should be interpreted in the light of the extremely large confusion network in Table 4. We postulate that the divergence in German hypotheses yields wrong alignments, and therefore amounts to larger networks with incorrect hypotheses. Table 4 also shows that CN produces a forest that is an order of magnitude larger than those created by CFs. Although we cannot directly relate the runtime and the number of hyperedges in CN and CFs, since the shape of the forests are different, CN requires more space to encode the hypotheses than those by CFs. Table 5 compares the average length of the minimum/maximum hypothesis that each method can produce. CN may generate shorter hypotheses, whereby CF prefers longer hypotheses as we decrease the vertical order. Large divergence is also observed for German, such as for hypergraph size.

Conclusion
We presented a confusion forest based method for system combination in which system outputs are merged into a packed forest using their syntactic 3 We measure the hypergraph size before intersecting with non-local features, like n-gram language models. language cz-en de-en es-en fr similarity. The forest construction is treated as a generation from a CFG compiled from the parsed outputs. Our experiments indicate comparable performance to a strong confusion network baseline with smaller space, and statistically significant gains in some language pairs. To our knowledge, this is the first work to directly introduce syntactic consensus to system combination by encoding multiple system outputs into a single forest structure. We believe that the confusion forest based approach to system combination has future exploration potential. For instance, we did not employ syntactic features in Section 5.2 which would be helpful in discriminating hypotheses in larger forests. We would also like to analyze the trade-offs, if any, between parsing errors and confusion forest constructions by controlling the parsing qualities. As an alternative to the grammar-based forest generation, we are investigating an edit distance measure for tree alignment, such as tree edit distance (Bille, 2005) which basically computes insertion/deletion/replacement of nodes in trees.