Online Learning for Inexact Hypergraph Search

Hao Zhang, Liang Huang, Kai Zhao, Ryan T. McDonaldEMNLP 2013 · OpenReview

Abstract

Online learning algorithms like the perceptron are widely used for structured prediction tasks. For sequential search problems, like left-to-right tagging and parsing, beam search has been successfully combined with perceptron variants that accommodate search errors (Collins and Roark, 2004; Huang et al., 2012). However, perceptron training with inexact search is less studied for bottom-up parsing and, more generally, inference over hypergraphs. In this paper, we generalize the violation-fixing perceptron of Huang et al. (2012) to hypergraphs and apply it to the cube-pruning parser of Zhang and McDonald (2012). This results in the highest reported scores on WSJ evaluation set (UAS 93.50% and LAS 92.41% respectively) without the aid of additional resources.

Introduction

In structured prediction tasks like natural language parsing, the number of possible outputs is exponential. To handle this, researchers often use "inexact search" methods like cube pruning to find the most likely parse tree quickly. However, a challenge arises when training these models with the standard Structured Perceptron. The perceptron algorithm assumes that errors stem from incorrect weights. Yet, with inexact search, a model might fail simply because the search algorithm pruned the correct answer too early.

When search is inexact, the model can encounter "non-violations"—cases where the gold standard scores higher than the predicted output, but the search failed to find an even higher-scoring (but incorrect) output. Standard perceptron updates fail to converge here, leading to sub-optimal models. While this problem was previously addressed for sequential search, this paper generalizes the solution to bottom-up hypergraph search.

Methods: Violation-Fixing for Hypergraphs

The authors generalize the "violation-fixing" perceptron to hypergraphs. Instead of updating at the root, they identify internal nodes where the "violation" (the score difference between the predicted and gold subtrees) is most prominent. They propose two specific update strategies:

  1. Single-node max-violation (s-max): The algorithm traverses the gold tree to find the specific node where the violation is largest and performs a targeted update for that subtree.
  2. Parallel max-violation (p-max): This strategy identifies a "frontier" of non-overlapping nodes that each contain a maximum violation for their respective spans and updates them in parallel.

These methods ensure the model is always learning from "true" violations—instances where the model's current weights genuinely prefer an incorrect structure over the gold one within the reachable search space.

UAS performance over training epochs for different update strategies.

Evaluation

The approach was evaluated on several major benchmarks, including the Penn WSJ Treebank (English), the Chinese Penn Treebank (CTB-5), and the CoNLL 2006/2007 shared task datasets covering 17 different languages.

Key Results

The parser achieved state-of-the-art performance on the WSJ evaluation set with 93.50% UAS and 92.41% LAS, which were the highest reported scores at the time without using external resources. The method improved UAS in 16 out of 17 languages in the CoNLL tasks compared to the baseline, achieving the best published results for 7 of those languages. Despite the added complexity of finding max-violations, the parser remains efficient, processing 200–300 tokens per second.

Comparison of the cube-pruning parser with state-of-the-art systems on English and Chinese benchmarks.

Discussion

A core insight of this work is that search and learning are deeply intertwined; learning algorithms must account for search approximations to remain stable. In complex structures like parse trees, errors are often deep-seated. By localizing updates to "max-violation" nodes, the learning signal becomes more targeted and mathematically correct for convergence. The authors found that on difficult datasets like Penn-S, up to 36% of root updates were actually "non-violations." The violation-fixing approach successfully converts these into useful learning signals.

Conclusion

While the current parser is based on the Eisner algorithm for projective dependency trees, the hypergraph framework is theoretically applicable to any bottom-up inference task, including constituency parsing or syntax-based machine translation. Future work includes extending the framework to natively handle non-projectivity, which would further benefit performance for languages like German or Czech.

Summary updated

Abstract

Online learning algorithms like the perceptron are widely used for structured prediction tasks. For sequential search problems, like left-to-right tagging and parsing, beam search has been successfully combined with perceptron variants that accommodate search errors (Collins and Roark, 2004; Huang et al., 2012). However, perceptron training with inexact search is less studied for bottom-up parsing and, more generally, inference over hypergraphs. In this paper, we generalize the violation-fixing perceptron of Huang et al. (2012) to hypergraphs and apply it to the cube-pruning parser of Zhang and McDonald (2012). This results in the highest reported scores on WSJ evaluation set (UAS 93.50% and LAS 92.41% respectively) without the aid of additional resources.
BibTeX
@inproceedings{zhang2013online,
  author = {Hao Zhang and Liang Huang and Kai Zhao and Ryan T. McDonald},
  title = {{Online Learning for Inexact Hypergraph Search}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2013},
  url = {https://openreview.net/forum?id=H1Vcuzfdbr},
}
Figure