按年被提到
20222023 · 7 次2026
机器学习与深度学习›深度学习理论与泛化·arXiv:2207.02098 · cs.LG

Neural Networks and the Chomsky Hierarchy

神经网络与乔姆斯基层级
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, Pedro A. Ortega · 2022

用乔姆斯基层级预测不同神经网络架构在分布外泛化上的极限

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 7 人首次 2022-07-16 · 最近 2026-07-12
7不同的人
12活跃月份
14讨论串
64被引(OpenAlex)

作者做了大规模实证研究(20,910 个模型、15 个任务),检验计算理论能否预测神经网络泛化的实际极限,发现按乔姆斯基层级对任务分组可以预测某些架构能否泛化到分布外输入,包括数据和训练时间再多也无法出现任何非平凡泛化的负面结果。结果显示在其任务子集上,RNN 和 Transformer 无法在非正则任务上泛化,LSTM 能解决正则和计数器语言任务,只有带结构化记忆(如栈或记忆带)的网络才能成功泛化到上下文无关和上下文相关任务。

HN 为什么提它

评论者讨论 Transformer 的局限时反复引用它,作为 Transformer 在嵌套结构等乔姆斯基层级任务上不如 LSTM 或带记忆网络的形式化证据,也有人提醒结论并不绝对,因为训练不是无限进行的。

实证研究难度 4 / 5约 60 分钟经得起时间
读之前最好知道
1乔姆斯基层级(Chomsky hierarchy)与形式语言
2自动机与可计算性基础
3RNN、LSTM 与 Transformer
4分布外泛化(out-of-distribution generalization)
5带栈或记忆带的记忆增强网络

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
强烈推荐YeGoblynQueenne · 2024-11

“And btw that's a good paper. Probably one of the most satisfying DL papers I've read in recent years.”

强烈推荐,称是近年读过最令人满足的深度学习论文之一
Interview with gwern原评论 ↗
推荐wslh · 2024-09

“worth exploring the work discussed in the paper”

推荐它,认为论文所讨论的工作值得探索
Chain of Thought empowers transformers to solve inherently serial problems原评论 ↗
引用emiliano2022 · 2022-08

“This is a very interesting article, in particular because it brings up that whole Chomsky topic of the grammar hierarchy (see Neural Networks and the Chomsky Hierarchy).”

引它说明文章涉及乔姆斯基语法层级,并与神经网络相关
Deep Learning Alone Isn’t Getting Us to Human-Like AI原评论 ↗
引用cma · 2023-02

“Some big limitations of transformers as well:”

引它说明 Transformer 在形式语言任务上的一些重大局限
What Is ChatGPT Doing and Why Does It Work?原评论 ↗
引用shawntan · 2023-04

“Recurrency will help, see the empirical results in this paper: Neural Networks and the Chomsky Hierarchy.”

引它的实证结果说明循环结构有帮助,LSTM 能解奇偶并泛化到更长输入
The New XOR Problem原评论 ↗
引用cma · 2023-05

“There are also limits to the sequence to sequence things they can effectively learn, in some cases weaker than LSTMs:”

引它说明模型能学的序列到序列任务有限,有时弱于 LSTM
Ask HN: Why can GPT4 en/decode base64?原评论 ↗
看全部 13 条 →
引用jabowery · 2023-06

“This limitation has been pointed out formally by the DeepMind paper "Neural Networks and the Chomsky Hierarchy".”

引它说明这篇 DeepMind 论文已形式化指出 Transformer 的这一局限
Bard is getting better at logic and reasoning原评论 ↗
引用jabowery · 2023-06

“This limitation has been pointed out formally by the DeepMind paper "Neural Networks and the Chomsky Hierarchy".”

引它说明这篇 DeepMind 论文已形式化指出 Transformer 的这一局限
Bard is getting better at logic and reasoning原评论 ↗
引用cma · 2023-06

“Deep Mind had this paper on that, showing weaknesses of transformers relative to other models in generalizing from example productions from different tiers of the hierarchy:”

引它说明 Transformer 在乔姆斯基层级各层的泛化弱于其他模型
Modern language models refute Chomsky’s approach to language原评论 ↗
引用cma · 2024-04

“It's not conclusive since it is not training indefinitely”

说明它的结论并不确凿,因为训练没有无限进行
LLMs can't simulate a Turing machine reliably原评论 ↗
引用cma · 2024-04

“transformers get beat out on learning to reproduce outs towards the general computer end”

引它说明在接近通用计算的任务上 Transformer 学得不如其他模型
Transformer as a general purpose computer原评论 ↗
引用YeGoblynQueenne · 2026-06

“Transformers, even equipped with memory, can only represent Regular automata [1].”

引它说明即使加了记忆,Transformer 也只能表示正则自动机
No, Artificial Intelligence is not Conscious - Ted Chiang原评论 ↗
引用cma · 2026-07

“This deepmind paper showed big limitations on nested structures with transformers, LSTMs actually did better:”

引它说明 Transformer 处理嵌套结构有明显局限,LSTM 反而更好
An agent in 100 lines of Lisp原评论 ↗
被提交为 story · 2 次