Stress Rules from Surface Forms: Experiments with Program Synthesis (2021)

Abstract: Learning linguistic generalizations from only a few examples is a challenging task. Recent work has shown that program synthesis – a method to learn rules from data in the form of programs in a domain-specific language – can be used to learn phonological rules in highly data-constrained settings. In this paper, we use the problem of phonological stress placement as a case to study how the design of the domain-specific language influences the generalization ability when using the same learning algorithm. We find that encoding the distinction between consonants and vowels results in much better performance, and providing syllable-level information further improves generalization. Program synthesis, thus, provides a way to investigate how access to explicit linguistic information influences what can be learnt from a small number of examples.

## introduction deep neural models have driven recent success in nlp, including models for tasks in phonology and morphology. they have been applied to tasks such as grapheme-to-phoneme conversion @xcite and morphological reinflection @xcite , and also been incorporated into theories of phonology @xcite . while neural models are powerful learning machines, they require a large number of training examples, either for supervised or for transfer learning. additionally, these models are not easily interpretable, and understanding what stuctures and patterns these models learn from data is a non-trivial task. in this paper, we explore an different approach to learning linguistic patterns from data -program synthesis. program synthesis @xcite is a method to learn interpretable rules in the form * work done while at the microsoft research india ## program synthesis program synthesis is the task of finding a program in a domain-specific language (dsl) that satisfies certain constraints @xcite . this approach allows us to encode domain-specific assumptions about a task, and use generic searchbased @xcite or constraintbased @xcite approaches to synthesize programs. we apply program synthesis to learn rules for stress placement. the programs that are synthesized operate directly on the surface form of a word, which is provided as a string. by varying the structure of the dsl, we control the kind of phonological abstractions that are available to the synthesizer, and observe the effects of this on learning and generalization. ## dataset we obtain data by consulting grammars and other linguistic and phonological analyses of languages listed in the stresstyp2 database @xcite or by @xcite . the database contains information about various lects and the kinds of stress patterns exhibited by these lects. the database also has links to the sources from which the data was collected for compiling the database, and these were the sources we consulted learnprogram learnbranch input examples @xmath0. isphoneme ( 'a ' ,0) #2. iskthphoneme ( 'a ' ,0 , -1) #3. and ( isphoneme ( 'b ' ,1) iskthphoneme ( 'a ' ,0 , -1)) learnconj #4. isphoneme ( 'b ' ,0) #5. isphoneme ( 'a ' ,1) #6. not ( iskthphoneme ( 'a ' ,0 , -1)) a. iskthphoneme('a', 0, -1), replaceby('1') b. not(iskthphoneme('a', 0, -1)), replaceby('0') figure 3: illustration of the synthesis algorithm on a hypothetical case where the stress is on the last vowel, using the basic dsl. the input examples are first used to generate phoneme-level examples. the learnprogram procedure then learns a decision list for the phoneme-level examples through calls to learnbranch. the learnbranch procedure iterates through different candidate transformations (such as replaceby('0') and replaceby('1')). for each transformation, the learnconj procedure produces candidate conjunctions for when the transformation applies and when it does not. the candidate which is true for the most number of cases where the transformation applies, and none of the cases where it does not, is chosen. here, this is #1 for the replaceby('1') action and #6 for the replaceby('0') action. the predicate-action pair which solves the most examples (here b) is then added to the decision list, and the learnbranch procedure is called again on the unsolved examples. all the words collected from these sources have the stress marking attested in the source -there are no cases of a given rule being used to predict the stress pattern on words. once words and the corresponding stress patterns are collected for a language, the set of words is split into two parts -one to be used for synthesizing programs (the training split) and the other (the test split) to be used for evaluating the synthesized rules. we ensure that all test examples are marked with a stress rule that is attested in the training examples. we also use data from the stress problems presented in @xcite . these problems are chosen from the linguistics olympiads, a set of contests in linguistics for high school students. they present a task that is of a similar form to the tasks we study in this paper. these problems present words from a language with stress marked, and require a solver to use this data to infer the stress rules for that language, just as we do for the program synthesis system in this work. for these problems, we preserve the train-test splits from @xcite . in total, we have data from 34 languages -28 from the data we collect, and 6 from linguistics olympiad problems. each language has between 5 and 33 training examples, with an average of 11.3, and between 2 and 16 test examples, with an average of 4.8. ## experiments as described in section 3, each language has a number of pairs -of word and stress pattern -in the training split. these are provided to the synthesis system, which produces a program. given that the system checks shorter programs before longer ones, programs that are found after a long search are likely to be overfit to the given examples, and unlikely to generalize to unseen cases. this is why we terminate the synthesis if a program isn't found within 60 minutes. we also observe that for most of the languages, synthesis terminates well before this limit. for each language, we experiment with each of the 4 dsls described in section 2.2. we also experiment with two neural sequenceto-sequence baselines, based on the lstm and the transformer architecture respectively. we use the implementation made available by @xcite , and train models with the same hyperparameters as in @xcite . to evaluate the synthesized programs, we consider the output of the program on words in the test split. we only consider cases where the predicted stress pattern exactly matches the ground truth stress pattern as correct, and compute the fraction of samples for which the predictions are correct -the accuracy of the program on the test set. we report the average accuracy for the set of languages we consider. we also report the average accuracy separately for data from each source -data which we collect and that chosen from linguistics olympiads -to observe any differences based on the source of data. additionally, we report the number of languages for which a synthesizer acheives a test accuracy of 100% or over 50%. this allows us to count the number of languages for which the synthesizers infer all, or a substantial fraction of, the rules of stress placement. ## analysis we examine the synthesized programs for specific languages to understand the reasons for different levels of performance when using different dsls, and illustrate patterns in failures due to properties of the dsl. ## conclusion in this paper, we explore the problem of learning rules for the placement of phonological stress from only a few examples using program synthesis. we pose the problem as one of learning rules in the form of programs for string-to-string transformations. by designing the domain-specific language in which the rules are synthesized, we can control the amount of linguistic information available to the synthesizer. we use the allowance to explicity provide the learning algorithm access to linguistic information to investigate how different linguistic concepts influence the rules that are learnt from data. to do this, we develop a generic program synthesis algorithm, and different domain-specific languages in which programs are synthesized. each algorithm provides access to a different set of phonological classes, which can be used to identify phonemes that share common features. we find that given a small number of examples, a synthesizer that doesn't have access to linguistic information beyond phoneme identity is unable to learn any useful rules. however, distinguishing consonants and vowels proves extremely useful, and distinguishing different types of syllables proves even more so. thus, using synthesis of rules for stress as a case study, we show how program synthesis can be used as a way to compare how different primitive concepts can be combined to learn rules for the same data using the same learning algorithm. such methods can therefore be used to analyze what concepts are necessary to learn various rules from a limited number of samples, without changing the way in which these concepts are combined. since program synthesis results in human-readable programs, we can also understand how primitive concepts are combined based on the data.