GPT-5.6和Fable联手，解决了一道悬了25年的数学难题

克雷西 发自 凹非寺

量子位 | 公众号

GPT - 5.6与之携手合作的Fable 5, 将一道悬念搁置长达25年之久的数学难题成功予以解决了。

担任微软研究院首席研究员的那个人, 证实了一种算法, 该算法属于多项式时间算法类别, 它具备这样的能力, 即能够让MIMO检测极其精准地恰好达到最大似然阈值。

作者表示，这个过程花了他整整七天。

MIMO检测, 属于无线通信领域里的一个经典问题, 它要求接收端, 要从被噪声搅乱的信号当中, 将发送端原本发出的信息, 完整地还原出来。

在统计方面, 这样的操作目前已能够达成, 然而以往所采用的办法, 乃是进行穷举搜索, 其所消耗的时间呈现指数级增长。

所以问题就变成，能不能不通过穷举，利用快速算法实现还原。

在2001年的时候, 有人觉得好像是找到了一个突破口, 然而呢, 到了2005年, 这条原本被认为找到突破口的路, 又被Jaldén和证实是走不通的了。

之后, 学界又陆陆续续尝试了半正定松弛、比特翻转局部搜索、AMP、统计物理方法这些方法, 然而最终非常贴近的结果也仅仅只能停留在比起理论门槛高出一倍的位置上, 是有标点符号的。

25年，一波又一波学者轮番上阵，但谁都没能啃下来。

25年来，只能靠穷举

MIMO检测，是无线通信里的一个基础问题。

发送端传输N个比特经由一个N×N的信道发出, 该信道会将这些比特进行混合, 并且还会增添噪声。

接收端那儿仅有一份被弄乱了的信号, 得把发送端一开始发出的N个比特, 一个不少地给找回来。

理论之中存在着一种万无差错的办法, 它被称作最大似然检测, 意思便是将全部有可能的比特组合逐一进行计算, 从中寻觅出与接收到的信号最为契合匹配的那一个。

换一种方式来讲, 在你愿意等待的状况下, 这种方式必然能够找寻得到正确的答案, 就像是涉及到N个比特所意味着的2的N次方种组合, 只要N稍微增大一些, 要是进行穷举工作, 那计算起来就会达到那种漫长到仿佛要等到天荒地老的地步！

1989年, Verdú证实了这类问题于最坏情形下是NP - hard的, 亦即不论采取何种算法, 终归存在某些输入会致使计算量呈指数级激增。

但是, 所谓的「最坏情况」, 指的是那一种数学上经过有目的的精心构造, 专门用来给算法制造难题的信道矩阵。

现实当中的无线信道, 并非是有人特意去构造的, 它所出现的一次次衰减, 还有一次次噪声, 都是随机出现的, 并不会去挑选那些最难以计算的状况, 从而去为难接收端。

于是学界从2000年代初开始问一个更具体的问题——

倘若信道乃随即形成的, 只要从统计层面存有恢复原本比特的可能性, 那么是否必定能够寻觅到一个无需穷举的算法呢?

后来进行的研究, 给出了一条精准的分界线, 在这种情况下, 当信噪比达到2logN时，发送的那些比特, 能够被完全恢复的概率, 就会趋近于1。

低过这条线, 就连最大似然检测自身都会开始出现错谬, 这条分界线所以被称作最大似然阈值。

那问题, 就这么着变得具体起来了, 具体成了这么一种情况, 可不可以去搞出一个能够跑得较快的算法, 精准地命中那个最大似然阈值?

2001年，Babak 和Haris 以为找到了答案。

他们分析的是一种叫球形译码（ ）的算法。

这种算法, 会先于接收信号的周边, 划出一个“球”, 仅在包含于球内的候选当中展开搜索, 而处于球外的部分, 则直接予以跳过, 依靠这一举措, 来压缩搜索的范围。

