奇妙而诡异的复型方法

    意大利学者帕里西为2021年三位诺贝尔物理奖的获奖人之一,他的最著名贡献是于上世纪80年代末和梅查德和维拉索罗一起发展的复型方法(replica method)。自然界中有很多复杂随机大系统,由无数的随机个体相互作用而构成,我们感兴趣的是复杂大系统的宏观作用和特性。比如,一杯水由无数的水分子构成,每个水分子在室温下做随机的布朗运动,相互作用,对水杯壁产生压力,这个压力就是水分子的宏观作用结果,是一个非随机的量。那么,如何通过每个个体的随机特性,推导出复杂大系统的宏观特性呢?复型方法正是这样一个数学方法。

    自从被发现以来,复型方法被广泛地运用于物理,材料,编码,网络,人工神经网,解决了一系列不同领域里复杂大系统的宏观定性分析问题。然而,复型方法是一个奇妙而诡异、还没有被数学证明正确的方法,因此也常常被称为复型诡计(replica trick)。在复型方法中,先构成N个相同的系统,形成系统配分函数的N次幂期望值。诡异的是,复型方法要对这个函数关于N求导数,然后让N连续的趋近0。但是N是一个自然整数,关于N求导数和要求N连续的趋近0,在数学上都是不成立的。尽管如此,在所有的对宏观特性已知的复杂大系统的分析中,复型方法的结果都和已知的宏观结果一致,这说明了复型方法的正确性和实用性。

    帕里西获得今年诺贝尔物理学奖,也是对复型方法的奖励和肯定。这让我想起曾经使用复型方法分析局域最大似然检测器的经历,体会到这一方法的奇妙、诡异、和强大。

    1990年代中期,无线通信技术正从2G(第二代)向3G(第三代)发展,提出了码分多用户(CDMA)技术。CDMA技术要求多个用户共用一个宽频信道,每个用户携带一个特定的编码条,用于在接收端区分各个用户的信息比特。要充分利用CDMA的潜在通信能力,接收端对每个用户比特的检测是一个关键技术,这要求发展功能强大的检测器或算法,是当时的一个热门研究问题。普林斯顿大学教授韦尔杜的开创性研究表明,全局最大似然(全局最优)检测器的性能要比当时使用的匹配检测器的性能高几个数量级,指出了CDMA潜在的巨大通信能力。然而,最优检测器是NP难度的,属于一类计算复杂度最高的算法,如果有N个用户,最优检测器的复杂度是2的N次方,其无法在实际通信系统中使用,因此需要发展各种难度低、性能弱的检测器。我当时在明尼苏达大学读博士,对这个问题产生了强烈的兴趣。当时正好,我刚刚为霍普菲尔德人工神经网络发展了一个稳定的算法家族,用于解离散的最小二乘问题。于是将这个算法家族用于CDMA检测,发展出了似然向上搜索算法家族,这其中,包含一个局域最大似然(局域最优)算法家族。局域最优解一般有很多个,全局最优解是这些局域最优解中的一个。通常,局域最优解的性能远远比全局最优解差,但是局域最优解的复杂度是线性的,即N乘一个常数。为了测试局域最优检测器的性能,通过模拟实验,可以获得误码率的估值。为了获得一个数学解,采用高斯近似方法,我获得了一个不动点方程,误码率是这个不动点方程的解。奇怪的是,通过分析这个不动点方程,发现竟然存在着两个不同的误码率解。也就是说,在同样的条件下,误码率竟然是一个多值函数,当时无法理解这一现象。1990年代,个人计算机的计算能力差,内存小,做模拟实验时,用户数最多只有几十个,结果显示局域最优解的误码率不低,因此没有显示出这个局域最大似然算法家族的巨大优点。而且,数学解和模拟解有差距,不知其中的原因,因此没有将数学解在学术期刊发表。博士毕业,做博士后,研究转了方向,生活漂泊,只好暂时放下了这个算法的研究。然而,对于这个算法家族的一些疑惑,一直萦绕在我的脑海里。

    2002年,日本学者田中采用复型方法分析了全局最优算法的误码率,获得了巨大的成功。全局最优算法是一个穷尽搜索算法,很难获得误码率的解析解。然而,当采用随机码条,用户数N趋向无穷大,即形成一个复杂随机大系统的时候,用复型方法导出了一组数学方程,误码率就是这组方程的解。看到这一结果,我立即想到用复型方法分析我的局域最优检测器家族的误码率。然而,要了解并运用复型方法分析局域最优检测器家族的误码率可不是一件容易的事情,这其中,也研读了帕里西等人写的《Spin Glass Theory and Beyond》和其他书籍及文章。和田中分析的全局最优解不同,局域最优解由一个不动点方程约束,如何用复型方法来分析它,真的是想破了脑壳。反反复复,复复反反,终于,获得了一组不动点方程,局域最优解的误码率就是这组方程的解。奇妙的是,第一,局部最优解的误码率竟然是全局最优解的一个分支,也就是说,虽然只有线性复杂度,在用户数很大的情况下,局部最优解的性能达到了全局最优解的性能。第二,当用户数趋向无穷大时,大量的局部最优解都消失了,最终只剩下一个全局最优解,即局部最优解就是全局最优解。第三,将这个方程组化简为一个不动点方程,它竟然就是我十年前用高斯近似方法获得的不动点方程,这太奇妙了。也就是说,十年前获得的不动点方程描述的,实际上是复杂随机大系统下局域解的误码率。这也就解释了,为什么它有两个解。这就相当于,雨滴在云端遇到零下气流后形成的雪花会有不同的形状,这正是复杂随机大系统的特性之一。第四,因为个人计算机的计算能力和内存都大大提高了,可以做大用户数的模拟实验,结果是,当用户数超过200的时候,局域最优解的误码率的确突然降低,性能逼近不动点方程所描述的理论结果。萦绕在大脑中多年的疑惑终于获得解答。这些结果最终在学术期刊上发表。

    自然的法则蕴藏在一些数学公式中,揭示出自然的美妙。复型方法就像自然界留给人类的一个奇妙而诡异的金钥匙,通过这把金钥匙,人类可以打开自然界中各种复杂随机大系统的大门,获得奇妙的数学公式,观察到其中的神奇和美妙。