最大公约数算法（智能时代的算法发展）

我们正在经历一场智能革命，而这场智能革命建立在算法的基础上。无论是智慧城市、智能制造、智慧医疗等宏大愿景，还是自动驾驶、智能机器、虚拟现实等前沿应用，抑或是智能购物、智慧出行、智能娱乐等生活日常，“智能”的实现都离不开算法。可以说，我们生活在一个算法无所不在的时代。

古代算法思想及其发展

“算法”一词的英文“algorithm”源于波斯数学家花拉子密（Al Khwarizmi）名字的拉丁化。在数学和计算机科学中，算法是有明确定义、有限步骤且计算机可执行的，通常用于计算、数据处理和自动推理的一组指令序列。算法作为一个复杂的体系，是数学、逻辑学和计算机科学的集合。尽管第一台计算机诞生距今不过70多年，但是算法思想源远流长。

● 算法思想的数学源头

数学起源于人类早期的生产活动对计数、天文、度量甚至贸易的需要。这些需要可以简单概括为数学对结构、空间和时间的研究。数学对结构的研究发展出算术和代数，对空间的研究发展出几何，对时间的研究发展出函数。人类关于数字和算术的概念从史前时代就已存在，如苏美尔人用黏土保留数字信息和我国古人用结绳计数都是人类对计算的早期实践。公元前7世纪的古希腊数学家及天文学家泰勒斯（Thales of Miletus）被认为是最早提出几何定理的人。公元前4世纪，古希腊数学家欧几里得（Euclid）所著的《几何原本》是历史上第一部系统化的数学理论典籍，而求最大公约数的欧几里得算法是人类历史上第一个算法。12世纪至13世纪，阿拉伯数学中的代数思想，尤其是数字“零”的概念随着十字军东征传入欧洲。花拉子密所著的《代数学》是第一本解决一次方程及一元二次方程的系统著作，他也因此被称为代数的开创者，他的著作《印度数字计算》在12世纪将十进制和算法思想传入欧洲。函数的概念最早出现在苏格兰数学家及天文学家格雷戈里（James Gregory）发表于1667年的论文《论圆和双曲线的求积》中。1673年，德国数学家莱布尼茨（Gottfried Wilhelm Leibniz）在其手稿里使用了“函数”这一概念，后来又引进“常量”“变量”和“参变量”的概念。函数概念的引入使人们可以从数量上描述运动，伽利略的落体运动定律、牛顿的万有引力定律和爱因斯坦的质能转换公式等都是用函数概念表达的。

中国同样有悠久的数学传统。数学在中国历史上称为“算学”，起源于仰韶文化，距今已有5 000多年的历史。在距今3 000年前的周朝，“数”是六艺之一。在春秋时代，十进位制的筹算已经普及。算学的文献记载最早见于《周髀算经》。《周髀算经》是中国流传至今最早的天文学和数学著作，其中记载了周公曾问商高如何测量天地高远，这是勾股定理最早的文字记录，比古希腊数学家毕达哥拉斯（Pythagoras）的证明早了500多年。中国古代数学把利用算筹进行计算的算法称为“术”，中国古代数学的成就多是用术来表述的，如成书于东汉前期的《九章算术》中的方程术、正负术、今有术，三国时期刘徽的割圆术，南宋数学家秦九韶《数术九章》中的大衍求一术等。尤其是大衍求一术，已经是相当复杂的算法，具备了现代算法的基本特征。

● 算法思想的逻辑学脉络

逻辑学是一门关于推理或论证的学问，主要研究推理的有效性和正确性问题。逻辑学分别发源于古希腊、中国古代和古印度，其中古希腊逻辑最终发展成当前的国际主流逻辑。古希腊逻辑学大约诞生于公元前350年，古希腊哲学家亚里士多德（Aristotle）开创了以“三段论”为核心的词项逻辑，这是人类历史上第一个演绎逻辑体系，他关于逻辑的6篇论文被追随者汇编成《工具论》，对西方思想史产生了深远影响。公元前3世纪早期，古希腊哲学家芝诺（Zeno of Citium）创立斯多葛学派，发展了命题逻辑，但是与亚里士多德逻辑的主导地位相比影响较小。

1543年，波兰数学家及天文学家哥白尼（Nicolas Copernicus）的《天体运行论》和比利时医生及解剖学家维萨留斯（Andreas Vesalius）的《人体结构》在同一年出版，标志着现代科学的诞生。自然科学需要根据个别现象概括出一般性结论，以解释现象间的因果关系，但亚里士多德逻辑无法处理自然科学研究中的因果问题。1620年，英国科学家及哲学家培根（Francis Bacon）提出以观察和实验为基础的科学认识理论，开创了归纳逻辑。1843年，英国哲学家穆勒（John S. Mill）在培根归纳法基础上提出判断因果联系的5种逻辑方法。归纳逻辑在17世纪欧洲科学革命中起到了不可估量的作用。1666年，莱布尼茨在《论组合术》中阐述了以符号运算表述推理过程的思想，开创了符号逻辑和数理逻辑的研究。符号逻辑是现代逻辑的基础，包括命题演算和谓词演算；数理逻辑是符号逻辑在数学中的应用。1847年，英国数学家布尔（George Boole）提出的布尔逻辑就是一个命题演算系统。1928年，德国数学家希尔伯特（David Hilbert）和阿克曼（Wilhelm Ackermann）在《理论逻辑原理》中提出了现在人们常用的命题演算系统。1879年，德国逻辑学家费雷格通过引入量词，将命题演算拓展成了谓词演算系统，最终完成了符号逻辑体系的构建。

人工智能时代的算法

1936年，英国数学家及计算机科学家图灵（Alan Turing）提出被称为“图灵机”的计算数学模型，其构想是将人的计算行为抽象为数学逻辑机器。图灵机是现代通用计算机的理论基础，如今所有通用计算机都是图灵机的一种实现。1943年，美国数学家香农（Claude E. Shannon）和图灵在贝尔实验室探讨了“人工智能”的可能性。1950年，图灵在一篇论文中预言了创造出具有真正智能的机器的可能性，并提出了判断机器是否具有智能的思想实验——图灵测试。1956年，明斯基（Marvin Minsky）、麦卡锡（John McCarthy）、香农等13位科学家在美国达特茅斯学院召开会议，标志着人工智能学科的诞生，算法也由此进入人工智能时代。

● 机器学习

机器学习是人工智能和计算机科学的重要分支，是基于样本数据构建模型并利用模型在没有明确编程的情况下做出预测或决策的一类算法。监督学习、无监督和强化学习是机器学习的基本方法。

监督学习使用人工标记的训练样本将已有知识应用于新数据，以预测未来事件。1936年，英国数学家费希尔（Ronald Fisher）提出的线性判别分析是最早的监督学习算法。20世纪50年代，基于贝叶斯决策理论的贝叶斯分类器开始被用于分类问题。1958年，美国认知心理学家罗森布拉特（Frank Rosenblatt）发明感知器算法，它被认为是人工神经网络的前身。1967年，美国信息理论家科弗（Thomas Cover）和计算机科学家哈特（Peter Hart）提出基于模板匹配思想的K-最近邻算法。20世纪八九十年代，决策树和神经网络算法开始兴起。1995年，两种重要算法——支持向量机和AdaBoost诞生。支持向量机是处理线性分类和非线性分类问题的主要方法，而AdaBoost可以将许多其他类型的算法集成起来使用以达到最佳性能。1995年至1997年，德国计算机科学家霍赫赖特（Sepp Hochreiter）和施米德胡贝（Juergen Schmidhuber）提出长短期记忆算法，可以部分处理梯度消失问题。2013年，长短期记忆算法与深度循环神经网络结合成功应用于语音识别。2001年，美国统计学家布赖曼（Leo Breiman）提出优化的随机森林算法。随机森林是一个用随机方式建立的包含多个决策树的分类器，对多数据集和高维数据的处理有很大优势。监督学习的常见应用场景包括评估信用分数、手写识别、语音识别、信息检索、财务分析、侦测垃圾邮件等。

无监督学习是基于统计的学习方法，通过对未知数据进行分析来发现数据隐藏特征。无监督学习包括聚类和数据降维两种主要算法类型。1963年，美国空军研究员沃德（Joe Ward）根据方差分析提出了最早的聚类算法——层次聚类算法。1967年，美国数学家麦奎因（James MacQueen）提出的k均值算法是聚类算法中知名度最高的算法，在此基础上出现了大量的改进算法和成功应用。1977年，美国统计学家登普斯特（Arthur Dempster）提出最大期望算法，被用于聚类问题和极大似然估计问题。1995年，美国辛辛那提大学教授程（Yizong Cheng）提出可用于计算机视觉和图像处理的均值漂移算法。2000年，美国计算机科学家史建波（Jianbo Shi）推广了谱聚类算法，可以将聚类问题转化为图的最优切割问题。最早的数据降维算法是1901年英国数学家及生物统计学家皮尔逊（Karl Pearson）提出的主成分分析法，比第一台真正的计算机的诞生早了40多年。然而，在此后的近100年里数据降维算法在机器学习领域没有出现重量级成果。1998年，德国计算机科学家舍尔科普夫（Bernhard Schölkopf）提出基于核方法的核主成分分析算法，可以实现高维数据的非线性降维。2000年以后，流形学习开始成为热点，它的主要思想是将高维的数据映射到低维，使该低维的数据能够反映原高维数据的某些本质结构特征。基于流行学习出现了局部线性嵌入、拉普拉斯特征映射、局部保持投影等距映射等新算法。2008年出现的t-分布式随机邻居嵌入算法是降维算法中最年轻的成员。无监督学习的常见应用场景包括反洗钱、客户分组、广告推荐、销售趋势预测等。

强化学习源于心理学中的行为主义理论，强调智能体在奖励或惩罚的环境刺激下如何做出能取得最大化预期利益的行动，也就是说，让智能体在环境中自我学习。早在1954年，明斯基就提出了“强化学习”的概念和术语。1965年，美国普渡大学教授傅京孙（King-Sun Fu）在研究控制论时提出“智能控制”的概念，明确了“试错”作为强化学习的核心机制。1957年，美国应用数学家贝尔曼（Richard Bellman）为了求解最优控制问题的马尔可夫决策过程提出了动态规划法，这一方法采用了类似强化学习的试错迭代求解机制。最早的强化学习算法是1988年加拿大计算机科学家萨顿（Richard Sutton）提出的时序差分学习，它不需要获知环境的全部信息就可以直接从实际经验来获取信息，同时不需要完整的收益反馈信息就可以实时更新决策。1989年，英国计算机科学家沃特金斯（Chris Watkins）提出的Q学习进一步拓展了强化学习的应用，使得强化学习不再依赖于问题模型，Q学习也因此成为最广泛使用的强化学习方法之一。此后近20年的时间里，强化学习被监督学习的光芒所遮掩而发展缓慢。2010年以后，强化学习结合神经网络发展出深度强化学习算法，强化学习由此迎来大发展时期。2013年，谷歌公司旗下的深度思维公司（DeepMind）发表了利用强化学习玩雅达利（Atari）游戏的论文。2015年，深度思维公司开发的AlphaGo程序击败了围棋二段选手樊麾，成为第一个无须让子即可以击败围棋职业棋手的计算机围棋程序。2016年，AlphaGo在一场五番棋比赛中以4:1击败顶尖围棋职业棋手李世石。强化学习的常见应用场景包括无人驾驶、机器翻译、医疗保健、新闻定制、广告营销、机器人控制等。

● 深度学习

深度学习是机器学习的一个分支，是一种模拟大脑神经网络结构对数据进行表征学习的方法。深度学习源于对人脑工作机制的研究。获得1981年诺贝尔生理学或医学奖的美国神经生理学家休伯尔（David Hubel）和维泽尔（Torsten Wiesel）发现人的视觉系统的信息处理是分级的，人类对高层特征的感知基于低层特征的组合。例如，对人脸的识别经过瞳孔摄入像素（形状判断）抽象出人脸概念——识别为人脸的过程，从低层到高层的特征表达越来越抽象和概念化。这一发现意味着大脑是一个深度架构，认知过程也是深度的，而深度学习恰恰就是通过组合低层特征形成更加抽象的高层特征。深度学习的发展可以分为感知器、神经网络和深度学习等3个阶段。

1943年，美国心理学家麦卡洛克（Warren S. McCulloch）和数理逻辑学家皮茨（Walter Pitts）提出人工神经网络的概念，并构建了人工神经元的数学模型，即MCP模型，从而开创了人工神经网络研究的时代。1949年，加拿大心理学家赫布（Donald Hebb）描述了突触可塑性的基本原理，从神经科学理论上解释了学习过程中大脑神经细胞所发生的变化。赫布理论是人工神经网络的生物学基础。1958年，罗森布拉特在康奈尔航空实验室发明感知器算法，这是世界上第一个具有完整算法描述的神经网络学习算法。感知器算法是简单配置的单层神经网络，可以区分三角形等基本形状。但是，受限于计算机硬件，感知器算法在当时无法被广泛应用。1969年，明斯基和佩珀特（Seymour Papert）证明感知器不能解决简单的异或（XOR）等线性不可分问题，感知器研究随之在20世纪70年代陷入低谷。

1959年，休伯尔和维泽尔在研究猫的视觉神经系统时发现，在大脑的初级视觉皮层中存在两种细胞：简单细胞和复杂细胞，其中，简单细胞感知光照信息，复杂细胞感知运动信息。受此启发，1980年日本计算机科学家福岛邦彦（Kunihiko Fukushima）提出了一个网络模型——“神经认知机”（Neocognitron）。这种网络分成多层，每层由一种神经元组成。在网络内部，两种神经元交替出现，分别用来提取图形信息和组合图形信息。这两种神经元后来分别演化成卷积层（Convolution Layer）和提取层（Pooling Layer）。然而，这个网络的神经元都是人工设计的而不能根据计算结果自动调整，所以只能识别少量简单数字而不具备学习能力。

1982年，美国物理学家霍普菲尔德（John J. Hopfield）基于统计物理提出了有少量记忆能力的霍普菲尔德神经网络模型，开创性地论证了按照赫布法则设计权重的神经网络稳定性问题。同年，芬兰计算机科学家科霍宁（Teuvo Kohonen）通过模拟大脑神经元的信号处理机制，提出了自组织映射网络，被用于数据分析和数据探索，其第一个应用领域是语音分析。科霍宁的关键发明是引入了一个系统模型，包含一个实现赢家通吃功能的竞争性神经网络和一个实现可塑性控制的子系统。1987年，美国科学家格罗斯伯格（Stephen Grossberg）和卡彭特（Gail Carpenter）提出了自适应共振理论网络，通过让已知信息和未知信息发生“共振”，从已知信息推测未知信息来实现类比学习。然而，这些神经网络存在学习效率不高、需要不断优化设计、网络记忆容量小等不足，实际应用范围有限。

1986年，美国心理学家鲁姆哈特（David Rumelhart）、计算机科学家威廉姆斯（Ronald Williams）和加拿大认知心理学家及计算机科学家欣顿（Geoffrey Hinton）共同提出反向传播算法（BP算法）。BP算法通过梯度的链式法则使输出结果和真实值之间的差异反馈到每一层的权重中，从而让每一层函数都能像感知机那样得到训练。BP算法阶段性解决了神经网络自适应、自主学习的难题。1989年，贝尔实验室的法国计算机科学家杨立昆（Yann LeCun）第一次成功实现了神经网络的实践应用。他将卷积神经网络与BP算法结合，提出LeNet网络。20世纪90年代，美国邮政署将LeNet网络用于自动读取信封上的邮政编码。然而，基于BP算法的神经网络仅能求解局部最优，而且这种情况随着网络层数的增加越来越严重，这一问题制约了神经网络的发展。

