Approximation-Aware Dependency Parsing by Belief Propagation

Approximation-Aware Dependency Parsing by Belief Propagation Matthew R. Gormley Mark Dredze Jason Eisner Human Language Technology Center of Excellence Center for Language and Speech Processing Department of Computer Science Johns Hopkins University, Baltimore, MD {mrg,mdredze,jason}@cs.jhu.edu Abstract We show how to train the fast dependency parser of Smith and Eisner (2008) for im- proved 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 pos- terior distribution that is constructed only ap- proximately, 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 re- sulting parser obtains higher accuracy with fewer iterations of belief propagation than one trained by conditional log-likelihood. 1 Introduction Recent improvements to dependency parsing ac- curacy have been driven by higher-order features. Such a feature can look beyond just the parent and child words connected by a single edge to also con- sider siblings, grandparents, etc. By including in- creasingly global information, these features pro- vide more information for the parser—but they also complicate inference. The resulting higher-order parsers depend on approximate inference and decod- ing procedures, which may prevent them from pre- dicting the best parse. For example, consider the dependency parser we will train in this paper, which is based on the work of Smith and Eisner (2008). Ostensibly, this parser finds the minimum Bayes risk (MBR) parse under a probability distribution defined by a higher-order dependency parsing model. In reality, it achieves O(n3tmax) runtime by relying on three approxima- tions during inference: (1) variational inference by loopy belief propagation (BP) on a factor graph, (2) truncating inference after tmax iterations prior to convergence, and (3) a first-order pruning model to limit the number of edges considered in the higher- order model. Such parsers are traditionally trained as if the inference had been exact.1 In contrast, we train the parser such that the ap- proximate system performs well on the final eval- uation function. We treat the entire parsing com- putation as a differentiable circuit, and backprop- agate the evaluation function through our approx- imate inference and decoding methods to improve its parameters by gradient descent. The system also learns to cope with model misspecification, where the model couldn’t perfectly fit the distribution even absent the approximations. For standard graphical models, Stoyanov and Eisner (2012) call this ap- proach ERMA, for “empirical risk minimization un- der approximations.” For objectives besides empiri- cal risk, Domke (2011) refers to it as “learning with truncated message passing.” Our primary contribution is the application of this approximation-aware learning method in the pars- ing setting, …

Content truncated to 500 words