{'fraction_non_alphanumeric': 0.03557030068872837, 'fraction_numerical': 0.012094742146816731, 'mean_word_length': 4.522495361781076, '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}}
Two Languages are Better than One (for Syntactic Parsing)

We show that jointly parsing a bitext can substantially improve parse quality on both sides. In a maximum entropy bitext parsing model, we define a distribution over source trees, target trees, and node-to-node alignments between them. Features include monolingual parse scores and various measures of syntactic divergence. Using the translated portion of the Chinese treebank, our model is trained iteratively to maximize the marginal likelihood of training tree pairs, with alignments treated as latent variables. The resulting bitext parser outperforms state-of-the-art monolingual parser baselines by 2.5 F1 at predicting English side trees and 1.8 F1 at predicting Chinese side trees (the highest published numbers on these corpora). Moreover, these improved trees yield a 2.4 BLEU increase when used in a downstream MT evaluation.


Introduction
Methods for machine translation (MT) have increasingly leveraged not only the formal machinery of syntax (Wu, 1997;Chiang, 2007;Zhang et al., 2008), but also linguistic tree structures of either the source side (Huang et al., 2006;Marton and Resnik, 2008;Quirk et al., 2005), the target side (Yamada and Knight, 2001;Galley et al., 2004;Zollmann et al., 2006;Shen et al., 2008), or both (Och et al., 2003;Aue et al., 2004;Ding and Palmer, 2005). These methods all rely on automatic parsing of one or both sides of input bitexts and are therefore impacted by parser quality. Unfortunately, parsing general bitexts well can be a challenge for newswiretrained treebank parsers for many reasons, including out-of-domain input and tokenization issues.
On the other hand, the presence of translation pairs offers a new source of information: bilingual constraints. For example, Figure 1 shows a case where a state-of-the-art English parser (Petrov and Klein, 2007) has chosen an incorrect structure which is incompatible with the (correctly chosen) output of a comparable Chinese parser. Smith and Smith (2004) previously showed that such bilingual constraints can be leveraged to transfer parse quality from a resource-rich language to a resourceimpoverished one. In this paper, we show that bilingual constraints and reinforcement can be leveraged to substantially improve parses on both sides of a bitext, even for two resource-rich languages.
Formally, we present a log-linear model over triples of source trees, target trees, and node-tonode tree alignments between them. We consider a set of core features which capture the scores of monolingual parsers as well as measures of syntactic alignment. Our model conditions on the input sentence pair and so features can and do reference input characteristics such as posterior distributions from a word-level aligner DeNero and Klein, 2007).
Our training data is the translated section of the Chinese treebank (Xue et al., 2002;Bies et al., 2007), so at training time correct trees are observed on both the source and target side. Gold tree alignments are not present and so are induced as latent variables using an iterative training procedure. To make the process efficient and modular to existing monolingual parsers, we introduce several approximations: use of k-best lists in candidate generation, an adaptive bound to avoid considering all k 2 combinations, and Viterbi approximations to alignment posteriors. Figure 1: Two possible parse pairs for a Chinese-English sentence pair. The parses in a) are chosen by independent monolingual statistical parsers, but only the Chinese side is correct. The gold English parse shown in b) is further down in the 100-best list, despite being more consistent with the gold Chinese parse. The circles show where the two parses differ. Note that in b), the ADVP and PP nodes correspond nicely to Chinese tree nodes, whereas the correspondence for nodes in a), particularly the SBAR node, is less clear. We evaluate our system primarily as a parser and secondarily as a component in a machine translation pipeline. For both English and Chinese, we begin with the state-of-the-art parsers presented in Petrov and Klein (2007) as a baseline. Joint parse selection improves the English trees by 2.5 F 1 and the Chinese trees by 1.8 F 1 . While other Chinese treebank parsers do not have access to English side translations, this Chinese figure does outperform all published monolingual Chinese treebank results on an equivalent split of the data.
As MT motivates this work, another valuable evaluation is the effect of joint selection on downstream MT quality. In an experiment using a syntactic MT system, we find that rules extracted from joint parses results in an increase of 2.4 BLEU points over rules extracted from independent parses. 1 In sum, jointly parsing bitexts improves parses substantially, and does so in a way that that carries all the way through the MT pipeline.

