Benchmarking Compositionality with Formal Languages (2022)

Abstract: Recombining known primitive concepts into larger novel combinations is a quintessentially human cognitive capability. Whether large neural models in NLP acquire this ability while learning from data is an open question. In this paper, we look at this problem from the perspective of formal languages. We use deterministic finite-state transducers to make an unbounded number of datasets with controllable properties governing compositionality. By randomly sampling over many transducers, we explore which of their properties (number of states, alphabet size, number of transitions etc.) contribute to learnability of a compositional relation by a neural network. In general, we find that the models either learn the relations completely or not at all. The key is transition coverage, setting a soft learnability limit at 400 examples per transition.

## introduction compositionality is a hallmark of human language @xcite @xcite . it is arguably a requirement for any model to count as a model of language, or to achieve human-like natural language understanding. compositionality seems to be such a deep property of language that speakers draw conclusions about the overall meaning of sentences even when the meanings of individual words are not known. for instance, english speakers reading the jabberwocky @xcite comprehend that the noun phrase slithy toves is built from the composition of the adjective slithy with the plural noun toves, despite lacking a clear understanding of what slithy or toves-let alone their composition-could mean. in cognitive science, whether neural networks can learn to combine a limited number of primitives (in the case of language, word or morphemes) to describe a complex environment has been debated for over 30 years @xcite . in recent work, researchers have explored the inherent limitations of neural models to exhibit compositionality by analyzing sequence-tosequence model performance on small, controlled datasets @xcite @xcite @xcite . however, the conclusions of these studies are often murky. for instance, lake and baroni (2018) cast doubt on neural models' ability to do compositional generalization using their toy scan dataset, but shortly thereafter, @xcite demonstrated that an out-of-the-box sequence-tosequence model could indeed fully master the task. instead of hand-crafting small challenge datasets, we propose to test for compositionality by randomly sampling from a whole class of stringto-string functions. in doing so, we draw on two linguistic traditions. on the one hand, we follow montague's assertion that no important theoretical difference exists between natural and artificial languages @xcite . following this logic, the question of whether neural networks compositionally process human language is fundamentally equivalent to asking whether they compositionally process artificial languages. on the other hand, we draw lessons from the field of grammatical inference (de la higuera, 2010; @xcite , and evaluate neural sequence-to-sequence models on many automatically generated artificial languages sampled from particular classes of functions-as is standard practice at grammatical inference competitions @xcite . in this paper, we study the class of string functions encoded by subsequential finite-state transducers (sfsts), a restricted class of general finite-state transducers @xcite . we sample arbitrary sfsts to generate many different string-to-string datasets and evaluate the behavior of neural sequence-to-sequence models when learning them. by controlling the formal properties of the sfsts we sample from, we are able to make precise statements about the learnability of systematic phenomena. empirically, we find that neural sequence-tosequence models are, in many cases, capable of perfectly learning sfsts from finite data. moreover, we observe an interesting tendency for neural models to either generalize correctly or to fail outrightwith little middle ground. our analysis reveals a possible explanation for this-generalization seems to be possible when the training data has sufficient coverage, i.e., when every transition in a given transducer is crossed in a minimum number of training examples (≈ 400 in our experiments). we then turn to analyze a popular hand-crafted dataset, scan, through the lens of an sfst that encodes it. we find that scan is peculiar in that it seems to serve as a counterexample to our transition coverage finding. this suggests that there is a more nuanced story to tell: we predict the learnability of a language based on a notion of complexity native to subregular languages, but it may be that a more consistently predictive complexity metric would come from a higher point on the chomsky hierarchy. future work might seek to limit the number of outlier languages like scan in order to identify a notion of complexity that is native to the architecture of the model itself. such a notion of complexity would identify the level of abstraction that best reflects the representations learned by the model. a fruitful avenue towards this goal might lie in exploring more complex formalisms. ## finite-state transducers this section provides a short technical overview of finite-state transducers and motivates our choice to learn this class of relations. ## compositionality formalized it is widely held that compositionality is a cornerstone of human language. however, language researchers use the term compositionality to refer to a variety of different concepts @xcite . here, we discuss the specific definition we employ throughout the paper and give a theoretical justification for the use of finite-state transducers as an instantiation of that definition. ## experimental methods next we introduce the methodology for generating our datasets as well as the neural and symbolic models employed in the empirical portion of our paper. ## results and discussion we train a neural network, as described in §4.3, on the datasets taken from our sampled sfsts. we discuss and analyze the results below. ## what about scan? we now turn to the scan dataset and examine it in light of our findings above. first, we encode scan as an sfst. in so doing, we find it to be an outlier in terms of the number of states it requires, which far exceeds the 100 states of our largest sfst. in fact, we calculate that the full sfst encoding scan has 7, 728 states; see a small example in fig. 4 . with a finite dataset size of 20, 000 input-output pairs, it should not be possible to learn scan with high accuracy. however, unlike other datasets of a similar size, scan turns out to be nearly perfectly learnable in our (random-split) experiments. this result stands in contrast to our randomly generated sfsts, which exhibit a consistent relationship between the complexity of a formal language and its learnability. we offer a possible theoretical behavior for scan's surprising learnability. the class of subregular relations has a native complexity metric built into the formalism: the size of the sfst itself, as measured by the number of transitions. however, the results on the scan dataset indicate that the number of transitions in an sfst is not the native complexity metric of neural networks under consideration. this should not come as a surprise because neural networks can learn context-free transductions, which are not even representable by an sfst. while it is interesting that we empirically identify a scaling law that consistently applies to our randomly sampled sfsts, it is not the whole story. indeed, scan is not a randomly sampled dataset from the class of sfsts: it is generated by a handcrafted synchronous context-free grammar (lake and baroni, 2018, figure 6 ). while scan is a complex sfst, requiring thousands of transitions, it can be encoded by a very small synchronous contextfree grammar. casting scan as an sfst therefore misrepresents its native complexity. thus, it is left for future work to identify a class of automata whose native complexity metric can consistently predict the learnability of arbitrary language tasks; such a class will surely be higher than sfsts on the chomsky hierarchy given our reported results. ## related work our paper builds on two common strains of research: the construction of datasets to benchmark compositional behavior in neural networks and research in grammatical inference. ## conclusion we study whether neural sequence-to-sequence models are capable of learning string-to-string transductions with montague-style compositionality, i.e., where compositional behavior is defined to be homomorphic. to execute our study, we first provide a theoretical justification of why sfsts meet montague's definition. in the empirical portion of the paper, we randomly sample 2800 sfsts using the process described in §4.1, and, then, sample input-output pairs from each sfst to create our unique string-to-string transduction datasets. we find that neural networks tend to either generalize completely or fail miserablywith little middle ground. moreover, we identify a simple complexity metric, transition coverage, that seems to reliably allow us to predict when an sfst in our randomly sampled dataset is learnable from the dataset sampled from it. finally, our paper discusses how analyzing scan as an sfst provides a counterexample to our contention that transtion coverages reliably predicts the learnability of an sfst from a given dataset. it seems that while transition coverage is a good metric for subregular languages, there are datasets generated by synchronous context-free grammars that are learnable despite requiring a large number of transitions when encoded as an sfst. for example, scan's learnability is likely due to the fact that the synchronous context-free grammar used to generate it is relatively small and, thus, under a metric such as production coverage it would be considered simple. in conclusion, to get a more complete view of the factors underlying learnability, it may be fruitful to consider not only sfsts, but other formalisms that describe more complex formal relations. we hypothesize that there might yet be a class of automata whose native complexity will more consistently predict the learnability of a language task.