Online Learning for Inexact Hypergraph Search

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 908–913, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Online Learning for Inexact Hypergraph Search Hao Zhang Google haozhang@google.com Liang Huang Kai Zhao City University of New York {lhuang@cs.qc,kzhao@gc}.cuny.edu Ryan McDonald Google ryanmcd@google.com Abstract 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. 1 Introduction Structured prediction problems generally deal with exponentially many outputs, often making exact search infeasible. For sequential search problems, such as tagging and incremental parsing, beam search coupled with perceptron algorithms that ac- count for potential search errors have been shown to be a powerful combination (Collins and Roark, 2004; Daum´e and Marcu, 2005; Zhang and Clark, 2008; Huang et al., 2012). However, sequen- tial search algorithms, and in particular left-to-right beam search (Collins and Roark, 2004; Zhang and Clark, 2008), squeeze inference into a very narrow space. To address this, Huang (2008) formulated constituency parsing as approximate bottom-up in- ference in order to compactly represent an exponen- tial number of outputs while scoring features of ar- bitrary scope. This idea was adapted to graph-based dependency parsers by Zhang and McDonald (2012) and shown to outperform left-to-right beam search. Both these examples, bottom-up approximate de- pendency and constituency parsing, can be viewed as specific instances of inexact hypergraph search. Typically, the approximation is accomplished by cube-pruning throughout the hypergraph (Chiang, 2007). Unfortunately, as the scope of features at each node increases, the inexactness of search and its negative impact on learning can potentially be ex- acerbated. Unlike sequential search, the impact on learning of approximate hypergraph search – as well as methods to mitigate any ill effects – has not been studied. Motivated by this, we develop online learn- ing algorithms for inexact hypergraph search by gen- eralizing the violation-fixing percepron of Huang et al. (2012). We empirically validate the benefit of this approach within the cube-pruning dependency parser of Zhang and McDonald (2012). 2 Structured Perceptron for Inexact Hypergraph Search The structured perceptron algorithm (Collins, 2002) is a general learning algorithm. Given training in- stances (x, ˆy), the algorithm first solves the decod- ing problem y′ = argmaxy∈Y(x) w · f(x, y) given the weight vector w for the high-dimensional fea- ture representation f of the mapping (x, y), where y′ is the prediction under the current model, ˆy is the gold output and Y(x) …

Content truncated to 500 words