Type-Based MCMC

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 573–581, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Type-Based MCMC Percy Liang UC Berkeley pliang@cs.berkeley.edu Michael I. Jordan UC Berkeley jordan@cs.berkeley.edu Dan Klein UC Berkeley klein@cs.berkeley.edu Abstract Most existing algorithms for learning latent- variable models—such as EM and existing Gibbs samplers—are token-based, meaning that they update the variables associated with one sentence at a time. The incremental na- ture of these methods makes them suscepti- ble to local optima/slow mixing. In this paper, we introduce a type-based sampler, which up- dates a block of variables, identified by a type, which spans multiple sentences. We show im- provements on part-of-speech induction, word segmentation, and learning tree-substitution grammars. 1 Introduction A long-standing challenge in NLP is the unsu- pervised induction of linguistic structures, for ex- ample, grammars from raw sentences or lexicons from phoneme sequences. A fundamental property of these unsupervised learning problems is multi- modality. In grammar induction, for example, we could analyze subject-verb-object sequences as ei- ther ((subject verb) object) (mode 1) or (subject (verb object)) (mode 2). Multimodality causes problems for token-based procedures that update variables for one example at a time. In EM, for example, if the parameters al- ready assign high probability to the ((subject verb) object) analysis, re-analyzing the sentences in E-step only reinforces the analysis, resulting in EM getting stuck in a local optimum. In (collapsed) Gibbs sam- pling, if all sentences are already analyzed as ((sub- ject verb) object), sampling a sentence conditioned 2 1 2 2 1 2 2 2 1 2 1 2 1 2 2 2 1 2 2 1 2 2 2 1 2 1 2 1 2 2 2 1 2 2 1 2 2 2 1 2 1 2 1 2 2 (a) token-based (b) sentence-based (c) type-based Figure 1: Consider a dataset of 3 sentences, each of length 5. Each variable is labeled with a type (1 or 2). The unshaded variables are the ones that are updated jointly by a sampler. The token-based sampler updates the vari- able for one token at a time (a). The sentence-based sam- pler updates all variables in a sentence, thus dealing with intra-sentential dependencies (b). The type-based sam- pler updates all variables of a particular type (1 in this ex- ample), thus dealing with dependencies due to common parameters (c). on all others will most likely not change its analysis, resulting in slow mixing. To combat the problems associated with token- based algorithms, we propose a new sampling algo- rithm that operates on types. Our sampler would, for example, be able to change all occurrences of ((sub- ject verb) object) to (subject (verb object)) in one step. These type-based operations are reminiscent of the type-based grammar operations of early chunk- merge systems (Wolff, 1988; Stolcke and Omohun- dro, 1994), but we work within a sampling frame- work for increased robustness. In NLP, perhaps the the most simple and popu- lar sampler …

Content truncated to 500 words