《蒙特卡罗方法与人工智能》的原著作者朱松纯教授在人工智能和计算机视觉领域享有盛誉，他的研究成果广泛引用并影响了该领域的发展；从学术成果、荣誉和贡献上来说，他是一位世界著名科学家。
本书由朱松纯教授推荐西安交通大学人工智能学院教授、国家青年人才魏平翻译，全面叙述了蒙特卡罗方法，包括序贯蒙特卡罗方法、马尔可夫链蒙特卡罗方法基础、Metropolis算法及其变体、吉布斯采样器及其变体、聚类采样方法、马尔可夫链蒙特卡罗的收敛性分析、数据驱动的马尔可夫链蒙特卡罗方法、哈密顿和朗之万蒙特卡罗方法、随机梯度学习和可视化能级图等，文字精练、流畅，内容经典，有深度，是人工智能领域经典图书，可适合计算机、人工智能、机器人等领域的教师、学生阅读和参考，也适合相关领域的研究者和工业界的从业者阅读。

本书全面叙述了蒙特卡罗方法，包括序贯蒙特卡罗方法、马尔可夫链蒙特卡罗方法基础、Metropolis算法及其变体、吉布斯采样器及其变体、聚类采样方法、马尔可夫链蒙特卡罗的收敛性分析、数据驱动的马尔可夫链蒙特卡罗方法、哈密顿和朗之万蒙特卡罗方法、随机梯度学习和可视化能级图等。为了便于学习，每章都包含了不同领域的代表性应用实例。本书旨在统计学和计算机科学之间架起一座桥梁以弥合它们之间的鸿沟，以便将其应用于计算机视觉、计算机图形学、机器学习、机器人学、人工智能等领域解决更广泛的问题，同时使这些领域的科学家和工程师们更容易地利用蒙特卡罗方法加强他们的研究。

本书适合计算机、人工智能、机器人等领域的教师、学生阅读和参考，也适合相关领域的研究者和工业界的从业者阅读。

朱松纯，1996年获得哈佛大学计算机科学博士学位，现任北京通用人工智能研究院院长、北京大学人工智能研究院院长、北京大学讲席教授、清华大学基础科学讲席教授；曾任美国加州大学洛杉矶分校（UCLA）统计学与计算机科学教授，加州大学洛杉矶分校视觉、认知、学习与自主机器人中心主任。 他长期致力于为视觉和智能探寻一个统一的统计与计算框架：包括作为学习与推理的统一表达和数字蒙特卡罗方法的时空因果与或图（STC-AOG）。他在计算机视觉、统计学习、认知、人工智能和自主机器人领域发表了400多篇学术论文。他曾获得了多项荣誉，2003年因图像解析的工作成就获马尔奖，1999年因纹理建模、2007年因物体建模两次获得马尔奖提名。2001 年，他获得了NSF青年科学家奖、ONR青年研究员奖和斯隆奖。因为在视觉模式的概念化、建模、学习和推理的统一基础方面的贡献，他2008年获得了国际模式识别协会授予的J.K. Aggarwal奖。2013 年，他关于图像分割的论文获得了亥姆霍兹奖（Helmholtz Test-of-Time Award）。2017年，他因生命度建模工作获国际认知学会计算建模奖。2011年，他当选IEEE Fellow。他两次担任国际计算机视觉与模式识别大会（CVPR 2012，2019）主席。作为项目负责人，他领导了多个ONR MURI和DARPA团队，从事统一数学框架下的场景和事件理解以及认知机器人的工作。

