A Better N-Best List: Practical Determinization of Weighted Finite Tree Automata

Jonathan May, Kevin Knight

Abstract

Ranked lists of output trees from syntactic statistical NLP applications frequently contain multiple repeated entries. This redundancy leads to misrepresentation of tree weight and reduced information for debugging and tuning purposes. It is chiefly due to nondeterminism in the weighted automata that produce the results. We introduce an algorithm that determinizes such automata while preserving proper weights, returning the sum of the weight of all multiply derived trees. We also demonstrate our algorithm's effectiveness on two large-scale tasks.

Introduction

In many statistical natural language processing (NLP) tasks, such as machine translation or parsing, models generate a list of top results by searching through a space of "derivations"—the specific sequences of rules used to build a structure. However, a significant problem arises: different derivations can often produce the exact same output tree.

This leads to several critical issues in practical applications:

  1. Redundancy: A top-10 list might contain only a few unique trees, wasting slots that could have held useful alternatives.
  2. Weight Distortion: The true probability of a tree is the sum of the probabilities of all its possible derivations. When these are split, the most likely tree might not appear at the top because its individual derivations are lower-ranked.
  3. Downstream Failure: Reranking systems and tuning processes (like MERT) perform poorly when fed lists of near-identical candidates.

While this problem was addressed for strings (finite-state automata) in the late 90s, tree automata present a much higher complexity due to their branching, hierarchical structure.

Methodology: Determinizing Tree Automata

The authors propose an algorithm for the determinization of weighted finite tree automata (WFTA). The core logic is an extension of the "powerset construction" used to convert non-deterministic automata into deterministic ones.

The Core Logic and Residual Weights

To handle weights correctly, the algorithm utilizes residual weights. When the algorithm merges multiple paths into a single path, it tracks the "leftover" weight proportion for each original state. This ensures that the final deterministic automaton produces a single derivation for each tree with a weight equal to the sum of all original derivations.

Figure 3: Illustration of the determinization step (a) to (b) showing the calculation of residual weights.

From Strings to Trees

Unlike string automata, tree automata operate on hypergraphs. A transition takes a vector of states (the children) and produces a new state (the parent). The algorithm adapts its bookkeeping to handle these state vectors, allowing it to process the hierarchical nature of natural language effectively.

Evaluation and Key Insights

The algorithm was evaluated on two large-scale tasks: Machine Translation (Chinese to English) and Data-Oriented Parsing (DOP) using the Penn Treebank.

  • Derivations vs. Trees: The study confirms that the "best" result is often hidden because its probability mass is fragmented across identical-looking outputs. In the MT task, the "top" tree changed in 77.6% of cases after determinization.
  • Massive Redundancy: In MT, an average of 86.3% of trees in undeterminized forests were duplicates. In parsing, forest sizes were reduced by factors up to 900,000.

Key Results

Translation Quality

Determinization led to a significant improvement in translation quality as measured by the BLEU score. By correctly summing the weights of all derivations for a tree, the system moved from a BLEU of 21.87 (best derivation) to 24.17 (best tree). This outperformed the common "crunching" heuristic, which only reached 23.33.

Figure 6: BLEU score comparison between undeterminized, top-500 crunching, and determinized methods.

Parsing Accuracy

For the DOP task, determinization improved the F-measure from 80.20 to 80.40. While the numerical increase is smaller than in MT, the astronomical reduction in the search space makes the results far more representative of the true model.

Conclusion and Future Work

Despite the theoretical NP-complete complexity of determinization, the algorithm proved practical for real-world NLP forests, provided that cycles (recursion) were removed. Future work remains to extend this to "string determinization" of tree automata, as users often care about the unique strings (yields) produced by trees, which can also have multiple derivations.

Summary updated

Abstract

Ranked lists of output trees from syntactic statistical NLP applications frequently contain multiple repeated entries. This redundancy leads to misrepresentation of tree weight and reduced information for debugging and tuning purposes. It is chiefly due to nondeterminism in the weighted automata that produce the results. We introduce an algorithm that determinizes such automata while preserving proper weights, returning the sum of the weight of all multiply derived trees. We also demonstrate our algorithm's effectiveness on two large-scale tasks.
BibTeX
@inproceedings{may2006better,
  author = {Jonathan May and Kevin Knight},
  title = {{A Better N-Best List: Practical Determinization of Weighted Finite Tree Automata}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
  url = {https://openreview.net/forum?id=HkNMeQb_ZB},
}
Figure