Intersecting Hierarchical and Phrase-Based Models of Translation: Formal Aspects and Algorithms

Marc Dymetman, Nicola CanceddaSSST @ COLING 2010 · OpenReview

Abstract

This paper establishes a formal bridge between the two dominant paradigms in Statistical Machine Translation (SMT): phrase-based and hierarchical models. By introducing a novel construct called the $\sigma$-automaton, the authors provide a rigorous algorithmic framework to intersect Synchronous Context-Free Grammars (SCFG) with the non-linear token consumption patterns of phrase-based models. This unification allows for a single translation grammar that leverages both the global reordering capabilities of hierarchical models and the local lexical context of phrase-based approaches.

Introduction

In the late 2000s, the SMT community was divided between two primary approaches. Phrase-Based Models (PBMT) excelled at capturing local context and surface-level lexical patterns but struggled with long-distance reordering. Conversely, Hierarchical Models (Hiero), based on Synchronous Context-Free Grammars (SCFG), handled complex reordering well but often suffered from sparse rules and lexical selection issues.

The primary obstacle to a hybrid approach was mathematical incompatibility: hierarchical models are defined by formal grammars, while phrase-based models allow for arbitrary word reordering that violates standard finite-state logic. This research addresses the formal prerequisites needed to intersect these models, enabling the hierarchical component to govern structural reordering while the phrase-based component manages lexical selection.

Methodology: The $\sigma$-Automaton and Intersection

The authors propose a three-step theoretical solution centered on a new type of automaton designed to bridge the gap between linear processing and bag-of-phrases reordering.

The $\sigma$-Automaton

Standard finite-state automata process strings linearly. To model the nature of PBMT, the authors introduce the $\sigma$-automaton. In this structure, transitions are labeled with sets of source tokens. A path is considered valid only if it "consumes" every token in the source sentence exactly once, regardless of the order in which they appear. This perfectly captures the reordering flexibility inherent in phrase-based translation.

The $\sigma$-automaton representing translation options with target language lexical labels in brackets.

Algorithmic Intersection

The core of the methodology is the intersection of a weighted SCFG with this $\sigma$-automaton. This process involves:

  1. SCFG-FSA Intersection: Extending the classic Bar-Hillel algorithm to intersect a weighted SCFG with a standard finite-state automaton.
  2. Full Intersection Algorithm: Adapting the previous algorithm to handle the "token consumption" constraints of the $\sigma$-automaton. The resulting structure is a new, larger SCFG representing the "parse forest" of all translations valid under both models simultaneously.

Key Insights: Separation of Concerns

The fundamental insight of this work is the "separation of concerns." The hierarchical model provides the "skeleton" or structural reordering of the sentence, while the phrase-based model provides the "flesh" or specific lexical choices.

Visualization of the intersected grammar (parse forest) showing hierarchical structures (S1, NP1, VP1) mapped onto the $\sigma$-automaton.

However, this intersection is technically NP-hard due to the state explosion caused by tracking consumed source tokens. To mitigate this, the authors suggest a "sync" constraint, requiring the two models to remain relatively aligned in terms of the source segments being translated at any given time.

Conclusion

This paper provides the mathematical "recipe" for a hybrid decoder, proving that the intersection of an SCFG and a $\sigma$-automaton can be represented as a new SCFG. While the paper is purely theoretical and lacks empirical evaluation on specific datasets, it establishes a formal means for advancing toward unified translation systems. Future work must address the computational costs of these massive intersected grammars, likely through approximation techniques such as cube pruning. This theoretical framework serves as a significant milestone in bridging the gap between structural and lexical modeling in machine translation.

Summary updated

BibTeX
@inproceedings{dymetman2010intersecting,
  author = {Marc Dymetman and Nicola Cancedda},
  title = {{Intersecting Hierarchical and Phrase-Based Models of Translation: Formal Aspects and Algorithms}},
  booktitle = {SSST @ COLING},
  year = {2010},
  url = {https://openreview.net/forum?id=JIdSPjUL9fv},
}
Figure