人工智能(第2版)

   第一部分引言

第1章人工智能概述 2

1.0 引言 2

1.0.1 人工智能的定义 3

1.0.2 思维是什么？智能是什么？ 3

1.1 图灵测试 5

1.1.1 图灵测试的定义 6

1.1.2 图灵测试的争议和批评 8

1.2 强人工智能与弱人工智能 9

1.3 启发法 11

1.3.1 长方体的对角线：解决一个相对简单但相关的

问题 11

1.3.2 水壶问题：向后倒推 12

1.4 识别适用人工智能来求解的问题 13

1.5 应用和方法 15

1.5.1 搜索算法和拼图 16

1.5.2 二人博弈 18

1.5.3 自动推理 18

1.5.4 产生式规则和专家系统 19

1.5.5 细胞自动机 20

1.5.6 神经计算 21

1.5.7 遗传算法 23

1.5.8 知识表示 23

1.5.9 不确定性推理 24

1.6 人工智能的早期历史 25

1.7 人工智能的近期历史到现在 29

1.7.1 博弈 29

1.7.2 专家系统 30

1.7.3 神经计算 31

1.7.4 进化计算 31

1.7.5 自然语言处理 32

1.7.6 生物信息学 34

1.8 新千年人工智能的发展 34

1.9 本章小结 36

第二部分 基础知识

第2章盲目搜索 46

2.0 简介：智能系统中的搜索 46

2.1 状态空间图 47

2.2 生成与测试范式 49

2.2.1 回溯 50

2.2.2 贪婪算法 54

2.2.3 旅行销售员问题 56

2.3 盲目搜索算法 58

2.3.1 深度优先搜索 58

2.3.2 广度优先搜索 60

2.4 盲目搜索算法的实现和比较 63

2.4.1 实现深度优先搜索 63

2.4.2 实现广度优先搜索 65

2.4.3 问题求解性能的测量指标 65

2.4.4 DFS和BFS的比较 66

2.5 本章小结 68

第3章 知情搜索 74

3.0 引言 74

3.1 启发法 76

3.2 知情搜索（第一部分）——找到任何解 81

3.2.1 爬山法 81

3.2.2 最陡爬坡法 82

3.3 很好优先搜索 84

3.4 集束搜索 87

3.5 搜索算法的其他指标 89

3.6 知情搜索（第二部分）——找到很好解 90

3.6.1 分支定界法 90

3.6.2 使用低估值的分支定界法 95

3.6.3 采用动态规划的分支定界法 98

3.6.4 A*搜索 99

3.7 知情搜索（第三部分）—高级搜索算法 100

3.7.1 约束满足搜索 100

3.7.2 与或树 101

3.7.3 双向搜索 102

3.8 本章小结 104

第4章 博弈中的搜索 109

4.0 引言 109

4.1 博弈树和极小化极大评估 110

4.1.1 启发式评估 112

4.1.2 博弈树的极小化极大评估 112

4.2 具有α-剪枝的极小化极大算法 115

4.3 极小化极大算法的变体和改进 120

4.3.1 负极大值算法 120

4.3.2 渐进深化法 122

4.3.3 启发式续篇和地平线效应 122

4.4 概率游戏和预期极小化极大值算法 123

4.5 博弈理论 125

迭代的囚徒困境 126

4.6 本章小结 127

第5章 人工智能中的逻辑 133

5.0 引言 133

5.1 逻辑和表示 134

5.2 命题逻辑 135

5.2.1 命题逻辑—基础 136

5.2.2 命题逻辑中的论证 140

5.2.3 证明命题逻辑论证有效的第二种方法 141

5.3 谓词逻辑——简要介绍 143

5.3.1 谓词逻辑中的合一 144

5.3.2 谓词逻辑中的反演 146

5.3.3 将谓词表达式转换为子句形式 148

5.4 其他一些逻辑 151

5.4.1 二阶逻辑 151

5.4.2 非单调逻辑 152

5.4.3 模糊逻辑 152

5.4.4 模态逻辑 153

5.5 本章小结 153

第6章 知识表示 160

6.0 引言 160

6.1 图形草图和人类视窗 163

6.2 图和哥尼斯堡桥问题 166

6.3 搜索树 167

6.4 表示方法的选择 169

6.5 产生式系统 172

6.6 面向对象 172

6.7 框架法 173

6.8 脚本和概念依赖系统 176

6.9 语义网络 179

6.10 关联 181

6.11 新近的方法 182

6.11.1 概念地图 182

6.11.2 概念图 184

6.11.3 Baecker的工作 184

6.12 智能体：智能或其他 185

6.12.1 智能体的一些历史 188

6.12.2 当代智能体 189

6.12.3 语义网 191

6.12.4 IBM眼中的未来世界 191

6.12.5 作者的观点 192

6.13 本章小结 192

第7章 产生式系统 199

7.0 引言 199

7.1 背景 199

7.2 基本示例 202

7.3 CARBUYER系统 204

7.4 产生式系统和推导方法 208

7.4.1 冲突消解 211

7.4.2 正向链接 213

7.4.3 反向链接 214

7.5 产生式系统和细胞自动机 219

7.6 随机过程与马尔可夫链 221

7.7 本章小结 222

第三部分 基于知识的系统

第8章 人工智能中的不确定性 228

8.0 引言 228

8.1 模糊集 229

8.2 模糊逻辑 231

8.3 模糊推理 232

8.4 概率理论和不确定性 235

8.5 本章小结 239

第9章 专家系统 242

9.0 引言 242

9.1 背景 242

9.2 专家系统的特点 249

9.3 知识工程 250

9.4 知识获取 252

9.5 经典的专家系统 254

9.5.1 DENDRAL 254

9.5.2 MYCIN 255

9.5.3 EMYCIN 258

9.5.4 PROSPECTOR 259

9.5.5 模糊知识和贝叶斯规则 261

9.6 提高效率的方法 262

9.6.1 守护规则 262

9.6.2 Rete算法 263

9.7 基于案例的推理 264

9.8 更多近期新的专家系统 269

9.8.1 改善就业匹配系统 269

9.8.2 振动故障诊断的专家系统 270

9.8.3 自动牙科识别 270

9.8.4 更多采用案例推理的专家系统 271

9.9 本章小结 271

第10章机器学习第一部分 277

10.0 引言 277

10.1 机器学习：简要概述 277

10.2 机器学习系统中反馈的作用 279

10.3 归纳学习 280

10.4 利用决策树进行学习 282

10.5 适用于决策树的问题 283

10.6 熵 284

10.7 使用ID3构建决策树 285

10.8 其余问题 287

10.9 本章小结 288

第11章机器学习第二部分：神经网络 291

11.0 引言 291

11.1 人工神经网络的研究 292

11.2 麦卡洛克-皮茨网络 294

11.3 感知器学习规则 295

11.4 增量规则 303

11.5 反向传播 308

11.6 实现关注点 313

11.6.1 模式分析 316

11.6.2 训练方法 317

11.7 离散型霍普菲尔德网络 318

11.8 应用领域 323

11.9 本章小结 330

第12章受到自然启发的搜索 337

12.0 引言 337

12.1 模拟退火 338

12.2 遗传算法 341

12.3 遗传规划 349

12.4 禁忌搜索 353

12.5 蚂蚁聚居地优化 356

12.6 本章小结 359

第四部分 高级专题

第13章自然语言处理 368

13.0 引言 368

13.1 概述：语言的问题和可能性 368

13.2 自然语言处理的历史 371

13.2.1 基础期（20世纪40年代和50年代） 371

13.2.2 符号与随机方法（1957—1970） 372

13.2.3 ４种范式（1970—1983） 372

13.2.4 经验主义和有限状态模型（1983—1993） 373

13.2.5 大融合（1994—1999） 373

13.2.6 机器学习的兴起（2000—2008） 374

13.3 句法和形式语法 374

13.3.1 语法类型 374

13.3.2 句法解析：CYK算法 379

13.4 语义分析和扩展语法 380

13.4.1 转换语法 381

13.4.2 系统语法 381

13.4.3 格语法 382

13.4.4 语义语法 383

13.4.5 Schank系统 383

