2023計算機科學7項重大突破！P與NP50年經(jīng)典難題，大模型涌現(xiàn)上榜（2021計算機學科）
編輯：桃子 好困
【新智元導讀】2023年，計算機領(lǐng)域都發(fā)生了哪些大事？Quanta Magazine的年終盤點來了。
一年一度的年終盤點來了！
2023年，計算機科學領(lǐng)域大事件人人都能脫口而出，火遍全網(wǎng)的ChatGPT一系列大模型、AI作畫神器Midjourney，AI視頻生成Gen-2、Pika飛速迭代……
在「P與NP」最經(jīng)典的問題上，研究人員取得了微妙但重要的進展。
秀爾算法（Shor’s algorithm），量子計算的殺手級應(yīng)用程序，在近30年后進行了首次重大升級。還有研究人員終于學會了如何在理論上通過一種普通類型的網(wǎng)絡(luò)，以最快速度找到最短路徑。
此外，加密學家在與AI建立意想不到的連接時，展示了機器學習模型和機器生成內(nèi)容也必須應(yīng)對隱藏的漏洞和消息。
Top 1：50年P(guān)與NP難題，「元復雜性」理論開路
50年來，計算機科學家一直試圖解決所在領(lǐng)域中最大，且懸而未決的問題，即「P與NP」。
簡單講，「P與NP」就是探討已知的困難的計算問題，具體有多難，是否存在更高效的算法。
但是，50年來想要解決這個問題的科學家們，都以失敗而告終。
就在許多科學家感覺快要有突破的時候，總是會遇到無法跨越的障礙，證明他們的方法行不通。
久而久之，科學家開始質(zhì)疑，為什么就連證明一個問題「很難」本身也這么困難。
在回答這類內(nèi)省式問題的努力中，出現(xiàn)了一個新興的領(lǐng)域「元復雜性」（meta-complexity）理論。它為這個問題提供了迄今為止最好的見解。
8月，Quanta一篇文章中曾介紹了「元復雜性」的理念，以及科學家們開始的探索。
三位數(shù)學家對數(shù)學推理的局限性不同看法
「P與NP」問題破解，能夠解決無數(shù)日志問題，使所有密碼學毫無意義，甚至揭示人類能夠知曉的事物的本質(zhì)。
簡單來說，P是那些可以輕松解決的問題，比如按字母順序排列。NP是那些解決方案易于檢查的問題，如數(shù)獨。
由于所有易于解決的問題也易于檢查，所以P中的問題也屬于NP。
但有些NP問題似乎很難解決，你無法在不先嘗試許多可能性的情況下直觀地得出數(shù)獨難題的解決方案。
通過研究這些內(nèi)省式問題，研究人員了解到，證明計算難度的困難程度，與乍看起來似無關(guān)的基本問題密切相關(guān)。
在明顯隨機的數(shù)據(jù)中發(fā)現(xiàn)隱藏的模式有多難？如果確實存在真正困難的問題，那么這些問題多久會出現(xiàn)一次？
德克薩斯大學奧斯汀分校的復雜性理論家Scott Aaronson表示，「很明顯，元復雜性與事物的核心關(guān)系密切」。
「P與NP」問題引領(lǐng)研究人員進入「元復雜性」理論艱難的旅程。
然而對于「元復雜性」的研究人員來說，這段在未知領(lǐng)域的旅程就是它自身的回報。
Top 2：大模型涌現(xiàn)，黑盒誰能打開
涌現(xiàn)，可以成為大模型領(lǐng)域年度熱詞。
OpenAI團隊曾在2022年一篇論文中，給「涌現(xiàn)」下了一個定義：
在參數(shù)規(guī)模較小的模型中不存在，在規(guī)模較大的模型中存在，那么這種能力就是涌現(xiàn)。
比如，你給大模型幾個表情包，然后詢問這代表著什么電影？LLM會根據(jù)已有的知識，去預(yù)測下一個token，最后給出答案。
答案：海底總動員
不僅如此，小模型無法完成的任務(wù)，其中許多似乎與分析文本沒有什么關(guān)系，從乘法到生成可執(zhí)行的計算機代碼，再到顯然基于表情符號對電影進行解碼。
OpenAI這項研究也表明，對于一些任務(wù)和一些模型，存在一個復雜性閾值，超過這個閾值，模型的能力會迅速增長。
但是，不得不承認，隨著LLM能力不斷增長，引發(fā)了新的擔憂。
這些強大的AI系統(tǒng)不僅編造謊言，制造社會偏見，甚至連人類語言中一些最基本的元素都無法處理。
最重要的是，這些AI仍舊是一個黑盒，內(nèi)部推理邏輯無法得知。
不過，在打開AI「黑盒」上的研究也在不斷涌現(xiàn)。比如，OpenAI團隊用GPT-4去解釋30萬個GPT-2神經(jīng)元，甚至在最新研究中提出用GPT-2監(jiān)督GPT-4。
總而言之，揭開大模型內(nèi)部運作機制還有很長的路要走。
Top 3：40年前算法，找到最短路徑
計算機科學家很早就知道，可以快速遍歷圖網(wǎng)絡(luò)的算法（由邊連接的節(jié)點網(wǎng)絡(luò)），而且其中的連接是有一定成本的，比如連接兩個城市的收費公路。
但幾十年來，如果只考慮一條路的成本和回報，科學家找不到任何快速算法來確定最短路徑。
去年年底，來自羅格斯大學的3位研究人員提出了一種可行的算法。
他們的新算法找到了從一個給定的「源」節(jié)點到每一個其他節(jié)點的圖中的最短路徑，幾乎趕上了很久以前正權(quán)重算法所達到的速度。
論文地址：https://arxiv.org/abs/2203.03456
值得一提的是，Dijkstra這一算法早在1956年，是由荷蘭計算機科學家Edsger Dijkstra開發(fā)的快速算法，可以在只有正權(quán)的圖上找到最短路徑。
對此，研究人員反轉(zhuǎn)思路，給出了負權(quán)圖的最短路徑算法。
今年3月，芝加哥大學的華人計算機科學家Xiaorui Sun提出了一種更快的算法，以更快的速度打破了群同構(gòu)問題中最難解決的實例。
論文地址：https://arxiv.org/abs/2303.15412
它可以精確地確定兩種被稱為組的數(shù)學對象何時相同。
此外，今年的其他重大算法新聞還包括，通過結(jié)合隨機和確定性方法計算素數(shù)的新方法，反駁了一個關(guān)于信息有限算法性能的長期猜想。
以及一項分析，展示了一個非直觀的想法如何提高漸降算法的性能，梯度下降算法在機器學習程序和其他領(lǐng)域中隨處可見。
Top 4：AI生圖爆火，背后技術(shù)沉淀多年
今年，DALL·E、Midjourney、Stable Diffusion等圖像生成工具，深受人們歡迎。
只需給一個文字提示，AI就可以按照你的要求創(chuàng)作出一幅藝術(shù)作品。
不過，這些AI藝術(shù)家背后的技術(shù)，其實早已經(jīng)歷了多年的積累——
擴散模型（diffusion models）基于的是物理學中流體擴散的原理，它們能有效地把模糊的噪聲轉(zhuǎn)換為清晰的圖形——就好比將咖啡中混合均勻的奶油再次分離出來，恢復成清晰的形狀。
此外，AI工具在提高現(xiàn)有圖像的清晰度方面也取得了進展，雖然這距離電視劇中警察反復大喊「增強！」的場景還有很長的路要走。
最近，研究人員開始研究擴散以外的其他物理過程，來尋找機器生成圖像的新方法。
其中一種新的方法是基于泊松方程（Poisson equation）——用于描述電場力隨距離變化的過程。這種方法已經(jīng)證明在處理錯誤方面更加高效，并且在某些情況下比擴散模型更容易訓練。
Top 5：30年后，量子因數(shù)分解運算速度飆升
幾十年來，秀爾算法（Shor’s algorithm）一直被視為量子計算機強大能力的象征。
這套由Peter Shor在1994年開發(fā)的算法，讓量子計算機能夠利用其量子物理特性，比經(jīng)典計算機更快地將大數(shù)分解為質(zhì)因數(shù)。而這對目前大部分的互聯(lián)網(wǎng)安全系統(tǒng)，構(gòu)成了潛在威脅。
2023年8月，一位計算機科學家開發(fā)出了一個更快的Shor算法變體，這是自該算法被發(fā)明以來的首次重大改進。
盡管如此，真正實用的量子計算機仍然遙不可及。
在實際應(yīng)用中，微小的誤差會迅速累積，從而破壞計算結(jié)果，并進一步消除了量子計算帶來的所有優(yōu)勢。
事實上，去年年底，一組計算機科學家的研究表明，對于一個特定的問題，經(jīng)典算法與包含誤差的量子算法大致相同。
但希望還是有的：8月的研究顯示，某些糾錯碼（稱為低密度奇偶校驗碼）的效率，至少是現(xiàn)行標準的10倍。
Top 6：密碼學 AI的隱藏秘密
在密碼學和人工智能交叉領(lǐng)域的一項不尋常研究中。
最近，一組計算機科學家證明了可以在機器學習模型中嵌入后門，這些后門不僅幾乎無法被發(fā)現(xiàn)，而且它們的隱蔽性得到了類似于現(xiàn)代最先進加密技術(shù)的邏輯支持。
不過，團隊主要研究的是較簡單的模型，因此目前還不清楚這一發(fā)現(xiàn)是否也適用于當今AI技術(shù)中使用的更復雜的模型。
然而，這些研究成果為未來系統(tǒng)如何防御這類安全漏洞提供了可能的方向。
正是因為這類安全問題，Cynthia Rudin強烈推薦使用可解釋的模型，來更深入地了解機器學習算法內(nèi)部的運作機制。
與此同時，像Yael Tauman Kalai這樣的研究人員，也在安全性和隱私領(lǐng)域取得了進展，而這對即將到來的量子技術(shù)來說極為重要。
而在隱寫術(shù)這一相關(guān)領(lǐng)域，研究成果展示了如何在機器生成的媒體中以絕對安全的方式隱藏信息。
Top 7：向量注入語義，讓LLM推理更高效
盡管人工智能已經(jīng)非常強大，但支撐大多數(shù)現(xiàn)代系統(tǒng)的人工神經(jīng)網(wǎng)絡(luò)存在兩大問題：
1. 在訓練和運行時需要消耗大量資源
2. 容易變成難以理解的「黑箱」
因此，很多研究人員都認為，現(xiàn)在或許是采取新方法的時候了——
通過成千上萬的超維向量來表現(xiàn)概念，而不是用人工神經(jīng)元來檢測單個特征或特性。
這種系統(tǒng)用途更廣，處理錯誤的能力更強，計算效率也高得多。
而且，研究人員還可以直接操作模型所考慮的想法和關(guān)系，從而更深入地了解它的推理過程。
今年3月，蘇黎世IBM研究院的團隊，使用帶有神經(jīng)網(wǎng)絡(luò)的超維計算來解決抽象視覺推理中的一個經(jīng)典問題——「瑞文的遞進矩陣」。
它將幾何對象的圖像呈現(xiàn)在一個3×3的網(wǎng)格中。網(wǎng)格中的一個位置為空，對象必須從一組候選圖像中選擇最適合空白的圖像。
為了使用超維計算解決這個問題，該團隊首先創(chuàng)建了一個超向量字典來表示每幅圖像中的對象。
字典中的每個超向量代表一個對象及其屬性的某種組合。
然后，該團隊訓練神經(jīng)網(wǎng)絡(luò)來檢查圖像并生成一個雙極超向量，一個元素可以是 1或?1，它盡可能接近字典中超向量的某種疊加。
因此，生成的超向量包含關(guān)于圖像中所有對象及其屬性的信息。
他們提出的方法在一組問題上的準確率接近88%，而僅使用神經(jīng)網(wǎng)絡(luò)的解決方案的準確率不到61%。
目前超維計算尚處于初期階段，但隨著其在更大規(guī)模的測試中的應(yīng)用，我們可能會看到這種新方法開始展現(xiàn)其潛力。
參考資料：
https://www.quantamagazine.org/the-biggest-discoveries-in-computer-science-in-2023-20231220/
