Martin Davis:機器學習是一個收斂的過程,背後理論並不高深
Allyn Jackson / 我在思考中-陳彩嫻 / 何渝婷編譯
2021-08-31 13:30

近日,ACM通訊(Communications of the ACM)刊登了一篇德國科技記者Allyn Jackson對著名數學家Martin Davis的採訪。

在採訪中,Martin Davis提出了一個有意思的觀點:「機器學習是一個收斂的過程,其連續逼近,並已在分析中應用多年。如果你在建構多級神經網路時選擇正確的函數,那麼它就會迅速收斂......」

Martin Davis於1928年在美國出生,1950年從普林斯頓大學取得數學博士學位,博士導師為現代電腦理論之父、著名的數學家與邏輯學家Alonzo Church。後來,他加入紐約大學任教,成為了NYU電腦科學系最重要的創始人之一。

在他數十年的研究生涯中,Martin Davis最為人稱道的是他在數理邏輯上的研究成果,尤其是對希爾伯特第十問題(H10)的深入研究。希爾伯特第十問題是關於不定方程的可解答性,希望對於任意多個未知數的整系數不定方程,可以找到一個可行算法,借助該算法後,通過有限次的運算就能判定該方程是否有整數解。

在他的博士答辯論文中,Martin Davis提出了著名的「戴維斯的大膽假設」(Daviss daring hypothesis),在邏輯與數論之間建立了連結。他假設了遞迴可列舉集合(recursively enumerable sets)與丟番圖方程(Diophantine sets)是相同的,從而判定H10不可解。

後來,在與數學家Hilary Putnam與Julia Robinson的合作中,Davis進一步證明了這個大膽的假設,並為俄羅斯電腦科學家Yuri Matiyasevich後來在1970年,最終證明H10不可解提供了重要的理論基礎。

此外,上世紀60年代,Martin Davis與Hilary Putnam一起設計的 Davis-Putnam算法(簡稱「DP算法」)成為SAT問題的第一個算法,在SAT問題被證明為NP-Complete問題後,DP算法也成為了所有完備問題算法的基本框架。

以下是ACM通訊對Martin Davis的訪談問答:

Q1:您對 「P不同於NP」持懷疑態度,是這樣嗎?

人們認為NP類是類似於遞迴可列舉集合的。這種類比是基於假設多項式時間的可計算性是可計算性的類比,多項式時間的可計算性是切實可行的可計算性。為什麼你會相信這個說法呢?這個說法並不合理。如果你有一個包含大數值系數的高階多項式邊界,那麼它在計算上根本是不可行的。NP類具有良好的數學閉合特性。這當然是一個有趣的類別,但為什麼認為它可行呢?

在實際的應用中,存在非常有用且運行良好的指數時間算法(exponential-time algorithms)。我的這個觀點是參考了Margaret Wright的研究工作。起初,人們認為線性規劃不是多項式時間。所以,在發現用於線性規劃的多項式時間算法時,人們認為這是一項重大突破,但事實上,這個算法的效果並不出色!如Margaret Wright所展示,在最壞的情況下呈指數的單純形法(simplex method)在許多案例中性能更好,也更快。

我的部分懷疑也與我在研究H10問題的經歷有關。在H10這個問題上,人們顯然對高級多項式沒有任何直覺。

順便說一句,雖然我不知道Donald Knuth的推理依據是什麼,但他的看法跟我一樣,即「P不同於NP」絕對不是一個開放與封閉的案例,所以我會說,概率是一半一半吧!

Q2:那您對NP-Complete問題怎麼看?

我認為NP-complete問題肯定是難題。我不認為有人可以為任何NP-Complete問題找到一個漂亮、可愛又快速的算法。不過,這並不意味著研究人員找不到多項式時間算法,只是這也許不是一個非常可行的算法。關於啓發式的爭論背後,總是有一個觀點,即「多項式時間」(polynomial-time)與「可行」(feasible)是一回事。

Q3:如何更好地定義「可行」?

目前還不清楚是否有一個非常精確的概念。定義的方式可能就像「有些算法比其他算法更難」,只有一個範圍。

此外,什麼是可行的,部分要取決於你有哪些可用的電腦設備。在我寫的《通用電腦》(The Universal Computer)中,我想用數字π來解釋關於收斂的想法。所以我用萊布尼茲的數列π/ 4 = 1 - 1/3 + 1/5 - 1/7......寫了一個程式,並計算出這個數列大約有20,000項。

但最近,又感覺通過將萊布尼茲級數中的20,000項相加來計算π的想法似乎是非常愚蠢的。不過,這只是一個業餘愛好者可以輕鬆地使用家裡的電腦和電腦編程知識的表現罷了。

Q4:在《通用電腦》的2018年版本中,您添加了一些關於機器學習與人工智慧的新內容。機器學習最讓您感到驚喜的是什麼?