巴布·艾俊，2000 年获得俄亥俄州立大学数学博士学位，2005 年获得加州大学洛杉矶分校计算机科学博士学位（师从朱松纯博士）。2005年至2007年，他在西门子研究院从事医学成像研究工作，从开始担任研究科学家到后来升任项目经理。由于在边缘空间学习方面的工作成就，他与西门子的合作者获得了2011年Thomas A. Edison专利奖。2007年，他加入佛罗里达州立大学统计系，从助理教授到副教授，再到2019年担任教授。他发表了70多篇关于计算机视觉、机器学习和医学成像方面的论文，并拥有超过25项与医学成像和图像去噪相关的专利。
魏平，西安交通大学人工智能学院教授、博士生导师，人工智能学院副院长，国家级青年人才，陕西高校青年创新团队（自主智能系统）带头人，西安交通大学“青年拔尖人才支持计划”A类入选者。西安交通大学学士、博士学位，美国加州大学洛杉矶分校（UCLA）博士后、联合培养博士。研究领域包括计算机视觉、机器学习、智能系统等。主持国家自然科学基金项目、国家重点研发计划子课题等科研项目十余项，作为骨干成员参与国家自然科学基金重大科学研究计划等课题多项。在TPAMI、CVPR、ICCV、ACM MM、AAAI、IJCAI等国际权威期刊和会议发表学术论文多篇，是十余个国际著名期刊和会议审稿人。担任中国自动化学会网联智能专委会副主任委员、中国图象图形学学会机器视觉专委会委员。

目 录
第1 章 蒙特卡罗方法简介··············································································.1
1.1 引言·······························································································.1
1.2 动机和目标······················································································.1
1.3 蒙特卡罗计算中的任务·······································································.2
1.3.1 任务1：采样和模拟········································································.3
1.3.2 任务2：通过蒙特卡罗模拟估算未知量···················································.5
1.3.3 任务3：优化和贝叶斯推理································································.7
1.3.4 任务4：学习和模型估计···································································.8
1.3.5 任务5：可视化能级图·····································································.9
本章参考文献··························································································13
第2 章 序贯蒙特卡罗方法··············································································14
2.1 引言·······························································································14
2.2 一维密度采样···················································································14
2.3 重要性采样和加权样本·······································································15
2.4 序贯重要性采样（SIS） ······································································18
2.4.1 应用：表达聚合物生长的自避游走························································18
2.4.2 应用：目标跟踪的非线性/粒子滤波·······················································20
2.4.3 SMC 方法框架总结·········································································23
2.5 应用：利用SMC 方法进行光线追踪·······················································24
2.6 在重要性采样中保持样本多样性···························································25
2.6.1 基本方法····················································································25
2.6.2 Parzen 窗讨论··············································································28
2.7 蒙特卡罗树搜索················································································29
2.7.1 纯蒙特卡罗树搜索··········································································30
2.7.2 AlphaGo ·····················································································32
2.8 本章练习·························································································33
本章参考文献··························································································35
第3 章 马尔可夫链蒙特卡罗方法基础·······························································36
3.1 引言·······························································································36
蒙特卡罗方法与人工智能
·X ·
3.2 马尔可夫链基础················································································37
3.3 转移矩阵的拓扑：连通与周期······························································38
3.4 Perron-Frobenius 定理··········································································41
3.5 收敛性度量······················································································42
3.6 连续或异构状态空间中的马尔可夫链·····················································44
3.7 各态遍历性定理················································································45
3.8 通过模拟退火进行MCMC 优化·····························································46
3.9 本章练习·························································································49
本章参考文献··························································································51
第4 章 Metropolis 算法及其变体······································································52
4.1 引言·······························································································52
4.2 Metropolis-Hastings 算法······································································52
4.2.1 原始Metropolis-Hastings 算法······························································53
4.2.2 Metropolis-Hastings 算法的另一形式·······················································54
4.2.3 其他接受概率设计··········································································55
4.2.4 Metropolis 算法设计中的关键问题·······························4

译  者  序

蒙特卡罗方法是一种基于概率统计和随机采样的数值计算方法。18世纪70年代，法国数学家蒲丰用投针实验方法求圆周率π，一般被认为是蒙特卡罗方法的起源。20 世纪30 年代，费米运用类似蒙特卡罗思路的方法来解决中子研究中的计算问题，但他并没有正式命名或发表这些方法。直到20世纪40年代，为了解决科学实践中遇到的大规模数值计算问题，冯·诺伊曼和乌拉姆等科学家正式提出并命名了蒙特卡罗方法。进入 21 世纪，随着计算能力的高速增长和数据的极大丰富，蒙特卡罗方法在人工智能、计算机、工程学、物理、生物、经济、金融等领域发挥着越来越重要的作用。

蒙特卡罗方法与人工智能任务的结合是一个自然而美妙的过程，因为两者都要面对并解决“不确定性”问题。但蒙特卡罗方法的基础理论复杂，计算框架灵活，算法思路精巧，导致很多研究者和工程师觉得用蒙特卡罗方法解决人工智能问题的门槛较高，领域内也缺少系统探讨将蒙特卡罗方法与人工智能相结合的资料。