Model
In our model, we consider pairs of sentences (s, s ), where we use the convention that unprimed variables are source domain and primed variables are target domain. These sentences have parse trees t (respectively t ) taken from candidate sets T (T ).
Non-terminal nodes in trees will be denoted by n (n ) and we abuse notation by equating trees with their node sets. Alignments a are simply at-mostone-to-one matchings between a pair of trees t and t (see Figure 2a for an example). Note that we will also mention word alignments in feature definitions; a and the unqualified term alignment will always refer to node alignments. Words in a sentence are denoted by v (v ).
Our model is a general log-linear (maximum entropy) distribution over triples (t, a, t ) for sentence pairs (s, s ): P(t, a, t|s, s ) ∝ exp(w φ(t, a, t )) Features are thus defined over (t, a, t ) triples; we discuss specific features below.

Features
To use our model, we need features of a triple (t, a, t ) which encode both the monolingual quality of the trees as well as the quality of the alignment between them. We introduce a variety of features in the next sections.

Monolingual Features
To capture basic monolingual parse quality, we begin with a single source and a single target feature whose values are the log likelihood of the source tree t and the target tree t , respectively, as given by our baseline monolingual parsers. These two features are called SOURCELL and TARGETLL respectively. It is certainly possible to augment these simple features with what would amount to monolingual reranking features, but we do not explore that option here. Note that with only these two features, little can be learned: all positive weights w cause the jointly optimal parse pair (t, t ) to comprise the two top-1 monolingual outputs (the baseline).

Word Alignment Features
All other features in our model reference the entire triple (t, a, t ). In this work, such features are defined over aligned node pairs for efficiency, but generalizations are certainly possible.
Bias: The first feature is simply a bias feature which has value 1 on each aligned node pair (n, n ). This bias allows the model to learn a general preference for denser alignments.
Alignment features: Of course, some alignments are better than others. One indicator of a good nodeto-node alignment between n and n is that a good word alignment model thinks that there are many word-to-word alignments in their bispan. Similarly, there should be few alignments that violate that bispan. To compute such features, we define a(v, v ) to be the posterior probability assigned to the word alignment between v and v by an independent word aligner. 2 Before defining alignment features, we need to define some additional variables. For any node n ∈ t (n ∈ t ), the inside span i(n) (i(n )) comprises the input tokens of s (s ) dominated by that node. Similarly, the complement, the outside span, will be denoted o(n) (o(n )), and comprises the tokens not dominated by that node. See Figure 2b,c for examples of the resulting regions.
Hard alignment features: We also define the hard versions of these features, which take counts from the word aligner's hard top-1 alignment output δ: Scaled alignment features: Finally, undesirable larger bispans can be relatively sparse at the word alignment level, yet still contain many good word alignments simply by virtue of being large. We therefore define a scaled count which measures density rather than totals. The geometric mean of span lengths was a superior measure of bispan "area" than the true area because word-level alignments tend to be broadly one-to-one in our word alignment model.
Head word alignment features: When considering a node pair (n, n ), especially one which dominates a large area, the above measures treat all spanned words as equally important. However, lexical heads are generally more representative than other spanned words. Let h select the headword of a node according to standard head percolation rules (Collins, 2003;Bikel and Chiang, 2000).

Tree Structure Features
We also consider features that measure correspondences between the tree structures themselves.
Span difference: We expect that, in general, aligned nodes should dominate spans of roughly the same length, and so we allow the model to learn to penalize node pairs whose inside span lengths differ greatly.

