MIT新研究：43%算法改進(jìn)速度超摩爾定律，解決超大規(guī)模問(wèn)題，算法比硬件更有用
這是MIT研究1137篇論文后得到的結(jié)果
博雯 發(fā)自 凹非寺
量子位 報(bào)道 | 公眾號(hào) QbitAI
軟件算法對(duì)計(jì)算速度的提升有多大？
MIT最新研究說(shuō)：超過(guò)4成算法對(duì)性能的改進(jìn)，已經(jīng)超過(guò)了硬件的摩爾定律。
對(duì)于中等規(guī)模的問(wèn)題，30%-43%的算法的改進(jìn)比硬件進(jìn)步更能提升性能。
當(dāng)問(wèn)題數(shù)據(jù)增加到數(shù)億規(guī)模時(shí)，算法改進(jìn)變得比硬件改進(jìn)/摩爾定律更重要。
這就是MIT的兩位科學(xué)家對(duì)來(lái)自57本教科書(shū)，超過(guò)1137篇研究論文的數(shù)據(jù)進(jìn)行分析后得到的結(jié)論。
不僅如此，他們還全面敘述了現(xiàn)有以及歷史上的算法何時(shí)被發(fā)現(xiàn)、如何改進(jìn)、以及改進(jìn)的規(guī)模。
14%的算法改進(jìn)率超過(guò)1000%
研究者通過(guò)分析QS排名中前20的計(jì)算機(jī)名校所用的課件，總結(jié)出11個(gè)算法子領(lǐng)域：
組合學(xué)、統(tǒng)計(jì)學(xué)/機(jī)器學(xué)習(xí)、密碼學(xué)、數(shù)值分析、數(shù)據(jù)庫(kù)、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)、機(jī)器人學(xué)、信號(hào)處理、計(jì)算機(jī)圖形/圖像處理、生物信息學(xué)。
通過(guò)分析子領(lǐng)域中的算法教材、學(xué)術(shù)期刊、已發(fā)表論文等信息，研究者劃分出了113個(gè)算法家族，平均每個(gè)家族8個(gè)算法。
他們首先統(tǒng)計(jì)了從1940年到現(xiàn)在，各種算法的最初提出時(shí)間：
并且根據(jù)這些算法最初被提出時(shí)的時(shí)間復(fù)雜度進(jìn)行了歸納?？梢钥吹?，其中31%的算法屬于指數(shù)復(fù)雜度類別：
在時(shí)間復(fù)雜度的改進(jìn)上，對(duì)于n=100萬(wàn)的問(wèn)題規(guī)模，一些算法比硬件或摩爾定律的改進(jìn)率更高：
將這一分析拓展到110個(gè)算法家族上時(shí)，可以看到，對(duì)于中等規(guī)模（n=1000）的問(wèn)題來(lái)說(shuō)，只有18%的算法改進(jìn)率快于硬件。
但當(dāng)問(wèn)題規(guī)模來(lái)到了百萬(wàn)、億、甚至萬(wàn)億級(jí)別時(shí)，算法的改進(jìn)速度就超過(guò)了硬件性能。
甚至有14%的算法家族的改進(jìn)率超過(guò)1000%，遠(yuǎn)超硬件改進(jìn)所帶來(lái)的性能提升。
作者介紹
論文一作Yash Sherry本科畢業(yè)于印度德里大學(xué)計(jì)算機(jī)科學(xué)專業(yè)，現(xiàn)在是MIT斯隆商學(xué)院的一位研究員，工作重點(diǎn)是跟蹤算法的改進(jìn)及其對(duì)IT公司經(jīng)濟(jì)的影響。
另一位Neil Thompson是麻省理工大學(xué)CSAIL（計(jì)算機(jī)科學(xué)和人工智能實(shí)驗(yàn)室）的科學(xué)家，也是哈佛大學(xué)創(chuàng)新科學(xué)實(shí)驗(yàn)室的客座教授。
論文：
https://ieeexplore.ieee.org/document/9540991
參考鏈接：
https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920
相關(guān)閱讀
OpenAI提出的新摩爾定律怎樣理解？中國(guó)隱藏算力巨頭有話說(shuō)
Sam Altman：宇宙中的智能每18個(gè)月翻一番
提升12倍！香港浸會(huì)大學(xué)與MassGrid發(fā)布低帶寬高效AI訓(xùn)練新算法
目前實(shí)驗(yàn)結(jié)果及相關(guān)論文已被ICDCS workshop收錄
谷歌實(shí)現(xiàn)2種新的強(qiáng)化學(xué)習(xí)算法，“比肩”DQN，泛化性能更佳?。麵CLR 2021
受到神經(jīng)架構(gòu)搜索（NAS）啟發(fā)