正因此，朱松纯教授和巴布·艾俊教授撰写了《蒙特卡罗方法与人工智能》（Monte Carlo Methods），并于2020年由施普林格（Springer）出版社出版。该书系统介绍了蒙特卡罗方法及其在计算机和人工智能中的应用，包括计算机视觉、计算机图形学、机器学习、机器人等领域，目的是在蒙特卡罗方法和人工智能之间架起一座桥梁，促进该方法更好地应用于人工智能。

朱松纯教授和巴布·艾俊教授一直耕耘于统计学习和人工智能领域的前沿。自 20 世纪 90 年代中期，朱松纯教授引领了视觉统计建模与计算理论的发展潮流，是数据驱动的马尔可夫链蒙特卡罗（DDMCMC）、FRAME等众多著名的统计学习方法的提出者。朱松纯教授为人工智能的发展和人才培养做出了重要贡献。

《蒙特卡罗方法与人工智能》英文版完成后，朱松纯教授深感有必要推出中文版本，以方便我国的学者特别是青年学生和初学者使用。我很荣幸受朱松纯教授委托负责翻译出版《蒙特卡罗方法与人工智能》中文版。

感谢西安交通大学郑南宁教授和原著作者朱松纯教授给予的建议和帮助。感谢电子工业出版社李树林编辑，他认真负责、精益求精，给出了大量修改建议。同时，我的研究生们在书稿整理、校对等方面做了大量工作，在此表示感谢。正是有了他们的帮助，《蒙特卡罗方法与人工智能》中文版才得以顺利出版。

特别说明，为了与原著对应，译者在翻译过程中对参考文献并未做修改，完全保留原著格式；为了符合中文出版规范，中文版书中修改了原著中的部分数学符号及表达形式。同时，为了便于读者阅读，特准备了原著中的彩色图片资料包，读者可从电子工业出版社华信教育资源网（https://www.hxedu.com.cn）下载。

译者虽尽心竭力以期尽可能传达原意，但因水平和能力有限，对此博大精深内容仅知皮毛，书中难免有翻译谬误和不当之处，敬请读者批评指正，以期今后进一步修改完善。

魏  平

2023年11月于西安交通大学人工智能学院

中 文 版 序

在很多科学领域（如物理学、化学与生物学）与工程领域（如计算机视觉、图形学与仿真），还有经济与社会模拟领域，蒙特卡罗方法已经得到广泛应用。近年来，统计建模与机器学习成为人工智能发展的主要推动力量，而模型的模拟、推理、学习都是基于各种蒙特卡罗方法的。可以说，统计建模与蒙特卡罗方法是未来人工智能科学发展的主流，这个趋势在后面的发展中还会得到加强。

我在加州大学洛杉矶分校（UCLA）教了“蒙特卡罗方法”（Monte Carlo Methods）这门课 10 多年后，在我的一名博士生巴布·艾俊（Adrian Barbu）协助下根据教案于2020 年完成了英文版教材的编写并出版。目前，我们正计划于 2024 年春天在北京大学开设“蒙特卡罗方法与人工智能”的课程。

西安交通大学魏平教授用了几年的时间，把该教材翻译成中文，交由电子工业出版社出版，这必将有助于促进蒙特卡罗方法在人工智能中的应用和推广。非常感谢魏平教授在翻译和出版过程中所做的大量工作。由于中英文排版的习惯不同，蒙特卡罗方法术语众多、公式复杂，他在翻译过程中做了很多细致的修改，几易其稿，多次校正，才形成了目前的版本。

相信中文版一定有助于促进和推广蒙特卡罗方法在人工智能以及其他相关领域的应用，助力我国人工智能人才的培养。

朱松纯

2023年11月于北京

前   言

