靠「猜」答案獲得頂會(huì)最佳論文，華人IOI金牌獲得者找到復(fù)雜「雞兔同籠」最簡(jiǎn)解法
來(lái)源 ： 量子位
還記得小時(shí)候被“雞兔同籠”支配的恐懼嗎？
其實(shí)，當(dāng)我們學(xué)習(xí)了二元一次方程，就知道這個(gè)問(wèn)題并不復(fù)雜：
不過(guò)，可別小看了這樣的線性方程，試想一下，如果動(dòng)物的種類(lèi)不止2種，特征也不只頭和腳呢？
比如……
這個(gè)時(shí)候，我們就只能求助矩陣乘法了。
那么，問(wèn)題來(lái)了，采用高斯消元法，求解的復(fù)雜度就是O(n3)。
也就是說(shuō)，如果n從2增加到4，求解復(fù)雜度就會(huì)增加23即8倍。
n越來(lái)越大，計(jì)算的步驟就會(huì)以3次方的速度快速增加……
想想機(jī)器學(xué)習(xí)、工程項(xiàng)目里極其復(fù)雜的矩陣乘法，是不是有點(diǎn)頭皮發(fā)麻的感覺(jué)。
好消息是，現(xiàn)在，這個(gè)困擾工程師們已久的基礎(chǔ)問(wèn)題，有了突破性進(jìn)展。
計(jì)算機(jī)理論頂會(huì)SODA 2021的最佳論文，用“猜”答案的方式，一口氣把算法復(fù)雜度減小到了O(n2.3316)！
論文作者，是來(lái)自佐治亞理工學(xué)院的兩位數(shù)學(xué)家：彭泱和Santosh Vempala。
這項(xiàng)研究具體是怎么一回事？快來(lái)一起研究研究。
IOI金牌獲得者，靠“猜”推動(dòng)研究
IOI金牌獲得者、來(lái)自佐治亞理工學(xué)院的助理教授彭泱，和他的合作者Santosh Vempala共同提出了一種全新的思路。
相比于此前，數(shù)學(xué)家們不停地改進(jìn)矩陣乘法的算法，他們別出心裁，想到能否靠“猜”，來(lái)重新設(shè)計(jì)一種算法。
這種方法就是：猜測(cè)每個(gè)未知數(shù)的值，把它們代入方程后，查看結(jié)果與實(shí)際值相差有多大。
然后，修正未知數(shù)的值，再猜一次。
這種方法，在計(jì)算機(jī)方向上被稱為迭代法。
彭泱的這種迭代算法，在方程的數(shù)量變得極多、且每個(gè)方程涉及的未知數(shù)較少時(shí)，顯示出了巨大的優(yōu)勢(shì)。
也就是說(shuō)，如果在一個(gè)系數(shù)矩陣屬于“稀疏矩陣”——矩陣本身特別大，但相對(duì)地，系數(shù)為0的數(shù)量又非常多的時(shí)候，迭代法就會(huì)出現(xiàn)神奇的結(jié)果。
此前，沒(méi)有人能夠證明，“迭代法”對(duì)于稀疏矩陣而言，是否會(huì)比“矩陣乘法”更快。
當(dāng)然，這種算法并不只靠“猜”。
彭泱設(shè)計(jì)的算法中，他們還會(huì)在給出多組隨機(jī)數(shù)的同時(shí)，將這些隨機(jī)數(shù)組并行計(jì)算。
這就像是數(shù)百個(gè)人同時(shí)在山林中搜索寶藏，肯定比一個(gè)人反復(fù)搜索要更快。
但這種算法的設(shè)計(jì)，還面臨兩個(gè)難點(diǎn)：
如何保證設(shè)計(jì)出來(lái)的數(shù)，足夠隨機(jī)、不偏向問(wèn)題的任何一部分？
如何保證設(shè)計(jì)出來(lái)的這些隨機(jī)數(shù)組，全面覆蓋每一種可能性？
他們發(fā)現(xiàn)，正因?yàn)橛呻S機(jī)數(shù)構(gòu)造出的矩陣中，項(xiàng)數(shù)是隨機(jī)的、且彼此之間有著某種關(guān)聯(lián)，因此，這一矩陣本身就具有某種對(duì)稱性。
這就意味著，如果知道矩陣中某些具體的數(shù)值，就能推斷出一整個(gè)矩陣的形狀。
這一發(fā)現(xiàn)，使得他們?cè)O(shè)計(jì)的算法，比未考慮矩陣對(duì)稱性的那些算法，找到解的速度更快。
事實(shí)證明，這種算法確實(shí)能夠保證在O(n2.3316)復(fù)雜度以內(nèi)，完成任何計(jì)算。
這比之前的O(n2.37286)，復(fù)雜度降低了不少，可以說(shuō)是一個(gè)巨大的進(jìn)步。
這一新發(fā)現(xiàn)，讓彭泱和他的合作者獲得了ACM-SIAM離散算法研討會(huì)SODA 2021的最佳論文獎(jiǎng)。
為什么要降低計(jì)算復(fù)雜度？
解一個(gè)二元一次方程，也就是2×2的矩陣，靠中學(xué)知識(shí)就能輕松搞定。
然而當(dāng)n變得越來(lái)越大，求解方程的計(jì)算量就會(huì)以3次方的速度迅速增加。
這是什么概念？
意味著如果線性問(wèn)題中，要求解的未知數(shù)達(dá)到100甚至10000，那么計(jì)算量復(fù)雜度就會(huì)增加1000000、甚至1012倍。
目前，機(jī)器學(xué)習(xí)、動(dòng)力學(xué)模擬等問(wèn)題，都會(huì)遇到超大規(guī)模線性方程組，如何降低計(jì)算復(fù)雜度，一直是學(xué)者們致力于解決的問(wèn)題。
要是計(jì)算復(fù)雜度居高不下，對(duì)于計(jì)算機(jī)而言，將會(huì)是一個(gè)巨大而沉重的負(fù)擔(dān)。
因此，數(shù)學(xué)家們一直在想方設(shè)法將線性問(wèn)題的復(fù)雜度弄得更小一點(diǎn)，也就是讓O(nω)中的ω變小。
哪怕ω減小的量只有0.00001，對(duì)于上百萬(wàn)未知數(shù)的方程組來(lái)說(shuō)也是一個(gè)巨大的進(jìn)步。
通過(guò)不斷改善矩陣乘法，ω先是從3降低到2.81，歷經(jīng)多次研究后，被MIT和哈佛的數(shù)學(xué)家們降低到2.37286。
然而，到這個(gè)階段，數(shù)學(xué)家們傾盡全力所設(shè)計(jì)的新算法，也只是將ω降低了0.00001而已。
有數(shù)學(xué)家進(jìn)行過(guò)預(yù)測(cè)，ω可以無(wú)限接近于2，也就意味著這種線性問(wèn)題的計(jì)算復(fù)雜度還能盡力向O(n2)靠攏。
因此，彭泱他們的新算法，可以說(shuō)是將這一研究向前推動(dòng)了一大步。
關(guān)于作者
論文作者彭泱，江蘇南京人，現(xiàn)為佐治亞理工學(xué)院計(jì)算機(jī)科學(xué)系助理教授。
他本科畢業(yè)于滑鐵盧大學(xué)數(shù)學(xué)專(zhuān)業(yè)，其后在CMU拿下計(jì)算機(jī)科學(xué)博士學(xué)位。2013-2015年在MIT擔(dān)任應(yīng)用數(shù)學(xué)博士后。
目前，他主要關(guān)注的研究方向是高效算法的設(shè)計(jì)、分析和實(shí)現(xiàn)。
根據(jù)Google Scholar，彭泱的論文引用數(shù)為2788，h指數(shù)為28。
他的名字，也頻頻見(jiàn)于FOCS、STOC、SODA等計(jì)算機(jī)理論頂會(huì)論文當(dāng)中。
彭泱與數(shù)學(xué)和計(jì)算機(jī)結(jié)緣很早，據(jù)中國(guó)僑網(wǎng)報(bào)道，他8年級(jí)時(shí)就曾參加10年級(jí)水平的美國(guó)數(shù)學(xué)比賽，并獲得滿分的成績(jī)。還在2004年和2005年參加加拿大計(jì)算機(jī)競(jìng)賽，摘下金牌。
2005年和2006年，彭泱代表加拿大隊(duì)參加國(guó)際奧林匹克數(shù)學(xué)競(jìng)賽（IMO），分別獲得銀牌和銅牌。
而在此期間，他還參與了2004、2005和2006年的國(guó)際奧林匹克信息學(xué)競(jìng)賽（IOI），并在2005年獲得金牌。
論文的另一位作者Santosh Vempala是著名計(jì)算機(jī)科學(xué)家，佐治亞理工學(xué)院計(jì)算機(jī)科學(xué)杰出教授。2015年，他入選“因?qū)ν辜透怕史植妓惴ǖ呢暙I(xiàn)”入選ACM Fellow。
他的主要研究方向是算法理論，用于抽樣、學(xué)習(xí)、優(yōu)化和數(shù)據(jù)分析的算法工具，高維幾何，隨機(jī)線性代數(shù)等。
Santosh Vempala還是古根海姆獎(jiǎng)、斯隆獎(jiǎng)獲得者。
論文地址：
https://arxiv.org/abs/2007.10254
參考鏈接：
[1]https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/
[2]https://www.cc.gatech.edu/~rpeng/
[3]http://www.arc.gatech.edu/
[4]https://www.chinaqw.com/node2/node2796/node2882/node3156/userobject6ai253919.html
[5]https://www.siam.org/conferences/cm/conference/soda21
— 完 —