  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.
