【Reinforcement Learning】蒙特卡洛算法
强化学习相关的蒙特卡洛算法的介绍。此处笔记根据B站课程,王树森老师的强化学习记录而来。6.蒙特卡洛 Monte Carlo(Av374239425,P6)_哔哩哔哩_bilibili
1.Monte Carlo Algorithms蒙特卡洛算法
蒙特卡罗算法是随机算法的一种, 本质是使用随机样本估计真实值。最终的值是错的,但是它靠近真实值,像是难以求解解析解的积分、神经网络等,使用近似解就可以了,蒙特卡洛算法就是常用的近似算法之一。
2.例1——使用几何方式近似Π
正方形的面积是A1=2*2=4,圆的面积是A2=Π*1^2=Π
在正方形内采用均匀随机抽样,抽点(x,y),点在圆上的概率为p=A2/A1=Π/4。抽取n个点,期望为E(x)=Π*n/4。如何判断点是否在圆上,如x^2+y^2<=1时,点在圆上,否则点不在圆上。
已知均匀抽样n个点,其中m个点在圆上,则可以用m近似Π*n/4,则可以用4m/n近似Π。大数定理保证了蒙特卡洛搜索的正确性,n越大,近似越准确。
3.例2——投针算法
Buffon's Needle Problem布芬投针实验
一组平行线,间距为d, 针长为l, 随机投针,计算针与平行线有交点的概率。p=2l/Πd,n个针投针实验期望为E(X)=np=2ln/Πd
l越大,p越大,d越大,p越小。
使用n个针进行投针实验,有m个针与平行线有交点,则有m近似2ln/Πd, 则2ln/dm可以近似Π。
验证的一种方法:根据概率不等式, 近似精度反比根号n
4.例3——估计阴影布芬面积,近似Π
正方形面积为2*2=4,在正方形内随机均匀采样点(x,y),
若点在圆内,则有(x-1)^2+(y-1)^2<=1
若点在扇外,则有 x^2+y^2>2
则阴影部分,在圆内扇外,设其面积为A2, 正方形为A1=4,则点在阴影部分的概率为p=A2/4。抽n个点,则期望为E(x)=np=n*A2/4。 其中m个点在阴影内,则可用m近似n*A2/4, 则A2的面积可近似为4*m/n
5.例4——近似求积分
复杂积分没有数值解,只能近似,常用蒙特卡罗算法近似。
一元积分:
多元积分,如二元函数近似Π
6.例5——近似期望
7.Monte Carlo相关
Monte Carlo的名字来自赌场,algorithm that rely on repeated random sampling to obtain numerical results.
结果是错的但是接近真实值。
随机快排:随机性不影响正确性,总是正确的
大西洋算法: 正确率高达75%