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.

该研究探讨了基于 Transformer 的架构在学习隐藏马尔科夫模型 (HMMs) 及其变种方面的性能。通过广泛的实验证明，Transformer 在训练速度和测试精度方面始终不如循环神经网络 (RNNs)。此外，研究还揭示了 Transformer 的深度与其能够有效学习的最长序列长度之间的关系，并通过实验证明了一种名为块 Chain-of-Thought (CoT) 的变种可以帮助 Transformer 模型减小评估误差且学习更长的序列。最后，理论结果证明了 Transformer 在近似具有对数深度的 HMMs 时的表达能力。

Transformer 学习 HMM 的局限性

On Limitation of Transformer for Learning HMMs

Effective and efficient malware detection is at the forefront of research
into building secure digital systems. As with many other fields, malware
detection research has seen a dramatic increase in the application of machine
learning algorithms. One machine learning technique that has been used widely
in the field of pattern matching in general-and malware detection in
particular-is hidden Markov models (HMMs). HMM training is based on a hill
climb, and hence we can often improve a model by training multiple times with
different initial values. In this research, we compare boosted HMMs (using
AdaBoost) to HMMs trained with multiple random restarts, in the context of
malware detection. These techniques are applied to a variety of challenging
malware datasets. We find that random restarts perform surprisingly well in
comparison to boosting. Only in the most difficult "cold start" cases (where
training data is severely limited) does boosting appear to offer sufficient
improvement to justify its higher computational cost in the scoring phase.

通过将 AdaBoost 技术与多个随机重启训练的隐马尔可夫模型（HMMs）进行比较，我们发现在应对具有挑战性的恶意软件数据集时，随机重启表现出令人惊讶的良好性能，只有在训练数据严重受限的最困难的 “冷启动” 情况下，AdaBoost 才显著改善且可较高计算成本来进行评分阶段的义学。