• 我的订阅
  • 科技

Yann LeCun说自回归要完,DeepMind论文证明自回归能实现通用计算

类别:科技 发布时间:2024-10-09 09:50:00 来源:机器之心Pro

毫无疑问,现在可说是自回归大型语言模型(LLM)的时代,我们看到技术迭代,我们也看到应用频出,但即便如此,也依然有人表示不看好。

唱衰自回归范式的最著名人物应当是 Yann LeCun 无疑了。他甚至还曾给出过一个相当大胆的判断:「从现在起 5 年内,没有哪个头脑正常的人会使用自回归模型。」详见机器之心报道《GPT-4 的研究路径没有前途?Yann LeCun 给自回归判了死刑》。

Yann LeCun 在演讲中表示自回归 LLM 会走向末路(doomed)

但现在,DeepMind 和阿尔伯塔大学的一篇论文却给出了截然相反的见解,其研究结果表明:无需外部干预或修改模型权重,基于 Transformer 的语言模型的自回归式解码就可以实现通用计算。

论文标题:Autoregressive Large Language Models are Computationally Universal 论文地址:https://arxiv.org/pdf/2410.03170

具体来说,这篇论文研究的核心问题是:当使用无界限的思维链时,大型语言模型是否可以支持通用计算?

近期很多研究都已经证明,可以通过外部记忆来增强 LLM,从而通过提示来实现对通用图灵机的模拟。但是,如果使用会将计算责任转移到语言模型之外的外部控制机制(尤其是正则表达式解析工具),则可能削弱这一结果。那无辅助的 LLM 是否能成为通用图灵机呢?这一问题仍待解答。

DeepMind 的这项研究给出了肯定答案:无辅助 LLM 确实可以模拟通用图灵机。不知道 Yann LeCun 会如何评价这一结果?

为了做到这一点,需要从一个更普适的视角来看待自回归解码,并且其要能处理任意长度的输入字符串。

该团队研究了自回归解码的一种自然泛化,其中在处理每个连续的上下文之后,输出的 token 都会被添加到序列末端 —— 只要输入能放入上下文窗口中,则该过程就会简化成标准的自回归解码。

不过,该团队得到这一结果的过程比较复杂,涉及到一步步地演算推进:

    首先,针对自回归解码,他们给出了一个更通用的视角,其可适用于长输入字符串的情况。 他们提出了一种扩展,可让语言模型实现 Lag 系统的一种受限形式。而 Lag 系统则是一种最早的通用计算模型的一个变体。 他们又接着证明 Lag 系统不仅能将内存组织为循环队列,还可以提供对内存访问的双向控制。 在介绍了图灵机的有限内存模拟的相关背景之后,他们又证明任何图灵机都可由上下文长度为 2 的受限 Lag 系统模拟。他们指出,尽管 Lag 系统的通用性早为人知,但他们给出的证明更加直接,并能为后续证明提供支持。 之后,他们将此归约技术应用于一种特定的通用图灵机 U_{15,2},得到了一个通用 Lag 系统,该系统由一组 2027 条产生式规则(production rule)定义,这些规则基于 262 个符号构成的字母表。 最后,他们开发了一条系统提示词,可让 gemini-1.5-pro-001 这个特定的 LLM 正确地在贪婪解码下应用那 2027 条规则中的每一条。基于此,该团队得出结论认为:扩展了自回归(贪婪)解码的 gemini-1.5-pro-001 可以精确模拟 U_{15,2} 对任何输入的执行情况,因此它是一台通用计算机。

下面我们将简要介绍一下其证明过程,并将重点关注最后一步,更多详情请参阅原论文。

自回归解码与 Lag 系统

语言模型表示的是在给定的输入字符串 s_1...s_n 上,下一个符号 s_{n+1} 的条件分布 p。任何此类模型都可以通过概率链式法则扩展为输出序列上的条件分布。

Yann LeCun说自回归要完,DeepMind论文证明自回归能实现通用计算

从 (1) 式也能看出,这个过程是自回归式的,也因此叫做自回归解码。算法 1 总结了上下文长度为 N 的语言模型的确定式自回归解码。

Yann LeCun说自回归要完,DeepMind论文证明自回归能实现通用计算

该团队给出的第一个关键观察是:大型语言模型的自回归解码可以通过 Lag 系统复现出来。Lag 系统最早由 1963 年的论文《Tag systems and Lag systems》提出,这是通用计算的一种最早的形式模型 Tag 系统的一个简单变体。

Lag 系统由一组有限的规则 x_1...x_N → y 组成,其中 N 是上下文的长度,x_1...x_N 表示要匹配的符号序列,y 表示相应的输出。

