一年一度的年終盤(pán)點(diǎn)來(lái)了！

2023年，計(jì)算機(jī)科學(xué)領(lǐng)域大事件人人都能脫口而出，火遍全網(wǎng)的ChatGPT一系列大模型、AI作畫(huà)神器Midjourney，AI視頻生成Gen-2、Pika飛速迭代......

在「P與NP」最經(jīng)典的問(wèn)題上，研究人員取得了微妙但重要的進(jìn)展。

秀爾算法（Shor’s algorithm），量子計(jì)算的殺手級(jí)應(yīng)用程序，在近30年后進(jìn)行了首次重大升級(jí)。還有研究人員終于學(xué)會(huì)了如何在理論上通過(guò)一種普通類(lèi)型的網(wǎng)絡(luò)，以最快速度找到最短路徑。

此外，加密學(xué)家在與AI建立意想不到的連接時(shí)，展示了機(jī)器學(xué)習(xí)模型和機(jī)器生成內(nèi)容也必須應(yīng)對(duì)隱藏的漏洞和消息。

Top 1：50年P(guān)與NP難題，「元復(fù)雜性」理論開(kāi)路

50年來(lái)，計(jì)算機(jī)科學(xué)家一直試圖解決所在領(lǐng)域中最大，且懸而未決的問(wèn)題，即「P與NP」。

簡(jiǎn)單講，「P與NP」就是探討已知的困難的計(jì)算問(wèn)題，具體有多難，是否存在更高效的算法。

但是，50年來(lái)想要解決這個(gè)問(wèn)題的科學(xué)家們，都以失敗而告終。

就在許多科學(xué)家感覺(jué)快要有突破的時(shí)候，總是會(huì)遇到無(wú)法跨越的障礙，證明他們的方法行不通。

久而久之，科學(xué)家開(kāi)始質(zhì)疑，為什么就連證明一個(gè)問(wèn)題「很難」本身也這么困難。

在回答這類(lèi)內(nèi)省式問(wèn)題的努力中，出現(xiàn)了一個(gè)新興的領(lǐng)域「元復(fù)雜性」（meta-complexity）理論。它為這個(gè)問(wèn)題提供了迄今為止最好的見(jiàn)解。

8月，Quanta一篇文章中曾介紹了「元復(fù)雜性」的理念，以及科學(xué)家們開(kāi)始的探索。

三位數(shù)學(xué)家對(duì)數(shù)學(xué)推理的局限性不同看法

「P與NP」問(wèn)題破解，能夠解決無(wú)數(shù)日志問(wèn)題，使所有密碼學(xué)毫無(wú)意義，甚至揭示人類(lèi)能夠知曉的事物的本質(zhì)。

簡(jiǎn)單來(lái)說(shuō)，P是那些可以輕松解決的問(wèn)題，比如按字母順序排列。NP是那些解決方案易于檢查的問(wèn)題，如數(shù)獨(dú)。

由于所有易于解決的問(wèn)題也易于檢查，所以P中的問(wèn)題也屬于NP。

但有些NP問(wèn)題似乎很難解決，你無(wú)法在不先嘗試許多可能性的情況下直觀地得出數(shù)獨(dú)難題的解決方案。

通過(guò)研究這些內(nèi)省式問(wèn)題，研究人員了解到，證明計(jì)算難度的困難程度，與乍看起來(lái)似無(wú)關(guān)的基本問(wèn)題密切相關(guān)。

在明顯隨機(jī)的數(shù)據(jù)中發(fā)現(xiàn)隱藏的模式有多難？如果確實(shí)存在真正困難的問(wèn)題，那么這些問(wèn)題多久會(huì)出現(xiàn)一次？

德克薩斯大學(xué)奧斯汀分校的復(fù)雜性理論家Scott Aaronson表示，「很明顯，元復(fù)雜性與事物的核心關(guān)系密切」。

「P與NP」問(wèn)題引領(lǐng)研究人員進(jìn)入「元復(fù)雜性」理論艱難的旅程。

