LSTM Networks Can Perform Dynamic Counting
Table 3: The performances of the RNN, GRU, and LSTM models on four language modeling tasks. Shuffle-2 denotes the shuffle of two Dyck-1 languages defined over different alphabets, and similarly Shuffle-6 denotes the shuffle of six Dyck-1 languages defined over different alphabets. Min/Max/Median results were obtained from 10 different runs of each model with the same random seed across each run. We note that the LSTM models not only outperformed the RNN and GRU models but also often achieved full accuracy on the short test set in all the “counting” tasks. Nevertheless, even the LSTMs were not able to yield a good performance on the Dyck-2 language modeling task, which requires a stack-like mechanism.
['[BOLD] Task', '[BOLD] Model', '[BOLD] Training Set  [BOLD] Min', '[BOLD] Training Set  [BOLD] Max', '[BOLD] Training Set  [BOLD] Med', '[BOLD] Short Test Set  [BOLD] Min', '[BOLD] Short Test Set  [BOLD] Max', '[BOLD] Short Test Set  [BOLD] Med', '[BOLD] Long Test Set  [BOLD] Min', '[BOLD] Long Test Set  [BOLD] Max', '[BOLD] Long Test Set  [BOLD] Med']
First, we highlight that all the LSTM models obtained full accuracy on the training set and short test set, whose sequences were bounded to [2,50], in all the ten trials. They were also able to easily generalize to longer and deeper sequences in the long test set: They obtained perfect accuracy in nine out of ten trials and 99.98% accuracy (only 1 incorrect prediction) in the remaining trial. These results exhibit that the LSTMs can indeed perform unbounded dynamic counting. Furthermore, they were able to generalize well to longer and deeper sequences in both shuffle languages, achieving an almost perfect median accuracy score on the long test set. In contrast, the GRU models performed slightly worse than the LSTM models on the training and short test sets, but the GRUs did not yield the same performance as the LSTMs on the long test set, obtaining median scores of 93.12% and 85.14% in the Shuffle-2 and Shuffle-6 languages, respectively. Additionally, the simple RNN models always performed much worse than the GRU and LSTM models and could not even learn the training sets in either of the shuffle languages. These empirical findings show that the LSTM models can successfully emulate a DCAk, a deterministic (real-time) automaton with k-counters, each capable of performing an arbitrary number of turns.