Why Synchronous Tree Substitution Grammars?

Andreas MalettiNAACL 2010

TL;DR

This paper argues for the adoption of Multi Bottom-Up Tree Transducers (MBOTs) over Synchronous Tree Substitution Grammars (STSGs) for syntax-based machine translation. MBOTs offer significant algorithmic advantages, including full binarization, efficient input/output restriction, and composition, which are either impossible or significantly more complex with STSGs.

What Problem Does This Paper Address?

Syntax-based machine translation (MT) relies on formal models to describe the translation process. While string-based statistical MT has been successful, syntax-based approaches leverage the grammatical structure of sentences. Synchronous Tree Substitution Grammars (STSGs) are a powerful model for this, originating from synchronous context-free grammars. However, certain crucial operations for STSGs, like full binarization and composition, are known to be problematic or impossible in general. This paper investigates an alternative model, the Multi Bottom-Up Tree Transducer (MBOT), which is more expressive than STSGs but retains good computational properties, and demonstrates its superiority for these operations.

Methods

The paper formally defines STSGs and MBOTs, highlighting their differences. A key contribution is demonstrating that every STSG can be transformed into an equivalent MBOT in linear time. This transformation is crucial because it allows us to leverage the MBOT's superior algorithmic properties. The paper then systematically compares STSGs and MBOTs on several standard algorithms:

  • Binarization: MBOTs can be fully binarized in linear time, whereas STSGs can only achieve partial or asynchronous binarizations. This is achieved by first converting the STSG to an MBOT and then binarizing the MBOT.
  • Input/Output Restriction: MBOTs allow for regular restriction of the input language with better complexity than STSGs, especially after binarization.
  • Composition: MBOTs can be composed, meaning two transformations can be combined to form a new one. This is a significant advantage over STSGs, for which composition is generally not possible. The paper outlines a construction for MBOT composition.
  • Forward/Backward Application: While MBOTs can efficiently handle forward and backward application when equivalent to STSGs, their full expressive power (due to the finite-copying property) can lead to non-regular domains/ranges, making these applications potentially impossible.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • MBOTs as a Superior Alternative: The core insight is that MBOTs, while more expressive, offer substantial algorithmic benefits over STSGs for essential MT operations, making them a more practical choice.
  • Linear-Time STSG-to-MBOT Conversion: The ability to convert any STSG to an equivalent MBOT in linear time is a critical enabler, allowing us to "upgrade" STSG-based systems to benefit from MBOT algorithms.
  • Full Binarization is Key: The paper emphasizes that full binarization, which is achievable for MBOTs, is crucial for improving efficiency and enabling operations like composition.
  • Composition is a Major Win: The fact that MBOTs can be composed, while STSGs generally cannot, is a significant advantage for building complex MT systems by combining simpler components.
  • Trade-off with Expressiveness: While MBOTs offer algorithmic advantages, their full expressive power can sometimes hinder operations like forward/backward application if the resulting domain or range is not a regular tree language.

Key Results

  • Every STSG can be transformed into an equivalent MBOT in linear time.
  • MBOTs can be fully binarized in linear time, while STSGs cannot in general.
  • The BAR-HILLEL construction for input restriction on MBOTs has a complexity of O(|M|·|S|³), which is better than the O(|M|·|S|²rk(M)+5) for STSGs.
  • MBOTs can be composed, whereas STSGs generally cannot.
  • The paper provides a construction for MBOT composition with a complexity of O(|M'|·|M"|·|S'"|rk(M')), where rk(M') is the maximal rank of a state in M'.

Limitations and Future Work

  • Forward/Backward Application Limitation: The paper acknowledges that the full expressive power of MBOTs (finite-copying property) can lead to non-regular domains/ranges, making forward and backward application potentially impossible. This is presented as a warning for direct MBOT training.
  • Composition Complexity: While composition is possible for MBOTs, the complexity can still be high, especially concerning the rank of states.
  • Output Restriction Complexity: The paper suggests that a similar construction for the output side of MBOTs might suffer from higher complexity, comparable to STSGs.
  • Future Work: The paper implicitly suggests further investigation into the practical implications of MBOTs for MT, particularly in scenarios where their full expressive power is leveraged. It also highlights the importance of the one-symbol normal form for achieving these algorithmic benefits.

Summary updated

BibTeX
@inproceedings{maletti2010why,
  author = {Andreas Maletti},
  title = {{Why Synchronous Tree Substitution Grammars?}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}

Loading related content...

Figure