谷歌造出拉馬努金機(jī)：幾毫秒求解數(shù)學(xué)常數(shù)，無(wú)需任何先驗(yàn)信息

魚(yú)羊 曉查 2019-07-06 13:02:13 來(lái)源：量子位

馭洋 曉查 發(fā)自 凹非寺

量子位 出品 | 公眾號(hào) QbitAI

3.1415926……

π和e這樣的基本常數(shù)在科學(xué)領(lǐng)域中無(wú)處不在，但計(jì)算它們的高精度近似值往往令人頭大。如今，機(jī)器學(xué)習(xí)或許能幫上大忙。

能算近似值，還能在數(shù)學(xué)計(jì)算中快速找出精準(zhǔn)規(guī)律，機(jī)器學(xué)習(xí)表示 I can I up。

這就是以色列理工學(xué)院和谷歌一起開(kāi)發(fā)的拉馬努金機(jī)器（Ramanujan Machine）。

拉馬努金，這位英年早逝的天才數(shù)學(xué)家，總能發(fā)現(xiàn)一些讓世人驚嘆的數(shù)學(xué)公式。由他發(fā)現(xiàn)的圓周率π的計(jì)算公式，只需計(jì)算第一項(xiàng)就能突破普通計(jì)算器的最高精度。

拉馬努金機(jī)器也有類似的奇效。面對(duì)各種奇怪復(fù)雜的數(shù)學(xué)常數(shù)，只要找出它的連分?jǐn)?shù)表示，只需計(jì)算十幾步、幾毫秒就能快速收斂，得到精準(zhǔn)答案。而且算法已經(jīng)開(kāi)源！

然而讓拉馬努金玩出花來(lái)的連分?jǐn)?shù)可不是簡(jiǎn)簡(jiǎn)單單就能被找出來(lái)的，幾個(gè)世紀(jì)以來(lái)，與基本常數(shù)相關(guān)的新數(shù)學(xué)公式十分少見(jiàn)，畢竟奠基人是歐拉、高斯這樣堪稱“變態(tài)”的天才，想要繼承他們的事業(yè)，不僅要有豐富的知識(shí)積累，還要有敏銳的數(shù)學(xué)直覺(jué)。

而機(jī)器學(xué)習(xí)卻表示，無(wú)需先驗(yàn)信息，我也能快速get新公式。

什么是連分?jǐn)?shù)

優(yōu)美的歐拉公式將e和π兩個(gè)數(shù)學(xué)常數(shù)聯(lián)系起來(lái)，但你知道這兩個(gè)無(wú)理數(shù)是怎么算出來(lái)的嗎？

你可以用泰勒展開(kāi)的方法計(jì)算：

實(shí)際上還有另一種計(jì)算方法，那就是連分?jǐn)?shù)，它的分母無(wú)限延伸下去，結(jié)果就會(huì)越來(lái)越接近：

黃金分割比φ=0.618……有著幾乎最簡(jiǎn)單的連分?jǐn)?shù)形式，一組全是1表示的數(shù)：

其他的數(shù)學(xué)嘗試，包括自然對(duì)數(shù)的底e、圓周率π，還有黎曼猜想中黎曼Zeta函數(shù)ζ(3)的值。都可以用連分?jǐn)?shù)來(lái)表示。

△π的連分?jǐn)?shù)表示

任意實(shí)數(shù)都可以用連分?jǐn)?shù)來(lái)表示。

連分?jǐn)?shù)有何用

你如果認(rèn)為連分?jǐn)?shù)是數(shù)學(xué)家們的奇技淫巧，那就大錯(cuò)特錯(cuò)了，發(fā)現(xiàn)連分?jǐn)?shù)的某個(gè)表達(dá)式有著實(shí)際的用途。

各種數(shù)學(xué)常數(shù)的連分?jǐn)?shù)是存在卻不是唯一的，如果找到一個(gè)合適的連分?jǐn)?shù)，那么計(jì)算結(jié)果的收斂速度會(huì)非常快，大大減少計(jì)算機(jī)的運(yùn)算量。

但是找到連分?jǐn)?shù)里一組特殊的數(shù)卻并不是一件容易的事情，否則這套算法也不會(huì)叫做拉馬努金機(jī)器了。

△?拉馬努金發(fā)現(xiàn)的連分?jǐn)?shù)，φ是黃金分割比

發(fā)現(xiàn)連分?jǐn)?shù)里那些特殊整數(shù)的規(guī)律，需要有長(zhǎng)年數(shù)學(xué)知識(shí)的積累，更要有易于常人的直覺(jué)。

現(xiàn)在有了拉馬努金機(jī)器，可以用電腦代替人的思維去尋找特殊的連分?jǐn)?shù)了。

有Reddit網(wǎng)友把拉馬努金機(jī)器找到的公式寫成Python代碼，各算了一遍e和π，分別用了15步和18步的迭代，就能達(dá)到float 64的精度，也就是小數(shù)點(diǎn)后15位。

拉馬努金機(jī)器不僅能算數(shù)學(xué)常數(shù)，如李維常數(shù)、辛欽常數(shù)，還能計(jì)算一些物理常數(shù)，如天文學(xué)計(jì)算中的拉普拉斯極限等等。

