Evaluating Transformer’s Ability to Learn Mildly Context-Sensitive Languages (2023)

Abstract: Despite the fact that Transformers perform well in NLP tasks, recent studies suggest that self-attention is theoretically limited in learning even some regular and context-free languages. These findings motivated us to think about their implications in modeling natural language, which is hypothesized to be mildly context-sensitive. We test the Transformer’s ability to learn mildly context-sensitive languages of varying complexities, and find that they generalize well to unseen in-distribution data, but their ability to extrapolate to longer strings is worse than that of LSTMs. Our analyses show that the learned self-attention patterns and representations modeled dependency relations and demonstrated counting behavior, which may have helped the models solve the languages.

## introduction transformers @xcite have demonstrated well-versed language processing capabilities and enabled a wide range of exciting nlp applications ever since its inception. however, @xcite shows that hard self-attention transformers, as well as soft attention under some assumptions, fail at modeling regular languages with periodicity as well as hieararchical context-free languages eventually when presented with long enough sequences. these theoretical limitations have since sparked the interest of the formal language community. a variety of formal languages, as well as formal models of computation such as circuits, counter automata, and predicate logic, have been studied to characterize the expressiveness of the architecture. when it comes to probing an architecture's linguistic adequacy, a particular class of formal languages and formalisms naturally comes into sight: the mildly context-sensitive class @xcite ; recursively enumerable figure 1 : how certain mcsgs fit on the chomsky hierarchy of languages in terms of their weak generative capacities @xcite : cfl ⊂ l(tag) = l(ccg) ⊂ l(mg) = l(lcfrs) = l(mcfg) ⊂ csl. no formalism generates the largest set of mcsls. @xcite , the formal complexity class hypothesized to have the necessary expressive power for natural language. this motivates us to study the transformer's ability to learn a variety of linguistically significant, mildly context-sensitive string languages of varying degrees of complexities. specifically, we ask two research questions: figure 2 : swiss german subordinate clauses allow n accusative nps before m dative nps, followed by n corresponding accusative object taking verbs before m corresponding dative object taking verbs. @xcite defined a homomorphism for swiss german such that when intersecting with regular wa * b * xc * d * yz yields non-context-free wa n b m xc n d m yz, which contradicts cfl's closure property under intersection with regular languages. the representations encoded count information for some complex languages, which may have been useful for solving languages in this class. ## mildly context-sensitive hypothesis in search of computational models that have adequate power to generate natural language sentences while also assigning meaningful structural descriptions like trees to them, @xcite defined context-sensitive grammars (csg) and context-free grammars (cfg) as intermediate systems that lie between two extremities: the turing machine which overgenerates and the finitestate automaton which undergenerates. a question that immediately follows the definitions is whether the cfg could serve as a computational model for natural language, which had been an open question for a few decades until it was settled by evidence such as swiss german cross-serial dependency (figure 2 ; @xcite and bambara vocabulary @xcite , which demonstrated the existence of natural languages that are supra-context-free. however, although more restricted than the turing machine, the csg is also undesired as it still has much more generative capacity than natural languages should ever need, and as a result of that, is hard to parse efficiently. this motivated tree-adjoining grammars @xcite and @xcite among a few other weakly equivalent formalisms such that extend the cfg with just enough additional descriptive power so that phenomena like swiss german cross-serial dependency can be treated, while not using the full csg thus parsing can still be efficient. the properties of these formalisms with such additional power roughly characterize a class of languages and grammars that @xcite calls mildly context-sensitive languages/grammars (mcsl/mcsg). another related line of weakly equivalent for-malisms, such as linear context-free rewriting systems (lcfrs; @xcite , multiple context-free grammars (mcfg; @xcite , and minimalist grammars (mg; stabler, 1997), further extend their expressive power beyond that of the tag, as motivated by more complex phenomena like german scrambling @xcite . while no single grammar formalism generates the largest possible set of mcsls that satisfy the formal characterization in @xcite , these are the closest approximations we have. such differences in expressiveness formed a subhierarchy within this class (figure 1 ), and the languages recognizable by tags and mgs and their respective equivalents, denoted as l(tag) and l(mg), are therefore the language complexity classes that we examine in this work. therefore, one hypothesis for the complexity of natural language is that it is mildly contextsensitive (henthforth mcs). there have been some challenges citing linguistic data requiring more power beyond mcs @xcite @xcite , but the validity of these claims remains controversial @xcite , or no consensus has been reached on the need for more power @xcite . thus, while acknowledging that whether the mcs hypothesis is true remains an open question, it is a reasonably good hypothesis that allows us to analyze natural languages meaningfully. ## related work regarding the expressiveness of the transformer, @xcite established the turingcompleteness of the hard-attention transformer. @xcite proves the turingcompleteness of soft attention by showing that they can simulate rnns. however, these results assumed arbitrary precision for weights and activations, had certain departures from the original archi-tecture, and made the proofs through their unique task definitions. in a practical case of formal language learning from finite examples, the transformer's ability is known to be limited, even in the regular language class. empirically, it was shown that transformers of different self-attention variants have limited abilities to learn certain star-free languages, as well as non-star-free, periodic regular languages @xcite , although the latter may still be recognized theoretically with a simple modification to the architecture @xcite . as for context-free languages with hieararchical structural analyses such as dyck-n, @xcite empirically demonstrated one transformer encoder setup in which such languages may be learned and observed stack-like behavior in selfattention patterns. @xcite proved and empirically showed that self-attention can learn dyckn with a bounded depth, although the boundedness reduces the cfl to regular. additional empirical work on dyck-n include @xcite ; @xcite , among others. besides language recognition guided by the chomsky hierarchy, another line of research investigates other alternative formal languages, such as counter-recognizable languages @xcite and first-order logic @xcite , to characterize the expressiveness of transformers. this work introduces mcsgs into the empirical explorations through assessing the ability of transformers in certain learning settings to learn a variety of string languages recognizable by mcsgs of different complexities, which have not yet been studied as a whole like languages in other classes. occasionally, studies on the transformer's learning ability worked with data that conveniently fall into this class, including a few counter languages that are also tag-recognizable @xcite , discontinuities in dutch @xcite , reduplication @xcite , as well as a crossed parentheses language inspired by crossing dependency foot_0 @xcite . this work complements these and other aforementioned related work by presenting a systematic evaluation guided by basic mcsl constructions and the subhierarchy within the class, as well as comparing each of the basic constructions against a less and a more complex counterparts. ## experiments each model is evaluated on three sets: an indistribution held-out test set, an out-of-distribution (henthforth ood) set with strings longer than the ones seen during training, and a second ood set with even longer strings. we report the mean and standard deviation of test accuracies in three runs with different random seeds. we then visualize the heads from our bestperforming runs that most clearly demonstrate highly interpretable patterns upon visual inspection, but note that all visualized patterns do recur across different configurations. ## discussion and conclusion we empirically studied the transformer's ability to learn a variety of linguistically significant mcsls. the significance of the languages is two-fold: they represent a hypothesized upper bound for the complexity of natural language, and they are the abstractions of the motivating linguistic phenomena. overall, the transformers performed well in indistribution tests and are comparable to lstms, but their ability to extrapolate is limited. in our next character prediction experiments with transformer decoders, removing the sinusoidal pe alleviated the problem, which is an established empirical finding for some formal languages and natural language, but this technique is not always generalizable to other data, nor does it work in the encoder since the decoder can rely on the indirect positional information from the causal mask in absence of pe. transformers leveraged the attention mechanism to score the similarity between the substrings. in our analyses, the learned self-attention's alignments often reflect the symbol dependency relations within the string, which had been useful for mcsls because of the rich and complex dependencies in the languages. in a more complex language like mix, transformers had implicitly learned some form of counting behavior that may have helped solve the language. within the same family of languages spanning across complexity classes, the learned patterns are similar and no significant differences in behaviors are observed in the reduced or added complexity languages. this may suggest that we cannot draw parallels between the mcsg formalisms and the transformer's expressiveness directly, like some other formal models such as circuits @xcite do. however, this work serves as an example of how we may draw inspiration from the rich mcsl scholarships to motivate work in nlp, as they help us examine the linguistic capacity of current and future nlp models.