通过对这个算法进行推导, 得出了期望复杂度公式, 其结果看上去呈现出多项式时间的特征。

如果这个结论成立，这道题基本就解决了。

可在二零零五年, Jaldén以及Björn将这一结论给推翻掉了。

他们证实, 于任意固定的信噪比状况下, 球形译码的期望复杂度实际上是呈指数级的, 并非是多项式的。

因要将发送的信号以不趋于零的概率包进「球」里, 所以球的半径得随问题规模一同变大, 既然球变大了, 那么球内要搜索的候选数量也就跟着呈指数级增长。

当球形译码这条路无法通行之后, 学界转而朝向了各类近似方法, 诸如半正定松弛、比特翻转局部搜索、AMP（）以及统计物理里的方法。

结果, 每一种都能够给出漂亮的分析, 然而, 没有一种被证实可以精确匹配2logN这条阈值。

2020年, 有一种方法，它把离散问题放宽成连续优化问题来解, 这种方法叫box , 它拿到了当时最好的严格证明结果, 它能在信噪比达到4logN时做到精确恢复, 不过它的复杂度依然是理论门槛的两倍。

过去了二十五年, 在统计方面所谓的“能恢复”, 与使用那般快速算法所宣称的“能恢复”当中, 始终横亘着这样一条鸿沟。

上周，这条鸿沟被填平了。

GPT - 5.6、 Fable 5一起证明了, 存在一种算法, 它只有两步, 属于简单算法, 在信噪比等于2logN的情况下, 能够精确恢复全部比特, 并且是在多项式时间内做到的, 而该算法只需要O(N³)次运算。

而且这篇论文证明的是一个双向结果。

一部分表明, 当信噪比处于等于2logN的状况下, 信号能够被精准恢复；另一部分进而证实, 只要信噪比稍微低于2logN这个最大似然阈值, 就连最大似然检测这种「笨办法」也会开始出现失败的情况。

GPT-5.6和Fable 5联手证明

找来GPT - 5.6去尝试这道题目, 同时找来Fable 5去尝试这道题, 两个模型迅速地各自给出了自身的证明思路, 然而紧接着的打磨进程却是波折不断, 状况连连, 充满了各种起伏变化之处。

GPT - 5.6的路径运用了一种称作AMP的算法, 这是一类工具 , 是一直都没能彻底理解其分析方法的那种。

“Fable 5”给出的路径不一样, 采用的是「符号LMMSE与贪心逐位翻转」, 这是一个在业内实际被运用、然而却从来没有被严格证实过的陈旧算法。

两种路径, 都分别给出了完备的证明, 宣称能够在信噪比值为2logN时精准恢复。

最终做出的选择是Fable所给出的那条路, 而后让GPT着手去接手检查, 并且去修补里面存在的漏洞。

GPT 将漏洞修复了, 然而修复之后的证明呈现为一堵形如「符号墙」的东西, 变量指向了变量, 被指向的变量又指向了更多的变量, 并且充斥着令人看不懂的矩阵分析工具。

随后的几日里, 他再三促使两个模型, 去相互简化对方所给出的论证, 唯一存在的底线便是, 无论怎样进行简化, 最终都得将2logN这个门槛给保住。

除此之外，只要他自己能看懂，怎么改都行。

那个他, 居然还拒绝了使用Lean来进行形式化验证, 而其中的原因也是相当抓马的, 这是因为呀……他竟然不懂。

Lean乃是一种具备让计算机自行检查数学证明是否得以成立功能的工具, 只是若要运用它, 那就必须先将证明转化成Lean能够读懂的形式语言。

从事这道翻译工作, 其自身就存在出错的可能性, 然而, 要是不懂得Lean, 那么就没有办法去检查翻译到底正不正确。

总之折腾了一周后，他终于拿到了一份可以逐行手算核对的证明。

拆开看，这个算法只有两个核心步骤。

第一步，叫LMMSE取整。

