中国人工智能学会：2023年中国人工智能系列白皮书-人工智能原理（514页）.pdf

《中国人工智能学会：2023年中国人工智能系列白皮书-人工智能原理（514页）.pdf》由会员分享，可在线阅读，更多相关《中国人工智能学会：2023年中国人工智能系列白皮书-人工智能原理（514页）.pdf（514页珍藏版）》请在三个皮匠报告上搜索。

1、中国人工智能系列白皮书 中国中国人工智能系列人工智能系列白皮书白皮书 -人工智能人工智能原理原理 中国中国人工智能学会人工智能学会 二二二二三年年九九月月 中国人工智能系列白皮书 1 中国人工智能系列白皮书编委会中国人工智能系列白皮书编委会 主 任：戴琼海 执行主任：王国胤 副 主 任：陈 杰 何 友 刘成林 刘 宏 孙富春 王恩东 王文博 赵春江 周志华 委 员：班晓娟 曹 鹏 陈 纯 陈松灿 邓伟文 董振江 杜军平 付宜利 古天龙 桂卫华 何 清 胡国平 黄河燕 季向阳 贾英民 焦李成 李 斌 刘 民 刘庆峰 刘增良 鲁华祥 马华东 苗夺谦 潘 纲 朴松昊 钱 锋 乔俊飞 孙长银 孙茂松

2、陶建华 王卫宁 王熙照 王 轩 王蕴红 吾守尔斯拉木 吴晓蓓 杨放春 于 剑 岳 东 张小川 张学工 张 毅 章 毅 周国栋 周鸿祎 周建设 周 杰 祝烈煌 庄越挺 中国中国人工智能系列人工智能系列白皮书白皮书-人工智能人工智能原理原理编写组编写组 李昂生 杨博 彭攀 冯启龙 陈薇 金弟 祁琦 姚鹏晖 陈雪 王子贺 中国人工智能系列白皮书 2 前言前言 人工智能技术的发展与成功应用已经成为 21 世纪科技领域最大的新现象。然而，科学地理解人工智能原理已经超出了现有科学体系的范畴。显然，人工智能是人类科学技术发展的必然结果，人工智能科学也将是人类科学进步与发展必然实现的目标。破解人工智能的科学和

3、技术障碍是人类科学技术发展绕不开也跨不过的重大前沿课题，并且已经凸显为人类 21 世纪首先需要突破的问题。人工智能的科学与技术突破需要新的科学思想；人工智能本身是一个多学科交叉融合的科学现象，人工智能必然与若干主要的学科实质相关；人工智能技术开始于 20 世纪中叶，已经经历了几个重要的发展阶段，推动人工智能作为一个重大挑战走到 21 世纪的科学前沿。本白皮书顺应并体现人工智能的上述现状，由人工智能基础专委会负责组织。具体编写组织如下：北京航空航天大学、中关村国家实验室李昂生教授撰写了人工智能总论，分析了人工智能的重大科学问题，和其它学科的边界，论述了人工智能原理的总体框架和主要构成部分。吉林大

4、学杨博教授撰写了符号主义人工智能以总结基于逻辑推理的人工智能的成就、问题与未来展望。中国科学技术大学彭攀教授和陈雪博士撰写了大数据算法与可信计算理论以总结基于计算的智能研究成果，分析计算与智能这两个概念的实质、关系与边界。中南大学冯启龙教授撰写了难解问题的智能算法，以总结在困难问题智能算法求解方面的成就，分析困难问题的实质，展望智能算法在困难问题求解方向的前景。中国人工智能系列白皮书 3 中国科学院计算技术研究所陈薇研究员撰写了神经网络的数学原理以总结深度神经网络学习理论方向的成就、问题和未来展望。天津大学金弟教授撰写了神经网络的计算原理以总结神经网络作为计算模型方向的成就、问题和未来展望。中

5、国人民大学祁琦教授和王子贺博士撰写人工智能的博弈理论以总结智能的博弈途径研究的成就、问题和未来展望。南京大学姚鹏晖教授撰写了量子人工智能以总结基于量子物理的人工智能方向研究的成就、问题和未来展望。李昂生教授撰写了白皮书的其余章节，包括信息定律与信息模型，信息演算理论，（观察）学习的数学理论，自我意识的数学理论，博弈/谋算理论，人工智能信息模型，这些内容是李昂生创建的信息世界的数学原理中的主要科学思想和基本科学原理的简单介绍；在信息时代的科学双引擎和信息时代重大科学问题一章，李昂生提出了信息时代的几个重大科学问题。本白皮书的内容包括了：智能作为一个科学概念的模型、原理与方法；智能与推理、计算、通

6、信、博弈等科学概念的实质关系与边界界定；智能与数据、数学、物理、生物的实质关系与边界界定；智能技术的工程原理与方法等。这些内容构成了本白皮书人工智能原理的五大部分：第一部分 人工智能总论 由李昂生教授的人工智能总论构成。第二部分 逻辑推理人工智能和计算智能 由杨博教授的 符号主义人工智能，彭攀教授和陈雪博士的 大数据算法与可信计算理论 和冯启龙教授的 难解问题的智能算法等三章构成。中国人工智能系列白皮书 4 第三部分 神经网络人工智能和生物人工智能 由陈薇研究员的神经网络的数学原理和金弟教授的神经网络的计算原理两章构成。第四部分 数学人工智能和物理人工智能 由祁琦教授和王子贺博士的人工智能的博

7、弈理论和姚鹏晖教授的量子人工智能两章构成。第五部分 信息主义人工智能：层谱抽象认知模型人工智能 由李昂生教授的信息定律与信息模型，信息演算理论，（观察）学习的数学理论，自我意识的数学理论，博弈/谋算理论，人工智能信息模型，和信息时代的科学双引擎和信息时代重大科学问题等章构成。白皮书的第一部分分析了人工智能的根本科学问题，揭示了人工智能科学是人类科学技术发展的必然结果，分析了人工智能科学是现有科学体系所不足于支撑的重大科学问题；第二、第三和第四部分主要是基于分而治之这一物理世界分析方法科学体系的人工智能原理；第五部分是李昂生创建的层谱抽象认知模型这一信息世界科学范式的数学原理及基于这个新科学原理

8、的人工智能原理。本白皮书第五部分揭示了信息是建立智能科学的钥匙；揭示了层谱抽象是人认知世界、感知认知自我的模型与方法；揭示了信息世界的层谱抽象认知模型、原理与方法；揭示了层谱抽象认知模型与分而治之分析方法结合是建立人工智能科学的总方法，这一总方法恰好就是 2500 多年以前，孙子兵法的核心科学思想：谋算，谋就是层谱抽象，算就是分而治之；揭示并建立了人工智能的数学实质与基本科学原理；提出人工智能的智能论断智能论断（Intelligence Thesis）：智能智能=信息信息；揭示了层谱抽象认知模型与分而治之分析方法构成了信息时代的科学双引擎。中国人工智能系列白皮书 5 目 录 目 录.5 第一部

9、分.1 人工智能总论.1 第 1 章 人工智能总论.2 1.1 人工智能的科学思想起源.2 1.2 人工智能的数理逻辑原理.5 1.3 人工智能的计算原理.7 1.4 图灵对机器智能的研究.9 1.5 人工智能研究的兴起.11 1.6 符号主义人工智能.11 1.7 连接主义人工智能.12 1.8 行为主义人工智能.14 1.9 人工智能的数学、物理挑战.15 1.10 人工智能的重大科学挑战.15 1.10.1 数学、物理对象的可分性.15 1.10.2 信息世界对象的不可分性.16 1.10.3 信息世界对象的可定义性问题.17 中国人工智能系列白皮书 6 1.10.4 人学习的基本问题.

10、17 1.10.5 自我意识的基本问题.18 1.10.6 博弈/谋算的基本科学问题.18 1.10.7 本节小结.19 1.11 信息科学重大挑战性问题.19 1.11.1 经典信息论.19 1.11.2 生成策略.21 1.11.3 解码策略.23 1.11.4 信息的模型.24 1.11.5 信息基本定律.25 1.11.6 信息科学是什么？.25 1.11.7 信息的数学理论是什么？.26 1.12 信息科学原理.26 1.13 本章小结.27 第二部分.29 逻辑推理人工智能与计算人工智能.29 第 2 章 符号主义人工智能.30 2.1 命题知识表示与推理.30 中国人工智能系列白

11、皮书 7 2.1.1 命题逻辑.31 2.1.2 命题推理问题.33 2.1.3 命题可满足性求解方法.34 2.1.4 模型计数.35 2.1.5 知识编译.37 2.2 自动定理证明.38 2.2.1 自动定理证明的起源、发展与现状.38 2.2.2 Herbrand 定理.41 2.2.3 合一与匹配.43 2.2.4 归结原理.44 2.2.5 归结原理的改进策略.46 2.2.6 等词推理.48 2.2.7 几何定理证明和数学机械化.50 2.2.8 定理证明器竞赛和著名定理证明器.51 2.3 约束可满足性求解.52 2.4 基于模型的诊断.56 2.4.1 MBD 问题.57 2

12、.4.2 国内外总体研究现状.58 中国人工智能系列白皮书 8 2.5 神经符号系统.59 2.5.1 神经符号系统的背景.59 2.5.2 神经符号系统研究现状.61 2.5.3 神经符号系统的挑战及未来研究方向.64 第 3 章 大数据算法与可信计算理论.67 3.1 大数据算法计算模型.67 3.1.1 亚线性时间算法.68 3.1.2 亚线性空间算法.69 3.1.3 动态图算法.70 3.1.4 大规模并行计算.70 3.1.5 数据降维.71 3.2 满足可信需求的算法.71 3.2.1 鲁棒性.71 3.2.2 公平公正.73 3.2.3 隐私保护.73 第 4 章 难解问题的智

13、能算法.75 4.1 难解问题图学习方法求解.78 4.1.1 路径规划问题.81 中国人工智能系列白皮书 9 4.1.2 最大割问题.84 4.1.3 作业调度问题.85 4.1.4 其他难解问题.86 4.2 难解问题强化学习求解.87 4.2.1 基于无模型的强化学习方法.88 4.2.2 基于有模型的强化学习方法.92 4.3 总结与展望.94 第三部分.98 神经网络人工智能与生物人工智能.98 第 5 章 神经网络的数学原理.99 5.1 神经网络的背景及意义.99 5.1.1 神经网络的发展历史.99 5.1.2 神经网络对人工智能发展的作用.100 5.1.3 神经网络给人工智

14、能带来的挑战.101 5.2 神经网络的数学原理的内涵.102 5.2.1 研究意义.102 5.2.2 分析视角.103 5.2.3 基本框架.104 中国人工智能系列白皮书 10 5.2.4 研究趋势.106 5.3 神经网络的传统理论.106 5.3.1 表达能力.107 5.3.2 泛化能力.107 5.3.3 优化能力.107 5.4 前沿发展.108 5.4.1 对自适应优化器的分析.108 5.4.2 基于神经网络结构的优化分析.108 5.4.3 优化器的隐式正则分析.108 5.4.4 神经网络的精确泛化估计.109 5.4.5 表示所需参数量下界.109 5.5 未来展望.

15、109 5.5.1 设计适用不同场景的安全性度量.109 5.5.2 构建以安全为中心的神经网络理论.110 5.5.3 发展可信可控的神经网络模型.110 第 6 章 神经网络的计算原理.111 6.1 经典神经网络的计算原理.112 6.1.1 表示学习.112 中国人工智能系列白皮书 11 6.1.2 前馈神经网络.116 6.1.3 神经网络训练.119 6.2 面向序列数据的神经网络.123 6.2.1 循环神经网络 RNN.124 6.2.2 转换器 Transformer.127 6.2.3 时序卷积神经网络 TCN.132 6.3 图神经网络.134 6.3.1 图表示学习.1

16、35 6.3.2 图神经网络的基础原理.137 6.3.3 图神经网络前沿.139 第四部分.158 数学人工智能与物理人工智能.158 第 7 章 人工智能的博弈理论.159 7.1 均衡计算.160 7.1.1 纳什均衡.160 7.1.2 纳什均衡的存在性.162 7.1.3 纳什均衡的计算.165 7.1.4 纳什均衡的计算复杂性.170 中国人工智能系列白皮书 12 7.2 人工智能中的合作博弈.174 7.2.1 合作博弈.175 7.2.2 合作博弈的表示和算法.180 7.2.3 合作博弈在多智能体系统中的应用.182 7.2.4 结论.184 7.3 公平分配.184 7.3

17、.1 引言.185 7.3.2 模型定义.186 7.3.3 公平性.187 7.3.4 可分割物品的公平分配.191 7.3.5 不可分物品的公平分配.193 7.3.6 其他研究.195 7.4 适当评分规则（Proper Scoring Rule）.196 7.4.1 适当评分规则的起源.198 7.4.2 适当评分规则种类.198 7.4.3 适当评分规则的应用.204 7.4.4 总结.206 7.5 社会选择与投票.206 中国人工智能系列白皮书 13 7.5.1 经典投票规则.207 7.5.2 社会选择中的经典结论.211 7.5.3 总结.214 7.6 重复拍卖.215 7

18、.6.1 动态定价问题.215 7.6.2 上下文动态定价问题.218 7.6.3 重复拍卖中的均衡分析问题.221 7.6.4 总结.222 7.7 小结.222 第 8 章 量子人工智能.224 8.1 概述.224 8.2 量子学习方法介绍.224 8.2.1 HHL 算法.224 8.2.2 量子奇异值变换.228 8.3 量子吉布斯采样.231 8.2.4 变分量子电路.234 8.3 量子学习应用场景.240 8.3.1 传统机器学习问题的量子化.240 中国人工智能系列白皮书 14 8.3.2 量子无监督学习.247 8.3.3 量子有监督学习.253 8.3.4 量子强化学习.

19、259 8.3.5 量子层析.266 8.3.6 其它量子学习算法.267 第五部分.272 信息主义人工智能：.272 层谱抽象认知模型人工智能.272 第 9 章 信息定律与信息模型.273 9.1 信息科学的研究对象.273 9.2 物理世界对象基本定律（Fundamental Law of Physical Objects）.273 9.3 信息性质/知识的定义.274 9.4 现实世界对象的物理性质与信息性质.275 9.5 策略.276 9.6 信息的模型.277 9.7 学习的数学实质.278 9.8 知识是信息在某一个模型下的解释.279 中国人工智能系列白皮书 15 9.9

20、抽象.279 9.10 层谱抽象.281 9.11 科学范式定律.283 9.12 个体定律.284 9.13 信息定律.285 9.14 运动定律.287 9.15 竞争定律.287 9.16 认知模型定律.288 9.17 观察定律.289 9.18 知识表示定律.290 9.19 知识定律.291 9.20 规律的定义.292 9.21 创造策略.292 9.22 学习的可解释性原理.293 9.23 自我意识定律.293 9.24 系统定律.293 9.25 本章总结.294 第 10 章 信息演算理论.296 中国人工智能系列白皮书 16 10.1 信息系统的数学表示.296 10.

21、2 一维结构熵.299 10.3 信息系统的编码树.299 10.4 在一个层谱抽象策略下的结构熵.300 10.5 信息系统的结构熵.301 10.6 结构熵极小化原理.302 10.7 解码信息.303 10.8 层谱抽象策略的压缩信息.304 10.9 压缩/解码原理.304 10.10 层谱抽象解码原理.305 10.11 层谱抽象可定义性.306 10.12 层谱抽象.307 10.13 基于结构熵的推理演算.308 10.14 基于解码信息的推理.310 10.15 推理的数学理论.311 10.16 信息生成原理.312 10.17 解码信息原理.313 10.18 本章总结.3

22、14 中国人工智能系列白皮书 17 第 11 章（观察）学习的数学理论.316 11.1 先验认知模型.317 11.2 观察的数学实质.317 11.3 学习的数学定义.319 11.4 人的先验分析方法.320 11.5 学习的主体与客体.321 11.6 学习的目的、目标.321 11.7 知识的定义.321 11.8 规律的定义.322 11.9 学习过程表示：层谱抽象.322 11.11 学习的数学模型.324 11.11 创造策略的理解与实现.326 11.12 局部观察学习.328 11.13 全局观察学习.330 11.14 学习模型中的生成策略与生成原理.331 11.15

23、学习模型中的解码策略与解码原理.331 11.16 知识树.331 11.17 知识的一致性准则.332 中国人工智能系列白皮书 18 11.18 知识的度量.333 11.19 知识演算推理.334 11.20 学习的极限.337 11.21 学习的数学理论总结.338 第 12 章 自我意识的数学理论.341 12.1 自我意识体的先验感知模型.343 12.2 自我意识体的可定义性.345 12.3 自我意识体五维认知.347 12.4 自我意识的数学实质.349 12.5 生命定律.350 12.6 自我意识体的基本性质.352 12.7 自我意识论断.353 12.8 领土/领地意识

24、.353 12.9 自我意识学习.354 12.10 自我意识体的层谱抽象认知.355 12.11 自我意识体的认知熵.356 12.12 自我意识体的认知信息.357 12.13 自我意识体的内结构熵.358 中国人工智能系列白皮书 19 12.14 自我意识体的外结构熵.358 12.15 自我意识体的外解码信息.359 12.16 自我意识体的层谱抽象感知.359 12.17 自我意识理论总结.361 第 13 章 博弈/谋算理论.363 13.1 博弈的基本定义.363 13.2 竞争定律.365 13.3 现实世界博弈的可能结局.366 13.4 博弈的系统原理.368 13.5 现

25、实世界博弈的基本规律.369 13.6 孙子模型.369 13.7 孙子兵法的核心科学思想：谋算.372 13.8 博弈中的学习.375 13.9 博弈中的自我意识学习.378 13.10 力量的系统生成原理.379 13.11 威胁度量.380 13.12 必胜策略原理.382 13.13 博弈策略的信息科学原理.383 中国人工智能系列白皮书 20 13.14 博弈策略的数理原理.384 13.15 博弈设计原理.385 13.16 博弈的收益原理.386 13.17 博弈系统中玩家的定义.388 13.18 博弈中学习与自我意识学习的正确性与可解释性.389 13.19 博弈结局的层谱抽

26、象定义.391 13.20 博弈获胜的主客观一致性准则.394 13.21 博弈中的谋算策略.396 13.22 博弈/谋算理论总结.398 第 14 章 人工智能的信息模型.399 14.1 智能的定义（非形式化）.399 14.2 人类智能模型.400 14.3 人类智能的信息科学原理.402 14.4 人工智能的科学原理.402 14.5 人工智能模型.403 14.6 智能的数学定义：智能论题.404 第 15 章 信息时代科学双引擎与信息时代重大科学问题.406 15.1 数学中的三个基本问题.407 中国人工智能系列白皮书 21 15.2 物理中的两个基本问题.408 15.3 生

27、命科学的三个基本问题.409 15.4 信息时代的科学双引擎.410 参考文献.412 1 符号主义人工智能：第 2 章参考文献.412 2 难解问题的智能算法：第 4 章参考文献.433 3 神经网络的计算原理：第 6 章参考文献.448 4 人工智能的博弈理论：第 7 章参考文献.459 7.1 节参考文献.459 7.2 节参考文献.460 7.3 节参考文献.464 7.4 节参考文献.467 7.5 节参考文献.468 7.6 节参考文献.470 5 量子人工智能：第 8 章参考文献.472 6 人工智能的信息科学原理：第 1 章、第 9-15 章参考文献.491 中国人工智能系列白

28、皮书 1 第一部分 人工智能总论 中国人工智能系列白皮书 2 第 1 章 人工智能总论 1.1 人工智能的科学思想起源 人工智能已经凸显为 21 世纪的重大科学挑战。这一现象本身就已经说明人工智能是科学发展在 21 世纪的必然而且自然的结果。因此，人工智能的科学障碍正是 21 世纪的重大前沿科学问题。科学是人类在认识世界、认知自我、改造世界、改造自我的过程中产生的对现实世界的知识发现、规律揭示以及基于知识与规律的创造。科学研究的对象是现实世界的对象。对现实世界对象的科学研究的第一步是现实世界对象的表示，这也是对现实世界对象的抽象表示。数与形是现实世界对象的基本属性。因此，数与形就构成了现实世界

29、对象的基本数学表示。经典数学研究数与形的基本规律。数与形的基本规律提供了研究现实世界对象的基础。因此，数学就是现实世界对象研究的基础。公理化的思想使得数学可以建立严格的数学理论。公理化体系是公理化数学的规范化体系，它解决了“形”这个不太容易建立规则的对象的公理化体系。公理化数学已经成为数学研究的范式。数学定理就是基于公理的推理的结果。因此，推理就是数学研究的基本策略，它包括一些基本推理规则。然而，推理这一概念并没有一个数学定义。而且人的推理中还包含或隐含了人的直观。人的推理包括逻辑推理、直觉推理以及逻辑推理与直觉推理的结合。然而长期以来，一直没有一个推理的数学定义，更没有一个逻辑推理和直觉推理

30、的数学定义。但是人们实际上是清楚的，人有直觉推理。而且第三次数学危机中国人工智能系列白皮书 3 就在于数学家们发现，很多的数学证明依赖于人的直观，这使得数学家开始怀疑：是否在已经建立的数学证明中隐含了不可靠的直观？如果是这样，数学就是建立在“沙滩”上了。这就是第三次数学危机。怎样避免人的直观造成数学证明的不可靠？公理化数学的边界在哪里？为了回答这两个问题，Hilbert 1900 年提出一个计划，数学史上称为 Hilbert 计划。该计划提出数学证明的形式化方法，并猜想一切真的命题都是可证明的。Hilbert 要求的证明是一种排除直观的完全基于规则的“证明”，即后来人们熟知的形式化证明。Hil

31、bert 计划的第一个问题是：给（形式化）证明这一概念一个数学定义。以Godel为代表的一批数学家给出了形式化证明的数学定义，建立了数理逻辑新学科，并用构造性方法构造了一个数学命题，使得 和 的否定命题 都是不可证明的。从语义上来说，对任何数学命题，该命题和它的否定命题必然有一个是真的。这就是Godel 1930 年代的不完全性定理，即：在一个适当复杂的公理系统中，必然存在不可证明的真命题。Godel 不完全性定理彻底否定了 Hilbert 一切真命题均可证明的猜想。数理逻辑中定义一个证明就是一个基于公理和推理规则的序列。证明的这一定义完全排除了证明过程中任何可能的直观的因素。基于这一定义的数

