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

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

均匀分布的采样

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

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

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

其中\equiv为同余号,abm的余数相同,记作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,cm,例如:

\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.png
图中左边的是概率函数,右边的是累积分布函数,可以看出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,也就是说,函数ff ^ { - 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.png

接受/拒绝采样

对于目标分布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.png

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

马尔科夫蒙特卡洛采样

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

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


参考:
<百面机器学习>

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

发表评论