Created by potrace 1.13, written by Peter Selinger 2001-2015

机器学习中常见的采样方法

日常编程的过程中,经常使用的随机数,其实就是对均匀分布的采样.有可能你还用过服从正态分布的随机数,就是对正态分布的采样.

在机器学习中,还会对更多的分布进行采样,从而处理一些复杂的问题.本文来讨论一下机器学习中主流的采样方法.

均匀分布的采样

首先需要明确的是,计算机程序都是确定性的,因此并不能产生真正意义上的随机数,只能产生伪随机数.另外由于计算机的存储和计算单元智能处理离散状态值,因此也不能产生连续均匀分布随机数,只能通过离散分布来逼近连续分布.

一般可采用线性同余法来生成离散均匀分布伪随机数,计算公式为:

x_{t+1} \equiv ax_t+c \pmod{m}

其中 \equiv 为同余号, a 和 b 对 m 的余数相同,记作 a\equiv b \pmod{m} .例如100和60除以8的余数相同。可以写成 100\equiv60 \pmod{8} ,数论相关的书中就经常把 a \bmod 3 = 1 写作 a\equiv 1\pmod{3} ,关于更多同余的性质可以参考同余运算及其基本性质,将这种记法思想运用到线性同余法可以得到如下递推公式:

x_{t+1} = (ax_t+c) \bmod{m}

根据当前生成的随机数 x_t 来进行适当变换,进而产生下一次的随机数 x_{t+1} .初始值 x_0 称为随机种子.上式可得到区间 [0,m-1] 上的随机数,用 x_t 除以 m 即可.

此外,该算法最大周期为m,要使其达到最大周期需要精心挑选 a , c 和 m ,例如:

\left\{ \begin{array} { l } { m = 2 ^ { 31 } - 1 } \\ { a = 1103515245 } \\ { c = 12345 } \end{array} \right.

想要真正的随机数可以通过自然界的物理产生,比如放射性物质的衰变,温度,气流的扰动等.有一些网站可以提供基于大自然的随机现象的随机数,有兴趣的读者可以尝试一下.

下面是线性同余法的编程实现:

x = {}

x[0] = int(time.time()); # 以当前时间作为种子

m = (1 << 31) -1; # 2^31 -1
a = 1103515245;
b = 12345;

for i in range(1,100):
    x[i] = ( a * x[i-1] + b ) % m;
    print(x[i]/m)

累积分布函数

累积分布函数，又叫分布函数，是概率密度函数的积分,一般以大写“CDF”（Cumulative Distribution Function）标记。

image

图中左边的是概率函数,右边的是累积分布函数,可以看出 F_x 的值就是 P_x 的面积.

反函数

设函数 y=f(x) 的定义域是 D ，值域是 f(D) 。如果对于值域 f(D) 中的每一个 y ，在 D 中有且只有一个 x 使得 g(y)=x ，则按此对应法则得到了一个定义在 f(D) 上的函数，并把该函数称为函数 y=f(x) 的反函数，记为

x = f ^ { - 1 } ( y ) , y \in f ( D )

由该定义可以很快得出函数 f 的定义域 D 和值域 f(D) 恰好就是反函数 f ^ { - 1 } 的值域和定义域，并且 f ^ { - 1 } 的反函数就是 f ，也就是说，函数 f 和 f ^ { - 1 } 互为反函数.

逆变换采样法

上文介绍了均匀分布的采样,但是如何采样非均匀分布呢?这里介绍一种方法将区间 [0, 1] 上的均匀分布变换到其他的分布.

假设 X 为一个连续随机变量，其累积分布函数为 F_{X} 。此时，随机变量 Y=F_{X}(X) 服从区间 [0, 1] 上的均匀分布。逆变换采样即是将该过程反过来进行：首先对于随机变量 Y ，我们从0至1中随机均匀抽取一个数 u 。之后，由于随机变量 F_{X}^{-1}(Y) 与 X 有着相同的分布， x=F_{X}^{-1}(u) 即可看作是从分布 F_{X} 中生成的随机样本。

若待采样的目标分布的累积分布函数的逆函数无法求解或者不容易计算,则不适用于逆变换采样法.

image

接受/拒绝采样

对于目标分布 p(z) ,选取一个容易采样的参考分布 q(z) ,使得对于任意 z 都有 p ( z ) \leqslant k \cdot q ( z ) ,则可以按如下过程采用:

  1. 从参考分布 q(z) 中随机抽取一个样本 z_i
  2. 从均匀分布 U(0,1) 产生一个随机数 u_i
  3. 如果 u _ { i } < \frac { p \left( z _ { i } \right) } { k q \left( z _ { i } \right) } ,则接受样本 z_i ;否则拒绝,重新进行步骤1~3,直到新产生的样本 z_i 被接受.

image

拒绝采用的关键是为目标分布 p(z) 选取一个合适的包络网络函数 k\cdot q ( z ) :包络函数越紧,每次采样时样本被接受的概率越大,采样效率越高.

马尔科夫蒙特卡洛采样

在实际应用中,如果是高维随机变量,拒绝采用经常难以寻找到合适的参考分布,采样效率低下(样本的接受概率小),此时可以考虑马尔科夫蒙特卡洛采样.

之前转载过一篇文章MCMC和Gibbs Sampling,读者可以参考这篇文章了解马尔科夫蒙特卡洛采样的详细内容.

参考:
<百面机器学习>

posted @ 2019-01-22 14:55:16
评论加载中...
发表评论