Exploiting Sentence Order in Document Alignment

In this work, we exploit the simple idea that a document and its translation should contain approximately the same information, in approximately the same order. We propose methods for both document pair candidate generation and candidate re-scoring which incorporate high-level order information. Our method results in 61% relative reduction in error versus the best previously published result on the WMT16 document alignment shared task. We also apply our method to web-scraped Sinhala-English documents from ParaCrawl and find that our method improves MT performance by 1.2 BLEU over the current ParaCrawl document alignment method.


Introduction
Document alignment is the task of finding parallel document pairs (i.e. documents which are translations of each other) from a large collection of documents, often crawled from the web. Aligned documents have historically been used to produce sentence-level machine translation (MT) data, but there is also recent interest in training on documents directly to improve document-level coherence (Junczys-Dowmunt, 2019).
In this work, we exploit the simple idea that two parallel documents should each contain approximately the same information, in approximately the same order. This idea can be traced back at least to the late 1990s, when STRAND (Resnik, 1998) measured how well linearized HTML tags from two documents could be aligned in order to judge whether two web pages were likely parallel. 1 However, in subsequent work, high-level order has largely taken a backseat to unordered representations for documents including bag-of-words, bagof-N-grams, and averages of sentence embeddings.
We propose a simple method for embedding documents into a joint semantic embedding space (Berry and Young, 1995;Germann, 2016), in a manner which encodes high-level document content order, enabling candidate generation via fast approximate nearest neighbor search. We propose re-scoring those candidate pairs by performing sentence alignment and then scoring that alignment based on the semantic similarity of the resulting sentence pairs, whether the sentence pairs are in the correct languages, and the number of inserted/deleted sentences.
Our method results in 61% relative reduction in the false positive rate on the WMT16 document alignment shared task versus the best previously reported method. Applied to Sinhala-English ParaCrawl 2 data, it improves MT performance by 1.2 BLEU over Buck and Koehn (2016b).

Method
We follow a 2-stage approach to consider the D S * D T possible alignments between D S source documents and D T target documents: 1. Candidate Generation: We first find a fixed number K of target documents as potential matches for each source document. 2. Candidate Re-scoring: We re-score the D S * K document pairs from part 1 using a slower, but more accurate, scoring method. In particular, we propose (1) a document embedding method to enable fast approximate nearestneighbor search to find generate candidate document pairs; and (2) a scoring method to re-score candidate document pairs. Each part explicitly models both the content of a document and the order of that content in the document.

Candidate Generation
We propose the concatenation of several subvectors, each representing a different section of the document, as multilingual document vector. Each sub-vector is a weighted average of multilingual sentence embeddings for the sentences in the given document. Sentences embedding are weighted with a function to emphasize the region of the document that the sub-vector represents, and a function to de-emphasize boilerplate text (Kohlschütter et al., 2010) such as text from navigational buttons, pulldown menus, or headers.
Let S i for i ∈ {1, ..., N } be the N sentences in a given document, and let emb(S i ) be the embedding of sentence S i . We compute sub-vectors V j for uniformly spaced positions j ∈ {1, ..., J} in the document as follows: For H j (i), the function to emphasize position j in the document, we use the modified PERT distribution (Malcolm et al., 1959;Vose, 2000) with support over [1, J] and mode j. For B(S i ), the function to de-emphasize boilerplate text, we simply downweight common sentences -see Appendix A. The final document vector V is a concatenation of the position-weighted sub-vectors: Vectors are compared using cosine distance. We compare all documents within each webdomain 3 using approximate nearest neighbor search.