在科学（如物理学、化学和生物学）和工程（如视觉、图形和机器人）中研究的现实世界系统涉及大量要素之间的复杂交互，我们可以用高维空间中定义在图上的概率模型表达这种系统，但这种模型的解析解通常是难以获得的。因此，蒙特卡罗方法已作为通用工具，用在科学和工程的模拟、估计、推理和学习中。毫无疑问，Metropolis算法是20世纪科学实践中最常用的十大算法之一（Dongarra和Sullivan，2000）。随着计算能力的不断增长，研究人员需要解决更加复杂的问题并采用更加先进的模型。在21世纪科学和工程的发展中，蒙特卡罗方法将继续发挥重要的作用，而哈密顿和郎之万蒙特卡罗方法在近期发展的深度学习的随机梯度下降法中的应用是这个趋势的又一个例子。

在历史上，一些领域为蒙特卡罗方法的发展做出了贡献。

• 物理和化学：早期的Metropolis算法（Metropolis、Rosenbluth、Rosenbluth、Teller和Teller，1953）、模拟退火（Kirkpatrick、Gelatt和Vecchi，1983）、聚类采样（Swendsen和Wang，1987；Edwards和Sokal，1988），以及近期用于可视化自旋玻璃（Spin Glass）模型能级图的工作（Becker和Karpus，1997）。
• 概率学和统计学：随机梯度（Robin和Monro，1951；Younes，1988），Hastings动态过程（Hastings，1970），数据增强（Tanner和Wong，1987），可逆跳跃（Green，1995），用于研究生物信息学的动态加权（Wong和Liang，1997），以及限制马尔可夫链蒙特卡罗收敛的数值分析（Diaconis，1988；Diaconis和Stroock，1991；Liu，1991）。
• 理论计算机科学：聚类采样的收敛率（Jerrum和Sinclair，1989；Cooper和Frieze，1999）。
• 计算机视觉和模式理论：用于图像处理的吉布斯采样器（Geman和Geman，1984），用于分割的跳跃扩散（Miller和Grenander，1994），用于目标跟踪的条件密度传播或粒子滤波算法（Isard和Blake，1996），以及近期用于图像分割和解析的数据驱动的马尔可夫链蒙特卡罗方法（Tu和Zhu，2002）和广义SW切分算法（Barbu和Zhu，2005）。

考虑到这些多样化的领域使用不同的方法语言，跨学科交流一直都非常少。这给想要使用蒙特卡罗方法的计算机科学与工程领域的从业者带来了巨大的挑战。

一方面，有效的蒙特卡罗方法必须探索问题领域的基础结构，因此它们是针对特定领域或问题而很难被领域外的人理解的。例如，物理学中的许多重要著作，如 SW 算法（Swendsen和Wang，1987），只有2～3页，并且不包含背景或介绍，这使它们对计算机科学家和工程师显得十分神秘。

另一方面，虽然统计学家发明的通用或领域无关的蒙特卡罗方法具有很好的可解释性，但是当工程师在不利用底层模型和表示结构的情况下以通用方式来实现这些方法时，通常会发现它们不是很有效。因此，科学家和研究人员普遍有一种误解，认为这些方法计算效率太低并且通常效果不好。这对蒙特卡罗方法不公平，同时对初出茅庐的学生来说也是不幸的。

本书基于作者过去10年为加州大学洛杉矶分校（UCLA）统计系和计算机科学系学生授课的材料和草稿，是为统计学、计算机科学和工程学领域的研究人员和研究生而编写的。它涵盖了蒙特卡罗计算中广泛的主题，包括在上述几个领域发展的理论基础和直观思想，同时省略了在实践中较少使用或不起作用的小技巧。它采用计算机视觉、图形学和机器学习中的经典问题阐述了蒙特卡罗设计的艺术，因此可以被计算机视觉与模式识别、机器学习、图形学、机器人学和人工智能领域的研究人员用作参考书。

作者感谢UCLA许多在读和已毕业的博士研究生，他们为本书做出了贡献。Mitchell Hill以他的学位论文工作为基础，为第9章、第10章和第11章做出了贡献，这些工作丰富了本书的内容。Zachary Stokes润色了手稿中的许多细节。Maria Pavlovskaia、Kewei Tu、Zhuowen Tu、Jacob Porway、Tianfu Wu、Craig Yu、Ruiqi Gao和Erik Nijkamp贡献了作为例子的材料和图表。作者在UCLA的同事Qing Zhou教授等为本书的改进提供了非常宝贵的建议。

作者还要感谢DARPA、ONR MURI基金和NSF在完成本书过程中的支持。

巴布·艾俊

朱松纯