2006年，欣顿提出深度学习算法，通过无监督学习和逐层预训练的方式有效降低了训练难度，从而解决了BP神经网络难以达到全局最优的问题。2012年，欣顿的研究小组采用深度学习赢得了ImageNet图像分类比赛的冠军，准确率超出第二名10%以上，在计算机视觉领域产生极大震动，引发了深度学习的热潮。2013年，《麻省理工科技评论》将深度学习列为年度世界十大技术突破之首。如今，深度学习已经被广泛用于搜索引擎、语音识别、自动机器翻译、自然语言处理、自动驾驶、人脸识别等领域，是人工智能最热门的研究方向之一。

量子时代算法的发展

根据摩尔定律，计算机芯片的性能每18个月翻1番。然而，随着摩尔定律逼近极限，经典计算的算力增长即将遭遇瓶颈。量子计算是利用量子态的相干性、叠加性、纠缠性等量子力学特性进行信息运算、保存和处理操作的新型计算模式。量子计算可以突破经典计算机的算力极限，被认为是未来30年最有可能改变世界的颠覆性技术之一。

● 量子计算理论

1979年，美国阿贡国家实验室物理学家贝尼奥夫（Paul Benioff）提出了第一个量子计算机模型。1980年，苏联数学家马宁（Yuri Manin）在其著作《可计算与不可计算》中同样阐述了量子计算的概念。1981年，贝尼奥夫和美国物理学家费恩曼（Richard Faynman）在麻省理工学院举行的第一届计算物理会议上就量子计算发表演讲。贝尼奥夫表示计算机可以在量子力学定律下运行，费恩曼表示使用经典计算机难以有效模拟量子系统的演化，并提出了量子计算机的基本模型。贝尼奥夫、马宁和费曼奠定了量子计算的理论基础。

1985年，英国牛津大学教授多伊奇（David Deutsch）首次提出了量子图灵机模型，并设计了第一个量子算法Deustch算法。然而，Deustch算法没有确定性，其成功的概率仅有50%。1992年，多伊奇和英国剑桥大学教授乔萨（Richard Jozsa）在早期Deustch算法基础上提出了有确定性的Deutsch-Jozsa算法，并将其推广到n个量子比特的Deutsch问题。Deutsch-Jozsa算法首次实现了对经典算法的指数级加速，奠定了量子算法的基本思想。然而，限于当时的理论和技术水平，此时量子算法还停留在纸面设想阶段。

● 量子计算核心算法

Shor算法、Grover算法和以HHL算法为代表的对偶量子算法是量子计算的三大核心算法。1994年，贝尔实验室的美国数学家肖尔（Peter Shor）基于量子傅里叶变换提出了针对整数分解问题的大数质因子分解算法（又称为Shor算法）。Shor算法从理论上展示了量子计算机能够把质因数分解问题的求解从指数时间降到多项式时间，可用于破解目前通用的计算机加密方案——RSA加密算法。假如超级计算机破解一个2048位的RSA密钥需要数十亿年，那么使用Shor算法的量子计算机仅需要几分钟。这意味着依赖RSA密钥机制的银行、网络和电子商务系统在理论上不再安全。然而，Shor算法在量子计算机上的实验实现一直是国际公认难题。2008年，中国科技大学教授潘建伟的团队与英国牛津大学合作，首次在光量子计算机上实现了Shor量子分解算法，标志着我国光学量子计算研究达到了国际领先水平。

1996年，贝尔实验室的美国计算机科学家格罗弗（Lov K. Grover）基于量子黑盒加速工具提出了针对乱序数据库的量子搜索算法（又称为Grover算法）。Grover算法从本质上解决了函数求逆的任务，使无序数据库中“大海捞针”成为可能，其在密码学上的应用可以加速对称密钥算法的破解。然而，原始的Grover算法只能以一定概率输出正确结果，在一些特殊情况下输出错误结果的概率较大。2001年，清华大学教授龙鲁桂利用相位匹配的技巧将Grover算法的成功概率提高到100%，即龙算法。