对于确定性 Lag 系统,每个模式 x_1...x_N 都是唯一的,因此 Lag 系统定义了一个部分函数 L,其可将模式 x_1...x_N 映射成相应的输出 y。Lag 系统的计算是通过对内存字符串进行操作来定义的 —— 在每次迭代中,都会有一条规则与内存字符串的前缀匹配,然后结果被附加到字符串后面,之后再删除第一个符号;参见算法 2。

Yann LeCun说自回归要完,DeepMind论文证明自回归能实现通用计算

图灵机

形式上看,图灵机 T 由一个元组 T = (Q, Γ, b, q_0, H, f) 组成,其中 Q 是一组有限的状态,Γ 是一组有限的磁带符号,b ∈ Γ 是唯一的「空白」符号,q_0 ∈ Q 是唯一的起始状态,H ⊆ Q×Γ 是一组表示终止的配对的 (状态,符号),f : Q×Γ → Γ × Q × {−1, +1} 是一组有限的转换规则,用于指定该图灵机在每个计算周期中的操作。

该图灵机可以访问单向无界的存储磁带,因此可以通过自然数 i ∈ N (i > 0) 来索引存储位置,这样 i = 1 处有一个最左边的存储位置,但没有最右边的存储位置

图灵机的执行定义如下。

磁带用一个由有限数量的非空白符号表示的输入进行初始化,其它所有位置均为空白,T 从状态 q_0 开始,磁带头从指定位置 i_0 开始(默认 i_0 = 1)。

在每个计算周期开始时,T 处于某个状态 q ∈ Q,磁带头位于某个位置 i > 0,当前正在从磁带读取符号 γ ∈ Γ。组合 (q, γ) 确定更新 f (q, γ) → (γ′ , q′ , D),指定符号 γ′ 写入当前内存位置 i,机器状态 q 更新为 q′ ,磁带头移动到 i + D(即根据 D 的符号向左或向右一步)。假设机器永远不会移出磁带的左端。计算循环重复进行,直到机器遇到配置 (q, γ) ∈ H。不停机计算是可能的。

为便于后续证明,了解可以如何仅使用有限内存来模拟图灵机的计算会很有用。算法 3 描述了一种标准模拟策略,其中使用新的分隔符 # 来标记访问内存的末尾,从而可在必要时分配额外的空间。这使得可以模拟潜在的无限内存,而无需分配无限存储空间。

Yann LeCun说自回归要完,DeepMind论文证明自回归能实现通用计算

用 Lag 系统模拟图灵机

该团队证明,任意图灵机都可通过一个受限 (2, 2)-Lag 系统模拟。这是他们得到的首个主要结果。该证明还意味着任何线性有界自动机都可以用一个受限 (2, 2)-Lag 系统模拟。

之前研究者已经证明 Lag 系统具有计算通用性,但原始的证明依赖于一种少有人知形式的寄存器机(register machine )的简化。这里并不方便利用这个证明。于是,该团队开发了一种将图灵机直接简化为 Lag 系统的方法,从而能在后续论证中利用小型通用图灵机。

给定一个图灵机 T = (Q, Γ, b, q_0, H, f),可以这样构建其对应的 Lag 系统:Lag 系统将使用字母表

其中 # 是分隔符符号,Q 是来自 T 的有限状态集(使得空白符号不属于 Q),Σ_left 和 Σ_right 是位置控制字母表。

也就是说,Lag 系统中的每个符号都是一个三元组,由内存符号、状态符号和位置控制符号组成。

该团队为该 Lag 系统设计了一些规则,使得其内存字符串会跟踪图灵机模拟算法 3 中局部变量的状态。

具体而言,在每次迭代 k ∈ N 开始时,算法 3 维护一组局部变量:m、n、q 和 i,其中 m 是一个表示当前磁带内容的数组、n 是 m 的当前长度、q 是 T 的控制器的当前状态,i 是磁带头的当前位置。

为了镜像这些局部变量的值,Lag 系统将维护一个内存字符串 s,使得序列 m_1...m_{n−1}# 对应于 m,s 的长度为 n,q 对应于相同的控制器状态,图灵机磁带头的位置 i 由三元组第二个位置中唯一的非空白状态符号 q 的位置表示。

具体来说,对于给定的图灵机 T,通过算法 4 确定的规则集定义相应的滞后系统 L。

这项研究结果表明:基于算法 4 得到的 Lag 系统 L,算法 2 可模拟给定图灵机 T 在任意输入 γ_1...γ_{n−1} 上执行算法 3。

一个通用的 Lag 系统

由于论文的主要目标是证明当前的语言模型在扩展的自回归解码下是计算上通用的,最直接的证明方法就是看看这个模型是否能够模拟一个已知的、计算上通用的系统。

从本质上来讲,任何关于计算机通用性的讨论,都要回到大名鼎鼎的「邱奇 - 图灵」论题。邱奇和图灵都有过这样的猜想:所有计算机制都可以由图灵机来表达。图灵提出了通用图灵机的概念,它能够模拟任何计算过程。