然而對(duì)于「元復(fù)雜性」的研究人員來(lái)說(shuō)，這段在未知領(lǐng)域的旅程就是它自身的回報(bào)。

Top 2：大模型涌現(xiàn)，黑盒誰(shuí)能打開(kāi)

涌現(xiàn)，可以成為大模型領(lǐng)域年度熱詞。

OpenAI團(tuán)隊(duì)曾在2022年一篇論文中，給「涌現(xiàn)」下了一個(gè)定義：

在參數(shù)規(guī)模較小的模型中不存在，在規(guī)模較大的模型中存在，那么這種能力就是涌現(xiàn)。

比如，你給大模型幾個(gè)表情包，然后詢問(wèn)這代表著什么電影？LLM會(huì)根據(jù)已有的知識(shí)，去預(yù)測(cè)下一個(gè)token，最后給出答案。

答案：海底總動(dòng)員

不僅如此，小模型無(wú)法完成的任務(wù)，其中許多似乎與分析文本沒(méi)有什么關(guān)系，從乘法到生成可執(zhí)行的計(jì)算機(jī)代碼，再到顯然基于表情符號(hào)對(duì)電影進(jìn)行解碼。

OpenAI這項(xiàng)研究也表明，對(duì)于一些任務(wù)和一些模型，存在一個(gè)復(fù)雜性閾值，超過(guò)這個(gè)閾值，模型的能力會(huì)迅速增長(zhǎng)。

但是，不得不承認(rèn)，隨著LLM能力不斷增長(zhǎng)，引發(fā)了新的擔(dān)憂。

這些強(qiáng)大的AI系統(tǒng)不僅編造謊言，制造社會(huì)偏見(jiàn)，甚至連人類(lèi)語(yǔ)言中一些最基本的元素都無(wú)法處理。

最重要的是，這些AI仍舊是一個(gè)黑盒，內(nèi)部推理邏輯無(wú)法得知。

不過(guò)，在打開(kāi)AI「黑盒」上的研究也在不斷涌現(xiàn)。比如，OpenAI團(tuán)隊(duì)用GPT-4去解釋30萬(wàn)個(gè)GPT-2神經(jīng)元，甚至在最新研究中提出用GPT-2監(jiān)督GPT-4。

總而言之，揭開(kāi)大模型內(nèi)部運(yùn)作機(jī)制還有很長(zhǎng)的路要走。

Top 3：40年前算法，找到最短路徑

計(jì)算機(jī)科學(xué)家很早就知道，可以快速遍歷圖網(wǎng)絡(luò)的算法（由邊連接的節(jié)點(diǎn)網(wǎng)絡(luò)），而且其中的連接是有一定成本的，比如連接兩個(gè)城市的收費(fèi)公路。

但幾十年來(lái)，如果只考慮一條路的成本和回報(bào)，科學(xué)家找不到任何快速算法來(lái)確定最短路徑。

去年年底，來(lái)自羅格斯大學(xué)的3位研究人員提出了一種可行的算法。

他們的新算法找到了從一個(gè)給定的「源」節(jié)點(diǎn)到每一個(gè)其他節(jié)點(diǎn)的圖中的最短路徑，幾乎趕上了很久以前正權(quán)重算法所達(dá)到的速度。

論文地址：https://arxiv.org/abs/2203.03456

值得一提的是，Dijkstra這一算法早在1956年，是由荷蘭計(jì)算機(jī)科學(xué)家Edsger Dijkstra開(kāi)發(fā)的快速算法，可以在只有正權(quán)的圖上找到最短路徑。

對(duì)此，研究人員反轉(zhuǎn)思路，給出了負(fù)權(quán)圖的最短路徑算法。

今年3月，芝加哥大學(xué)的華人計(jì)算機(jī)科學(xué)家Xiaorui Sun提出了一種更快的算法，以更快的速度打破了群同構(gòu)問(wèn)題中最難解決的實(shí)例。

論文地址：https://arxiv.org/abs/2303.15412

