炼数成金 门户 科学探索 数学 查看内容

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

2019-7-7 10:55| 发布者: 炼数成金_小数| 查看: 7987| 评论: 0|来自: 量子位

摘要: 3.1415926……π和e这样的基本常数在科学领域中无处不在,但计算它们的高精度近似值往往令人头大。如今,机器学习或许能帮上大忙。能算近似值,还能在数学计算中快速找出精准规律,机器学习表示 I can I up。这就是 ...

算法 机器学习 计算机 数学 超级计算 公式

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

声明:本文版权归原作者所有,文章收集于网络,为传播信息而发,如有侵权,请联系小编及时处理,谢谢!

欢迎加入本站公开兴趣群
高性能计算群
兴趣范围包括:并行计算,GPU计算,CUDA,MPI,OpenMP等各种流行计算框架,超级计算机,超级计算在气象,军事,航空,汽车设计,科学探索,生物,医药等各个领域里的应用
QQ群:326600878

鲜花

握手

雷人

路过

鸡蛋

相关阅读

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

 

GMT+8, 2019-7-20 09:31 , Processed in 0.130704 second(s), 25 queries .