最近一两年，transformer 已经在 NLP、CV 等多样化任务上实现了卓越的性能，并有一统 AI 领域的趋势。那么，推出已近五年的注意力机制真的是所有人需要的吗？近日，有论文检验了 transformer 在两种形式语言上的理论缺陷，并且设计了方法克服这种缺陷。文章还研究了可能出现的长度泛化的问题，并提出了相应的解决方案。
尽管 transformer 模型在许多任务中都非常有效，但它们对一些看起来异常简单的形式语言却难以应付。Hahn (2020) 提出一个引理 5），来试图解释这一现象。这个引理是：改变一个输入符号只会将 transformer 的输出改变 𝑂(1/𝑛)，其中 𝑛 是输入字符串的长度。
因此，对于接收（即判定某个字符串是否属于某个特定语言）只取决于单个输入符号的语言，transformer 可能会以很高的准确度接受或拒绝字符串。但是对于大的 𝑛，它必须以较低的置信度做出决策，即给接受字符串的概率略高于 ½，而拒绝字符串的概率略低于 ½。更准确地说，随着 𝑛 的增加，交叉熵接近每个字符串 1 比特，这是最坏情况的可能值。
近期，在论文《Overcoming a Theoretical Limitation of Self-Attention》中，美国圣母大学的两位研究者用以下两个正则语言（PARITY 和 FIRST）来检验这种局限性。
Hahn 引理适用于 PARITY，因为网络必须关注到字符串的所有符号，并且其中任何一个符号的变化都会改变正确答案。研究者同时选择了 FIRST 作为引理适用的最简单语言示例之一。它只需要注意第一个符号，但因为更改这个符号会改变正确答案，所以该引理仍然适用。
尽管该引理可能被解释为是什么限制了 transformer 识别这些语言的能力，但研究者展示了三种可以克服这种限制的方法。
首先，文章通过显式构造表明，以高准确度识别任意长度的语言的 transformer 确实是存在的。研究者已经实现了这些结构并通过实验验证了它们。正如 Hahn 引理所预测的那样，随着输入长度的增加，这个构建的 transformer 的交叉熵接近 1 比特（也就是，仅比随机猜测好一点）。但文章也表明，通过添加层归一化，交叉熵可以任意接近零，而与字符串长度无关。
研究者在实践中还发现，正如 Bhattamishra 等人所指出的，transformer 无法学习 PARITY。也许更令人惊讶的是，在学习 FIRST 时，transformer 可能难以从较短的字符串泛化到较长的字符串。尽管这不是 Hahn 引理的逻辑上可以推出的结果，但它是 Hahn 引理预测行为的结果。幸运的是，这个问题可以通过简单的修改来解决，即将注意力的 logit 乘以 log 𝑛。此修改还改进了机器翻译中在长度方面的泛化能力。
论文地址：https://arxiv.org/pdf/2202.12172.pdf
精确解决方案
克服 Hahn 引理所暗示的缺点的第一种方法是通过显式构造表明 transformer 可以以高精度识别出上述提到的两种语言。
针对 PARITY 的前馈神经网络（FFNN）
Rumelhart 等人表明，对于任何长度𝑛都有一个前馈神经网络 (FFNN) 可以计算长度正好为 𝑛 的字符串的 PARITY。他们还表明，随机初始化的 FFNN 可以自动学习这么做。
由于文章所提出构建方式部分基于他们的，因此详细回顾他们的构建可能会有所帮助。设𝑤为输入字符串，|𝑤| = 𝑛，𝑘是𝑤中 1 的个数。输入是一个向量 x，使得 x_𝑖 = I[𝑤_𝑖 = 1]。第一层计算 𝑘 并将其与 1,2,...,n 进行比较：
因此，
第二层将奇数元素相加并减去偶数元素：
针对 PARITY 的 transformer
命题 1. 存在一个带有 sigmoid 输出层的 transformer，它可以识别（在上述意义上）任意长度字符串的 PARITY 语言。
最初，研究者将构造一个没有层归一化的 transformer 编码器（即 LN(x) = x）；然后展示如何添加层标准化。设 𝑘 是 1 在 𝑤 中出现的次数。网络计算的所有向量都有 𝑑 = 9 维；如果显示出较少的维度，则假设剩余的维度为零。词和位置嵌入是：
研究者认为，位置编码的第五维使用余弦波是一个相当标准的选择，尽管它的周期 (2) 比标准正弦编码中的最短周期 (2𝜋) 短。第四维度诚然不是标准的；但是，研究者认为这依然是一种合理的编码，并且非常容易计算。因此，单词𝑤_𝑖的编码是：
第二个 head 不做任何事情（W^V,1,2 = 0；query 和 key 可以是任何东西）。在残差连接之后，可以得到：
在 Rumelhart 等人的构造中，下一步是使用阶跃激活函数为每个 𝑖 计算 I[𝑖 ≤ 𝑘]。文章提出的构造有两个不同之处。首先，激活函数采用 ReLU，而不是阶跃激活函数。其次，因为注意力总和必须为 1，如果 𝑛是奇数，那么偶数和奇数位置将获得不同的注意力权重，因此奇数位置减去偶数位置的技巧将不起作用。相反，我们想要计算 I[𝑖 = 𝑘]（如下图 1）。
第一个 FFNN 有两层，第一层是：
由此可以得出：
第二层采用线性的方式把这三个值结合在一起得到想要的 I[𝑖 = 𝑘]。
第二个自注意力层测试位置𝑘是偶数还是奇数。它使用两个 head 来做到这一点，一个更强烈地关注奇数位置，一个更强烈地关注偶数位置；两者的平均维度大小为 8：
针对 FIRST 的 transformer
接下来，研究者为 FIRST 构建一个 transformer。根据学习每个位置词嵌入的常见做法（Gehring 等人，2017 年），他们使用位置编码来测试一个词是否在第 1 个位置 ：
第一层 FFNN 计算一个新的组件（5）来测试是否 i = 1 以及 w_1 = 1。
第二个自注意力层只有一个单一的 head，这使得 CLS 关注于位置 1.
第二层 FFNN 什么都不做（W^F,2,1 = b^F,2,1 = W^F,2,2 = b^F,2,2 = 0)。所以在 CLS 处（位置 0 处）：
最后输出层仅仅选择组件 6。
