Learning Tier-based Strictly 2-Local Languages

Learning Tier-based Strictly 2-Local Languages Adam Jardine and Jeffrey Heinz University of Delaware {ajardine,heinz}@udel.edu Abstract The Tier-based Strictly 2-Local (TSL2) lan- guages are a class of formal languages which have been shown to model long-distance phonotactic generalizations in natural lan- guage (Heinz et al., 2011). This paper in- troduces the Tier-based Strictly 2-Local In- ference Algorithm (2TSLIA), the first non- enumerative learner for the TSL2 languages. We prove the 2TSLIA is guaranteed to con- verge in polynomial time on a data sample whose size is bounded by a constant. 1 Introduction This work presents the Tier-based Strictly 2-Local Inference Algorithm (2TSLIA), an efficient learn- ing algorithm for a class of Tier-based Strictly Lo- cal (TSL) formal languages (Heinz et al., 2011). A TSL class is determined by two parameters: the tier, or subset of the alphabet, and the permissible tier k-factors, which are the legal sequences of length k allowed in the string, once all non-tier symbols have been removed. The Tier-based Strictly 2-Local (TSL2) languages are those in which k = 2. As will be discussed below, the TSL languages are of interest to phonology because they can model a wide variety of long-distance phonotactic patterns found in natural language (Heinz et al., 2011; Mc- Mullin and Hansson, forthcoming). One example is derived from Latin liquid dissimilation, in which two ls cannot appear in a word unless there is an r intervening, regardless of distance. For exam- ple, floralis ‘floral’ is well-formed but not *mili- talis (cf. militaris ‘military’). As explained in sec- tions 2 and 4, this can be modeled with permissible 2-factors over a tier consisting of the liquids {l, r}. For long-distance phonotactics, k can be fixed to 2, but it is does not appear that the tier can be fixed since languages employ a variety of different tiers. This presents an interesting learning problem: Given a fixed k, how can an algorithm induce both a tier and a set of permissible tier k-factors from positive data? There is some related work which addresses this question. Goldsmith and Riggle (2012), building on work by Goldsmith and Xanthos (2009), present a method based on mutual information for learn- ing tiers and subsequently learning harmony pat- terns. This paper differs in that its methods are rooted firmly in grammatical inference and formal language theory (de la Higuera, 2010). For instance, in contrast to the results presented there, we prove the kinds of patterns 2TSLIA succeeds on and the kind of data sufficient for it to do so. Nonetheless, there is relevant work in computa- tional learning theory: Gold (1967) proved that any finite class of languages is identifiable in the limit via an enumeration method. Given a fixed alphabet and a fixed k, the number of possible tiers and per- missible tier k-factors is finite, and thus learnable in this way. However, such learners are grossly inef- ficient. No provably-correct, non-enumerative, ef- ficient learner for both the tier and permissible tier k-factor parameters has previously been proposed. This …

Content truncated to 500 words