鉴于语言模型的自回归解码与 Lag 系统在更新时具有类似的机制,因此,很自然地想要通过一个通用的 Lag 系统来证明其通用性。定理 7 为构建这样一个通用 Lag 系统提供了明确的路径。

使用语言模型模拟通用 Lag 系统

最后,要证明现有的 LLM 可以模拟通用 Lag 系统 L (U_{15,2}) 在任意输入字符串上的执行情况。该团队的做法是开发一个特定的提示词,以让扩展过的自回归(贪婪)编码模仿 L (U_{15,2}) 的行为。

他们开发了一个提示策略,其中包含两个组件:系统提示词和滑动窗口提示词。其中系统提示词提供了完整的规则集,而滑动窗口提示词会在输入序列中附加下一个符号对(4 个 token)。

每次迭代过程中,下一个符号对都会附加到系统提示词中并作为输入提供给语言模型;然后,语言模型的输出(2 或 4 个 token)会附加到序列的末尾,如图 3 所示。

为了确保系统是确定性的,他们将温度值设置为 0,并固定了定义语言模型行为的所有随机种子。

为了允许语言模型为每个上下文窗口输出可变数量的 token ,他们采用了扩展自回归解码,其中除了 262 个 token 对的基本字母表之外,还使用了一个隐式的隐含终止 token h。

最后,为了验证扩展自回归(贪婪)解码是否确实能够复制 L (U_{15,2}) 的行为,他们挑选了一个特定的 LLM:gemini-1.5-pro-001。几番实验之后,他们开发了一个系统提示词,可让模型正确执行那 2027 条规则中的每一条。他们将这个系统提示词称为 S_gemini。之后他们得出了最终结论。

从这个定理出发,根据「邱奇 - 图灵」定理,可以得出结论:在扩展自回归(贪婪)解码条件下,gemini-1.5-pro-001 是一台通用计算机。重要的是,实现这一结果不需要引入任何扩展自回归解码之外的计算机制。

Yann LeCun 演讲《From Machine Learning to Autonomous Intelligence》,https://www.youtube.com/watch?v=mViTAXCg1xQ

以上内容为资讯信息快照,由td.fyun.cc爬虫进行采集并收录,本站未对信息做任何修改,信息内容不代表本站立场。

快照生成时间:2024-10-09 11:45:09

本站信息快照查询为非营利公共服务,如有侵权请联系我们进行删除。

信息原文地址:

