View source for Taskar et al. 2004. Max-margin Parsing

{{MyCiteconference | booktitle = Proc. EMNLP| coauthors = Taskar, B. and Klein, D. and Collins, M. and Koller, D. and Manning, C.| date = 2004| first = Ben| last = Taskar| pages = 305-312| title = Max-margin parsing| url = http://acl.ldc.upenn.edu/acl2004/emnlp/pdf/Taskar.pdf }}

This [[Category::Paper]] is available online [http://acl.ldc.upenn.edu/acl2004/emnlp/pdf/Taskar.pdf].

== Summary ==

This paper presents a novel approach to [[AddressesProblem::Parsing]] by maximizing separating margins using [[UsesMethod::Support Vector Machines]]. 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:

<math>y_i=\arg\max_{y\in\mathbf{G}(x_i)} \langle\mathbf{w}, \Phi(x_i,y)\rangle</math>

for all sentences <math>x_i</math> in the training data, <math>y_i</math> being the parse tree, <math>\mathbf G(x_i)</math> the set of possible parses for <math>x_i</math>.

Formulating it as an optimization problem,

<math>\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</math>

Using SVM, we can find the dual of the above program

<math>\max C\sum_{i,y} \alpha_{i,y}L_{i,y}-\dfrac{1}{2} || C\sum_{i,y} (I_{i,y}-\alpha_{i,y})\Phi_{i,y}||</math>

s.t <math>\sum_y \alpha_{i,y} =1, \forall i; \alpha_{i,y}\geq 0, \forall i,y</math>

where <math>I_{i,y}</math> indicates whether <math>y</math> is the true parse for sentence <math>i</math>

For each sentence, we need to enumerate all possible parse trees, which is exponential in size. However, we can make use of local substructures similar to [[UsesMethod::CYK Parsing | chart parsing dynamic programming algorithm]] to factor these trees into parts like <math>\langle A,s,e,i\rangle</math> and <math>\langle A\rightarrow B C,s,m,e,i\rangle</math>, where <math>s,m,e,i</math> refers to start, split, end points and sentence number respectively.

Therefore, 

<math>\Phi(x,y)=\sum_{r\in R(x,y)}\phi(x,r)</math>

where <math>R(x,y)</math> is the set of all possible parts. <math>\phi</math> can be any function that maps a rule production part to some feature vector representation. In addition, the loss function can also be decomposed into sum of parts similar to above. In the paper, the loss function used was the number of constituent errors made in a parse.

By incorporating parts, the factored dual objective can be expressed in polynomial number of variables, which is in fact cubic in the length of the sentence.

== Results ==

Experiments on the [[UsesDataset::Penn Treebank]] dataset with lexical features achieved 0.43 f-score over the Collins 99 parser.

== Related Papers ==

[[RelatedPaper::McDonald_et_al,_ACL_2005:_Non-projective_dependency_parsing_using_spanning_tree_algorithms]] Margin learning for dependency parsing

[[RelatedPaper::Tsochantaridis,_Joachims_,_Support_vector_machine_learning_for_interdependent_and_structured_output_spaces_2004]] Using SVMs for structured output space.