寻找算法的真正潜力
2020-01-08 21:24

寻找算法的真正潜力

文章来自公众号:原理(ID:principia1687),作者:Rob Matheson,题图来自:图虫创意。


1


每学期,弗吉尼亚·威廉斯(Virginia Williams)教授都试图给她的计算机科学本科生上一堂“基础课”,告诉他们“数学是一切的基础”。


通常,选修威廉斯的算法入门课程的学生都是想要学习高阶的编程,不少学生希望有很多编程练习,或许还能应用到深度学习等算法,掌握前沿的计算技术。但相反,威廉斯的课程却和数学紧密相关,课上几乎没有编程内容,而是侧重于如何围绕核心数学模型和概念设计算法。


数学深深地影响了威廉斯的生活。作为两位数学家的孩子,她很早就爱上了这门学科。在她日后的研究生涯中,她也运用数学技能在计算机科学领域掀起了波澜。


2012年,她对一种用于矩阵相乘的算法进行了改进。矩阵乘法是计算机科学中的一种基本运算,而威廉斯的算法被认为是24年来最快的迭代。几年后,她和其他科学家共同建立了一个新兴领域,名为“细粒度复杂性”(fine-grained complexity),试图在某种程度上解释某些算法解决各种问题最快能有多快。


她现在从事的关于矩阵乘法的研究工作略有变化,已经转变为证明现有技术“已经再好不过了”。她说:“我们无法再提高我们自己的算法的表现,所以我们想出了一些方法来解释为什么我们不能,以及为什么其他方法也不能提高表现。”


2


威廉斯在保加利亚长大,她从小热爱数学,在学校里是一名极具天赋的学生。1999年,威廉斯考入加州理工学院。在大二的时候,她被计算机科学这一新领域吸引。她第一次上编程课就爱上了这门课程。她着迷于矩阵乘法的算法,这些算法的核心是一些繁重的数学运算。


矩阵乘法的算法会对一些与数据相对应的多个数组进行计算,并输出一个含有一些目标值的组合矩阵。这种算法应用广泛,包括计算机图形学、产品设计、人工智能和生物技术。2012年,她针对矩阵乘法开发了一种新的算法,比库珀史密斯-威诺格拉德算法(Coppersmith-Winograd algorithm)更快,后者自20世纪80年代以来在矩阵乘法中占据主导地位。威廉斯的方法减少了矩阵相乘所需的步骤。她的算法只比目前的记录保持者稍慢一点。


在2010到2015年间,威廉斯和她的丈夫、MIT教授赖恩·威廉斯(Ryan Williams)成为“细粒度复杂性”领域的主要奠基人。


“计算复杂性”中的更早领域所研究的,是基于算法在解决一个问题时所需的计算步骤的阈值,来发现一些有效的算法,以及可能低效的算法。而细粒度复杂性目标是将原先的定性区别细化为定量指导,以找到解决问题所需的确切时间。细粒度复杂性还通过计算等价性将问题归类在一起,可以更好地证明算法是否真的是最优解。


例如,有问题A和问题B,表面上看起来,这两个问题可能在它们所要解决的内容,以及算法所需的步骤上非常不同。但细粒度复杂性表明它们的背后其实是一样的。因此,如果解决问题A的算法存在更少步骤的可能,那么问题B也一定存在一种步骤更少的算法,反之亦然。另一方面,如果一个问题存在可证明的最优算法,那么所有等价问题都有最优算法。如果有人找到一个更快的算法来解决一个问题,那所有等价问题都可以被更快地解决。


自从他们共同开创这个领域以来,它已经逐渐壮大。目前,许多研究生和科研人员都在从事与细粒度复杂度相关的工作。威廉斯也在尝试在其他学科中引入细粒度复杂性的想法。


3


威廉斯的另一个感兴趣的课题是“计算社会选择”(computational social choice)。她主要研究的是对体育赛事、投票方案等系统进行操纵时所需的计算复杂性。在这些系统中,竞争对手成对出现。威廉斯作为一个网球爱好者,在2010年发表了一篇论文,她发现操纵一个淘汰赛让某一位运动员赢得比赛其实并不复杂,这取决于对配对比赛的胜利者的准确预测和其他一些因素。


2019年,她与其他科学家合著了一篇论文,表明赛事组织者可以通过某种最初的赛事安排,并在特定的预算内贿赂某些顶级选手,来确保一个最受欢迎的选手赢得比赛。尽管模拟所有可能的组合来操纵这些方案非常复杂,但威廉斯说:“当我需要从平时的工作中解脱出来时,我就钻研这个领域。这是一个有趣的节奏变化。”


现如今,由于计算机的普及,威廉斯的研究生进入她的课堂时所掌握的计算机科学方面的经验,比她同龄时要丰富得多。威廉斯表示,她希望在算法课堂有限的时间里,让学生能看到一点数学之美,因为数学让我们看到一切是如何在一起协作的,以及为什么会这样。


威廉斯说:“为了做好研究,你必须沉迷于一个问题。我希望他们能在我的课程中找到一些能让他们为之着迷的东西。”


参考链接:

http://news.mit.edu/2020/virginia-williams-professor-0107

https://simons.berkeley.edu/programs/complexity2015


文章来自公众号:原理(ID:principia1687),作者:Rob Matheson。

本内容为作者独立观点,不代表虎嗅立场。未经允许不得转载,授权事宜请联系hezuo@huxiu.com
如对本稿件有异议或投诉,请联系tougao@huxiu.com
正在改变与想要改变世界的人,都在 虎嗅APP
赞赏
关闭赞赏 开启赞赏

支持一下   修改

确定