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