Type-based MCMC for Sampling Tree Fragments from Forests

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1735–1745, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Type-based MCMC for Sampling Tree Fragments from Forests Xiaochang Peng and Daniel Gildea Department of Computer Science University of Rochester Rochester, NY 14627 Abstract This paper applies type-based Markov Chain Monte Carlo (MCMC) algorithms to the problem of learning Synchronous Context-Free Grammar (SCFG) rules from a forest that represents all possible rules consistent with a fixed word align- ment. While type-based MCMC has been shown to be effective in a number of NLP applications, our setting, where the tree structure of the sentence is itself a hid- den variable, presents a number of chal- lenges to type-based inference. We de- scribe methods for defining variable types and efficiently indexing variables in or- der to overcome these challenges. These methods lead to improvements in both log likelihood and BLEU score in our experi- ments. 1 Introduction In previous work, sampling methods have been used to learn Tree Substitution Grammar (TSG) rules from derivation trees (Post and Gildea, 2009; Cohn et al., 2009) for TSG learning. Here, at each node in the derivation tree, there is a binary vari- able indicating whether the node is internal to a TSG rule or is a split point, which we refer to as a cut, between two rules. The problem of extract- ing machine translation rules from word-aligned bitext is a similar problem in that we wish to au- tomatically learn the best granularity for the rules with which to analyze each sentence. The prob- lem of rule extraction is more complex, however, because the tree structure of the sentence is also unknown. In machine translation applications, most pre- vious work on joint alignment and rule extrac- tion models uses heuristic methods to extract rules from learned word alignment or bracketing struc- tures (Zhang et al., 2008; Blunsom et al., 2009; DeNero et al., 2008; Levenberg et al., 2012). Chung et al. (2014) present a MCMC algorithm schedule to learn Hiero-style SCFG rules (Chiang, 2007) by sampling tree fragments from phrase de- composition forests, which represent all possible rules that are consistent with a set of fixed word alignments. Assuming fixed word alignments re- duces the complexity of the sampling problem, and has generally been effective in most state- of-the-art machine translation systems. The al- gorithm for sampling rules from a forest is as follows: from the root of the phrase decomposi- tion forest, one samples a cut variable, denoting whether the current node is a cut, and an edge vari- able, denoting which incoming hyperedge is cho- sen, at each node of the current tree in a top-down manner. This sampling schedule is efficient in that it only samples the current tree and will not waste time on updating variables that are unlikely to be used in any tree. As with many other token-based Gibbs Sam- pling applications, sampling one node at a time can result in slow mixing …

Content truncated to 500 words