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