Shor算法和Grover算法提出之后，量子算法研究进展缓慢。2003年，肖尔发出著名的“肖尔之问”，即为什么难以发现更多的量子算法。肖尔对这一问题的解释是，量子计算机的运行模式与经典计算机不同，以至于经典算法中的构造设计技巧和直觉在量子计算过程中不再成立。

2002年，龙鲁桂提出酉算符线性叠加的对偶量子算法。酉算符是泛函分析中定义在希尔伯特空间上的有界线性算符，Shor算法和Grover算法都是通过酉算符对信息进行处理。由于酉算符只允许乘除运算，经典计算中的许多技巧不能用于量子计算。对偶量子算法通过引入辅助比特以实现非酉操作，这使酉算符的加减乘除四则运算成为可能，从而解决了经典算法转化为量子算法的问题。2009年，美国麻省理工学院的哈罗（Aram W. Harrow）、哈希迪姆（Avinatan Hassidim）和劳埃德（Seth Lloyd）基于酉算符线性叠加提出可求解线性方程组的HHL算法。求解线性方程组是很多科学和工程问题的核心，HHL算法相对于经典计算有指数加速的效果，因此在机器学习、数据拟合等多种场景中展示出巨大优势。

● 量子人工智能算法

量子叠加和量子纠缠等量子力学特性使量子算法非常适于解决人工智能和机器学习研究中核心的最优化问题。所谓“最优化”是指在给定预期结果和约束条件的情况下，从一组可能选项中找到问题最优解的过程。最优化问题是应用数学和计算机科学领域的重要基础研究之一，其理论与方法广泛用于工业生产、工程设计与管理、交通运输、经济决策、市场管理等关乎国计民生的重要领域。1995年，美国计算机科学家卡克（Subhash Kak）首先提出量子神经计算的概念。同年，英国科学家米尼尔（Tamaryn Menneer）和纳拉亚南（Ajit Narayanan）将量子信息学中的多体观点应用到单层人工神经网络，提出了量子衍生神经网络，显示出在处理分类问题上的有效性。2000年，韩国科学家韩国贤（Kuk-Hyun Han）等采用量子比特编码染色体，提出了具有更强并行搜索能力的量子遗传算法。2005年，日本科学家幸田典明（Noriaki Kouda）等将量子位引进神经元定义，提出了量子位神经网络，仿真试验表明该神经网络具有良好的学习能力。2006年，谷歌眼镜项目联合创始人奈文（Hartmut Neven）在D-Wave量子计算机上开发了第一个结合了量子算法和机器学习的图像识别系统。近年来，量子人工智能算法发展迅速，出现了量子卷积网络、量子自然语言处理、量子生成模型等新型算法。以IBM、谷歌为代表的科技企业纷纷加强了量子人工智能在新材料设计、药物设计以及化学反应模拟等领域的算法研究。2017年至2020年，IBM、IonQ和谷歌公司先后利用量子计算模拟出氢化铍、水分子和二氮烯分子，标志着量子计算在模拟和发现小分子化合物上迈出重要一步。2021年1月，谷歌公司与德国医药企业勃林格殷格翰联合成立量子实验室，致力于实现对蛋白质、核酸、多糖等生物大分子的模拟，有望开启在原子、分子层面理解生命和研发新药的新模式。

算法是人工智能的基础。当前，数据和算力已经不再是人工智能发展的主要瓶颈，人工智能的创新主要就是算法的创新。随着人工智能在国家治理、经济发展、科技创新、医疗保健、教育培训，乃至日常生活的应用日益广泛和深入，算法越来越重要。在这样的背景下，只有不断探索新的算法机制，发展新的算法应用，开发新的算法模型，发掘和培养算法人才，才能为推动智能社会发展提供强劲动力。

作者：王楠、王国强，中国科协创新战略研究院

本文转载自微信公众号张江评论，原载于《张江科技评论》2021年05期