這些神經網路模型非常有用,而且它們的功能非常強大。多年來,我一直對神經網路抱有懷疑的態度。最初的想法是,神經網路是在模仿大腦。然後我想,「這只是另一種模式,沒有什麼特別的優點。」但事實是,對於某些問題,例如圍棋比賽,神經網路的效果出奇地好。在這一點上,我的直覺是完全錯誤的。

Q5:目前沒有理論解釋為什麼機器學習這麼有效。您認為會出現這樣的理論嗎?

我不認為機器學習有多神秘。機器學習就是一個收斂過程,一個逐次逼近,已經在分析中應用多年。如果在建構多層神經網路時選擇正確的函數,那麼它就會迅速收斂,所以我不認為機器學習涉及到了特殊的深層理論。我甚至懷疑神經網路是在模仿自然。

如果你要成為鋼琴演奏家,你每天要練習七個小時。那麼,為什麼你不能只讀一本手冊,上面告訴你「你必須要成為一名鋼琴演奏家」?因為這行不通。你坐在鋼琴前,去請教一位老師,他也只會看著你做的事情,然後說:「你這不對,你的小指放的位置偏離了一點點。」 這就是一個收斂過程。

Q6:目前,人工智慧的研究成果與社會應用正呈爆炸式成長。這是一件好事,還是一件需要警惕的事?

我是這樣想的:我們有沒有可能製造一台自動機,可以幫我們做所有事情,甚至做得更好?比如圍棋和國際象棋之類難度極高的遊戲。是的,我們可以。在這些方面,人類已經不能打敗機器。

這就涉及到我們自己如何做這些事情,但我們真的不瞭解。大腦真的會執行算法嗎?大腦確實會一些。當我們製造一台自動機器去執行算法時,我們也會使用算法。我們的大腦顯然會進行搜尋。我們試圖記住一條訊息,它不會立即彈出來,但我們等一下,它就會突然彈出。當然,我們知道,通用運算不需要太多。Stephen Wolfram幾乎把通用電腦搞成了一種邪教,稱通用計算可以在非常小的實體中使用。事實上,如果大腦要通過執行算法來完成所有奇妙的事情,那麼我們也肯定能夠製造出做同樣事情的電腦。 

萊斯大學有一位學者Moshe Vardi討論過這個問題。他說,在一個時代後,我們將可以擁有一台能做人類做的任何事情的機器。

這個說法可能有點過於樂觀了。

如果你看這些神經網路的驚人成就,你會發現,他們無法產生新的想法。問題是,我們的大腦中在多大程度上產生一些更高級的想法,就像完全不同的技術一樣。不過,我的看法不同,我懷疑,在另一個層面上,這些技術是完全相同的。畢竟,我們要通過研究大量的數學知識,才能成為優秀的數學家。

Q7:那麼您如何解釋偉大的數學家在感知新結構、或將兩個看起來非常不同的事物連結起來時,所產生的洞察力或想像力的飛躍?您在研究H10問題時就是這樣的,當時您認為遞迴可列舉集合和丟番圖方程可能是相同的。

嗯......一個集畢竟是另一個集的子集,所以我不是將兩個完全不同的事物連結在一起。這更像是擴展了一些看起來非常有限的事物的研究範圍。

Q8:但這是跳出條框思考,思考您的知識以外的內容。如果大腦真的只是接收和合成資訊,您如何解釋這種飛躍?

很顯然,我不知道我們的大腦是如何做到這一點的。但是,這顯然是一種有用的生存技能,也是人類社會建立的可能因素之一。如他人曾說:「火不僅僅只會燒傷我們,也可以烹飪出美味的食物。」

Q9:您怎麼看待莫扎特寫交響曲這件事?電腦還做不了這種事。

嗯......電腦已經可以創作音樂了,只是還沒有創作出我所欣賞的音樂。但莫扎特是非常罕見的。就像任何作曲家一樣,莫扎特的技能要經過磨練,他的大腦以某種非常特殊的方式連接在一起,從而產生了美妙的音樂創意。我們不知道他是怎麼做到的,也不知道如何「造出」一個莫扎特。但未來,也許我們會知道。

Q10:所以您認為這是可能的?

我想不出為什麼它應該是不可能的。這會使舊思想更頑固。如果你問哥德爾,他會說,認為原生質(protoplasm)成就一切的想法是荒謬的。他相信思想是產生抽象、甚至超越的事物,思想使用了大腦,但大腦並不產生思想。另一方面,Marvin Minsky還認為,思想是大腦運作的原因。

20世紀生物學的勝利已經破壞了生機主義(vitalism)的案例,這也是哲學立場,即生物的屬性不能用物理和化學的一般規律來解釋。哥德爾是心理現象(mental phenomena)的活躍分子,心理現象的觀點在神經科學知識的現有狀態下,仍然可以保持一致。

本文為雷鋒網授權刊登,原文標題為「Martin Davis最新訪談:機器學習是一個收斂的過程,背後理論並不高深