Approximation-Aware Dependency Parsing by Belief Propagation
By Matthew R. Gormley, Mark Dredze, Jason Eisner. 2015
36 citations recorded by the source corpus.
We show how to train the fast dependency parser of Smith and Eisner (2008) for improved accuracy. This parser can consider higher-order interactions among edges while retaining O(n3) runtime. It outputs the parse with maximum expected recall—but for speed, this expectation is taken under a posterior distribution that is constructed only approximately, using loopy belief propagation through structured factors. We show how to adjust the model parameters to compensate for the errors introduced by this approximation, by following the gradient of the actual loss on training data. We find this gradient by back-propagation. That is, we treat the entire parser (approximations and all) as a differentiable circuit, as others have done for loopy CRFs (Domke, 2010; Stoyanov et al., 2011; Domke, 2011; Stoyanov and Eisner, 2012). The resulting parser obtains higher accuracy with fewer iterations of belief propagation than one trained by conditional log-likelihood.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Graham Neubig
- Noah A. Smith
- Yoav Goldberg
- Mohit Bansal
- Luke S. Zettlemoyer
- Yejin Choi
- Yonatan Belinkov
- Chris Dyer
Citations in the corpus
- Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, background): “• how to use the inside algorithm within a larger neural network that can be differentiated endto-end (Gormley et al., 2015; Gormley, 2015); • how to efficiently obtain the partial derivatives of the expected counts by differentiating the algorithm a second time (Li and Eisner, 2009); • how to navig”
- DyNet: The Dynamic Neural Network Toolkit (2017, methodology): “In some cases, it is desirable to use sophisticated inference algorithms to compute or approximate a differentiable quantity such as the marginal likelihood or Bayes risk during learning [26, 15, 25, 38].”
- Neural, symbolic and neural-symbolic reasoning on knowledge graphs (2021, methodology): “The approximation algorithm belief propagation [49] is adopted to compute the probability.”