Online Learning for Inexact Hypergraph Search
Hao Zhang, Liang Huang, Kai Zhao, Ryan McDonald · 2013
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.