Nonconvex Global Optimization for Latent-Variable Models

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 444–454, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Nonconvex Global Optimization for Latent-Variable Models∗ Matthew R. Gormley Jason Eisner Department of Computer Science Johns Hopkins University, Baltimore, MD {mrg,jason}@cs.jhu.edu Abstract Many models in NLP involve latent vari- ables, such as unknown parses, tags, or alignments. Finding the optimal model pa- rameters is then usually a difficult noncon- vex optimization problem. The usual prac- tice is to settle for local optimization meth- ods such as EM or gradient ascent. We explore how one might instead search for a global optimum in parameter space, using branch-and-bound. Our method would eventually find the global maxi- mum (up to a user-specified ϵ) if run for long enough, but at any point can return a suboptimal solution together with an up- per bound on the global maximum. As an illustrative case, we study a gener- ative model for dependency parsing. We search for the maximum-likelihood model parameters and corpus parse, subject to posterior constraints. We show how to for- mulate this as a mixed integer quadratic programming problem with nonlinear con- straints. We use the Reformulation Lin- earization Technique to produce convex relaxations during branch-and-bound. Al- though these techniques do not yet pro- vide a practical solution to our instance of this NP-hard problem, they sometimes find better solutions than Viterbi EM with random restarts, in the same time. 1 Introduction Rich models with latent linguistic variables are popular in computational linguistics, but in gen- eral it is not known how to find their optimal pa- rameters. In this paper, we present some “new” at- tacks for this common optimization setting, drawn from the mathematical programming toolbox. We focus on the well-studied but unsolved task of unsupervised dependency parsing (i.e., depen- ∗This research was partially funded by the JHU Human Language Technology Center of Excellence. -180.2 -231.0 -254.3 -387.1 -287.3 -311.1 -467.5 -298 -342 !5 " -0.6 -0.6 " !5 !5 " -2 -2 " !5 !3 " -0.6 -0.6 " !3 !2 " -0.6 -0.6 " !2 Branch-and-bound tree: Incumbent solution: $ $ M ￿ m=1 θmf·m = −400 θ = [−0.1, −0.6, −20, −1.3, . . . ] f = [4, 0, 2, 21, . . .] M ￿ i=1 θmfm = −400 Figure 1: Each node contains a local upper bound for its subspace, computed by a relaxation. The node branches on a single model parameter θm to partition its subspace. The lower bound, -400, is given by the best solution seen so far, the incum- bent. The upper bound, -298, is the min of all re- maining leaf nodes. The node with a local bound of -467.5 can be pruned because no solution within its subspace could be better than the incumbent. dency grammar induction). This may be a par- ticularly hard case, but its structure is typical. Many parameter estimation techniques have been attempted, including expectation-maximization (EM) (Klein and Manning, 2004; Spitkovsky et al., …

Content truncated to 500 words