tailieunhanh - Báo cáo khoa học: "Blocked Inference in Bayesian Tree Substitution Grammars"

Learning a tree substitution grammar is very challenging due to derivational ambiguity. Our recent approach used a Bayesian non-parametric model to induce good derivations from treebanked input (Cohn et al., 2009), biasing towards small grammars composed of small generalisable productions. In this paper we present a novel training method for the model using a blocked Metropolis-Hastings sampler in place of the previous method’s local Gibbs sampler. | Blocked Inference in Bayesian Tree Substitution Grammars Trevor Cohn Department of Computer Science University of Sheffield Phil Blunsom Computing Laboratory University of Oxford Abstract Learning a tree substitution grammar is very challenging due to derivational ambiguity. Our recent approach used a Bayesian non-parametric model to induce good derivations from treebanked input Cohn et al. 2009 biasing towards small grammars composed of small generalisable productions. In this paper we present a novel training method for the model using a blocked Metropolis-Hastings sampler in place of the previous method s local Gibbs sampler. The blocked sampler makes considerably larger moves than the local sampler and consequently converges in less time. A core component of the algorithm is a grammar transformation which represents an infinite tree substitution grammar in a finite context free grammar. This enables efficient blocked inference for training and also improves the parsing algorithm. Both algorithms are shown to improve parsing accuracy. 1 Introduction Tree Substitution Grammar TSG is a compelling grammar formalism which allows nonterminal rewrites in the form of trees thereby enabling the modelling of complex linguistic phenomena such as argument frames lexical agreement and idiomatic phrases. A fundamental problem with TSGs is that they are difficult to estimate even in the supervised scenario where treebanked data is available. This is because treebanks are typically not annotated with their TSG derivations how to decompose a tree into elementary tree fragments instead the derivation needs to be inferred. In recent work we proposed a TSG model which infers an optimal decomposition under a nonparametric Bayesian prior Cohn et al. 2009 . This used a Gibbs sampler for training which repeatedly samples for every node in every training tree a binary value indicating whether the node is or is not a substitution point