SentAlign: Accurate and Scalable Sentence Alignment

Steinthor Steingrimsson, Hrafn Loftsson, Andy WayEMNLP 2023

TL;DR

This paper introduces SentAlign, a novel sentence alignment tool designed for massive parallel document collections. By leveraging LaBSE embeddings for scoring and a divide-and-conquer strategy for scalability, SentAlign achieves state-of-the-art performance on standard benchmarks and significantly improves downstream machine translation tasks.

What Problem Does This Paper Address?

Sentence alignment is a crucial preprocessing step for creating parallel corpora, which are essential for training machine translation (MT) systems. The challenge lies in accurately identifying corresponding sentences across two documents, especially when dealing with very large datasets. Traditional methods often struggle with scalability, accuracy, and handling complex alignment scenarios like sentence merging or reordering. Existing tools can be slow on large corpora or miss subtle but important alignments, which can negatively impact the quality of MT models. This paper aims to bridge this gap by providing a tool that is both accurate and scalable, capable of handling millions of sentence pairs efficiently.

Methods

SentAlign employs a multi-faceted approach:

  • LaBSE-based Scoring: At its core, SentAlign uses LaBSE (Language-agnostic BERT Sentence Embedding) to generate bilingual sentence representations. This allows for a robust semantic similarity score between sentence pairs, forming the basis for alignment decisions.
  • Graph-based Alignment: The problem is framed as finding an optimal path through a 2D graph where nodes represent potential sentence alignments. The algorithm explores all possible paths, considering various alignment types (1-1, 1-n, n-1, n-m, insertions, deletions).
  • Divide and Conquer (DaC): To tackle the exponential growth of the search space in large documents, SentAlign implements a DaC strategy. When the number of nodes in the alignment graph exceeds a user-defined threshold, the system identifies "hard delimiters" (high-confidence 1-1 alignments) to split the document into smaller, manageable chunks. This significantly reduces computational complexity from O(n²) to O(n log n).
  • Pathfinding Algorithm: A modified Dijkstra's algorithm is used to find the optimal path through the alignment graph, aiming to maximize the cumulative score.
  • Re-evaluation and Readjustment: After an initial path is found, SentAlign performs a re-evaluation step. It looks for opportunities to improve the alignment by considering mergers, insertions, and deletions, ensuring that the final alignment is truly parallel and minimizes unnecessary merges.

Datasets

The paper evaluates SentAlign on two main datasets:

  • German-French Text+Berg Corpus: A standard, manually aligned evaluation set commonly used for sentence alignment research.
  • English-Icelandic Corpus: A newly compiled evaluation set consisting of 10 aligned documents from the ParIce corpus, containing 549 sentence alignments. This set is noted as being potentially easier to align than Text+Berg due to fewer long non-alignment stretches and n-m merges.

SentAlign was also tested on a downstream Machine Translation task using English and Icelandic documents from EEA regulations and directives.

Key Insights and Ideas

  • Semantic Embeddings are Key: The use of LaBSE embeddings proves highly effective for scoring sentence similarity, outperforming previous methods that relied more heavily on lexical or length-based features.
  • Scalability is Achievable: The Divide and Conquer strategy is a critical innovation, enabling sentence alignment on previously intractable document sizes without sacrificing accuracy.
  • Post-alignment Refinement Matters: The re-evaluation step is crucial for correcting potential over-merging and ensuring the final alignment is as precise as possible, especially in complex cases.
  • Language Pair Specificity: The optimal threshold for LaBSE scores might vary between language pairs, suggesting that fine-tuning might be beneficial for specific language combinations.

Key Results

  • Evaluation Sets: SentAlign achieved state-of-the-art results on both the German-French and English-Icelandic evaluation sets, outperforming five other sentence aligners (Vecalign, Bleualign, Gargantua, Hunalign, and Gale-Church) in terms of precision, recall, and F1 scores.
  • Downstream MT Task: When used to train MT systems, SentAlign generated sentence pairs that resulted in the best BLEU scores for both English-to-Icelandic (42.8) and Icelandic-to-English (53.6) translation directions, with statistical significance.

Limitations and Future Work

  • Scalability Limits: While the DaC mechanism improves scalability, SentAlign may still encounter memory and time constraints with documents containing tens of thousands of sentences.
  • Language Representation in LaBSE: The accuracy of SentAlign might be affected if used on languages not well-represented in the LaBSE training data.
  • MT Model Quality: The performance of Bleualign could potentially be improved by using higher-quality MT models for its alignment process.
  • Parameter Tuning: The optimal LaBSE threshold may differ across language pairs, suggesting that language-specific tuning could further enhance performance.

The authors suggest that further analysis of language-specific parameters could be beneficial.

Summary updated

BibTeX
@inproceedings{steingrimsson2023sentalign,
  author = {Steinthor Steingrimsson and Hrafn Loftsson and Andy Way},
  title = {{SentAlign: Accurate and Scalable Sentence Alignment}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2023},
}
Figure