蒙特卡洛（Markov Chain & Monte Carlo, MCMC）方法

作者：YJLAugus 博客： https://www.cnblogs.com/yjlaugus 项目地址：https://github.com/YJLAugus/Reinforcement-Learning-Notes，如果感觉对您有所帮助，烦请点个⭐Star。

背景介绍

20世纪40年代，在John von Neumann，Stanislaw Ulam 和 Nicholas Metropolis 在洛斯阿拉莫斯国家实验室为核武器计划工作时，发明了蒙特卡罗方法。因为Ulam的叔叔经常在蒙特卡洛赌场输钱得名，而蒙特卡罗方法正是以概率为基础的方法。

蒙特卡洛是摩纳哥的一个小城，蒙特卡洛是摩纳哥公国的一座城市，位于欧洲地中海之滨、法国的东南方，属于一个版图很小的国家摩纳哥公国，世人称之为“赌博之国”、“袖珍之国”、“邮票小国” ， 很漂亮的一座小城。

算法介绍

• 不是 “蒙特卡洛” 发明的，“蒙特卡洛”仅仅是一个城市的名字。由冯·诺依曼、乌拉姆等人发明。这是基于概率的方法的一个统称。

• 常于拉斯维加斯（Las Vegas）方法比较。两种方法各有侧重点：

蒙特卡洛（Monte Carlo）：民意调查——抽样，并估算到最优解。采样越多，越近似最优解。

拉斯维加斯（Las Vegas）：找人——必须要精确到找到那个人。采样越多，越有机会找到最优解。

• 相关算法：

蒙特卡洛算法、蒙特卡洛模拟、蒙特卡洛过程、蒙特卡洛搜索树（AlphaGo就是基于此算法）

工作原理

不断抽样（近似采样），逐渐逼近最优解。

为什么要采样（采样动机）？

• 采样本身就是常见的任务：机器学习中，产生一堆样本，然后进行采样分析。
• 求和或者是求积分的运算（比如下面的例子）。

假定已经采样完毕，那么什么是好的样本？

• 样本趋向于高概率区域（同时兼顾其他区域）：红色球区域
• 样本与样本之间相互独立： 也就是说 在下图红色球最密集区域的球不能有相互联系，不然依然是采样失败的，不能算好的样本。

如下图的概率密度函数图所示，只有样本落在高概率的区域，越集中的样本才算是好的样本（红色球），相反的，绿色球样本就不算是好的样本

一个例子

利用蒙特卡洛方法计算圆周率pi 。如下图所示：

从上面可得，扇形的面积\(S_扇 = \pi·1^2·1 ·\frac{1}{4}=\frac{\pi}{4}\)。正方形的面积为\(S_方 = 1\) ，可得：一个关系如下： $$ \frac {扇形面积}{正方形面积} = \frac{\pi}{4} $$

接下来，如果在下面的图中随机打点，那么点落在绿色扇形区域的概率就是\(P = \frac {扇形面积}{正方形面积} = \frac{\pi}{4}\) ，并最终得到 \(\pi = 4P\)

在程序中实现我们的算法：可以发现，随着样本空间的增加，利用蒙特卡洛算法得到\(\pi\) 的值越接近真实的\(\pi\) 值。

import random
total = 1000000
in_count = 0

for i in range(total):
    x = random.random()
    y = random.random()

    dis = (x ** 2 + y ** 2) ** 0.5

    if dis <= 1:
        in_count += 1
print('Π是:', 4*in_count/total)

# PI = 概率 * 4
# 5       Π是: 4.0
# 100     Π是: 3.28
# 1000    Π是: 3.244
# 10000   Π是: 3.1524
# 100000  Π是: 3.15212
# 1000000 Π是: 3.141696

简单应用

现在进行一个简单的应用，对于上面的规则形状，我们可以很方便的计算出图像的面积，但是对于不规则的图形，就不是那么容易求得了，这里就用蒙特卡洛方法进行计算不规则图形的面积。如下图，如果我们计算图中白色区域的面积，该如何去求得呢？

根据，蒙特卡洛方法，我们还是采用“打点”的方式，总点数为 total_count ，在白色区域的点数为in_count。那么点落在白色区域的概率就是 in_count/total_count，最后用这个概率乘以整张图的面积，就可以大概的估算出白色区域的面积，代码如下：

from PIL import  Image
import random

img = Image.open('panda.jpg')

# 2. 获取像素的颜色
total_count = 1000000
in_count = 0

for i in range(total_count):
    x = random.randint(0, img.width-1)
    y = random.randint(0, img.height-1)
    # color = img.getpixel((x, y))
    # print(color)
    if img.getpixel((x, y)) == (255, 255, 255):
        in_count += 1
p = in_count/total_count
print(int(img.width*img.height * p))
# 20        132240
# 100       143811
# 1000      131744
# 10000     130388
# 100000    130739
# 1000000   130699
# 1.图片读取

接下来进行一个准确的遍历。也就是白色区域的真正的面积值，可以发现，和上面的几乎一致，利用蒙特卡洛算法得到的是 130699，准确的数据是130686， 相差无几。

# right: 130686
# 1.图片读取
from PIL import  Image
import random

img = Image.open('panda.jpg')

# 2. 获取像素的颜色
count = 0
for x in range(img.width):
    for y in range(img.height):
        if (255, 255, 255) == img.getpixel((x,y)):
            count += 1
print(count)

参考文献

https://www.bilibili.com/video/BV1Gs411g7EJ?t=1690