Loading... # 前言 在学习贝叶斯数据分析的时候，看到了一个陌生而又熟悉的词汇：蒙特卡罗方法（Monte Carlo method，简称MC）。这个词我在很多地方都有见到过，很多算法的论文、博客都有提到，最近又想起来，在本科学习优化与建模这门课的时候，似乎就有一节专门讲蒙特卡罗方法的，但是蒙特卡罗方法到底是什么，似乎很少有人提起过，因此想专门写一篇博客记录和分享下我对蒙特卡罗方法及其延伸的一些理解。 # 蒙特卡罗方法 > 提醒： > > 1. 对蒙特卡罗方法原文感兴趣的同学可以看下这篇论文："The Monte Carlo Method", 1949 > 2. 这篇论文整体并没有很高深的数学公式，行文也更偏一个思考过程而非现在经常看到的大数据类的论文 ## 蒙特卡罗方法的背景 蒙特卡罗方法这个名字最初是由Nicholas Metropolis、Stanislaw Ulam和John von Neumann三人在20世纪40年代末期提出来的。在英文维基百科上，关于蒙特卡罗方法最初的想法和实践，Stanislaw Ulam有下面这样的描述[<sup>[1]</sup>](#ref1)： > The first thoughts and attempts I made to practice [the Monte Carlo Method] were suggested by a question which occurred to me in 1946 as I was convalescing from an illness and playing solitaires. **The question was what are the chances that a Canfield solitaire laid out with 52 cards will come out successfully?** After spending a lot of time trying to estimate them by pure combinatorial calculations, **I wondered whether a more practical method than "abstract thinking" might not be to lay it out say one hundred times and simply observe and count the number of successful plays**. This was already possible to envisage with the beginning of the new era of fast computers, and I immediately thought of problems of neutron diffusion and other questions of mathematical physics, and more generally how to change processes described by certain differential equations into an equivalent form interpretable as a succession of random operations. Later [in 1946], I described the idea to John von Neumann, and we began to plan actual calculations. 这段话中给出了两个关键点： - 第一是研究的问题。Stanislaw Ulam想要研究给定52张扑克牌的情况下，通过特定的游戏规则，能够成功完成接龙游戏的概率有多高，这个问题本质上就是一个概率问题。 - 第二是研究的方法。对于这一个概率问题，Stanislaw Ulam想要测试100次，通过观察完成接龙的次数来计算坎菲尔德接龙这个游戏成功接龙的的概率。也就是说，想要通过抽样统计的方式来解决这一问题。 看到这，肯定有很多人会想，这个不就是在应用大数定律吗？这和蒙特卡罗方法有什么关系呢？ 实际上，**蒙特卡洛方法的理论基础就是我们常说的大数定律**。如果说要给蒙特卡罗方法下个定义的话，我认为是：**蒙特卡罗方法就是通过大量的、重复的随机抽样，获得数值结果，并根据这些数值结果来分析、推断或求解某些问题的一种方法。** ## 蒙特卡罗方法的步骤 蒙特卡罗方法的步骤非常简单，主要有以下三步： - step1: 将实际问题抽象成一个简单且便于实现的概率统计模型，使所求的量（或解）恰好是该模型某个指标的概率分布或者数字特征。 - step2: 确定抽样方法，然后大量重复抽样，抽取出足够多的样本，对有关事件进行统计 - step3: 对抽样统计结果加以分析，给出所求的量（或解）的估计及其精度(方差)的估计 蒙特卡罗方法本身不是一种算法，更像是一种算法的集合，很多算法其实就是基于蒙特卡罗方法的步骤和思想创建的。 ## 蒙特卡罗方法使用的关键点和难点 ### 关键点 蒙特卡罗方法有效的关键点在于**如何产生好的随机样本**。样本性质优良，才能保证我们统计模拟的结果接近于理论结果，抽样统计结果是可信的。在计算机模拟时，这个问题变得尤为重要，我们所使用的随机数实际上是由确定性算法产生的伪随机数，如果伪随机数的性质不够优良（比如不满足均匀性），将会那么我们实际求出的问题的解会受到我们随机数本身产生的内在规律的影响。在此后的篇章，我们会介绍随机数生成器的相关科普。 ### 难点 而蒙特卡罗方法使用的难点在于**如何低成本的大量重复抽样以及如何确定抽样数量**。通过大数定律我们可以知道，随着样本数的增多，样本均值逐渐趋于总体均值，样本方差也趋于总体方差。由于我们的样本数是有限的，因此在抽样时可能会面临以下两个问题： 第一个问题是抽样的样本量不足的问题。过小的样本量往往意味着更大的方差，也就是说，如果抽样的样本过少，精度往往达不到要求，参数的置信区间将会变得比较大而没法使用。 **为了评估样本数量是否充足，需要计算抽样计算的精度**。比如我们要模拟抛硬币的情形，需要估计硬币为正面的概率$p$的大小。假设我们抽样了$L=20$个样本点，为方便计算，我们同时假设计算得到的样本均值为$p=0.5$，那么这个计算的精度为 $$ \begin{aligned} std(x)=\sqrt{\frac{p(1-p)}{L}}=11.18\% \end{aligned} $$ 如果抽样了$L=200$个样本点，则这个精度为 $$ \begin{aligned} std(x)=\sqrt{\frac{p(1-p)}{L}}=3.54\% \end{aligned} $$ 精度是否足够需要根据自己的实际问题进行判断，对于大多数问题来说，3.54\%的标准误已经可以满足需求了。**另一方面，既然可以评估抽样精度，自然我们也就可以根据根据预设的抽样精度，估算出所需要的样本量**。方法是大同小异的，这里不再赘述。 第二个问题则是关于抽样的样本量过大导致无法抽样的问题。随机抽样不是零成本的。抽样的数量越多，我们所需要消耗的计算资源和时间成本也就越大。 假设我们要估计的参数$\theta$满足$\theta \in R$，那么我们抽样$L=1000$个样本，也就是需要生成$1000^{1}=1000$个随机数（网格点，grid point），看起来这并不是很大。 但假如要估计的参数$\theta$满足$\theta \in R^{10}$，抽样$L=1000$个样本时，相当于需要给每个样本的每一维都需要生成一个某分布的随机数，此时所需要生成的网格点数量为$1000^{10}=10^{30}$。 如果我们的计算机程序每秒可以生成$10^{9}$个某分布的随机数，那也需要$\frac{10^{30}}{10^{9}*3600*24*365}\approx1.59*10^{13}$年才可能计算出来。 上面便是一个维数灾难的例子，即对于高维参数的估计，随着维数的增加，其计算量将会呈现非线性的增长。 后来人们发现，**对于高维参数的估计，比如要估计其期望，并不是所有的网格点都对最终的结果有巨大贡献。应该说，绝大部份网格点的概率都很小，只有少数网格点的概率较高，因此真正对参数的期望起贡献的的只有少数的一些网格点**。 这也就使得人们在开始研究不同的采样方法，比如说Rejection Sampling，Importance Sampling等，还有一类算法，其统称我们也经常在各类博客、论文里听到，它就是马尔科夫蒙特卡罗方法（Markov Chain Monte Carlo Method），关于采样方法，后续也会有专门的介绍 # 参考文献 <div id="ref1"></div> [1] Monte Carlo Method. (n.d.). https://en.wikipedia.org/wiki/Monte_Carlo_method 最后修改：2022 年 06 月 04 日 © 允许规范转载 打赏 赞赏作者 赞 0 如果觉得我的文章对你有用，请随意赞赏