随机数在人工智能的训练过程中占据重要作用,本节的四个随机数算法:

  1. 线性同余生成法
  2. 进位乘数法
  3. 梅森旋转算法
  4. 蒙特卡洛算法

不同于自然界中的真随机数,通过计算机算法生成的随机数都属于伪随机数,也就是虽然结果呈现出随机性,但只要他们初始条件相同,完全可以预测出未来的随机数.
随机数生成算法包含了如下概念:

  1. 种子
  2. 内部状态
  3. 周期

    随机数概念

    种子

    种子决定了随机数算法的初值.如果相同的随机数生成算法的种子相同,那么就会得到相同的随机数序列

    内部状态

    内部状态是生成下一个随机数的依据,如果你知道了内部状态和种子,那就可以预测整个随机数序列.

    周期

    每个随机数的生成都会存在极限,就是随机数序列的长度,超过了这个长度,随机数就会从头开始重复,以此类推
    成熟的随机数生成算法的周期非常长,完全满足了工程所需.

    真随机

    真随机的概念是根据科学发展而进步的,例如混沌系统中收集随机数:
    在三体问题中收集随机数,但是三体问题不能是稳定解.
    在大气扰动中收集随机数,但是大气扰动不能在未来被数学成功建立模型.
    目前有些处理器使用基于量子热效应来收集热辐射信号的方法产生随机数,这种方法是现阶段最可靠的.但是由于性能原因,这种方式产生的随机数速度并没有算法直接生成来的快.

    随机分布

    均匀分布

    在一定区间内尽可能的平均分布而实现整体一致便是均匀分布.
    随机变量X服从在闭区间[a,b]上的均匀分布,记为第四节 随机数生成 - 图1
    对于连续性的X,其概率密度为第四节 随机数生成 - 图2仅在第四节 随机数生成 - 图3成立,其余情况均为0

    均匀分布的期望值和方差

    第四节 随机数生成 - 图4

第四节 随机数生成 - 图5
随机数缩放区间
如果某编程语言的函数rand()提供一个0~1的随机数,可根据如下函数放缩到区间(h,l)中
第四节 随机数生成 - 图6

轮盘模拟

