Learning Stochastic OT Grammars: A Bayesian Approach using Data Augmentation and Gibbs Sampling

Proceedings of the 43rd Annual Meeting of the ACL, pages 346–353, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Learning Stochastic OT Grammars: A Bayesian approach using Data Augmentation and Gibbs Sampling Ying Lin∗ Department of Linguistics University of California, Los Angeles Los Angeles, CA 90095 yinglin@ucla.edu Abstract Stochastic Optimality Theory (Boersma, 1997) is a widely-used model in linguis- tics that did not have a theoretically sound learning method previously. In this pa- per, a Markov chain Monte-Carlo method is proposed for learning Stochastic OT Grammars. Following a Bayesian frame- work, the goal is finding the posterior dis- tribution of the grammar given the rela- tive frequencies of input-output pairs. The Data Augmentation algorithm allows one to simulate a joint posterior distribution by iterating two conditional sampling steps. This Gibbs sampler constructs a Markov chain that converges to the joint distribu- tion, and the target posterior can be de- rived as its marginal distribution. 1 Introduction Optimality Theory (Prince and Smolensky, 1993) is a linguistic theory that dominates the field of phonology, and some areas of morphology and syn- tax. The standard version of OT contains the follow- ing assumptions: • A grammar is a set of ordered constraints ({Ci : i = 1, · · · , N}, >); • Each constraint Ci is a function: Σ∗ → {0, 1, · · · }, where Σ∗ is the set of strings in the language; ∗The author thanks Bruce Hayes, Ed Stabler, Yingnian Wu, Colin Wilson, and anonymous reviewers for their comments. • Each underlying form u corresponds to a set of candidates GEN(u). To obtain the unique surface form, the candidate set is successively filtered according to the order of constraints, so that only the most harmonic candidates remain after each filtering. If only 1 candidate is left in the candidate set, it is chosen as the optimal output. The popularity of OT is partly due to learning al- gorithms that induce constraint ranking from data. However, most of such algorithms cannot be ap- plied to noisy learning data. Stochastic Optimality Theory (Boersma, 1997) is a variant of Optimality Theory that tries to quantitatively predict linguis- tic variation. As a popular model among linguists that are more engaged with empirical data than with formalisms, Stochastic OT has been used in a large body of linguistics literature. In Stochastic OT, constraints are regarded as independent normal distributions with unknown means and fixed variance. As a result, the stochastic constraint hierarchy generates systematic linguistic variation. For example, consider a grammar with 3 constraints, C1 ∼ N(µ1, σ2), C2 ∼ N(µ2, σ2), C3 ∼ N(µ3, σ2), and 2 competing candidates for a given input x: p(.) C1 C2 C3 x ∼ y1 .77 0 0 1 x ∼ y2 .23 1 1 0 Table 1: A Stochastic OT grammar with 1 input and 2 outputs 346 The probabilities p(.) are obtained by repeatedly sampling the 3 normal distributions, generating the winning candidate according to the ordering of con- straints, and counting …

Content truncated to 500 words