13.5 NLP中的统计方法 387

13.5.1 统计解析 387

13.5.2 机器翻译（回顾）和IBM的Candide系统 388

13.5.3 词义消歧 389

13.6 统计NLP的概率模型 390

13.6.1 隐马尔可夫模型 390

13.6.2 维特比算法 391

13.7 统计NLP语言数据集 392

13.7.1 宾夕法尼亚州树库项目 392

13.7.2 WordNet 394

13.7.3 NLP中的隐喻模型 394

13.8 应用：信息提取和问答系统 396

13.8.1 问答系统 396

13.8.2 信息提取 401

13.9 现在和未来的研究（基于CHARNIAK的工作） 401

13.10 语音理解 402

13.11 语音理解技术的应用 405

13.12 本章小结 410

第14章自动规划 417

14.0 引言 417

14.1 规划问题 418

14.1.1 规划术语 418

14.1.2 规划应用示例 419

14.2 一段简短的历史和一个有名的问题 424

14.3 规划方法 426

14.3.1 规划即搜索 426

14.3.2 部分有序规划 430

14.3.3 分级规划 432

14.3.4 基于案例的规划 433

14.3.5 规划方法集锦 434

14.4 早期规划系统 435

14.4.1 STRIPS 435

14.4.2 NOAH 436

14.4.3 NONLIN 436

14.5 更多现代规划系统 437

14.5.1 O-PLAN 438

14.5.2 Graphplan 439

14.5.3 规划系统集锦 441

14.5.4 学习系统的规划方法 441

14.5.5 SCIBox自动规划器 442

14.6 本章小结 444

第五部分 现在和未来

第15章机器人技术 452

15.0 引言 452

15.1 历史：服务人类、仿效人类、增强人类和替代人类 455

15.1.1 早期机械机器人 455

15.1.2 电影与文学中的机器人 458

15.1.3 20世纪早期的机器人 458

15.2 技术问题 464

15.2.1 机器人的组件 464

15.2.2 运动 467

15.2.3 点机器人的路径规划 468

15.2.4 移动机器人运动学 469

15.3 应用：21世纪的机器人 471

15.4 本章小结 479

第16章高级计算机博弈 482

16.0 引言 482

16.1 跳棋：从塞缪尔到舍弗尔 483

16.1.1 在跳棋博弈中用于机器学习的启发式方法 486

16.1.2 填鸭式学习与概括 488

16.1.3 签名表评估和棋谱学习 489

16.1.4 含有奇诺克程序的世界跳棋锦标赛 490

16.1.5 解决跳棋游戏 491

16.2 国际象棋：人工智能的“果蝇” 494

16.2.1 计算机国际象棋的历史背景 495

16.2.2 编程方法 496

16.2.3 超越地平线效应 505

16.2.4 DeepThought和DeepBlue与特级大师的比赛（1988—1995年） 505

16.3 计算机国际象棋对人工智能的贡献 507

16.3.1 在机器中的搜索 507

16.3.2 在搜索方面，人与机器的对比 508

16.3.3 启发式、知识和问题求解 509

16.3.4 蛮力：知识vs.搜索；表现vs.能力 510

16.3.5 残局数据库和并行计算 511

16.3.6 本书第一作者的贡献 514

16.4 其他博弈 514

16.4.1 奥赛罗 515

16.4.2 西洋双陆棋 516

16.4.3 桥牌 518

16.4.4 扑克 519

16.5 围棋：人工智能的“新果蝇”？ 520

16.6 本章小结 523

第17章大事记 532

17.0 引言 532

17.1 提纲挈领——概述 532

17.2 普罗米修斯归来 534

17.3 提纲挈领——介绍人工智能的成果 535

17.4 IBM的沃森-危险边缘挑战赛 539

17.5 21世纪的人工智能 543

17.6 本章小结 545

附录A CLIPS示例：专家系统外壳 548

附录B 用于隐马尔可夫链的维特比算法的实现（由HarunIftikhar提供） 552

附录C 对计算机国际象棋的贡献：令人惊叹的WalterShawnBrowne 555

附录D 应用程序和数据 559

附录E 部分练习的答案 560