32、学，即数理逻辑，恰好就是逻辑推理的数学理论，完美地实现了 Hilbert 计划所要求的证明的形式化。因此，数理逻辑给出了逻辑推理的数学定义，建立了逻辑推理的数学理论。与此同时，数理逻辑完全排除了直觉推理。可以肯定的是直觉推理是人的基本推理方式，可以肯定的是没有一个重要的数学定理不是中国人工智能系列白皮书 4 数学家们直觉推理的结果。长期以来一直没有一个直觉推理的数学理论（这是 20 世纪未能解决的问题，也是 21 世纪凸显的一个科学问题，不解决这个问题，不可能理解学习是什么意思。）Hilbert 的猜想是不对的，但是，这不影响 Hilbert 计划的意义。因为正是有 Hilbert 计划，才有

33、了Godel 后来数理逻辑的研究。进一步，Turing 1936 年提出了通用 Turing 机模型，给“计算”这一概念一个数学定义与数学模型。Turing 1936 的文章基于通用 Turing 机模型，证明了存在不可计算函数。由于计算也是一种逻辑推理，Turing 的通用 Turing 机也否定了 Hilbert 的猜想。Turing 1936 年提出通用 Turing 机模型的动机是为了否定 Hilbert猜想。Hilbert 1900 年计划的实质是“证明”与“计算”这两个概念的数学定义是什么？Godel 1930 年代对基于逻辑推理的证明给出了一个定义；Turing 1936 年给出

34、了计算这一概念的数学定义。（在数学、乃至科学意义上的“证明”这一概念的数学定义仍然是一个重大的科学问题，是Godel 不曾解决的问题，也是 21 世纪需要回答的科学问题。）显然，在Godel 和 Turing 之前，证明与计算这两个概念还没有严格的数学定义，仍属于哲学概念。证明和计算是数学研究的基本概念，当然也是人的智力活动的基本概念，是人工智能的基本概念。Hilbert 的猜想不对，然而 Hilbert 计划提出了当时的一个重大科学问题，引出了后来的数理逻辑和计算理论，成为 20 世纪科学革命的主要动力。正是由于这个原因，Hilbert 计划的意义远大于 Hilbert 1900 年提出的

35、23 个问题，这些问题，每一个都对一个方向很重要，但是所有问题合起来也仅在数学领域有意义，在其它学科影响有限。然而中国人工智能系列白皮书 5 Hilbert 计划是对整个 20 世纪科学技术产生革命性影响的问题。人工智能已经凸显为 21 世纪的重大科学挑战。然而破解人工智能科学挑战的钥匙和关键科学思想是什么？理解学习、智能和人工智能等概念的钥匙是正确地理解信息这一科学概念。信息是破解人工智能科学挑战的钥匙。Shannon 1948 年提出度量嵌入在一个随机变量中的不确定性的熵的概念，提出在端到端信道传输中，收方消除的发送方的不确定性的量，即互信息的概念，证明了当互信息适当大时，存在一个解码器，

36、根据收方数据解码出发送方所要传输的数据的通信原理，建立了通信的数学理论。第一次提出了信息的概念。然而 Shannon 信息论里面的信息仅限于作为一个通信概念。显然，信息是一个科学概念，而不仅仅是一个通信概念。李昂生建立了作为科学概念的信息的基本原理与理论，提出了层谱抽象认知模型（或者，称为，认知方法），建立了层谱抽象这一方法论的数学理论。信息世界的层谱抽象认知模型和物理世界的分而治之的分析方法，相结合就是破解人工智能科学障碍的模型、原理与方法。本白皮书第十一、第十二和第十三章将建立这一人工智能科学原理。这一科学原理的思想可以追溯到 2500 多年以前，中国科学与军事科学祖师孙武的孙子兵法。层谱

37、抽象认知方法和分而治之分析方法相结合的人工智能原理正是 孙子兵法 的核心科学思想：“谋算”，这里“谋”就是层谱抽象，“算”就是分而治之。1.2 人工智能的数理逻辑原理 Hilbert 1900 年提出 Hilbert 计划的时代背景是第三次数学危机，人们突然发现或意识到数学并没有建立在一个可靠的基础之上。原因在于数学中最通常的概念“证明”和“推理”并没有一个数学定义。中国人工智能系列白皮书 6 Hilbert 计划的目的与动机是为数学建立一个可靠的基础。数理逻辑建立了逻辑推理的规则，给出了基于逻辑推理的证明的数学定义，从而建立了逻辑推理系统，作为公理化数学的公共基础，建立了数学的基础。数理逻辑

38、第一次把“逻辑推理”这一人的推理方法用数学规则来实现了，从而把曾经认为的只有人才能做的“逻辑推理”用数学规则实现了。数学规则显然可以由算法来实现，因此逻辑推理可以由算法来实现。这就意味着算法可以实现人的逻辑推理。这就是人工智能的数理逻辑原理。数理逻辑还建立了后来的计算机科学三大支柱之一的计算机程序理论的数学原理。（程序理论、计算理论和体系结构原理正是计算机科学的三大支柱理论，支撑着整个计算机科学大厦。）基于逻辑推理的定理机器证明正是第一代人工智能的典型代表。数理逻辑，特别命题逻辑中的一些基本问题还提供了新的算法问题，及研究算法复杂性的经典问题，例如第一个NP完全性问题，SAT问题。数理逻辑系统

39、的分析方法，即系统的完备性（completeness）和可靠性（soundness），还提供了计算机程序分析的一般方法。扩充或变种的各种应用逻辑，比如非单调逻辑提供了基于逻辑推理的常识推理，成为第一代人工智能的重要组成部分。数理逻辑揭示了一个逻辑推理有一个语法（syntax）和一个语义（semantic），语法指按规则的推理过程，语义指该推理过程的数学意义，即真、假值。一个正确的推理必然要求语法和语义的一致性。推理的可靠性（soundness）要求符合推理规则的推理结果是正确的（即，真的），推理的完备性（completeness）要求真的一定能按推中国人工智能系列白皮书 7 理规则证明，即推出

40、来。一个逻辑系统的基本要求是可靠性，即推出来的结论一定是正确的（或真的）。基本的逻辑系统同时还要求满足完备性。然而在一个适当复杂的数学系统，例如算术系统中，存在一个命题，使得和的否定，均不可证明。然而和 A 的否定 必然有一个是真的。因此，存在真的命题，它不可证明。这就是deloG 不完全性定理所揭示的结论。在deloG 不完全性定理中，是否“可证”是语法问题，真或者假是语义问题。不完全性定理的实质是：语法和语义的不一致性，即，一个适当复杂的数学系统必然有：语法和语义的不一致性。这里面的一个根本问题是仅仅基于逻辑推理的证明的概念是不充分的（第十五章将把这个问题作为信息时代的重大科学问题之一提出

41、）。基于数理逻辑的人工智能是人工智能的一个重要方向，即符号主义人工智能，其使命是揭示，逻辑推理在人工智能中的作用与极限。1.3 人工智能的计算原理“计算”是人类的一个基本智能活动。Turing 1936 年的 Turing 机，特别是通用 Turing 机给出了计算这一概念的数学定义和数学模型。计算这一概念有很多属性。然而计算的根本属性是机械性，即计算的每一步动作都是机器可执行的。这就是计算这一概念的实质。Turing 机模型揭示了计算概念的这一实质。Turing 机执行的任何一个步骤都是：（1）指向一个位置；（2）改变一个符号；（3）改变一个状态；（4）左移一格或者右移一格。中国人工智能系列

42、白皮书 8 计算的实质：计算的实质：计算的每个动作都是机器可执行的。因此，计算可以由机器来实现。一个 Turing 机就是一个机器的数学模型，它能实现一个计算任务。通用 Turing 机就是一个机器的数学模型，它能实现任何一个计算任务。Turing 的理论贡献是证明了任何一个计算都可以由一个机器，即通用 Turing 机来实现。Turing 机模型还揭示了：计算定律（计算定律（The law of computation）计算是局部的，即计算过程中任何一个动作都是局部操作，而且一个计算就是一系列局部操作构成的序列。显然，逻辑推理是一个计算过程，计算定律也表明逻辑推理是局部的。计算是局部的这一计

43、算定律表明：计算完美地实现了逻辑推理，但是不能实现直觉推理。什么是逻辑推理？什么是直觉推理？逻辑推理就是同一抽象层次的推理。直觉推理就是跨越抽象层谱的推理。现实世界必然包含不同抽象层谱的对象。逻辑推理和直觉推理都是人推理不可或缺的推理形式，是人学习的基本策略。因此仅仅依靠计算不可能实现人的学习，这是以计算为中心建立学习理论的先天不足，不可弥补。Turing 机模型揭示了计算概念的实质，更证明任何一个计算可以用一个 Turing 机来实现，然而并没有回答如何对一个问题通过计算来求解。任何一个计算问题必然有一个“目标函数”。计算的目标函数是中国人工智能系列白皮书 9 由人来确定的，机器本身不能确定

44、计算的目标函数。一个计算问题的目标函数是该计算问题的语义，而计算的过程是该计算问题的语法。因此，一个计算问题有一个人确定的语义和一个机器实现的语法。计算机解决计算问题的语法，但是不能解决计算问题的语义。Turing 机的定义揭示了计算这一概念的实质，奠定了计算理论的基础。而计算理论正是计算机科学的三大支柱之一。通用 Turing 机还为后来的电子计算机提供了数学模型，因此，通用 Turing 机也为计算机体系结构提供了原理。体系结构是计算机科学的三大支柱之一。程序理论、计算理论和体系结构正是计算机科学的三大支柱，其中程序理论的数学基础是数理逻辑，而计算理论和体系结构的数学基础都是 Turing

45、 机和通用 Turing 机。计算这一概念的研究毫无疑问仍然是计算机科学，特别是理论计算机科学的核心问题。计算的数学实质由 Turing Thesis 确定。这个论题是否正确仍然是一个重大问题。在计算复杂性层面，现有的算法复杂性及计算复杂性都是基于 Turing 机来定义的。基于 Turing 机模型，建立了 NP 困难性、NP 完全性的理论。然而计算复杂性理论并没有揭示一个计算问题为什么困难的实质。一个计算问题为什么复杂应该是由这个问题内在本质属性所决定的。算法、计算复杂性，甚至可计算性的任何突破实质上都要求有一个算法新思想。这仍然是计算机科学研究的发动机。1.4 图灵对机器智能的研究 在

46、Turing 之前，有很多计算装置，中国古代的算盘就是一个简单、有效的计算装置。然而计算这一概念有一个严格的数学定义，而且计算可以完全由机器来实现。计算器和计算机的根本区别在于：计中国人工智能系列白皮书 10 算器是单一计算任务的计算；计算机是通用计算模型的计算。通用Turing 机预示着计算可以完全由机器来实现。这是一个伟大的科学成就。基于对这一成就的预见，Turing 1948 年提出了机器智能的概念，并第一次对机器智能这一问题做了认真的研究。Turing 1948 年提出：“机器会思考吗？”这一问题，并针对这一问题进行了充分论证。然而，“思考”这个概念太复杂，没有一个数学模型来实现它。对

47、此，Turing 提出了后来人们称之为“Turing 测试”（Turing Test）的模型以检测一个机器是否有智能，从而回避了什么是智能的问题？以及机器是否有智能的问题？在这篇文章中，Turing 提出了一个基于计算的模拟小学生在学校在老师指导下学习的学习模型。这是第一个尝试给学习这一概念建立模型的工作。Turing 的学习模型引出后来强化学习的模型。成为机器学习的一个重要方向。Turing 1948 年的工作第一次明确提出了机器学习和机器智能的问题。然而 Turing 的工作并没有对学习和智能这两个概念的数学实质做出有意义的理解。实际上，如前所说，计算是局部的，不可能实现直觉推理，更不可能

48、实现学习；计算需要人来确定目标函数，学习的目标函数人也不知道。因此仅仅基于计算是不可能建立学习模型的。Turing 1948 年的工作实际上也说明学习和计算是根本不同的概念。不然，Turing 肯定可以基于计算模型很容易地建立学习的模型与原理。Turing 明确提出“机器智能”的概念，然而回避了什么是智能？智能是怎样形成的？等问题。Turing 1948 年提出的“Turing Test”模型仍然被认为是检验一个机器，是否有智能的准则。因此，Turing 1948 年的工作是开启人工智能研究的奠基性成果。中国人工智能系列白皮书 11 Turing 的工作也引出两大基本问题：（1）计算与智能这两

49、个科学概念的关系是什么？（2）作为科学概念的“计算”一定是 Turing 机吗？显然，这两个问题仍然是 21 世纪的重要科学问题。1.5 人工智能研究的兴起 人工智能的兴起是 1956 年在美国达特茅斯的一个会议开始的。它的兴起不是人工智能有了科学突破而自然产生的，是一些学者感觉会有那么一个学科。然而，这个学科真正的科学贡献还没有什么成果。基础性的成果仅限于数理逻辑、Turing 机，以及如上所说 Turing 第一个认真研究的成果。会议讨论决定用“人工智能”这个名称，并决定了一些研讨会组织形式。会议对人工智能学术没有什么影响性成果。顺便说几点：会议确定了“人工智能”名称。在这之前，Turin

50、g用的名称是:智能机，intelligent machinery。人工智能这个名称现在用的最多，但严格科学意义上，未必严谨、科学。人工智能后来几波的发展都是一波三折。其原因可能就是：人工智能的提出并不是基于科学已经取得突破的基础，而只是感觉有那么一个东西，大家提出来，口号性的东西比较多，实质科学思想少，口号介入到了科学研究的原因。科学研究应该是有其自身规律的，重大科学问题的突破必然有其历史的规律性。1.6 符号主义人工智能 符号主义的根本原理就是逻辑推理，逻辑推理的数学理论就是数理逻辑。中国人工智能系列白皮书 12 因此符号主义的人工智能就是基于数理逻辑的人工智能。人的推理包括逻辑推理和直觉推

51、理，人的推理是逻辑推理和直觉推理的结合。显然，逻辑推理和直觉推理是不一样的，两者对人的学习都至关重要。逻辑推理的数学理论是数理逻辑。然而，长期以来，没有一个直觉推理的数学理论。为正确理解推理这一概念，这里提出：定义定义 1.1（逻辑推理）逻辑推理就是同一个抽象层谱的推理。定义定义 1.2（直觉推理）直觉推理就是跨越抽象层谱的推理。定义 1.1 和定义 1.2 表明了逻辑推理和直觉推理的本质区别。定义 1.1 和定义 1.2 同时还表明，建立推理的数学理论的一个不可逾越的障碍是建立层谱抽象的数学理论。我们第一次建立了这样一个理论，具体参见本白皮书第十章。一个基本观察是人的推理是逻辑推理和直觉推理

52、的结合或融合。由于符号主义的人工智能就是基于逻辑推理的人工智能，符号主义的人工智能技术不可能实现直觉推理，从而不可能实现人的推理。这就是符号主义人工智能的根本缺陷。然而我们并不知道：符号主义人工智能的边界在哪里？这仍然是一个重要的科学问题。1.7 连接主义人工智能 连接主义人工智能的基本原理是：一个良定义的函数必然可以由一个神经网络来任意逼近。神经网络学习的一个基本假设是：学习的目标是一个良定义的函数。一个神经网络学习过程就是通过大量的已标注实例学习一个神中国人工智能系列白皮书 13 经网络的参数使得该神经网络逼近未知的学习目标，它是一个良定义的函数。连接主义人工智能就是一个神经网络模型学习。

53、这一学习模型已经取得重要应用成果，并正在引领着当代机器学习技术的潮流。然而，神经网络学习有若干根本性缺陷：1.它假设学习的目标是一个函数或分布 一个分布或随机变量实质上也是一个函数。因此，这一假设表明学习的目标是一个函数。然而，一个函数实质上是一个表，尽管在简单情况下，知识可以用一个表来表示，但是根本上来说，人学习的知识并不能用一个表或函数来表示。数学家们喜欢函数是因为函数简单，好研究，成果多，并不是因为函数是表示人类知识的标准模型。人工智能或者计算机科学中，把函数作为学习目标的标准模型是否正确，需要科学地来研究。2.神经网络学习模型并没有回答学习的数学实质是什么这一基本问题 因此，神经网络学

54、习模型并没有增加我们对“学习”这一概念的数学理解。3.神经网络模型学习需求大量已知或已标注的实例 然而大量已标注实例在现实世界中不容易建立，关键是人并不是通过大量已标注数据来学习的。人从观察一、两个例子就能学习，而且学得很好。因此，神经网络学习不是一个像人一样学习的模型。4.神经网络学习并没有一个可解释性 人的学习是有可解释性的，说明神经网络学习跟人学习是不一样的。而且由于没有可解释性，神经网络学习在严格科学技术标准要求下的应用是不可信的。中国人工智能系列白皮书 14 有人可能认为学习不需要可解释性。人学习是有可解释性的；现在的每一个学科的分支、领域都是可解释的。人和动物都在学习，学习作为一个

55、现实世界的重大基本现象，需要科学的研究，正确、准确、精确，到点、到位地捕捉到学习这一基本概念的（数学）实质，是科学研究的必然要求和应有之意。神经网络学习的不可解释性是这一模型的先天不足，而不是优点。如果对此没有清醒的认识，对科学和人类未来技术都有可能造成破坏性影响。5.神经网络的生成学习模型会去修改规则、修改数据，而且需要一个后台人员团队的控制 学习的结果自然地受到后台控制人员的主观因素影响。从应用技术上说，对神经网络学习模型的潜在风险、危害和威胁的认知、识别与防范，应该和它带来的收益同样重视，甚至是更加重视。综上所述，连接主义人工智能技术的新现象提出了一系列新问题：（i）神经网络人工智能技术

56、的数学原理是什么？（ii）神经网络人工智能技术的计算原理是什么？（iii）神经网络人工智能技术的安全性怎么实现？（iv）神经网络人工智能技术是否存在可解释性的原理？（v）神经网络人工智能是否可以不依赖大量的标注数据？等 1.8 行为主义人工智能 行为主义人工智能就是行为主义学习，或称为模仿学习。模仿学习本身并没有一个科学原理，更没有揭示学习这一概念的数学实质。行为主义学习更多地是一个控制原理，对揭示学习与智能的科学中国人工智能系列白皮书 15 原理没有直接的帮助。1.9 人工智能的数学、物理挑战 人工智能作为 21 世纪的重大科学问题，它的突破需要新的科学思想。同时，人工智能本身是一个交叉结合

57、的科学现象，它和其它主要学科的交叉结合、实质关系和边界界定又提出一系列新问题，例如：（1）人工智能需要什么样的新数学？（2）智能机的物理原理是什么？1.10 人工智能的重大科学挑战 人工智能的实质是实现机器智能。人是现实世界最高智能的主体。机器智能就是用机器来实现人的智能。实现智能（或人的智能）的必要条件是揭示，智能，即人的智能，的科学原理。然而，一个重大科学挑战性问题正是：智能的科学原理是什么？智能的主体是人。人是信息世界的对象，而不是物理世界的对象。智能这一概念只能在信息世界空间中来理解，而不能在物理世界空间来理解。现有的科学体系是物理世界的科学体系。人们现有的对智能的理解，包括符号主义的

58、人工智能、连接主义的人工智能、行为主义的人工智能等都是基于物理世界科学范式的关于人工智能的理解。这样的理解是有根本缺陷的。1.10.1 数学、物理对象的可分性数学、物理对象的可分性 物理世界对象的可分性：物理世界对象是任意可分的。例如：一块石头任意砸碎以后还是石头，合起来还是石头。数学对象的可分性：数学对象是任意可分的。例如：一条一米长的线段的任意分割以后的线段之和仍是一米。中国人工智能系列白皮书 16 因此：（1）物理对象是任意可分的。（2）数学对象是任意可分的。根据数学、物理对象的可分性，对数学物理对象研究的总方法论，或科学范式就是：分而治之。分而治之这个总方法论的数学理论就是微分学与积分

59、学，或简称为微积分。因此，微积分就是支撑数学、物理世界分析的原理与方法。1.10.2 信息世界对象的不可分性信息世界对象的不可分性 信息世界对象不是任意可分的。例如：（1）一个 DNA 序列是一个复杂的生命体。如果把一个 DNA 序列任意分割它就不再是生命体了。（2）一个数学命题的语义是不可分的。一个数学命题的语义就是真或假，且不再进一步可分。（3）一个生命体不是任意可分的。任意分割一个生命体，它就不再是生命体了。信息世界对象不是任意可分的，因此，分而治之不再是信息世界对象分析的方法论，微积分也不支撑信息世界对象的分析。因此，信息世界对象和数理世界对象有根本区别；信息和数学、物理不一样。用物理

60、世界的科学方法和原理来分析信息世界对象这种做法，或许在特定条件下，在技术层面是有用的，但是，在科学原理层面是不成立的。然而现在的做法，还真就是用物理世界的科学方法和原理来分析信息世界的对象与现象。这就是 21 世纪科学最大的障碍、危机、危险与威胁。那么：（1）信息世界对象分析的方法论是什么？中国人工智能系列白皮书 17（2）支撑信息世界对象分析的数学原理是什么？1.10.3 信息世界对象的可定义性问题信息世界对象的可定义性问题 数与形是经典数学的研究对象，同时数与形可以很好地表示物理世界对象。然而，信息世界的对象本身可能就是一个复杂系统，例如一个DNA、一个细胞、一个人、一个公司、甚至一个国家

61、等。对于这样的复杂对象，数、或者任意高维的向量、或者高维几何形状都不足于表示。因此，尽管经典数学的数与形仍然是表示信息世界对象的基本模型，然而，仅仅是数与形已经不足于表示信息世界的对象与现象了。表示与定义当然是科学研究的基础。信息世界的对象与现象的科学研究，在表示模型与可定义性这个最基本的问题上就遇到了新的挑战。基本问题是：表示信息世界对象的数学模型是什么？信息世界的对象是否可定义？1.10.4 人学习的基本问题人学习的基本问题 人和动物都是观察学习的。观察的数学实质是什么？人和动物的观察有什么本质区别？机器学习的目标就是由机器来实现人的学习。因此我们聚焦人的学习，而不去研究人和动物学习有什么

62、不同。人的观察本身就是一个信息处理的过程，而不是简单地如照相机照相一样。人在观察时，一眼看上去就已经做了一个层谱抽象的识别、区分与分类等。人认知世界时有一个先验的认知模型。直观地说，人的学习就是根据自己的先验模型来观察世界，并基于对观察数据的分析，发现现实世界的知识、揭示现实世界的规律、并且基于发现的知识和揭示的规律进行创造。中国人工智能系列白皮书 18 人学习的模型就是对上述直观过程的数学建模。为此，我们需要回答如下基本问题：（1）学习的数学实质是什么？（2）人的先验认知模型是什么？（3）人的先验分析方法是什么？（4）人观察的数学实质是什么？（5）知识的定义与度量是什么？（6）规律的定义是什

63、么？（7）学习的基本策略是什么？（8）学习的数学原理是什么？（9）学习的目标与极限是什么？（10）学习的数学模型是什么？1.10.5 自我意识的基本问题自我意识的基本问题 人是会主动学习的，因为人有自我意识。自我意识是什么？怎样实现一个个体的自我意识？自我意识的数学原理是什么？直观地说，一个个体的自我意识包括：（1）感知自身；（2）自我感知的先验模型；（3）区分自身与外界；（4）自身对外界作用的感知与认知；（5）来自外界的确定性对自身影响的认知；（6）来自外界的不确定性对自身影响的认知。数学地实现以上目标就揭示了自我意识的基本科学原理。基于自我意识原理所建立的机器可以实现机器自我意识。1.10

64、.6 博弈博弈/谋算的基本科学问题谋算的基本科学问题 现实世界的每一个个体或对象都有一个趋势保持自己的存在性，保持自己在环境中的作用，以及保持自己的运动性。中国人工智能系列白皮书 19 现实世界的一个环境中包括有很多对象，这些对象在运动中，对象之间相互作用。因此现实世界充满了不确定性，不确定性产生了竞争，每一个对象在竞争中都想获胜、获利。这就是现实世界的基本现象与法则。然而，在充满了不确定性、充满竞争的现实世界中，大量的对象被征服或被消灭。一个自我意识个体在现实世界的竞争与博弈中获胜、获利，保持和改善自身的存在性、保持和扩大自己在现实世界中的作用、扩大自己的运动性就是一个自我意识体智能的表现。

65、现实世界的每一个对象都有其存在性、作用和运动性；一个对象在现实世界中的存在性、作用和运动性背后的原因实际上就是该对象在现实世界中博弈的结果。因此，博弈还是一个对象存在性、作用和运动性背后的原因。博弈与竞争是现实世界的基本现象，其背后的深层逻辑必然有一些科学原理。现实世界博弈与竞争的科学原理是什么？这个问题是智能科学的重大问题，也是人工智能的重大科学问题。1.10.7 本节小结本节小结 我们已经看到，人工智能的根本科学问题实质上是信息科学的重大科学问题。因此，人工智能科学原理必然是建立在信息科学原理基础之上的。换句话说，人工智能的科学原理本质上就是信息科学原理。破解人工智能科学原理的钥匙是信息。

66、1.11 信息科学重大挑战性问题 1.11.1 经典信息论经典信息论 Shannon 1948 年定义了嵌入在一个随机变量中的不确定性的量。中国人工智能系列白皮书 20 假设 =1,2,是一个概率分布，是服从分布 的随机变量，定义嵌入在 中的不确定性的量为：()=12,称为 的熵熵。给定一个联合概率分布(,)，假设 和 分别是两个随机变量，使得(,)服从联合概率分布(,)，Shannon 定义了 和 的互信息互信息为：(;)=(,)log(,)()().互信息(;)表示了知道 的情况下消除的嵌入在 中的不确定性的量，也表示在知道 的情况下消除的嵌入在 中的不确定性的量。Shannon 1948

67、 年证明了如下通信原理：（1）（数据）假设发送方想传输的数据为，它是一个随机变量。（2）（编码）通过一个纠错码 把 编码为 =().（3）（信道传输）发送方把 通过由一个条件概率分布(|)定义的通信信道发送，传输给收方。（4）（信息）收方收到，它是一个随机变量，当收到 后，收方获得的信息为(;)，即已知 的情况下消除的嵌入在 中的不确定性的量。（5）（通信原理）当(;)适当大时，存在解码器，使得()=,即解码器 根据 就可以把发送方想发送的数据 解码出来。中国人工智能系列白皮书 21 Shannon 1948 年的论文应用概率方法证明了以上通信原理。到目前为止的信息论就是在不断优化 Shann

68、on 的通信原理。但是整个信息论没有超出 Shannon 通信模型与通信原理的范畴。Shannon的理论完美地解决了通信问题，为通信建立了数学原理，这个原理正是通信从 1G 到 5G 通信技术的理论支撑。毫无疑问，Shannon 的理论也是 20 世纪的一个重大科学贡献。Shannon 的科学贡献在于：（1）度量了嵌入在一个随机变量的不确定性的量，即该随机变量的熵；（2）通信信道可以用一个条件概率分布来表示；（3）信息是消除的不确定性；（4）信道传输是消除不确定性，即获得信息，的动作或操作；（5）信道传输所获得的信息是可以度量的；（6）信息是有用的，通过信道传输所获得的信息可以解码出发送方想发

69、送的数据。这就为通信技术提供了数学原理。（5G 通信技术已经接近实现了 Shannon 原理的极限，因此，6G需要新的通信原理。如果没有新的通信原理，原则上来说 6G 是不靠谱的。）1.11.2 生成策略生成策略 熵是不确性的量。随机变量肯定包含有不确性，Shannon 熵度量了嵌入在一个随机变量的不确定性的量。然而，随机变量只是一个特殊的函数。函数是数学中的基本对象，然而现实世界对象要复杂得多，通常情况是函数所不能表示的。函数概念的推广是二元关系，二元关系的推广是图，一个图表示是由很多个体及个体之间的关系构成的系统。现实世界中的一个对象通常是一个由很多个体及个体之间的关中国人工智能系列白皮书

70、 22 系构成的系统。一个系统的数学表示就是图或非负矩阵。因此，图（有向或无向，有权重或无权重）表示一个系统，由多个个体及从个体到个体的交互作用构成。图或系统是表示现实世界对象的基本模型，它表示了由很多相互作用的个体构成的运动系统。显然图或系统是函数的推广，从而是随机变量的推广。一个随机变量有不确定性。自然地一个图或系统表示的运动有不确定性。Shannon 熵度量了嵌入在一个随机变量中的不确定性。然而Shannon 没有给出嵌入在一个系统中的不确定性的度量。一个基本问题是：不确定性在哪里？不确定性是怎样生成的？怎样度量现实世界的不确定性？这些问题的答案将解决现实世界的不确定性的数学表示与模型，

71、回答信息是怎样生成的这一基本问题。现实世界中，不确定性来自于很多对象，而且这些对象在运动，对象之间相互作用。原因是：假设只有一个对象，则该对象按自身规律不受干扰地运动，没有不确定性；如果有很多对象，这些对象都不运动，也不相互作用，则所有对象永远保持一个状态，也没有不确定性。因此，不确定性来自于很多对象的运动和相互作用。表示很多对象的运动和相互作用的数学模型恰好就是图、或者，等价地，非负矩阵。这解决了现实世界中不确定性载体的数学表示与模型。不确定性来自于多个个体及其相互作用。因此，生成多个个体及其相互作用的动作或者操作就是一个生成策略。任何一个生成不确定性的动作或操作都是一个生成策略。一个生成策

72、略生成的信息称为生成信息。一个生成策略的生成信息是可以度量的。中国人工智能系列白皮书 23 一个基本问题是：信息生成的原理是什么？1.11.3 解码策略解码策略 信息是消除的不确定性。消除一个不确定性载体中的不确定性需要一个动作。消除不确定性的动作是开放的，有很多种动作消除不确定性。消除不确定性的动作的例子：（1）计算（2）实验（3）询问（4）每天的学习（5）想一想 等都是消除不确定性的策略。任何一个消除不确定性的动作都称为一个解码策略。一个策略就是一个生成策略，或者一个解码策略。生成策略生成不确定性，即，生成信息；一个解码策略的解码信息就是该策略消除的不确定性的量。一个策略可能是一个物理动作

73、，也可能是个数学动作，还可能是个生物动作等。由于一个策略可能是不同类型的动作，信息也因此是不同类型对象的基本概念，例如是物理概念、数学概念、计算机科学概念或生物概念等等，这取决于获取该信息的动作是物理、数学、计算机或生物动作等。给定一个信息载体，以及该载体的一个解码策略，该解码策略消除的嵌入在载体中的不确定性的量称为解码信息。解码信息是可以度量的。一个解码策略是一个动作，该动作必然来自于某一个主体，因为现实世界中的任何一个动作都不是免费的，必然来自于某个主体。一个解码策略的解码信息对该策略主体一定是中国人工智能系列白皮书 24 有用的，即解码信息一定有一个语义，表示解码信息的功能与作用。一个基

74、本问题是：信息解码的原理是什么？1.11.4 信息的模型信息的模型 信息是消除的不确定性。信息的这一定义揭示了信息是一个模型，称为信息模型信息模型，它由如下步骤构成：（1）（主体）策略的主体；（2）（信息生成）信息的生成与信息载体；（3）（解码策略）主体 对载体 的解码策略；（4）（解码信息）策略 消除的嵌入在 中的不确定性的量，即解码策略 对载体 的解码信息()，()是可度量的；（5）（信息的语义）解码信息()对策略 的主体 的作用。信息模型揭示了：（1）策略是一个新的科学概念；（2）有两种类型的策略，生成策略和解码策略；（3）生成策略必然有一个生成原理；（4）解码策略必然有一个解码原理；（

75、5）生成信息就是一个生成策略生成的信息量，即产生的不确定性的量；（6）解码信息就是一个解码策略消除的不确定性的量；（7）生成信息是可以度量的；（8）解码信息是可以度量的；（9）生成信息是有用的；（10）解码信息是有用的。信息模型揭示了作为科学概念的信息的数学实质。注意到，经典中国人工智能系列白皮书 25 信息论中，严格意义上说，信息只是一个通信概念，而不是一个科学概念。作为科学概念的信息和作为通信概念的信息是两个本质不同的概念。1.11.5 信息基本定律信息基本定律 信息作为一个全新的科学概念，它不属于任何一个已有的学科，例如数学、物理、化学、计算机、生物等，但是由于解码信息的策略可以是任何已

76、有学科的操作，例如数学操作、物理操作、化学操作、计算机算法或生物动作等，信息也是包括数学、物理、化学、计算机、生物等学科的基本概念。作为一个全新的科学概念的信息必然有一些新的基本公理或定律。一个基本问题是：信息的基本定律是什么？1.11.6 信息科学是什么？信息科学是什么？信息是一个全新的科学概念。信息科学就是一个全新的科学，它不同于已有的任何学科，包括数学、物理、化学、计算机、生物等任何一个已有的学科，同时信息也是所有这些学科的基本概念。经典信息论中“信息”的实质是一个通信概念，它表示信道传输所解码的信息，或者通过信道传输这一动作或操作所消除的不确定性的量，这时，解码策略就是信道传输，它是消

77、除不确定性的动作。信息模型揭示了：（1）确定性和不确定性是可以相互转化的，转化是有条件的，即需要一个动作或操作，这个动作或操作称为策略；（2）从确定性到不确定性的转化的策略称为生成策略；（3）从不确定性到确定性的转化的动作或操作称为解码策略；（4）生成策略的生成信息是可度量的；（5）解码策略的解码信息是可度量的；中国人工智能系列白皮书 26（6）信息科学就是研究现实世界的确定性和不确定性，以及确定性和不确定性之间相互转化的规律与作用的学科。1.11.7 信息的数学理论是什么？信息的数学理论是什么？信息是一个全新的科学概念，是揭示和分析信息世界的钥匙。信息世界的科学范式，或总方法论是什么？这个总

78、方法论的数学理论是什么？信息世界的科学范式，即总方法论是：层谱抽象。层谱抽象的数学定义是编码树，见第九章。编码树的意义是：（1）编码树是层谱抽象的数学模型；（2）编码树是层谱抽象的数据结构；（3）编码树是一个全局的无损编码。层谱抽象的意义在于：（1）层谱抽象是一个离散系统的微分算子；（2）层谱抽象是一个信息系统的解码策略；（3）层谱抽象是信息世界对象的范式；（4）层谱抽象是先验认知模型；（5）层谱抽象是先验感知模型等。显然信息世界总方法论的数学理论就是支撑信息世界分析的数学原理。层谱抽象作为解码策略的信息论就是信息的数学理论，它也是信息模型的数学理论，见本白皮书第十章。1.12 信息科学原理

79、信息的数学理论揭示了信息科学的三大原理：（1）信息演算理论；（2）信息解码原理；（3）信息生成原理。中国人工智能系列白皮书 27 信息演算理论提供了基于编码树的推理理论，建立了融合逻辑推理与直觉推理的数学理论。更为重要的是信息科学原理建立了层谱抽象这一认知模型的数学原理与理论。由于层谱抽象是信息世界的科学范式和认知模型，信息科学原理建立了层谱抽象认知模型的数学理论，为信息时代的科学提供了新的动力。现有的科学体系的各学科分支、方向都是在物理世界的科学范式，即，范畴的研究，其总方法就是分而治之这一分析方法。总体而言，分而治之是一个科学分析方法，它是物理世界科学体系的总发动机。信息科学原理揭示了信息

80、时代的科学研究有两个发动机：分而治之的分析方法，和层谱抽象的认知模型，这就构成了信息时代科学的双引擎。信息科学原理，见本白皮书第十章，就是层谱抽象认知模型的数学原理与理论。信息时代科学的双引擎首先解决的一个科学问题是人工智能科学的建立，见本白皮书第十一章、第十二章、第十三章和第十四章。1.13 本章小结 本章分析了人工智能的起源，各阶段的理论基础及根本缺陷，揭示了人工智能是科学发展的必然结果，指出人工智能科学是 21 世纪的重大科学障碍。分析了现有科学体系的缺陷，人工智能的重大挑战、信息世界的重大科学挑战性问题。分析了人工智能科学的根本问题；提出层谱抽象认知模型；提出层谱抽象感知模型；提出博弈

81、的信息原理和数理原理；提出博弈的必胜策略原理；揭示了人工智能的路线图：（观察）学习、自我意识和中国人工智能系列白皮书 28 在竞争中获胜、获利等基本策略和概念。提出了信息的模型；揭示了信息这一科学概念的数学实质；提出了策略这一全新的科学概念，以及生成策略和解码策略的基本概念；提出层谱抽象这一信息世界的科学范式；揭示了层谱抽象这一认知模型与方法，建立了未来科学与技术的新动力。中国人工智能系列白皮书 29 第二部分 逻辑推理人工智能与计算人工智能 中国人工智能系列白皮书 30 第 2 章 符号主义人工智能 2.1 命题知识表示与推理 知识表示与推理是人工智能中的一个重要领域。早在 1958 年，麦

82、卡锡考虑的人工智能系统建议采纳者（Advice Taker 1，其可被视为第一个完整的人工智能系统2）已主张采用知识求解问题。目前，知识表示与推理方法的应用涵盖了人工智能领域的多个应用分支，包括形式化验证、问答系统、语义网、自动规划、感知机器人和多智能体系统在内的多个领域3。逻辑是一种使用时间最长，且应用最为广泛的知识表示方法，几乎所有其它知识表示方法都能够使用某种逻辑进行等价表示。早在计算机时代到来之前，数理逻辑学家就已开始使用经典逻辑形式化表示陈述性的知识，主要为了对数学进行形式化，以自动进行定理证明。尽管经典逻辑在某些情况下不能表达人工智能中各式各样的非数学形式的知识，但毫无疑问其仍然在

83、知识表示领域占有举足轻重的地位，其中一阶逻辑由于其极强的表达能力、易理解的基于模型论的语义以及较好的推理能力而应用最为广泛。研究人员为一阶逻辑提出了多种的推理方法，例如 Tableau 方法4、DP 方法5、归结方法6等，开发了包括 Otter7、3TAP8、Isabelle9等在内的多个推理机。一阶逻辑最大的问题在于其推理代价过于昂贵，命题逻辑是一阶逻辑的子集，近二十多年来随着命题可满足性（satisfiability，SAT）问题求解器效率的快速提高，其在人工智能中发挥着越来越重要的作用10。从本质上讲，SAT 求解器提供的是一个通用的命题推理平台，但是其可应用于推理之外的多个组合优化领域

84、。例如，自动规划问题是 PSPACE 完全的，当规划解的长度被限制为多项式时，该问题为NP 完全问题，可编码为 SAT 问题，著名的 SatPlan 规划器11在该思想的基础上实现，其在国际规划竞赛中多次夺得第一名。另外，在有界模型检测（bounded model checking）12和回答集编程13等领域，SAT中国人工智能系列白皮书 31 求解器都有重要应用。实际上，很多组合优化问题，通过编码为 SAT问题后再调用 SAT 求解器的求解效率甚至高于直接求解原问题的效率3。2.1.1 命题逻辑命题逻辑 命题逻辑下的公式由逻辑常量（true 和 false）、命题变量（表示为斜体小写字母，如

85、 x、y、z）和逻辑联接词（否定、合取）组成。本文记公式中出现的变量的集合为 Vars()。任意变量集 X 上赋值是从 X 到true,false的映射，X 上所有赋值的集合记为 2X。给定公式以及 X 上的赋值，其中 Vars()X，满足递归定义如下：（1）满足 true；（2）不满足 false；（3）满足 x 当且仅当 x true ；（4）满足当且仅当不满足；（5）满足 当且仅当满足和满足。给定公式和，若对于 Vars()Vars()上的任意赋值满足都有满足，则称蕴含，与等价（记为 ）当且仅当与相互逻辑蕴含。等价于常量 true 或 false 的公式称为平凡（trivial）公式。给

86、定公式，Vars()上满足的赋值称为的模型，的所有模型的集合记为 M()，是可满足的（satisfiable）当且仅当 M()，是有效的（valid）当且仅当 M()2Vars()。给定任意赋值，其中赋值为 false 的变量数称为的度（cardinality）。给定公式，若其可满足，则的最小度定义为 M()中所有元素的度的最小值，否则定义为。为了方便，本文还将使用到如下五个逻辑联接词（其定义如表1.1）：析取、条件、反条件、双条件和决策 ITE（表示“if.then.else.”）。任意公式的大小为|表示公式中使用的逻辑联接词的数目。表表 2-1 逻辑联接词逻辑联接词 中国人工智能系列白皮书

87、 32 名称名称 定义定义 析取 ()条件 反条件 双条件 ()()决策 ITE ITE(,)()()在下文中，我们将使用到如下特定类型的公式：（1）文字（literal）：变量 x（正文字）或其否定x（负文字）。给定文字 l，若 l x，则其否定文字l 为x，否则其否定文字为 x，l与l称为互补的文字。给定不含互补文字的文字集L，下文记Vars(L)x:x L 或x L，记(L)x false:x L x true:x L。给定赋值，下文记 L()x:x false x:x true ；（2）子句（clause）：多个文字的析取，在明确上下文中子句有时亦表示为文字的集合，相反，给定文字集 L

88、，在非明确上下文中我们使用(L)表示 L 中所有文字的析取组成的子句；（3）项（term）：多个文字的合取，在明确上下文中项有时亦表示为文字的集合，相反，给定文字集 L，在非明确上下文中我们使用(L)表示 L 中所有文字的合取组成的项；（4）合取范式（conjunctive normal form，CNF）：多个子句的合取，有时亦表示为子句的集合，所有子句中文字数为 k 的 CNF 公式记为 k-CNF 公式，其中 k 为常数；（5）析取范式（disjunctive normal form，DNF）：多个项的析取，有时亦表示为项的集合；（6）否定范式（negation normal form，

89、NNF）：否定运算符只出现在变量之前的公式，显然，任意 CNF 和 DNF 公式都为 NNF 公式。中国人工智能系列白皮书 33 任意命题公式可表示为有根的有向无环图，每个终止节点标记为常量或变量，非终止节点标记为逻辑联接词，然后相同的子公式可合并为一个节点从而节省空间开销。2.1.2 命题推理问题命题推理问题 命题知识库通常表示为命题公式，库中的知识表示为被该公式蕴含的所有公式，因此命题推理问题通常可表示为知识库的查询问题。本文中涉及到的推理问题如下：（1）判定知识库的一致性，也即判定对应命题公式的可满足性。该问题的重要性主要来源于两方面。第一，不满足当且仅当 可满足，因此该问题在自动推理中

90、处于核心位置。第二，SAT 问题是第一个被证明为 NP 完全的问题，其多项式时间的求解算法将导致所有 NP 中问题皆能在多项式时间求解。由于任意逻辑公式的可满足性问题都可转化为某个线性大小的 CNF 公式的可满足性问题，且 CNF公式的可满足性问题也是 NP 完全的，因此有时 SAT 问题也简单表示为 CNF 公式的可满足性问题，k-CNF 公式的可满足性问题相应称为kSAT 问题。当 k 3 时，kSAT 问题是 NP 完全的，而 2SAT 问题为NL 完全的。（2）判定知识库的有效性。该问题与 SAT 问题互补，是 co-NP完全的。（3）判定知识库是否蕴含某个子句。由于任意公式都可表示为

91、等价的 CNF 公式，而知识库蕴含一个 CNF 公式当且仅当其蕴含 CNF中所有子句，因此任意表示语言是否支持多项式时间的子句蕴含判定算法是衡量该语言易处理性的最基本标准14 15 。（4）判定某个项是否蕴含知识库。该问题与子句蕴含判定问题互补，在基于模型的诊断领域有重要应用。（4）计算知识库的模型数。CNF 公式的模型计数问题为#P 完全问题，模型计数问题在人工智能和形式化验证领域具有众多应用场景，中国人工智能系列白皮书 34 例如，解决多种概率推理问题，如贝叶斯网络推理可以高效地转化为模型计数问题16 ，文献17 提出的基于加权模型计数的贝叶斯推理方法是目前最快的精确贝叶斯推理方法.此外,

92、模型计数还在自动规划18 、神经网络验证19 等领域有着广泛的应用场景。（5）枚举知识库的所有模型。该操作在产品配置中有重要应用，可用于枚举出所有满足用户需求的方案20 。（6）判定知识库间的等价性。该问题在电子设计自动化领域有重要应用，可用于确定两种电路设计是否表现出完全相同的行为21 。（7）判定知识库间的蕴含关系。（8）计算知识库的最小度。知识库的最小度在某些应用中代表明确的语义。例如，在基于模型的诊断中，最小度可表示给定可观察系统中最小的故障数；又如，在自动规划中，可用于表示得到指定目标所需的最少动作数22 。2.1.3 命题可满足性求解方法命题可满足性求解方法 当命题知识库表示为 C

93、NF 公式时，目前高效的 SAT 求解能较好地解决一致性判定这一问题，在某些情况下甚至可在较短的时间内判定出多达上百万个变量的知识库的一致性。对于其他命题推理任务中，除模型计数、模型枚举以及计算最小度外，也可通过调用一次或线性次 SAT 求解器进行求解。例如，对于子句蕴含问题，蕴含当且仅当 可满足。又如，对于知识库间蕴含问题，蕴含当且仅当对于任意 都有蕴含。SAT 问题是第一个被证明为 NP 完全的问题，Cook 也因此获得了图灵奖。SAT 求解方法主要可分为完备和非完备两类，前者能判断出可满足性并对于可满足的问题能给出解，后者对于不可满足的问题无法给出判断。完备的求解方法中使用最广的为 DP

94、LL 算法5 23 ，最早由Davis 和 Putnam 于 1960 年提出，并在 1962 年由 Davis、Logemann、Loveland 进行进一步的优化，这是一种搜索树上的深度优先搜索算法，中国人工智能系列白皮书 35 它结合了单文字规则、纯文字规则等缩小搜索空间，主要思想是在公式的所有部分赋值的空间中进行回溯搜索。在 DPLL 框架下，研究人员通过嵌入多种优化技术实现了多个高效的求解器，最著名优化技术为 1996 年 Silva 和 Sakallah24 在求解器 GRASP 中提出的冲突学习技术，后续的完备的求解器都使用到了这项技术，该技术通过对冲突进行分析学习新子句缩减搜索

95、空间，极大的提高了 DPLL 方法的效率，现代的 SAT 求解都使用到了这项技术，对应的求解器也被称为基于冲突的子句学习（Conflict-driven clause learning，CDCL）求解器。最经典的 CDCL 求解器是 MiniSAT25 ，后续的很多求解器PrecoSAT26 、CryptoMiniSat27 、Kissat28 等都是在 MiniSAT 的源代码基础上改进的。非完备求解方法多基于局部搜索，包括 GSAT29 、Walksat30 、调查传播（survey propagation）31 、格局检测32 等。自 2002 开始，SAT 领域内每年举办一次 SAT

96、竞赛，也极大地推动了SAT 问题求解效率的提高。国内对于 SAT 问题也取得了很多研究成果，早在 2000 年，中科院软件所张健研究员出版了一部关于可满足性求解器的专著，中科院软件所蔡少伟和华中科技大学何琨等研究组在 SAT 竞赛中多次获得冠亚军，吉林大学欧阳丹彤团队在基于扩展规则的 SAT 求解方面发表了一系列的成果。2.1.4 模型计数模型计数 模型计数问题是 SAT 问题的重要扩展，该问题旨在计算满足公式的赋值的数量。模型计数问题相较于 SAT 问题更具有挑战性，具有#P 完全的计算复杂性。总体而言，模型计数方法可分为精确和近似两大类。随着模型计数应用需求的持续增长以及学界对模型计数相关

97、算法研究的不断深入，再加之模型计数竞赛10的推广，领域中已出现了数十种模型计数求解器。精确求解算法主要分为三类：基于搜索、基于编译以及基于变量中国人工智能系列白皮书 36 消元。基于搜索的模型计数方法的主要思想是通过更智能的枚举部分解来扩展 DPLL 框架33 。开创性的基于搜索的模型计数求解器是Cachet34 ，它首先实现了将组件（子句的子集）缓存与冲突驱动的子句学习相结合来进行模型计数。随后的模型计数求解器sharpSAT35 改进了组件缓存方案以及决策启发式。在sharpSAT的基础上，Ganak36 进一步引入了概率缓存。考虑到 Cachet、sharpSAT 和 Ganak 按照D

98、ecision-DNNF37 进行搜索,可扩展模型计数器 ExactMC38 按照Decision-DNNF 的泛化表示进行搜索,实验结果表明能明显著提高求解效率。最近的 SharpSAT-TD39 在 sharpSAT 的基础上使用FlowCutter 算法计算输入公式的树分解，并将树分解应用到决策启发式中，在 2021 年的模型计数比赛中取得了冠军。基于编译的技术依赖于高效的知识编译器，编译器将输入语言表示的公式编译为目标语言表示的公式，编译后可以使用目标语言的表示高效地进行模型计数。例如，可以将公式转换为二元决策图并从标记为 1 的叶节点开始一直遍历到根节点以读取解的数量。c2d41 就

99、是一个著名的基于编译的模型计数求解器，它将给定的合取范式公式转换为可分解的否定范式,而该范式是有序二元决策图的严格超集，并且通常更简洁.其他有代表性的模型计数求解器还有 Dsharp42 、miniC2D43 和 d444 等。基于变量消除的方法将问题表述为，并通过对变量进行一系列相乘、映射来执行模型计数。ADDMC45 是一个具有代表性的基于变量消除的模型计数求解器，它的主要思想是使用代数决策图来执行相乘、映射操作。随后，研究人员提出了一个统一的动态规划框架，称为DPMC46 ，ADDMC 可以视为 DPMC 的特例。在 DPMC 框架中,公式的模型计数是对公式构建项目连接树后计算得到。近似

100、模型计数算法根据提供的近似保障可进一步分为三类。第一类是提供(,)近似保证的近似求解器，假设真实模型数为 Z，则求解器能在 1的概率内输出介于Z/(1+)，Z(1+)的估计值，代表性的求中国人工智能系列白皮书 37 解器为 ApproxMC47 。第二类求解器提供一定概率下的上界或下界保证，代表性的求解器包括 MBound48 和 SampleCount49 。第三类不提供任何保证，但在实际应用中可扩展性最强，代表性的求解器为 satss50 和 STS 51 。目前国内开展模型计数研究的单位包括吉林大学、中科院软件所、东北师范大学、暨南大学等。2.1.5 知识编译知识编译 命题推理问题通常被

101、认为是不易处理的。例如，命题知识库的子句蕴含查询为 co-NP 完全问题，通常被认为不存在多项式时间的求解算法。知识编译是解决这种不易处理性问题的重要方法14 15 52 ，目前已被应用到模型检测53 、诊断54 、产品配置55 、自动规划56 、数据库57 和数据挖掘58 等多个领域。命题推理问题可从概念上分为知识库和查询两部分，其中知识库的更新频率较低，人们通常需要对同一知识库做多次查询。知识编译的主要思想是将查询应答过程分成两个阶段：离线的编译阶段(off-line compilation phase)和在线的查询应答阶段(online query-answering phase)。在离

102、线时将命题公式编译为易处理的目标语言(target language)，从而能更有效地回答在线阶段的查询。离线阶段的时间代价能在多次（甚至指数次）的在线查询中通过类似于分期付款的方式补偿回来。目标语言是任意知识编译方法的重要方面，其最基本的要求是需满足多项式时间的子句蕴含查询。目前在实际中应用较为广泛的目标语言主要可分为如下三大类。第一类为 CNF 和 DNF 的子集，主要包括 Horn 理 论14 59 、本 原 蕴 含 式/本 原 蕴 含 范 式（prime implicates/implicants normal form，PI/IP）60 61 62 63 、EPCCL（each pa

103、ir containing complementary literals）理论65 、MODS（models）52 等。第二类为有序二元决策图（ordered binary decision diagram，OBDD）66 及其推广。第三类为可分解否定范式（decomposable negation 中国人工智能系列白皮书 38 normal form，DNNF）22 及其子集。由于到目前为止研究人员针对不同的推理问题提出了多种知识编译语言，从而增加了在实际应用中选择合适编译语言的困难性。鉴于此，文献52 主张按照如下三个标准对知识编译语言进行评估：简洁性（succinctness），多项式时

104、间内支持的查询的种类以及多项式时间内支持的转化的种类。文献52 按照上述三种标准对多种知识编译语言进行了评估，并将评估结果形成了一个知识编译图谱（knowledge compilation map）。之后，研究人员多次对知识编译图谱进行了扩展。除了知识编译图谱中涉及到的三个重要评价标准外，知识编译语言是否具有规范性（canonicity，即对于任意知识库，对应编译结果是唯一的）也是实际应用中选择知识编译语言需要考虑的一个重要因素，其能极大方便搜索最优编译结果。例如，OBDD 在实际中广泛应用的一个重要因素即为 ROBDD 具有规范性，且能在线性时间内通过等价的 OBDD 得到 ROBDD67

105、。国内吉林大学最早开展了知识编译的研究，提出了 EPCCL、OBDD、CCDD 等知识编译语言，并设计了多个编译器。2.2 自动定理证明 2.2.1 自动定理证明的起源、发展与现状自动定理证明的起源、发展与现状 第一个可运行的定理证明程序是1954年由逻辑学家Martin Davis完成，实现了普利斯伯格算术(Presburger Arithmetic)的判定过程68 。自然数的一阶理论又称皮亚诺算术，包括自然数的加法和乘法，普利斯伯格算术是皮亚诺算术的一个子集，只有加法没有乘法。皮亚诺算术不可判定，但普利斯伯格算术则是可判定的。这个证明器证明了“两个偶数之和还是偶数”。1956 年的达特茅斯

106、人工智能讨论会议被认为是人工智能研究领域的起源。讨论会上，Newell 和 Simon 发表 逻辑理论机（The Logic 中国人工智能系列白皮书 39 Theory Machine），被认为是自动定理证明（Automated Theorem Proving，ATP）领域的第一篇论文69 。逻辑理论机的目标是想机械地模仿人类在证明命题逻辑时所用的推导过程，它可以证明怀海特和罗素数学原理第一卷中命题逻辑部分的一个很大的子集。1957 年 Dag Prawwitz 和他父亲编程实现了根岑 Gentzen 提出的自然演绎，发表了影响深远的论文，在论文中提出合一的概念70 。1959 年 IBM 的

107、 Gelernter 等人实现几何定理证明器71 。该系统采用“反向链”的推理方法，从目标开始向前提产生新的子目标，这些子目标逻辑蕴涵最终目标。几何定理证明器能够证明直线图形中的大部分高中考试的问题，并且运行时间也常常与高中生解题时间近似。同年，与 Gelernter 同项目组的同事 Gilmore 实现了基于语义表(Semantic Tableau)方法的定理证明器，被认为是对谓词演算的第一个可用的机械证明程序72 。1958 年至 1960 年间，王浩先后实现了三个 ATP 程序73 ：一个完全的命题逻辑程序，一个谓词逻辑程序及其改进。其改进的谓词逻辑程序在 40 分钟内证明了数学原理中全

108、部的 150 条谓词逻辑以及 200 条命题逻辑定理。王浩的这项工作说明让机器拥有人类的技巧已不再是一种游戏。Gilmore 方法的理论基础是 Herbrand 定理：为证明某谓词逻辑公式的恒假性，转化为去证明该谓词逻辑公式在 Herbrand 域上实例化得到的命题公式的恒假性75 。在证明命题公式恒假性时，Gilmore 采用了最原始的“乘法方法”。1960 年，Martin Davis 和 Hilary Putnam 对 Gilmore 方法做了改进，提出所谓的 D-P 过程76 ，后进化为当前使用的 DPLL 过程77 。但是，D-P 过程对 Gilmore 方法的改进不是本质的，因为这

109、两种方法，都需要枚举基替换，去产生恒假的命题公式。1960 年 Dag Prawitz 发表论文，指出 D-P 过程的这个致命弱点，中国人工智能系列白皮书 40 并给出了改进70 。Prawitz 不再枚举替换去产生恒假的命题公式，而是主动去寻找产生这个恒假命题公式的那个替换。Prawitz 的“直接寻找替换，从而避免产生公式的组合爆炸”这种思想是深刻的，使用了人工智能中的匹配技术。但 Prawitz 在实现这种想法时，效果却很不理想。1960 年前后的三年间，是自动定理证明领域中逻辑方法的一段重要时间。基于 Herbrand 定理的 Gilmore 方法，D-P 过程，尤其是 D-P 过程中

110、的单文字规则和 Prawitz 的匹配思想，最终导致归结原理的产生。1964 年 J.A.Robinson 提出简洁而漂亮的归结原理78 。被Robinson 用归结原理所形式化的逻辑里，没有公理，只有一条使用合一替换的推导规则。而如此简洁的逻辑系统，却是谓词演算中的一个完备系统：任意一个恒真的一阶公式，在 Robinson 的逻辑系统中都是可证的。重要的改进工作包含：1964 年 Wos，Carson 和 G.Robinson 提出了单文字子句优先处理79 和支撑集策略80 。1965 年 J.A.Robinson 提出超归结方法。1967年提出语义归结81 。1968年Loveland和L

111、uckham提出线性归结82 。1970 年 Boyer 提出锁归结。1970 年提出 SL-归结83 ，被用于早期的PROLOG 语言中。1970 年 C.L.Chang 提出输入归结，并证明其和单元归结等价84 。1982 年 Murray 提出 NC（Non-Clausal）归结85 。相等是数学中重要且常见的概念，对于包含等词的公式进行推理需要特殊的规则：Wos 等人提出 Paramodulation 调解方法86 ，调解方法被推广为 superposition 方法，成为现代定理证明器的理论和实践基础88 。方程式（等式）是一阶逻辑的子集，即只有一个谓词 EQUAL。BirkHoff

112、 证明了方程逻辑是完全的。在项重写89 中，证明就是将一个符号串（实际上是谓词逻辑中的项）根据给定的等式重写成另一符中国人工智能系列白皮书 41 号串。为减少生成的项的数量，引入项之间的序关系来限制重写。Knuth-Bendix Ordering是上世纪七十年代提出的用于项重写的主要技术90 。上世纪八十年代后，自动定理证明领域没有突破性的进展，但该方向逐渐改名为自动推理，希望计算机程序成为一种工具，能够自动完 成 各 种 需 要 的 推 理 任 务。自 动 推 理 领 域 的 归 结 会 议 是CADE(Conference of Automated DEduction)91 和 IJCAR

113、(International Conference of Automated Reasoning)92 ，它们都是双年会议，每年两个会议交替召开。CASC(CADE ATP System Competition)是至今每年仍在 CADE 或 IJCAR 会议上举办的自动定理证明系统比赛93 ，赛题来自 TPTP(Thousands Problems for Theorem Provers)，TPTP 是定理证明器的公认的benchmark94 。历年的CASC冠军中包括Otter95 ,Vampire96 等著名定理证明器。归结原理导致的组合爆炸仍然需要启发式方法的帮助，定理证明领域陷入停滞状

114、态。近年，谷歌团队的实验表明，简单的卷积神经网络可以帮助定理证明器挑选子句从而提高性能97 。另一方面，研究者们在几何定理证明与计算机代数方向取得比较满意的结果，代表性的工作为吴文俊院士在上世纪七十年代针对特定初等几何问题得到高效的算法98 ，并且被推广到一类微分几何问题上99 。2.2.2 Herbrand 定理定理 在离散数学中证明过 Skolem 范式的性质：设谓词逻辑公式 G 的Skolem 范式为 S，则 G 的不可满足性与 S 的不可满足性等价。因此，若想证明谓词逻辑公式 G 是不可满足的，可以通过证明 S 的不可满足性来实现。相比于公式 G 可以具有任意形式，S 是只包含全称量词

115、的前束范式，并且母式为合取范式（若干个子句的合取）。因此，S 可以看成是一个子句集合，该集合中出现的量词均是被全称量词作用。中国人工智能系列白皮书 42 这就是下面经常谈论子句集的原因。项、文字、子句等若不含变量，则相应地称为基项、基文字和基子句。首先介绍子句集 S 的 Herbrand 域。设 H0是出现于子句集 S 的常量符号集合，若 S 中无常量符号出现，则H0由一个常量符号a组成。对于i=1,2,.,在Hi-1中加入fn(t1,.,tn)得到的集合 Hi称为 S 的 i 级常量集，其中 fn是出现在 S 中的所有 n元函数符号，项 t1,.,tn取自 Hi-1。H称为 S 的 Herb

