1700537200
百面机器学习：算法工程师带你去面试 [:1700532214]
1700537201
百面机器学习：算法工程师带你去面试 03 常见的采样方法
1700537202
1700537203
1700537204
1700537205
场景描述
1700537206
1700537207
对于一个随机变量，通常用概率密度函数来刻画该变量的概率分布特性。具体来说，给定随机变量的一个取值，可以根据概率密度函数来计算该值对应的概率（密度）。反过来，也可以根据概率密度函数提供的概率分布信息来生成随机变量的一个取值，这就是采样。因此，从某种意义上来说，采样是概率密度函数的逆向应用。与根据概率密度函数计算样本点对应的概率值不同，采样过程往往没有那么直接，通常需要根据待采样分布的具体特点来选择合适的采样策略。
1700537208
1700537209
知识点
1700537210
1700537211
逆变换采样，拒绝采样，重要性采样
1700537212
1700537213
问题 抛开那些针对特定分布而精心设计的采样方法，说一些你所知道的通用采样方法或采样策略，简单描述它们的主要思想以及具体操作步骤。
1700537214
1700537215
难度：★★★☆☆
1700537216
1700537217
分析与解答
1700537218
1700537219
几乎所有的采样方法都是以均匀分布随机数作为基本操作。均匀分布随机数一般用线性同余法来产生，上一小节有具体介绍，这里不再赘述。
1700537220
1700537221
1700537222
首先假设已经可以生成[0,1]上的均匀分布随机数。对于一些简单的分布，可以直接用均匀采样的一些扩展方法来产生样本点，比如有限离散分布可以用轮盘赌算法来采样。然而，很多分布一般不好直接进行采样，可以考虑函数变换法。一般地，如果随机变量x和u存在变换关系，则它们的概率密度函数有如下关系：
1700537223
1700537224
1700537225
p(u)||=p(x) ．
1700537226
1700537227
（8.2）
1700537228
1700537229
1700537230
1700537231
1700537232
因此，如果从目标分布p(x)中不好采样x，可以构造一个变换，使得从变换后的分布p(u)中采样u比较容易，这样可以通过先对u进行采样然后通过反函数来间接得到x。如果是高维空间的随机向量，则对应Jacobian行列式。
1700537233
1700537234
特别地，在函数变换法中，如果变换关系φ(·)是x的累积分布函数的话，则得到所谓的逆变换采样（Inverse Transform Sampling）。假设待采样的目标分布的概率密度函数为p(x)，它的累积分布函数为
1700537235
1700537236
1700537237
，
1700537238
1700537239
（8.3）
1700537240
1700537241
则逆变换采样法按如下过程进行采样：
1700537242
1700537243
（1）从均匀分布U(0,1)产生一个随机数ui；
1700537244
1700537245
1700537246
1700537247
（2）计算，其中是累积分布函数的逆函数。
1700537248
1700537249
根据式（8.2）和式（8.3），上述采样过程得到的xi服从p(x)分布。图8.2是逆变换采样法的示意图。