Using a maximum entropy model to build segmentation lattices for MT

Chris DyerNAACL 2009

TL;DR

This paper introduces a novel maximum entropy model for automatically generating segmentation lattices for morphologically rich languages, significantly improving machine translation quality. By learning to produce diverse, yet plausible, segmentations of compound words, the model overcomes limitations of single-best segmentation approaches and offers a more robust input for translation decoders.

What Problem Does This Paper Address?

Statistical Machine Translation (SMT) systems often struggle with languages that have productive compounding, where words are formed by combining multiple morphemes. A common solution is to segment these compound words into their constituent parts before translation. However, determining the optimal segmentation is challenging. Using a single, "best guess" segmentation can lead to error propagation, where mistakes in segmentation negatively impact translation quality. Previous work has shown that using lattices of multiple possible segmentations can improve translation, but this typically required multiple, diverse segmenters. This paper addresses the need for a single, principled method to generate these valuable segmentation lattices automatically, especially for languages where morphological boundaries are not explicitly marked in writing.

Methods

The core of this paper is a maximum entropy (MaxEnt) model for word segmentation. MaxEnt models are chosen for their ability to handle many overlapping features and their probabilistic grounding. The model learns to assign probabilities to different ways of splitting a word into segments.

Key aspects of their approach include:

  • Feature Engineering: The model uses a set of features that capture linguistic intuitions about word segmentation. These include the frequency of hypothesized segments in a monolingual corpus, segment length, and features related to character sequences at word boundaries (e.g., reverse 5-gram character models).
  • Lattice Generation: The MaxEnt model outputs probabilities for segmentations. These probabilities are used to construct segmentation lattices, which are essentially directed acyclic graphs where nodes represent coverage of the input word and edges represent hypothesized segments.
  • Lattice Pruning: To manage the size of these lattices (which can become very large), they employ forward-backward pruning. This technique prunes edges that are unlikely to contribute to high-probability paths, controlled by a density parameter.
  • Training: The model is trained using maximum likelihood estimation on manually created "gold standard" segmentation lattices. For cases where lattices are not usable (e.g., for word alignment), they also explore training to minimize 1-best error using the Minimum Error Training (MERT) algorithm.
  • Cross-lingual Transfer: A significant finding is that features and weights learned for one language (German) transfer well to others (Hungarian, Turkish) with minimal or no additional training data.

Datasets

  • Training Data: For German-English, Hungarian-English, and Turkish-English translation experiments, they used data from the 2009 EACL Workshop on Machine Translation and the work of Oflazer and Durgar El-Kahlout (2007).
  • Monolingual Corpora: Used for calculating segment frequencies (feature f(si)).
  • Development and Test Sets: For German-English, they created a development set from 19 German newspaper articles and a test set from 4 articles, focusing on words longer than 6 characters.
  • "Gold Standard" Segmentation Lattices: These were manually created for training and evaluation. For German, they generated 489 training sentences (564 paths) and 302 paths for the test set.

Key Insights and Ideas

  • Lattices are Better than 1-Best: The core idea that providing multiple segmentation options (via lattices) to the MT decoder is superior to forcing a single segmentation is reinforced. This allows the decoder to leverage its full translation model to resolve segmentation ambiguities.
  • Single Model for Diverse Segmentations: The MaxEnt approach elegantly generates diverse segmentations from a single model, unlike prior methods that relied on multiple, disparate segmenters. This simplifies the process significantly.
  • Feature Engineering is Key: The success hinges on carefully chosen features that capture linguistic properties of segmentation, such as segment frequency and character patterns.
  • Cross-lingual Transferability: The parameters learned for one language's segmentation model can be surprisingly effective for other languages, drastically reducing the need for language-specific annotated data. This is a major practical advantage.
  • Pruning is Essential: While lattices are beneficial, their size must be managed. Forward-backward pruning effectively balances lattice density (diversity of segmentations) with computational cost and translation quality.

Key Results

  • Significant Translation Quality Improvement: The proposed segmentation lattice approach led to significant improvements in both BLEU and TER scores for German-English, Hungarian-English, and Turkish-English translation compared to both unsegmented baselines and 1-best segmentation baselines.
  • German-English: BLEU increased from 20.7 (1BEST) to 21.6 (LATTICE), TER decreased from 60.1 to 59.8.
  • Hungarian-English: BLEU increased from 10.7 (1BEST) to 12.3 (LATTICE), TER decreased from 70.4 to 69.1.
  • Turkish-English: BLEU increased from 27.8 (1BEST) to 28.7 (LATTICE), TER decreased from 61.2 to 59.6.
  • Hungarian/Turkish Gains Larger: Improvements were notably larger for Hungarian and Turkish systems, possibly due to less in-domain training data available for these languages compared to German.
  • Cross-lingual Transfer Effectiveness: Parameters trained on German data performed well on Hungarian and Turkish, demonstrating the model's adaptability.
  • Pruning Parameter Impact: Figure 4 shows that translation quality improves with lattice density up to a point, after which it degrades, indicating that too many implausible segmentations harm performance.

Limitations and Future Work

  • Manual Lattice Creation: The primary limitation is the reliance on manually created "gold standard" segmentation lattices for training. While the authors argue their model requires minimal annotated data, this manual effort is still a bottleneck.
  • Future Work:
    • Unsupervised Segmentation: Explore unsupervised approaches to segmentation to completely remove the need for manual lattices.
  • Target Language Information: Incorporate information from the target language into the segmentation model to induce more effective translation models.
  • Named Entities: The authors note their model could be extended to handle named entities by incorporating this as a feature.

Summary updated

BibTeX
@inproceedings{dyer2009using,
  author = {Chris Dyer},
  title = {{Using a maximum entropy model to build segmentation lattices for MT}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure