Empirical Analysis of the Inductive Bias of Recurrent Neural Networks by
  Discrete Fourier Transform of Output Sequences
A unique feature of Recurrent Neural Networks (RNNs) is that it incrementally
processes input sequences. In this research, we aim to uncover the inherent
generalization properties, i.e., inductive bias, of RNNs with respect to how
frequently RNNs switch the outputs through time steps in the sequence
classification task, which we call output sequence frequency. Previous work
analyzed inductive bias by training models with a few synthetic data and
comparing the model's generalization with candidate generalization patterns.
However, when examining the output sequence frequency, previous methods cannot
be directly applied since enumerating candidate patterns is computationally
difficult for longer sequences. To this end, we propose to directly calculate
the output sequence frequency for each model by regarding the outputs of the
model as discrete-time signals and applying frequency domain analysis.
Experimental results showed that Long Short-Term Memory (LSTM) and Gated
Recurrent Unit (GRU) have an inductive bias towards lower-frequency patterns,
while Elman RNN tends to learn patterns in which the output changes at high
frequencies. We also found that the inductive bias of LSTM and GRU varies with
the number of layers and the size of hidden layers.
Taiga Ishii, Ryo Ueda, Yusuke Miyao
Empirical Analysis of the Inductive Bias of Recurrent Neural Networks by Discrete Fourier Transform of Output Sequences

###### Abstract

A unique feature of Recurrent Neural Networks (RNNs) is that it incrementally processes input sequences. In this research, we aim to uncover the inherent generalization properties, i.e., inductive bias, of RNNs with respect to how frequently RNNs switch the outputs through time steps in the sequence classification task, which we call output sequence frequency. Previous work analyzed inductive bias by training models with a few synthetic data and comparing the model's generalization with candidate generalization patterns. However, when examining the output sequence frequency, previous methods cannot be directly applied since enumerating candidate patterns is computationally difficult for longer sequences. To this end, we propose to directly calculate the output sequence frequency for each model by regarding the outputs of the model as discrete-time signals and applying frequency domain analysis. Experimental results showed that Long Short-Term Memory (LSTM) and Gated Recurrent Unit (GRU) have an inductive bias towards lower-frequency patterns, while Elman RNN tends to learn patterns in which the output changes at high frequencies. We also found that the inductive bias of LSTM and GRU varies with the number of layers and the size of hidden layers.

## 1 Introduction

In this research, we aim to uncover the inherent generalization properties, i.e., inductive bias, of RNNs with respect to how frequently RNNs switch the outputs through time steps in the sequence classification task, which we call _output sequence frequency_ (Figure 1).

In supervised learning settings, a model is trained with finite input-output examples \(\{(x_{0},\,y_{0}),\dots,(x_{n},\,y_{n})\}\) and then tested with unseen input-output pairs. The models that achieve high accuracy on test data are often said to "generalize well". However, the important point is that function \(f\) that satisfies \(f(x_{i})=y_{i}\) cannot be uniquely determined by finite train examples. This entails that if a model generalizes well to a certain function \(f\), then the model hardly generalizes to another function \(f^{\prime}\) that has different outputs for the same unseen inputs, i.e., \(f(x_{\mathrm{test}})\neq f^{\prime}(x_{\mathrm{test}})\) but is consistent with the same train examples; \(f^{\prime}(x_{i})=y_{i}\). Therefore, it is crucial to understand what kind of functions a model inherently prefers to learn, which is referred to as **inductive bias**(White and Cotterell, 2021; Kharitonov and Chaabouni, 2020; Deletang et al., 2022; Lovering et al., 2020).

Our target is Recurrent Neural Network (RNN): a well-known deep learning architecture. A key feature of RNN is that it processes the input incrementally and predicts the output at each time step, producing a sequence of outputs. This is different from other deep learning architectures, e.g., Feed Forward Network (FFN), Convolutional Neural Network (CNN), and Transformers (Vaswani et al.,

Figure 1: An example showing a train dataset and two candidate generalization patterns, each showing a different output sequence frequency. Here, ”aababba” is the input sequence, and there are four binary train labels \(0,1,1,0\) each corresponding to the prefix of length \(2,3,5,6\).
2017). Due to the incremental processing feature of RNNs, the inputs can be of variable length; RNNs have been used for various tasks in natural language processing, such as sentence classification and text generation. It has also been used as a subcomponent of more complex architectures (Dyer et al., 2016) and to simulate human sequential processing (Steinert-Threlkeld and Szymanik, 2019). Variants of RNN architectures have been proposed so far. The most basic one is the Elman RNN (Elman, 1990). Later, more complex architectures, such as LSTM (Hochreiter and Schmidhuber, 1997) and GRU (Cho et al., 2014), have been proposed to improve modeling long-term dependencies.

Although deep learning models, including RNNs, are said to be high-performance models, they are essentially black boxes, and it is not clear what inductive bias they may have. In this research, in order to analyze the inductive bias of RNNs, we propose to calculate the output sequence frequency by regarding the outputs of RNNs as discrete-time signals and applying frequency domain analysis. Specifically, we apply discrete Fourier transform (DFT) to the output signals and compute the dominant frequencies to grasp the overall output patterns.

Inductive bias is not straightforward to analyze since it can be affected by various factors such as the task, dataset, and training method; theoretical analysis has been limited to simple architecture such as FFN (Rahaman et al., 2019; Valle-Perez et al., 2019). Therefore, empirical studies have been conducted to clarify the inductive bias in various tasks and settings, such as language modeling (White and Cotterell, 2021), sequence classification (Lovering et al., 2020), and sequence-to-sequence (Kharitonov and Chaabouni, 2020). These works approached the problems by designing synthetic datasets and testing several generalization patterns. However, when examining the output sequence frequency, we cannot directly apply these previous methods since enumerating exponentially many output sequence patterns in longer sequences is computationally difficult. To this end, our method makes use of frequency domain analysis to directly calculate the output sequence frequencies and avoid enumerating the candidate generalization patterns.

In the experiment, we randomly generated \(500\) synthetic datasets and trained models on a few data points (Figure 1). As a result, we found:

* LSTM and GRU have an inductive bias such that the output changes at lower frequencies compared to Elman RNN, which can easily learn higher frequency patterns,
* The inductive bias of LSTM and GRU varies with the number of layers and the size of hidden layers.

## 2 Background

### Inductive Bias Analysis

Inductive bias analysis is usually performed by constructing synthetic datasets. This is because data from real tasks are complex and intertwined with various factors, making it difficult to determine what properties of the dataset affect the behavior of the model. For example, White and Cotterell (2021) targeted LSTM and Transformer and investigated whether easy-to-learn languages differ depending on their typological features in language modeling. White and Cotterell (2021) used Context Free Grammar (CFG) to construct parallel synthetic language corpora with controlled typological features. They trained models on each language and computed their perplexities to find that LSTM performs well regardless of word order while the transformer is affected. Another more synthetic example is Kharitonov and Chaabouni (2020). Kharitonov and Chaabouni (2020) targeted LSTM, CNN, and Transformer. They designed four synthetic tasks in the sequence-to-sequence framework and trained models on very small datasets (containing 1\(\sim\)4 data points). To examine the inductive biases of the models, they prepared a pair of candidate generalization patterns, such as COUNT and MEMORIZATION, for each task and compared the models' preference over the candidate patterns by calculating the Minimum Description Length (Rissanen, 1978). Using extremely small train datasets makes it possible to restrict the information models can obtain during training and analyze the models' inherent inductive bias in a more controlled setup.

In this research, we take a similar approach as (Kharitonov and Chaabouni, 2020), restricting the train data to extremely small numbers. However, we cannot directly apply the methods of Kharitonov and Chaabouni (2020) because the approach of comparing with candidate generalization patterns can be impractical in our case. Specifically, when examining the output sequence frequency, it is necessary to feed the models with longer se
quences in order to analyze a wide range of frequencies from low to high; there are exponentially many patterns with the same number of output changes in longer sequences, which makes it difficult to exhaustively enumerate the candidate generalization patterns. Therefore, instead of preparing candidate generalization patterns, we directly calculate the output sequence frequency for each model by regarding the outputs of the model as discrete-time signals and applying frequency domain analysis.

### Frequency Domain Analysis

Discrete Fourier Transform (DFT) is a fundamental analysis technique in digital signal processing. Intuitively, DFT decomposes a signal into a sum of finite sine waves of different frequencies, allowing one to analyze what frequency components the original signal consists of. The DFT for a length \(N\) discrete-time signal \(f[0],\ldots,f[N-1]\) is defined by the following equation:

\[F[k]\;=\;\sum_{n=0}^{N-1}f[n]\exp\left(-\sqrt{-1}\frac{2\pi}{N}kn\right). \tag{1}\]

When \(f[n]\) is a real-value signal, it is sufficient to consider only \(k\in\{1,\ldots,\frac{N}{2}\}\).1 Here, \(k=1\) corresponds to the lowest frequency component and \(k=\frac{N}{2}\) to the highest.

Footnote 1: This is due to the periodicity of \(\exp(-\sqrt{-1}\frac{2\pi}{N}kn)\). Furthermore, we do not take into account the \(k=0\) term since it is called a DC term and works as an offset.

One useful measure for analyzing the property of the signal \(f[n]\) is the dominant frequency (Ng and Goldberger, 2007). In short, dominant frequency is the frequency component of maximum amplitude and is expected to represent the general periodic pattern of the original signal \(f[n]\). The dominant frequency \(\omega_{\mathrm{dom}}\;=\;\frac{2\pi}{N}k_{max}\), where \(k_{max}\;=\;\arg\max\{|F[k]|\}\).

## 3 Methods

### Task

To analyze the output sequence frequency, i.e., how frequently the output changes through time steps, we focus on a simple case of binary sequence classification task: the inputs are the prefixes of a binary sequence \(s\in\{\mathrm{a},\mathrm{b}\}^{*}\). Specifically, given a binary sequence \(s\in\{\mathrm{a},\mathrm{b}\}^{*}\), the input space \(\mathcal{I}\) and the output space \(\mathcal{O}\) are defined as follows:

\[\mathcal{I} \;=\;\{s_{0:i}\:|\:i=0,\ldots|s|-1\}, \tag{2}\] \[\mathcal{O} \;=\;\{(1-p,p)\:|\:p\in[0,1]\}, \tag{3}\]

where \(\mathcal{O}\) is a set of categorical distributions over the binary labels \(\{0,1\}\), and \(p\) denotes the probability of predicting label \(1\).

Without loss of generality, we can only consider the model's output probability of predicting label \(1\) for the sequence \(s_{0:i}\), which we denote by \(\mathcal{M}(s_{0:i})\). In this way, we can regard the model's output sequence \(\mathcal{M}(s_{0:0}),\ldots,\mathcal{M}(s_{0:|s|-1})\) as a discrete-time signal taking values in \([0,1]\).

### Train Dataset

Figure 2 shows an intuitive illustration of our dataset construction. Given a sequence \(s\), we randomly generate the binary labels \(y_{0:|s|-1}\), where each \(y_{i}\) is the label assigned to the prefix \(s_{0:i}\). When two successive labels \(y_{i}\) and \(y_{i+1}\) differ, we say there is a _label change_ (e.g., \(y_{9}\) and \(y_{10}\) in Figure 2).2 We then make a train dataset \(\mathcal{D}\) by taking instances where the labels change: \(\{(s_{0:i},y_{i}),(s_{0:i+1},y_{i+1})\:|\:y_{i}\neq y_{i+1}\}\). For example, in Figure 2, the train data \(\mathcal{D}\) contains \(\{(\mathrm{aa},0)\:(\mathrm{aab},1)\:(\mathrm{aababba},1)\:(\mathrm{aababba},0 ),\ldots\}\). Note that the original labels \(y_{0:|s|-1}\) can be uniquely recovered from \(\mathcal{D}\) simply by _interpolating_ or _extending_ the labels for other prefixes.

Footnote 2: Similarly, we use _output change_ for output sequences.

The procedure is formalized as follows:

1. Sample a sequence \(s\in\{0,1\}^{N}\), where \(N\) is

Figure 2: Illustration of train dataset construction. The train dataset contains only the instances corresponding to the label changes.
the length of the sequence,
2. Sample the number of label changes \(m\in\{1,\ldots M\}\), where \(M\) is the maximum number of label changes,
3. Sample the labels \(y_{0:|s|-1}\) so that all the \(m\) label changes do not overlap3, i.e. \(\forall i,j.\ i<j\wedge y_{i}\neq y_{i+1}\wedge y_{j}\neq y_{j+1}\Rightarrow i+1<j\), Footnote 3: This condition ensures that the labels in the train dataset are balanced.
4. Create a dataset as \[\mathcal{D}\ =\ \{(s_{0:i},y_{i}),(s_{0:i+1},y_{i+1})\,|\,y_{i}\neq y_{i+1}\}.\]

By training models on random input sequences \(s\), we expect the model predictions to represent the inherent generalization property of the model.

### Evaluation Metrics

For the analysis, we apply two evaluation metrics.

#### 3.3.1 Test Cross-entropy Loss

First, we compare the model's output sequence \(\mathcal{M}(s_{0:0}),\ldots,\mathcal{M}(s_{0:|s|-1})\) with the original labels \(y_{0:|s|-1}\) by calculating test cross-entropy loss \(\mathcal{L}_{\mathrm{CE}}\). Intuitively, near-zero \(\mathcal{L}_{\mathrm{CE}}\) indicates that the model generalizes to simply _interpolate_ or _extend_ the training labels since we constructed the train datasets so that the original labels can be recovered by interpolation, as described in section 3.2.

The loss is formalized as:

\[\begin{split}\mathcal{L}_{\mathrm{CE}}\ =&-\frac{1}{| \mathcal{T}|}\sum_{i\in\mathcal{T}}(y_{i}\ln(\mathcal{M}(s_{0:i}))\\ +(1&-y_{i})\ln(1-\mathcal{M}(s_{0:i}))),\end{split} \tag{4}\]

where \(\mathcal{T}=\{i\,|\,(s_{0:i},\_)\notin\mathcal{D}\}\) is the set of test data indices.

#### 3.3.2 Dominant Frequency

In case \(\mathcal{L}_{\mathrm{CE}}\) is high, we consider the model's output sequence \(\mathcal{M}(s_{0:0}),\ldots,\mathcal{M}(s_{0:|s|-1})\) as a discrete-time signal and apply frequency domain analysis to look into the model's behavior. More specifically, we apply DFT to the output signal and obtain the dominant frequency \(\omega_{\mathrm{dom}}\). The dominant frequency \(\omega_{\mathrm{dom}}\) is calculated by simply replacing \(f[n]\) in Equation 1 with \(\mathcal{M}(s_{0:n})\).

### Experiment Settings

Here, we describe the basic settings of our experiment. We use well-known basic RNN architectures: LSTM [16], GRU [10], and Elman RNN [1]. For the decoding, we use a linear decoder without bias followed by a softmax function. We try 4 combinations of hyperparameters: \((\textit{num\_layers},\ hidden\_size)\in\{(1,200),\ (2,200),\ (3,200),\ (2,2000)\}\), where \(\textit{num\_layers}\) denotes the number of layers, and \(\textit{hidden\_size}\) denotes the size of hidden layers.4

Footnote 4: For other hyperparameters and parameter initialization, we used the default settings of PyTorch [https://pytorch.org/](https://pytorch.org/).

For optimization, we train models to minimize the average cross-entropy loss by gradient descent using Adam [11] with a learning rate of \(1.0\times 10^{-4}\) for \(1000\) epochs.5

Footnote 5: Since the maximum size of train data is 10 in our settings, all the data are put in a batch during the training.

Finally, we randomly generate \(500\) train datasets with \(N\,=\,100,M\,=\,5\) and train \(10\) models with different random seeds for each dataset, architecture, and parameter setting. Note that this sparse setting (\(10:90\) train-test data ratio at maximum) keeps the hypothesis space large and thus enables us to analyze the inductive bias of the models as described in section 2.1.

Training all the models took around 30 hours using 8 NVIDIA A100 GPUs.

## 4 Findings

### Models Do Not Learn to Interpolate

In order to see if the models generalize simply to interpolate the given labels, we calculate the median test cross-entropy loss of the multiple models trained for each dataset (Figure 3). The dotted vertical line shows the random baseline loss

Figure 3: The median test cross-entropy loss counts for LSTM, GRU, and Elman RNN with \((\textit{num\_layers},\ hidden\_size)=(2,200)\). The dotted vertical line shows the random baseline loss of \(-\ln(\frac{1}{2})\).
of \(-\ln(\frac{1}{2})\approx 0.7\). As can be seen in Figure 3, the median test cross-entropy loss is higher than the random baseline for most datasets for all of LSTM, GRU, and Elman RNN. This indicates that, in most cases, none of the LSTM, GRU, or Elman RNN learns to interpolate in this extremely simple setup, where only the label-changing part is given as training data. We also observe a similar trend in other hyperparameter settings; The test cross-entropy losses for other settings are shown in Appendix A.

### Architectural Difference

Now that the test cross-entropy loss has revealed that the patterns learned by the models contain more output changes than the original pattern in the train data, the next step is to see if there are any architecture-specific trends in the output sequence patterns. We calculate the dominant frequency for each model and take the median over the models trained on the same dataset. Figure 4 shows the distribution of median dominant frequencies for LSTM, GRU, and Elman RNN with different hyperparameters. It is clear that, in all settings, LSTM and GRU tend to learn lower-frequency patterns, while the dominant frequencies of Elman RNN tend to be higher. Comparing LSTM and GRU, LSTM has slightly lower-frequency patterns for \(hidden\_size=200\) (Figure 4 (a, b, c)), though the difference is not as clear for \(hidden\_size=2000\) (Figure 4 (d)).

An example of sequential outputs of LSTM and Elman is shown in Figure 5. The top rows show the actual model outputs for a specific sequence, and the bottom rows show the DFT of model outputs. In this example, only 4 labels \(0,1,1,0\) are given to the prefixes of length \(60,61,84,85\). It is clear that both LSTM and Elman learn periodic patterns but do not learn to interpolate the given train labels. Besides, it is also notable that LSTMs indeed learn lower

Figure 4: The median dominant frequency counts for LSTM, GRU, and Elman RNN with different hyperparameters.
frequency patterns compared to Elman RNNs.

### Effect of Hyperparameters

Here, we describe how hyperparameters affect the observed inductive biases.

#### 4.3.1 Number of Layers

Figure 6 shows the median dominant frequencies of \(num\_layers=1,2,3\) for LSTM, GRU, and Elman RNN. As for LSTM, it can be seen that the proportion of patterns in the lower-frequency domain tends to increase as the number of layers increases. In other words, despite the increased complexity of the models, LSTMs tend to learn simpler patterns (in the sense that the output changes less). A similar trend is observed for GRU, although not as clear as for LSTM. On the other hand, Elman RNN does not show such apparent differences.

#### 4.3.2 Hidden Layer Size

Figure 7 shows the median dominant frequencies of \(hidden\_size=200,2000\) for LSTM, GRU, and Elman RNN. Although the trend is not so clear, for LSTM and GRU, the counts are slightly larger for \(\omega_{\mathrm{dom}}=0.5\sim 1.0\) when \(hidden\_size=2000\), while the counts are larger for \(\omega_{\mathrm{dom}}=0.0\sim 0.5\) when \(hidden\_size=200\). This is rather the opposite trend from that of \(num\_layers\). However, the above trend does not seem to appear in Elman RNN.

## 5 Discussion and Limitation

### Expressive Capacity and Output Sequence Frequency

Our results do not align with the expressive capacity of RNNs reported in previous work (Merrill et al., 2020; Weiss et al., 2018). Merrill et al. (2020); Weiss et al. (2018) formally showed that LSTM is strictly more expressive than GRU and Elman RNN. On the other hand, in our experiments, LSTM and GRU show a bias toward lower frequencies, while Elman RNN, which has the same expressive capacity as GRU, according to (Merrill et al., 2020), shows an opposite bias toward higher frequencies. Note that the expressive capacity and the inductive bias of a model are basically different concepts. This is because expressive capacity is the theoretical upper bound on the functions a model can represent with all possible combinations of its parameters, regardless of the training procedure. In contrast, inductive bias is the preference of functions that a model learns from finite train data, possibly depending on training settings. However, they are not entirely unrelated because a function that is impossible to learn in terms of expressive capacity will never be learned, which can emerge as inductive bias. We conjecture that the difference

Figure 5: An example of LSTM and Elman RNN with \((num\_layers,\ hidden\_size)=(2,200)\). The top rows show the actual model outputs for a specific sequence, and the bottom rows show the DFT of model outputs. In this example, 4 labels \(0,1,1,0\) are assigned to the prefixes of length \(60,61,84,85\). The Red and blue vertical lines correspond to the labels \(0,1\), respectively. The results of 10 models with different random seeds are shown.
Figure 6: The median dominant frequencies of \(num\_layers=1,2,3\) for LSTM, GRU, and Elman RNN with \(hidden\_size=200\).
between the expressive capacity and the observed inductive bias is due to the simplicity of our experiment setting. This difference is not a negative result: It indicates that inductive bias in such a simple setting is effective in observing detailed differences that cannot be captured by expressive capacity.

### Randomness of Outputs

Previous study showed that FFNs hardly learn random functions since they are inherently biased toward simple structured functions Valle-Perez et al. (2019). We can find a similar trend for RNNs in our experimental results. In other words, by regarding the outputs of RNNs as discrete-time signals, we can confirm that the signals are not random, i.e., white noises. If we assume that the output signals of the RNNs are random, the dominant frequency should be uniformly distributed from low to high-frequency regions. Therefore, the biased distribution in Figure 4 indicates that the outputs of the RNNs are not random signals. This is also clear from the example outputs in Figure 5, where the models show periodic patterns.

### Practical Implication

For LSTM and GRU, we observed different inductive biases between increasing the number of layers and hidden layer size. Previous study that investigated whether RNNs can learn parenthesis also reported that LSTM and GRU behaved differently when the number of layers and the hidden layer size were increased Bernardy (2018). Although the tasks are different, our findings align with the previous work. From a practical point of view, these findings suggest that it may be more effective to increase the number of layers than to increase the hidden layer size depending on the target task.

Besides, the fact that LSTM and GRU, which are known to be "more practical" than Elman RNN, tend to learn lower frequency patterns may support the idea that output sequence frequency aligns with "practical usefulness." Furthermore, a concept similar to output sequence frequency has been proposed as a complexity measure in sequence classification: sensitivity Hahn et al. (2021). While output sequence frequency focuses on the change in output over string length, sensitivity focuses on the change in output when a string is partially replaced, keeping its length. It would be an interesting future direction to examine the validity of inductive biases in output sequence frequency as an indicator of complexity and practical usefulness.

### Limitation

There are some dissimilarities between our experimental setup and practical sequence classification tasks:

* The task is limited to the binary classification of binary sequences,
* Models are trained only on prefixes of a sequence,
* The number of train data is extremely small.

Therefore, in order to accurately estimate the impact of our findings on the actual task, it is necessary to expand from sequence to language in a multi-label setting with a larger vocabulary.

Due to the computational complexity, we only tried 4 combinations of hyperparameters. However, it is still necessary to exhaustively try combinations of hyperparameters for a more detailed analysis.

## 6 Conclusion

This study focuses on inductive bias regarding the output sequence frequency of RNNs, i.e., how often RNNs tend to change the outputs through time steps. To this end, we constructed synthetic datasets and applied frequency domain analysis by regarding the model outputs as discrete-time signals.

Experimental results showed that LSTM and GRU have inductive biases towards having low output sequence frequency, whereas Elman RNN tends to learn higher-frequency patterns. Such differences in inductive bias could not be captured by the expressive capacity of each architecture alone. This indicates that inductive bias analysis on synthetic datasets is an effective method for studying model behaviors.

By testing different hyperparameters, we found that the inductive biases of LSTM and GRU vary with the number of layers and the hidden layer size in different ways. This confirms that when increasing the total number of parameters in a model, it would be effective not only to increase the hidden layer size but also to try various hyperparameters, such as the number of layers.

Although the experimental setting was limited to simple cases, we believe this research shed some light on the inherent generalization properties of RNNs and built the basis for architecture selection and design.