Non-projective Dependency Parsing using Spanning Tree Algorithms

3 Online Large Margin Learning

1. How does MIRA learn the weights for structured outputs like dependency trees?
   Online: for each training sentence, find the new weights closest to the old ones, \(\min \|\mathbf{w}^{(i+1)} - \mathbf{w}^{(i)}\|\), such that the correct tree outscores every other tree \(y'\) by at least its loss: \(s(x_t, y_t) - s(x_t, y') \ge L(y_t, y')\). The final weights are averaged over all updates, as in the averaged perceptron.
   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §3, p. 527
2. What loss does MIRA use for dependency trees in McDonald et al. (2005)?
   The number of words with an incorrect parent relative to the correct tree, closely related to the Hamming loss used for sequences.
   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §3, p. 527