作者下一步的目標(biāo)用它來(lái)做數(shù)學(xué)證明，發(fā)現(xiàn)數(shù)學(xué)常數(shù)的固有屬性。比如e和π，我們都已經(jīng)能證明他們是無(wú)理數(shù)而且是超越數(shù)，其他常數(shù)是不是無(wú)理數(shù)呢？以后或許可以用計(jì)算機(jī)來(lái)證明了。

算法介紹

論文當(dāng)中提到了兩種算法。

第一種是中間相遇法（The Meet-In-The Middle）。這個(gè)算法的思路非常簡(jiǎn)單：

給定一個(gè)常數(shù)c（如 c=π），根據(jù)公式：

f1(x)=x，f2(x)=1/x ，……；GCF(α，β)代表 an=α(n)，bn=β(n)的連分?jǐn)?shù)；α，β，γ，δ為整數(shù)多項(xiàng)式。

先計(jì)算出公式右邊一個(gè)精度較低的值，并將其存入哈希表，然后通過(guò)枚舉的方法來(lái)使公式左右兩邊的值相匹配，匹配上的值稱為“hits”，隨后增加hits的精度并重新比較，重復(fù)這個(gè)過(guò)程直到hits達(dá)到指定精度。這個(gè)最終的結(jié)果就提供了一個(gè)新的連分?jǐn)?shù)。

有些hits值會(huì)產(chǎn)生誤報(bào)，針對(duì)這一點(diǎn)，研究人員提出通過(guò)計(jì)算任意精度的有理函數(shù)來(lái)減少誤報(bào)。

在這個(gè)算法當(dāng)中，由于公式右邊的計(jì)算成本更高，所以將它的值以哈希表來(lái)存儲(chǔ)，以空間換時(shí)間。這個(gè)哈希表也可以保存下來(lái)重新服務(wù)于公式左邊的枚舉，從而大大減少未來(lái)的枚舉時(shí)間。

MITM-RF算法不需要任何關(guān)于基本常數(shù)的先驗(yàn)信息，不過(guò)有許多基本常數(shù)的結(jié)構(gòu)是可以推斷出來(lái)的，以此作為MITM-RF的先驗(yàn)信息可以有效降低空間復(fù)雜度和計(jì)算復(fù)雜度。

不過(guò)，MITM-RF方法還是存在擴(kuò)展性不佳的問(wèn)題，于是研究者使用到了機(jī)器學(xué)習(xí)當(dāng)中常用的梯度下降方法，他們稱其為Descent&Repel方法。

我們可以把優(yōu)化問(wèn)題描述成這個(gè)樣子：

這里的最小值不是零維度點(diǎn)，而是（d-1）維的流形，其中d是給定的單一約束所預(yù)期的優(yōu)化變量的數(shù)量。

研究者還觀察到所有的最小值都是全局的，并且它們的誤差為0，也就是說(shuō)所有的梯度下降過(guò)程最后都會(huì)得到L=0的解。

這個(gè)優(yōu)化問(wèn)題起始于一個(gè)大的點(diǎn)的集合，在示例當(dāng)中，所有初始條件被放置在一條線上。對(duì)每一個(gè)點(diǎn)迭代執(zhí)行梯度下降，然后強(qiáng)制所有的點(diǎn)通過(guò)庫(kù)侖排斥彼此排斥。通過(guò)梯度下降步驟保證算法朝向整數(shù)格并趨向最小曲線，最后僅返回位于整數(shù)格上的解。

網(wǎng)友的質(zhì)疑

有Reddit網(wǎng)友認(rèn)為，連分?jǐn)?shù)通過(guò)等效變換可以獲得無(wú)限多種組合這篇論文不是機(jī)器學(xué)習(xí)，它只是一種自動(dòng)化查找新表達(dá)式的算法。

網(wǎng)友雖然反對(duì)將作者的結(jié)果稱為機(jī)器學(xué)習(xí)，但它仍然是一種吸引人的算法，最有趣的是使用梯度下降優(yōu)化整數(shù)分?jǐn)?shù)，以前從未見(jiàn)過(guò)有人這么用過(guò)，因此是有創(chuàng)新性的。

對(duì)此，作者表示，是不是機(jī)器學(xué)習(xí)取決于你如何定義，文章中尋找新數(shù)學(xué)公式的算法是基于梯度下降的模型，因此可以看做是機(jī)器學(xué)習(xí)，今后他還將展示更直接地利用機(jī)器學(xué)習(xí)的其他結(jié)果。

至于發(fā)現(xiàn)新的連分?jǐn)?shù)表達(dá)式，已經(jīng)有前人的研究成果可供查詢，而作者用拉馬努金機(jī)器發(fā)現(xiàn)的很多結(jié)果已經(jīng)被人類手工發(fā)現(xiàn)了。況且只要掌握了連分?jǐn)?shù)的知識(shí)，就能發(fā)現(xiàn)各種表達(dá)式變體。

但這不正是拉馬努金機(jī)器的魅力所在嗎？如果你沒(méi)有過(guò)人的數(shù)學(xué)頭腦，就把特殊技巧交給計(jì)算機(jī)來(lái)做吧！

傳送門

論文地址：

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

源代碼：

https://github.com/AnonGit90210/RamanujanMachine

連分?jǐn)?shù)查詢：

https://oeis.org/A003417

— 完 —