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