Relaxed Marginal Inference and its Application to Dependency Parsing

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 760–768, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Relaxed Marginal Inference and its Application to Dependency Parsing Sebastian Riedel David A. Smith Department of Computer Science University of Massachusetts, Amherst {riedel,dasmith}@cs.umass.edu Abstract Recently, relaxation approaches have been successfully used for MAP inference on NLP problems. In this work we show how to extend the relaxation approach to marginal inference used in conditional likelihood training, pos- terior decoding, confidence estimation, and other tasks. We evaluate our approach for the case of second-order dependency parsing and observe a tenfold increase in parsing speed, with no loss in accuracy, by performing in- ference over a small subset of the full factor graph. We also contribute a bound on the error of the marginal probabilities by a sub-graph with respect to the full graph. Finally, while only evaluated with BP in this paper, our ap- proach is general enough to be applied with any marginal inference method in the inner loop. 1 Introduction In statistical natural language processing (NLP) we are often concerned with finding the marginal proba- bilities of events in our models or the expectations of features. When training to optimize conditional like- lihood, feature expectations are needed to calculate the gradient. Marginalization also allows a statis- tical NLP component to give confidence values for its predictions or to marginalize out latent variables. Finally, given the marginal probabilities of variables, we can pick the values that maximize these marginal probabilities (perhaps subject to hard constraints) in order to predict a good variable assignment.1 1With a loss function that decomposes on the variables, this amounts to Minimum Bayes Risk (MBR) decoding, which is Traditionally, marginal inference in NLP has been performed via dynamic programming (DP); how- ever, because this requires the model to factor in a way that lends itself to DP algorithms, we have to restrict the class of probabilistic models we con- sider. For example, since we cannot derive a dy- namic program for marginal inference in second or- der non-projective dependency parsing (McDonald and Satta, 2007), we have non-projective languages such as Dutch using second order projective mod- els if we want to apply DP. Some previous work has circumvented this problem for MAP inference by starting with a second-order projective solution and then greedily flipping edges to find a better non- projective solution (McDonald and Pereira, 2006). In order to explore richer model structures, the NLP community has recently started to investigate the use of other, well-known machine learning tech- niques for marginal inference. One such technique is Markov chain Monte Carlo, and in particular Gibbs sampling (Finkel et al., 2005), another is (loopy) sum-product belief propagation (Smith and Eisner, 2008). In both cases we usually work in the frame- work of graphical models—in our case, with factor graphs that describe our distributions through vari- ables, factors, and factor potentials. In theory, meth- ods such as belief propagation can take …

Content truncated to 500 words