谷歌造出拉马努金机：几毫秒求解数学常数，无需任何先验信息

鱼羊 晓查 2019-07-06 13:02:13 来源：量子位

驭洋 晓查 发自 凹非寺

量子位 出品 | 公众号 QbitAI

3.1415926……

π和e这样的基本常数在科学领域中无处不在，但计算它们的高精度近似值往往令人头大。如今，机器学习或许能帮上大忙。

能算近似值，还能在数学计算中快速找出精准规律，机器学习表示 I can I up。

这就是以色列理工学院和谷歌一起开发的拉马努金机器（Ramanujan Machine）。

拉马努金，这位英年早逝的天才数学家，总能发现一些让世人惊叹的数学公式。由他发现的圆周率π的计算公式，只需计算第一项就能突破普通计算器的最高精度。

拉马努金机器也有类似的奇效。面对各种奇怪复杂的数学常数，只要找出它的连分数表示，只需计算十几步、几毫秒就能快速收敛，得到精准答案。而且算法已经开源！

然而让拉马努金玩出花来的连分数可不是简简单单就能被找出来的，几个世纪以来，与基本常数相关的新数学公式十分少见，毕竟奠基人是欧拉、高斯这样堪称“变态”的天才，想要继承他们的事业，不仅要有丰富的知识积累，还要有敏锐的数学直觉。

而机器学习却表示，无需先验信息，我也能快速get新公式。

什么是连分数

优美的欧拉公式将e和π两个数学常数联系起来，但你知道这两个无理数是怎么算出来的吗？

你可以用泰勒展开的方法计算：

实际上还有另一种计算方法，那就是连分数，它的分母无限延伸下去，结果就会越来越接近：

黄金分割比φ=0.618……有着几乎最简单的连分数形式，一组全是1表示的数：

其他的数学尝试，包括自然对数的底e、圆周率π，还有黎曼猜想中黎曼Zeta函数ζ(3)的值。都可以用连分数来表示。

△π的连分数表示

任意实数都可以用连分数来表示。

连分数有何用

你如果认为连分数是数学家们的奇技淫巧，那就大错特错了，发现连分数的某个表达式有着实际的用途。

各种数学常数的连分数是存在却不是唯一的，如果找到一个合适的连分数，那么计算结果的收敛速度会非常快，大大减少计算机的运算量。

但是找到连分数里一组特殊的数却并不是一件容易的事情，否则这套算法也不会叫做拉马努金机器了。

△ 拉马努金发现的连分数，φ是黄金分割比

发现连分数里那些特殊整数的规律，需要有长年数学知识的积累，更要有易于常人的直觉。

现在有了拉马努金机器，可以用电脑代替人的思维去寻找特殊的连分数了。

有Reddit网友把拉马努金机器找到的公式写成Python代码，各算了一遍e和π，分别用了15步和18步的迭代，就能达到float 64的精度，也就是小数点后15位。

拉马努金机器不仅能算数学常数，如李维常数、辛钦常数，还能计算一些物理常数，如天文学计算中的拉普拉斯极限等等。

作者下一步的目标用它来做数学证明，发现数学常数的固有属性。比如e和π，我们都已经能证明他们是无理数而且是超越数，其他常数是不是无理数呢？以后或许可以用计算机来证明了。

算法介绍

论文当中提到了两种算法。

第一种是中间相遇法（The Meet-In-The Middle）。这个算法的思路非常简单：

给定一个常数c（如 c=π），根据公式：

f1(x)=x，f2(x)=1/x ，……；GCF(α，β)代表 an=α(n)，bn=β(n)的连分数；α，β，γ，δ为整数多项式。

先计算出公式右边一个精度较低的值，并将其存入哈希表，然后通过枚举的方法来使公式左右两边的值相匹配，匹配上的值称为“hits”，随后增加hits的精度并重新比较，重复这个过程直到hits达到指定精度。这个最终的结果就提供了一个新的连分数。

有些hits值会产生误报，针对这一点，研究人员提出通过计算任意精度的有理函数来减少误报。

在这个算法当中，由于公式右边的计算成本更高，所以将它的值以哈希表来存储，以空间换时间。这个哈希表也可以保存下来重新服务于公式左边的枚举，从而大大减少未来的枚举时间。

MITM-RF算法不需要任何关于基本常数的先验信息，不过有许多基本常数的结构是可以推断出来的，以此作为MITM-RF的先验信息可以有效降低空间复杂度和计算复杂度。

不过，MITM-RF方法还是存在扩展性不佳的问题，于是研究者使用到了机器学习当中常用的梯度下降方法，他们称其为Descent&Repel方法。

我们可以把优化问题描述成这个样子：

这里的最小值不是零维度点，而是（d-1）维的流形，其中d是给定的单一约束所预期的优化变量的数量。

研究者还观察到所有的最小值都是全局的，并且它们的误差为0，也就是说所有的梯度下降过程最后都会得到L=0的解。

这个优化问题起始于一个大的点的集合，在示例当中，所有初始条件被放置在一条线上。对每一个点迭代执行梯度下降，然后强制所有的点通过库仑排斥彼此排斥。通过梯度下降步骤保证算法朝向整数格并趋向最小曲线，最后仅返回位于整数格上的解。

网友的质疑

有Reddit网友认为，连分数通过等效变换可以获得无限多种组合这篇论文不是机器学习，它只是一种自动化查找新表达式的算法。

网友虽然反对将作者的结果称为机器学习，但它仍然是一种吸引人的算法，最有趣的是使用梯度下降优化整数分数，以前从未见过有人这么用过，因此是有创新性的。

对此，作者表示，是不是机器学习取决于你如何定义，文章中寻找新数学公式的算法是基于梯度下降的模型，因此可以看做是机器学习，今后他还将展示更直接地利用机器学习的其他结果。

至于发现新的连分数表达式，已经有前人的研究成果可供查询，而作者用拉马努金机器发现的很多结果已经被人类手工发现了。况且只要掌握了连分数的知识，就能发现各种表达式变体。

但这不正是拉马努金机器的魅力所在吗？如果你没有过人的数学头脑，就把特殊技巧交给计算机来做吧！

传送门

论文地址：

https://arxiv.org/pdf/1907.00205.pdf

源代码：

https://github.com/AnonGit90210/RamanujanMachine

连分数查询：

https://oeis.org/A003417

— 完 —