An Empirical Analysis of Optimization for Max-Margin NLP
Jonathan K. Kummerfeld, Taylor Berg-Kirkpatrick, Dan Klein · 2015
Despite the convexity of structured maxmargin objectives (Taskar et al., 2004;Tsochantaridis et al., 2004), the many ways to optimize them are not equally effective in practice.We compare a range of online optimization methods over a variety of structured NLP tasks (coreference, summarization, parsing, etc) and find several broad trends.First, margin methods do tend to outperform both likelihood and the perceptron.Second, for max-margin objectives, primal optimization methods are often more robust and progress faster than dual methods.This advantage is most pronounced for tasks with dense or continuous-valued features.Overall, we argue for a particularly simple online primal subgradient descent method that, despite being rarely mentioned in the literature, is surprisingly effective in relation to its alternatives.