Abstract: Anders Søgaard. Proceedings of the Third Workshop on Syntax and Structure in Statistical Translation (SSST-3) at NAACL HLT 2009.
2009.
Introduction
In syntax-based machine translation, synchronous grammars model the transformation of sentences between languages. A fundamental challenge is the alignment problem: determining the mapping between words in a source sentence and a target sentence given a specific grammar. This paper investigates the computational complexity of this problem across two formalisms: Inversion Transduction Grammars (ITGs) and (2,2)-Bounded Range Concatenation Grammars ((2,2)-BRCGs).
Synchronous Grammar Formalisms
The study focuses on two primary formalisms with differing levels of expressivity:
- Inversion Transduction Grammars (ITGs): Widely used but structurally limited, ITGs cannot represent certain complex alignments, such as discontinuous or "inside-out" mappings.
- Range Concatenation Grammars (specifically (2,2)-BRCGs): A more expressive class capable of inducing any possible word alignment.
Despite the difference in expressivity, both formalisms share a universal recognition complexity of $O(n^6)$. This paper explores why the added power of (2,2)-BRCGs does not immediately lead to higher complexity in general recognition, but rather manifests when common linguistic constraints are applied.
Methodology: Complexity Analysis
The author defines 15 variations of the alignment problem by applying three types of constraints:
- 1:1 Alignments: Each source word maps to exactly one target word.
- Island-free (IF): All words must be aligned (no "islands" of unaligned text).
- Sure-possible sorted (SP): Distinguishing between certain and potential alignments.
To prove NP-hardness for (2,2)-BRCGs under these constraints, the paper employs polynomial-time reductions from known NP-complete problems. For instance, the 1:1 alignment restriction is proven intractable via a reduction from the Hamiltonian Circuit problem.
Key Results: The NP-hard Wall
The central finding is a sharp divergence in complexity between the two formalisms when constraints are introduced. While ITGs remain solvable in $O(n^6)$ for all 15 variations, (2,2)-BRCGs become NP-complete in every single case. The author provides a definitive table (Figure 1) comparing these results.
This "Expressivity Paradox" suggests that (2,2)-BRCGs maintain polynomial efficiency only by being "sloppy"—they avoid NP-hardness by failing to enforce global properties like ensuring every word is translated exactly once. Once these global constraints are imposed, the search space becomes intractable.
Conclusion and Future Work
The results highlight a significant trade-off in machine translation: choosing a grammar that can represent any alignment (like BRCG) necessitates facing NP-hard search problems when enforcing basic translation rules. Conversely, ITGs remain efficient by restricting the types of alignments they can represent. Future research may seek a middle ground—formalisms more expressive than ITGs that still allow for efficient constrained alignment.
Summary updated