算法快速模拟
2020-06-01
2192
长期以来，快速有效地生成随机数一直是一个重要的挑战。几个世纪以来，机会游戏依靠掷骰，掷硬币或洗牌来给程序带来一些随机性。20世纪下半叶，计算机开始接管该角色，用于密码学，统计和人工智能以及各种模拟（气候，流行病学，金融等）。
麻省理工学院的研究人员现在已经开发出一种计算机算法，该算法至少在某些任务上可能会以当今速度，准确性和低内存要求的最佳组合来产生随机数。该算法称为快速加载骰子滚轮（FLDR），由MIT研究生Feras Saad，研究科学家Cameron Freer，Martin Rinard教授和首席研究科学家Vikash Mansinghka创建，并将于下周在第23届国际会议上进行介绍。关于人工智能和统计。
简而言之，FLDR是一种计算机程序，可以模拟骰子掷骰以生成随机整数。骰子可以具有任意数量的侧面，并且可以对其进行“加载”或称重，以使某些侧面比其他侧面更容易举起。加载的骰子仍然可以产生随机数（因为无法预先预测哪一侧会出现），但是随机性受到限制，无法满足预设的概率分布。例如，可能使用装好的骰子来模拟棒球比赛的结果。尽管上级球队更有可能获胜，但在某一天，任何一支球队都可能排名最高。
使用FLDR，可以“完美”加载骰子，这意味着它们可以完全达到指定的概率。例如，使用四边模，可以安排东西，使数字1,2,3和4分别准确地分别占23％，34％，17％和26％的时间。
为了模拟具有大量边的装填骰子的掷骰，麻省理工学院的团队首先必须利用一种更简单的随机性来源-一种抛硬币的计算机化（二进制）版本，产生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更有效地利用了随机来源（即“抛硬币”）来延续这种隐喻。此外，在某些情况下，FLDR在生成加载的骰子卷时也比Alias更快。
当然，FLDR仍然是全新的，尚未得到广泛使用。但是其开发人员已经在考虑通过软件和硬件工程来提高其有效性的方法。除了对随机数的普遍需求之外，它们还考虑了特定的应用。Mansinghka建议，FLDR可以提供最大帮助的地方是使所谓的蒙特卡洛模拟和蒙特卡洛推理技术更有效。就像FLDR使用硬币翻转来模拟更复杂的加权多面骰子掷骰一样，Monte Carlo模拟也使用掷骰来生成更复杂的随机数模式。
例如，联合国对地震活动进行模拟，以显示地球上何时何地发生地震，地震或核试验。联合国还进行了蒙特卡洛推断：运行随机模拟，为实际地震数据生成可能的解释。这是通过进行第二系列的蒙特卡洛模拟来进行的，该系列会随机测试基础地震模拟的替代参数，以找到最有可能重现观测数据的参数值。这些参数包含有关可能实际发生地震和核试验的时间和地点的信息。
Mansinghka说：“ Monte Carlo推理可能需要比Monte Carlo模拟多数十万倍的随机数。” “这是FLDR真正可以帮助的一个大瓶颈。蒙特卡罗模拟和推理算法对于概率编程也是至关重要的，概率编程是AI的新兴领域，具有广泛的应用。”
Google研究总监Ryan Rifkin认为FLDR在这方面具有巨大潜力。“蒙特卡洛推理算法对于现代AI工程……以及大规模统计建模至关重要”，未参与此项研究的Rifkin说。“ FLDR是一个非常有前途的发展，它可能会导致加快随机数生成的基本构建模块的速度，并可能帮助Google显着更快，更节能地进行蒙特卡洛推理。”
尽管前途看似光明，但FLDR几乎没有被发现。它的提示首先出现在同一篇麻省理工学院研究人员在1月份的一次研讨会上发表的前一篇论文中，该论文介绍了一种单独的算法。在那项工作中，作者表明，如果为计算机程序分配了预定数量的内存来模拟掷骰子，他们的算法可以确定可能的最小“错误”数量，即与会议相距多近骰子每一侧的指定概率。
如果不预先限制内存，则错误可以减少到零，但是Saad注意到一种零错误的变体，它使用的内存更少，并且几乎一样快。起初，他认为结果可能太琐碎以至于无法理会。但是他向弗里尔提到了这一点，弗里尔向萨德保证说这条路值得追求。FLDR在这方面没有错误，起源于那些不起眼的起源，现在有机会成为随机数生成领域的领先技术。考虑到我们生活在一个很大程度上受随机过程支配的世界中，这不是一件小事，这是一个适用于宇宙中星系分布以及充满活力的掷骰子游戏结果的原理。
