1700537300
1700537301
1700537302
图8.4 重要性采样示意图
1700537303
1700537304
在实际应用中，如果是高维空间的随机向量，拒绝采样和重要性重采样经常难以寻找合适的参考分布，采样效率低下（样本的接受概率小或重要性权重低），此时可以考虑马尔可夫蒙特卡洛采样法，常见的有Metropolis-Hastings采样法和吉布斯采样法。后续会专门介绍马尔可夫蒙特卡洛采样法，这里不再赘述。
1700537305
1700537306
·总结与扩展·
1700537307
1700537308
上述解答中我们只是列举了几个最常用的采样算法，简单介绍了它们的具体操作。在实际面试时，面试官可能会让面试者选择其最熟悉的某个采样算法来回答，然后较深入地问一下该算法的理论证明、优缺点、相关扩展和应用等。例如，为何拒绝采样或重要性采样在高维空间中会效率低下而无法使用？如何从一个不规则多边形中随机取一个点？
1700537309
1700537310
1700537311
1700537312
1700537313
百面机器学习：算法工程师带你去面试 [:1700532215]
1700537314
百面机器学习：算法工程师带你去面试 04 高斯分布的采样
1700537315
1700537316
1700537317
1700537318
场景描述
1700537319
1700537320
高斯分布，又称正态分布，是一个在数学、物理及工程领域都非常重要的概率分布。在实际应用中，经常需要对高斯分布进行采样。虽然在很多编程语言中，直接调用某个函数就可以生成高斯分布随机数，但了解其中的具体算法能够加深我们对相关概率统计知识的理解。此外，高斯分布的采样方法有多种，通过展示不同的采样方法在高斯分布上的具体操作以及性能对比，我们会对这些采样方法有更直观的印象。
1700537321
1700537322
知识点
1700537323
1700537324
高斯分布，Box-Muller算法，拒绝采样
1700537325
1700537326
问题 如何对高斯分布进行采样？
1700537327
1700537328
难度：★★★☆☆
1700537329
1700537330
分析与解答
1700537331
1700537332
首先，假设随机变量z服从标准正态分布N(0,1)，令
1700537333
1700537334
x=σ·z+μ ，
1700537335
1700537336
（8.7）
1700537337
1700537338
则x服从均值为 μ、方差为σ2的高斯分布N(μ,σ2)。因此，任意高斯分布都可以由标准正态分布通过拉伸和平移得到，所以这里只考虑标准正态分布的采样。常见的采样方法有逆变换法、拒绝采样、重要性采样、马尔可夫蒙特卡洛采样法等。具体到高斯分布，要如何采样呢？
1700537339
1700537340
如果直接用逆变换法，基本操作步骤为：
1700537341
1700537342
（1）产生[0,1]上的均匀分布随机数u。
1700537343
1700537344
1700537345
（2）令，则z服从标准正态分布。其中erf（·）是高斯误差函数，它是标准正态分布的累积分布函数经过简单平移和拉伸变换后的形式，定义如下
1700537346
1700537347
1700537348
．
1700537349