新的MIT随机数算法可以帮助分析从地球气候到金融市场的复杂系统

算法快速模拟一卷加载的骰子

长期以来，快速有效地生成随机数一直是一个重要的挑战。几个世纪以来，机会游戏一直依靠掷骰子，掷硬币或洗牌来给程序带来一些随机性。在20世纪下半叶，计算机开始接管该角色，用于密码学，统计和人工智能中的应用，以及各种模拟（气候，流行病学，金融等）。

麻省理工学院的研究人员现在已经开发出一种计算机算法，该算法可能至少在某些任务上能够以当今速度，准确性和低内存要求的最佳组合来生产出随机数。该算法称为快速加载骰子滚轮（FLDR），由MIT研究生Feras Saad，研究科学家Cameron Freer，Martin Rinard教授和首席研究科学家Vikash Mansinghka创建，并将于下周在第23届国际会议上进行介绍。关于人工智能和统计。

简而言之，FLDR是一种计算机程序，可以模拟骰子掷骰以生成随机整数。骰子可以具有任意数量的侧面，并且可以对其进行“加载”或称重，以使某些侧面比其他侧面更容易举起。加载的骰子仍然可以产生随机数（因为无法预先预测哪一侧会出现），但是随机性受到限制，无法满足预设的概率分布。例如，可能使用装好的骰子来模拟棒球比赛的结果。尽管上级球队更有可能获胜，但在某一天，任何一支球队都可能排名最高。

使用FLDR，可以“完美”加载骰子，这意味着它们可以完全达到指定的概率。例如，使用四面模具，可以安排事情，使数字1,2,3和4分别准确地分别占23％，34％，17％和26％的时间。

一种称为快速加载骰子滚轮（FLDR）的新算法可以模拟骰子滚动以生成随机整数。在这种情况下，骰子可以有任意数量的侧面，并且可以对它们进行“加载”或称重，以使某些侧面比其他侧面更容易举起。

为了模拟具有大量边的骰子的掷骰，麻省理工学院的团队首先必须利用一个更简单的随机性来源-它是抛硬币的计算机化（二进制）版本，产生0或1，每个都有50％的概率。他们的方法的效率（一个关键的设计标准）取决于他们必须利用此随机源的次数（即“掷硬币”的次数）来模拟每个骰子掷骰。

在1976年的一篇具有里程碑意义的论文中，计算机科学家Donald Knuth和Andrew Yao设计了一种算法，该算法可以模拟理论上可获得的最大效率来掷骰子。Saad解释说：“尽管他们的算法在时间上是最有效的，但实际上这没有什么比这更快的了，”在存储该信息所需的空间或计算机内存方面，它是低效的。实际上，所需的内存量成倍增加，具体取决于骰子上边的数量和其他因素。他说，这使Knuth-Yao方法不切实际，除了特殊情况外，尽管它在理论上很重要。

FLDR旨在提高实用性。Saad说：“我们的时间效率几乎一样高，但在内存效率方面却提高了几个数量级。”与Knuth-Yao方法相比，FLDR可以使用多达10,000倍的内存存储空间，而每次操作所花费的时间不超过1.5倍。

目前，FLDR的主要竞争对手是Alias方法，该方法几十年来一直是该领域的主要技术。根据Freer的理论分析，FLDR与Alias相比有一个明显的优势：与Alias相比，它更有效地利用了随机来源-“抛硬币”，以继续这种隐喻。此外，在某些情况下，FLDR在生成加载的骰子卷时也比Alias更快。

当然，FLDR仍然是全新的，尚未得到广泛使用。但是其开发人员已经在考虑通过软件和硬件工程来提高其有效性的方法。除了对随机数的普遍需求之外，它们还考虑了特定的应用。Mansinghka建议，FLDR可以提供最大帮助的地方是使所谓的蒙特卡洛模拟和蒙特卡洛推断技术更有效。正如FLDR使用硬币翻转来模拟更复杂的加权多面骰子掷骰一样，Monte Carlo仿真也使用骰子掷骰生成更复杂的随机数模式。

例如，联合国对地震活动进行模拟，以显示地球上何时何地发生地震，地震或核试验。联合国还进行了蒙特卡洛推论：进行随机模拟，为实际地震数据提供可能的解释。这是通过进行第二系列的蒙特卡洛模拟来进行的，该系列会随机测试基础地震模拟的替代参数，以找到最有可能重现观测数据的参数值。这些参数包含有关可能实际发生地震和核试验的时间和地点的信息。

“蒙特卡洛推论所需要的随机数比蒙特卡洛模拟要多数十万倍，”曼辛格说。“这是FLDR真正可以帮助的一个大瓶颈。蒙特卡罗模拟和推理算法对于概率编程也是至关重要的，概率编程是AI的一个新兴领域，具有广泛的应用。”

Google研究总监Ryan Rifkin认为FLDR在这方面具有巨大潜力。“蒙特卡洛推理算法对于现代AI工程…和大规模统计建模至关重要，”未参与此项研究的Rifkin说。“ FLDR是一个非常有希望的发展，它可能会导致加快随机数生成的基本构建模块的速度，并可能帮助Google显着更快，更节能地进行蒙特卡洛推理。”

尽管FLDR的前途看似光明，但它几乎没有被发现。它的提示首先出现在同一篇麻省理工学院研究人员在1月份的一次研讨会上发表的前一篇论文中，该论文介绍了一种单独的算法。在那项工作中，作者表明，如果为计算机程序分配了预定数量的内存来模拟掷骰子，他们的算法可以确定可能的最小“错误”数量，也就是说，接近会议的距离骰子每一侧的指定概率。

如果不预先限制内存，则错误可以减少到零，但是Saad注意到一种错误为零的变体，它使用的内存少得多，并且速度差不多。起初，他认为结果可能太琐碎了，以至于无法理会。但是他向弗里尔提到了这一点，弗里尔向萨德保证说这条路值得追求。FLDR在这方面没有错误，起源于那些不起眼的起源，现在有机会成为随机数生成领域的领先技术。考虑到我们生活在一个很大程度上由随机过程控制的世界中，这并不是一件小事，这是一个原理，适用于宇宙中星系的分布以及充满活力的掷骰子游戏的结果。