Simulating Weighted Automata over Sequences and Trees with Transformers

变压器是自然语言处理（NLP）社区中无处不在的模型，并在过去几年中展示了令人印象深刻的实证成功。然而，我们对它们如何推理以及它们计算能力的限制知之甚少。这些模型不按顺序处理数据，却表现出比RNN等顺序神经模型更好的性能。最近的研究表明，这些模型可以紧凑地模拟确定性有限自动机（DFAs）的顺序推理能力。这引出了以下问题：变压器能否模拟更复杂的有限状态机的推理？在这项工作中，我们展示了变压器可以模拟加权有限自动机（WFAs）和加权树自动机（WTA）。这些模型类包含DFAs，并将加权自动机推广到树形结构输入。我们正式证明了这些说法，并提供了变压器模型所需的上界，作为目标自动机状态数量的函数。在实证方面，我们进行了合成实验，表明变压器能够通过标准的基于梯度的训练学习这些紧凑的解决方案。

论文旨在探究transformers的计算能力极限，能否模拟更复杂的有限状态机，如加权有限自动机和加权树自动机。

论文证明了transformers可以模拟加权有限自动机和加权树自动机，并给出了所需transformer模型大小的上限。

论文通过标准梯度训练在合成实验中证明了transformers可以学习这些紧凑的解决方案。值得关注的是，这项研究为理解transformers的计算能力提供了新的视角。

最近的相关研究包括《Attention is all you need》和《The expressive power of neural networks》。