Candidate Re-scoring
To re-score a document pair proposed by candidate generation, we perform sentence alignment and score the quality of the resulting sentence alignment in order to judge whether the proposed document pair appears to be a good translation pair. Our work is enabled by two recent advances: (1) cosine similarity of multilingual sentence embeddings (Schwenk and Douze, 2017;Guo et al., 2018a) provide fast and accurate judgments of semantic similarity of sentences in different languages and (2) Vecalign (Thompson and Koehn, 2019), in conjunction with a multilingual embedding method, provides accurate sentence alignment in linear time complexity. Together, these enable us to quickly align and score a large number of potential document pairs, between any languages supported by the multilingual embedder.
One artifact of using multilingual sentence embeddings is that they give perfect alignment scores to exact, un-translated sentence copies. Since automatic language identification (LID) of web data is often erroneous and not well defined, 4 this can result in un-translated, (near) duplicate documents being found as document pairs. To address this issue, we use sentence-level LID terms when scoring a sentence alignment.
Our proposed document pair scoring function is: where a(E, F ) is the sentence alignment of documents E and F , cos(e, f ) is the cosine similarity between sentences e and f , and p(L e |e), p(L f |f ) are the probabilities, as judged by automatic LID, that sentences e, f are in the correct languages L E , L F . To penalize unaligned sentences, a(E, F ) includes insertions/deletions but we define cos(e, f ) to be zero when e or f is an insertion/deletion.

Experiments and Results
We evaluate our document alignment method in both high-and low-resource settings. For highresource, we utilize the publicly available French-English data released for the WMT 2016 shared task on document alignment (Buck and Koehn, 2016a) and evaluate document recall following the shared task. The shared task provides a strong set of baselines, as 13 different teams contributed at least one submission. For low-resource, we experiment with Sinhala-English documents extracted from ParaCrawl. In this setting we do not have gold document alignments, so we instead evaluate the quality of MT systems trained on the data extracted via document alignment.
We develop and set all parameters using the training data from WMT16 ("WMT16-train") and then test on the WMT16 test data ("WMT16-test") and the Sinhala-English ParaCrawl data. Basic statistics for each dataset are shown in Figure 1.

Candidate Generation
We find that encoding order in document vectors significantly reduces the number of candidates that must be searched to find the correct document; see Figure 2. We use 16 sub-vectors with modified PERT with γ (which controls peakedness) set to 20, as this performed well on WMT16-train.  (2016b). We evaluate document pairs following Buck and Koehn (2016a). 6 The proposed method has a recall of 98.5%, compared to the previous best of 96.2%. This corresponds to a 61% relative reduction in false positive rate; see Figure 3.

Impact on Downstream MT
We perform document alignment on Sinhala-English documents web-scraped by ParaCrawl. We apply the same method as in French-English, using parameters selected using WMT16-train. We compare to document alignment via Buck and Koehn (2016b), followed by sentence alignment using both Vecalign and Hunalign (Varga et al., 2007) (the latter is the current ParaCrawl pipeline). Our document alignment system and Vecalign both use LASER embeddings, which were proposed as a method for finding parallel sentences in comparable corpora (i.e. without doing document alignment). Since the underlying method to measure semantic similarity at the sentence level is the same, this allows us run an experiment to determine to what extent using document-level information (i.e. performing document alignment and then sentence alignment) provides better data than simply treating the data as comparable corpora and searching for sentence pairs. To search for sentence pairs, we use the margin-based criterion proposed by LASER's authors (Artetxe and Schwenk, 2019) and FAISS fast nearest-neighbor search. For a fair comparison, we search for sentence matches within each webdomain, as this matches the document alignment settings. We denote this method "LASER-cc." For each method of finding parallel sentences, evaluation is the same: Since the true amount of parallel data is unknown, we filter the data following Chaudhary et al. (2019) using a number of different thresholds. The thresholds are selected to produces corpora of particular data sizes, as measured by the number of English words (e.g. 0.5M, 1M, 2M, . . . ). We train NMT systems following the procedure/hyperparameters from the WMT19 sentence filtering shared task (Koehn et al., 2019;Guzmán et al., 2019). Following Thompson and Koehn (2019), we train 5 systems per setting and show both mean and standard deviation. Results are shown in Figure 4. The proposed method improves BLEU by 1.2 BLEU over Buck and Koehn (2016b), when both are used in conjunction with Vecalign, and 2.9 BLEU over Buck and Koehn (2016b) with Varga et al. (2007) sentence alignment (the current Paracrawl pipeline). It also outperforms the LAESR-cc baseline by 1.2 BLEU, showing that document-level information improves the quality of extracted sentence pairs compared to treating the data as comparable corpora.

