The Structured Weighted Violations Perceptron Algorithm

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 469–478, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics The Structured Weighted Violations Perceptron Algorithm Rotem Dror and Roi Reichart Faculty of Industrial Engineering and Management, Technion, IIT {rtmdrr@campus|roiri@ie}.technion.ac.il Abstract We present the Structured Weighted Violations Perceptron (SWVP) algorithm, a new struc- tured prediction algorithm that generalizes the Collins Structured Perceptron (CSP, (Collins, 2002)). Unlike CSP, the update rule of SWVP explicitly exploits the internal structure of the predicted labels. We prove the convergence of SWVP for linearly separable training sets, provide mistake and generalization bounds, and show that in the general case these bounds are tighter than those of the CSP special case. In synthetic data experiments with data drawn from an HMM, various variants of SWVP substantially outperform its CSP special case. SWVP also provides encouraging initial de- pendency parsing results. 1 Introduction The structured perceptron ((Collins, 2002), hence- forth denoted CSP) is a prominent training algo- rithm for structured prediction models in NLP, due to its effective parameter estimation and simple im- plementation. It has been utilized in numerous NLP applications including word segmentation and POS tagging (Zhang and Clark, 2008), dependency pars- ing (Koo and Collins, 2010; Goldberg and Elhadad, 2010; Martins et al., 2013), semantic parsing (Zettle- moyer and Collins, 2007) and information extrac- tion (Hoffmann et al., 2011; Reichart and Barzilay, 2012), if to name just a few. Like some training algorithms in structured pre- diction (e.g. structured SVM (Taskar et al., 2004; Tsochantaridis et al., 2005), MIRA (Crammer and Singer, 2003) and LaSo (Daum´e III and Marcu, 2005)), CSP considers in its update rule the differ- ence between complete predicted and gold standard labels (Sec. 2). Unlike others (e.g. factored MIRA (McDonald et al., 2005b; McDonald et al., 2005a) and dual-loss based methods (Meshi et al., 2010)) it does not exploit the structure of the predicted label. This may result in valuable information being lost. Consider, for example, the gold and predicted de- pendency trees of Figure 1. The substantial differ- ence between the trees may be mostly due to the dif- ference in roots (are and worse, respectively). Pa- rameter update w.r.t this mistake may thus be more useful than an update w.r.t the complete trees. In this work we present a new perceptron algo- rithm with an update rule that exploits the struc- ture of a predicted label when it differs from the gold label (Section 3). Our algorithm is called The Structured Weighted Violations Perceptron (SWVP) as its update rule is based on a weighted sum of up- dates w.r.t violating assignments and non-violating assignments: assignments to the input example, de- rived from the predicted label, that score higher (for violations) and lower (for non-violations) than the gold standard label according to the current model. Our concept of violating assignment is based on Huang et al. (2012) that presented a variant of the CSP algorithm where the argmax inference problem is replaced with a violation …

Content truncated to 500 words