On Limitation of Transformer for Learning HMMs
This work addresses a limitation in sequential modeling for machine learning researchers, showing Transformers' shortcomings in learning basic models like HMMs, which is incremental as it builds on prior comparisons with RNNs.
The paper investigates Transformers' ability to learn Hidden Markov Models (HMMs), finding they consistently underperform RNNs in training speed and testing accuracy, with Transformers struggling on challenging instances where RNNs succeed, and proposes a block Chain-of-Thought variant to reduce error and learn longer sequences at increased training time.
Despite the remarkable success of Transformer-based architectures in various sequential modeling tasks, such as natural language processing, computer vision, and robotics, their ability to learn basic sequential models, like Hidden Markov Models (HMMs), is still unclear. This paper investigates the performance of Transformers in learning HMMs and their variants through extensive experimentation and compares them to Recurrent Neural Networks (RNNs). We show that Transformers consistently underperform RNNs in both training speed and testing accuracy across all tested HMM models. There are even challenging HMM instances where Transformers struggle to learn, while RNNs can successfully do so. Our experiments further reveal the relation between the depth of Transformers and the longest sequence length it can effectively learn, based on the types and the complexity of HMMs. To address the limitation of transformers in modeling HMMs, we demonstrate that a variant of the Chain-of-Thought (CoT), called $\textit{block CoT}$ in the training phase, can help transformers to reduce the evaluation error and to learn longer sequences at a cost of increasing the training time. Finally, we complement our empirical findings by theoretical results proving the expressiveness of transformers in approximating HMMs with logarithmic depth.