Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity
Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity
复制标题
DOI：
10.1162/tacl_a_00490
复制
发表时间：
2022-04
影响因子：
10.9
通讯作者：
Sophie Hao;D. Angluin;R. Frank
中科院分区：
文献类型：
--
作者：
Sophie Hao;D. Angluin;R. Frank
摘要分析了变压器编码者自我注意机制的三种不同形式：唯一硬注意(UHAT)、广义唯一硬注意(GUHAT)和平均硬注意(AHAT)。我们证明了UHAT和GUHAT转换器被视为字符串接受器，它们只能识别复杂类AC0中的形式语言，复杂类AC0是恒定深度和多项式大小的布尔圈族可识别的语言。这个上限包含了Hahn(2020)的结果，即GUHAT不能识别Dyck语言或对等语言，因为这些语言不在AC0之外(Furst等人，1984)。相比之下，AHAT网络可以识别非AC0语言大多数和Dyck-1，这意味着AHAT可以识别UHAT和GUHAT无法识别的语言。
Abstract This paper analyzes three formal models of Transformer encoders that differ in the form of their self-attention mechanism: unique hard attention (UHAT); generalized unique hard attention (GUHAT), which generalizes UHAT; and averaging hard attention (AHAT). We show that UHAT and GUHAT Transformers, viewed as string acceptors, can only recognize formal languages in the complexity class AC0, the class of languages recognizable by families of Boolean circuits of constant depth and polynomial size. This upper bound subsumes Hahn’s (2020) results that GUHAT cannot recognize the DYCK languages or the PARITY language, since those languages are outside AC0 (Furst et al., 1984). In contrast, the non-AC0 languages MAJORITY and DYCK-1 are recognizable by AHAT networks, implying that AHAT can recognize languages that UHAT and GUHAT cannot.