A Simple Sentence-Level Extraction Algorithm for Comparable Data

Christoph Tillmann, Jian-ming XuNAACL 2009

TL;DR

This paper introduces a novel, efficient algorithm for extracting parallel sentence pairs from comparable (non-translated) monolingual text. By directly scoring sentence pairs at the sentence level using a simplified IBM Model 1 approach, they achieve significant speedups and demonstrate improved performance in statistical machine translation (SMT) systems.

What Problem Does This Paper Address?

The core challenge addressed is the efficient extraction of parallel sentence pairs from "comparable" corpora. Comparable corpora are collections of texts that are similar in topic and genre but are not direct translations of each other (e.g., news articles about the same event from different countries). Traditional methods often rely on document-level filtering using Information Retrieval (IR) techniques to first identify potentially parallel documents, and then apply more complex sentence-level models. This two-step process is computationally expensive and can be problematic when document-level information is unavailable or unreliable. The authors aim to bypass document-level filtering and directly extract parallel sentences at the sentence level, significantly reducing computational overhead.

Methods

The paper proposes a simple, symmetric sentence-level scoring function inspired by phrase-based SMT. This function, denoted as $\rho(S, T)$, scores a sentence pair $(S, T)$ based on word translation probabilities derived from a preliminary IBM Model 1 training on existing parallel data. The key innovation lies in the efficient implementation of this scoring function. Instead of a brute-force calculation, they decompose the scoring into $I+J$ terms (where $I$ and $J$ are sentence lengths) and employ several optimization techniques:

  • Caching for target terms: Pre-computes and caches the probability of a target word given the source sentence ($p(t|S)$) to avoid redundant calculations.
  • Array access for source terms: Efficiently retrieves translation probabilities for source words ($p(s|t)$) by storing them in arrays, enabling fast lookups.
  • Early-Stopping: Implements a pruning mechanism where the scoring of a sentence pair is halted if its partial score falls below the best score found so far, significantly reducing computation for many pairs.
  • Frequency-Sorting: Further optimizes early-stopping by sorting words based on their frequency, prioritizing words that are more likely to contribute to high partial scores.
  • Sentence-level filter: Incorporates a filter that checks for word overlap and length ratios between sentence pairs, a common technique to quickly discard unlikely candidates.

Datasets

  • Spanish-English Gigaword: Used for training and evaluation. This dataset consists of news articles from three feeds (AFP, APW, Xinhua).
  • Portuguese-English Reuters: Used for experiments.

Key Insights and Ideas

  • Direct Sentence-Level Scoring is Feasible: The paper demonstrates that effective parallel sentence extraction can be achieved by directly scoring sentence pairs, eliminating the need for computationally intensive document-level IR filtering.
  • Efficiency is Key: The core contribution is not just the scoring function itself, but its highly optimized implementation. The reported speedups (up to 30x) are crucial for making sentence-level processing practical on large datasets.
  • Early-Stopping is a Powerful Pruning Technique: The early-stopping mechanism, combined with frequency sorting, dramatically reduces the number of full sentence pair scores that need to be computed.
  • Language-Specific Thresholds: The optimal threshold for selecting parallel sentence pairs is found to be language-specific, highlighting the need for careful tuning.

Key Results

  • Significant Speedup: The optimized implementation achieves a speedup of up to 30 times compared to a baseline approach.
  • Efficient Processing of Large Corpora: The algorithm can process close to 1 trillion candidate sentence pairs without search errors.
  • Improved SMT Performance: Including the extracted sentence pairs into the training of a phrase-based SMT system resulted in a statistically significant improvement in BLEU scores (e.g., from 42.3 to 45.6 for Spanish-English).
  • Processing Time: For a dataset of 20 million source sentences, the overall processing time was less than 3 days using approximately 120 processors.

Limitations and Future Work

  • Language Specificity: The optimal selection threshold is language-specific, requiring manual determination.
  • Future Work: The authors plan to explore a "feature-rich approach" to further improve sentence-pair selection accuracy. They also intend to re-implement IR-based document-level techniques to evaluate their impact in conjunction with their sentence-level processing. The goal is to see if a purely sentence-level approach can yield even more productive pair extraction in the future.

Summary updated

BibTeX
@inproceedings{tillmann2009simple,
  author = {Christoph Tillmann and Jian-ming Xu},
  title = {{A Simple Sentence-Level Extraction Algorithm for Comparable Data}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure