Penalized Expectation Propagation for Graphical Models over Strings

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 932–942, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics Penalized Expectation Propagation for Graphical Models over Strings∗ Ryan Cotterell and Jason Eisner Department of Computer Science, Johns Hopkins University {ryan.cotterell,jason}@cs.jhu.edu Abstract We present penalized expectation propaga- tion (PEP), a novel algorithm for approximate inference in graphical models. Expectation propagation is a variant of loopy belief prop- agation that keeps messages tractable by pro- jecting them back into a given family of func- tions. Our extension, PEP, uses a structured- sparsity penalty to encourage simple mes- sages, thus balancing speed and accuracy. We specifically show how to instantiate PEP in the case of string-valued random variables, where we adaptively approximate finite-state distri- butions by variable-order n-gram models. On phonological inference problems, we obtain substantial speedup over previous related al- gorithms with no significant loss in accuracy. 1 Introduction Graphical models are well-suited to reasoning about linguistic structure in the presence of uncertainty. Such models typically use discrete random vari- ables, where each variable ranges over a finite set of values such as words or tags. But a variable can also be allowed to range over an infinite space of dis- crete structures—in particular, the set of all strings, a case first explored by Bouchard-Côté et al. (2007). This setting arises because human languages make use of many word forms. These strings are systematically related in their spellings due to lin- guistic processes such as morphology, phonology, abbreviation, copying error and historical change. To analyze or predict novel strings, we can model the joint distribution of many related strings at once. Under a graphical model, the joint probability of an assignment tuple is modeled as a product of poten- tials on sub-tuples, each of which is usually modeled in turn by a weighted finite-state machine. In general, we wish to infer the values of un- known strings in the graphical model. Deterministic ∗This material is based upon work supported by the Na- tional Science Foundation under Grant No. 1423276, and by a Fulbright Research Scholarship to the first author. approaches to this problem have focused on belief propagation (BP), a message-passing algorithm that is exact on acyclic graphical models and approxi- mate on cyclic (“loopy”) ones (Murphy et al., 1999). But in both cases, further heuristic approximations of the BP messages are generally used for speed. In this paper, we develop a more principled and flexible way to approximate the messages, using variable-order n-gram models. We first develop a version of expectation propa- gation (EP) for string-valued variables. EP offers a principled way to approximate BP messages by dis- tributions from a fixed family—e.g., by trigram mod- els. Each message update is found by minimizing a certain KL-divergence (Minka, 2001a). Second, we generalize to variable-order models. To do this, we augment EP’s minimization prob- lem with a novel penalty term that keeps the num- ber of n-grams finite. In general, we …

Content truncated to 500 words