Paper: Online Learning for Inexact Hypergraph Search

ACL ID D13-1093
Title Online Learning for Inexact Hypergraph Search
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2013

Online learning algorithms like the percep- tron are widely used for structured predic- tion 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.