Massively Multilingual Document Alignment with Cross-lingual Sentence-Mover’s Distance (2020)

Abstract: Document alignment aims to identify pairs of documents in two distinct languages that are of comparable content or translations of each other. Such aligned data can be used for a variety of NLP tasks from training cross-lingual representations to mining parallel data for machine translation. In this paper we develop an unsupervised scoring function that leverages cross-lingual sentence embeddings to compute the semantic distance between documents in different languages. These semantic distances are then used to guide a document alignment algorithm to properly pair cross-lingual web documents across a variety of low, mid, and high-resource language pairs. Recognizing that our proposed scoring function and other state of the art methods are computationally intractable for long web documents, we utilize a more tractable greedy algorithm that performs comparably. We experimentally demonstrate that our distance metric performs better alignment than current baselines outperforming them by 7% on high-resource language pairs, 15% on mid-resource language pairs, and 22% on low-resource language pairs.

## introduction while the web provides a large amount of monolingual text, cross-lingual parallel data is more difficult to obtain. despite its scarcity, parallel cross-lingual data plays a crucial role in a variety of tasks in natural language processing such as machine translation. previous works have shown that training on sentences extracted from parallel or comparable documents mined from the web can improve machine translation models @xcite or learning word-level translation lexicons @xcite . other tasks that leverage these parallel texts include cross-lingual information retrieval, document classification, and multilingual representations such as xlm @xcite . document alignment is a method for obtaining cross-lingual parallel data that seeks to pair documents in different languages such that pairs are translations or near translations of each other. as seen in figure 1 , this involves a one-to-one pairing of documents in a source language with documents in a target language. to automate and scale the process of identifying these documents pairs, we introduce an approach to accurately mine comparable web documents across a variety of low, mid, and high-resource language directions. previous approaches have been applied to homogeneous corpora, however mining the web involves analyzing a variety of heterogeneous data sources @xcite . other approaches rely on corpus-specific features such as metadata and publication date which can be inconsistent and unreliable @xcite . related methods utilize document structure when calculating document similarity @xcite . however, when mining large, unstructured collections of web documents these features are often missing or unreliable. as such, we introduce an approach that aligns documents based solely on semantic distances between their textual content. for our approach, we first decompose documents into sentences, and encode each sentence into a cross-lingual semantic space yielding a bag-of-sentences representation. utilizing the dense, cross-lingual representation of sentences, we then compute document distances using a variant of earth mover's distance where probability mass is moved from the source document to the target document. we then leverage these document distances as a guiding metric for identifying cross-lingual document pairs and demonstrate experimentally that our proposed method outperforms state-of-theart baselines that utilize cross-lingual document representations. ## related works crawling and mining the web for parallel data has been previously explored by @xcite where the focus is on identifying parallel text from multilingual data obtained from a single source. for example, parallel corpora were curated from the united nations general assembly resolutions @xcite and from the european parliament @xcite . however, curating from homogeneous sources by deriving domain-specific rules does not generalize to arbitrary web-domains. other approaches rely on metadata for mining parallel documents in unstructured web corpora. some methods leveraged publication date and other temporal heuristics to identifying parallel documents @xcite @xcite @xcite . however, temporal features are often sparse, noisy, and unreliable. another class of alignment methods rely on document structure @xcite yet these structure signals can be sparse and may not generalize to new domains. in the wmt-2016 bilingual document alignment shared task @xcite , many techniques were proposed to retrieve, score, and align cross-lingual document pairs. however this shared task only considered english to french -a highresource direction and the proposed techniques were not readily extendable to more languages. several approaches translate the target corpus into the source language, then apply retrieval and matching approaches on translated 2-grams and 5grams to query, retrieve, and align documents @xcite . these methods rely on high-quality translation systems to translate, however such models may not exist, especially for low-resource language directions. ad-ditionally, these methods leverage rare n-grams to identify likely candidates, yet low-frequency words and phrases that are likely to be mistranslated by machine translation systems. in the shared task, many document similarity measures were investigated for use in aligning english to french web documents. one method utilized a phrase table from a phrase-based statistical machine translation system to compute coverage scores, based on the ratio of phrase pairs covered by a document pair @xcite . other methods utilize the translated content of the target (french) document, and find the source (english) corresponding document based on n-gram matches in conjunction with a heuristic document length ratio @xcite . other methods translate the target documents into the source language and apply cosine similarity between tf/idf weighted vectors on unigrams and n-grams @xcite @xcite . finally, several methods were introduced that score pairs using metadata in each document such as links to documents, urls, digits, and html structure @xcite . recently, the use of neural embedding methods has been explored for bilingual alignment of text at the sentence and document level. one method proposes using hierarchical document embeddings, constructed from sentence embeddings, for bilingual document alignment @xcite ). another method leverages a multilingual sentence encoder to embed individual sentences from each document, then performs a simple vector average across all sentence embeddings to form a dense document representation with cosine similarity guiding document alignment @xcite . word mover's distance (wmd) is an adaptation of earth mover's distance (emd) @xcite that has been recently used for document similarity and classification @xcite @xcite . other methods have leveraged the distance for cross-lingual document retrieval @xcite . however these methods treat individual words as the base semantic unit for comparison which are intractable for large web-document alignment. finally, sentence mover's similarity has been proposed for automatically evaluating machinegenerated texts outperforming rouge @xcite . this method is purely monolingual and sentence representations are constructed by summing individual word embeddings. ## problem definition given a set of source documents, d s and a set of target documents d t , there exist |d s | × |d t | potential pairs of documents of the form (d s , d t ). let p be the set of all candidate pairs (d s × d t ). then cross-lingual document alignment aims to find the largest mapping from source documents to target documents, p ⊂ p, s.t. given an d s and d t where, without a loss of generality, |d s | ≤ |d t |, the largest injective function mapping between d s and d t : in other words, each source document and target document can only be used in at most a single pair. this can be seen in figure 1 where within the same web-domain, given source and target documents, the task is to match each source document to a unique target document where possible. to find the best possible mapping between d s and d t we require two components: 1) a similarity function φ(d s , d t ) which is used to score a set of candidate document pairs according to their semantic relatedness; and 2) an alignment or matching algorithm which uses the scores for each of the pairs in d s × d t to produce an alignment of size min(|d s |, |d t |) representing the best mapping according to φ(d s , d t ). ## cross-lingual sentence mover's distance wmd fails to generalize to our use case for two reasons: (1) it relies on monolingual word representations which fail to capture the semantic distances between different language documents (2) intractability due to long web documents or lack word boundaries in certain languages. to address this, we introduce cross-lingual sentence mover's distance (smd) and show that representing each document as a bag-of-sentences (bos) and leveraging recent improvements in multilingual sentence representations, smd can better identify cross-lingual document pairs. ## document matching algorithm in addition to a distance metric (i.e. smd), we need a document matching algorithm to determine the best mapping between documents in two languages. in our case, this works as follows: for any given webdomain, each document in the source document set, d s is paired with each document in the target set, d t , yielding |d s × d t | scored pairs -a fully connected bipartite graph representing all candidate pairings. similar to previous works @xcite , the expected output assumes that each webpage in the non-dominant language has a translated or comparable counterpart. as visualized in figure 1 while an optimal matching maximizing scoring can be solved using the hungarian algorithm @xcite , the complexity of this algorithm is o(max(|d s ||d t |) 3 ) which is intractable to even moderately sized web domains. as such, similar to the work in @xcite , a one-to-one matching between english and non-english documents is enforced by applying, competitive matching, a greedy bipartite matching algorithm. algorithm 2: competitive matching input: @xmath0, dt)|@xmath1, @xmath2: @xmath3,i, dt,i), ...} ⊂ p 1 scored ← {(p, score(p)) for @xmath4, @xmath5, dt)} 9 ss ← ss ∪ ds 10 st ← st ∪ dt 11 end 12 return aligned in algorithm 2, the algorithm first scores each candidate document pair using a distance function and then sorts pairs from closest to farthest. the algorithm then iteratively selects the closest document pair as long as the d s and d t of each pair have not been used in a previous (closer) pair. the algorithm terminates when min(|d s |, |d t |) pairs have been selected. unlike the hungarian algorithm, the runtime complexity is a more tractable o(|d s ||d t | × log(|d s ||d t |)) which is dominated by the cost of sorting all candidate pairs. ## experiments and results in this section, we explore the question of whether smd can be used as a dissimilarity metric for the document alignment problem. moreover, we explore which sentence weighting schemes yield the best results. ## discussion although using sentences over words as the base semantic unit drastically reduces the overall cost of computing emd-based metrics, the cubic in figure 3 , we see that the distance computations for exact smd and the greedy smd approximation are highly correlated with small variance, while the relaxed approximation is less so with high variance. additionally, as discussed in section 4.3, the visualizations empirically suggest that our greedy approximation is a fairly tight upper bound while the relaxed approximation is a looser lower bound. in as seen in figure 2 , in 45 of the 47 evaluated language pairs, our proposed greedy mover's distance approximation yielded higher downstream recall in our alignment task over using the relaxed distance proposed for use in wmd @xcite . in ## conclusion in this paper, we introduce smd a cross-lingual sentence mover's distance metric for automatically assessing the semantic similarity of two documents in different languages. we leverage state-of-the-art multilingual sentence embeddings and apply smd to the task of cross-lingual document alignment. we demonstrate that our new metric outperforms other unsupervised metrics by a margin, especially in medium and low-resourced conditions.