Two monolingual parses are better than one (synchronous parse)

Chris DyerNAACL 2010

TL;DR

This paper introduces a novel synchronous parsing algorithm that decomposes the problem into two sequential monolingual parses. This "two-parse" approach significantly speeds up synchronous parsing for certain grammars, making it practical for large-scale applications without sacrificing accuracy, and it works with more general grammar types than previous methods.

What Problem Does This Paper Address?

Synchronous parsing is crucial for tasks like machine translation, where the goal is to find the best way to derive a pair of sentences (source and target) from a synchronous context-free grammar (SCFG). However, existing algorithms for general SCFGs can be computationally very expensive, often requiring complex heuristic search strategies to be feasible. The worst-case complexity for binary SCFGs is O(n^4), and even with restricted grammar forms (like ITGs), the complexity is O(n^3). This high computational cost hinders the application of SCFGs in large-scale systems. The paper aims to develop a more efficient synchronous parsing algorithm that is practical for real-world use.

Methods

The core innovation is reframing synchronous parsing as a composition of relations, specifically as the composition of an FST (representing the source sentence) with an SCFG (the translation model), and then composing that result with another FST (representing the target sentence). This is expressed as (F ◦ G) ◦ E or F ◦ (G ◦ E).

The key idea is that each composition step can be performed using standard, efficient monolingual parsing algorithms (like CKY or Earley).

  1. First Monolingual Parse: The source sentence (represented as an FST) is parsed against the SCFG. This produces a "parse forest" which is itself a CFG.
  2. Second Monolingual Parse: The target sentence (represented as an FST) is then parsed against the CFG derived from the first step.

This decomposition avoids the direct O(n^4) or O(n^3) complexity of traditional synchronous parsers. The paper also notes that the resulting SCFGs do not need to be in a specific "normal form" (like ITGs), making the approach more flexible.

Datasets

Not discussed in the paper. The experiments use existing Arabic-English phrasal ITG alignment tasks and "Hiero" grammars, implying the use of standard parallel corpora for these tasks, but specific dataset names are not provided.

Key Insights and Ideas

  • Decomposition is Key: Breaking down the complex synchronous parsing problem into two simpler, sequential monolingual parsing steps is the central insight. This leverages existing efficient parsing technology.
  • Practical Efficiency: The "two-parse" approach offers significant average-case speedups, making synchronous parsing feasible for large-scale applications where previous methods were too slow.
  • Generality: The algorithm is not restricted to specific, highly constrained grammar formalisms (like ITGs), allowing it to work with more general SCFGs.
  • Connection to FST Composition: The paper frames the problem in terms of FST composition, providing a clear theoretical basis for the two-parse approach.

Key Results

  • Significant Speedup: The two-parse algorithm is substantially faster than previous synchronous parsing algorithms. For an Arabic-English phrasal ITG alignment task, it completed in less than 4 hours, compared to over 1 week for a baseline algorithm.
  • Practical Performance: The average run-time for the two-parse algorithm was 0.20 seconds per sentence, compared to 7.31 seconds for a "cube-parsing" technique on "Hiero" grammars.
  • Worst-Case Complexity: While the average-case performance is excellent, the worst-case complexity for binary SCFGs is still O(n^6) (due to the size of the intermediate parse forest), which is comparable to the O(n^3) of ITG algorithms. However, the paper emphasizes that this worst-case is rarely hit in practice.

Limitations and Future Work

  • Worst-Case Complexity: The O(n^6) worst-case complexity, while rarely encountered, is still a theoretical limitation. The authors suggest that faster composition algorithms incorporating top-down filtering might be discovered.
  • Grammar Restrictions: The analysis primarily holds for rank-2 and e-free grammars. The paper notes that extending this to grammars with e-productions or higher ranks is left for future work.
  • Implementation Details: The paper mentions that their ITG aligner was minimal and only computed probabilities, whereas the two-parse aligner stored the complete forest. This difference in implementation might affect direct comparisons, though the speedup is still dramatic.

Summary updated

BibTeX
@inproceedings{dyer2010two,
  author = {Chris Dyer},
  title = {{Two monolingual parses are better than one (synchronous parse)}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure