还用「臭皮匠顶诸葛亮」解释博弈求和证明

詹士 发自 凹非寺

非常AI | 公众号 QbitAI

两度获得理论计算机科学最高荣誉哥德尔奖，将75年前算法的理论做改进，并一直用到今天——

他叫滕尚华，南加州大学教授，美国计算机协会会士（ACM fellow），上交大校友。

△ 图源：quantamagazine

在与另一位理论计算机科学家Spielman的长期合作下，他于2008年，以平滑分析理论的贡献获得哥德尔奖。

此后，二人又因网络系统中的近线性时间拉普拉斯算子求解器，于2015年，再次斩获领域内最高奖项。

多数人不知道的是，光环之外的日常生活工作中，滕尚华却是个“躺平”工作拥护者，熟悉三国，也喜欢玩游戏，这两天跟媒体聊天交流中，他还自曝曾用“三个臭皮匠顶个诸葛亮”描述研究工作。

△ 图源：南加大 维特比工程学院 官网

被使用75年的线性规划算法

作为计算机科学与数学教授，滕尚华研究的主要方向为—— 量子组合博弈、可扩展算法、网络分析、谱图论、算法平滑分析、计算经济学和博弈论。

其名下论文被引用次数上万。

诸多成果中，让他名声迅速被熟知的，莫过于在平滑分析理论方面的贡献——

利用平滑分析方式，滕尚华与合作伙伴Daniel Spielman破解了线性规划的单纯形算法的遗留问题。

具体来说，单纯形算法，是一种由美国应用数学家George Dantzig于1947年发明的算法，旨在为线性规划最优解问题寻找解决方案，因其实用又强大，一直以来被广泛应用于工业、科学等领域，经久不衰。

单纯形算法从原理可以理解为：

面向线性规划问题，在可行域范围内先找出一个顶点，根据一定规则判断是否为最优，若否，那就转而寻找与之相邻的顶点，再判断是否最优。如此进行下去，直到找到最优解。

△ 图源：wiki

时至今天，单纯形算法仍是线性规划的最常用算法之一，甚至被一些研究者誉为：

算法万神殿中的一块天花板。

△ 最近ACM通讯网站还发文，将其称为：首选算法

不过，单纯形算法之于学研界有个遗留问题——工程上它应用广泛，从当时理论看，它本不该如此强大。

随着70年代复杂性理论的兴起，计算机科学家们开始用“多项式时间”来描述算法的复杂度，一个算法运行在特定多项式时间范围内，就被认为有效。

但对于单纯形算法实际应用中，其并不在多项式时间范围内运行，性能却优于理论上本应表现更好的其他算法。

滕尚华和他的合作者Spielman也发现了这一问题，彼时，滕尚华只是一名MIT讲师，他的合作者还在读研。

针对上述理论实际不符的问题，二人认为——既然实践都验证了此种算法价值，那么，一定存在着限定条件，让该算法复杂度远低于理论设定。

最初，他们的办法是找到一种新方式改进单纯形法，使其能够在多项式时间内运行，但很快他们发现自己的努力一无所得。

于是，二人转而思考——理论出了什么问题。

滕尚华和同伴发现，当时所使用的“多项式时间标准”侧重于分析算法在最坏情况的表现，但忽略了这种情况是否属于典型状况。于是，他们转而研究另一种理论分析方法，设定一个随机输入，看算法的表现如何。

但即便随机输入，也不是最好的理论解释途径。毕竟在线性规划问题中，输入来自真实世界，这种输入也并非随机，而是内部包含结构的。

这一思考促使他们开发出一种新方法——平滑分析。

该分析方法融合了最坏情况和随机观点，依靠“平滑复杂度”判定算法表现。

所谓“平滑复杂度”，指的是——算法在包含轻微扰动的输入下，运行时间的最大值。该理论分析下——对于低平滑复杂度的算法，每个输入都有一个包含输入的邻域，算法将在该邻域上执行良好。

正是依靠上述理论，他们成功解释了单纯形算法有效性背后的原理。这让他们非常激动。

有同领域的研究者评价他们的分析方法——不仅仅解释了单纯形算法，还可应用于线性规划，两方面成就都令人兴奋。的确，此后在计算机理论界和工业界，平滑分析都产生了深刻的影响。

因上述贡献，滕尚华和他的合作者Daniel Spielman在2008年获得了理论计算机界最高荣誉的哥德尔奖。

第二年，滕尚华当选美国计算机协会会士（ACM fellow），并于同年获得由美国数学学会和美国数学规划学会颁发的富尔克森奖(Fulkerson Prize)。

值得一提的是，Spielman前不久被授予了2023 年数学突破奖，部分原因也源于这项工作。

△ 二人获哥德尔奖合影 图源：南加大 维特比工程学院 官网

时至今日，平滑分析仍被用于分析单纯形算法的性能，提供工程技术从业者理论帮助，该分析方法还被用于更多算法的性能分析中，包括线性规划的内点法，它还指导了很多新算法的设计。

近些年的机器学习热潮中，平滑分析被用于帮助人们分析聚类等任务。作者之一的Spielman对此解释道——相关数据来自真实世界，同样掺杂了噪音，利用平滑分析更为合适。

喜欢「躺平式」研究

重新介绍一下滕尚华。

他生于1964年，是上海交大1985届电工及计算机科学系校友，在南加州大学和卡内基梅隆大学获得硕士和博士学位。

滕尚华曾在MIT、UIUC、波士顿大学等院校任教，2009年他加入南加州大学。不光供职于教学机构，滕尚华还为微软研究院、IBM、英特尔、NASA、波音等机构工作，一直看重理论与应用落地的结合。

△ 图源：quantamagazine

光环之外，滕尚华并不是一副刻板科学家的形象。

滕尚华和研究伙伴Spielman都喜欢“躺平式”科研，窝在沙发里思考问题，有想法就站起来聊聊，为此，他们在办公室摆了两个沙发。

不光身体躺，心态上他们似乎也比较“不太以结果为导向”。

据Spielman之前分享，面对很多努力很久都没结果的研究，他们似乎也觉得“没关系”。有意思的是，他俩的平滑分析想法就来自更早一个失败项目。“关键是你必须享受工作的过程”，滕尚华的研究伙伴补充道。

△ 图源：南加大 维特比工程学院 官网

生活中，滕尚华是个游戏爱好者，喜欢下棋，或是玩一些在线小游戏（比如一些HTML组合游戏），用网页浏览器就能玩，并从中还收获过科研思路。

他开玩笑地自称游戏理论家，“不像我的学生们，他们生下来就可以一直玩游戏”，他补充道。

滕尚华还挺熟悉三国，这两天一次分享中，他跟媒体透露——曾用“三个臭皮匠顶个诸葛亮”描述自己的研究，让学土木的父亲理解博弈求和证明定理的背后思路。

△ 图源：quantamagazine

有意思的是，有外国友人看了滕尚华自曝的生活片段表示：

自己也知道“三个臭皮匠顶个诸葛亮”，最近还新学到一个词：裨将。

唔，这一波属实是靠科学家带动文化输出了。（手动狗头）

参考链接：
[1]https://cacm.acm.org/news/269347-why-the-simplex-method-at-age-75-is-still-the-go-to-algorithm/fulltext
[2]https://www.quantamagazine.org/the-computer-scientist-who-parlays-failures-into-breakthroughs-20220613/
[3]https://www.quantamagazine.org/the-computer-scientist-who-finds-life-lessons-in-board-games-20230125/
[4]https://viterbi-web.usc.edu/~shanghua/