116、rand 域。例 1：S=P(f(x),a,g(y,z),b)，于是，H0=a,b H1=a,b,f(a),f(b),g(a,a),g(a,b),g(b,a),g(b,b)H2=a,b,f(a),f(b),g(a,a),g(a,b),g(b,a),g(b,b),f(f(a),f(f(b),f(g(a,a),f(g(a,b),f(g(b,a),f(g(b,b),g(a,f(a),g(a,f(b),g(a,g(a,a),g(a,g(a,b),.只要子句集 S 中包含函数符号，则 S 的 Herbrand 域是无限集。对于子句集 S 中子句 C，使用 S 的 Herbrand 域中元素代替 C 中变

117、量得到的基子句构成的集合称为 C 的基例集。定理 1（Herbrand 定理）子句集 S 是不可满足的，当且仅当存在S 的一个有限不可满足的 S 的基例集 S。Herbrand 定理指出了一种证明子句集 S 的不可满足性的方法：如果存在一个机械程序，它可以分别用 H1,H2,.中的元素生成 S 中子句的基例集 S1,.,Sn，并依次检查 S1,.,Sn,.的不可满足性，那么根据 Herbrand 定理，如果 S 是不可满足的，则这个程序一定可以找到一个有限数 N，使 SN是不可满足的。因为每个 Si可以视为该集合中全部基子句的合取，因此可以使用命题逻辑中的任意方法检查 Si的不可满足性。Gil

118、more 是实现这个想法的第一人，他将 Si化为析取范式，如果其中任意一个短语包含一个互补对（文字与该文字的否定），则可以从析取范式中删除该短中国人工智能系列白皮书 43 语。最后，如果某个 Si是空的，则 Si是不可满足的。Gilmore 方法需要求析取范式，因此面临组合爆炸的情况，为了克服这个缺点，Davis和 Putnam 提出改进方法，即后来的 DPLL 过程77 。即使采用 DPLL 来判定命题公式的不可满足性，Herbrand 定理的主要障碍仍然是它要求生成关于子句集 S 的基例集 S1,S2.,，在多数情况下，这些集合的元素个数是以指数方式增加的。非常有可能发生：子句集 S 的最

119、小的不可满足基例集 Sk的元素数远超计算机的存储能力，更别提来判定 Sk的不可满足性了。为了避免上述情况，J.A.Robinson 于 1965 年文章中提出归结原理78 ，可以直接判定任意子句集 S（不一定是基子句集）的不可满足性，其的核心思想是合一算法，通过合一算法来主动生成能证明 S不可满足性的实例。2.2.3 合一与匹配合一与匹配 替换是形如t1/v1,.,tn/vn的有限集合，其中 vi是变量符号，ti是不同于 vi的项，并且 v1,.,vn互不相同。设替换=t1/v1,.,tn/vn，E 是表达式，将 E 中出现的每个变量符号 vi，都用项 ti来代替，得到的表达式记为 E，称为

120、E 的例。替换的乘积：设替换=t1/x1,.,tm/xm，=u1/y1,.,un/yn，将集合t1/x1,.,tm/xm,u1/y1,.,un/yn中任意满足如下条件的元素删除，（1）ui/yi，当 yix1,.,xm；，（2）tj/xj，当 tj=xj时；如此得到的替换称为替换 和 的乘积，记为。替 换 称 为 是 表 达 式 集 合 E1,.,Ek 的 合 一，当 且 仅 当E1=E2=.=Ek。表达式集合E1,.,Ek的合一 被称为最一般合一（匹配），当且仅当对此集合的任意合一，都存在替换 满足=。例如表达式集合P(a,y),P(x,f(b)是可合一的，其最一般合一为a/x,f(b)/y

121、。对于有限的可合一的表达式集合，存在合一算法返回其最一中国人工智能系列白皮书 44 般合一。2.2.4 归结原理归结原理 2.2.4.1 基子句的归结原理 对任意两个基子句 C1和 C2，如果 C1中存在文字 L1，C2中存在文字 L2，且 L1=L2，则从 C1，C2中分别删除 L1，L2，将 C1，C2的剩余部分析取起来构成子句，称为 C1和 C2的归结式。例如，C1=PQR，C2=QS，于是 C1和 C2的归结式为PRS。设 C1，C2是两个基子句，则 C1，C2的归结式 C 是 C1和 C2的逻辑结果。设 S 是子句集，从 S 推出子句 C 的演绎是有限子句序列：C1,C2,.,Ck。

122、其中Ci或者是S中子句，或者是Cj和Cr的归结式（ji,ri）；并且 Ck=C。从 S 推出空子句的演绎称为反驳，或称为 S 的一个证明。从子句集 S 演绎出子句 C，是指存在一个从 S 推出 C 的演绎。例 2，S=PQ,PQ,PQ,PQ（1）PQ；（2）PQ；（3）PQ；（4）PQ；（5）Q 由（1）,（2）；（6）Q 由（3）,（4）；（7）由（5）,（6）。如果基子句集 S 是不可满足的，则存在从 S 推出空子句的归结演绎。2.2.4.2 一般子句的归结原理 提升引理：如果 C1和 C2分别是子句 C1和 C2的例，C是 C1和C2的归结式，则存在 C1和 C2的一个归结式 C，使 C

123、是 C 的例。根据 Herbrand 定理和提升引理，可以证明一阶逻辑中归结原理的完备性：若子句集 S 是不可满足的，则存在从 S 推出空子句的归结演绎。中国人工智能系列白皮书 45 例 3：已知某些病人喜欢所有的医生，没有一个病人喜欢任意一个骗子。证明任意一个医生都不是骗子。证：令 P(x):x 是病人 D(x):x 是医生 Q(x):x 是骗子 L(x,y):x 喜欢 y A1:x(P(x)y(D(y)L(x,y)A2:x(P(x)y(Q(y)L(x,y)B:x(D(x)Q(x)要证明公式 A1A2B 是不可满足的，先求出其 Skolem 范式中的子句集：A1=xy(P(x)(D(y)L(

124、x,y)，Skolem 范式为 y(P(a)(D(y)L(a,y)A2=xy(P(x)Q(y)L(x,y)，Skolem 范式与前束范式相同 B=x(D(x)Q(x)，Skolem 范式为 D(b)Q(b)因此，A1A2B 公式的子句集为下述（1）-（5）（1）P(a)；（2）D(y)L(a,y)；（3）P(x)Q(y)L(x,y)；（4）D(b)；（5）Q(b)；（6）L(a,b)由（2），（4）；（7）Q(y)L(a,y)由（1），（4）；（8）L(a,b)由（5），（7）；（9）由（6），（8）。2.2.4.3 删除策略 归结原理是比 Gilmore 或 Herbrand 方法更有效的判

125、定一阶逻辑中国人工智能系列白皮书 46 中公式的不可满足性的方法。但是，归结原理的效率，也由于在归结过程中产生大量的无用子句而受到影响。在子句集 S 上使用归结原理的最直接的一种方法是，计算 S 中所有子句对的归结式，并将这些归结式并入 S，再进一步计算所有子句对的归结式。重复此过程，直到空子句被导出。这个过程被称为水平浸透法。对前面例子中子句集S=PQ,PQ,PQ,PQ使用水平浸透法，将生成非常多的对导出空子句无用的子句。为了解决防止多余子句产生这个问题，提高归结推理效率，删除策略被引入。称子句 C 包含子句 D，当且仅当存在替换 使得 CD。D 称为被包含子句。例如，设C=P(x),D=P

126、(a)Q(a)，令=a/x，则C=P(a)D，即 C 包含 D。设 S 是子句集，下面的序列是从 S 出发推出子句 C 的演绎 D：C1,C2,.,Ck(=C)。如果 Ci是重言式，或者 Ci被某个 Cj包含（jt,lr 时，才能用 r 替换 l 得出 sr=t，其中 sl表示包含项 l 的项。2.2.7 几何定理证明和数学机械化几何定理证明和数学机械化 哥德尔证明一阶整数（算术）是不可判定的，但几乎同时塔尔斯基则证明一阶实数（初等几何和代数）是可判定的。塔尔斯基的结果意味着可以存在算法能对所有初等几何和代数问题给出证明。但塔尔斯基的原始算法是超指数的，被后人多次改进后仍然很难被当作通用中国人

127、工智能系列白皮书 51 算法。数学家吴文俊受到中国数学思想的启发，针对某一大类的初等几何问题给出了高效的算法。后来又将这种方法推广到一类微分几何问题上。在定理证明的早期，研究者追求“一招鲜吃遍天”，即找到一个超级算法能证明所有问题，最典型的例子是归结方法和 superposition。王浩不认可这种思路，他认为他自己的早期工作和吴文俊的方法都表明最有效的方法是先找对一个相对可控的子领域，然后针对这个子领域的特性，找到有效的算法。吴文俊院士喜欢用“数学机械化”而不是“机器定理证明”来描述自己的工作。笛卡儿认为代数使得数学机械化，因此使得思考和计算步骤变得容易，无须花很大脑力。小学算术很难的题目，

128、在初中代数中通过方程很容易被解决。每一次数学的突破，往往以脑力劳动的机械化来体现。王浩和吴文俊是在人工智能领域做出突出贡献的中国人。2.2.8 定理证明器竞赛和著名定理证明器定理证明器竞赛和著名定理证明器 自动定理证明领域的权威国际会议有 CADE 和 IJCAR，它们均是每两年召开一次，交替召开。美国迈阿密大学的 Geoff Sutcliffe 每年都在 CADE 或 IJCAR 上组织机器定理证明大赛 CASC(CADE ATP System Competition)，主要面向命题逻辑和一阶逻辑证明器。Sutcliffe还维护一个 TPTP(Thousands of Problems fo

129、r Theorem Provers)网站，是 CASC 的比赛题库，也是公认的检验一阶逻辑证明器性能的benchmark。在 2000 年以前的比赛中，Otter 是多个组别的冠军，2005年后英国曼彻斯特大学的Vampire后来居上，至今一直维持领先状况。定理证明程序可用于软硬件验证，例如 Vampire 曾被微软公司用来进行软件系统验证。美国阿贡国家实验室的 William McCune 在上世纪九十年代使用C 语言实现了 Otter 定理证明器，Otter 实现了当时定理证明里最先进中国人工智能系列白皮书 52 的所有技术，在 CASC 比赛中获得多个组别的冠军。例如，归结原理中的删除策

130、略要求删除被包含的子句，包含测试时定理证明器中最耗时的部分。McCune 最早把项索引引入定理证明器。Otter 主要用到两种项索引，一种是路径索引，另一种是 McCune 提出的差别树索引(discrimination tree indexing)，这项技术极大地提高了定理证明器的效率104 。McCune 利用 Otter 的模块开发了专门用于等词推理的证明器EQP。1996 年 10 月，McCune 使用 EQP 证明了罗宾斯猜想95 。这是数学家罗宾斯(Herbert Robbins)1933 年提出的一个关于布尔代数的猜想，60 多年来从未被证明。EQP 在一台 486 机器上运行

131、 13 天给出证明，之后又在一台 IBM RS/6000 工作站上运行 7 天进行验证。阿贡国家实验室的定理证明小组在 2006 年被撤销，被认为是符号派低潮的标志性事件。2.3 约束可满足性求解“Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming:the user states the problem,the computer solves it.”这是美国艺术与科学学院院士、AAAI Fel

132、low、约束程序（Constraint Programming，CP）研究领域的开创者和奠基人、著名人工智能学学者、爱尔兰考克大学 Eugene Freuder 教授 1997 年为我们描绘的约束程序未来发展愿景105 。这也毫无疑问是人工智能，乃至计算机科学的最高理想，即：用户表述问题，计算机自动求解。彼时，CP 这个源于计算机图形学 106 107 的问题求解方法刚在人工智能研究领域中占有一席之地，尚不广为人知。进入 21 世纪后，约束程序研究得到空前快速发展，并已逐步成为人工智能的基本支撑方法和技术108 109 。2005 年 3 月，在法国成立了“国际约束程序学会”（Associat

133、ion for Constraint Programming,ACP）110 ，会刊为 International Journal of Constraints，每年定期召中国人工智能系列白皮书 53 开 CP 学术年会。目前，在 IJCAI,AAAI 等权威人工智能国际会议上，与约束程序相关的研究论文数量呈现逐年增长的趋势，越发显示其作为人工智能问题求解方法的重要地位。IJCAI2011、IJCAI2013、AAAI2019 和 IJCAI2020 的程序委员会主席分别是或将是澳大利亚新南威尔士大学的 Toby Walsh 教授和意大利帕多瓦大学的 Francesca Rossi 教授，美国

134、密歇根大学 Pascal Van Hentenryck 教授（与南京大学周志华教授同为联合主席）和法国蒙彼利埃大学的 Christian Bessiere 教授，他们都是蜚声国际专门从事约束程序研究的人工智能学者。约束程序以人工智能领域著名的约束满足问题（Constraint Satisfaction Problems,CSPs）的建模和求解研究108 109 为核心，大量来自汽车、交通、航空、电信、教育等领域中的规划、调度、配置、推荐等问题都适合采用约束满足问题来建模和求解108 109 ，这为约束程序的成功应用提供了天然优越条件。当前，约束程序在工业界取得极大成功。IBM ILOG 优化引

135、擎成已成为 SAP、Oracle 等跨国 IT 巨头 ERP 等软件产品的核心优化技术111 。2014 年 11 月 12 日，欧洲宇航局 10 年前发射的彗星探测器的着陆器“菲莱”成功登陆“丘留莫夫格拉西缅科”彗星，完成人造探测器的首次彗星登陆壮举，在“菲莱”执行此次任务及后续实验过程中起主导作用的软件技术是约束传播和基于约束调度方法等 CP 技术112 113 ，这为人工智能助力人类太空探索历史留下了浓墨重彩的一笔。但是，和通用人工智能当前面临的困境类似114 ：具有通用功能的约束程序的建模和求解方法的进展与我们的期望还有距离。尤其在大数据背景下，特别是 2015 年以来，在以机器学习飞

136、速进步为代表的新人工智能浪潮冲击下，约束程序还面临不少新的挑战。如我们面对的约束满足问题呈现出开放交互、大规模、结构化不显著等多种特征115 ，半结构甚至无明确显式结构的约束满足问题建模问题，怎样中国人工智能系列白皮书 54 利用大数据和机器学习方法改善现有的建模和求解方法？约束程序从建模到求解全过程的自动化和可用性亟待加强，这也是 2017年国务院印发的新一代人工智能发展规划对人工智能发展提出的新要求116 。当前，由 Freuder 教授创立、目前由 OSullivan 教授领导的爱尔兰 Cork 大学 Insight 研究中心是最具影响力的约束程序研究基地，并辐射法国、澳大利亚、美国、英

137、国、和意大利等国研究机构。其中，OSullivan 教授领导的研究组在约束建模和约束组合求解等方面研究独树一帜，蒙彼利埃大学 Bessire 教授等在自适应约束传播和自动约束建模方法的研究最为突出。国内研究主要集中在经典和分布式约束求解方法的研究，对于交互式约束建模与求解方法研究涉及不多，代表工作有：北京航空航天大学许可教授等提出了著名的 RB、RD 模型117 。香港中文大学的李浩文教授主要研究基于对称消除的约束求解方法118 ；国防科技大学王怀民教授、东北大学张斌教授以及中国科技大学陈恩红教授等主要研究分布式约束优化问题的求解算法119 120 121 、中科院软件所张健教授、马菲菲博士对

138、于混合约束满足问题求解方法及应用的研究122 123 。吉林大学研究组组早期在孙吉贵教授领导下，在国内较早开展约束程序研究，在约束求解理论、方法及约束求解系统方面做了很多颇具特色的研究工作124 125 ，研究结果得到 Christian Bessi re教授、李浩文教授等国际知名研究者的肯定。约束建模126 是约束求解的基础，模型选择的好坏将直接影响约束求解效率甚至问题是否可解，这一点已经得到约束程序界的共识127 128 。对于约束程序建模，2000 年，Simonis 曾给出了“30 条金法则”129 ，但是多数并不具有普适性，只有“尽量不用布尔模型”、“尽量少用变量和约束”等简单规则有

139、一定影响。商用和学术方面取得成功的约束建模语言也层出不穷，如 OPL、Essence、MiniZinc 等功中国人工智能系列白皮书 55 能都十分强大，但这些建模语言都有一定的局限性：要求用户对于问题特征和求解算法有一个清晰的了解，即用户应具备相当专业的约束程序知识。在互联网浪潮下，对于计算机系统的交互能力要求日渐提升，自动化同时也是各种人工智能系统的追求的普遍目标，对于交互建模和自动建模的能力需求迫切。基于此，先后在2003年和2007年，Bessi re和 OSullivan 等人开创了基于问答的约束模型获取研究工作130 131 并开发原型系统 CONACQ。2009 年，Shcheko

140、tykhin 等人132 ，提出了基于辩论的建模方法，以减少学习实例数。2010 年，Lallouet 等133 提出基于归纳逻辑程序的约束模型自动获取方法。2016 年，Picard-Cantin 等134 针对序列约束建模问题提出了从正例中学习参数的方法。2016 年，Bessi re 和 OSullivan 人首次提出了归纳约束程序循环理论模型135 ，为机器学习和约束程序融合研究搭建了桥梁，同时也为约束自动模型获取研究指明了方向，但仅限于理论层面和小规模问题实例上，具体实现细节还不十分清晰。近年来，约束求解方法的发展极为迅速108 ，算法组合方法（Algorithms Portfoli

141、os）和自动配置问题成为研究热点136 137 。目前新的研究进展有：2010 年，Balafoutis 和 Stergiou 用统计学习方法对当前流行的变量序启发式做了一个比较系统的实验评估138 。对于值选择启发式，最近的代表性工作有：2005 年，Epstein、Freuder 和Wallace 联合研制了个性哈启发式策学习、挖掘系统139 ，2015 年，Chu 等提出了值选择启发式学习策略140 。同年，Ortiz-Bayliss 等首次提出了初步具备自动选择功能的“超级变量启发式”141 。但目前，在挖掘新的选择启发式策略和各种启发式策略组合应用方面的研究还刚起步，研究空间很大。对

142、于算法级别的组合研究，2012年，Amadini等人对约束求解器级别的组合求解进行了初步的实验评估142 ，取得不错的效果，未来需要结合机器学习方法加强约束求解方法的精确选中国人工智能系列白皮书 56 择和深度融合。自适应约束传播的有影响力的开创性工作是 2009 年 Stergiou 等提出的基于探查和简单学习机制实现的自适应143 。最新进展是2015年，Balafrej 等人提出的参数化自适应约束传播144 ，我们研究组对此亦有贡献。但对于交互式环境的约束满足问题的自动求解研究还刚刚起步，理论基础还不足。除此之外，约束满足问题的结构特征也是影响算法求解效率的重要因素，法国阿尔多瓦大学的

143、Christophe Lecoutre 教授整理建立的 Benchmark 测试问题实例库109 145 ，涵盖各个应用领域的 2000 多个问题实例，是良好的学习和测试数据集。2017 年，Freuder 教授为 ACP 会刊 Constraints 创刊 20 周年专门撰文“Progress towards the Holy Grail”指出114 ：自动约束建模、自动问题求解146 将是约束程序下一步的研究重点。2.4 基于模型的诊断 基于模型诊断（Model-Based Diagnosis,MBD）是为了克服传统基于规则诊断方法的严重缺陷而兴起的智能诊断方法，避免了基于规则诊断方法对被

144、诊断问题进行规则提取及其带来的不完备性问题。MBD 依据被诊断问题的拓扑结构和逻辑行为知识将诊断问题建模为可满足问题（Satisfiability Problem,SAT），随后利用智能推理技术进行完备性诊断求解。MBD 智能诊断方法一经提出，就引起了国际人工智能和故障诊断领域众多专家和学者的赞誉。人工智能领域著名学者 De Kleer 将其称为是故障诊断领域理论和方法上的重大技术性革命147 。著名 MBD 学者 Struss 称基于推理技术的 MBD 方法是 AI 研究发展的试金石和重大挑战148 。著名人工智能学者 Dressler 和Console 在 IJCAI-99 会议上特邀报告

145、中指出：MBD 求解方法和理论的进一步研究，不仅是 AI 基础理论研究的需要，对整个 AI 领域研究的发展起着进一步深化和推动的作用149 。中国人工智能系列白皮书 57 2.4.1 MBD 问题问题 定义 1 诊断问题147 （Diagnosis Problem，DP）：诊断问题可以被定义为一个三元组，在这个三元组中（1）SD（System Description）表示诊断问题的系统描述，用谓词公式的集合表示；（2）Comps（System Components）代表系统中所有组件的集合，用一个有限的常量集表示；（3）Obs（System Observations）代表系统的一个观测，用谓词

146、公式的集合表示。假定所有组件的状态是正常的情况下，当系统的模型描述和观测出现不一致时，我们称存在一个诊断问题。也就是：()|.其中，系统中组件的状态用一元谓词 h(c)表示，当 h(c)的值为 1代表组件 c 是故障的，相反，h(c)为 0 代表组件 c 是正常的。系统描述部分包含系统的行为描述以及系统的连接情况。行为描述是一个描述了组件在正常和异常（故障）状态下的执行功能的情况的公式。系统的连接情况是一个形式为=的公式，其中表示组件的输入，表示组件的输出。下面我们给出诊断的定义。定 义 2 诊 断147 （Diagnosis）：给 定 一 个 诊 断 问 题 G=V,E;,;A,RDP=，一

147、个诊断被定义为一组组件的集合，其中 Comps，当 ()|()|此处，为一组关于组件的赋值，用于表示组件是正常状态还是异常（故障）状态的行为假设，在上述公式中，表示逻辑蕴涵关系的否定，表示矛盾。中国人工智能系列白皮书 58 2.4.2 国内外总体研究现状国内外总体研究现状 国外从事MBD领域研究的知名大学和研究机构主要集中分布在欧美。Princeton University 教授 Sharad Malik 领导的 MBD 研究小组已经成为全世界一流的研究基地；Stanford Research Institute 设有芯片故障调试和诊断研究中心，在研究员 Bruno Dutertre 的带领下

148、此研究小组在全球享有盛誉；University of Lisbon 教授 Joao Marques-Silva 在SAT 和 MBD 方面取得的研究成果国际领先；University of Toronto 教授 Andreas Veneris 领导的研究小组在 MBD 方面得了系列重要科研成果；在 University of Michigan,University of Bremen,Australian National University 和 Graz University of Technology 等著名大学也都设有 MBD 相关的研究小组。随着 SAT 和 MaxSAT 求解技术的

149、飞速发展，MBD 问题主流求解方法也都调用 SAT 和 MaxSAT 求解器。在调用此求解器前需要将MBD 问题的描述形式转换成 SAT 可接受的布尔可满足形式，而在转换时其内部元件间的拓扑和逻辑信息被丢弃150 151 。在 MBD 求解过程中，电路的拓扑和逻辑信息对提高MBD求解效率起着重要作用。国内外学者开始研究结合电路结构和逻辑信息的 MBD优化方法，Zhu 等152 学者给出了利用诊断解中骨架变量信息提高 MBD 求解效率的方法，在 MBD 方法得到部分候选诊断解后，提取当前诊断解集中的所有变量的骨架变量信息，在下次求解前约束传播已有骨架变量对应的赋值，进而在骨架变量对应的缩减空间中

150、进行 MBD 求解，有效缩减了后续求解时的搜索空间。Deorio 等153 学者提出结合电路设计阶段的模式信息对 MBD 进行优化的方法，在设计阶段学习电路设计中通讯模型的模式信息，在硅后诊断时利用提取的模式信息对MBD 候选诊断解空间进行剪枝，进而减小了 MBD 问题的求解空间提高了诊断效率。欧阳丹彤等154 学者给出了结合电路结构特征进行抽象的 MBD 方法，提取电路结构特征并将电路抽象成不同的区域，中国人工智能系列白皮书 59 调用 MaxSAT 求解器对这些区域构成的抽象电路求解得到诊断，将此诊断解扩展以有效地获得抽象电路对应的所有诊断。周慧思等155 提出一种结合结构特征的随机搜索

151、MBD 方法，依据单元传播规则结合问题结构特征逐步将问题中硬单元子句分成两部分，对新的子问题再次利用单元传播得出原问题中的硬单元子句中硬阻塞变量，再结合子句特征翻转相应软阻塞变量，从而提高 MBD 的求解效率。Feldman 等学者156 提出结合 MaxSAT 的诊断求解方法，首先将诊断问题建模成最大可满足问题(maximum satisfiability，MaxSAT)，此方法比基于随机搜索的SAFARI求解方法运行时间更长。Metodi 等学者157 从编译建模角度提出考虑电路的统治关系的 SATbD 诊断方法，此方法依据统治关系有效缩减求解空间，进而高效地找出所有极小势诊断。2015

152、年，Ignatiev 等学者158 提出一种面向统治者编码(dominator oriented encoding，DOE)的诊断问题建模方法，通过寻找过滤掉一些节点和一些边的方法将 MBD 编码为 MaxSAT，进而有效缩减建模后诊断问题的规模。此种建模编码方法利用了系统的结构信息，有效地缩减了 MBD 问题建模后子句集的规模。欧阳丹彤等学者159 从拓扑结构出发以第一组观测的系统输入为基础，分析其他观测与第一个观测之间的差异，提出多观测压缩模型对所选系统变量的约束进行编码，多观测压缩模型还可以用于计算极小势的聚合诊断或极小子集的聚合诊断。此外，还从逻辑关系角度出发提出基于支配的多观测压缩模

153、型，在压缩模型中使用支配门的概念来计算压缩模型的顶层诊断，此模型更适用于计算极小势的聚合诊断。2.5 神经符号系统 2.5.1 神经符神经符号号系统的背景系统的背景 智能系统往往需要兼具感知与认知能力。近年来，神经系统实现了感知智能且具有高效的学习能力，但推理能力差。符号系统实现了认知智能且具有强推理能力，但学习效率差。目前，越来越多的国内中国人工智能系列白皮书 60 外学者开始尝试结合神经系统与符号系统两者的优点，开发兼具高效学习能力与强推理能力的模型，该类模型被称为神经符号系统（neural-symbolic system）。神经符号系统利用神经网络快速的计算能力和符号强大的表达能力，能够

154、在不同领域的任务上有效学习与推理，实现模型的感知与认知。解决现实世界很多领域中的问题都需要智能感知与认知，如医学领域中的医疗诊断和自动驾驶领域中的智能决策等。图灵奖获得者约书亚本吉奥(Yoshua Bengio)在 NeuIPS 2019 的特邀报告中明确提到：“深度学习需要从系统 1(system 1)到系统 2(system 2)转化，其中，系统 1 表示直觉的、快速的、无意识的、非语言的、习惯的系统；系统2 表示慢的、有逻辑的、有序的、有意识的、可用语言表达以及可推理的系统。”该观点表明了人工智能的一个重要发展方向。如图所示，纵观人工智能的发展史，从上世纪 50 年代到 90 年代，符号

155、主义比较盛行，逻辑推理和知识工程成为了人工智能的主流技术。之后，联结主义比较盛行，机器学习是人工智能的主流技术，研究者们不再过多关注逻辑推理。从图中也可以看出，人工智能的整个发展主要包含两大主义：符号主义（符号系统）与联结主义（神经系统）。符号主义研究演绎、逻辑推理以及为特定模型求解的搜索算法，如专家系统（通过规则与决策树从输入数据中推导出结论）、约束求解器（在一些给定的可能性中求解）与规划系统（从一些初始状态值中找到一系列动作实现给定目标）等。联结主义研究归纳、学习以及可以从数据中自动捕获信息的神经网络，如卷积神经网络（擅长处理有关图像问题）与长短期记忆网络（擅长处理有关时间序列的问题）等。

156、中国人工智能系列白皮书 61 图图 2-1 人工智能发展简史人工智能发展简史 基于以上分析，表表 2-2分别列出了神经系统和符号系统的优缺点。通过对两者优缺点的总结及对比，我们可以发现：符号系统与神经系统的优缺点具有互补性。符号系统善于利用知识，神经系统善于利用数据，而人在做决策时需要知识与数据并存。根据符号系统与神经系统优缺点的互补性，以及人作决策时所需的条件，将两者结合是未来人工智能发展的主要趋势。表表 2-2 神经系统及符号系统优缺点神经系统及符号系统优缺点 系统系统 优点优点 缺点缺点 符号系统（擅长演绎推理）泛化能力强 具有可解释性 知识驱动 不擅长处理非结构化数据 鲁棒性差 推理速

157、度慢 神经系统（擅长归纳学习）擅长处理非结构化数据 鲁棒性强 学习速度快 泛化能力弱 不具有可解释性 需要大量标注数据 2.5.2 神经符神经符号号系统研究现状系统研究现状 神经符号系统研究的相关工作归结为三大类：神经辅助符号(learning for reasoning)，符号辅助神经(reasoning for learning)和神经-符号(learning-reasoning)。第一类方法以符号系统为主,神经系统为辅。它的目的是利用神经网络的计算速度快的优势去辅助用符号系统去搜索解，使得推理更加高效160 161 162 163 164 165 166 。例如在中国人工智能系列白皮书

158、62 基于统计关系学习(Statistical Relational Learning,简称 SRL)167 的方法中用神经网络来近似搜索算法，实现模型的高效推理。第二类以神经系统为主，符号系统为辅。它的目的是整合符号系统（符号知识包括逻辑规则和知识图谱）的优势到神经系统学习的过程中，提升神经系统的学习性能168 169 170 171 172 。如正则化(Regularization)方法将符号作为神经网络的约束项，指导模型的学习。第三类方法，神经系统与符号系统以平等的方式参与到模型中，两者以一种互利共存的方式充分发挥其优势173 174 175 176 。神经辅助符号。Qu 和 Zhang

159、 等人分别提出了概率逻辑神经网络(probabilistic Logic Neural Network,简 称pLogicNet)177 和ExpressGNN178 。这两个模型的主要思想都是将知识图谱中的推理问题（三元组补全问题）建模为概率图中隐变量的推理问题，都采用变分 EM 方法和神经网络相结合的思路进行近似推理。以上方法手工设计概率图模型的势函数，但仅利用专家构建的规则不能完全捕获隐含在数据中的知识，为此研究者们开始探索从数据中自动捕获规则的方法。Marra 等人179 180 扩展了马尔可夫逻辑网（Markov logic network,简称 MLN）的学习模型，设计了一个通用的

160、神经网络从原始数据中自动学习规则和 MLN 的势函数。除了基于 MLN 自动学习规则的方法以外，一些学者在传统 ILP 方法的基础上，结合神经网络与逻辑提出了可微的 ILP 161 181 182 183 184 。Yang 等人185 提出了神经逻辑归纳学习方法(Neural Logic Inductive Learning,简称NLIL)，可以推理复杂的规则信息（如树型规则和合取式规则等），通过学习到的 FOL 解释隐含在数据中的模式，应用于目标检测任务。符号辅助神经。Diligenti 与 Xu 等人186 187 分别提出语义正则化(SBR)和语义损失(SL)方法，将逻辑知识作为假设空

161、间的约束，如果违背了相应的逻辑规范或逻辑理论，模型将受到惩罚。SBR 是一种从约束中学习的方法,该方法融合了经典机器学习（具有连续特征表中国人工智能系列白皮书 63 示学习能力）和统计关系学习（具有高级语义知识推理能力），以解决多任务优化和分类等问题。SL 方法将命题逻辑的自动推理技术与现有的深度学习架构相结合，将神经网络的输出喂给损失函数，作为可学习神经网络的约束，通过训练算法将命题逻辑编码为损失函数的一部分，提高神经网络学习能力。该方法使用目标原子的边缘概率定义正则项，并用算术电路评估模型的有效性。Hu 等人188 提出了一个通用框架，称为利用逻辑规则辅助深度学习的方法(Harnessin

162、g Deep Neural Networks with Logic Rules，简称 HDNN)。其中，神经网络模型包括 CNN 和 DNN 等。该方法借助知识蒸馏的思想，通过一个大规模且已训练好的网络去引导小规模网络的学习，设计了教师网络和学生网络。教师网络能够学习标签数据和逻辑规则（无标签数据）中的信息，学生网络近似教师网络，使逻辑规则编码的结构化信息可以约束学生网络的学习。Xie 等人189 将命题逻辑融入到关系检测模型中，提出了具有语义正则化的逻辑嵌入网络(Logic Embedding Network with Semantic Regularization，简称 LENSR)，以提

163、升深度模型的关系检测能力。Luo 等人190 提出基于上下文的零次学习方法(Context-Aware Zero-Shot Recognition，简称 CA-ZSL)，解决零次目标检测问题。它基于深度学习和条件随机场建立模型，利用类别之间的语义关系图谱辅助识别未知类别的目标。Li 等人191 提出了大规模的小样本学习方法(Large-scale few shot learning，简称 LSFSL)，解决小样本图像识别任务。Chen 等人192 发现迁移类间的相关性信息可以帮助学习新概念，采用知识图谱建模已知类与未知类之间的相关性，结合神经网络提出了知识图谱迁移网络模型(Knowledge

164、Graph Transfer Network，简称 KGTN)，解决小样本分类问题。神经-符号。Robin 等人160 基于 ProbLog 提出了将概率、逻辑与深度学习有机结合的模型深度概率逻辑(Deep probabilistic logic，简称 DeepProbLog)。该模型首次提出了将神经网络与概率逻辑以某种中国人工智能系列白皮书 64 方式结合的通用框架，它兼具两者的优点，有更强的表达能力，并且可以基于样本进行端到端的训练。DeepProbLog 是一种概率程序设计语言，以“神经”谓词(neural predicates)的方式与深度学习结合，也就是输入谓词中的实体对（该文中的数

165、据都是二元谓词）。神经网络的分类器预测实体对属于所有谓词的概率，然后将预测的结果用于概率程序的推理。不同于 DeepProbLog，Zhou 等人193 基于反绎推理提出了反绎学习（abductive learning，简称 ABL）。ABL 利用机器学习的归纳和逻辑程序的反绎，将两者结合到一个统一的框架中，进行端到端的学习。该方法用逻辑程序语言表示一阶谓词逻辑知识并且建模复杂的推理任务。其中，逻辑程序语言中的部分事实由机器学习提供。基于 ABL 的思想，Tian 等人194 提出了一个弱监督的神经符号学习模型（WS-NeSyL）去解决具有逻辑推理的感知任务。该方法将机器学习部分设计为一个编码

166、器-解码器框架，其中包含一个编码器和两个解码器。编码器将输入信息映射为一个向量后，感知解码器会将向量解码为伪标签，认知解码器会基于伪标签采样出来的逻辑规则进行推理。整个过程是一个端到端的迭代优化，直到模型收敛。吉林大学杨博团队195 提出了一个双层概率图推理框架（BPGR），该框架利用统计关系将神经网络和符号推理整合起来。其中，概率图模型的上层节点是神经网络的预测结果，下层节点是逻辑规则中的闭原子。整个模型进行端到端的迭代训练，直到神经网络的预测结果不再变化。BPGR 用神经网络提升了概率推断的效率，用符号推理提升了神经网络的预测性能。2.5.3 神经神经符号符号系统的挑战及未来研究方向系统的

167、挑战及未来研究方向 前文详细介绍了神经符号系统的研究现状，在此基础上,本节尝试分析目前的神经符号系统面临的主要挑战，以及未来的研究方向。1.推断方法 从概率图的角度建模神经符号系统时，计算阶段依然存在推理困中国人工智能系列白皮书 65 难的问题。例如，基于 MLN 模型，如果逻辑规则数量多且实体规模较大，那么实例化的数量将呈“指数级”增长，导致模型推理的速度迅速下降。例如，实体的数量是 n，一个 m 元谓词实例化，需要 nm种方式。针对该问题，尽管已经提出了一些改进方法196 197 ，但其仍然存在局限性，例如常用的近似推断是以减少数据的使用率和牺牲推理准确性为代价提高推理速度的。因此，结合深

168、度学习模型的特征，为 MLN 等统计关系学习模型设计规则实例化的选取方法及快速推理算法是神经符号系统亟需解决的一个问题。2.规则自动构建 上述神经符号系统模型使用的规则通常都是领域专家人工构建好的，这种构建方式费时费力且不具有可扩展性。如何从数据中端到端的学习出刻画先验知识的规则,也是神经符号系统面临的一个挑战问题。目前，人们探索并扩展基于 ILP 的方法解决规则的自动构建问题，但该类方法存在推理过程复杂且发现的规则比较简单（只能发现单链式规则）等问题。为此，端到端的规则自动构建也是神经符号系统未来需要关注的方向。3.符号表示学习 好的符号表示能够使看似复杂的学习任务变得更加容易和高效。例如，

169、在零次图像分类任务中，引入符号知识对提升模型的分类能力至关重要，如果学得的符号表示包含较少所需的语义信息，那么分类模型将不胜任复杂的分类任务。目前，多数符号表示方法都不能很好地处理具有强相似性的谓词（语义相似但字面意思不同）。若两个谓词语义相似，但逻辑公式形式不同，当前的符号表示学习方法就不能捕获到一致的语义，从而损害了模型的推理能力。因此，如何设计更加鲁棒和高效的符号表示学习方法是神经符号系统面临的一个重要挑战。随着图表示学习的发展，将节点映射为低维、稠密、连续的向量，可以灵活的嵌入到各类学习和推理任务。很多符号知识都可以建中国人工智能系列白皮书 66 模为异质、多关系、甚至多模态的有向图或

170、无向图，如何发展和利用异质图表示学习方法解决神经符号系统面临的挑战也是一个值得探索的方向。4.应用领域扩展 目前，神经符号系统主要应用于计算机视觉与自然语言处理领域，并取得了不错的效果。此外，一些工作还探索了如何利用神经符号系统解决推荐系统的可解释性问题198 和网络节点的分类问题199 200 。因此，一个很自然的想法是，神经符号系统还能有效解决哪些领域的问题，如何针对共性和特点（特殊性）设计相应的模型和方法。中国人工智能系列白皮书 67 第 3 章 大数据算法与可信计算理论 一直以来，算法都是推动人工智能发展的重要力量，而各类计算范式与计算模型则奠定了人工智能技术进步的基础。在算法层面，超

171、大规模的数据处理算法一直是人工智能发展的必要条件；最近两年，大模型的训练也成为算法研究的热点之一。在计算范式方面，随着人工智能技术的普及，新的计算需求不断涌现，其中可信性（如鲁棒性、公平性等）是近期新计算范式研究的核心关注点。算法的理论发展一直推动着人工智能的前进。从早期的线性规划算法到近年来的凸规划与非凸规划算法，从机器学习早期的自适应提升算法到神经网络训练算法，一系列经典算法为人工智能的发展做出了巨大贡献。仅就大数据算法的发展而言，美国自然基金委就推出了多个大规模的长期计划来资助大数据处理、分析以及应用算法的研究，并专门设立了人工智能优化算法的研究中心。然而，随着人工智能问题的不断涌现，针

172、对不同计算资源受限场景的算法设计与分析的需求也在不断扩张。推动各类算法理论的发展同样是保证人工智能稳定进步的重要基础。人工智能技术的应用普及也急需新的计算范式来满足可信的需求。作为人工智能的理论保障，算法的鲁棒性是其广泛应用的基础。同时，许多场景在鲁棒性的基础上，更进一步要求对人工智能的计算具有公平性。近年来，越来越多的场景对保护用户数据的隐私提出了更高的要求。早在 2012 年，美国自然基金委就资助哈佛大学五百万美金用于新型安全可信的计算范式研究；而在 2022 年，美国自然基金委也启动了安全与可信计算项目的新一轮资助计划。在理论层面保障人工智能的可信成为下一阶段理论研究的重要课题。3.1

173、大数据算法计算模型 在计算资源受限的场景，针对不同的计算资源（如时间、空间、中国人工智能系列白皮书 68 通信等），我们可以考虑相应的计算模型。在这些计算模型设计提出的各类算法可以帮助我们更好地理解和优化实际应用中使用的算法效率和性能。以下是几个典型的、具有一定理论基础的模型的简单介绍，这些模型可以用于图、矩阵、分布、几何等各种场景中。3.1.1 亚线性时间算法亚线性时间算法 随着许多应用中数据规模的指数级增长（例如社交网络、基因组学和互联网规模的数据），传统的多项式时间（甚至线性时间）算法由于其不断增加的计算需求而变得不切实际。在面对如此庞大的数据量时，我们迫切需要运行时间比输入大小都要小很

174、多的算法，这种算法被称之为亚线性时间算法。亚线性时间算法的基本思想是利用随机抽样的方法，观测输入对象（如大图）的局部信息，通过这些信息来近似地推断整个输入的全局性质或估计其参数。这种方法为我们提供了一种高效处理大规模数据集的新途径，使得即使是海量数据，也能在可接受的时间内进行有效处理。在过去的二十几年里，以性质检测为代表的亚线性时间算法一直是理论计算机科学领域的研究热点。性质检测主要关注如何高效且近似地测试给定对象（如图或函数）是否满足某种性质或远离满足该性质。它的主要目标是通过少量的查询，而不是对整个对象进行详尽分析，来确定对象是否具有特定性质。性质检测在计算几何、图论和机器学习等各个领域都

175、有广泛应用。它可以高效验证大型数据集或复杂结构的性质，并对现实世界中的算法设计和数据分析产生重要影响。性质检测的研究带来重要的算法技术，并加深了对各种问题计算复杂性的理解。图性质检测是用于快速判定一个图是否满足某个性质（如连通性、二部性、3-可着色性、平面性等）的亚线性时间算法。我们也可以对图中不同的重要参数进行快速估计，设计近似最小生成树权重、边数、最大匹配数、子图个数等参数的亚线性时间算法。更进一步，当输出中国人工智能系列白皮书 69 结构很大时（如图的最大匹配），我们可以设计相应的局部计算算法，允许用户“探测”大输出中的局部位置信息（如查询某条边是否属于最大匹配）；对于每次“探测”，算法

176、对输入图做尽可能少的查询。3.1.2 亚线性空间算法亚线性空间算法 以数据流算法为代表的亚线性空间算法也是处理大规模数据的有效手段。在这个场景里，输入以一个包含元素更新的序列形式呈现：对于图数据流，这些元素对应于图中的边；对于几何数据流，这些元素可能是欧氏空间中的点；对于数据串数据，元素可能对于于某个整数。我们的目标是使用尽可能少的空间来分析数据。由于存储空间有限，我们希望在扫描一次（或少量几次）输入流之后，可以较为准确的推断大数据的性质或结构。数据流算法的代表性工作之一曾在2005年获得了理论计算机科学领域著名的哥德尔奖。流算法能大幅度降低服务器的运算开销，被谷歌,网飞等公司广泛运用于数据的

177、分析与处理中。此外，流算法无需存储数据的特点也能有效保护用户数据的隐私。在数据流算法中，有许多经典问题，其中包括向量的频率矩和信息熵等。为了解决这些问题，学者们提出了一系列抽样和勾勒等算法框架。典型的抽样方法包括重要性采样、拒绝采样、重采样等。勾勒技术在大数据处理和实时分析中扮演着重要角色，它允许使用较少的内存和计算资源在数据流中获得近似的答案，同时支持回答一些有趣的查询。由于数据处理过程中持续不断地有数据到达，无法将全部数据存储在内存中，因此通过使用勾勒技术，我们可以在有限的内存和计算资源下对数据进行摘要和近似处理，从而实现高效的数据分析和查询。此外，勾勒技术在优化、联邦学习等领域也发挥着重

178、要作用。在优化问题中，勾勒技术可以加速动态数据结构的更新，从而提高优化算法的效率；在联邦学习中，勾勒技术可以帮助保护隐私并减少通信开销，同时仍然能够进行有意义的模型聚合和更新。中国人工智能系列白皮书 70 在图数据算法方面，当网络规模过大而无法完全容纳在计算机的主内存中，并且边以数据流的形式出现时，我们希望能够对网络结构进行近似分析。特别是在网络相对密集的情况下，半流算法提供了一种重要的空间高效（相对于输入大小）的处理方式。对于图中的最大匹配等问题，设计高近似比的半流算法仍然是当前研究的热点问题。3.1.3 动态图算法动态图算法 动态图算法是数据结构中的一个重要分支。它是一种支持边的插入、删除

179、，并能够回答与所考虑问题相关的特定查询的数据结构。其目标是尽可能快速地支持查询和更新操作，通常比从头开始重新计算要快得多。在动态图算法的研究中，当前的热点问题包括如何设计更加鲁棒的算法以适应不断变化的输入，以及如何保证在每次更新或查询时算法的时间复杂度尽可能小（即最坏情况下的时间复杂度）。为了解决这些问题，通用的算法设计技巧被广泛应用于动态图算法的设计中，其中最常见的是图分解。图分解包括扩张图分解和低直径分解两种类型。扩张图分解指将一个图分解成若干个扩张图，保证每个扩张图内部联系紧密且连通性良好，同时扩张图之间的边数较少。而低直径分解则指将一个图分解成若干直径较小的子图，保证这些子图之间的边数

180、较少。这些算法设计技巧为动态图算法的高效实现提供了重要支持。3.1.4 大规模并行计算大规模并行计算 大规模并行计算模型是对现实世界中并行计算系统框架进行数学抽象的一种方式，这些系统包括 MapReduce、Hadoop、Spark 和Dryad 等。这个模型处理的是如下场景：由于图的规模太大，我们将图的边任意地存储在若干个机器上。每个机器存储图的部分数据，且这些机器的总空间几乎是整个图大小的线性函数。计算在同步轮次中进行。在每一轮中，每台机器本地对存储在本地的数据执行一些计算，然后与其他机器交换消息。这个过程可以被抽象为通信模型，其中每中国人工智能系列白皮书 71 台机器在每一轮中创建消息包

181、，并将其加载到路由网络中。每台机器的空间大小也隐含地反映了大规模并行计算模型中的通信瓶颈。局部计算通常在线性或近线性时间内运行，在大规模并行计算算法的分析中通常被忽略，因为通信是瓶颈。大规模并行计算模型中算法设计的目标是使用尽可能少的通信轮次来尽可能准确地对数据进行分析。3.1.5 数据降维数据降维 大数据处理中的另一个焦点问题是数据的降维算法，用来减少高维数据的运算代价。自经典的 Johnson-Lindenstrauss 引理和压缩感知算法诞生以来，数据降维算法得到了大量的发展。压缩、蒸馏、核心集等算法的进步也推动了业界对高维数据处理技术的发展。很多流处理与数据降维的理论算法依赖于随机高斯

182、变量的独特性质，而后者在实际中很难被实现。由于上述各类算法的高效性，它们在实际应用中具有极大的吸引力。大数据算法领域成为当前计算机科学中的热门研究方向之一，备受国际知名学术单位（如麻省理工学院、斯坦福大学等）和信息技术产业界知名研究机构（如谷歌、微软等）的重点发展。在当前大数据时代，亚线性算法、动态算法及降维等方法的进展为处理庞大数据量的实际问题提供了有力支持，同时也为计算机科学领域的创新和进步带来了新的可能性。然而，当前大数据的理论算法研究与实际应用之间仍然存在相当大的距离。因此，填补当前理论算法研究与实际应用的空白是大数据处理的关键。3.2 满足可信需求的算法 随着人工智能、机器学习在实际

183、场景中的广泛应用，其鲁棒性、公平性、隐私保护等可信性需求一直是一个主要挑战。下面我们针对这几种需求分别给出简单介绍。3.2.1 鲁棒性鲁棒性 机器学习的鲁棒性问题一直是其实际应用的主要挑战。与此同时，中国人工智能系列白皮书 72 我们迫切需要利用机器学习技术来改进传统仅针对最坏情况性能设计的算法。最近，一种带有预测的算法设计框架被提出。该框架利用机器学习所提供的额外信息，以实现鲁棒性需求。在这个新框架中，算法可以访问通过机器学习技术得到的不可信的预测器，并且需要在预先不了解预测器具体性能的情况下，同时实现有效利用预测器提供的信息和具备最坏情况性能保证（即鲁棒性）。实现这一目标需要考虑以下几个关

184、键环节：针对具体问题，利用机器学习方法从历史数据中得到对未来数据本身或最优解的预测器。针对研究问题，综合考虑预测器的特点，设计一种对预测器误差的衡量方法。根据误差衡量和预测器所提供的信息，对已有具备最坏情况保证的算法进行改造，以在不牺牲最坏情况保证的前提下，充分利用预测器的信息。这一步是整个框架的重点和技术难点，需要综合具体问题、算法、预测器以及误差衡量的结构和性质来进行设计，因此需要具体问题具体分析。通过有机地结合这些步骤，我们可以获得一种新的高效鲁棒算法，该算法可以有效地利用机器学习预测，同时保证鲁棒性。这一创新性框架为克服机器学习应用中的鲁棒性难题，并提高传统算法的性能，带来了新的可能性

185、。这一框架一经提出，便受到广泛认可和应用，在短短 3 年多时间内，已经受到了国际上诸多知名学者的关注。相比之下，国内在这一领域的研究处于相对起步阶段。然而，这个方向与传统算法研究有很多交叉点，与工业界的需求紧密结合，并正在成为国际上的研究热点和国内新兴方向，具有广阔的研究前景。目前带预测的算法框架主要被用于研究在线问题，但它也可被用于提高非在线问题的算法性能，例如算法的运行时间或近似比。传统的“超越最坏情况分析”为了提升近似算法的性能，往往考虑的是一些特殊的图或平均情形的图。然而，带有预测的算法在最坏情况下，如果加上合适的预测，可以改进算法的近似比。中国人工智能系列白皮书 73 3.2.2 公

186、平公正公平公正 为了解决偏见、歧视等问题，我们可以设计满足公平性约束的算法来寻求解决方案。在这个领域，一些研究的热点问题包括：根据不同的公平性指标度量，设计快速准确的算法来检测数据和模型的公平性；利用带可信约束的优化方法以及加入公平性正则化等技术，设计机器学习算法和模型，以最小化数据中的固有歧视和偏见，从而实现对个体和群体的公平保障。在公平性算法设计方面，一个重要的研究难点是如何使用恰当的公平性指标来量化算法在分析数据时产生的歧视或偏见。目前，如何高效地检测算法的公平性，以及如何引入合适的约束优化问题并以此设计公平性算法，都是尚待解决的研究问题。3.2.3 隐私保护隐私保护 为解决当前数据隐私

187、泄露、滥用和大规模数据带来的计算挑战等问题，需要实现隐私损失与估计精度权衡更优的隐私保护算法，即保证个体用户信息不泄露的同时，尽量避免数据的重要统计信息和模式发生较大偏离。以差分隐私为代表的隐私保护算法是目前国内外学术界与工业界的研究热点。哈佛大学、麻省理工学院等知名高校及苹果、谷歌、阿里巴巴等 IT 公司在理论研究与落地应用中已经取得了显著成果。然而，大部分差分隐私及公平性算法在计算性能上的保证相对较弱。具体来说，由于许多数据规模宏大，传统的多项式时间算法（甚至是线性时间算法）已经不再适用；在有些应用中，数据以流的形式动态出现，给高效分析其性质和结构带来挑战。而现有的差分隐私与公平性算法大多

188、集中在多项式时间算法或静态数据上，这极大限制了这类可信算法的适用范围。另一方面，尽管已有研究发现差分隐私算法与自适应数据分析、鲁棒性算法之间有一定的关联，但对于这种关联性的理解还很初步。例如，我们仍不清楚在什么条件下可以使用差分隐私的算法来设计对抗性鲁棒的数据流算法。总体来说总体来说，算法的发展与计算范式的进步对于人工智能技术的发中国人工智能系列白皮书 74 展至关重要。亚线性（时间或空间）算法、动态图算法、大规模并行计算等计算模型为高效处理大规模数据提供了新的途径。同时，可信与安全性成为新的计算范式中备受关注的核心问题，鲁棒性、公平性和隐私保护是当前研究的热点方向。填补算法研究与实际应用之间

189、的距离，加强学术界与工业界的合作与交流，培养更多的专业人才，将为人工智能技术的发展和应用带来新的突破。中国人工智能系列白皮书 75 第 4 章 难解问题的智能算法 在计算机科学领域，难解问题代表一类解空间庞大且解空间搜索规模往往会随着问题规模增大而呈指数级增长的组合优化问题。由于此类问题本身的难解性，极大的增加了这类问题求解的难度。难解问题普遍存在于实际应用的诸多领域中，包括物流和供应链管理、航空运输、生产调度等。人们提出了求解难解问题的一系列求解算法，如启发式算法、精确算法、近似算法、随机算法等，并提出了诸多求解难解问题的算法设计与分析技术，推动了理论计算机及其相关领域的发展。随着大数据和人

190、工智能领域的发展，难解问题普遍存在于人工智能的各种应用中，研究难解问题的求解可以提升人工智能系统的性能和效率。因此，研究难解问题的求解方法，对于深化人工智能的理论基础，提升人工智能的应用效果，推动人工智能技术的进步，具有重大的实际价值和意义。尽管难解问题可以通过精确算法、近似算法和随机算法等方法进行求解，但各类方法在求解难解问题的过程中仍然存在一定的局限性。精确算法面临的主要挑战是计算复杂性。对于难解问题，精确算法在最坏的情况下往往需要指数时间才能找到精确解，这使得精确算法无法在实际可行的时间对大规模难解问题进行求解。近似算法的挑战主要来自于解的质量和理论保证的设计。首先，如何设计出能在多项式

191、时间内给出高质量近似解的算法是一个重要的问题。这往往需要对问题本身有深刻的理解和精巧的算法设计。随机算法的挑战主要来自于概率性和随机性。由于随机算法的解是基于概率的，因此不能保证每次运行都能得到同样的结果，也不能保证总是得到高质量的解。此外，随机算法的分析和设计往往需要使用复杂的概率论和统计学知识，这增加了随机算法的理解和实现的难度。难解问题的高效求解是一个充满挑战的任务。每个难解问题都可能具有独特的特征、约束和目标函数等，不同问题所采用的求解方法中国人工智能系列白皮书 76 不尽相同。另外，问题实例的多样性增加了算法设计的复杂性和难度。难解问题实例规模的增大也给难解问题的高效求解带来了挑战。

192、当问题的数据量和复杂性增加时，计算资源的需求也随之增加。如何面对大规模难解问题实例保持高效的求解速度是一个具有挑战性的难题。某些难解问题需要在有限的时间内给出最优或次优解。例如，在实时调度问题中，需要在短时间内确定最佳的任务分配方案。因此，高效的求解效率是难解问题求解中的一个重要因素。另外，难解问题的求解还需要考虑如下内容：如何根据优化目标进行参数调优和优化？如何基于有限的资源和时间内设计出高效且可靠的算法？如何选择合适的数据结构实现算法效率的优化？综上所述，如何高效求解难解问题面临着问题实例多样性、问题规模大、求解效率要求高和优化复杂等多个方面的挑战。克服这些挑战需要深入理解问题的特点和约束

193、，灵活应用合适的算法技术，并持续进行优化和改进，以实现对难解问题的高效求解。针对难解问题求解带来的挑战，机器学习方法相较于传统方法具有特定的优势。首先，机器学习算法通过学习和训练的方式，能够为难解问题提供高效求解方法。对于难解问题而言，机器学习算法可以通过学习数据中的模式和规律，并根据这些学习结果给出接近最优解的结果。机器学习算法具备自适应性和泛化能力，能够从大量数据中学习并推广到难解问题新实例中。这种泛化性使得机器学习算法可以适应不同类型和规模的难解问题，并为其提供解决方案。其次，机器学习算法可以借助并行化和分布式技术，增强求解难解问题的效率。通过将任务分解为多个独立子任务，并同时进行计算和

194、处理，机器学习算法能够加速难解问题的求解过程。例如，针对传统经典排序问题，传统方法在对大量数据进行排序时会面临复杂度上升的困扰，而OpenAI 提出的基于机器学习的排序算法1 通过训练模型使其能够学习和理解数据规律，将大数据排序算法的求解速度提升了 70%。这中国人工智能系列白皮书 77 一思想对于处理大规模难解问题尤为重要，因为它消除了计算资源限制和响应时间的压力。机器学习算法还具备结合领域知识和人类专家经验的能力，通过引入领域知识和专家经验，机器学习算法可以针对难解问题提取有意义的特征和规则，从而改善难解问题求解的准确性和效率。难解问题的机器学习求解方法通常包含如下步骤：数据收集和准备、特

195、征提取、模型选择和训练、模型评估和优化、预测决策与问题求解。在数据收集和准备阶段，需要收集足够的难解问题训练数据，并对其进行预处理和清洗，包括去除噪声、处理缺失值和异常值等。这一步骤对于保证模型的训练和泛化能力非常关键，因为高质量的数据能够提供有代表性的样本分布，更有利于问题求解的泛化。特征提取需要从实例中编码并提取相关的特征，包含特征选择、降维和特征转换等，进而可以更好的表征难解问题并捕获与问题相关的关键信息。在模型选择和训练阶段，机器学习方法需要根据难解问题的特性和数据特点选择合适的机器学习算法。常见的算法包括图学习、强化学习等。在模型评估和优化阶段，机器学习方法需要使用独立的测试数据集来

196、评估训练好的模型性能，并通过各种指标（如准确率、精确率、召回率等）来衡量模型的效果。如果模型表现不佳，可以进行参数调整、模型结构修改或者尝试其他改进方法，以进一步提升性能。最后，在预测决策与问题求解阶段，机器学习方法将训练好的模型应用于实际问题的求解中，对新的输入样本进行预测决策与问题求解。在难解问题求解的机器学习方法中，图学习和强化学习是两个重要的分支。其中，图学习方法的核心思想是基于难解问题的图结构关系，利用图结构中的节点和边之间的关系对难解问题进行表征，结合图结构中的拓扑信息和节点特征来理解难解问题，采用图神经网络等技术对图进行分析并对难解问题进行求解。图学习方法在难解问题求解中的应用广

197、泛，其中常用的模型包括图卷积网络、图注意力网络等。中国人工智能系列白皮书 78 此类方法能够充分考虑图实例中节点和边之间的交互，并学习到节点的表示和图级别的特征，帮助理解和推断难解问题的决策和求解。强化学习则通过智能体与环境的交互来求解难解问题。在强化学习中，智能体根据当前的环境选择动作，并观察环境返回的奖励信号，通过迭代的进行试错和学习，智能体能够找到每次迭代的最优策略以最大化累积奖励。在难解问题求解中，可以将问题的求解状态定义为环境，利用强化学习算法来优化决策策略，找到最佳的决策对难解问题进行求解。常用的强化学习算法包括深度 Q 网络、策略梯度等，能够在复杂的难解问题状态空间中找到较好的决

198、策策略。4.1 难解问题图学习方法求解 诸多图问题本身就属于难解问题，例如旅行商问题、最大割问题等。此外，许多其他的难解问题可以通过转化为图问题来进行求解。这种转化通常涉及将问题中的元素映射为图中的节点，并利用图中的边来表示元素之间的关系或约束。例如，布尔可满足性问题可以转化为图的着色问题，线性规划问题可以转化为图的最大流或最小割问题，调度优化问题也可以转化为图着色问题进行求解等等。在图问题的求解过程中，图中的拓扑结构和边的关系对难解问题求解具有较大的影响。例如，在任务调度问题中，图中节点代表任务，边表示任务之间的依赖关系。图的拓扑结构可以用来判断是否存在循环依赖，并帮助确定任务的执行顺序。图

199、结构在求解难解问题中发挥着重要作用，利用图结构求解难解问题可以提供更好的问题表征。由于难解问题通常具有复杂的结构和相互依赖关系，图结构提供了一种有效的方式来表示和分析这些难解问题的底层逻辑和层谱结构。通过将问题建模为图结构，可以利用图中的拓扑信息、节点特征和边关系来理解问题，并设计相应的图学习算法和利用图学习模型来求解难解问题。图学习是机器学习领域的一个重要分支，专注于处理和分析图数据。图数据具有节点和边的关系，能够描述实体之间的复杂交互和依中国人工智能系列白皮书 79 赖关系。图学习的目标是通过学习图数据中的模式、结构和特征，从中提取知识并进行预测。与传统的数据形式（如表格或向量）不同，图数

200、据的处理需要考虑节点之间的连接和依赖关系，以及节点本身的属性特征。图学习算法可以自动发现图中的模式、社区、中心节点和相似性等重要信息，从而对新的节点特征或边特征进行推断。在图层级上，图学习可以用于进行分类或回归任务。在节点层级上，图学习可以用于进行节点属性预测。在边层级上，图学习可以用于进行边属性预测或缺失边预测。在子图层级上，图学习可以用于进行社区检测或子图属性预测。图学习方法已被广泛应用于求解各种难解问题，例如旅行商问题，最大割问题，调度问题等。难解问题图学习方法的求解思路包含问题的图表征、图特征的学习、目标优化函数设计和问题求解几个关键步骤。在问题的图表征阶段，需要建立待求解难解问题与图

201、的关系，将问题中的实体抽象为图的节点，将实体间的抽象关系构建为图的边连接，并为每个节点和边赋予恰当的特征。这个阶段的关键目标是构建一个精准且可以被图学习算法处理的图模型。图特征的学习阶段主要是通过图神经网络或其他相关算法，对图的节点和边的特征进行编码和学习，从而得到一个可以反映图结构和特征的向量。这一步的目标是提取出图的关键特征，从而为后续的优化和求解提供数据支持。在目标优化函数设计阶段，需要设计一个具体的目标优化函数，用以度量当前图的状态和期望的学习目标之间的差距。对于不同的难解问题，这个优化函数可能会有所不同。最后是问题的求解阶段，主要通过学习的模型特征，在满足各种约束条件的情况下，利用模

202、型决策预测找到问题的最优解或近似解。例如，在旅行商问题（Traveling Salesman Problem,TSP）的求解中，其目标是寻找一条可以遍历所有城市并返回原点的最短路径。这个问题的主要挑战在于随着城市数量的增加，可能的路线组合呈指数级增长。图学习可以利用图卷积神经网络，学中国人工智能系列白皮书 80 习旅行商问题中的图结构特性和节点间的关系，挖掘问题的全局结构，并根据当前求解状态对近似最优的路径选择进行预测，大大降低了搜索空间和计算复杂度。对于最大割问题，其目标是在一个给定的无向图中将图中节点分成不同子集，使得子集之间的边权之和最大。图学习方法可以融合最大割问题中的节点与其邻居节点

203、的特征，使得每个节点都能获取其周围邻居的信息。具体的，学习方法经过多层图卷积操作，使得每个节点的特征将会包含更广泛的 k-跳邻域信息。图卷积网络能够捕获到图的深度结构信息，并利用学习的特征进行分割决策，从而实现对最大割问题的求解。难解问题的图学习求解方法主要可以分为两类，一类是基于端到端学习（End To End Learning）的求解方法，另一类是基于决策配置学习（Learn To Configure）的求解方法。基于端到端学习的求解算法是一种完全依赖端到端训练完成问题求解的方法。该方法的核心是通过构建一个端到端的模型，接收输入的问题图表征，经过学习和训练，直接输出问题的最优解或者近似解。

204、这类方法一般采用图神经网络技术，其优点在于可以自动学习到问题的复杂特征和规律，并通过不断的训练，不断优化其学习效果。然而，端到端的方法也存在一定的缺点，即需要大量的实例数据和计算资源来训练、优化模型，并且端到端方法在模型训练的过程中很难进行有效的控制和干预。基于决策配置学习的求解方法主要利用机器学习方法，尤其是图卷积神经网络、图循环神经网络等确定最佳的决策配置选择。此类方法通过反复的试错和学习，不断优化其算法决策的编码特征，最终找出一个近似最优的算法决策配置。基于决策配置学习的求解方法可以帮助确定难解问题求解过程中算法下一步应该探索的方向。具体来说，基于决策配置学习的求解方法首先使用图神经网络

205、提取难解问题实例的图编码特征。然后，基于这些特征，决策配置学习将训练一个模型来预测算法学习特征的重要性。在每一步的决策优化中，决策配置中国人工智能系列白皮书 81 学习求解方法都会根据当前的状态和已经学习到的特征重要性，选择一个算法的近似最优决策。然后，根据这个算法决策的结果，自动调整其决策策略，以便后续做出更好的决策。这种方法的优点在于，在经过一定量的训练后，决策配置学习求解方法可以自动的找到一个有效的重要性特征刻画和算法决策策略，从而在很大程度上减轻了人工干干预和参数调整优化。同时，通过持续的学习和优化，决策配置学习求解方法也能够不断改进其决策策略，以适应不断变化的难解问题环境。图学习方法

206、已被广泛应用于求解各种难解问题，这些问题包括路径规划问题、最大割问题、作业调度问题以及资源分配问题等。下面将以路径规划问题、最大割问题和作业调度问题为例，详细阐述图学习方法求解难解问题的具体方式和策略。4.1.1 路径规划问题路径规划问题 路径规划问题（Routing Problem）是一类受到广泛关注的组合优化问题，旨在满足一定约束的情况下，寻找从源节点到目标节点的最优路径。旅行商问题（Traveling Salesman Problem，TSP）、汽车路由问题（Vehicle Routing Problems，VRP）均为典型的路径规划问题。求解路径规划问题的传统启发式算法往往基于局部搜索

207、技术，求解一个实例往往需要较长的时间，无法满足实际应用场景中的效率要求。基于图学习方法求解路径规划问题，挑战在于图学习方法需要设计和训练模型来处理大量可能的路径组合。另外，路径的顺序影响着求解的质量。因此，在图学习过程中，需要在处理图结构时采用特殊的策略模拟路径的先后顺序选择。路径规划问题需要在全局层面找到问题的解，而不仅仅是在局部找到较好的解决方案。如何寻找问题的全局结构是一个挑战，因为大多数图神经网络都基于邻域信息聚合，可能无法有效的捕捉全局结构信息。路径规划问题的直接求解思路是利用端到端学习方法进行训练中国人工智能系列白皮书 82 求解。为了克服端到端学习方法中的路径规划节点顺序问题，K

208、ool 等人2 提出了一种基于图注意力机制的模型，来学习 TSP 问题节点序列之间的公共模式，并基于训练得到的特征构造路径解。Chen 等人3 提出了一种称为 NeuRewriter 的方法，通过深度图神经网络学习重写当前路径解的局部模块，改进路径选择过程。NeuRewriter 可以分解为 region-picking 和 rule-picking 两个模块，每个模块由 actor-critic 方法分别进行训练，分别负责路径规划中的路径顺序选择和路径重新规划决策。Lu 等人4 提出一种新的学习方法（L2I）。基于一个随机初始解，L2I 从一系列由图编码特征预训练得到的运算符中进行选择，通过

209、选定的最优运算符改进路径顺序。尽管上述路径规划训练方法考虑了节点选择的先后顺序特征，但训练过程缺乏有效的搜索策略，这也导致这些方法在路径规划问题上的求解质量难以保证。为了进一步提高路径规划问题的求解质量，Fu 等人5 考虑首先在子图中训练一个小规模神经网络模型，然后利用图采样、图转换和图合并等技术构建完整图的热力图。基于合成得到的热力图，通过蒙特卡洛树搜索获得高质量路径解。Jin 等人6 提出了一种基于多指针 Transformer 的端到端图深度学习方法（Pointerformer）。通过可逆残差网络和多指针网络，Pointerformer 有效的控制了编码器-解码器架构的内存消耗。同时，P

210、ointerformer 通过引入特征增强和上下文增强方法，可以获取更优的搜索决策，从而提升了路径解的质量。虽然图神经网络算法的计算速度优势明显，但其求解路径规划问题的质量相对于传统启发式搜索方法仍有很大的提升空间。为了结合二者的优势，人们提出利用图神经网络指导传统启发式搜索共同改进路径规划解的质量。Hottung 等人7 基于注意力深度图神经网络，提出了一种新的邻域搜索框架求解车辆路径规划问题，并通过更广泛邻域信息的学习来指导搜索算法的求解过程。Delarue 等人8 设计了基于值函数的深度图卷积网络框架，将搜索过程的动作选择问题建模为中国人工智能系列白皮书 83 混合整数优化问题，并通过启

211、发式搜索算法进行改进。Hottung 等人9 使用了条件变分自编码器，学习如何将潜在搜索空间中的点映射到特定实例的图编码特征中，并通过无约束连续优化方法对所学习的图特征进行导向性搜索。利用图神经网络指导传统启发式搜索的图学习方法在求解速度和求解质量上相较于传统启发式方法有了很大的提升。然而，由于大规模图神经网络具有较高的计算复杂性，大规模路径规划问题实例的搜索空间庞大，这些方法只能够依赖于小规模图神经网对生成实例小样本进行训练。为了提高问题求解泛化能力，人们尝试用 Transformer、多阶段学习等方法进行改进。Li 等人10 提出了在图神经网络中引入一种基于 Transformer 模型的

212、局部搜索框架，利用空间局部性原理从原始指数级解空间中选择线性数量的子问题，最终调用启发式求解器来迭代优化路径解，提高了求解大规模路径规划实例的能力。Choo 等人11 提出在图神经网络中引入模拟引导的束搜索算法，在固定宽度的树搜索中识别候选解，减小了问题的搜索空间，提高了问题求解的泛化能力。Hou 等人12 提出两阶段划分方法，对 VRP 问题子路径序列进行编码。在求解过程中首先根据子路径编码将大实例划分为小实例，通过调用传统启发式算法进行求解，提升了问题的求解效率和求解能力。尽管基于端到端的学习方法可以有效求解路径规划问题，但它需要大量的训练数据生成和计算资源来对模型进行预训练。路径规划问题

213、的另一种求解方法是利用决策配置学习方法进行求解。在决策配置学习方法中，训练模型将学习图实例的抽象特征并直接学习算法决策的重要性，进而获得较好的求解决策。Xin 等人13 设计了一种多解码器注意力模型（MDAM）对路径序列特征进行学习，获得了问题求解的自主决策。Joshi 等人14 使用图卷积网络学习节点与边特征的重要性，随后使用高度并行化的集束搜索（Beam search）算法生成路径中国人工智能系列白皮书 84 解，并在配置学习过程中不断改进启发式算法的决策搜索效率。Kool 等人15 将机器学习算法与动态规划算法的优势相结合，提出了DPDP 方法。具体来说，DPDP 训练一个深度神经网络对

214、实例中的边进行打分，并基于网络打分结果减少动态规划算法决策状态空间，以提高求解速度与求解质量。4.1.2 最大最大割问题割问题 给定一个无向图，最大割问题的目标是将图的节点分成两个不相交的子集，使得两个子集之间边的权重最大。最大割问题的求解过程涉及到对每个节点做二进制决策，这是非连续的。这种非连续性在神经网络中往往难以直接建模。传统的图神经网络主要基于节点和其邻居的局部信息进行推理，可能无法有效捕获整个图的全局信息。在最大割问题的求解过程中，许多端到端图学习方法利用图神经网络学习顶点和其邻居的特征关系，并基于学习到的特征关系给出节点分类预测。Barrett 等人16 提出了一种探索性图神经网络

215、，该方法通过逐步扩大探索域改进解节点分类和最大割问题的求解质量。Khalil 等人17 利用图神经网络学习最大割问题的重复结构，并基于训练得到的网络设计贪心策略逐步构建每个节点的分类决策。直接的端到端图学习方法受解空间复杂性影响，往往难以适应大规模最大割问题实例的求解。为了改进端到端图学习方法的泛化性能，Barrett 等人18 提出 ECORD 学习算法。ECORD 算法在图数据进入递归探索单元前，预先将其在单一神经元进行预处理，提高了求解效率和模型泛化性能。Ireland 等人19 提出了 LeNSE 算法，用于学习基于割集得到的子图特征。LeNSE 算法调用启发式算法求解子问题，最终基于

216、局部解合成全局解，提高了模型求解的效率和泛化能力。为了进一步提高模型求解的质量，研究最大割问题中的全局结构对节点分类的影响是一个重要内容。基于对最大割问题全局结构的刻画，Yao 等人20 引入了一个通用全局结构学习框架，该方法首先利中国人工智能系列白皮书 85 用图神经网络提取问题实例的特征表示，然后应用深度 Q 学习通过全局翻转或交换顶点标签逐步改进解的质量。Zhang 等人21 认为最大割问题中高度结构化的全局约束会阻碍解的优化。在图神经网络中引入 GFlowNets 可以高效的从非标准化概率密度中进行采样，进而削弱组合优化问题中全局约束造成的不利影响。Zhang 等人21 针对最大割等多

217、个组合优化问题，基于条件 GFlowNets 在解空间中进行采样，同时基于长期信度分配问题技术对图神经网络进行训练，提高了模型对全局结构约束的理解能力，提高了最大割问题解的质量与泛化性能。基于决策配置学习的最大割问题求解方法通过利用图学习方法获得算法分类决策的重要性特征，进而指导搜索策略对最大割问题进行求解。Li 等人22 将图深度学习技术与经典启发式算法相结合来求解最大割问题。通过训练图卷积神经网络对图中每个顶点是否属于最优解进行打分，并利用树搜索方法探索解空间提升解的质量。Karalias等人23 提出了一种通过图神经网络学习求解最大割问题的无监督框架。该框架通过优化神经网络实现概率分布的

218、学习，并确定最大割问题的搜所空间映射。该分布可以以一定的概率生成满足问题约束条件的低成本整数解。4.1.3 作业调度问题作业调度问题 作业调度问题（JSSP）是计算机科学和运筹学中广泛研究的组合优化问题，在制造业和交通运输等行业中有着广泛的应用。在 JSSP中，许多具有预定义约束的作业被分配给一组异构机器，该问题的求解目标为最小化完工时间、流动时间或延迟。优先级调度方法（PDR）是在实际中被广泛应用的一种高效启发式算法。PDR 计算快速、直观且易于实现。然而，设计一个有效的 PDR 需要大量的领域知识和试错，特别是对于复杂的调度问题。机器学习可以很好的发掘实例的共同特征，且通过大量实例训练得到

219、的模型表现往往相对稳定。因此，中国人工智能系列白皮书 86 人们越来越关注调度问题的机器学习求解方法。调度问题通常基于端到端的图学习方法进行求解。例如，Wang 等人24 提出了一种基于图深度学习的动态调度方法，采用近端策略优化来寻找调度的最优策略，以应对由于问题规模增加而导致的状态和行动空间维度灾难。Zhang 等人25 通过端到端图深度学习获得调度的公共模式，并应用训练得到的模型来自动学习分配优先级。Zhang等人25 使用离散图表示调度问题，提出了一种基于图神经网络求解调度过程中的状态，有效的提高了泛化性能。然而，上述学习方法没有考虑到作业车间调度问题中决策顺序对整体求解的影响，影响了求

220、解的质量。为了克服决策顺序对问题求解质量的影响，Park 等人26 提出了使用图神经网络来学习作业车间调度问题的框架。将 JSSP 的调度过程建模为一个具有图表示的序列决策问题，随后使用 GNN 来学习节点特征，通过节点特征学习最佳调度。Jeon 等人27 提出了一种基于机器学习的序列调度器，该调度器使用 one-shot 图神经网络编码器对节点序列优先级进行采样，通过列表调度将节点序列优先级转换为最终调度。Park 等人28 提出了一种基于图深度学习的实时调度器 ScheduleNet。具体的，ScheduleNet 首先将多代理调度问题建模为具有连续奖励的 semi-MDP，用智能体（Ag

221、ent）任务图表示调度问题的状态，利用类型感知图注意力提取智能体和任务节点的节点嵌入，最终用计算出的节点嵌入计算调度分配概率。4.1.4 其他难解问题其他难解问题 对于其他难解问题，人们同样基于图学习方法提出了一系列求解方案。下面以可满足性、计算资源分配、装箱、图编辑距离、影响力最大化等问题为例简要概述。对于可满足性问题，人们基于图神经网络加速可满足性问题分支搜索过程，提高了求解准确率29 -36 。对于计算资源分配问题，人们利用图神经网络学习资源分配的公共模式37 41 ，自适应分配计算资源。对于装箱问题，人们基于图神经网络中国人工智能系列白皮书 87 预测不同装箱动作的可行性，并通过树搜索

222、算法进行剪枝42 -45 。对于图编辑距离问题，人们通过注意力机制等学习图节点特征，加速图结构的检索和匹配46 -50 。对于影响力最大化问题，人们通过图神经网络学习影响力公共模式，提高了分支搜索速度51 -55 。4.2 难解问题强化学习求解 强化学习旨在研究智能体（Agent）在与环境（Environment）的交互过程中学习到一种行为策略，以最大化得到的累积奖赏56 。强化学习由两部分和三要素组成，两部分指的是智能体和环境，三要素则为状态（State）/观察值（Observation）、动作（Action）以及奖励（Reward）。在强化学习过程中，智能体与环境一直在交互，智能体在环境中

223、获取某个状态后，它会利用该状态输出一个动作，然后这个动作会在环境中被执行，环境会根据智能体采取的动作，输出下一个状态以及当前这个动作带来的奖励。智能体的目的就是尽可能多的从环境中获取奖励。难解问题的求解过程和强化学习之间存在紧密的关系。诸多难解问题存在许多不确定性，传统的方法难以找到高质量解。强化学习通过与环境的交互学习，能够自主的发现并优化决策策略，以适应问题的动态变化和不确定性。另外，许多难解问题的求解需要在庞大的搜索空间中找到高质量解。强化学习可使用搜索算法（比如，蒙特卡洛树搜索）或价值函数估计来引导搜索过程，实现高效的探索和优化解空间。许多难解问题具有很好的组合优化结构。强化学习可利用

224、问题的组合结构，通过建立合适的状态表示、定义动作空间和奖励函数等实现问题的求解。在求解难解问题时，随着问题规模的增加，解空间变得非常庞大。强化学习为难解问题的求解提出了新的思路，其目标是最大化得到的累积奖赏。在求解难解问题时，强化学习方法可能需要在不同的阶段做出不同的决策，以实现较好解的获取，并考虑长期回报的优化来引中国人工智能系列白皮书 88 导决策过程，使智能体能够在全局上找到更好的求解方案，通过不断的尝试和学习来改进决策策略，并逐步接近最优解。总之，强化学习作为一种强大的学习和决策方法，可以应用于各种难解问题求解。它的学习能力、搜索优化能力和适应性使得它在求解难解问题时具有广泛的应用潜力

225、。近年来，强化学习方法已被成功应用于若干难解问题的求解中，比如混合整数规划、计算资源分配、车辆路径规划等问题。例如，在混合整数规划问题中，强化学习可以结合搜索算法，如分支定界或割平面法，来引导决策过程。通过学习最佳的分支或割平面选择策略，实现加速找到最优整数解的过程。在车辆路径规划问题中，强化学习可用于学习最优的路径选择和车辆调度策略。通过与环境的交互和学习，强化学习可以逐步改进路径规划和调度决策，以最大化服务效率和资源利用。诸多研究结果表明，强化学习模型可成为求解难解问题的一种有效方法57 61 。在难解问题求解中，强化学习方法可以分为有模型（Model-based）和无模型（Model-f

226、ree）两种。有模型方法的智能体尝试通过在环境中不断执行动作来获取样本，并构建对未知环境元素（如奖励函数、状态转移函数）的模型。而无模型方法则不尝试对环境进行建模，而是直接寻找最优策略。根据模型的来源，有模型方法可分为给定模型（Given Model）和学习模型（Learn Model）。无模型方法可分为基于值函数估计的方法（Value-based）、基于策略估计的方法（Policy-based）以及两者结合的 Actor-Critic 方法。4.2.1 基于无模型的强化学习方法基于无模型的强化学习方法 无模型方法在求解难解问题时主要关注于直接寻找最优策略，而不需要对环境进行建模，具体包括基于

227、值函数估计的方法、基于策略估计的方法以及两者结合的 Actor-Critic 方法。基于值函数估计的方法试图在与环境交互的过程中估计出每一中国人工智能系列白皮书 89 状态上每一动作对应的累积奖赏，从而得出最佳策略。典型的基于值函数估计的方法有 Q-learning 方法62 、Deep Q-Networks（DQN）方法63 和时序差分方法64 。近年来，基于值函数估计的方法在难解问题求解中得到了广泛应用。例如，Khalil 等人65 提出了一种结合Q-learning 和图嵌入的框架，用于求解旅行商问题、最小顶点覆盖问题和最大割问题。给定问题实例图 G，该方法将图 G 作为输入，将部分解（

228、图中部分节点的集合）作为状态 S，并将图中不属于当前状态S 的一个节点作为动作 v。在每个时间步，智能体采取动作 v，并根据环境反馈的回报奖励 r 来更新 Q 值表，以估计状态 S 和动作 v 的 Q值。然后，根据 Q 值表选择具有最大收益的动作来进行决策。这种方法的核心思想是通过使用 Q-learning 算法和图嵌入技术，学习并优化状态和动作之间的 Q 值，从而指导求解难解问题的决策过程。Cappart等人66 设计了深度强化学习模型来确定与问题相关的决策图变量顺序，该模型可用于最大独立集问题和最大割问题。Bai 等人67 提出了一种图神经网络和深度Q-learning相结合的检测最大公共

229、子图的方法，该方法使用探索树在两个图中提取相应的子图，并通过 DQN进行训练以优化子图提取奖励。Song 等人68 提出了策略共同训练的元学习框架，该框架可以将强化学习和模仿学习作为子程序，从而改善单视图的学习模式。Barrett 等人69 提出了结合强化学习和深度图网络的探索性组合优化深度 Q 网络，该方法可以使智能体通过训练数据反馈不断改进解决方案。Liao 等人70 提出了一种深度强化学习方法来求解模拟环境中的全局路由问题，该方法使得智能体能够根据所提出的各种问题产生最优路由策略，并利用了深度强化学习的联合优化机制。Scavuzzo 等人71 提出了一种马尔可夫决策过程范式的泛化，为更一

230、般的分支变量选择、强化学习算法和奖励函数提供了基础。Qu 等人72 提出了一种新的基于强化学习的分支定界算法。该方法与离线强化学习类似，最初在演示数据上进行训练，以大规模加速学中国人工智能系列白皮书 90 习。随着训练效果的提高，智能体开始逐渐用学到的策略与环境交互。确定演示数据与自生成数据的混合比例是提升算法性能的关键。Wang 等人73 提出了一种智能的深度强化学习算法来求解计算资源分配问题，该方法在 MEC 架构中引入基于 DQN 的 Software Defined Network（SDN）控制器。在 SDN 控制器中，智能体通过与 MEC 环境的持续交互可以采取行动并获得相应的奖励。

231、He 等人74 开发了一个两阶段的框架来求解复杂调度问题，该方法将强化学习和传统运筹学算法结合在一起来求解调度问题。Jacobs 等人75 提出鲁棒优化来求解路径优化问题，该方法通过精确求解内部最小化问题来获得鲁棒解，并应用强化学习来学习外部问题的启发式方法。相比基于值函数估计的方法，基于策略估计的方法不需要显式的估计每个状态或动作对应的 Q 值，而是直接输出下一步动作的概率，根据概率来选取动作。近年来，策略梯度、PPO 等基于策略估计的方法也逐渐应用于难解问题求解中。Tang 等人76 提出了一种混合整数规划求解器和强化学习相结合的切割平面选择方法，该方法将强化学习智能体作为整数规划算法框架

232、中的子程序，动作则是增加新的切割平面，从而获得良好的收益。Yolcu 等人77 提出了一种图神经网络和强化学习相结合的随机局部搜索方法，该方法通过图神经网络计算变量选择启发式策略，并通过强化学习训练一套专门针对不同类别的启发式求解器，从而较好的求解布尔满足性问题。Ma 等人78 提出了一种图指针网络和分层强化学习相结合的方法来求解旅行商问题，该方法采用分层强化学习框架和 GPN 架构，有效的求解了带时间窗约束的旅行商问题。Nazari 等人79 提出一种使用强化学习求解车辆路径问题的端到端框架，该方法训练了一个单一的策略模型，仅通过观察奖励信号和遵循可行性规则，就能为类似规模的问题实例找到接近

233、最优的解决方案。Deudon 等人80 将神经网络框架扩展到求解旅行商问题，该方法将城市坐标作为输入，使用强化学习训练神经网络，以中国人工智能系列白皮书 91 预测城市排列的分布。Kool 等人81 提出了一个基于注意力层的模型并使用强化学习来训练模型，从而求解旅行商问题。Bello 等人82 提出了一种循环神经网络和强化学习相结合的求解旅行商问题的方法。该方法在给定一组城市坐标的情况下，训练一个循环神经网络，并以负路径长度作为奖励信号，使用策略梯度方法优化循环神经网络的参数，从而预测不同城市排列的分布。Hu 等人83 提出了一种新的三维装箱问题，并将深度强化学习结合求解旅行商问题的方法实现对

234、新型三维装箱问题的求解。Lu 等人84 提出一种迭代搜索的方法求解车辆路径规划问题。该方法在同一时间训练多个强化学习策略，并使用不同的状态输入特征。Sun 等人85 提出了一种搜索进化策略的网络，该网络策略使用强化学习并将变量选择过程建模为马尔可夫决策过程。虽然基于值函数估计的方法和基于策略估计的方法在求解难解问题上获得了较好的效果，然而这些方法均存在明显的不足。基于值函数估计的方法不能直接得到动作值输出，难以扩展到连续动作空间上，并存在高偏差的问题。而基于策略估计函数估计的方法要对大量的轨迹进行采样，而每个轨迹之间的差异可能是巨大的，可能导致高方差和较大梯度噪声问题。为了解决高方差和高偏差之

235、间的矛盾，基于值函数估计的方法和基于策略估计的方法被结合起来形成 Actor-Critic 方法。该方法构造一个全能型的智能体，既能直接输出策略，又能通过价值函数来实时评价当前策略的好坏。Emami 等人86 提出了 Sinkhorn 策略梯度算法（SPG），并为 SPG 算法引入的 Actor-Critic神经网络架构，将状态空间的表示学习与 Sinkhorn 层解耦。Sinkhorn层产生置换矩阵的连续松弛，使 Actor-Critic 架构可以进行端到端的训练。Chen 等人87 提出了一种车辆路径规划的 NeuRewriter 策略。该策略分解为一个区域选择和一个规则选择模块，每个模块

236、都由Actor-Critic 方法训练的神经网络进行参数化。Malazgirt 等人88 提出中国人工智能系列白皮书 92 了一种 TauRieL 方法，该方法受 Actor-Critic 的启发，采用普通前馈网络来获得策略更新向量，并用该向量来改进生成策略的状态转移矩阵。Cappart 等人89 提出一种基于深度强化学习方法来求解约束规划问题，该方法将动态规划作为约束规划和深度强化学习之间的桥梁。Gao 等人90 提出了一种学习局部搜索启发式算法的方法，通过行动者-评论家框架进行训练，迭代改进了车辆路径问题的求解方法。4.2.2 基于有模型的强化学习方法基于有模型的强化学习方法 有模型的强化

237、学习方法使用已知的环境模型或通过学习建立的环境模型来进行规划和决策，根据模型的来源可分为模型给定法（Given Model）和模型学习法（Learn Model）。模型给定方法假设已经拥有一个准确的环境模型，该模型描述了环境中的状态转移和与状态-动作对关联的奖励。这些问题的已知模型可以是具体规则、概率转移矩阵等，使得智能体能够根据这些信息得到最佳的行动策略。AlphaZero 91 是 DeepMind 公司开发的一种人工智能算法。通过自我对弈的方式，AlphaZero 采用深度强化学习的方法，成功超越了人类在诸如国际象棋、围棋和将棋等游戏上的表现，代表了模型给定强化学习方法的一种典范。Alp

238、haZero 的成功在于其与蒙特卡洛树搜索算法的巧妙结合。蒙特卡洛树搜索是一种在博弈游戏中广泛应用的智能搜索算法。该算法通过大量的随机抽样来估计最优策略，有效的平衡了两者之间的关系。当蒙特卡洛树搜索与AlphaZero 结合使用时，每次搜索步骤可以借助深度神经网络来评估状态并选择行动，进而产生更优的策略。这种将 AlphaZero 与蒙特卡洛树搜索结合的方法已被广泛应用于各种难解问题求解中，因为它能够有效的处理大规模状态空间和决策空间，并从中发现较好的策略。例如，Laterre 等人92 提出了一种名为 Ranked Reward(R2)的算法，用于在单人游戏中实现自我对弈的训练策略。该算法通

239、过对单个代理在多个游戏中获得的奖励进行排名，创建了一个相对性能度量。特别中国人工智能系列白皮书 93 的，R2 算法在二维和三维装箱问题的实例上，优于通用的蒙特卡洛树搜索、启发式算法和整数规划求解器。基于 AlphaGo Zero93 的强化学习策略，Abe 等人94 进一步发展了这种思路，提出了一种名为CombOptZero 的新型学习策略，用于求解最小顶点覆盖、最大割和最大团等问题。Abe 等人94 将图组合优化问题转化为马尔可夫决策过程，并将 AlphaZero 中的卷积神经网络替换为图神经网络，提高了模型对问题的处理能力。在此基础上，利用蒙特卡洛树搜索训练网络，让智能体依据网络预测的信

240、息来确定最佳策略。Li 等人95 将深度学习技术与经典启发式算法的元素相结合，提出了一个新的求解方法。该方法通过训练图卷积网络来估计图中每个顶点属于最优解的概率，然后通过树搜索方法搜索解空间。在布尔可满足性、最大独立集、最小顶点覆盖和最大团等问题上的应用表明，该方法与最先进启发式求解器性能相当。Huang 等人96 结合 AlphaGoZero 和深度神经网络架构，提出了无需任何先验知识的图着色启发式算法。Wang 等人97 提出了 AlphaTSP 方法，该方法利用自我对弈强化学习来学习一个策略网络，并结合蒙特卡洛树搜索求解旅行商问题。实验证明，AlphaTSP在解决小规模旅行商实例时优于最

241、近邻和传统蒙特卡洛树搜索方法。Pierrot 等人98 结合了神经程序解释器和 AlphaZero 的优点，提出了一种新型的算法，被称为 AlphaNPI。神经程序解释器采用模块化、层次结构和递归等结构性偏差，从而减少了样本复杂性，提高了泛化性能。而 AlphaZero 则为其提供了神经网络引导搜索算法。Xu 等人99 提出了 Zermelo Gamification（ZG）方法。该方法将特定组合优化问题转化为Zermelo游戏，且专门设计了一个神经蒙特卡洛树搜索算法。这一策略为求解组合优化问题提供了新的方法和思路。模型学习方法主要依赖于与环境的交互，进而理解环境的动态性。具体来说，模型学习方

242、法尝试基于已观察到的状态转移和奖励来估计环境的未知转移和奖励函数。当模型被学习后，它可以用来模拟环境，中国人工智能系列白皮书 94 预测未来的状态和奖励。模型学习方法可大致分为参数化方法和非参数化方法。参数化方法指的是学习一个具有特定参数的环境模型，而非参数化方法不假定任何特定的环境模型，直接估计状态转移和奖励函数。一些模型学习方法还利用了深度学习技术，以构建更复杂的环境模型。尽管学习环境模型可以帮助更深入的理解环境动态，从而提升规划和决策的有效性，但在实际应用中，特别是在处理组合优化问题时，模型学习方法仍然处于初级阶段。4.3 总结与展望 图学习方法和强化学习方法构成了求解难解问题的重要研究

243、方向。图学习方法的基本原理是基于难解问题实例与图的关系，依赖图中节点和边的互联关系为这些难解问题做出表征，借助于图的拓扑结构和节点特性，对难解问题进行深度理解，并运用图神经网络等工具对图进行深入的剖析和推理，以此对难解问题进行求解。强化学习方法通过智能体（Agent）在其环境中的探索行为求解难解问题。在这个求解过程中，智能体通过连续的互动和反馈，学习如何采取最优行动策略实现特定的优化目标。然而，难解问题的机器学习方法仍然存在着如下挑战。（1）泛化能力差：诸多图学习方法在训练数据上性能表现良好，然而大规模实例和实际应用实例上的性能表现不佳。这主要是由于模型过拟合或者对训练数据的分布假设过于严格造

244、成的。这种泛化能力差的问题在复杂、高维度和稀疏的数据环境中尤为严重。尽管强化学习方法已有在许多组合优化问题上的表现不错，但将学习到的策略有效的泛化到其他问题或数据分布上仍然有难度。（2）全局结构无法获取：在利用机器学习方法处理结构化图问题时，图问题全局结构的获取往往对学习