2023計(jì)算機(jī)科學(xué)7項(xiàng)重大突破！「P與NP」50年經(jīng)典難題，大模型密集涌現(xiàn)上榜
發(fā)布人：傳感器技術(shù)
時(shí)間：2023-12-24
來(lái)源：工程師
發(fā)布文章
加入技術(shù)交流群
掃碼加入
和技術(shù)大咖面對(duì)面交流
海量資料庫(kù)查詢
編輯：桃子 好困【導(dǎo)讀】2023年，計(jì)算機(jī)領(lǐng)域都發(fā)生了哪些大事？Quanta Magazine的年終盤點(diǎn)來(lái)了。
一年一度的年終盤點(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ò)一種普通類型的網(wǎng)絡(luò)，以最快速度找到最短路徑。此外，加密學(xué)家在與AI建立意想不到的連接時(shí)，展示了機(jī)器學(xué)習(xí)模型和機(jī)器生成內(nèi)容也必須應(yīng)對(duì)隱藏的漏洞和消息。 ，時(shí)長(zhǎng)10:58
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)題「很難」本身也這么困難。在回答這類內(nèi)省式問(wèn)題的努力中，出現(xiàn)了一個(gè)新興的領(lǐng)域「元復(fù)雜性」（meta-complexity）理論。它為這個(gè)問(wèn)題提供了迄今為止最好的見(jiàn)解。8月，Quanta一篇文章中曾介紹了「元復(fù)雜性」的理念，以及科學(xué)家們開(kāi)始的探索。
通過(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，最后給出答案。
總而言之，揭開(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á)到的速度。
此外，今年的其他重大算法新聞還包括，通過(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ò)碼（稱為低密度奇偶校驗(yàn)碼）的效率，至少是現(xiàn)行標(biāo)準(zhǔn)的10倍。Top 6：密碼學(xué)+AI的隱藏秘密
在密碼學(xué)和人工智能交叉領(lǐng)域的一項(xiàng)不尋常研究中。最近，一組計(jì)算機(jī)科學(xué)家證明了可以在機(jī)器學(xué)習(xí)模型中嵌入后門，這些后門不僅幾乎無(wú)法被發(fā)現(xiàn)，而且它們的隱蔽性得到了類似于現(xiàn)代最先進(jìn)加密技術(shù)的邏輯支持。
不過(guò)，團(tuán)隊(duì)主要研究的是較簡(jiǎn)單的模型，因此目前還不清楚這一發(fā)現(xiàn)是否也適用于當(dāng)今AI技術(shù)中使用的更復(fù)雜的模型。然而，這些研究成果為未來(lái)系統(tǒng)如何防御這類安全漏洞提供了可能的方向。正是因?yàn)檫@類安全問(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)其潛力。來(lái)源：新智元*博客內(nèi)容為網(wǎng)友個(gè)人發(fā)布，僅代表博主個(gè)人觀點(diǎn)，如有侵權(quán)請(qǐng)聯(lián)系工作人員刪除。
