The Structured Weighted Violations Perceptron Algorithm
This work addresses structured prediction challenges for machine learning researchers, offering an incremental improvement over existing methods.
The paper tackles the problem of structured prediction by introducing the Structured Weighted Violations Perceptron (SWVP) algorithm, which generalizes the Collins Structured Perceptron and explicitly exploits label structure, resulting in tighter bounds and improved performance in synthetic HMM experiments and initial dependency parsing.
We present the Structured Weighted Violations Perceptron (SWVP) algorithm, a new structured prediction algorithm that generalizes the Collins Structured Perceptron (CSP). 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.