常见的采样方法

均匀分布随机数

• 伪随机数
• 通过离散分布来逼近连续分布
• 线性同余法
  (x_{t+1} = a cdot x_t + c (mod m))
  初始值(x_0)称为随机种子，一般会取系统时间
• 好的线性同余随机数生成器，循环周期要尽可能接近(m)，需要精心挑选合适的(a)和(m)

常见的采样方法

• 给定随机变量的一个取值，可以根据概率密度函数来计算该值对应的概率密度
• 根据概率密度函数提供的概率分布信息来生成随机变量的一个取值，这就是采样

采样策略

• 函数变换法
  如果随机变量(x)和(mu)存在变换关系(mu = varphi(x))，则它们的概率密度函数关系为：

  [p(mu)cdot|varphi^{'}(x)| = p(x) ]

  从目标分布(p(x))中不好采样(x)，可以构造一个变换(u = varphi(x))，使得从变换后的分布(p(mu))中采样(mu)比较容易，这样可以通过先对(mu)进行采样，然后通过反函数(x = varphi^{-1}(mu))来间接得到(x)

  前提是(varphi)的逆函数是好求的

  特别地，在函数变换法中，如果变换关系(varphi(cdot))是(x)的累积分布函数，则得到了逆变换采样(Inverse Transform Sampling)。假设待采样的目标分布的概率密度函数为(p(x))，它的累积分布函数为

  [mu = Phi(x) = int_{-infty}^x p(t)dt ]

  则逆变换采样法需按如下过程进行采样：

  • 从均匀分布(U(0,1))中产生一个随机数(mu_i)
  • 计算(x_i = Phi^{-1}(mu_i))，其中(Phi(cdot))是累积分布函数的逆函数

• 拒绝采样(Rejection Sampling)

  • 又叫接受/拒绝采样(Accept-Reject Sampling)。对于目标分布(p(x))，选取一个容易采样的参考分布(q(x))，使得对于任意(x)都有(p(x) leq M cdot q(x))，则可以按如下过程采样：
    • 从参考分布(q(x))中随机抽取一个样本(x_i)
    • 从均匀分布(U(0, 1))中产生一个随机数(mu_i)
    • 如果(mu_i < frac{p(x_i)}{M q(x_i)})，则接受样本(x_i)；否则拒绝，重新采样
  • (M cdot q(x))是(p(x))的包络函数。包络函数越紧，采样效率越高
  • 改进：自适应拒绝采样(Adaptive Rejection Sampling),在目标分队是对数凹函数时，用多段线性函数来覆盖目标分布的对数(ln p(x))

• 重要性采样

  • 用于计算函数(f(x))在目标分布(p(x))上的积分(函数期望),即
    [E[f] = int f(x) p(x)dx ]

  • 找到一个容易抽样的参考分布(q(x)),并令(w(x) = frac{p(x)}{q(x)})，则有：
    [E[f] = int f(x)w(x)q(x)dx ]
    这里(w(x))可以看作样本(x)的重要性权重
  • 从(q(x))抽取N个样本({x_i})，然后按下式估计(E[f]):
    [E[f]approx hat{E}_N[f] = sum limits_{i=1}^N f(x_i) w(x_i) ]

  • 重要性重采样(Sampling-Importance Re-samping, SIR)
    • 不计算积分，只采样样本
    • 先从(q(x))抽取N个样本，然后按照他们的权重(w(x))进行重新采样

• 如果是高维空间的随机向量，拒绝采样和重要性重采样经常难以寻找到合适的参考分布，采样效率低下，此时应考虑马尔可夫蒙特卡洛采样法