S pan A lign: Sentence Alignment Method based on Cross-Language Span Prediction and ILP (2020)

Abstract: We propose a novel method of automatic sentence alignment from noisy parallel documents. We first formalize the sentence alignment problem as the independent predictions of spans in the target document from sentences in the source document. We then introduce a total optimization method using integer linear programming to prevent span overlapping and obtain non-monotonic alignments. We implement cross-language span prediction by fine-tuning pre-trained multilingual language models based on BERT architecture and train them using pseudo-labeled data obtained from unsupervised sentence alignment method. While the baseline methods use sentence embeddings and assume monotonic alignment, our method can capture the token-to-token interaction between the tokens of source and target text and handle non-monotonic alignments. In sentence alignment experiments on English-Japanese, our method achieved 70.3 F1 scores, which are +8.0 points higher than the baseline method. In particular, our method improved by +53.9 F1 scores for extracting non-parallel sentences. Our method improved the downstream machine translation accuracy by 4.1 BLEU scores when the extracted bilingual sentences are used for fine-tuning a pre-trained Japanese-to-English translation model.

## introduction sentence alignment is the task that automatically extracts parallel sentences from noisy parallel documents. parallel sentences are used to train cross-language models, especially for machine translation (mt) systems. both the quantity and quality of the parallel sentences used for training are crucial for developing an accurate neural machine translation (nmt) system @xcite . recently, automatic sentence alignment methods using neural networks have gained popularity @xcite @xcite . such systems have a scoring function to calculate how the two sentences are parallel from sentence embeddings and obtain an alignment hypothesis from these scores with an alignment algorithm. these embeddings are obtained by separately encoding each source and target sentence. however, these prior works do not utilize context information and the interaction between the tokens of the source and target text although it may be useful for calculating the score. moreover, alignment algorithms of these works assumes monotonic alignments although not every alignment of noisy bilingual documents is monotonic. @xcite described a legislation corpus as an example of non-monotonic alignments. in such cases, the existing methods that assume monotonicity impair the accuracy. in this paper, we propose a novel sentence alignment method, called spanalign. that can be decomposed into two methods: scoring and optimization. we formalize the scoring method as a cross-language span prediction model, similar to models for the squad 2.0 question answering task @xcite . figure 1 shows an example. in meteorology, precipitation is any product of the condensation of atmospheric water vapour that falls under gravity. the main forms of precipitation include drizzle, rain, sleet, snow, graupel and hail... q. what causes precipitation to fall? a. gravity i said, "would you go to governments and lobby and use the system?" he said, "no, i'd take to the individuals." it's all about the individuals. it's all about you and me. it's all about partnerships... q. 全ては個人についてのことであり a. it's all about the individuals. figure 1 : example of squad-style monolingual question answering (upper) and sentence alignment task from bilingual document based on cross-language span prediction (lower). in sentence alignment, q. denotes a source sentence, and a. denotes a target text that corresponds the source sentence in a given target document. in sentence alignment, given a target text and source sentences, the model predicts a translation of the source text as the answer, which is a span in the target text, and calculates its score. we used pre-trained multilingual language models based on bert architecture @xcite and trained them using only pseudo-labeling data obtained from existing sentence alignment methods. one advantage of our approach is its adoption of cross-attention, which can capture context information and the token-to-token interaction between input sentences. moreover, this approach could work well on various language pairs without human-annotated data. since this span prediction method independently predicts the target spans for source sentences, the target spans might overlap. moreover, because this method is asymmetric, the source-to-target predictions might differ from the target-to-source ones. therefore, we propose an optimization method that introduces a total optimization method using integer linear programming (ilp), inspired by @xcite and @xcite . this method can use the predictions of both directions and extracts non-monotonic alignments. we conducted sentence alignment experiments to evaluate the accuracy of our proposed method using an actual noisy newspaper dataset on english-japanese articles, and our method significantly outperformed the previous works. we also evaluated on a downstream mt task and showed that the proposed method actually improved its performance. ## related works previous sentence alignment methods are based on the context-independent similarity of source and target sentences, including sentence length @xcite , bilingual dictionaries @xcite @xcite , a machine translation system @xcite , and multilingual sentence embeddings @xcite . they usually use dynamic programming, which assumes that the alignments are monotonic. on the contrary, alignment methods using integer linear programming (ilp), which does not assume a monotonic alignment, have also been proposed. @xcite formalized a sequence alignment problem as a set partitioning problem, which is a type of combinatorial optimization problem, and solved it by using ilp. @xcite showed that the problem of finding an optimal alignment can be cast as an ilp, which can quickly and reliably find the globally optimal alignment. following these works, we use ilp for optimization to handle non-monotonic alignments. @xcite proposed a method using the score of document alignment for sentence alignment. to obtain alignments for a document, they first translated a source document into a set of words from the target language using bilingual dictionaries. they then used each target document as a query and searched for the most similar source document in terms of bm25 @xcite . after that, they aligned the sentences in the aligned documents using dp matching @xcite based on similarity measure sim, which is defined as the relative frequency of the one-to-one correspondence between the source and target words obtained from bilingual dictionaries. as a reliable measure for document alignment, they used avsim, which is the average of the sims obtained from the sentence pairs in the document pair. as a reliable measure for sentence alignment, they used the product of the document similarity avsim and the sentence similarity sim. use of document similarity for sentence alignment performed robustly for predicted documents alignments which are not always parallel. this method is commonly used for building publicly available english-japanese parallel corpora, including the shared task data for the ntcir patent translation foot_1 and the workshop on asian translation (wat) 3 . in a recent work, @xcite proposed a sentence alignment method, called vecalign, which uses bilingual sentence embeddings @xcite and recursive dp approximation. they used a german-french test set and achieved state-of-the-art results. their method also effectively works for low-and medium-resource language pairs with the bible dataset and used for building the paracrawl corpus, which is one of the largest parallel corpus across 23 eu languages with english by crawling the web @xcite . since the targets of previous works on the sentence alignment task were mainly among european languages, it is unclear whether these methods are effective on such distant language pairs as english and japanese. in this paper, we also explore how well previous methods work well for such language pair. ## experiments on sentence alignment accuracy we conducted the experiment to evaluate sentence alignment accuracy using an actual noisy parallel newspaper article dataset on english-japanese. we evaluate two variants of our method exploiting different optimization methods: monotonic dp @xcite and ilp ( §3.2) as a baseline, we adopted vecalign @xcite , which achieved stateof-the-art results. we also compared our method with @xcite because it is the defacto standard approach for building english-japanese parallel corpora. for evaluation metrics, we used the f 1 score of sentence alignment, which is one of the standard metrics for sentence alignment 4 . the score was calculated by the correct and predicted alignment pairs. however, this metric didn't directly evaluate the accuracy of extracting non-parallel sentences even though there are a lot of these non-parallel sentences in noisy bilingual documents. therefore, for further detailed analysis, we also calculated the precision/recall/f 1 score for each number of source and target sentences in alignment pairs based on our implementation. ## experiments on machine translation task parallel sentences, which were extracted in the sentence alignment task, are important to train cross-language models, especially for building machine translation systems. to evaluate the effectiveness of our method on downstream mt tasks, we automatically and manually aligned the sentences on actual noisy newspaper article data in a distant language pair: japanese-to-english. we compared our method to vecalign @xcite and @xcite . we extracted parallel sentences using each method and randomly sample 300,000 sentence pairs to train the nmt models. since this newspaper dataset is noisy and the model that only uses these datasets works poorly, we created two types of nmt models: one is only trained on extracted parallel sentences, the other is fine-tuned by the pre-trained model using the extracted dataset. moreover, to confirm the reliability of the sentence alignment costs c ijkl , we took out various amounts of parallel corpora from the extracted sentence alignment in ascending order of their costs. we then fine-tuned the pre-trained model by using these parallel corpora and compared the translation accuracies of each method. ## discussion we first discuss about the usefulness of the token-level interaction for sentence alignment. in the context of an information retrieval (ir) task, neural models are characterized as either representation-based or interaction-based, according to their architecture @xcite . the representation-based model maps a query and a document into low-dimensional spaces and calculates its similarity. the interaction-based model calculates the similarity through the interaction between the elements of a query and a document. @xcite shows that the interaction-based model generally outperforms the representation-based model on ir task. for sentence alignment, which is one of the cross-language ir tasks, the prior works resemble a representation-based model, and our scoring method resembles an interaction-based model. our experiments, which show that our method outperformed the representation-based baseline models, indicate that the interaction between the source and target tokens is also useful for sentence alignment, as well as the ir task. the proposed cross-language span prediction method can be used for any alignment scoring between two sequences. we have already applied it to word alignment @xcite , and we would like to extend the method to other related problems. ## conclusion we presented a novel method of automatic sentence alignment from noisy parallel documents based on cross-language span prediction and optimization using integer linear programming. experimental results showed that our method significantly outperformed previous works and improved the performance of downstream mt tasks in english-japanese. in future work, we will apply our proposed method to other language pairs, use other multilingual pre-training models that support long sequence input, and incorporate with document alignment methods. current sentence alignment methods assume sentence boundaries are given in advance and depend on the accuracy of sentence segmentation. however, sentence segmentation often creates ambiguity, especially for low-resource languages and those whose words are not delimited by white spaces, such as chinese and japanese. we are considering an extension of our method so that it doesn't use sentence boundaries.