Dependency Parsing by Belief Propagation

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 145–156, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Dependency Parsing by Belief Propagation∗ David A. Smith and Jason Eisner Dept. of Computer Science, Johns Hopkins University Balitmore, MD 21218, USA {dasmith,eisner}@jhu.edu Abstract We formulate dependency parsing as a graphical model with the novel ingredient of global constraints. We show how to apply loopy belief propagation (BP), a simple and effective tool for approximate learning and inference. As a parsing algorithm, BP is both asymptotically and em- pirically efficient. Even with second-order features or la- tent variables, which would make exact parsing consider- ably slower or NP-hard, BP needs only O(n3) time with a small constant factor. Furthermore, such features sig- nificantly improve parse accuracy over exact first-order methods. Incorporating additional features would in- crease the runtime additively rather than multiplicatively. 1 Introduction Computational linguists worry constantly about run- time. Sometimes we oversimplify our models, trad- ing linguistic nuance for fast dynamic programming. Alternatively, we write down a better but intractable model and then use approximations. The CL com- munity has often approximated using heavy pruning or reranking, but is beginning to adopt other meth- ods from the machine learning community, such as Gibbs sampling, rejection sampling, and certain variational approximations. We propose borrowing a different approximation technique from machine learning, namely, loopy be- lief propagation (BP). In this paper, we show that BP can be used to train and decode complex pars- ing models. Our approach calls a simpler parser as a subroutine, so it still exploits the useful, well-studied combinatorial structure of the parsing problem.1 2 Overview and Related Work We wish to make a dependency parse’s score de- pend on higher-order features, which consider ar- ∗This work was supported by the Human Language Tech- nology Center of Excellence. 1As do constraint relaxation (Tromble and Eisner, 2006) and forest reranking (Huang, 2008). In contrast, generic NP-hard solution techniques like Integer Linear Programming (Riedel and Clarke, 2006) know nothing about optimal substructure. bitrary interactions among two or more edges in the parse (and perhaps also other latent variables such as part-of-speech tags or edge labels). Such features can help accuracy—as we show. Alas, they raise the polynomial runtime of projective parsing, and ren- der non-projective parsing NP-hard. Hence we seek approximations. We will show how BP’s “message-passing” disci- pline offers a principled way for higher-order fea- tures to incrementally adjust the numerical edge weights that are fed to a fast first-order parser. Thus the first-order parser is influenced by higher-order interactions among edges—but not asymptotically slowed down by considering the interactions itself. BP’s behavior in our setup can be understood intu- itively as follows. Inasmuch as the first-order parser finds that edge e is probable, the higher-order fea- tures will kick in and discourage other edges e′ to the extent that they prefer not to coexist with e.2 Thus, the next call to the first-order parser assigns lower probabilities to parses that contain these e′. (The …

Content truncated to 500 words