Simple induction of (deterministic) probabilistic finite-state automata for phonotactics by stochastic gradient descent (2021)

Abstract: We introduce a simple and highly general phonotactic learner which induces a probabilistic finite-state automaton from word-form data. We describe the learner and show how to parameterize it to induce unrestricted regular languages, as well as how to restrict it to certain subregular classes such as Strictly k-Local and Strictly k-Piecewise languages. We evaluate the learner on its ability to learn phonotactic constraints in toy examples and in datasets of Quechua and Navajo. We find that an unrestricted learner is the most accurate overall when modeling attested forms not seen in training; however, only the learner restricted to the Strictly Piecewise language class successfully captures certain nonlocal phonotactic constraints. Our learner serves as a baseline for more sophisticated methods.

## introduction natural language phonotactics is argued to fall in the class of regular languages, or even in a smaller class of subregular languages @xcite . this observation has motivated the study of probabilistic finite-state automata (pfas) that generate these languages as models of phonotactics. here we implement a simple method for the induction of pfas for phonotactics from data, which can induce general regular languages in addition to languages in certain more restricted subclasses, for example, strictly k-local and strictly k-piecewise languages @xcite . we evaluate our learner on corpus data from quechua and navajo, with a particular emphasis on the ability to learn nonlocal constraints. we make both theoretical and empirical contributions. theoretically, we present the differentiable linear-algebraic formulation of pfas which enables learning of the structure of the automaton by gradient descent. in our framework, it is possible to induce an unrestricted automaton with a given number of states, or an automaton with hard-coded constraints representing various subregular languages. this work fills a gap in the formal linguistics literature, where learners have been developed within certain subregular classes @xcite @xcite , whereas our learner can in principle induce any (sub)regular language. in addition, we demonstrate how strictly local and strictly piecewise constraints can be encoded within our framework, and show how informationtheoretic regularization can be applied to produce deterministic automata. empirically, our main result is to show that our approach gives reasonable and linguistically accurate results. we find that inducing an unrestricted pfa produces the best fit to held-out attested forms, while inducing an automaton for a strictly 2-piecewise language yields a model that successfully captures nonlocal constraints. we also analyze the nondeterminism of induced automata, and the extent to which induced automata overfit to their training data. ## inducing toy languages first, we test the ability of the model to recover automata for simple examples of subregular languages. we do so for the two subregular classes 2-sl and 2-sp described in section 2.5. for each of these language classes, we implement a reference pfa which generates strings from a simple example language in that class, then generate 10, 000 sample sequences from the reference pfa. we then use these samples as training data, and study whether our learners can recover the relevant constraints from the data. ## corpus experiments we evaluate our learner by training it on dictionary forms from quechua and navajo and then studying its ability to predict attested forms that were held out in training in addition to artificially constructed nonce forms which probe the ability of the model to represent nonlocal constraints. ## conclusion we introduced a framework for phonotactic learning based on simple induction of probabilistic finitestate automata by stochastic gradient descent. we showed how this framework can be used to learn unrestricted pfas, in addition to pfas restricted to certain formal language classes such as strictly local and strictly piecewise, via constraints on the transition matrices that define the automata. furthermore, we showed that the framework is successful in learning some phonotactic phenomena, with unrestricted automata performing best in a wide-coverage evaluation on attested but held-out forms, and strictly piecewise automata performing best in a targeted evaluation using nonce forms focusing on nonlocal constraints. our results leave open the question of whether the unrestricted learner or one of the restricted learners is 'best' for learning phonotactics, since they perform differently on different metrics. a key question for future work is whether there might be some model that could do well in inducing both local and nonlocal constraints simultaneously, and performing well on both the held-out evaluation and the nonce form evaluation. such a model could come in the form of another restricted language class such as tier-based strictly local languages @xcite @xcite , or perhaps in the form of a regularization term in the training objective which enforces an inductive bias that favors certain nonlocal interactions. the code for this project is available at http://github.com/hutengdai/ pfa-learner .