算法大数据算法

【随机算法】蒙特卡洛

字数统计: 986字   |   阅读时长: 3分
,

摘要: 蒙特卡洛方法入门

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

蒙特卡洛不是特定的算法，而是一种统计模拟算法思想，它可以理解为一种基于统计的数值计算方法。有很多随机化算法都是蒙特卡洛的思想的实现，要点如下：

为了求解问题，首先建立一个概率模型或随机过程，使它的参数或数字特征等于问题的解。
然后通过对模型或过程的观察或抽样试验来计算这些参数或数字特征，最后给出所求解的近似值。
解的精确度用估计值的标准误差来表示。
蒙特卡洛法的主要理论基础是概率统计理论，主要手段是随机抽样、统计试验。

基于以上要点，我们可以总结出蒙特卡洛的算法框架：

1
2
3
step1: 根据实际问题的特点．构造简单而又便于实现的概率统计模型．使所求的解恰好是所求问题的概率分布或数学期望
step2: 给出模型中各种不同分布随机变量的抽样方法
step3: 统计处理模拟结果，给出问题解的统计估计值和精度估计值。

蒙特卡洛的这套算法框架的优势主要有三点：

  1. 方法的误差与问题的维数无关。
  2. 对于具有统计性质的问题可以直接进行解决。
  3. 对于连续性的问题不必进行离散化处理。

当然蒙特卡罗法也有以下一些缺点，实践中需要注意：

  1. 确定性问题转化成了随机性问题。
  2. 精度问题，随机数的真伪性也有影响。
  3. 收敛比较慢，通常需要较多的计算步数。

采样

在蒙特卡洛思想的算法框架中，在方案层面最关键的是第一步：构造概率统计模型。在实现层面最关键的是第二步：给出模型的抽样方法。

其中第二步相当于问：给出了概率密度函数，如何采样出满足这个概率密度函数的随机变量。对于比较常见的问题，有下面这些主流的方法可以解决：

  • 直接采样
  • 拒绝采样
  • MCMC采样
  • MH采样
  • Gibbs采样
  • 蓄水池抽样
  • 逆变换采样
  • 别名采样

在文章 拒绝采样 中，我们学习过拒绝采样。

下面我们看一下更简单的直接采样，并解决求圆周率的问题，其他的采样方式我们以后再学习。

求圆周率 (直接采样)

首先构造概率统计模型：边长为 2r 的正方形，它的内切圆半径为 r。正方形的面积为 $4r^{2}$，内切圆的面积为 $\pi r^{2}$。因此随机地在正方形区域内取一个点，它落在圆内的概率为 $\pi/4$。

这个模型非常简单，因此对应的抽样方法就直接抽样即可：对点的横纵坐标分别用均匀分布进行采样，然后判断该点是否落在圆内，进行计数即可。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <random>
#include <iostream>

using namespace std;

int main()
{
    const long double EPS = 1e-15;
    std::default_random_engine dre;
    std::uniform_real_distribution<long double> dr(-1.0, 1.0);
    long double all = 1.0;
    long double get = 0.0;
    int iter = 0;
    while(true)
    {
        long double rand_x = dr(dre);
        long double rand_y = dr(dre);
        all += 1.0;
        if(rand_x * rand_x + rand_y * rand_y < 1 + EPS)
            get += 1.0;
        long double ratio = get / all;
        long double pi = ratio * 4;
        cout << "iter: " << iter << ", pi: " << pi << endl;
        ++iter;
    }
}
Share