靠「猜」答案获得顶会最佳论文,华人IOI金牌获得者找到复杂「鸡兔同笼」最简解法
共 3242字,需浏览 7分钟
·
2021-03-14 22:12
![](https://filescdn.proginn.com/4c6d390a558df701147935c778e2e590/48f31af57360f5de53ca00aa0b0e5d5d.webp)
极市导读
计算机理论顶会SODA 2021的最佳论文,用“猜”答案的方式,一口气把算法复杂度减小到了O(n2.3316)! >>加入极市CV技术交流群,走在计算机视觉的最前沿
还记得小时候被“鸡兔同笼”支配的恐惧吗?其实,当我们学习了二元一次方程,就知道这个问题并不复杂:
不过,可别小看了这样的线性方程,试想一下,如果动物的种类不止2种,特征也不只头和脚呢?比如……
这个时候,我们就只能求助矩阵乘法了。
那么,问题来了,采用高斯消元法,求解的复杂度就是O(n^3)。
也就是说,如果n从2增加到4,求解复杂度就会增加2³即8倍。
n越来越大,计算的步骤就会以3次方的速度快速增加……想想机器学习、工程项目里极其复杂的矩阵乘法,是不是有点头皮发麻的感觉。
好消息是,现在,这个困扰工程师们已久的基础问题,有了突破性进展。
计算机理论顶会SODA 2021的最佳论文,用“猜”答案的方式,一口气把算法复杂度减小到了O(n2.3316)!
论文作者,是来自佐治亚理工学院的两位数学家:彭泱和Santosh Vempala。
这项研究具体是怎么一回事?快来一起研究研究。
IOI金牌获得者,靠“猜”推动研究
IOI金牌获得者、来自佐治亚理工学院的助理教授彭泱,和他的合作者Santosh Vempala共同提出了一种全新的思路。
相比于此前,数学家们不停地改进矩阵乘法的算法,他们别出心裁,想到能否靠“猜”,来重新设计一种算法。这种方法就是:猜测每个未知数的值,把它们代入方程后,查看结果与实际值相差有多大。然后,修正未知数的值,再猜一次。这种方法,在计算机方向上被称为迭代法。
彭泱的这种迭代算法,在方程的数量变得极多、且每个方程涉及的未知数较少时,显示出了巨大的优势。也就是说,如果在一个系数矩阵属于“稀疏矩阵”——矩阵本身特别大,但相对地,系数为0的数量又非常多的时候,迭代法就会出现神奇的结果。
此前,没有人能够证明,“迭代法”对于稀疏矩阵而言,是否会比“矩阵乘法”更快。当然,这种算法并不只靠“猜”。彭泱设计的算法中,他们还会在给出多组随机数的同时,将这些随机数组并行计算。这就像是数百个人同时在山林中搜索宝藏,肯定比一个人反复搜索要更快。但这种算法的设计,还面临两个难点:如何保证设计出来的数,足够随机、不偏向问题的任何一部分?如何保证设计出来的这些随机数组,全面覆盖每一种可能性?
他们发现,正因为由随机数构造出的矩阵中,项数是随机的、且彼此之间有着某种关联,因此,这一矩阵本身就具有某种对称性。这就意味着,如果知道矩阵中某些具体的数值,就能推断出一整个矩阵的形状。这一发现,使得他们设计的算法,比未考虑矩阵对称性的那些算法,找到解的速度更快。事实证明,这种算法确实能够保证在O(n)复杂度以内,完成任何计算。这比之前的O(n),复杂度降低了不少,可以说是一个巨大的进步。
这一新发现,让彭泱和他的合作者获得了ACM-SIAM离散算法研讨会SODA 2021的最佳论文奖。
为什么要降低计算复杂度?
解一个二元一次方程,也就是2×2的矩阵,靠中学知识就能轻松搞定。然而当n变得越来越大,求解方程的计算量就会以3次方的速度迅速增加。这是什么概念?意味着如果线性问题中,要求解的未知数达到100甚至10000,那么计算量复杂度就会增加1000000、甚至10倍。目前,机器学习、动力学模拟等问题,都会遇到超大规模线性方程组,如何降低计算复杂度,一直是学者们致力于解决的问题。
要是计算复杂度居高不下,对于计算机而言,将会是一个巨大而沉重的负担。因此,数学家们一直在想方设法将线性问题的复杂度弄得更小一点,也就是让O(n)中的ω变小。哪怕ω减小的量只有0.00001,对于上百万未知数的方程组来说也是一个巨大的进步。通过不断改善矩阵乘法,ω先是从3降低到2.81,历经多次研究后,被MIT和哈佛的数学家们降低到2.37286。然而,到这个阶段,数学家们倾尽全力所设计的新算法,也只是将ω降低了0.00001而已。有数学家进行过预测,ω可以无限接近于2,也就意味着这种线性问题的计算复杂度还能尽力向O(n²)靠拢。因此,彭泱他们的新算法,可以说是将这一研究向前推动了一大步。
关于作者
论文作者彭泱,江苏南京人,现为佐治亚理工学院计算机科学系助理教授。他本科毕业于滑铁卢大学数学专业,其后在CMU拿下计算机科学博士学位。2013-2015年在MIT担任应用数学博士后。目前,他主要关注的研究方向是高效算法的设计、分析和实现。根据Google Scholar,彭泱的论文引用数为2788,h指数为28。
他的名字,也频频见于FOCS、STOC、SODA等计算机理论顶会论文当中。
彭泱与数学和计算机结缘很早,据中国侨网报道,他8年级时就曾参加10年级水平的美国数学比赛,并获得满分的成绩。还在2004年和2005年参加加拿大计算机竞赛,摘下金牌。2005年和2006年,彭泱代表加拿大队参加国际奥林匹克数学竞赛(IMO),分别获得银牌和铜牌。
而在此期间,他还参与了2004、2005和2006年的国际奥林匹克信息学竞赛(IOI),并在2005年获得金牌。
论文的另一位作者Santosh Vempala是著名计算机科学家,佐治亚理工学院计算机科学杰出教授。2015年,他入选“因对凸集和概率分布算法的贡献”入选ACM Fellow。
他的主要研究方向是算法理论,用于抽样、学习、优化和数据分析的算法工具,高维几何,随机线性代数等。
Santosh Vempala还是古根海姆奖、斯隆奖获得者。
论文地址:
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
推荐阅读
2021-03-08
![](https://filescdn.proginn.com/f8a59a27981a9f2991e3285d5252cb26/43a15a1737468dbda4cfcb6f95ec71d3.webp)
2021-03-08
![](https://filescdn.proginn.com/beb06c330115a2742b319cfac264b396/94fec611a7d5e092e856a46a03ad7c88.webp)
2021-03-08
![](https://filescdn.proginn.com/4acc039093c5de0b0ad452a6fc0bd1af/9a0a81e5cad855bc0719fce816da50f4.webp)
![](https://filescdn.proginn.com/0af59cfbcab876b92e0b748765f64430/d49122e59d9c62e41b5c75f11d14e748.webp)
# CV技术社群邀请函 #
备注:姓名-学校/公司-研究方向-城市(如:小极-北大-目标检测-深圳)
即可申请加入极市目标检测/图像分割/工业检测/人脸/医学影像/3D/SLAM/自动驾驶/超分辨率/姿态估计/ReID/GAN/图像增强/OCR/视频理解等技术交流群
每月大咖直播分享、真实项目需求对接、求职内推、算法竞赛、干货资讯汇总、与 10000+来自港科大、北大、清华、中科院、CMU、腾讯、百度等名校名企视觉开发者互动交流~
![](https://filescdn.proginn.com/5b9e202ff0bbde49b092f23ff77e7100/dc2e72f03e0f6905ba7e1026d0cdacc7.webp)