1. 项目概述当复杂性理论遇上AGI学习的“不可能性”证明最近在AI理论圈子里一篇题为《Reclaiming AI as a theoretical tool for cognitive science》的论文简称[VRGA24]引起了不小的波澜。这篇论文的核心主张相当大胆它声称从形式化的计算复杂性角度“证明”了通过机器学习从数据中实现人类水平智能即AGI本质上是计算不可行的。换句话说它试图给“通过数据学习实现AGI”这条路判了“死刑”。作为一名长期关注机器学习理论与实践的从业者我第一眼看到这个结论时直觉就告诉我这里面有问题。不是因为我对AGI的实现盲目乐观而是因为这种“一棍子打死”的论断与我们过去几十年在图像识别、自然语言处理等具体领域取得的、实实在在的进步经验相悖。ImageNet竞赛的突破、大语言模型的涌现能力都暗示着从数据中学习复杂函数是可能的关键在于我们如何理解“数据”和“学习”。经过仔细研读原文及其引发的讨论特别是Michael Guerzhoy的这篇反驳文章我发现问题的核心比想象中更深刻也更具启发性。它不是一个简单的对错之争而是触及了机器学习理论基石的两个关键概念数据分布假设和归纳偏置。[VRGA24]的证明之所以站不住脚根本原因在于它进行复杂性归约时偷偷地将“人类行为数据分布”这个高度结构化、充满规律的对象替换成了一个“任意的、多项式时间可采样的分布”。这相当于在证明“所有鸟都会飞”时把“鸟”的定义换成了“所有会飞的物体”然后得出结论说企鹅也会飞——逻辑上看似成立但前提已经偷换了概念。本文将深入拆解这个证明的逻辑漏洞并借此机会探讨在思考AGI或任何复杂学习任务的可学习性时为什么我们必须严肃对待数据的真实结构和学习算法自带的“偏见”。2. 核心论证拆解“不可能性”证明的逻辑链条与断裂点要理解反驳的关键我们首先需要看清原论文试图构建的论证大厦是如何搭建的以及它的地基在哪里出现了裂缝。2.1 [VRGA24]的“Ingenia定理”与归约策略原论文的核心是一个被称为“AI-by-Learning”的形式化问题。简单来说这个问题描述为给定一个从分布D中采样的方式即我们能获得一些数据以及参数K目标是找到一个长度不超过K的程序算法描述A使得A在从D中采样的情境s上能以高概率产生与人类行为b“足够接近”的输出。这里的“足够接近”由误差参数ε(n)和置信参数δ(n)来量化。随后论文提出了所谓的“Ingenia定理”声称AI-by-Learning问题是计算不可行的intractable。其证明策略是进行复杂性归约它将一个已知是计算困难的问题——“Perfect-vs-Chance”问题——归约到AI-by-Learning问题的一个实例上。因为Perfect-vs-Chance被证明是难的例如NP-hard那么如果存在一个高效算法能解决AI-by-Learning就能用它来高效解决Perfect-vs-Chance这与复杂性理论共识矛盾。因此AI-by-Learning也必须是难的。这个归约的逻辑听起来很严密但魔鬼藏在细节里。归约要成立有一个致命的前提AI-by-Learning问题中定义的分布D必须能够涵盖Perfect-vs-Chance问题中那个“任意的、多项式时间可采样的分布”。也就是说你必须证明任何这样的任意分布都能被解释为一种“人类情境-行为对”的分布。2.2 归约中的“偷梁换柱”从结构化分布到任意分布这正是整个论证崩塌的起点。在论文的非正式描述部分如第6页D被明确描述为从人类身上观察到的“情境-行为对”的分布。人类行为数据是什么样的它具有极强的内在结构和规律性。情境s的分布是结构化的如果s是自然图像其像素值的分布绝非随机噪声它遵循自然图像的统计规律如边缘、纹理、物体的层次结构。如果s是一段自然语言文本它遵循语法、语义和语用规则。行为b给定情境s的条件分布也是结构化的人类下象棋时走法受棋盘规则、策略和棋理约束人类在看到“猫”的图片时回答“这是猫”的概率远高于回答“这是香蕉”。这种条件分布反映了人类的认知规律、知识储备和目标任务。然而在附录的形式化证明和归约构造中为了将Perfect-vs-Chance问题嵌入进来D被悄然替换成了一个任意的、仅满足“多项式时间可采样”这一宽松条件的分布。“多项式时间可采样”只要求我们能高效地随机生成样本但对样本内容没有任何结构性要求。一个能快速输出随机加密密文的程序其输出分布也是多项式时间可采样的但这与人类行为数据相去甚远。这就导致了概念上的严重分裂论文标题和摘要中要证明不可行的对象是“从人类数据中学习以实现AGI”但实际证明中分析的对象是“从任意多项式时间可采样分布中学习一个函数”。后者是一个广为人知的、在无免费午餐定理框架下本就非常困难甚至不可学习的问题。而前者即从具有特定结构的人类行为分布中学习则是一个完全不同、且未被证明同等难度的问题。注意这里的关键区分在于“最坏情况分析”与“实际情况分析”。复杂性理论中的归约通常针对最坏情况。证明“问题X是NP-hard”意味着存在X的某些极端实例是难解的。但这不能直接推出“问题X的所有实例都是难解的”尤其是那些具有特殊结构的实例。例如布尔可满足性问题SAT是NP完全的但它的一个子集——2-SAT问题——是存在多项式时间算法的。同理即使“从任意分布学习”是难的也不能直接推出“从人类行为这一特定分布学习”同样是难的除非你能证明人类行为分布“足够任意”以至于包含了那些最难的学习实例。3. 归谬法的重击如果证明成立ImageNet学习也应是不可行的Michael Guerzhoy的反驳文章提供了一个极其有力且直观的归谬法reductio ad absurdum论证清晰地暴露了原证明的荒谬之处。他的论点简洁明了如果我们接受[VRGA24]的证明逻辑那么只需将证明文本中的“AGI”或“人类行为预测”全部替换为“ImageNet图像分类”整个数学证明结构依然完全成立。因为该证明只依赖于分布D是“多项式时间可采样”的这一性质而ImageNet数据集的采样过程从硬盘读取图片当然也是多项式时间的。因此按照原论文的论证我们将不得不得出结论学习对ImageNet图像进行分类也是计算不可行的。然而这与我们已知的事实严重矛盾。AlexNet在2012年的突破性工作[KSH12]已经证明ImageNet分类任务不仅是可解的而且可以通过深度卷积神经网络在有限的计算资源和数据下达到远超随机猜测的精度。此后的一系列工作更是将性能不断提升。这是一个在工程和学术上都被反复验证的可学习任务。这个矛盾迫使我们必须至少接受以下三者之一论文中对“计算不可行”的形式化定义并未准确捕捉其真实含义。论文的证明过程存在缺陷。ImageNet分类在理论上不可行但我们却奇迹般地做到了。显然第3点虽然是一种逻辑可能性但在一个务实的研究者看来近乎荒谬。第1点涉及定义问题但更直接、更核心的问题是第2点证明存在缺陷。这个归谬法像一把手术刀精准地指向了缺陷的根源——对数据分布D的不合理泛化。它告诉我们一个有效的可学习性证明必须紧密关联于特定问题本身的数据结构。ImageNet可学习是因为自然图像具有空间局部性、平移不变性等统计规律而卷积神经网络的归纳偏置恰好与之匹配。4. 修补证明面临的根本性挑战即使我们意识到原证明的漏洞一个自然的问题是能否通过修补建立一个真正坚实的、关于AGI学习不可行的复杂性证明Guerzhoy的文章指出了几条看似可行、实则布满荆棘的路径它们构成了根本性的挑战。4.1 挑战一精确数学化人类行为分布D这是最直接的挑战也可能是最困难的。要形式化地证明关于“从人类数据中学习”的命题首先必须对人类数据分布D给出一个严格的数学定义。这个定义需要刻画情境空间S所有可能输入视觉、语言、听觉、物理环境等的数学表示。行为空间B所有可能输出动作、语言回应、决策等的数学表示。联合概率分布P(s, b)描述特定情境s下产生行为b的似然。这需要编码所有的常识、物理规律、社会规范、个人目标等。目前我们对此仅有经验性的、局部的理解如在特定任务上的数据集远未达到一个完整、简洁、可用于复杂性分析的数学刻画。没有这个定义任何声称针对“人类行为分布”的复杂性结论都如同在沙地上建城堡。4.2 挑战二在数据子集中寻找“不可学习”的片段一种修补思路是退一步说也许整个人类行为分布是可学习的但其中存在某些“子集”或“方面”是计算不可学习的。例如人类能够执行某些复杂的、类似密码哈希函数的计算如果只考察这些特定任务上的输入-输出对学习预测其行为可能就和破解密码一样难。这个思路同样面临严峻问题“自然性”问题我们如何定义这个“有趣的”子集如果允许我们任意地、对抗性地选择数据子集例如只保留那些输出是随机数的数据对那么学习失败是平凡的但这没有意义。这个子集必须是人类行为中“自然”存在且“有意义”的部分。中间过程与外显知识人类在执行复杂算法时常常依赖外部工具纸笔、计算机或内部的口诀、分解步骤。如果训练数据包含了这些中间过程学习任务可能会变易。如果不包含那么要求模型从输入直接映射到最终输出可能本身就是一个不自然或不合理的设定就像要求猜出一个使用了一次性密钥加密的消息却不给密钥。代码的可得性对于许多人类能执行的算法世界上已经存在对应的Python代码或其他明确程序。如果训练数据中包含了这些代码本身那么学习任务可能就变成了简单的模式匹配或检索而非从零开始学习算法逻辑。4.3 挑战三归纳偏置的核心角色这是机器学习实践者最能共鸣的一点也是原论文完全忽略的关键维度。“没有免费的午餐”定理告诉我们在所有可能的问题上所有算法的平均表现是一样的。但对于任何一个特定的、结构化的实际问题总存在一些算法模型比另一些更有效。这种使模型倾向于某些解决方案的“偏好”就是归纳偏置。卷积神经网络在ImageNet上的成功绝非因为它是一个“万能学习机”而是因为它的归纳偏置局部连接、权重共享、平移不变性与自然图像的统计结构局部特征、层次化组合惊人地匹配。Transformer架构在自然语言处理上的统治地位也源于其自注意力机制对长程依赖和序列关系的强大建模能力这正好契合了语言的特性。因此要论证“AGI-by-Learning”不可行仅仅证明“一个没有偏置的、盲目的搜索算法会失败”是远远不够的。你必须证明对于人类行为数据分布D所对应的那个特定函数类不存在任何高效的归纳偏置能够使其被学习。这是一个强得多的论断。我们目前不仅没有这样的证明甚至缺乏如何形式化描述“适用于AGI的归纳偏置”的语言。历史上许多被认为困难的问题都在发现合适的归纳偏置或架构后得到解决。以物理规律学习为例人类从有限观察中归纳出了牛顿力学、相对论等这暗示我们的宇宙本身存在某种可归纳的规律性而人类心智或未来某种AI架构可能恰好内置了与之匹配的偏置。5. 从理论到实践的启示我们该如何思考AGI的可学习性这场争论虽然发生在理论层面但对我们的实际研究和工程方向有着深刻的启示。它告诫我们要避免陷入两种极端一种是盲目乐观认为只要有足够的数据和算力AGI就水到渠成另一种是盲目悲观基于有缺陷的理论证明就断言此路不通。5.1 重视数据分布的结构性先验任何严肃的AGI或复杂AI系统研究都必须对其训练数据的本质进行深思。人类产生的数据不是随机的它充满了冗余、模式、层次和因果关联。在构建数据集、设计任务时我们应该主动思考和利用这些结构性先验多模态与对齐人类经验天然是多模态视觉、听觉、语言、触觉且对齐的。利用这种跨模态的一致性作为监督信号是一种强大的结构性约束。时序性与因果性行为数据是嵌入在时间流和因果链中的。预测下一个动作或事件本身就隐含了对世界动态模型的学习。社会性与交互性大量人类数据产生于社会交互其中包含了合作、竞争、承诺、欺骗等复杂模式这些模式本身具有可学习的游戏论或逻辑结构。将这些结构性假设明确化而不是将其淹没在“任意分布”的笼统概念下是设计更高效学习算法的第一步。5.2 将归纳偏置的设计作为核心创新点与其追求一个“通用”的、无偏置的学习算法不如将研究重心转向如何为特定的、通向AGI的子问题设计强大的归纳偏置。这包括神经网络架构创新就像CNN之于图像Transformer之于序列我们需要发现更适合推理、规划、符号操作与子符号感知融合的新架构。学习范式与目标函数监督学习、强化学习、自监督学习、因果学习等各自引入了不同的偏置。如何为不同的认知能力组合或设计学习范式是关键问题。例如基于推理的强化学习、结合世界模型的自监督学习等。课程设计与环境交互让学习体在逐步复杂的任务或环境中学习本身就是一种强大的时间上和结构上的偏置模仿了人类和动物的发育学习过程。5.3 复杂性理论应作为指南针而非脚镣计算复杂性理论的价值在于它划出了清晰的边界告诉我们哪些问题在“最坏情况”下是异常困难的。这可以指导我们避开些可能本质上就无解的问题形式化方式或者去寻找问题的结构化特例。例如它告诉我们纯粹从随机输入-输出对中学习一个任意布尔电路是困难的但这并不妨碍我们在数据具有稀疏性、层次性时学习一个深度神经网络。对于AGI复杂性理论的作用应该是帮助我们识别出那些使学习变得容易或困难的数据分布特征和算法偏置而不是简单地给出一个“可行”或“不可行”的二元判决。我们需要的是更精细的理论能够区分“任意人类行为”和“具有特定统计规律的人类行为”并分析在不同强度的结构性假设下学习的复杂性如何变化。6. 总结在结构与偏置中寻找希望回顾这场争论[VRGA24]的尝试是有价值的它促使我们更严谨地思考AGI学习的理论边界。但其结论的缺陷也显而易见通过将一个高度结构化的学习问题从人类数据中学习归约到一个对分布几乎无约束的经典困难问题它得出了一个过于强大且与经验事实不符的否定性结论。Michael Guerzhoy的反驳精准地指出了其核心谬误并强调了两个在机器学习中至关重要、却在理论证明中常被忽略的要素真实世界数据分布的内在结构性以及学习算法归纳偏置的决定性作用。ImageNet的成功不是一个意外它是数据结构自然图像统计与算法偏置CNN架构完美契合的典范。通向AGI的学习之路注定不会是对“任意函数”的盲目搜索。它更像是在一个由宇宙物理规律、生物进化约束、社会文化环境共同塑造的、极其复杂的“函数空间”中利用我们精心设计的、带有某种“合理猜测”的搜索策略归纳偏置去寻找那个能解释和生成人类行为数据的特定函数。这条路是否最终能走通依然是一个开放的经验性问题。但现有的理论和实践都告诉我们以“任意分布”和“无偏置学习”为起点的复杂性证明并不能为这条路贴上“此路不通”的封条。真正的挑战和希望恰恰在于如何更深刻地理解“结构”并更巧妙地设计“偏置”。
