Estimating Strictly Piecewise Distributions

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 886–896, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Estimating Strictly Piecewise Distributions Jeffrey Heinz University of Delaware Newark, Delaware, USA heinz@udel.edu James Rogers Earlham College Richmond, Indiana, USA jrogers@quark.cs.earlham.edu Abstract Strictly Piecewise (SP) languages are a subclass of regular languages which en- code certain kinds of long-distance de- pendencies that are found in natural lan- guages. Like the classes in the Chom- sky and Subregular hierarchies, there are many independently converging character- izations of the SP class (Rogers et al., to appear). Here we define SP distributions and show that they can be efficiently esti- mated from positive data. 1 Introduction Long-distance dependencies in natural language are of considerable interest. Although much at- tention has focused on long-distance dependencies which are beyond the expressive power of models with finitely many states (Chomsky, 1956; Joshi, 1985; Shieber, 1985; Kobele, 2006), there are some long-distance dependencies in natural lan- guage which permit finite-state characterizations. For example, although it is well-known that vowel and consonantal harmony applies across any ar- bitrary number of intervening segments (Ringen, 1988; Bakovi´c, 2000; Hansson, 2001; Rose and Walker, 2004) and that phonological patterns are regular (Johnson, 1972; Kaplan and Kay, 1994), it is less well-known that harmony patterns are largely characterizable by the Strictly Piecewise languages, a subregular class of languages with independently-motivated, converging characteri- zations (see Heinz (2007, to appear) and especially Rogers et al. (2009)). As shown by Rogers et al. (to appear), the Strictly Piecewise (SP) languages, which make distinctions on the basis of (potentially) discon- tiguous subsequences, are precisely analogous to the Strictly Local (SL) languages (McNaughton and Papert, 1971; Rogers and Pullum, to appear), which make distinctions on the basis of contigu- ous subsequences. The Strictly Local languages are the formal-language theoretic foundation for n-gram models (Garcia et al., 1990), which are widely used in natural language processing (NLP) in part because such distributions can be estimated from positive data (i.e. a corpus) (Jurafsky and Martin, 2008). N-gram models describe prob- ability distributions over all strings on the basis of the Markov assumption (Markov, 1913): that the probability of the next symbol only depends on the previous contiguous sequence of length n − 1. From the perspective of formal language theory, these distributions are perhaps properly called Strictly k-Local distributions (SLk) where k = n. It is well-known that one limitation of the Markov assumption is its inability to express any kind of long-distance dependency. This paper defines Strictly k-Piecewise (SPk) distributions and shows how they too can be effi- ciently estimated from positive data. In contrast with the Markov assumption, our assumption is that the probability of the next symbol is condi- tioned on the previous set of discontiguous subse- quences of length k − 1 in the string. While this suggests the model has too many parameters (one for each subset of all possible subsequences), in fact the model has on the order of …

Content truncated to 500 words