Related Work
There is a large amount of prior work in document alignment. One of the simplest methods is URL similarity (Resnik, 1998;Chen and Nie, 2000), although this has been shown to be brittle (Tiedemann, 2011). HTML structure (Resnik and Smith, 2003;Shi et al., 2006) or metadata such as publication date (Munteanu and Marcu, 2005) is often similar between parallel websites. However, most more recent work has focused on content similarity via bag-of-words or bag-of-ngrams, using bilingual lexicon (Ma and Liberman, 1999;Fung and Cheung, 2004;Ion et al., 2011;Esplà-Gomis et al., 2016;Etchegoyhen and Azpeitia, 2016; Azpeitia and Etchegoyhen, 2019), machine translation (Uszkoreit et al., 2010), or phrase tables (Gomes and Pereira Lopes, 2016).
Some work has considered high-level order as a filtering step after using a unordered representation to generate candidates: Ma and Liberman (1999) and Le et al. (2016) discard n-gram pairs outside a fixed window, while Uszkoreit et al. (2010) filters out documents which have high edit distance between sequences of corresponding n-gram pairs. Utiyama and Isahara (2003) and Zhang et al. (2006) use sentence similarity and/or number of aligned sentences after performing sentence alignment to score candidate documents. Guo et al. (2018b) score document pairs using the sentence-level nearest neighbor as well as the absolute difference in sentence position between sentence pairs. In contrast to these methods, our work considers highlevel order in both candidate proposal and scoring.
Recent work (Guo et al., 2019) has also shown neural document embeddings are effective representations for document alignment. They train on millions of document pairs in each specific language pair of interest; in contrast, this work is much simpler and does not require document-level training data.

Conclusion
In this work we present a method for document alignment which explicitly models high-level document order. Our proposed method outperforms all published results on the dataset released for the WMT16 shared task on document alignment. It also increases downstream MT performance in a low-resource setting over prior work. We find that exploiting order information improves performance over a comparable corpora method using the same underlying semantic similarity measure, while additionally enabling document-level MT training.

A Boilerplate Downweighting
Many "sentences" in web-crawled data are not true sentences, but boilerplate text (Kohlschütter et al., 2010) such as text of navigational buttons or pulldown menus. We explore three methods for down-weighting such boilerplate: 1. Scaling by the inverse of the log of number of documents containing a given sentence, inspired by IDF (Sparck Jones, 1988;Buck and Koehn, 2016b) 2. A more aggressive variant of IDF which scales sentences by the inverse of the (linear, as opposed to log) number of documents containing a given sentence, which we denote "LIDF 3. Scaling each sentence by its length, in characters length, as boilerplate lines often very short (Kohlschütter et al., 2010).
We find that all three boilerplate methods improve candidate generation, but select LIDF for all experiments in this work as it results in the best recall performance on the WMT16-train.

B Vecalign Speed/Space/Accuracy
Trade-off We experimented with projecting the 1028dimension LASER embeddings into a lower dimensional space prior to computing cosine similarity. Sentence alignment accuracy is evaluated following Thompson and Koehn (2019), on the De-Fr test set released with Bleualign (Sennrich and Volk, 2010), Accuracy and alignment time for a range of embedding sizes shown in Figure 5. We see strong performance (F 1 > 0.85) for embeddings down to size 32, in conjunction with up to a 70% reduction in runtime and 97% reduction in disk space required to store the embeddings. We use an embedding size of 128 in this work.