人工智能通识-科普-随机-2

2019-03-06 本文已影响17人 zhyuzh3d

欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】

PRNGs

Pseudo-Random Number Generators,伪随机数生成器。

计算机的随机数生成器有两个常用套路：

第一种，神奇公式法。
就是说有人创造了一个公式，而其他人无法从这个公式计算出的一系列结果数字中找到规律。
什么？不可能找不到规律？只要数字足够多就一定能发现规律？
——圆周率都计算到小数点后数十亿位了，不也是没有找到规律吗？
上帝使用了神奇公式创造了圆周率，我们人类至今还没猜透，也许未来有一天能够猜透，但不是现在。

第二种，列表查找法。
还是圆周率，我们假定它的小数部分是一个无限不循环无规律的数字，这些数字是上帝用神奇公式生成的，虽然我们无法知道那个神奇公式，但我们可以认为圆周率的下一个小数的数字是没规律的，随机的。
然后我们就依次把每个小数作为下一个数字结果返回，这个结果看起来就像是随机的，——假设你不知道圆周率的下一个数字的话。

真随机数字生成器

以上那些都是伪随机。如何才能编写一个真随机程序？

几乎不可能！

也许人的自由意识是个办法，你可能认为你随口说出的数字就是真随机的，但实际并不是那么回事。
如果你连续记录下自己随口说出的1万个数字，然后统计一下其中0、1、2、..8、9每个数字出现的次数，就会发觉很可能相差很大。
但是，如果你统计圆周率小数点1万个数字，就会发觉0到9每个数字出现的概率几乎一样。
这说明圆周率是比你更真的随机。
你的大脑可能受到你自己经验和教育的影响，对某些数字有偏好，而对另一些则不大喜欢。

看来让一个人坐在计算机背后，扮演上帝随口说数字的办法是行不通了。

扔色子也许是个更好的办法，因为色子落地的点数受到太多因素的影响，比如桌面的粗糙、色子形状的粗糙、投掷的角度和力度，甚至构成色子的量子不确定性。
但我相信，如果你扔色子一万次，然后统计一下点数，也很可能是不均匀的，某些数字比如6或者3可能多些。因为毕竟你的力度往往变化不大，把色子扔出去再捡回来的动作区别也不大，只要不足够复杂，人的主观意识就会产生可观测的影响，你可能喜欢某个数字多些，而另一个点数少些，最终也体现在结果上。

除非色子小到量子尺度，以至于色子自身都变得不确定，而且这种量子不确定性质起到了主导作用，那样才能产生真正的随机。

然而，即使在量子尺度的不确定性，也只是我们这个世界的不确定性，就像圆周率在我们的世界无法确定下一位，但在另一个世界它可能只是一个公式算法的结果而已。

线性同余方法（LCG）

Linear congruential generator，线性同余生成器是在各自编程语言中应用最多的伪随机数生成算法。
这种算法也常被称为Multiplicative Congruential Generator (MCG), or Lehmer RNG。

它的算法表达式是：

$X_{n+1}=(aX_n+c) \% m$

这里百分号是取余数的意思，就是10%7等于3，10%4等于2。
$X$ 是一个随机数序列， $a$ 乘以第 $n$ 个数字，再加上 $c$ ，然后除以m，所得余数就是第 $n+1$ 个随机数。
这里 $m$ 是模数modulus； $a$ 是倍增multiplier； $c$ 是increment增量； $X_0$ 是种子数seed。

变成python的代码如下：

import time

def lcg(seed=False):
    if not seed:
        seed=int(time.time())
    a = int(time.time())
    c = int(time.time())
    modulus = time.time()
    for i in range(100):
        seed = (a * seed + c) % modulus
        yield seed/modulus

for itr in lcg():
    print(itr)

这个代码里面使用了时间戳time()做为模数和默认的种子数，每次运行可以得到100个随机数字，在0到1之间均匀分布。

下面是个更简化的可行的PRNGs：

def rd(max=1, seed=False):
    if not seed:
        seed = int(time.time() * time.time())
    return (seed * 48271234 + 877283) % 8923334 / 8923334*max

for i in range(10):
    print(rd(100),'\t',int(rd(100)))

这里利用了时间戳乘方的方法把它放大，然后使用一些比较大的随意数字对它做乘法、加法再取余数。得到结果如下：

真随机性的标准

怎么评判一个随机算法是否足够好，以最大程度模拟了真随机？

可以从以下几个方面考虑：

统计学的均匀分布。最简单说就是随机1万次，所得到的数字在设定范围内均匀分布。比如0~100之间随机1万次，那么应该出现大约100次的99，100次的88。
不可推演。不能从前面若干次的随机数推演出下一个，相反也不能从后面的随机数字推演出前面一个。历史和未来都不可以预测，无规律可寻。
不可重现。不会出现有规律的循环或局部循环的现象。每个随机都是独立的，和时空紧密绑定的。
不能有极限值。也就是说随机的数字不能在开始或结束或者某些情况下，越接近这个情况随机结果也就越接近一个极限值。

其实我们上面的算法都不满足第三条，因为这个程序在同一时间的不同计算机上生成的随机数是一样的。因为只有时间戳是真变量。

要解决时空独立，那么必须在算法中加入每个CPU芯片特有的型号作为变量，才可能做到。

同一CPU不可能在同一时间的不同地点运行随机程序，所以当我们把时间和CPU独有型号数字结合的时候，就能创造出时空独立的随机。

但要满足第2条不可推演就必须借助超越人类认知的真随机数字，比如圆周率。根据时间戳和芯片ID计算出一个数字n，然后取圆周率小数的第n位，作为此时空的随机数字。

这里隐藏了一个疑问，那就是观众知道圆周率的计算方法，或对圆周率的数字了解很多，这样情况会不会对随机性产生影响？实际是不会的，因为圆周率本身就是不可完整推测的，也就是说人类并没有真的掌握圆周率的生成规律，不知道它背后的神奇算法。

这里也隐藏了一个缺陷，就是我们的随机数是有限的，并不能超越我们所知的圆周率数字长度。有限或无限从来就不是问题，因为我们人类大脑根本无法有效处理无限的概念。何况我们计算机很多语言的随机程序计算的数字也只有2的32次方个可能数字，大约40亿个范围，这要比已知的圆周率数字少很多，所以够用了。

关于圆周率，可能这里的说法并不严谨。圆周率当然是可计算的，甚至有数学家发明了直接计算第n位小数的方法。但是，我们还是无法否认，圆周率的小数位的数字看上去都是随机出现的，而且这种随机的纯数字表面并没有规律可言。

欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】

每个人的智能新时代

如果您发现文章错误，请不吝留言指正；
如果您觉得有用，请点喜欢；
如果您觉得很有用，欢迎转载~

END