Number of children:
We also expect that there will be correspondences between the rules of the CFGs that generate the trees in each language. To encode some of this information, we compute indicators of the number of children c that the nodes have in t and t .
NUMCHILDREN |c(n)|, |c(n )| = 1 Child labels: In addition, we also encode whether certain label pairs occur as children of matched nodes. Let c(n, ) select the children of n with label .
CHILDLABEL , = |c(n, )| · |c(n , )| Note that the corresponding "self labels" feature is not listed because it arises in the next section as a typed variant of the bias feature.

Typed vs untyped features
For each feature above (except monolingual features), we create label-specific versions by conjoining the label pair ( (n), (n )). We use both the typed and untyped variants of all features.

Training
Recall that our data condition supplies sentence pairs (s, s ) along with gold parse pairs (g, g ). We do not observe the alignments a which link these parses. In principle, we want to find weights which maximize the marginal log likelihood of what we do observe given our sentence pairs: 3 There are several challenges. First, the space of symmetric at-most-one-to-one matchings is #P-hard to sum over exactly (Valiant, 1979). Second, even without matchings to worry about, standard methods for maximizing the above formulation would require summation over pairs of trees, and we want to assume a fairly generic interface to independent monolingual parsers (though deeper joint modeling and/or training is of course a potential extension).
As we have chosen to operate in a reranking mode over monolingual k-best lists, we have another issue: our k-best outputs on the data which trains our model may not include the gold tree pair. We therefore make several approximations and modifications, which we discuss in turn.

Viterbi Alignments
Because summing over alignments a is intractable, we cannot evaluate (2) or its derivatives. However, if we restrict the space of possible alignments, then we can make this optimization more feasible. One way to do this is to stipulate in advance that for each tree pair, there is a canonical alignment a 0 (t, t ). Of course, we want a 0 to reflect actual correspondences between t and t , so we want a reasonable definition that ensures the alignments are of reasonable quality. Fortunately, it turns out that we can efficiently optimize a given a fixed tree pair and weight vector: This optimization requires only that we search for an optimal alignment. Because all our features can be factored to individual node pairs, this can be done with the Hungarian algorithm in cubic time. 4 Note that we do not enforce any kind of domination consistency in the matching: for example, the optimal alignment might in principle have the source root aligning to a target non-root and vice versa. We then define a 0 (t, t ) as the alignment that maximizes w 0 φ(t, a, t ), where w 0 is a fixed initial weight vector with a weight of 1 for INSIDEBOTH, -1 for INSRCOUTTRG and INTRGOUTSRC, and 0 4 There is a minor modification to allow nodes not to match. Any alignment link which has negative score is replaced by a zero-score link, and any zero-score link in the solution is considered a pair of unmatched nodes. for all other features. Then, we simplify (2) by fixing the alignments a 0 : This optimization has no latent variables and is therefore convex and straightforward. However, while we did use this as a rapid training procedure during development, fixing the alignments a priori is both unsatisfying and also less effective than a procedure which allows the alignments a to adapt during training.
Again, for fixed alignments a, optimizing w is easy. Similarly, with a fixed w, finding the optimal a for any particular tree pair is also easy. Another option is therefore to use an iterative procedure that alternates between choosing optimal alignments for a fixed w, and then reoptimizing w for those fixed alignments according to (3). By iterating, we perform the following optimization: Note that (4) is just (2) with summation replaced by maximization. Though we do not know of any guarantees for this EM-like algorithm, in practice it converges after a few iterations given sufficient training data. We initialize the procedure by setting w 0 as defined above.

Pseudo-gold Trees
When training our model, we approximate the sets of all trees with k-best lists, T and T , produced by monolingual parsers. Since these sets are not guaranteed to contain the gold trees g and g , our next approximation is to define a set of pseudo-gold trees, following previous work in monolingual parse reranking (Charniak and Johnson, 2005). We definê T (T ) as the F 1 -optimal subset of T (T ). We then modify (4) to reflect the fact that we are seeking to maximize the likelihood of trees in this subset: where P(t, t |s, s , w) = max a exp(w φ(t, a, t )) (t,t )∈(T,T ) max a exp(w φ(t, a,t ))