地球进入崭新的一天(序与跋)
...会有意识吗?如果让我来回答,我可能要从“意识能够被图灵机计算吗”这一问题开始。1967年,科学家希拉里·普特南提出了心灵的计算理论,认为心灵是一个由大脑神经活动实现的计算系统
2025-03-21 06:10:00
以图灵机为师:通过微调训练让大语言模型懂执行计算过程
... LLM 的可组装算术执行框架 (CAEF),使 LLM 能够通过模仿图灵机的方式来执行算术,从而理解计算逻辑。此外
2024-10-21 09:54:00
揭秘注意力机制真正起源!10年前3项研究几乎同时独立提出
...的实验室中“可微且数据依赖的加权平均”的发明与神经图灵机、Memory Networks以及90年代(甚至 70 年代
2024-12-05 09:44:00
计算机科学的高塔
...。在当时,现在意义下的“计算机”还不存在。所谓的“图灵机”,在当时更像是数学家和逻辑学家们的一种纯粹的“智力游戏”。1939年,维特根斯坦在剑桥开设了一门名为《数学基础》的课
2024-05-23 13:37:00
《中国人工智能简史》:数学家翻开了中国人工智能研究的第一页
...年证明和计算限制的结果重新进行了论述,并用现在叫作图灵机的简单形式的抽象装置代替了哥德尔的以通用算术为基础的形式语言,证明了一切可计算过程都可以用图灵机模拟。这也是计算机科学
2023-09-04 16:58:00
华中科技大学霍普克罗夫特计算科学研究中心启动
...arra院士分别以“Introduction to the Conscious Turing Machine(意识图灵机简介)”和“Where We Are Today an
2023-02-13 17:41:00
在严肃学术讨论里玩烂梗,科学家也是认真的
...包括Pascal在内的多种编程语言的主设计师,因此获1984年图灵奖,曾在1995年提出吐槽软件愈发臃肿的Wirth定律,即软件变慢的速度永远超过硬件变快的速度。高德纳(右)
2024-12-04 09:36:00
中国科学院计算所孙晓明:量子计算具有指数加速潜力,算力或强于AI
...就提出了这样的构想。费曼认为,基于经典物理学的经典图灵机不能完美模拟任何物理意义上可实现的系统,沿着这一思想,多伊奇提出了基于量子力学的通用计算机模型,它的潜在计算能力远超经
2023-10-17 15:43:00
搭建交流平台 推动技术创新 “认知世界 智创未来”主题论坛在沪举办
...主题进行演讲,Manuel Blum教授为大家带来了关于他在意识图灵机领域的最新研究成果,复旦大学计算机专业博士王晓梅分享了关于“多模态大模型在行业中的应用”的主题演讲。发布
2024-07-06 08:26:00
更多关于科技的资讯:
2025新能源汽车零部件交易会丨新闻链接:产业巨头齐聚十堰 共话车载视听新场景
十堰广电讯(全媒体记者 翁红 张欣)车载视听不仅承载着信息传播、娱乐休闲的基本功能,也日益成为重要的宣传舆论阵地,给广大人民群众的精神文化生活带来了全新体验
2025-09-20 20:42:00
十堰广电讯(全媒体记者 陈林 通讯员 刘爱理)9月19日下午,2025新能源汽车零部件交易会汽车产业链出海对接会举行。会上
2025-09-20 20:42:00
了不起的河南制造丨牧原集团推出智能养猪方案 让“二师兄”过上“芯”生活
大河网讯 无针注射器、智能环控器、智能测定仪、智能机器人、猪群咳嗽管家……9月20日,2025世界制造业大会在安徽省合肥市召开
2025-09-20 18:17:00
近日,被认为是中国新式茶饮第一股的奈雪发布了中期业绩报告,数据显示公司上半年实现营收21.78亿元,较去年同期下降14
2025-09-20 18:05:00
展现数字化发展硬实力 济南能源集团亮相2025国际数字能源展
大众网记者 赵港宁 济南报道9月18日,以“深AI能源 数创未来”为主题的2025国际数字能源展在深圳举行。济南能源集团所属神思电子
2025-09-20 11:22:00
量子位「MEET2026智能未来大会」启动!
我们正迈入一个由人工智能重塑一切的新时代。智能技术已经深刻渗透进生产和生活,跨越了软件、硬件、机器人等不同形态,从工具发展为能深度理解人类需求的智能伙伴
2025-09-20 05:23:00
纵览·9张|空间魔术师
壹 随着网购的便利化和生活节奏的加快,许多人在购物的同时,却忽视了归纳和“断舍离”。于是整理收纳师进入了大家视野,成为走俏的新职业
2025-09-20 08:02:00
iPhone17系列正式发售,多地门店排起长队,有黄牛加价500元收购Max 256G版本
北京时间9月19日,iPhone 17系列正式发售,线上抢购到首批货源的用户将陆续收到新机,官方零售店也于8:00提前开门营业供预约取货用户取货
2025-09-19 12:06:00
在杭州看见创新未来 第四届数贸会全景前瞻
第四届全球数字贸易博览会(以下简称“数贸会”)将于2025年9月25日至29日在杭州大会展中心举行。作为我国唯一以数字贸易为主题的国家级
2025-09-19 14:13:00
走向国际,INGS英树三度荣获IFSCC青睐
2025年9月15日至18日,第35届IFSCC国际化妆品科学大会以“THE FUTURE IS SCIENCE”为主题于法国戛纳盛大启幕
2025-09-19 14:16:00
国网高密市供电公司:物资仓库里的“绣花功夫”
大众网记者 宋学敏 通讯员 赵雯雯 贾聚光 潍坊报道9月19日,走进国网高密市供电公司物资供应分中心的物资仓库,整齐的货架
2025-09-19 14:23:00
研发投入年增超40%!Coosea酷赛智能凭什么敢在创新上“下血本”?
在智能制造与AI设备行业加速迭代的浪潮中,研发实力已成企业核心竞争力的关键。近日,Coosea酷赛智能披露的研发投入数据引发行业关注——其研发投入年增超40%
2025-09-19 14:51:00
喜茶「超级植物茶」上新一周年,差异化引领新茶饮产品趋势
9月19日,喜茶「超级植物茶」迎来上新一周年。据官方数据显示,「超级植物茶」全系列产品已售出超1亿杯,喜茶坚持采用新鲜的羽衣甘蓝每日现榨
2025-09-19 15:01:00
京东运动户外品类日开启 运动、健身、户外出游全场景好物立减12%
秋高气爽迎国庆,正是走出家门、拥抱自然的好时机。9月19日晚8点至20日,京东运动户外品类日正式开启,携手阿迪达斯、北面
2025-09-19 15:08:00
华为云杨友桂:数智化转型从来不是 \
9月19日,在华为全联接大会2025上,华为高级副总裁、华为云全球Marketing与销售服务总裁杨友桂介绍了华为云如何通过四大关键竞争力
2025-09-19 15:24:00