Using Discourse Structure Improves Machine Translation Evaluation

In Rhetorical Structure Theory, discourse analysis involves two subtasks: (i) discourse segmentation, or breaking the text into a sequence of EDUs, and (ii) discourse parsing, or the task of linking the units (EDUs and larger discourse units) into labeled discourse trees. Recently, proposed discriminative models for both discourse segmentation and discourse parsing at the sentence level. The segmenter uses a maximum entropy model that achieves state-of-the-art accuracy on this task, having an $F_1$-score of $90.5\mathrm{\%}$, while human agreement is $98.3\mathrm{\%}$.

The discourse parser uses a dynamic Conditional Random Field [] as a parsing model in order to infer the probability of all possible discourse tree constituents. The inferred (posterior) probabilities are then used in a probabilistic CKY-like bottom-up parsing algorithm to find the most likely DT. Using the standard set of 18 coarse-grained relations defined in [], the parser achieved an $F_1$-score of 79.8%, which is very close to the human agreement of 83%. These high scores allowed us to develop successful discourse similarity metrics.²²The discourse parser is freely available from http://alt.qcri.org/tools/

A number of metrics have been proposed to measure the similarity between two labeled trees, e.g., Tree Edit Distance [] and Tree Kernels []. Tree kernels (TKs) provide an effective way to integrate arbitrary tree structures in kernel-based machine learning algorithms like SVMs.

In the present work, we use the convolution TK defined in [], which efficiently calculates the number of common subtrees in two trees. Note that this kernel was originally designed for syntactic parsing, where the subtrees are subject to the constraint that their nodes are taken with either all or none of the children. This constraint of the TK imposes some limitations on the type of substructures that can be compared.

One way to cope with the limitations of the TK is to change the representation of the trees to a form that is suitable to capture the relevant information for our task. We experiment with TKs applied to two different representations of the discourse tree: non-lexicalized (DR), and lexicalized (DR-lex). In Figure 7 we show the two representations for the subtree that spans the text: “suggest the ECB should be the lender of last resort”, which is highlighted in Figure 4.

As shown in Figure 7, DR does not include any lexical item, and therefore measures the similarity between two translations in terms of their discourse structures only. On the contrary, DR-lex includes the lexical items to account for lexical matching; moreover, it separates the structure (the skeleton) of the tree from its labels, i.e. the nuclearity and the relations, in order to allow the tree kernel to give partial credit to subtrees that differ in labels but match in their skeletons. More specifically, it uses the tags SPAN and EDU to build the skeleton of the tree, and considers the nuclearity and/or the relation labels as properties, added as children, of these tags.

For example, a SPAN has two properties (its nuclearity and its relation), and an EDU has one property (its nuclearity). The words of an EDU are placed under the predefined children NGRAM. In order to allow the tree kernel to find subtree matches at the word level, we include an additional layer of dummy leaves as was done in []; not shown in Figure 7, for simplicity.

In this study, we evaluate to what extent existing evaluation metrics can benefit from additional discourse information. To do so, we contrast different MT evaluation metrics with and without discourse information. The evaluation metrics we used are described below.

The human-annotated data from the WMT campaigns encompasses series of rankings on the output of different MT systems for every source sentence. Annotators rank the output of five systems according to perceived translation quality. The organizers relied on a random selection of systems, and a large number of comparisons between pairs of them, to make comparisons across systems feasible []. As a result, for each source sentence, only relative rankings were available. As in the WMT12 experimental setup, we use these rankings to calculate correlation with human judgments at the sentence-level, i.e. Kendall’s Tau; see [] for details.

For the experiments reported in Section 5.4, we used pairwise rankings to discriminatively learn the weights of the linear combinations of individual metrics. In order to use the WMT12 data for training a learning-to-rank model, we transformed the five-way relative rankings into ten pairwise comparisons. For instance, if a judge ranked the output of systems $A$, $B$, $C$, $D$, $E$ as $A>B>C>D>E$, this would entail that $A>B$, $A>C$, $A>D$ and $A>E$, etc.

To determine the relative weights for the tuned combinations, we followed a similar approach to the one used by PRO to tune the relative weights of the components of a log-linear SMT model [], also using Maximum Entropy as the base learning algorithm. Unlike PRO, (i)  we use human judgments, not automatic scores, and (ii)  we train on all pairs, not on a subsample.

In our experiments, we only consider translation into English, and use the data described in Table 1. For evaluation, we follow the setup of the metrics task of WMT12 []: at the system-level, we use the official script from WMT12 to calculate the Spearman’s correlation, where higher absolute values indicate better metrics performance; at the segment-level, we use Kendall’s Tau for measuring correlation, where negative values are worse than positive ones.⁷⁷We have fixed a bug in the scoring tool from WMT12, which was making all scores positive. This made TerrorCat’s score negative, as we present it in Table 3.

In our experiments, we combine DR and DR-lex to other metrics in two different ways: using uniform linear interpolation (at system- and segment-level), and using a tuned linear interpolation for the segment-level. We only present the average results over all four language pairs. For simplicity, in our tables we show results divided into evaluation groups:

1. 1.

   Group I: contains our evaluation metrics, DR and DR-lex.

2. 2.

   Group II: includes the metrics that participated in the WMT12 metrics task, excluding metrics which did not have results for all language pairs.