Training Set Pruning
To reduce the time and space requirements for training, we do not always use the full k-best lists. To prune the set T , we rank all the trees in T from 1 to k, according to their log likelihood under the baseline parsing model, and find the rank of the least likely pseudo-gold tree: Finally, we restrict T based on rank: where is a free parameter of the pruning procedure. The restricted set T pruned is constructed in the same way. When training, we replace the sum over all tree pairs in (T, T ) in the denominator of (6) with a sum over all tree pairs in (T pruned , T pruned ).
The parameter can be set to any value from 0 to k, with lower values resulting in more efficient training, and higher values resulting in better performance. We set by empirically determining a good speed/performance tradeoff (see §6.2).

Joint Selection
At test time, we have a weight vector w and so selecting optimal trees for the sentence pair (s, s ) from a pair of k best lists, (T, T ) is straightforward. We just find: (t * , t * ) = arg max (t,t )∈(T,T ) max a P(t, a, t |s, s , w) = arg max (t,t )∈(T,T ) max a w φ(t, a, t ) Note that with no additional cost, we can also find the optimal alignment between t * and t * :

Test Set Pruning
Because the size of (T, T ) grows as O(k 2 ), the time spent iterating through all these tree pairs can grow unreasonably long, particularly when reranking a set of sentence pairs the size of a typical MT corpus. To combat this, we use a simple pruning technique to limit the number of tree pairs under consideration. To prune the list of tree pairs, first we rank them according to the metric: Then, we simply remove all tree pairs whose ranking falls below some empirically determined cutoff. As we show in §6.3, by using this technique we are able to speed up reranking by a factor of almost 20 without an appreciable loss of performance.

Statistical Parsing Experiments
All the data used to train the joint parsing model and to evaluate parsing performance were taken from articles 1-325 of the Chinese treebank, which all have English translations with gold-standard parse trees. The articles were split into training, development, and test sets according to the standard breakdown for Chinese parsing evaluations. Not all sentence pairs could be included for various reasons, including one-to-many Chinese-English sentence alignments, sentences omitted from the English translations, and low-fidelity translations. Additional sentence pairs were dropped from the training data because they had unambiguous parses in at least one of the two languages. Table 1 shows how many sentences were included in each dataset.
We had two training setups: rapid and full. In the rapid training setup, only 1000 sentence pairs from the training set were used, and we used fixed alignments for each tree pair rather than iterating (see §4.1). The full training setup used the iterative training procedure on all 2298 training sentence pairs. We used the English and Chinese parsers in Petrov and Klein (2007) 5 to generate all k-best lists and as our evaluation baseline. Because our bilingual data is from the Chinese treebank, and the data typically used to train a Chinese parser contains the Chinese side of our bilingual training data, we had to train a new Chinese grammar using only articles 400-1151 (omitting articles 1-270). This modified grammar was used to generate the k-best lists that we trained our model on. However, as we tested on the same set of articles used for monolingual Chinese parser evaluation, there was no need to use a modified grammar to generate k-best lists at test time, and so we used a regularly trained Chinese parser for this purpose.
We also note that since all parsing evaluations were performed on Chinese treebank data, the Chinese test sentences were in-domain, whereas the English sentences were very far out-of-domain for the Penn Treebank-trained baseline English parser. Hence, in these evaluations, Chinese scores tend to be higher than English ones.
Posterior word alignment probabilities were obtained from the word aligner of Liang et al. (2006) and DeNero and Klein (2007) 6 , trained on approximately 1.7 million sentence pairs. For our alignment model we used an HMM in each direction, trained to agree , and we combined the posteriors using DeNero and Klein's (2007) soft union method.
Unless otherwise specified, the maximum value of k was set to 100 for both training and testing, and all experiments used a value of 25 as the parameter for training set pruning and a cutoff rank of 500 for test set pruning.

