Taskar et al. 2004. Max-margin Parsing

Max-margin parsing, by Ben Taskar, Taskar, B. and Klein, D. and Collins, M. and Koller, D. and Manning, C.. In Proc. EMNLP, 2004.

This Paper is available online [1].

Summary

This paper presents a novel approach to parsing by maximizing separating margins using SVMs. They show how we can reformulate the parsing problem as a discriminative task, which allow an arbitrary number of features to be used. Also, such a formulation allows them to incorporate a loss function that directly penalizes incorrect parse trees appropriately.

Brief description of the method

Instead of a probabilistic interpretation for parse trees, we seek to find:

$y_{i}=\arg \max _{y\in \mathbf {G} (x_{i})}\langle \mathbf {w} ,\Phi (x_{i},y)\rangle$

for all sentences $x_{i}$ in the training data, $y_{i}$ being the parse tree, $\mathbf {G} (x_{i})$ the set of possible parses for $x_{i}$.

Formulating it as an optimization problem,

$\max _{\gamma }\{\langle \mathbf {w} ,\Phi _{i,y_{i}}-\Phi _{i,y}\rangle \geq \gamma L_{i,y}\}\forall y\in \mathbf {G} (x_{i}),||\mathbf {w} ||^{2}\leq 1$

Related Papers

In Bartlett et al NIPS 2004, they used the EG algorithm for large margin structured classification.