Our formulations offer the following comparative advantages: • The numbers of variables and constraints are polynomial in the sentence length, as opposed to requiring exponentially many constraints, eliminating the need for incremental procedures like the cutting-plane algorithm; • LP relaxations permit fast online discriminative training of the constrained model; • Soft constraints may be automatically learned from data.
our formulations handle higher-order arc interactions (like siblings and grandparents), model word valency, and can learn to favor nearly-projective parses.