当你需要在三个或者三个以上的类别中做出选择时,就需要用到轮盘模拟.
例如某机器人在行进过程中只有前进/左转/右转三种操作可选.
我们并不希望他们的概率均等,因为机器人前进的时候多,转向时候少.那么就可以将三种情况的概率按照我们的设定放入区间内

  1. 前进 (80%) if(0<x<0.8) then move_forward;
  2. 左转(10%) if(0.8<x<0.9) then move_forward;

  3. 右转(10%) if(0.9

    线性同余生成法

    线性同余并不适用于密码学随机数.因为这种方法的随机数序列会受到时间序列的影响,出现质量问题.
    线性同余算法很简单,是由一个递推式构建的:
    第四节 随机数生成 - 图7
    由此可见,线性同余算法能够生成的序列只取决于m,c,a三者,但是三者如何选取是很重要的.
    GCC编译器的取值为:

    1. m = 2e31;
    2. a = 1103515245;
    3. c = 12345;

    进位乘数法

    为了拉长随机数的周期而实现更加拟真的随机数序列,进位乘数法可以将周期拉长至最低2 的60次方,而最高可达2的两百万次方.
    进位乘数法的特点:

  4. 乘法器的利用率高,在MUL指令中,乘法器的字长通常分为地位和高位,线性同余只是用到了低位,而乘数法通过进位来利用到了乘法器的高位,这样能拓展周期和他自身的长度,还利用了更多了乘法器位数资源.并不会影响效率,这对工程上的适应很重要(但编程语言支持很少)

  5. 乘法器使用多个种子值,而这些种子往往来自于另一些伪随机数算法.

线性同余有模数/乘法因子和增量,乘数法也有模数和乘法因子,但是 没有增量,不同的是,我们需提供r个种子,变量r用以描述延迟概念.
第四节 随机数生成 - 图8
a位乘法因子,b为模数.另外还有一个表示进位的c,进位的方式如下:
第四节 随机数生成 - 图9

梅森旋转算法

梅森旋转算法来自于”算法周期总是一个梅森素数”
对于任意一个素数M:如果满足下式:
第四节 随机数生成 - 图10,就称之为梅森素数.
例如2^5=32
32-1 = 31
31是一个素数,满足等式,也就是一个梅森素数.
需要注意的是梅森素数需要进行移位操作,Java等工作在虚拟机层面不支持移位操作的编程语言无法模拟该算法.
原始梅森素数算法需要保证位变量长度和C语言提供的算法相同.

Box-Muller算法

有些语言并不支持正态分布随机数,因此需要将平均分布转换为正太随机分布.这便是Box-Muller算法的转换目的.

算法步骤

给定一对数:y1 y2
变量useLast用以表示y2是否处于待使用状态.
y1一定是被返回的变量,如果useLast为真,就说明y2处于待使用状态,将y2赋值给y1,返回y1;
如果不是待使用状态,就需要执行转换逻辑:
生成两个在(-1,1)区间的随机数.x1,x2;这点可用rand函数来完成,但rand函数返回的数值是(1,0)的,因此需要进行放缩操作.
然后对x1和x2进行平方再求和,直到这个数小于1.0;
Box-Muller通过储存在x1和x2中的不相干随机数进行计算来得到结果.
防缩因子w也是这两个变量得到的.
应用这个防缩因子就可以得出正太分布的随机数

  1. #include <iostream>
  2. #include <cmath>
  3. #include <ctime>
  4. const int N = 100;
  5. bool useLast = false;
  6. double i_y1,i_y2;
  7. double x1,x2;
  8. double w;
  10. double box_muller()
  11. {
  12.     if(useLast)
  13.     {
  14.         i_y1 = i_y2;
  15.         useLast = false;
  16.     }else
  17.     {
  18.         do{
  19.             x1 = 2.0 * (rand() % (1000) / (double)(1000)) - 1.0;
  20.             x2 = 2.0 * (rand() % (1000) / (double)(1000)) - 1.0;
  21.             w = x1 * x1 + x2 * x2;
  22.         }while(w >= 1.0);
  23.         w = sqrt( (-2.0 * log(w)) / w);
  24.         i_y1 = x1 * w;
  25.         i_y2 = x2 * w;
  26.         useLast = true;
  27.     }
  28.     return i_y1;
  29. }
  31. int main(){
  33. //  srand((unsigned int)time(NULL));
  34.     double X_U_arr[N];
  35.     double X_N_arr[N];
  36.     for(int i = 0;i < N;i++)
  37.     {
  38.         X_N_arr[i] = box_muller();
  39.         X_U_arr[i] = rand() % (1000) / (double)(1000);
  40.     }
  41.     printf("Uniform distribution\n");
  42.     for(int i = 0;i < N;i++)
  43.         printf("%.3lf,",X_U_arr[i]);
  44.     printf("\n\nNormal distribution\n");
  45.     for(int i = 0;i < N;i++)
  46.         printf("%.3lf,",X_N_arr[i]);
  47. }

蒙特卡洛算法

对于圆周率的求值,我们可以用随机采样来对实际值进行估算,也就是用随机数来模拟投针法:
对于一个被限制在切线正方形中的圆,其半径为r,正方形边长为2r,则二者的面积比例为:
第四节 随机数生成 - 图11

  2. pi = 0
  3. tries = 0
  4. success = 0
  5. times = 100000000
  6. while times > 0:
  7.     times -= 1
  8.     x = random.random()
  9.     y = random.random()
  10.     tries += 1
  11.     if x*x + y*y <= 1:
  12.         success += 1
  13.     pi = 4.0 * success / tries
  15. print(pi)
  16. # c++的rand()函数会出现收敛问题

image.png
能收敛到万分位