2022年，計算機領域發(fā)生很多劃時代的大事。
在今年，計算機科學家學會了完美傳輸秘密，Transformer的進步神速，在AI的幫助下，數(shù)十年歷史的算法被大大改進……
現(xiàn)在，計算機科學家能解決的問題，范圍是越來越廣了，因此，他們的工作也越來越跨學科。
今年，許多計算機科學領域的成果，還助力了其他科學家和數(shù)學家。
比如密碼學問題，這涉及了整個互聯(lián)網(wǎng)的安全。
密碼學的背后，往往是復雜的數(shù)學問題。曾經(jīng)有一種非常有前途的新密碼方案，被認為足以抵御來自量子計算機的攻擊，然而，這個方案被「兩條橢圓曲線的乘積及其與阿貝爾曲面的關系」這個數(shù)學問題推翻了。
以單向函數(shù)的形式出現(xiàn)的一組不同的數(shù)學關系，將告訴密碼學家是否有真正安全的代碼。
計算機科學，尤其是量子計算，與物理學也有很大的重疊。
今年理論計算機科學的一件大事，就是科學家證明了NLTS猜想。
這個猜想告訴我們，粒子之間幽靈般的量子糾纏，并不像物理學家曾經(jīng)想象的那樣微妙。
這不僅影響了對我們對物理世界的理解，也影響了糾纏所帶來的無數(shù)密碼學的可能性。
另外，人工智能一直與生物學相得益彰——事實上，生物學領域就是從人腦中汲取靈感，人腦也許是最終極的計算機。
長久以來，計算機科學家和神經(jīng)科學家都希望了解大腦的工作原理，創(chuàng)造出類腦的人工智能，但這些似乎一直是白日夢。
但不可思議的是，Transformer神經(jīng)網(wǎng)絡似乎可以像大腦一樣處理信息。每當我們多了解一些Transformer的工作原理，就更了解大腦一些，反之亦然。
或許這就是為什么Transformer在語言處理和圖像分類上如此出色的原因。
甚至，AI還可以幫我們創(chuàng)造更好的AI，新的超網(wǎng)絡（hypernetworks）可以幫助研究人員以更低的成本、用更快的速度訓練神經(jīng)網(wǎng)絡，還能幫到其他領域的科學家。
量子糾纏是一種將遙遠的粒子緊密聯(lián)系起來的特性，可以肯定的是，一個完全糾纏的系統(tǒng)是無法被完全描述的。
不過物理學家認為，那些接近完全糾纏的系統(tǒng)會更容易描述。但計算機科學家則認為，這些系統(tǒng)同樣不可能被計算出來，而這就是量子PCP（概率可檢測證明，Probabilistically Checkable Proof）猜想。
為了幫助證明量子PCP理論，科學家們提出了一個更簡單的假設，被稱為「非低能平凡態(tài)」（NLTS）猜想。
今年6月，來自哈佛大學、倫敦大學學院和加州大學伯克利分校對三位計算機科學家，在一篇論文中首次實現(xiàn)了NLTS猜想的證明。
論文地址：https://arxiv.org/abs/2206.13228
這意味著存在可在更高的溫度下保持糾纏態(tài)的量子系統(tǒng)，同時也表明，即使遠離低溫等極端情況，糾纏粒子系統(tǒng)仍然難以分析，難以計算基態(tài)能量。
物理學家們很驚訝，因為這意味著糾纏不一定像他們想象的那樣脆弱，而計算機科學家們很高興離證明一個被稱為量子PCP（概率可檢測證明）定理的證明又近了一步。
今年10月，研究人員成功地將三個粒子在相當遠的距離上糾纏在一起，加強了量子加密的可能性。
在過去的五年里，Transformer徹底改變了AI處理信息的方式。
在2017年，Transformer首次出現(xiàn)在一篇論文中。
人們開發(fā)Transformer，是為了理解和生成語言。它可以實時處理輸入數(shù)據(jù)中的每一個元素，讓它們具有「大局觀」。
與其他采取零散方法的語言網(wǎng)絡相比，這種「大局觀」讓Transformer的速度和準確性大大提高。
這也使得它具有不可思議的通用性，其他的AI的研究人員，也把Transformer應用于自己的領域。
他們已經(jīng)發(fā)現(xiàn)，應用同樣的原理，可以用來升級圖像分類和同時處理多種數(shù)據(jù)的工具。
論文地址：https://arxiv.org/abs/2010.11929
Transformers迅速成為專注于分析和預測文本的單詞識別等應用程序的領跑者。它引發(fā)了一波工具浪潮，例如 OpenAI的GPT-3，它訓練數(shù)千億個單詞并生成一致的新文本，達到令人不安的程度。
不過，跟非Transformer模型相比，這些好處是以Transformer更多的訓練量為代價的。
這些人臉是由基于Transformer的網(wǎng)絡，在對超過20萬張名人面孔的數(shù)據(jù)集進行訓練后創(chuàng)建的
在今年3月，研究Transformer工作原理的研究人員發(fā)現(xiàn)，它之所以如此強大，部分原因是它將更大的意義附加到詞語上的能力，而不是簡單的記憶模式。
事實上，Transformer的適應性如此之強，神經(jīng)科學家已經(jīng)開始用基于Transformer的網(wǎng)絡對人腦功能進行建模。
量子計算的出現(xiàn)，讓很多原本需要消耗超大計算量的問題都得到了解決，而經(jīng)典加密算法的安全性也因此受到了威脅。于是，學界便提出了后量子密碼的概念，來抵抗量子計算機的破解。
作為備受期待的加密算法，SIKE（Supersingular Isogeny Key Encapsulation）是一種利用橢圓曲線作為定理的加密算法。
然而就在今年7月，兩位來自比利時魯汶大學的研究人員發(fā)現(xiàn)，這個算法可以在短短1個小時內(nèi)，用一臺10年「高齡」的臺式計算機被成功破解。
值得注意的是，研究人員從純數(shù)學的角度來解決這個問題，攻擊算法設計的核心，而不是任何潛在的代碼漏洞。
論文地址：https://eprint.iacr.org/2022/975
對此，研究人員表示，只有當你能證明「單向函數(shù)」的存在時，才有可能創(chuàng)建一個可證明的安全代碼，也就是一個永遠不可能失敗的代碼。
雖然現(xiàn)在仍然不知道它們是否存在，但研究人員認為，這個問題等同于另一個叫做Kolmogorov復雜性的問題。只有當某一版本的Kolmogorov復雜性難以計算時，單向函數(shù)和真正的密碼學才有可能。
近年來，人工神經(jīng)網(wǎng)絡的模式識別技能，為人工智能領域注入了活力。
但在一個網(wǎng)絡開始工作之前，研究人員必須首先訓練它。
這個訓練過程可能會持續(xù)數(shù)月，需要大量數(shù)據(jù)，在這個過程中，需要對潛在的數(shù)十億個參數(shù)進行微調(diào)。
現(xiàn)在，研究人員有了一個新的想法——讓機器替他們來做這件事。
這種新型「超網(wǎng)絡」叫做GHN-2，它能夠處理和吐出其他網(wǎng)絡。
論文鏈接：https://arxiv.org/abs/2110.13100
它的速度很快，能夠分析任何指定的網(wǎng)絡，并迅速提供一組參數(shù)值，這些參數(shù)值和以傳統(tǒng)方式訓練的網(wǎng)絡中的參數(shù)，一樣有效。
盡管GHN-2提供的參數(shù)可能不是最佳的，但它仍然提供了一個更理想的起點，減少了全面訓練所需的時間和數(shù)據(jù)。
通過在給定的圖像數(shù)據(jù)集和我們的DEEPNETS-1M架構(gòu)數(shù)據(jù)集上預測的參數(shù)進行反向傳播訓練
今年夏天，Quanta雜志還研究了另一種幫助機器學習的新方法——具身人工智能。
它允許算法從響應迅速的三維環(huán)境中學習，而不是通過靜態(tài)圖像或抽象數(shù)據(jù)。
無論是探索模擬世界的代理，還是真實世界中的機器人，這些系統(tǒng)擁有從根本上不同的學習方式，而且在許多情況下，這些方式比使用傳統(tǒng)方法訓練的系統(tǒng)更好。
提高基礎計算算法的效率一直都是學界熱點，因為它會影響大量計算的整體速度，從而對智能計算領域產(chǎn)生多米諾骨牌式的效應。
今年10月，DeepMind團隊在發(fā)表于Nature上的論文中，提出了第一個用于為矩陣乘法等基本計算任務發(fā)現(xiàn)新穎、高效、正確算法的AI系統(tǒng)——AlphaTensor。
它的出現(xiàn)，為一個50年來的懸而未決的數(shù)學問題找到了新答案：找到兩個矩陣相乘的最快方法。
矩陣乘法，作為矩陣變換的基礎運算之一，是是許多計算任務的核心組成部分。其中涵蓋了計算機圖形、數(shù)字通信、神經(jīng)網(wǎng)絡訓練和科學計算等等，而AlphaTensor發(fā)現(xiàn)的算法可以使這些領域的計算效率大大提升。
論文地址：https://www.nature.com/articles/s41586-022-05172-4
今年3月，由六位計算機科學家組成的團隊提出了一種「快得離譜」的算法，讓計算機最古老的「最大流問題」獲得了突破性的進展。
新算法可在「幾乎線性」的時間內(nèi)解決這個問題，也就是說，其運行時間基本與記錄網(wǎng)絡細節(jié)所需的時間正比。
論文地址：https://arxiv.org/abs/2203.00671v2
最大流問題是一種組合最優(yōu)化問題，討論的是如何充分利用裝置的能力使得運輸?shù)牧髁孔畲螅M而取得最好的效果。
在日常生活中，它在很多方面都有應用，如互聯(lián)網(wǎng)數(shù)據(jù)流、航空公司調(diào)度，甚至包含將求職者與空缺職位進行匹配等等。
作為論文的作者之一，來自耶魯大學的Daniel Spielman表示，「我原本堅信，這個問題不可能存在如此高效的算法?！?/section>
普林斯頓大學的理論計算機科學家Mark Braverman，花了一生中超過四分之一的時間，來研究交互式通信的新理論。
他的工作使研究人員能夠?qū)Α感畔ⅰ购汀钢R」等術語進行量化，這不僅使人們在理論上對互動有了更多的了解，而且還創(chuàng)造了新的技術，使交流更加高效和準確。
Braverman最喜歡在辦公室的沙發(fā)上思考量化的難題
由于他的這一成就，以及其他成果，國際數(shù)學聯(lián)盟今年7月授予Braverman IMU Abacus獎章，這是理論計算機科學領域的最高榮譽之一。
IMU的頒獎詞指出，Braverman對信息復雜性的貢獻，使人們更深入地了解了當兩方相互溝通時，信息成本的不同衡量標準。
他的工作為不易受傳輸錯誤影響的新編碼策略，以及在傳輸和操作過程中壓縮數(shù)據(jù)的新方法，鋪平了道路。
信息復雜性問題，來自于Claude Shannon的開拓性工作——在1948年，他為一個人通過通道向另一個人發(fā)送消息，制定了數(shù)學框架。
而Braverman最大的貢獻在于，建立了一個廣泛的框架，該框架闡明了描述交互式通信邊界的通用規(guī)則——這些規(guī)則提出了在通過算法在線發(fā)送數(shù)據(jù)時，壓縮和保護數(shù)據(jù)的新策略。
論文地址：https://arxiv.org/abs/1106.3595
「交互式壓縮」問題可以這么理解：如果兩個人交換一百萬條短信，但只學習1,000位信息，交換是否可以壓縮為1,000位守恒？
Braverman和Rao的研究表明，答案是否定的。
而Braverman不僅破解了這些問題，他還引入了一種新的視角，使研究人員能夠首先闡明它們，然后將它們翻譯成數(shù)學的正式語言。
他的理論為探索這些問題和確定可能出現(xiàn)在未來技術中的新通信協(xié)議，奠定了基礎。
更多詳細信息，請您微信關注“計算網(wǎng)”公眾號：
