@ 2020.07.13 , 23:54

MIT提出了用随机数生成随机数的计算机算法

众所周知,计算机无法制造出随机性,它们也不应该:计算机软件和硬件运行在布尔逻辑,而非概率上。

目前,我们使用的真随机数据,一般来自系统从物理环境中采集到的“随机噪音”。

但是计算机科学家想要可以处理随机性的程序,因为那有时候是解决问题所必须的。多年来,有些公司开发出新颖的算法,尽管它们本身不会生成随机数,但却提供了巧妙而有效的方式来使用和操纵随机性。8月份,在线国际人工智能与统计会议上,麻省理工学院的Mansinghka小组公布了他们的最新成果之一:提出了被称为“快速加载的骰子滚轮”(FLDR)的算法。

简而言之,FLDR使用随机序列完美地模拟了加载模具的滚动。“它显示了如何将完全公平的抛硬币演变成有偏差的抛硬币,”新奥尔良大学的数学家彼得·比尔霍斯特说。

FLDR无助于分析金融市场的起落,也不会让您在拉斯维加斯占有优势。但是它的创造者说,它提出了一种将随机数集成到软件和硬件中的方法,这些软件和硬件本身却都遵循确定性的规则。纳入不确定性有助于机器做出人性化的预测,并更好地模拟诸如气候或金融市场等概率现象。

随机性是一个比看起来棘手的概念。在没有可识别模式的随机数序列中,每个数字都有相同的出现概率。例如,Pi本身不是一个随机数,但是Pi的各位数字则被认为是随机的(数学家称之为“正则”):从0到9的每个整数都具有相同的出现频次。

即使您可以用Google的“随机数生成器”,也无法获得纯粹的随机性。当今的处理器,搜索引擎和密码生成器使用的“伪随机”方法对大多数用途而言都足够好用。它们来自复杂的生成公式,但是从理论上讲,如果您知道该公式,则可以预测之后的序列。

科学家将物理随机性植入机器的尝试,至少已有80年的历史。(在此之前,随机数来自掷骰子,从混匀的袋子中拾取的编号球或其他机械行为。1927年,统计学家对人口普查数据进行采样,从而得到了有40000个随机数字的工具手册。)

早期的随机数来源是物理过程。第一台产生随机数的机器是英国统计学家莫里斯·乔治·肯德尔(Maurice George Kendall)和伯纳德·巴宾顿·史密斯(Bernard Babington Smith)的发明。该机器被放置在一个黑暗的房间里,在那里,它旋转一个磁盘,将磁盘分成10个相等的楔形块(标记为0到9)。当某人以不规则的间隔轻敲按键时,短暂的霓虹灯或火花将照亮磁盘,使其看起来像定格,只有一个数字可见。后来,另一台名为Ernie的随机数机器改用氖管中的信号噪声。从1957年开始,英国彩票系统用它来开出中奖号码。

比尔霍斯特说,最近,为了得到真正的随机序列,计算机科学家必须研究自然现象,如宇宙背景辐射或量子系统的不可预测行为。他说:“自然界中存在可以利用的随机过程,这确实是不可预测的。向左或向右的电子甚至事先也不知道自己将要做什么。”

到1940年代后期,物理学家开始生成随机数以适应给定的概率分布。这样的工具可以更准确地模拟现实情况,例如交通物流或化学反应。1976年,计算机科学家高德纳(Donald Knuth)和姚期智(Andrew Yao)提出了一种算法,该算法可用一串随机数生成任何加权结果数组的随机采样。曼辛卡(Mansinghka)实验室的博士生Feras Saad说:“这是有史以来最省时的算法。”

不幸的是,萨阿德(Saad)说,不存在完美的算法,这对计算机科学家而言是众所周知的常识:许多运行速度很快的应用程序会占用大量内存,而占用内存少的应用程序则可能需要较长的运行时间。 Knuth和Yao的算法属于第一类,优雅,但在任何时候都会占用大量内存。

但是去年春天,萨阿德发现了一个聪明的解决方法。他首先意识到,当芯片上的权重加起来等于2的幂时,该算法在时间和内存上都是有效的。因此,对于六面骰子,假设将数字1到6滚动几率的加权分别为1、2、3、4、5和1。这意味着,如1的概率为1/16,滚动2的概率为2/16。由于权重的总和为16=2^4,因此针对该系统的算法在时间和内存上都很有效。

但是,假设权重取值为1、2、3、2、4、2,总和为14。由于14的乘方不是2的幂,因此Knuth-Yao算法需要更多的内存。 萨阿德意识到他可以添加一个额外的权重,这样总能令总和为2的幂次。就像是在6面骰子上,硬加上一个面,变成7面骰子。在这种情况下,如果最终“摇出”了人为添加的那一面,则返回值被丢弃,重新运行算法。

这是提高FLDR效率的关键,使之成为强大的工具:与原版需要的大量内存相比,添加额外权重所必须占用的额外内存量很小。

FLDR使Knuth-Yao算法高效,并提出了可被广泛应用的方法。气候变化建模,作物产量预测,模拟粒子行为,金融市场模型,甚至是核武器地下实验,都取决于加权概率分布中的随机数。

曼辛卡说,FLDR还可帮助研究人员找到将概率整合到计算机处理器中的方法,这是他在麻省理工学院实验室工作的重点。这将与我们过去使用的确定性布尔型计算机大相径庭。

本文译自 quantamagazine,由 majer 编辑发布。

支付宝打赏 [x]
您的大名: 打赏金额:
赞一个 (13)