跳转到内容

算法

来自VeritasWiki 真理百科

算法是解决某一特定类型问题的有限运算序列,即由计算机执行的一系列明确定义的计算步骤,常用于计算、数据处理和自动推理。在数学与计算机科学中,算法被精确定义为"表示为有限长列表的有效方法":它包含清晰定义的指令,从一个初始状态和初始输入开始,经过一系列有限而清晰定义的状态,最终产生输出并停止于终态。[1]中国科学院院士徐宗本则通俗地解释:"算法"即算的法则,它起源于数学,指解决某些"类数学"问题规范而完整的方法。[2]

从古代数学到形式化

算法的思想远早于计算机。人们熟悉的加减乘除、欧几里得《几何原本》里的演绎推理基本法则都属于算法;中国古代数学更有深厚的算法传统——《周髀算经》用文字记载勾股算法,三国时期刘徽提出圆周率的割圆术算法,后来祖冲之由此计算出圆周率为 3.1415926。现代逻辑学特别是数理逻辑,则为算法提供了完善的形式化语言描述,这种形式语言及公理系统方法为现代算法发展打下良好的语言基础。[3]算法概念的形式化,部分源自尝试解决希尔伯特提出的判定问题:库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于 1930 年、1934 年和 1935 年提出递归函数,阿隆佐·邱奇于 1936 年提出 λ 演算,埃米尔·莱昂·珀斯特于 1936 年提出 Formulation 1,艾伦·图灵于 1937 年提出图灵机——这些工作共同塑造了"有效可计算性"的现代定义。[4]1946 年世界上第一台电子计算机诞生后,算法与计算机技术密不可分:对计算机来说,算法就是处理信息的原理与遵循;理想状态下,算法能够将人的思维过程以形式化方式输入计算机,使其不停执行命令以实现设定目标。徐宗本据此把算法分为两个层次——数学和逻辑层次的算法刻画人类思维的逻辑过程,计算机算法则是固定化的计算方法与步骤,本质上是将人的逻辑思维过程与计算机的计算过程相融合的成果。[5]

五个特征与两大类别

计算机科学家高德纳在《计算机程序设计艺术》中把算法的特征归纳为五条:输入——一个算法必须有零个或以上输入量;输出——应有一个或以上输出量,即计算的结果;明确性——描述必须无歧义,保证实际执行结果精确符合要求;有限性——必须在有限个步骤内完成任务;有效性——算法中描述的操作都可通过已实现的基本运算执行有限次来实现。[6]国内的教材表述与此一致并有所引申:确定性要求每一条规则、每一个操作步骤都不允许多义性解释;有穷性还隐含执行时间应当合理——如果一个算法要执行几十年才结束,就失去了实用价值;可执行性则要求每一步操作都能实际执行。[7]按用途,算法可分为数值计算算法与非数值计算算法:前者主要用于科学计算以求数值解,如求方程根的二分法、迭代法和牛顿法,计算数值积分的梯形法、辛普森法,其特点是输入输出少、算术运算占主要地位;后者用于数据管理、实时控制以及人工智能等领域,特点是输入输出量大、逻辑判断占主导,处理对象也从单纯数值运算拓展到数据、图形和字符信息的综合处理。[8]在设计方法上,当问题的解是有限离散解空间且可验证时,最直接的算法是完全遍历——逐个检测解空间元素,但当解空间特别庞大时会导致工程上无法承受的计算量,此时需要借助搜索法、规划法等不完全遍历方法;分治法则把一个问题分割成互相独立的多个部分分别求解,其好处之一是便于并行计算。[9]算法与数据结构是计算机程序的两大基础:数据结构研究数据的组织方式,算法实现数据运算,两者互为依存,共同决定程序的效率。[10]

从执行规则到自行学习

算法史上最深刻的转折,是人工智能带来的范式变化。过去人们给计算机下达规则式指令来解决问题;现在只需告诉计算机想解决的问题,它就可以自行选择算法来解决问题。而人工智能最重要的能力是学习——根据机器以往的经验不断优化算法:上世纪 70 年代第一次人工智能浪潮采用符号逻辑推理规则以实现知识表征,因缺乏自我学习能力而无法解决新领域的问题;第二代人工智能在学习和感知能力上表现更佳,但受限于机器学习模型吸收训练数据的能力,与人类水平差距仍大;大约十年前,深度学习新范式打破了特征工程瓶颈——通过多层结构算法,机器对数据集的特征进行筛选和提取,反复训练后获得了提取抽象概念的能力,人工智能算法的智能程度由此越来越高。[11]深度学习也因此成为当代最具代表性的算法,它源于人工神经网络,目的是探索和模拟人的思维规律,仿照脑神经系统结构与信息处理机制构建智能软件系统。[12]但学习型算法并非没有代价:与人类相比,机器所需要的训练数据、能耗和计算资源要多得多;从统计学的角度看,机器能达到的识别精度总体令人印象深刻,但在个体应用中的表现往往不尽如人意;由于目前大多数深度学习模型不具备推理和解释能力,因而无法预测和提前防范严重错误的出现。[13]

当算法走进公共生活

随着深度学习、智能推荐广泛应用于日常生活,算法的社会属性日益凸显。2022 年 1 月,国家互联网信息办公室、工业和信息化部、公安部、国家市场监督管理总局联合发布《互联网信息服务算法推荐管理规定》,自 2022 年 3 月 1 日起施行;其中所称应用算法推荐技术,包括生成合成类、个性化推送类、排序精选类、检索过滤类、调度决策类等算法技术。出台规定的背景,是算法歧视、"大数据杀熟"、诱导沉迷等算法不合理应用已深刻影响正常的传播秩序、市场秩序和社会秩序,给社会公平公正和网民合法权益带来挑战。[14]规定明确了用户的算法知情权与算法选择权:算法推荐服务提供者应以显著方式告知用户提供算法推荐服务的情况,公示其基本原理、目的意图和主要运行机制,并向用户提供不针对其个人特征的选项或便捷的关闭算法推荐服务的选项;针对未成年人、老年人、劳动者、消费者等主体还设置了专门保护,如不得利用算法推荐服务诱导未成年人沉迷网络、不得根据消费者偏好和交易习惯在交易价格上实施不合理差别待遇。[15]学者评价认为,《规定》的出台将有效加强对算法推荐的规范化监管,有利于形成良好的信息传播秩序,具有舆论属性或社会动员能力的算法推荐服务提供者还须履行算法备案手续;从更长远看,优化算法规则的透明度和可解释性、以社会主流价值为导向驾驭算法力量,是算法与人类社会长期共处的基本课题。[16]

参考资料

  1. ↑ 科普中国·algorithm,科普中国。
  2. ↑ 徐宗本:用好算法,迈向智能社会,全国哲学社会科学工作办公室,2022-08-16。
  3. ↑ 徐宗本:用好算法,迈向智能社会,全国哲学社会科学工作办公室,2022-08-16。
  4. ↑ 科普中国·algorithm,科普中国。
  5. ↑ 徐宗本:用好算法,迈向智能社会,全国哲学社会科学工作办公室,2022-08-16。
  6. ↑ 科普中国·algorithm,科普中国。
  7. ↑ 科普中国·计算算法,科普中国。
  8. ↑ 科普中国·计算算法,科普中国。
  9. ↑ 科普中国·algorithm,科普中国。
  10. ↑ 科普中国·计算算法,科普中国。
  11. ↑ 人工智能何以成为"超强大脑"?算法让它不断学习,人民网科普中国频道,2017-06-06。
  12. ↑ 徐宗本:用好算法,迈向智能社会,全国哲学社会科学工作办公室,2022-08-16。
  13. ↑ 人工智能何以成为"超强大脑"?算法让它不断学习,人民网科普中国频道,2017-06-06。
  14. ↑ 国家互联网信息办公室等四部门发布〈互联网信息服务算法推荐管理规定〉,中国网信网,2022-01-04。
  15. ↑ 规范互联网信息服务算法推荐活动 维护国家安全和社会公共利益——解读〈互联网信息服务算法推荐管理规定〉,新华网,2022-01-05。
  16. ↑ 中国传媒大学沈浩:构建算法治理落地支撑体系,新华网,2022-03-09。