CNCC2018 | 研究经典计算机算法已经过时了吗？

本文转载自公众号“读芯术”

（ID：AI_Discovery）

在大家都追寻计算机前沿与新兴技术的时候，研究计算机的经典算法还有必要吗？会不会显得有些过时了？

在2018中国计算机大会（CNCC 2018）“经典计算机算法”分会论坛中，来自机器学习等领域的专家学者就经典计算机算法进行了研讨。

计算机理论领域一直以它独有的底蕴，散发醉人的芬芳，虽然看上去离我们很远，但是可能就源于我们的生活中，并且应用在生活的各方面。经典算法带给我们的，不仅是向前辈们一样卓越的研究成果，还包括他们研究道路上所收获的灵感和丰富的经验，这些都将对当前的应用、未来的研究乃至年轻一代的研究人员及从业者产生深刻的影响。

孙贤和：并行计算三大定律

人物小贴士：

孙贤和，美国伊利诺理工大学计算机科学系的大学杰出教授和前系主任； IEEE Fellow；IEEECS旗舰期刊Transactions on Parallel and Distributed Systems的副主编；美国阿岗国家实验室客座教授和伊利诺理工大学可扩展计算软件实验室主任。

作为并行计算三大定律之一——存储受限理论，也即“孙-倪”定律的提出者，孙贤和教授不远万里从伊利诺理工大学来到大洋彼岸，讲述三大定律的发展历程及自己如何想出“孙-倪”定律的故事。

阿姆达尔定律（Amdahl’s Law）考虑到在一个系统中，串行比例越低、处理器越多，则加速比越高。古斯塔夫森定律（Gustaufson’s Law）表明在应用负载随计算节点增加时，并行计算的增益没有“天生”的上限。由于两个定律分别有所偏重，没有很好解决加速比计算的问题，于是孙教授将两个定律结合起来，在处理器的基础上考虑到内存的容量，考虑到实际的运算量，提出“孙-倪”定律，很好的解释了内存传输和处理器与加速比的关系。

立威：机器学习——从理论到算法

人物小贴士：

王立威，北京大学信息科学技术学院教授。主要从事机器学习理论研究。在机器学习国际权威期刊会议发表高水平论文100余篇。2011年入选由人工智能国际期刊IEEE Intelligence Systems评选的AI’s 10 to Watch，是该奖项自设立以来首次获此荣誉的亚洲学者。

经典算法的价值一直是王立威教授所强调的，在深度学习火热发展的今天，他提醒大家合适的算法才是解决问题最重要的关键。

王立威教授从机器学习的起源讲起，首先是“学习”与“可学习”的定义提出，VC概念的确立，引出两个经典算法“SVM”和“Boosting”。

在讲SVM时他先讲到经典的二分类问题，通过线性分类器对于欧式空间里的正类数据和负类数据进行分类，采用三条直线的实例方式进行描述，由此引出其中数学关系：最小距离最大化。将其表示成数学中的公式后，王立威教授将数学公式再上升到优化问题，同时考虑计算复杂度，将问题变为一个“二次规划”问题。在解决最优化问题后，该问题的对偶问题（从原始的最优化问题出发，找到另外一个最优化问题，解出与原始问题相同最优值的问题），即拉格朗日对偶，可以采用核函数的引导将线性问题转化为非线性问题解决。

Boosting算法最开始是一个纯理论的问题，在5年之后将其改进为可应用的AdaBoost，王立威教授讲述了从将分类器组合的Idea到专家不断定类的思想再到精确权重改变数学落实的Boosting算法产生过程。

最后王教授提到，对于以空间为基础的图像处理和以时间为基础的语音处理，深度学习可能有所帮助，但是在最无序的数据中，考虑机器学习的经典算法，可能会使得实验效果更好。

于剑：从两个经典的机器学习算法谈起

人物小贴士：

于剑，现任北京交通大学计算机学院教授，博士生导师，北京交通大学人工智能研究院常务副院长，交通数据分析与挖掘北京市重点实验室主任，中国计算机学会会士、理事，中国计算机学会人工智能与模式识别专业委员会秘书长，中国人工智能学会理事，中国人工智能学会机器学习专业委员会副主任。主要研究兴趣是机器学习、数据挖掘和自然语言处理等，著有学术专著《机器学习：从公理到算法》。

