Inducing Synchronous Grammars with Slice Sampling

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 238–241, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Inducing Synchronous Grammars with Slice Sampling Phil Blunsom Computing Laboratory Oxford University Phil.Blunsom@comlab.ox.ac.uk Trevor Cohn Department of Computer Science University of Sheffield T.Cohn@dcs.shef.ac.uk Abstract This paper describes an efficient sampler for synchronous grammar induction under a non- parametric Bayesian prior. Inspired by ideas from slice sampling, our sampler is able to draw samples from the posterior distributions of models for which the standard dynamic pro- graming based sampler proves intractable on non-trivial corpora. We compare our sampler to a previously proposed Gibbs sampler and demonstrate strong improvements in terms of both training log-likelihood and performance on an end-to-end translation evaluation. 1 Introduction Intractable optimisation algorithms abound in much of the recent work in Natural Language Process- ing. In fact, there is an increasing acceptance that solutions to many of the great challenges of NLP (e.g. machine translation, summarisation, question answering) will rest on the quality of approximate inference. In this work we tackle this problem in the context of inducing synchronous grammars for a machine translation system. We concern ourselves with the lack of a principled, and scalable, algo- rithm for learning a synchronous context free gram- mar (SCFG) from sentence-aligned parallel corpora. The predominant approach for learning phrase- based translation models (both finite state or syn- chronous grammar based) uses a cascade of heuris- tics beginning with predicted word alignments and producing a weighted set of translation rules (Koehn et al., 2003). Alternative approaches avoid such heuristics, instead learning structured align- ment models directly from sentence aligned data (e.g., (Marcu and Wong, 2002; Cherry and Lin, 2007; DeNero et al., 2008; Blunsom et al., 2009)). Although these models are theoretically attractive, inference is intractable (at least O(|f|3|e|3)). The efficacy of direct estimation of structured alignment models therefore rests on the approximations used to make inference practicable – typically heuristic constraints or Gibbs sampling. In this work we show that naive Gibbs sampling (specifically, Blunsom et al. (2009)) is ineffectual for inference and reliant on a high quality initialisation, mixing very slowly and being easily caught in modes. Instead, blocked sam- pling over sentence pairs allows much faster mixing, but done in the obvious way (following Johnson et al. (2007)) would incur a O(|f|3|e|3) time complexity. Here we draw inspiration from the work of Van Gael et al. (2008) on inference in infinite hid- den Markov models to develop a novel algorithm for efficient sampling from a SCFG. We develop an auxiliary variable ‘slice’ sampler which can dramati- cally reduce inference complexity, and thereby make blocked sampling practicable on real translation cor- pora. Our evaluation demonstrates that our algorithm mixes more quickly than the local Gibbs sampler, and produces translation models which achieve state-of- the-art BLEU scores without using GIZA++ or sym- metrisation heuristics for initialisation. We adopt the generative model of Blunsom et al. (2009) which creates a parallel sentence pair by …

Content truncated to 500 words