它可以精確地確定兩種被稱(chēng)為組的數(shù)學(xué)對(duì)象何時(shí)相同。

此外，今年的其他重大算法新聞還包括，通過(guò)結(jié)合隨機(jī)和確定性方法計(jì)算素?cái)?shù)的新方法，反駁了一個(gè)關(guān)于信息有限算法性能的長(zhǎng)期猜想。

以及一項(xiàng)分析，展示了一個(gè)非直觀的想法如何提高漸降算法的性能，梯度下降算法在機(jī)器學(xué)習(xí)程序和其他領(lǐng)域中隨處可見(jiàn)。

Top 4：AI生圖爆火，背后技術(shù)沉淀多年

今年，DALL·E、Midjourney、Stable Diffusion等圖像生成工具，深受人們歡迎。

只需給一個(gè)文字提示，AI就可以按照你的要求創(chuàng)作出一幅藝術(shù)作品。

不過(guò)，這些AI藝術(shù)家背后的技術(shù)，其實(shí)早已經(jīng)歷了多年的積累——

擴(kuò)散模型（diffusion models）基于的是物理學(xué)中流體擴(kuò)散的原理，它們能有效地把模糊的噪聲轉(zhuǎn)換為清晰的圖形——就好比將咖啡中混合均勻的奶油再次分離出來(lái)，恢復(fù)成清晰的形狀。

此外，AI工具在提高現(xiàn)有圖像的清晰度方面也取得了進(jìn)展，雖然這距離電視劇中警察反復(fù)大喊「增強(qiáng)！」的場(chǎng)景還有很長(zhǎng)的路要走。

最近，研究人員開(kāi)始研究擴(kuò)散以外的其他物理過(guò)程，來(lái)尋找機(jī)器生成圖像的新方法。

其中一種新的方法是基于泊松方程（Poisson equation）——用于描述電場(chǎng)力隨距離變化的過(guò)程。這種方法已經(jīng)證明在處理錯(cuò)誤方面更加高效，并且在某些情況下比擴(kuò)散模型更容易訓(xùn)練。

Top 5：30年后，量子因數(shù)分解運(yùn)算速度飆升

幾十年來(lái)，秀爾算法（Shor’s algorithm）一直被視為量子計(jì)算機(jī)強(qiáng)大能力的象征。

這套由Peter Shor在1994年開(kāi)發(fā)的算法，讓量子計(jì)算機(jī)能夠利用其量子物理特性，比經(jīng)典計(jì)算機(jī)更快地將大數(shù)分解為質(zhì)因數(shù)。而這對(duì)目前大部分的互聯(lián)網(wǎng)安全系統(tǒng)，構(gòu)成了潛在威脅。

2023年8月，一位計(jì)算機(jī)科學(xué)家開(kāi)發(fā)出了一個(gè)更快的Shor算法變體，這是自該算法被發(fā)明以來(lái)的首次重大改進(jìn)。

盡管如此，真正實(shí)用的量子計(jì)算機(jī)仍然遙不可及。

在實(shí)際應(yīng)用中，微小的誤差會(huì)迅速累積，從而破壞計(jì)算結(jié)果，并進(jìn)一步消除了量子計(jì)算帶來(lái)的所有優(yōu)勢(shì)。

事實(shí)上，去年年底，一組計(jì)算機(jī)科學(xué)家的研究表明，對(duì)于一個(gè)特定的問(wèn)題，經(jīng)典算法與包含誤差的量子算法大致相同。

但希望還是有的：8月的研究顯示，某些糾錯(cuò)碼（稱(chēng)為低密度奇偶校驗(yàn)碼）的效率，至少是現(xiàn)行標(biāo)準(zhǔn)的10倍。

Top 6：密碼學(xué)+AI的隱藏秘密

在密碼學(xué)和人工智能交叉領(lǐng)域的一項(xiàng)不尋常研究中。