Feature Ablation
To verify that all our features were contributing to the model's performance, we did an ablation study, removing one group of features at a time. Table 2 shows the F 1 scores on the bilingual development data resulting from training with each group of features removed. 7 Note that though head word features seemed to be detrimental in our rapid training setup, earlier testing had shown a positive effect, so we reran the comparison using our full training setup, where we again saw an improvement when including these features. 6 Available at http://nlp.cs.berkeley.edu. 7 We do not have a test with the basic alignment features removed because they are necessary to compute a0(t, t ).

Baseline Parsers Features
Ch F 1 Eng F

Training Set Pruning
To find a good value of the parameter for training set pruning we tried several different values, using our rapid training setup and testing on the dev set. The results are shown in Table 3. We selected 25 as it showed the best performance/speed tradeoff, on average performing as well as if we had done no pruning at all, while requiring only a quarter the memory and CPU time.

Test Set Pruning
We also tried several different values of the rank cutoff for test set pruning, using the full training setup  and testing on the dev set. The results are in Table 4. For F 1 evaluation, which is on a very small set of sentences, we selected 500 as the value with the best speed/performance tradeoff. However, when reranking our entire MT corpus, we used a value of 200, sacrificing a tiny bit of performance for an extra factor of 2 in speed. 8

Sensitivity to k
Since our bitext parser currently operates as a reranker, the quality of the trees is limited by the quality of the k-best lists produced by the baseline parsers. To test this limitation, we evaluated performance on the dev set using baseline k-best lists of varying length. Training parameters were fixed (full training setup with k = 100) and test set pruning was disabled for these experiments. The results are in Table 5. The relatively modest gains with increasing k, even as the oracle scores continue to improve, indicate that performance is limited more by the model's reliance on the baseline parsers than by search errors that result from the reranking approach.

Final Results
Our final evaluation was done using the full training setup. Here, we report F 1 scores on two sets of data. First, as before, we only include the sentence pairs from our bilingual corpus to fully demonstrate the gains made by joint parsing. We also report scores on the full test set to allow easier comparison with   past work on Chinese parsing. For the latter evaluation, sentences that were not in the bilingual corpus were simply parsed with the baseline parsers. The results are in Table 6. Joint parsing improves F 1 by 2.5 points on out-of-domain English sentences and by 1.8 points on in-domain Chinese sentences; this represents the best published Chinese treebank parsing performance, even after sentences that lack a translation are taken into account.

Machine Translation
To test the impact of joint parsing on syntactic MT systems, we compared the results of training an MT system with two different sets of trees: those produced by the baseline parsers, and those produced by our joint parser. For this evaluation, we used a syntactic system based on Galley et al. (2004) and Galley et al. (2006), which extracts tree-to-string transducer rules based on target-side trees. We trained the system on 150,000 Chinese-English sentence pairs from the training corpus of Wang et al. (2007), and used a large (close to 5 billion tokens) 4-gram lan-Baseline Joint Moses BLEU 18.7 21.1 18.8 Table 7: MT comparison on a syntactic system trained with trees output from either baseline monolingual parsers or our joint parser. To facilitate relative comparison, the Moses (Koehn et al., 2007) number listed reflects the default Moses configuration, including its full distortion model, and standard training pipeline.
guage model for decoding. We tuned and evaluated BLEU (Papineni et al., 2001) on separate held-out sets of sentences of up to length 40 from the same corpus. The results are in Table 7, showing that joint parsing yields a BLEU increase of 2.4. 9

Conclusions
By jointly parsing (and aligning) sentences in a translation pair, it is possible to exploit mutual constraints that improve the quality of syntactic analyses over independent monolingual parsing. We presented a joint log-linear model over source trees, target trees, and node-to-node alignments between them, which is used to select an optimal tree pair from a k-best list. On Chinese treebank data, this procedure improves F 1 by 1.8 on Chinese sentences and by 2.5 on out-of-domain English sentences. Furthermore, by using this joint parsing technique to preprocess the input to a syntactic MT system, we obtain a 2.4 BLEU improvement.