LMMSE（即mean error, 也就是线性最小均方误差估计）属于信号处理范畴内、一种被认定的、标准意义上用于估计所作处理的方法, 首先会给出一个并非呈现整数特性、而是连续进行取值相关情况的、比较粗略的猜测预估, 随后会依照正负号方面涉及的情况, 将每一个坐标进行取整的操作, 使其取值成为+1或者-1 的状态。

这一步并非要精准猜中每一个比特, 论文所证明的是, 对于取整之后出现的结果与实际发送的比特而言, 在它们之间存在一种情况, 即汉明距离（也就是两个长度相等的比特串之间不同的位数）仅仅只有o(N)。

也就是说，随着N变大，猜错的比特数占总数的比例会趋近于零。

第二步，叫贪心逐位翻转。

首先以第一步给出的猜测开端, 接着每一轮都要对所有N个比特展开检查, 从中寻觅能使代价函数（其为衡量当前猜测与接收信号匹配程度的某个数值, 数值越小表明越匹配）下降幅度最大的那一位进行翻转, 随后翻转该位, 之后再重复这一流程。

存在这样一个问题, 那便是眼下这般的贪心搜索过程, 究竟是依托着何种理由, 能够顺利寻觅达到正确答案, 而并非徘徊于中途某个错误之处停滞不前呢?

为了回答这个问题，论文证明了两件事。

第一, 于猜测起点周边的一个范畴内, 每一个尚未猜对的点, 皆至少存有一位翻转可使代价函数严格降低, 并且下降的幅度存在一个不向零趋近的下限, 不会随N增大而消逝。

这意味着贪心搜索不会卡死不动，永远能找到继续往下走的一步。

第二, 代价函数会变大, 其因汉明距离增大而增大, 此即猜错的比特数之增加所导致的。

这造就了一道天然的护栏, 搜索路径即便在中途的某一个步骤猜错的比特数量姑且增多, 代价函数也返回不到起始点, 无法穿过这道护栏跑到猜测范围之外。

把这两件事放置到一起去看待, 每一步最少能够降低多少代价, 用这个代价去除以起点距离最优解总共相差的代价, 如此便得到了贪心搜索的算法复杂度, 论文所计算出来的答案是O(NlogN)步。

贪心搜索存在一条停止规则, 这条规则是, 当找不到任何能够让代价下降的翻转时, 那么就停下来。

在前边证实了, 处于护栏里面的每一个猜错的点, 都还有着至少一位进行翻转就能够让代价向下滑落的这样情况。

也就是说, 只要处于尚未猜对的状态, 算法必然能够找出接下来要去翻动哪一位, 并且不会停止。

当真正猜对之后, 每一次进行翻转, 代价都会朝着更差的方向发展, 直至此时, 不存在任何能够起到改进作用的翻转可供选择, 算法于是就会停止运行。

贪心搜索唯一能停下的地方，就是真实发送的那个比特串。

算法最终会仅仅停留在实际发送的比特串之上, 如此一来, 证明便宣告完成了。其表明, 这一整个论证流程, 自身已然从起始至末尾核验过一回了。

作者简介

目前, 身为微软研究院的首席研究员, 并且, 还是威斯康星大学麦迪逊分校电子与计算机工程系的副教授。

他早年的研究方向是信息论和编码理论。

2009年的时候, 他处于博士一年级这一阶段, 当时他写下了第一篇论文, 在接下来的一年发表了, 其合作者是导师Alex。

那篇论文尝试采用一种叫MCMC的方法来解决MIMO检测这道题, MCMC也就是马尔可夫链蒙特卡洛, 是一种靠随机采样去慢慢逼近答案的计算方法，然而其努力并没有收获成功这个结果。

这次被GPT - 5.6以及Fable 5证实拿下的, 恰好是同一道题, 是17年前那道曾使他陷入困境的题, 而这次是被他自己解开的。

参考链接：