承接王教授讲的分类问题，于剑教授讲到了问题的另一个方面：聚类问题。“物以类聚，人以群分”，你相信吗？早在《周易》中古人就提出了聚类的思想，但是算法在20世纪50年代才提出，几乎所有领域都涉及到聚类问题，因此聚类问题具有“思想早、算法晚、研究热”的特点。

从最简单的一个点表示类，到其余点和这个点的相似程度，想到这即可引出聚类。正是这简单的K-Means算法，在刚提出时并没有受到重视，甚至被发明者扔进垃圾桶，直到20年后，另一个人将这个算法应用后得到迅速应用，这才引起原发明人的重视。从此，由于线性收敛、收敛速度快等特征使得K-Means算法成为使用最广泛的聚类算法。

 “不知其子视其父；不知其人视其友；不知其君视其草木”，于剑教授引用孔子的话引出K-近邻算法，一个人可根据其临近的人来判断其类型，这也是K-近邻算法的核心——一个类由其所属的样本相似度来决定。

于教授针对聚类提炼出“十二字真言”：像哪类，归哪类；归哪类，像哪类。作为《机器学习：从公理到算法》的作者，于剑教授说：“机器学习算法虽然差异很大，但是很有共性。机器学习算法的基本假设和人学习的基本假设实际上是一致的。”

张响亮：无监督学习中的选代表和被选代表问题

人物小贴士：

张响亮：沙特阿卜杜拉国王科技大学(KAUST)计算机系副教授。2010毕业于法国国家计算机与控制科学研究院(INRIA)及巴黎第十ー大学并获得博士学位。研究方向为机器学习和数据挖掘。

《SCIENCE》作为科学界顶级刊物之一，发表了无监督学习的经典AP和LLE算法。张响亮教授从中受到启发，在博士阶段对AP算法进行了研究。

不同于K-Means算法，AP算法是采用消息传递的方式进行聚类。AP算法的聚类中心是一个真实的点，并且AP算法解决了K-Means算法一直困扰使用者的一个弊端，即可以在不用输入类数的情况下自动聚类。

张响亮教授将AP问题抽象成选代表的问题，将自己比喻为代表，使用自己代表群体的意愿和其余人被代表的意愿形象地描述AP中的点聚类的过程，将复杂的算法通过比喻生动的表示出。然后讲出AP算法的应用：将每个代表权值输入矩阵，则可以进行迭代计算。但是AP算法具有时间复杂度高的局限性。

LLE方法是一个经典的针对无监督的降维方法，它可以突破主元分析法在非线性数据处理的局限，在进行降维的过程中，高维空间代表到低维空间同样具有代表的性质，可以保留数据的本质特征。

陆品燕：两个经典的拍卖机制介绍

人物小贴士：

陆品燕，上海财经大学信息学院教授，副院长，理论计算机科学研究中心主任。他的主要研究方向是理论计算机，并注重与其它学科的交叉，包括自然科学中的统计物理以及社会科学中的经济学与社会选择理论等。

优化算法之所以能获得诺贝尔经济学奖，一定有其神奇的特点。计算机理论领域年轻一代的领军人物陆品燕教授指出，在互联网时代，设计的计算机算法需要满足经济学要求经常是一个必备的条件。

如果有三个人决定空调的温度（比如24、25、26），如果有一个人伪造自己的温度（25-22），就可以使得平均数被影响，但是如果采用中位数，那就可以无法伪造，那么采用中位数就是一个最优策略。

在进行拍卖的时候，第一高价的人有时会比第二高价高很多，那可能认为是一个损失。但是如果第一高价的人谎报数字，如果谎报太高，则更没有好处，如果谎报太低，则可能拿不到物品。那么这就说明：只要每个人真实的报价，那就可以达到最优。

陆品燕教授将问题提升到数学的层面，并且给出最优策略的数学论证，由此引出VCG机制和Myerson机制是一个最优机制。

通过这次分论坛，经典算法的重要性与意义再次被重视，特别是在众多业者都在研究深度学习的今天，机器学习的经典算法仍然在某些领域强于其他算法，而学习经典的计算机算法和知识，往往比现在最流行的语言或技术更有生命力。

中国计算机学会 

微信号：ccfvoice           

长按识别二维码关注我们

CCF推荐

【精品文章】

点击“阅读原文”，加入CCF。