Approximate Sentence Retrieval for Scalable and Efficient Example-Based Machine Translation

Johannes Leveling, Debasis Ganguly, Sandipan Dandapat, Gareth JonesCOLING 2012

TL;DR

This paper tackles the challenge of efficiently finding similar sentences for Example-Based Machine Translation (EBMT) by proposing a novel Information Retrieval (IR) model called LM-ASM. This model significantly speeds up the process compared to traditional methods while maintaining high translation quality, even outperforming exact edit distance computations in some cases.

What Problem Does This Paper Address?

Example-Based Machine Translation (EBMT) relies on finding similar sentence pairs in a large "example base" to translate new sentences. The core of this process is "approximate sentence matching" (ASM), which aims to find sentences that are similar to the input, even if they aren't an exact match. Traditional methods for ASM, like calculating the edit distance (e.g., Levenshtein distance) between the input sentence and every sentence in the example base, are computationally very expensive. This makes it difficult to use large example bases, which are crucial for achieving high-quality translations. While in-memory data structures like tries and ternary search trees can speed things up, they don't scale well for massive datasets due to memory constraints. Standard Information Retrieval (IR) techniques, which focus on term overlap, also fall short because they don't adequately consider word order and position, which are vital for accurate sentence similarity. This paper aims to bridge this gap by developing an efficient and scalable ASM approach that incorporates these crucial aspects of similarity.

Methods

The authors propose a novel retrieval model, LM-ASM (Language Modeling - Approximate Sentence Matching), which extends standard language modeling for IR. Unlike traditional LM that treats query terms independently, LM-ASM incorporates two key components to better estimate edit distance:

  1. Length Similarity (Plen): This component measures how close the length of the query sentence is to the length of a candidate sentence in the example base. It's calculated as the ratio of the minimum length to the maximum length.
  2. Positional Similarity (Ppos): This component captures how likely a query term is to appear at a similar absolute position in the candidate sentence as it does in the query. It uses the reciprocal of the minimum difference in positions between matching terms.

LM-ASM combines these two components multiplicatively to generate a score that approximates the edit distance. The overall approach is a two-stage process: first, an IR model (LM-ASM) retrieves a set of candidate sentences, and then these candidates are reranked using their true edit distance scores. This significantly reduces the number of expensive edit distance computations needed.

Datasets

The experiments were conducted on two parallel datasets:

  • IWSLT 09: English-Turkish (EN-TR) language pair, with approximately 19,972 sentences in the example base and 414 sentences for testing.
  • EMEA: English-French (EN-FR) language pair, with approximately 250,806 sentences in the example base and 10,000 sentences for testing.

These datasets are described as representing different sizes and types of parallel data.

Key Insights and Ideas

  • Sequential Edit Distance is Not Scalable: The paper clearly demonstrates that a brute-force, sequential computation of edit distance is infeasible for large example bases, even with optimized algorithms.
  • In-Memory Structures Have Memory Limitations: While data structures like tries and ternary search trees offer speedups, their high memory requirements prevent them from scaling to millions of sentences.
  • Standard IR is Insufficient for ASM: Traditional IR methods, focusing solely on term overlap (material similarity), fail to capture the nuances of approximate sentence matching, neglecting word order and position.
  • Positional and Ordinal Similarity are Crucial: The authors highlight that for effective ASM, similarity metrics must consider not only the words present (material similarity) but also their order (ordinal similarity) and positions (positional similarity).
  • LM-ASM Bridges the Gap: The proposed LM-ASM model successfully integrates positional and ordinal similarity into an IR framework, providing a more accurate approximation of edit distance.
  • Reranking is Key: The two-stage approach (retrieval followed by reranking with true edit distance) offers a practical balance between efficiency and accuracy.
  • Exact Matches Aren't Always Best for Translation: Surprisingly, the paper finds that LM-ASM can sometimes yield better translation quality (higher BLEU scores) than exact edit distance computations, suggesting that the "best" edit distance match might not always be the most suitable translation template.

Key Results

  • Efficiency: LM-ASM significantly speeds up the retrieval process. For the EN-TR dataset, it achieves an average time per sentence of 0.010-0.015 seconds, a substantial improvement over sequential methods (which can take seconds per sentence).
  • Effectiveness (Accuracy):
    • LM-ASM consistently outperforms standard Language Models (LM) in terms of Mean Average Precision (MAP) and Mean Reciprocal Rank (MRR). For example, on EN-TR, LM-ASM with bigrams achieves an MRR of 0.733 compared to LM's 0.688.
  • The proposed LM-ASM approach approximates edit distance better than standard LM by about 10%.
  • Translation Quality:
    • LM-ASM improves MT quality by 1.52% compared to sequential edit distance computation on the EN-TR dataset (BLEU score of 22.08 vs. 21.71).
  • For the larger EN-FR dataset, LM-ASM also shows improvements in BLEU scores (e.g., 44.92 for LM-ASM50 vs. 44.36 for LM50).
  • Preprocessing: The experiments indicate that standard IR preprocessing techniques like stopword removal and stemming actually decrease performance for ASM. Keeping all terms, including stopwords and punctuation, is important for exact matching and retaining syntactic structure.

Limitations and Future Work

  • Memory Requirements for Data Structures: While IR approaches are efficient, data structures like Tries and Ternary Search Trees, though faster than sequential methods, require significant memory to be kept in memory, limiting their scalability.
  • Tie-breaking: The paper acknowledges that resolving ties (sentences with identical edit distance scores) is done by selecting the sentence with the lowest document ID. Developing more sophisticated tie-breaking heuristics is suggested as future work.
  • Future Work: The authors plan to investigate alternatives for generating relevance assessments, potentially using BLEU scores themselves to guide similarity metrics and IR models, aiming to better approximate MT quality. They also suggest exploring how to adapt IR models for other tasks beyond information retrieval.

Summary updated

BibTeX
@inproceedings{leveling2012approximate,
  author = {Johannes Leveling and Debasis Ganguly and Sandipan Dandapat and Gareth Jones},
  title = {{Approximate Sentence Retrieval for Scalable and Efficient Example-Based Machine Translation}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2012},
}
Figure