Simpler neural networks prefer subregular languages (2023)

Abstract: We apply a continuous relaxation of L_0 regularization (Louizos et al., 2017), which induces sparsity, to study the inductive biases of LSTMs. In particular, we are interested in the patterns of formal languages which are readily learned and expressed by LSTMs. Across a wide range of tests we find sparse LSTMs prefer subregular languages over regular languages and the strength of this preference increases as we increase the pressure for sparsity. Furthermore LSTMs which are trained on subregular languages have fewer non-zero parameters. We conjecture that this subregular bias in LSTMs is related to the cognitive bias for subregular language observed in human phonology which are both downstream of a simplicity bias in a suitable description language.

## introduction despite the wide application of neural networks for sequence modeling, their inductive biases remain incompletely understood: for example, whether rnns have an inductive bias favoring the kind of hierarchical structures used in sentence formation in natural language @xcite @xcite @xcite . it is important to study the inductive biases of neural networks not only from a scientific perspective, but also a practical one: if neural networks can be developed that have inductive biases toward the same kinds of formal language structures that characterize human language, then these neural networks should be able to learn human language more easily. many patterns in natural language are characterized by a particular subset of the regular languages, called subregular languages. these languages have been hypothesized to form a bound on learnable human phonological patterns @xcite , as well as patterns within tree structures characterizing syntax @xcite . the particular subregular languages theorized to be human learnable are strictly piecewise (sp), strictly local (sl), and multiple tier-based strictly local (mtsl). artificial language learning tasks have shown these languages to be easier to acquire for humans @xcite @xcite . here we take up the question of inductive biases for subregular languages in lstms @xcite , using a relaxation of l 0 regularization to study networks that are constrained to be simple in the sense of network sparsity. we train these networks on several sets of toy languages which contrast subregular languages against regular languages in a controlled manner. this technique not only allows us to study the inductive biases of sparse networks, but also to address an outstanding question in the literature on subregular languages: whether there exists a computational description language under which subregular languages are simpler than other regular languages @xcite . to preview our results, we find that simple lstms favor subregular languages: such languages can be represented by lstms with fewer parameters, and sparse lstms favor subregular languages in generalization. the remainder of the paper is structured as follows: section 2 gives relevant background on subregular languages, section 3 gives our general methods for training sparse neural networks under l 0 regularization, section 4 presents our experiments on matched pairs of regular and subregular languages, and section 5 concludes. ## background it is known that phonological constraints should be regular given the most common formalisms in linguistics @xcite . however, the regular language class is too permissive: many pat- ## general methods a crucial part of our method requires finding optimal tradeoffs between accuracy and network complexity. we operationalize the complexity of a neural network as its number of nonzero parameters, reflecting the size of the subnetwork required to achieve a given accuracy. as such, we would like to use the l 0 norm, which counts the number of nonzero entries in the parameter vector θ: ideally, the l 0 norm would form a part of our objective function like so: we get around this limitation using a relaxation of l 0 regularization developed by @xcite . for the j'th parameter in our model θ j , we assign a masking parameter π @xmath0. this parameterizes a distribution with cumulative distribution function q(•|π j ), from which we can sample a mask value z @xmath1, 1], which critically can take the values of true 0 or 1. the vector of values z generated in this way is then used as a mask to filter the parameters θ, generating a vector of masked parameters θ where θj = z j θ j . this parameterization lends us a new objective function where the labels y i are predicted from the inputs x i using the masked parameters θ, and the model is penalized for having too few masked parameters: the regularization term now reflects the expected number of parameters whose value is not masked. we use equation 3 in all our experiments below, with different loss functions l as required. when l is a form of cross-entropy this term represents the cost of encoding the data using the distribution specified by the neural network. under these conditions, the objective becomes a form of minimum description length as a two part code: with the regularization term encoding the distribution, and l encoding the data @xcite . though our approach focuses on the mdl interpretation, this formulation also has a bayesian interpretation, optimizing the negative log likelihood with the regularization term as a prior and the loss term as a posterior as we show in appendix a. ## conclusion in our complexity measurement experiments we observe that subregular languages are represented by consistently simpler networks than similar regular languages, and that human-learnable subregular patterns are represented by simpler networks than unlearnable ones. this result is surprising, given that the use of a description length criterion to distinguish these languages had been deemed unlikely @xcite . furthermore, we found that in the generalization experiment, data consistent with a subregular and regular language leads to a preferential generalization towards learning the subregular distribution, and that this preference increases as the network becomes simpler. this supports the idea that a change in computational representation systems may favor subregular over regular languages, with the caveat that comparing subregular languages with radically different complexities in fsa representation may mean that this generalization pattern does not hold. why do lstms favor subregular languages? we argue that our results may explain this preference via the lottery ticket hypothesis @xcite . this hypothesis states that neural networks learn by tuning "winning tickets"-which are subnetworks that perform well on the task at initialization-which explains why larger neural networks perform well (they "buy more tickets"). the existence of smaller networks (as we define them) for subregular languages means that any neural network will contain more tickets for subregular languages at initialization, and thus have an inductive bias toward such languages. if this line of reasoning is true, l 0 regularization does not introduce anything qualitatively new in lstm training, but shifts the probability mass to favor tickets with smaller subnetworks. perhaps more controversially, we also believe these results may be of interest to human cognition. while the human brain is not an lstm, our results indicate that a subregular bias can be downstream of a bias for simplicity within an appropriate computational formalism, showing that rich (and often puzzling) constraints can be downstream from simple rules. a bias like this can be construed as a universal grammar-a bound on learnable formal languages @xcite . more needs to be done, of course. this work is far from a proof of the simplicity of subregular languages in lstms. likewise, more subregular languages ought to be investigated. we may find, for example, that the true inductive bias for lstms is not exactly subregular, or that only certain aspects of subregularity are simple to implement. but we find the current results exciting and intriguing, for its relationship to network complexity and function implementation, its potential to explain lstm inductive biases, and the demonstration of subregular biases resulting from computational complexity constraints.