Theoretical Conditions and Empirical Failure of Bracket Counting on Long Sequences with Linear Recurrent Networks (2023)

Abstract: Previous work has established that RNNs with an unbounded activation function have the capacity to count exactly. However, it has also been shown that RNNs are challenging to train effectively and generally do not learn exact counting behaviour. In this paper, we focus on this problem by studying the simplest possible RNN, a linear single-cell network. We conduct a theoretical analysis of linear RNNs and identify conditions for the models to exhibit exact counting behaviour. We provide a formal proof that these conditions are necessary and sufficient. We also conduct an empirical analysis using tasks involving a Dyck-1-like Balanced Bracket language under two different settings. We observe that linear RNNs generally do not meet the necessary and sufficient conditions for counting behaviour when trained with the standard approach. We investigate how varying the length of training sequences and utilising different target classes impacts model behaviour during training and the ability of linear RNN models to effectively approximate the indicator conditions.

## introduction recurrent neural networks (rnns) have a long history of being used to solve a wide range of tasks involving sequential data. they were the most common choice for natural language processing, but have since been largely replaced by transformers in recent years. however, there has been a recent resurgence of interest in the theoretical aspects of rnns, as seen in studies such as @xcite . another study found that rnns with squashing and non-squashing (i.e. unbounded) activation functions exhibit qualitative differences in their counting abilities @xcite . this, along with the findings of @xcite , suggests that even rnns with unbounded activation functions struggle to learn accurate counting on very long sequences. it is therefore crucial to understand why rnns, despite having the capacity, often fail to accurately count in practice. in this study, we examine the behaviour of the simplest form of rnns: a linear single-cell rnn. our goals are to: a) theoretically identify the necessary conditions for a linear rnn to have the ability to count, and b) explore how these conditions relate to the empirical behaviour of trained linear rnn models. the primary contributions of this paper are: a) we identify two conditions that indicate counting behaviour in linear rnns; b) we prove that these indicator conditions are necessary and sufficient for exact counting behaviour to be achieved in linear rnns; c) we then show empirically that linear rnns generally do not learn exact counting and do not meet the indicator conditions; and finally, d) we show empirical relationships between the length of the training sequences and the indicator value distributions. ## related work the success of deep learning sparked a renewed interest in research into the understanding of the theoretical properties of neural networks. it has been known for long that rnns are @xcite . however, @xcite showed that there are different classes of rnn architectures with respect to counting capacity when using finite precision states. the relationship between rnns and automata and formal languages has been investigated by @xcite and a formal hierarchy of counter machines has been developed by @xcite . this analysis is often based on "saturating" the network, i.e. replacing sigmoids with step functions, so that neural activations become binary, allowing for simpler analysis. in practice however, activations in neural networks use a wide variety of values and systematic behaviour like counting or even parsing is often not observed, which has been discussed for over 30 years since @xcite . more recently, lake and baroni (2017) identified a specific lack of systematic behaviour and devised scan, a synthetic language processing task that standard rnns fail on. a traditional approach for processing the hierarchical structure of language is to use a stack and a number of neural stack versions have been introduced, such as those by @xcite , @xcite and @xcite , which performed well on scan. @xcite use stack-augmented rnns to learn dyck-2 languages. @xcite developed methods to achieve more stable behaviour of neural stacks, achieving good, but not perfect, performance on longer sequences up to 160 tokens. the generalisation of formal language tasks to very long sequences is not often addressed, as it requires an exact or near exact behaviour of the neural network in order avoid accumulation of errors, e.g. when counting. @xcite claims that lstms can learn to count, but did not test for sequences of length greater than 100. @xcite reported that relu rnns, which were generally hard to train, and even lstms which are easier to train on counting tasks, did fail for sequences of several hundred tokens. similarly, in our previous work @xcite we show that almost all relu rnns and lstms fail on sequences of length 1000. these studies generally indicate that rnns do not reach a configuration that enables exact counting. it is not clear what the general conditions are for an rnn to perform exact counting, which is necessary for developing a deeper understanding of the behaviour of rnns. we start to address this question here by studying the case of a linear single-cell rnn. ## counting behaviour in linear rnns in this section we formally define the balanced bracket language, balanced bracket counter and linear recurrent network and we identify conditions for the network weights that indicate that the linear recurrent network will behave as a balanced bracket counter. we base our counter definitions on the general counter machine (gcm) as defined by merrill (2020), which we also listed for convenience in appendix a. the gcm is defined by a vocabulary σ, finite set of states q, initial state q 0 , counter update function u, state update function δ, and acceptance mask f . some components, such as states, can be empty. the counter computation also uses a zero check function. an input string x is processed by the counter one token x t at a time. the counter update function u is used to update the counter value c with integer increments (+m). the counter updates are dependent on the current input token, the current state, and a finite mask of the current state. in our setting, a counter machine is said to accept a sequence if @xmath0. a counter machine m is said to accept a language l if m accepts s ⇐⇒ @xmath1. we focus on sequences consisting of one type of bracket: σ ={'(', ')'}. ## counting in linear rnns in practice we conduct experiments to analyse the models and whether or not they satisfy the conditions defined in the previous section in training. we use 2 classification tasks to evaluate our models. ## conclusions and future work although linear rnns have the theoretical capacity for counting behaviour, previous research has shown that these models often struggle to effectively generalise counting behaviour to long sequences. in this study, we present a set of necessary and sufficient conditions that indicate counting behaviour in linear rnns and provide proof that meeting these conditions is equivalent to counting behaviour. to investigate the extent to which these conditions are met, we examine the parameters of models trained on sequences of varying lengths for classification tasks. we use both binary and ternary classification tasks and find that the models do not fully meet these conditions, but do approach them and get closer as the sequence length increases. there are several potential areas for future work based on these findings. one possible research direction is to extend this approach to relu rnns, and lstms as far as possible. another option is to devise methods to ensure that the indicator conditions we have identified are met during training in order to improve the generalisation abilities of our models.