Dependency Parsing by Belief Propagation

By David A. Smith, Jason Eisner. 2008

163 citations recorded by the source corpus.

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 empirically efficient. Even with second-order features or latent variables, which would make exact parsing considerably slower or NP-hard, BP needs only O(n3) time with a small constant factor. Furthermore, such features significantly improve parse accuracy over exact first-order methods. Incorporating additional features would increase the runtime additively rather than multiplicatively.

Subfields: Natural Language Processing, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

In Probabilistic & Bayesian Methods

Citations in the corpus

Structured Attention Networks (2017, methodology): “A dependency parser can be partially formalized as a graphical model with the following cliques (Smith & Eisner, 2008): latent variables z ij ∈ { 0 , 1 } for all i (cid:54) = j , which indicates that the i -th word is the parent of the j -th word (i.e. x i → x j ); and a special global constraint…”
Transition-based Dependency Parsing with Rich Non-local Features (2011, methodology): “Various recent attempts have been made to include non-local features into graph-based dependency parsing (Smith and Eisner, 2008; Martins et al., 2009; Koo and Collins, 2010).”
Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation (2011, background): “Earlier work on belief propagation (Smith and Eisner, 2008) is closely related to dual decomposition.”
Finding your friends and following them to where you are (2012, background): “In contrast with random walks, approaches related to our belief propagation method for enforcing and chaining soft transitive constraints have been validated in many areas in the machine learning literature, and are implicitly used in many works on link prediction as a way to solve the underlying pr”
Graphical Models over Multiple Strings (2009, background): “(2004) for chunking and tagging, Sutton and McCallum (2004) for information extraction, Smith and Eisner (2008) for dependency parsing, and Cromierès and Kurohashi (2009) for alignment.”
A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing (2012, methodology): “This idea is closely related to earlier work on the use of combinatorial algorithms within belief propagation, either for the MAP inference problem (Duchi et al., 2007), or for computing marginals (Smith and Eisner, 2008).”
Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers (2013, background): “Approximate parsers have therefore been introduced, based on belief propagation (Smith and Eisner, 2008), dual decomposition (Koo et al.”
Deep Multitask Learning for Semantic Dependency Parsing (2017, methodology): “In syntactic parsing, higher-order structures have commonly been used to model interactions be-tween multiple adjacent arcs in the same dependency tree (Carreras, 2007; Smith and Eisner, 2008; Martins et al., 2009; Zhang et al., 2014, inter alia ).”
Syntactic Processing Using the Generalized Perceptron and Beam Search (2011, background): “…research on the improvement of accuracies by incorporating non-local features via approximation, such as belief propagation for dependency parsing (Smith and Eisner 2008), integer linear programming for dependency parsing (Martins, Smith, and Xing 2009), and forest reranking for phrase-structure…”
Minimum-Risk Training of Approximate CRF-Based NLP Systems (2012, background): “…to use arbitrarily structured graphical models makes it possible to include latent linguistic variables, predict complex structures such as parses (Smith and Eisner, 2008), and do collective prediction in relational domains (Ji and Grish-man, 2011; Benson et al., 2011; Dreyer and Eis-ner, 2009).”
Frame-Semantic Parsing (2014, background): “Smith and Eisner (2008) and Martins et al. (2010) used such a representation to impose constraints in a dependency parsing problem; the latter discussed the equivalence of linear programs and factor graphs for representing discrete optimization problems.”
AD3: alternating directions dual decomposition for MAP inference in graphical models (2015, background): “, 2007), computer vision (Nowozin and Lampert, 2009), and natural language processing (Smith and Eisner, 2008).”
A Joint Model for Entity Analysis: Coreference, Typing, and Linking (2014, methodology): “, 2013) as well as for other NLP tasks (Smith and Eisner, 2008; Burkett and Klein, 2012).”
Approximation-Aware Dependency Parsing by Belief Propagation (2015, methodology): “This would suffice to train the structured BP systems that have been built for projective dependency parsing (Smith and Eisner, 2008), CNF grammar parsing (Naradowsky et al.”