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

魚羊 曉查 2019-07-06 13:02:13 來源：量子位

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

量子位 出品 | 公眾號 QbitAI

3.1415926……

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

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

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

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

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

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

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

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

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

你可以用泰勒展開的方法計算：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法介紹

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

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

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

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

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

有些hits值會產(chǎn)生誤報，針對這一點，研究人員提出通過計算任意精度的有理函數(shù)來減少誤報。

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

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

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

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

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

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

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

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

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

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

對此，作者表示，是不是機(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ù)的知識，就能發(fā)現(xiàn)各種表達(dá)式變體。

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

傳送門

論文地址：

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

源代碼：

https://github.com/AnonGit90210/RamanujanMachine

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

https://oeis.org/A003417

— 完 —