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