A Particle Filter algorithm for Bayesian Wordsegmentation

A Particle Filter algorithm for Bayesian Wordsegmentation Benjamin B¨orschinger Department of Computing Macquarie University Sydney benjamin.borschinger@mq.edu.au Mark Johnson Department of Computing Macquarie University Sydney mark.johnson@mq.edu.au Abstract Bayesian models are usually learned using batch algorithms that have to iterate multiple times over the full dataset. This is both com- putationally expensive and, from a cognitive point of view, highly implausible. We present a novel online algorithm for the word segmen- tation models of Goldwater et al. (2009) which is, to our knowledge, the first published ver- sion of a Particle Filter for this kind of model. Also, in contrast to other proposed algorithms, it comes with a theoretical guarantee of opti- mality if the number of particles goes to infin- ity. While this is, of course, a theoretical point, a first experimental evaluation of our algo- rithm shows that, as predicted, its performance improves with the use of more particles, and that it performs competitively with other on- line learners proposed in Pearl et al. (2011).1 1 Introduction Bayesian models have recently become quite pop- ular in Computational Linguistics. One undesir- able property of many such models is, however, that the inference algorithms usually applied to them, in particular popular Markov Chain Monte Carlo Methods such as Gibbs Sampling, require multi- ple iterations over the data — this is both compu- tationally expensive and, from a cognitive point of view, implausible. Online learning algorithms di- rectly address this problem by requiring only a sin- gle pass over the data, thus providing a first step 1The source code for our implementation is available for download from http://web.science.mq.edu.au/ ˜bborschi/ from ‘ideal learner’ analyses towards more realistic learning scenarios (Pearl et al., 2011). In this paper, we present a Particle Filter algorithm for the word segmentation models of Goldwater et al. (2009), to our knowledge showing for the first time how a Par- ticle Filter can be applied to models of this kind. Notably, Particle Filters are mathematically well- motivated algorithms to produce a finite approxima- tion to the true posterior of a model, the quality of which increases with larger numbers of particles and recovering the true posterior if the number of par- ticles goes to infinity. This sets them qualitatively apart from most previously proposed online learners that usually are based on heuristic ideas. The structure of the rest of the paper is as fol- lows. First, we give a high-level description of the Bayesian word segmentation model our algorithm applies to and make explicit our notion of an online learner. Then, we give a quick overview of previous work and go on to describe the word segmentation model in more detail, introducing the relevant nota- tion and formulae. Finally, we give a description of the algorithm and present experimental results, com- paring the algorithm with other proposed learning algorithms for the model and its performance across different numbers of particles. 2 The Goldwater model for word segmentation The model2 assumes that a segmented text is cre- ated by a random process …

Content truncated to 500 words