最近，一組計(jì)算機(jī)科學(xué)家證明了可以在機(jī)器學(xué)習(xí)模型中嵌入后門(mén)，這些后門(mén)不僅幾乎無(wú)法被發(fā)現(xiàn)，而且它們的隱蔽性得到了類(lèi)似于現(xiàn)代最先進(jìn)加密技術(shù)的邏輯支持。

不過(guò)，團(tuán)隊(duì)主要研究的是較簡(jiǎn)單的模型，因此目前還不清楚這一發(fā)現(xiàn)是否也適用于當(dāng)今AI技術(shù)中使用的更復(fù)雜的模型。

然而，這些研究成果為未來(lái)系統(tǒng)如何防御這類(lèi)安全漏洞提供了可能的方向。

正是因?yàn)檫@類(lèi)安全問(wèn)題，Cynthia Rudin強(qiáng)烈推薦使用可解釋的模型，來(lái)更深入地了解機(jī)器學(xué)習(xí)算法內(nèi)部的運(yùn)作機(jī)制。

與此同時(shí)，像Yael Tauman Kalai這樣的研究人員，也在安全性和隱私領(lǐng)域取得了進(jìn)展，而這對(duì)即將到來(lái)的量子技術(shù)來(lái)說(shuō)極為重要。

而在隱寫(xiě)術(shù)這一相關(guān)領(lǐng)域，研究成果展示了如何在機(jī)器生成的媒體中以絕對(duì)安全的方式隱藏信息。

Top 7：向量注入語(yǔ)義，讓LLM推理更高效

盡管人工智能已經(jīng)非常強(qiáng)大，但支撐大多數(shù)現(xiàn)代系統(tǒng)的人工神經(jīng)網(wǎng)絡(luò)存在兩大問(wèn)題：

1. 在訓(xùn)練和運(yùn)行時(shí)需要消耗大量資源

2. 容易變成難以理解的「黑箱」

因此，很多研究人員都認(rèn)為，現(xiàn)在或許是采取新方法的時(shí)候了——

通過(guò)成千上萬(wàn)的超維向量來(lái)表現(xiàn)概念，而不是用人工神經(jīng)元來(lái)檢測(cè)單個(gè)特征或特性。

這種系統(tǒng)用途更廣，處理錯(cuò)誤的能力更強(qiáng)，計(jì)算效率也高得多。

而且，研究人員還可以直接操作模型所考慮的想法和關(guān)系，從而更深入地了解它的推理過(guò)程。

今年3月，蘇黎世IBM研究院的團(tuán)隊(duì)，使用帶有神經(jīng)網(wǎng)絡(luò)的超維計(jì)算來(lái)解決抽象視覺(jué)推理中的一個(gè)經(jīng)典問(wèn)題——「瑞文的遞進(jìn)矩陣」。

它將幾何對(duì)象的圖像呈現(xiàn)在一個(gè)3x3的網(wǎng)格中。網(wǎng)格中的一個(gè)位置為空，對(duì)象必須從一組候選圖像中選擇最適合空白的圖像。

為了使用超維計(jì)算解決這個(gè)問(wèn)題，該團(tuán)隊(duì)首先創(chuàng)建了一個(gè)超向量字典來(lái)表示每幅圖像中的對(duì)象。

字典中的每個(gè)超向量代表一個(gè)對(duì)象及其屬性的某種組合。

然后，該團(tuán)隊(duì)訓(xùn)練神經(jīng)網(wǎng)絡(luò)來(lái)檢查圖像并生成一個(gè)雙極超向量，一個(gè)元素可以是+1或?1，它盡可能接近字典中超向量的某種疊加。

因此，生成的超向量包含關(guān)于圖像中所有對(duì)象及其屬性的信息。

他們提出的方法在一組問(wèn)題上的準(zhǔn)確率接近88%，而僅使用神經(jīng)網(wǎng)絡(luò)的解決方案的準(zhǔn)確率不到61%。

目前超維計(jì)算尚處于初期階段，但隨著其在更大規(guī)模的測(cè)試中的應(yīng)用，我們可能會(huì)看到這種新方法開(kāi)始展現(xiàn)其潛力。