Dual Decomposition Inference for Graphical Models over Strings

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 917–927, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Dual Decomposition Inference for Graphical Models over Strings∗ Nanyun Peng and Ryan Cotterell and Jason Eisner Department of Computer Science, Johns Hopkins University {npeng1,ryan.cotterell,eisner}@jhu.edu Abstract We investigate dual decomposition for joint MAP inference of many strings. Given an arbitrary graphical model, we de- compose it into small acyclic sub-models, whose MAP configurations can be found by finite-state composition and dynamic programming. We force the solutions of these subproblems to agree on overlap- ping variables, by tuning Lagrange multi- pliers for an adaptively expanding set of variable-length n-gram count features. This is the first inference method for ar- bitrary graphical models over strings that does not require approximations such as random sampling, message simplification, or a bound on string length. Provided that the inference method terminates, it gives a certificate of global optimality (though MAP inference in our setting is undecid- able in general). On our global phonolog- ical inference problems, it always termi- nates, and achieves more accurate results than max-product and sum-product loopy belief propagation. 1 Introduction Graphical models allow expert modeling of com- plex relations and interactions between random variables. Since a graphical model with given pa- rameters defines a probability distribution, it can be used to reconstruct values for unobserved vari- ables. The marginal inference problem is to com- pute the posterior marginal distributions of these variables. The MAP inference (or MPE) prob- lem is to compute the single highest-probability joint assignment to all the unobserved variables. Inference in general graphical models is NP- hard even when the variables’ values are finite dis- crete values such as categories, tags or domains. In this paper, we address the more challenging setting ∗This material is based upon work supported by the Na- tional Science Foundation under Grant No. 1423276. where the variables in the graphical models range over strings. Thus, the domain of the variables is an infinite space of discrete structures. In NLP, such graphical models can deal with large, incompletely observed lexicons. They could be used to model diverse relationships among strings that represent spellings or pronunciations; morphemes, words, phrases (such as named enti- ties and URLs), or utterances; standard or variant forms; clean or noisy forms; contemporary or his- torical forms; underlying or surface forms; source or target language forms. Such relationships arise in domains such as morphology, phonology, his- torical linguistics, translation between related lan- guages, and social media text analysis. In this paper, we assume a given graphical model, whose factors evaluate the relationships among observed and unobserved strings.1 We present a dual decomposition algorithm for MAP inference, which returns a certifiably optimal so- lution when it converges. We demonstrate our method on a graphical model for phonology pro- posed by Cotterell et al. (2015). We show that the method generally converges and that it achieves better results than alternatives. The rest of the paper is arranged as follows: We …

Content truncated to 500 words