按年被提到
20232023 · 4 次2026
大模型与语言模型›模型表达力与计算理论·arXiv:2301.10743 · cs.LG

Tighter Bounds on the Expressivity of Transformer Encoders

Transformer 编码器表达力的更紧界
David Chiang, Peter Cholak, Anand Pillay · 2023

用带计数量词的一阶逻辑刻画 Transformer 编码器的表达力

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 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

“I find it interesting that transformers are equivalent to first order logic on circuits with counters.”

觉得有意思:Transformer 等价于带计数器电路上的一阶逻辑
Thinking Like Transformers (pdf)原评论 ↗
引用bmc7505 · 2023-06

“Although there is a growing evidence that Transformers and GNNs have foundational limits to expressivity [3, 4, 5]”

引它说明有越来越多证据表明 Transformer 与 GNN 的表达力存在根本局限
Researchers warn of ‘model collapse’ as AI trains on AI-generated content原评论 ↗
引用meltyness · 2023-12

“To that, what can these express, precisely, is an interesting question; so for transformer encoders:”

借它回答 transformer encoder 究竟能表达什么,给出表达力的界
Ask HN: AI/ML papers to catch up with current state of AI?原评论 ↗
引用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 不是图灵完备的,受带计数量词的一阶逻辑限制
Turing Complete Transformers: Two Transformers Are More Powerful Than One原评论 ↗
被提交为 story · 1 次