We present a novel discriminative approach to parsing inspired by the
large-margin criterion underlying support vector machines. Our formulation
uses a factorization analogous to the standard dynamic programs for
parsing. In particular, it allows one to efficiently learn a model which
discriminates among the entire space of parse trees, as opposed to reranking
the top few candidates. Our models can condition on arbitrary features of
input sentences, thus incorporating an important kind of lexical information
without the added algorithmic complexity of modeling headedness. We provide
an efficient algorithm for learning such models and show experimental evidence
of the model's improved performance over a natural baseline model and a
lexicalized probabilistic context-free grammar.