研究人员距离将概率过程添加到确定性机器更近了一步
一个长期的计算问题-模拟骰子滚动
这是一个看似简单的练习：拿出一个随机的电话号码。连续选择七个数字，以使每个数字具有同等的可能性，因此您选择下一个数字不会影响下一个数字的选择。最有可能的是，这对您不起作用。您不能相信我的话-自1950年代以来进行的研究表明，从数学的角度来看，我们是如何不随机的，甚至没有意识到它。
不要难过。计算机也不会生成随机数。他们不应该-计算机的程序和硬件运行在布尔逻辑上，而不是概率上。 “计算机文化基于确定性，” Vikash Mansinhka说他在麻省理工学院运行一个概率计算项目-并且它几乎出现在每个级别。”
但是，程序员希望创建随机运行的程序-有时任务需要它。多年来，已经开发出了巧妙的算法，尽管它们不生成随机数，但提供了使用和操纵随机性的巧妙而有效的方法。麻省理工学院的Mansinhee小组进行了最近的尝试之一，该小组将在八月份的AI和统计国际会议上展示他们的Fast Loaded Dice Roller或FLDR算法。
简而言之，FLDR使用随机序列来完美模拟作弊骰子（或权重较重的硬币或标记的牌）。数学家说：“他展示了如何将完全随机的抛硬币变成扭曲的抛硬币。”新奥尔良大学的Peter Bierhorst。 Birhorst没有参与这项研究，但他认为FLDR的前提是“令人信服的”。
在玩大富翁游戏或在拉斯维加斯掷骰子游戏中，FLDR不会给您带来优势。但是，它的创建者说，它允许将随机数集成到本机确定性软件或硬件中。纳入这些不确定性将有助于机器做出更像人类的预测，并更好地根据偶然性来模拟事件，例如气候或金融市场。
随机性是一个比听起来更复杂的概念。没有可识别模式的随机数字序列中的每个数字，出现的可能性是相同的。例如，数字π不是随机的，但是据信，按照这种定义，其数字是随机的（数学家称其为“正常”）：从0到9的每个数字出现的次数大约相同。
而且，尽管您可以在Google上找到“随机数生成器”，但绝对不会有机会。当今的处理器，搜索引擎和密码生成器使用的“伪随机”方法对于大多数任务来说“足够好”。数字是使用复杂的公式生成的-但是，从理论上讲，知道该公式可以预测序列。
至少80年来，科学家们一直试图在机器中建立真正的随机性。在此之前，从可靠的老手那里拿出随机数-他们掷骰子，从混合充分的袋子中取出带有数字的球，或使用其他机械设备。 1927年，一位统计学家从一次普查中抽取了数据，编制了一个包含40,000个随机数的表格。
麻省理工学院概率计算项目经理Vikash Mansinkhka
随机数的最早来源是物理机器。英国统计学家莫里斯·乔治·肯德尔（Maurice George Kendall）和伯纳德·巴宾顿·史密斯（Bernard Babington Smith）于1938年发明了第一台随机数发生器。车子放在一个黑暗的房间里，在那里它转动了一个磁盘，分成10个扇区，从0到9编号。当有人不定期地按按钮时，短暂的霓虹灯或火花照亮了磁盘，将其从黑暗中夺走了。只能看到一个数字的冻结图像。后来的机器Ernie在霓虹灯管中使用了噪音。自1957年以来，她一直在英国彩票中挑选中奖号码。
后来，为了寻找真正随机的序列，根据Birhorst的说法，计算机科学家不得不求助于自然现象，例如文物辐射或不可预测的量子系统。他说：“自然界中存在真正无法预测的随机过程，可以利用。” “向左或向右反射的电子无法预先知道它将做什么。”
但是，仅凭机会并不能帮助您。到1940年代后期，物理学家开始生成适合给定概率分布的随机数。这样的工具-NOS多维数据集的理论版本-在实际情况下（例如交通拥堵或化学反应）可以更精确地工作。到1976年，计算机科学先驱Donald Knuth和Andrew Yao提出了一种算法，该算法能够基于随机数序列生成任何加权结果数组的随机样本。 “这是您可以想到的最省时的算法，”领导FLDR的Mansinkhka实验室的研究生Fera Saad说。
萨德说，不幸的是，该算法在计算机科学家中引起了折衷：许多快速运行的应用程序占用大量内存，而占用很少内存的应用程序可能需要很长时间。 Knuth和Yao的算法属于第一类，这使它优雅，但实际使用中却占用大量内存。
然而，萨阿德去年春天提出了一个明智的举动。他意识到，如果立方体数字的权重之和等于2的幂，则该算法在内存和时间上都是有效的。想象一下，对于六面立方体，权重1、2、3、4、5和1被加到从1到6推出数字的概率中。也就是说，推出1的概率是1/16，而2的概率是2/16。结果，权重的总和为16-或2 4-，并且该算法在内存和时间上都非常有效。
Fera Saad，麻省理工学院博士研究生
但是，可以说权重为1、2、3、2、4、2，它们的总和为14。由于14的乘方不是2的幂，因此Knut-Yao算法将需要更多的内存。 Saad意识到可以增加一个额外的权重，因此权重总和为2的幂。在这种情况下，您可以添加一个权重为2的虚拟面孔，然后权重之和为16。如果算法选择了真实面孔，则会记录该值。如果是虚构的，则该值将被丢弃，算法将再次开始。
这是提高FLDR有效性的关键，使其成为功能强大的仿真工具。与原始版本算法所需的大量内存相比，用于额外抛出的额外内存量可以忽略不计。
FLDR使Knuth-Yao算法高效，并提供了扩展其范围的机会。气候变化模拟，作物预测，粒子模拟，金融市场模型和地下核爆炸都取决于以加权概率分布的随机数。同样，随机数是保护通过Internet传输的数据的加密方案的核心。
曼辛卡说，FLDR可以帮助研究人员找到将概率集成到计算机处理器中的方法，他在麻省理工学院的实验室正在这样做。该算法可以帮助改进软件库和新的处理器体系结构，这些体系结构可以生成随机数并有效地使用它们。与我们过去使用的确定性布尔机相比，这将是一个重大变化。
他说：“我们可能有很大的机会将随机性集成到软件和硬件的构建块中。”
也可以看看：