0
| 本文作者： 我在思考中 | 2021-08-30 10:24 |
編譯 | 陳彩嫻
近日，ACM 通訊（Communications of the ACM）刊登了一篇德國科技記者 Allyn Jackson 對著名數(shù)學(xué)家 Martin Davis 的采訪。
在采訪中，Martin Davis 提出了一個有意思的觀點(diǎn)：“機(jī)器學(xué)習(xí)是一個收斂過程，一個連續(xù)逼近，已在分析中應(yīng)用多年。如果你在構(gòu)建多級神經(jīng)網(wǎng)絡(luò)時選擇正確的函數(shù)，那么它就會迅速收斂…”
Martin Davis 于1928年在美國出生，1950年從普林斯頓大學(xué)取得數(shù)學(xué)博士學(xué)位，博士導(dǎo)師為現(xiàn)代計算機(jī)理論之父、著名的數(shù)學(xué)家與邏輯學(xué)家 Alonzo Church。后來，他加入紐約大學(xué)任教，成為了 NYU 計算機(jī)科學(xué)系最重要的創(chuàng)始人之一。
在他數(shù)十年的研究生涯中，Martin Davis 最為人稱道的是他在數(shù)理邏輯上的研究成果，尤其是對希爾伯特第十問題（H10）的深入研究。希爾伯特第十問題是關(guān)于不定方程的可解答性，希望對于任意多個未知數(shù)的整系數(shù)不定方程，可以找到一個可行算法，借助該算法后，通過有限次的運(yùn)算就能判定該方程是否有整數(shù)解。
在他的博士答辯論文中，Martin Davis 提出了著名的“戴維斯的大膽假設(shè)”（Davis's daring hypothesis），在邏輯與數(shù)論之間建立了聯(lián)系。他假設(shè)了遞歸可枚舉集（recursively enumerable sets）與丟番圖集（Diophantine sets）是相同的，從而判定 H10 不可解。
后來，在與數(shù)學(xué)家 Hilary Putnam 與 Julia Robinson 的合作中，Davis 進(jìn)一步證明了這個大膽的假設(shè)，并為俄羅斯計算機(jī)科學(xué)家 Yuri Matiyasevich 后來在1970 年最終證明 H10 不可解提供了重要的理論基礎(chǔ)。
此外，上世紀(jì)60年代，Martin Davis 與 Hilary Putnam 一起設(shè)計的 Davis-Putnam 算法（簡稱“DP算法”）成為 SAT 問題的第一個算法，在 SAT 問題被證明為 NP-Complete 問題后，DP算法也成為了所有完備問題算法的基本框架。
以下是 ACM 通訊對 Martin Davis 的訪談問答：
Q1：您對 “P 不同于 NP”持懷疑態(tài)度，是這樣嗎？
人們認(rèn)為 NP 類是類似于遞歸可枚舉集的。這種類比是基于假設(shè)多項式時間的可計算性是可計算性的類比，多項式時間的可計算性是切實(shí)可行的可計算性。為什么你會相信這個說法呢？這個說法并不合理。如果你有一個包含大數(shù)值系數(shù)的高階多項式邊界，那么它在計算上根本是不可行的。NP類具有良好的數(shù)學(xué)閉合特性。這當(dāng)然是一個有趣的類別，但為什么認(rèn)為它可行呢？
在實(shí)際的應(yīng)用中，存在非常有用且運(yùn)行良好的指數(shù)時間算法（exponential-time algorithms）。我的這個觀點(diǎn)是參考了 Margaret Wright 的研究工作。起初，人們認(rèn)為線性規(guī)劃不是多項式時間。所以，在發(fā)現(xiàn)用于線性規(guī)劃的多項式時間算法時，人們認(rèn)為這是一項重大突破，但事實(shí)上，這個算法的效果并不出色！如 Margaret Wright 所展示，在最壞的情況下呈指數(shù)的單純形法（simplex method）在許多案例中性能更好，也更快。
我的部分懷疑也與我在研究 H10 問題的經(jīng)歷有關(guān)。在 H10 這個問題上，人們顯然對高級多項式?jīng)]有任何直覺。
順便說一句，雖然我不知道 Donald Knuth 的推理依據(jù)是什么，但他的看法跟我一樣，即“P 不同于 NP”絕對不是一個開放與封閉的案例，所以我會說，概率是一半一半吧。
Q2：那您對 NP-Complete 問題怎么看？
我認(rèn)為 NP-complete 問題肯定是難題。我不認(rèn)為有人可以為任何 NP-Complete 問題找到一個漂亮、可愛又快速的算法。不過，這并不意味著研究人員找不到多項式時間算法，只是這也許不是一個非常可行的算法。關(guān)于啟發(fā)式的爭論背后，總是有一個觀點(diǎn)，即“多項式時間”（polynomial-time）與“可行”（feasible）是一回事。
Q3：如何更好地定義“可行”？
目前還不清楚是否有一個非常精確的概念。定義的方式可能就像“有些算法比其他算法更難”，只有一個范圍。
此外，什么是可行的，部分要取決于你有哪些可用的計算機(jī)設(shè)備。在我寫的《通用計算機(jī)》（The Universal Computer）中，我想用數(shù)字 π 來解釋關(guān)于收斂的想法。所以我用萊布尼茨的數(shù)列 π/ 4 = 1 - 1/3 + 1/5 - 1/7…寫了一個程序，并計算出這個數(shù)列大約有 20,000 項。
但最近，又感覺通過將萊布尼茨級數(shù)中的 20,000 項相加來計算 π 的想法似乎是非常愚蠢的。不過，這只是一個業(yè)余愛好者可以輕松地使用家里的電腦和計算機(jī)編程知識的表現(xiàn)罷了。
Q4：在《通用計算機(jī)》的 2018 年版本中，您添加了一些關(guān)于機(jī)器學(xué)習(xí)與人工智能的新內(nèi)容。機(jī)器學(xué)習(xí)最讓您感到驚喜的是什么？
這些神經(jīng)網(wǎng)絡(luò)模型非常有用，而且它們的功能非常強(qiáng)大。多年來，我一直對神經(jīng)網(wǎng)絡(luò)抱有懷疑的態(tài)度。最初的想法是，神經(jīng)網(wǎng)絡(luò)是在模仿大腦。然后我想，“這只是另一種模式，沒有什么特別的優(yōu)點(diǎn)?！钡聦?shí)是，對于某些問題，例如圍棋比賽，神經(jīng)網(wǎng)絡(luò)的效果出奇地好。在這一點(diǎn)上，我的直覺是完全錯誤的。
Q5：目前沒有理論解釋為什么機(jī)器學(xué)習(xí)這么有效。您認(rèn)為會出現(xiàn)這樣的理論嗎？
我不認(rèn)為機(jī)器學(xué)習(xí)有多神秘。機(jī)器學(xué)習(xí)就是一個收斂過程，一個逐次逼近，已經(jīng)在分析中應(yīng)用多年。如果在構(gòu)建多層神經(jīng)網(wǎng)絡(luò)時選擇正確的函數(shù)，那么它就會迅速收斂，所以我不認(rèn)為機(jī)器學(xué)習(xí)涉及到了特殊的深層理論。我甚至懷疑神經(jīng)網(wǎng)絡(luò)是在模仿自然。
如果你要成為鋼琴演奏家，你每天要練習(xí)七個小時。那么，為什么你不能只讀一本手冊，上面告訴你“你必須要成為一名鋼琴演奏家”？因?yàn)檫@行不通。你坐在鋼琴前，去請教一位老師，他也只會看著你做的事情，然后說：“你這不對，你的小指放的位置偏離了一點(diǎn)點(diǎn)。” 這就是一個收斂過程。
Q6：目前，人工智能的研究成果與社會應(yīng)用正呈爆炸式增長。這是一件好事，還是一件需要警惕的事？
我是這樣想的：我們有沒有可能制造一臺自動機(jī)，可以幫我們做所有事情，甚至做得更好？比如圍棋和國際象棋之類難度極高的游戲。是的，我們可以。在這些方面，人類已經(jīng)不能打敗機(jī)器。
這就涉及到我們自己如何做這些事情，但我們真的不了解。大腦真的會執(zhí)行算法嗎？大腦確實(shí)會一些。當(dāng)我們制造一臺自動機(jī)器去執(zhí)行算法時，我們也會使用算法。我們的大腦顯然會進(jìn)行搜索。我們試圖記住一條信息，它不會立即彈出來，但我們等一會，它就會突然彈出。當(dāng)然，我們知道，通用計算不需要太多。Stephen Wolfram 幾乎把通用計算機(jī)搞成了一種邪教，稱通用計算可以在非常小的實(shí)體中使用。事實(shí)上，如果大腦要通過執(zhí)行算法來完成所有奇妙的事情，那么我們也肯定能夠制造出做同樣事情的計算機(jī)。
萊斯大學(xué)有一位學(xué)者討論過這個問題。他的名字是什么...？
Moshe Vardi?
是的?？矗銊倓傇陔娔X上搜了他的名字！他說，在一個時代后，我們將可以擁有一臺能做人類做的任何事情的機(jī)器。這個說法可能有點(diǎn)過于樂觀了。
如果你看這些神經(jīng)網(wǎng)絡(luò)的驚人成就，你會發(fā)現(xiàn)，他們無法產(chǎn)生新的想法。問題是，我們的大腦中在多大程度上產(chǎn)生一些更高級的想法，就像完全不同的技術(shù)一樣。不過，我的看法不同，我懷疑，在另一個層面上，這些技術(shù)是完全相同的。畢竟，我們要通過研究大量的數(shù)學(xué)知識，才能成為優(yōu)秀的數(shù)學(xué)家。
Q7：那么您如何解釋偉大的數(shù)學(xué)家在感知新結(jié)構(gòu)、或?qū)蓚€看起來非常不同的事物聯(lián)系起來時所產(chǎn)生的洞察力或想象力的飛躍？您在研究 H10 問題時就是這樣的，當(dāng)時您認(rèn)為遞歸可枚舉集和丟番圖集可能是相同的。
嗯……一個集畢竟是另一個集的子集，所以我不是將兩個完全不同的事物連接在一起。這更像是擴(kuò)展了一些看起來非常有限的事物的研究范圍。
Q8：但這是跳出條框思考，思考您的知識以外的內(nèi)容。如果大腦真的只是接收和合成信息，您如何解釋這種飛躍？
很顯然，我不知道我們的大腦是如何做到這一點(diǎn)的。但是，這顯然是一種有用的生存技能，也是人類社會建立的可能因素之一。如他人曾說：“火不僅僅只會燒傷我們，也可以烹飪出美味的食物?！?/span>
Q9：您怎么看待莫扎特寫交響曲這件事？計算機(jī)還做不了這種事。
嗯……計算機(jī)已經(jīng)可以創(chuàng)作音樂了，只是還沒有創(chuàng)作出我所欣賞的音樂。但莫扎特是非常罕見的。就像任何作曲家一樣，莫扎特的技能要經(jīng)過磨練，他的大腦以某種非常特殊的方式連接在一起，從而產(chǎn)生了美妙的音樂創(chuàng)意。我們不知道他是怎么做到的，也不知道如何“造出”一個莫扎特。但未來，也許我們會知道。
Q10：所以您認(rèn)為這是可能的。
我想不出為什么它應(yīng)該是不可能的。這會使舊思想更頑固。如果你問哥德爾，他會說，認(rèn)為原生質(zhì)（protoplasm）成就一切的想法是荒謬的。他相信思想是產(chǎn)生抽象、甚至超越的事物，思想使用了大腦，但大腦并不產(chǎn)生思想。另一方面，Marvin Minsky 還認(rèn)為，思想是大腦運(yùn)作的原因。
20世紀(jì)生物學(xué)的勝利已經(jīng)破壞了生機(jī)主義（vitalism）的案例，這也是哲學(xué)立場，即生物的屬性不能用物理和化學(xué)的一般規(guī)律來解釋。哥德爾是心理現(xiàn)象（mental phenomena）的活躍分子，心理現(xiàn)象的觀點(diǎn)在神經(jīng)科學(xué)知識的現(xiàn)有狀態(tài)下仍然可以保持一致。
贈書福利
AI科技評論本次聯(lián)合Springer為大家?guī)?strong>5本周志華教授親筆簽名的《Machine Learning》正版新書。
在AI科技評論8月28日頭條文章（注意不是本文，僅限AI科技評論微信公眾號端）留言區(qū)留言，歡迎大家暢所欲言，談一談你對本書的看法和期待。在綜合留言質(zhì)量（留言是敷衍還是走心）和留言點(diǎn)贊最高（注：點(diǎn)贊最高的前5不意味著一定會中獎）的讀者中選出5位讀者獲得贈書。獲得贈書的讀者請聯(lián)系 AI 科技評論客服（aitechreview）。
留言內(nèi)容會有篩選，例如“選我上去”、“這書寫的很棒（僅僅幾個字）”等內(nèi)容將不會被篩選，亦不會中獎。
留言送書活動時間為2021年8月28日 - 2021年9月01日（23:00），活動推送時間內(nèi)僅允許贈書福利中獎一次。
雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)
雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
