Identity transfer and the rise of virtual surrealism

蒙特卡洛(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\)

image-20201208140817233

在程序中实现我们的算法:可以发现,随着样本空间的增加,利用蒙特卡洛算法得到\(\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

简单应用

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

image-20201208192324680

根据,蒙特卡洛方法,我们还是采用“打点”的方式,总点数为 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

ABOUT

Goals determine what you going to be!

Contact