The Structured Weighted Violations Perceptron Algorithm

Published in Empirical Methods in Natural Language Processing (EMNLP), 2016

Recommended citation: "The Structured Weighted Violations Perceptron Algorithm." Rotem Dror and Roi Reichart. EMNLP 2016.

Abstract We present the Structured Weighted Violations Perceptron (SWVP) algorithm, a new structured 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 dependency parsing results.