3. 3.

   Group III: contains other important evaluation metrics, which were not considered in the WMT12 metrics task: NIST and Rouge for both system- and segment-level, and BLEU and TER at segment-level.

4. 4.

   Group IV: includes the metric combinations calculated with Asiya and described in Section 4.

For each metric in groups II, III and IV, we present the results for the original metric as well for the linear interpolation of that metric with DR and with DR-lex. The combinations with DR and DR-lex that improve over the original metrics are shown in bold, and those that degrade are in italic. Furthermore, we also present overall results for: (i) the average score over all metrics, excluding DR and DR-lex, and (ii) the differences in the correlations for the DR/DR-lex-combined and the original metrics.

Table 2 shows the system-level experimental results for WMT12. We can see that DR is already competitive by itself: on average, it has a correlation of .807, very close to BLEU and TER scores (.810 and .812, respectively). Moreover, DR yields improvements when combined with 15 of the 19 metrics; worsening only four of the metrics. Overall, we observe an average improvement of +.024, in the correlation with the human judgments. This suggests that DR contains information that is complementary to that used by the other metrics. Note that this is true both for the individual metrics from groups II and III, as well as for the metric combinations in group IV. Combinations in the last group involve several metrics that already use linguistic information at different levels and are hard to improve over; yet, adding DR does improve, which shows that it has some complementary information to offer.

As expected, DR-lex performs better than DR since it is lexicalized (at the unigram level), and also gives partial credit to correct structures. Individually, DR-lex outperforms most of the metrics from group II, and ranks as the second best metric in that group. Furthermore, when combined with individual metrics in group II, DR-lex is able to improve consistently over each one of them.

Note that, even though DR-lex has better individual performance than DR, it does not yield improvements when combined with most of the metrics in group IV.⁸⁸In this work, we have not investigated the reasons behind this phenomenon. We speculate that this might be caused by the fact that the lexical information in DR-lex is incorporated only in the form of unigram matching at the sentence-level, while the metrics in group IV are already complex combined metrics, which take into account stronger lexical models. Note, however, that the variations are very small and might not be significant. However, over all metrics and all language pairs, DR-lex is able to obtain an average improvement in correlation of +.035, which is remarkably higher than that of DR. Thus, we can conclude that at the system-level, adding discourse information to a metric, even using the simplest of the combination schemes, is a good idea for most of the metrics, and can help to significantly improve the correlation with human judgments.

Table 3 shows the results for WMT12 at the segment-level. We can see that DR performs badly, with a high negative Kendall’s Tau of -.433. This should not be surprising: (a) the discourse tree structure alone does not contain enough information for a good evaluation at the segment-level, and (b) this metric is more sensitive to the quality of the DT, which can be wrong or void.

Additionally, DR is more likely to produce a high number of ties, which is harshly penalized by WMT12’s definition of Kendall’s Tau. Conversely, ties and incomplete discourse analysis were not a problem at the system-level, where evidence from all 3,003 test sentences is aggregated, and allows to rank systems more precisely. Due to the low score of DR as an individual metric, it fails to yield improvements when uniformly combined with other metrics.

Again, DR-lex is better than DR; with a positive Tau of +.133, yet as an individual metric, it ranks poorly compared to other metrics in group II. However, when linearly combined with other metrics, DR-lex outperforms 14 of the 19 metrics in Table 3. Across all metrics, DR-lex yields an average Tau improvement of +.026, i.e. from .165 to .190. This is a large improvement, taking into account that the combinations are just uniform linear combinations. In subsection 5.4, we present the results of tuning the linear combination in a discriminative way.

We experimented with tuning the weights of the individual metrics in the metric combinations, using the learning method described in Section 4.2. First, we did this using cross-validation to tune and test on WMT12. Later we tuned on WMT12 and evaluated on WMT11. For cross-validation in WMT12, we used ten folds of approximately equal sizes, each containing about 300 sentences: we constructed the folds by putting together entire documents, thus not allowing sentences from a document to be split over two different folds. During each cross-validation run, we trained our pairwise ranker using the human judgments corresponding to nine of the ten folds. We aggregated the data for different language pairs, and produced a single set of tuning weights for all language pairs.⁹⁹Tuning separately for each language pair yielded slightly lower results. We then used the remaining fold for evaluation

The results are shown in Table 4. As in previous sections we present the average results over all four language pairs. We can see that the tuned combinations with DR-lex improve over most of the individual metrics in groups II and III. Interestingly, the tuned combinations that include the much weaker metric DR now improve over 12 out of 13 of the individual metrics in groups II and III, and only slightly degrades the score of the 13th one (spede07pP).

Note that the Asiya metrics are combinations of several metrics, and these combinations (which exclude DR and DR-lex) can be also tuned; this yields sizable improvements over the untuned versions as column three in the table shows. Compared to this baseline, DR improves for three of the six Asiya metrics, while DR-lex improves for four of them. Note that improving over the last two Asiya metrics is very hard: they have very high scores of .296 and .295; for comparison, the best segment-level system at WMT12 (spede07pP) achieved a Tau of .254.

On average, DR improves Tau from .165 to .201, which is +.036, while DR-lex improves to .222, or +.057. These much larger improvements highlight the importance of tuning the linear combination when working at the segment-level.