An Empirical Analysis of Optimization for Max-Margin NLP

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 273–279, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. An Empirical Analysis of Optimization for Max-Margin NLP Jonathan K. Kummerfeld, Taylor Berg-Kirkpatrick and Dan Klein Computer Science Division University of California, Berkeley Berkeley, CA 94720, USA {jkk,tberg,klein}@cs.berkeley.edu Abstract Despite the convexity of structured max- margin objectives (Taskar et al., 2004; Tsochantaridis et al., 2004), the many ways to optimize them are not equally ef- fective in practice. We compare a range of online optimization methods over a vari- ety of structured NLP tasks (coreference, summarization, parsing, etc) and find sev- eral 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 pri- mal subgradient descent method that, de- spite being rarely mentioned in the litera- ture, is surprisingly effective in relation to its alternatives. 1 Introduction Structured discriminative models have proven ef- fective across a range of tasks in NLP includ- ing tagging (Lafferty et al., 2001; Collins, 2002), reranking parses (Charniak and Johnson, 2005), and many more (Taskar, 2004; Smith, 2011). Common approaches to training such models in- clude margin methods, likelihood methods, and mistake-driven procedures like the averaged per- ceptron algorithm. In this paper, we primarily con- sider the relative empirical behavior of several on- line optimization methods for margin-based objec- tives, with secondary attention to other approaches for calibration. It is increasingly common to train structured models using a max-margin objective that incor- porates a loss function that decomposes in the same way as the dynamic program used for in- ference (Taskar, 2004). Fortunately, most struc- tured margin objectives are convex, so a range of optimization methods with similar theoretical properties are available – in short, any of these methods will work in the end. However, in prac- tice, how fast each method converges varies across tasks. Moreover, some of the most popular meth- ods more loosely associated with the margin ob- jective, such as the MIRA algorithm (Crammer and Singer, 2003) or even the averaged perceptron (Freund and Schapire, 1999) are not global opti- mizations and can have different properties. We analyze a range of methods empirically, to understand on which tasks and with which fea- ture types, they are most effective. We modified six existing, high-performance, systems to enable loss-augmented decoding, and trained these mod- els with six different methods. We have released our learning code as a Java library.1 Our results provide support for the conventional wisdom that margin-based optimization is broadly effective, frequently outperforming likelihood optimization and the perceptron algorithm. We also found that directly optimizing the primal structured margin objective based on subgradients calculated from single training instances is surprisingly effective, performing consistently well across all tasks. 2 Learning Algorithms We implemented a range of optimization …

Content truncated to 500 words