Efficient Algorithms for Richer Formalisms: Parsing and Machine Translation

Liang HuangNAACL 2006

TL;DR

This paper introduces novel, efficient algorithms for parsing and machine translation that handle richer linguistic formalisms. The authors present a new k-best parsing algorithm that is both fast and exact, and a syntax-directed translation framework that effectively handles word reordering across languages, leading to improved translation quality and speed.

What Problem Does This Paper Address?

Modern natural language processing (NLP) systems often rely on a cascade of modules, where the output of one module (e.g., a single best parse) might not be optimal for the next. To improve performance, especially in tasks like joint parsing and semantic role labeling, or in discriminative training and reranking, it's beneficial to consider multiple possible outputs (k-best lists) rather than just the single best one. However, generating these k-best lists for complex linguistic formalisms can be computationally expensive, often requiring approximations or pruning techniques that sacrifice optimality.

Similarly, machine translation (MT) has seen great progress with phrase-based systems, but incorporating syntactic information is seen as a crucial next step. While syntax-based MT systems exist, they often struggle with significant word reordering between languages, which can be a major source of translation errors. Existing approaches to handle this reordering within formalisms like synchronous context-free grammars (SCFGs) can lead to complex chart items and inefficient decoding.

This paper tackles these challenges by developing efficient algorithms for richer formalisms in both parsing and machine translation, aiming to integrate more linguistic knowledge without sacrificing computational efficiency.

Methods

The paper presents two main algorithmic contributions:

  • Efficient k-best Parsing: The authors introduce a new framework for k-best parsing within the general setting of directed monotonic hypergraphs. They generalize the standard Viterbi algorithm to hypergraphs and propose four k-best algorithms. The most advanced, "Algorithm 3," employs a lazy, recursive approach. It starts with a standard 1-best search and only computes higher-ranked derivations on demand, working backward from the target. This approach is designed to be efficient even for large values of k.
  • Syntax-Directed Translation with Extended Domain of Locality: For machine translation, the paper adapts syntax-directed transduction, a concept from compiler design, to statistical MT. They formalize this using synchronous context-free grammars (SCFGs) and propose an "extended domain of locality" using multi-level left-hand-side (LHS) trees (xRs). This allows the grammar rules to capture larger fragments of the source-side parse tree, which is crucial for handling word reordering. They also introduce a technique called "synchronous binarization" to efficiently convert these SCFGs into a form suitable for parsing algorithms, reducing the problem to binarizing permutations of non-terminal symbols.

Datasets

The paper primarily uses the Penn Treebank for evaluating parsing algorithms. For machine translation experiments, they mention using parallel corpora for English and Chinese, and specifically refer to experiments on the Section 23 of the Penn Treebank for parsing speed tests. They also cite work using parallel corpora for English-to-Chinese translation.

Key Insights and Ideas

  • Lazy Computation for k-best: The idea of delaying computation until it's absolutely necessary (as in Algorithm 3) is a powerful strategy for making k-best algorithms tractable. This "laziness" allows for significant overhead reduction, especially when only a moderate number of best candidates are needed.
  • Hypergraphs as a Unified Framework: Using directed monotonic hypergraphs provides a general and powerful framework for various parsing tasks, including k-best parsing, allowing for elegant extensions of classical algorithms.
  • Extended Domain of Locality for Reordering: Capturing larger syntactic fragments in translation rules (xRs) is key to handling significant word reordering, which is a common challenge in MT between languages with different word orders (e.g., English SVO vs. Arabic SOV).
  • Synchronous Binarization: This technique is critical for making complex, syntax-based MT models efficient. By binarizing rules synchronously, they enable the use of efficient parsing algorithms (like CKY) while preserving the ability to handle reordering.
  • Quality-Speed Trade-off: The work demonstrates that richer formalisms don't necessarily mean sacrificing efficiency. Their algorithms achieve both improved translation quality and faster processing speeds.

Key Results

  • k-best Parsing Speed: Algorithm 3 for k-best parsing shows very little overhead even for large k (up to 10⁶), as demonstrated by experiments on the Bikel parser (Figure 1).
  • MT Quality Improvement: Synchronous binarization significantly improves translation quality (BLEU score) compared to monolingual binarization in a state-of-the-art syntax-based MT system (Table 1 shows a jump from 36.25 to 38.44 BLEU).
  • Efficient Translation Algorithm: The proposed syntax-directed translation algorithm, when combined with xRs rules, can be implemented using dynamic programming with memoization, running in O(n) time where n is the input string length.
  • Promising English-to-Chinese MT: Initial experiments on English-to-Chinese translation using xRs rules show promising translation quality and fast translation speed.

Limitations and Future Work

  • Parser Availability: The authors note that they are performing English-to-Chinese translation partly due to the lack of a sufficiently good Chinese parser for the reverse direction.
  • Future Work: The paper suggests that the developed algorithms and frameworks are foundational for building more linguistically informed and efficient NLP systems. The success of the syntax-directed translation with extended domain of locality points towards further exploration of richer formalisms for MT. The re-implementation of their k-best parsing algorithms by other researchers also indicates the broad applicability and impact of their work.

Summary updated

BibTeX
@inproceedings{huang2006efficient,
  author = {Liang Huang},
  title = {{Efficient Algorithms for Richer Formalisms: Parsing and Machine Translation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
}
Figure