Paper: Nonconvex Global Optimization for Latent-Variable Models

ACL ID P13-1044
Title Nonconvex Global Optimization for Latent-Variable Models
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2013

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 ho...