“I find it interesting that transformers are equivalent to first order logic on circuits with counters.”
按年被提到
20232023 · 4 次2026
Tighter Bounds on the Expressivity of Transformer Encoders
Transformer 编码器表达力的更紧界
David Chiang, Peter Cholak, Anand Pillay · 2023
用带计数量词的一阶逻辑刻画 Transformer 编码器的表达力
被推荐 · 3 人首次 2023-04-25 · 最近 2024-01-09
3不同的人
4活跃月份
5讨论串
4被引(OpenAlex)
此前有研究表明 Transformer 编码器至少与某类计数器机一样有表达力,也有研究表明固定精度的 Transformer 编码器只能识别 uniform TC⁰ 中的语言。论文把二者联系并加强,找出一种带计数量词的一阶逻辑变体,它同时是固定精度 Transformer 编码器的上界和(一般)Transformer 编码器的下界。这使我们离准确刻画 Transformer 编码器能识别的语言又近了一步。
HN 为什么提它
评论者引用它说明:固定精度的 Transformer 不是图灵完备的,其能力受带计数量词的一阶逻辑变体界定。
其他难度 5 / 5约 60 分钟经得起时间
读之前最好知道
1形式语言与自动机
2一阶逻辑与计数量词
3电路复杂度(TC⁰)
4Transformer 编码器
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及推荐inciampati · 2023-06
觉得有意思:Transformer 等价于带计数器电路上的一阶逻辑
引用bmc7505 · 2023-06
“Although there is a growing evidence that Transformers and GNNs have foundational limits to expressivity [3, 4, 5]”
引它说明有越来越多证据表明 Transformer 与 GNN 的表达力存在根本局限
引用meltyness · 2023-12
“To that, what can these express, precisely, is an interesting question; so for transformer encoders:”
借它回答 transformer encoder 究竟能表达什么,给出表达力的界
引用inciampati · 2024-01
“Transformers with fixed precision and any amount of memory are not Turing complete. They're bounded by a variant of first order logic with counting quantifiers.”
拿它说明固定精度的 Transformer 不是图灵完备的,受带计数量词的一阶逻辑限制
被提交为 story · 1 次
- Tighter bounds on the expressivity of transformer encoders ↗bmc7505 · 2023-04-25 · 7 分