专利名称：组合的随机性逻辑的制作方法
组合的随机性逻辑
背景技术：
很多计算问题可以被归类为确定性(deterministic)问题或随机性(stochastic)问
题。一般，在确定性问题中，问题的“答案”或者问题的解答的下一个状态是可以基于 输入值和问题的当前状态确定地计算出来的。一般，在随机性问题中，问题的“答案” 或者问题的解答的下一个状态是不确定的，并且是根据概率分布来定义的。当多个可能事件中的任意一个事件可能已经生成了所观察到的场景时，通常在 现实世界中发生的一类随机性问题出现了。可以收集有关存在的场景的数据，并且可以 使用该数据来计算所观察到的场景由可能事件中的每一个事件导致的概率。基于所确定 的概率，可以做出判决。例如，可以基于最可能的事件实际导致了场景的出现的假设而 做出判决。当然，在更复杂的场景中，判决可以通过其他途径做出，诸如，基于概率对 特定的判决将导致好的还是不好的结果的预期进行评估。图像分析是包括随机性问题的领域的示例。在一个立体视觉问题中，两个不同 的图像可以由位置相近的两个数字摄像机生成(诸如，当针对机器人技术问题对人眼进 行近似时)。期望基于图像本身来确定到图像中的特定物体的距离。每个立体图像代表 了对于从物体传播到摄像机的光的测量。由于在光从物体反射出来时将在可以预测的路 径中传播，所以反射光的物体的位置似乎可以被确定地计算出来。然而，实际上，很多 因素会影响在摄像机处测量出来的实际的光。物体的形状、大小和表面性质以及光源的 位置、强度和其他性质可以影响测量出的结果。所以，距离摄像机不同距离处的大量不 同物体中的任意一个物体可以生成相同或者类似的测量值。因此，当立体图像分析被当作随机性问题时，计算出的是特定位置中的特定物 体导致测量的图像产生的概率。此数据例如可以被用来引导使用立体视觉系统的机器 人。如同最可能的物体实际存在一样，机器人的控制算法可以简单地对通过图像的随机 性分析所提供的数据进行反应。更复杂的控制算法可以引导机器人最大化机器人将不受 物体的困扰而到达它希望的目的地的预期，或者最小化机器人将由于物体的碰撞而被损 坏的预期。文本分析是随机性问题的另一个示例给定文档的文本中的一组单词，可能期 望识别出文档的主题。文档中的该组单词定义了由大量事件中的任意一个事件创建的场 景。具体地，文档可能是关于大量主题中的任意一个主题的。类似地，如果文档分析的 要点在于确定作者的观点，则大量观点中的任意一个观点将会导致在文档中被找出的这 些单词。当被当作随机性问题时，可以确定与诸如文档描述特定主题或者作者赞成特定 观点之类的这些事件相关联的概率。这些概率然后可以被用来判断诸如是否响应于特定 的搜索查询而返回文档或者如何对文档编目录等等。
其他问题类似地遵循这种模式并且可以通过确定可能导致特定观察到的场景出 现的事件的概率来解决。这些问题一般是以条件概率密度函数为特征的。条件概率密度 函数定义了一组事件中假设特定场景存在的事件的概率。根据告知什么场景存在的观察 数据以及概率密度函数，该组事件中每个事件导致所观察的场景出现的概率可以被计算出来。当期望确定定义场景的变量的值，但是这些变量的值具有随机成分时，第二种 随机性问题出现。这可能在变量不能被直接观察出来的很多情况中出现，例如，当它们 描述所关注的化学系统的微观结构时，或者当它们描述生物、文本或者人口统计数据的 聚类时。在所有这些设置中，尽管变量不能被确定地指定，但是可以根据概率分布来对 它们进行描述。通过根据概率分布来选择值，典型值可以被获取用于抽查或者用在解决 其他更大的随机性问题中。当理论上可以但是实际上很难计算场景中的一些参数值时，第三种随机性问题 出现。如果场景可以根据为实际的参数值分配高概率的概率分布来描述，则根据概率来 选择值将导致实际值的良好近似。广泛使用的Monte Carlo近似技术提供了这种随机性问 题的示例的丰富来源。这些种类的问题中的每种问题的共同点在于它们都涉及到根据概率分布来生成 一个或多个样本。通常，这种处理比较复杂并且不能手工或者靠脑力完成；因此，计算 机是解决随机性问题所必需的。使用常规计算机来解决随机性问题的一种传统方法是确定在概率分布下可能的 一组可能事件，然后计算每个潜在的事件的概率。在立体视觉问题的背景下，这可能包 括识别到物体的所有潜在的距离，并且计算每个距离是正确距离的概率。这些概率一般是高度精确地计算出来的，以便保它们紧密地近似实际概率。因 此，当随机性问题被近似为确定性问题时，可以使用64比特的浮点处理来计算，从而使 得每个事件发生(或者每个输出为“正确”输出的概率)的概率可以被以64比特的精确 度计算并存储。
发明内容
申请人:已经认识并意识到，用于计算解决随机性问题的当前方法存在很多缺 点。本文中描述了各种可以被独立使用也可以被结合使用来解决随机性问题的各种原理 和技术。这些原理可以被用来创建和/或操作根据模拟随机性问题的概率分布函数来随 机地生成样本的随机性电路。可以操作这种电路基于代表需要解决随机性问题的场景的 数据来生成这种样本流。在一些情况下，所生成的样本可以本身就是对于随机性问题的解答。例如， 随机性电路被配置为根据用于确定典型值的概率分布来生成样本，或者随机性电路被配 置为根据为将要解决问题的答案附于高概率的概率分布来生成采样的情况。在其他情况 下，所生成的样本流可以被用在解决随机性问题中。例如，定义可能的事件/输出的样 本的出现频率可以被用来计算这些事件在场景中的发生概率；在一些情况下，潜在解答 的可能性被使用。这些概率可以像在常规系统中那样被用来解决随机性问题，诸如通过 确定潜在事件或者一组潜在事件并且作用于该事件或者该组事件。在一个实施例中，提供了一种设备。该设备包括零个以上输入端子；至少一 个输出端子，从该至少一个输出端子输出从以零个以上输入端子上接收的输入为条件的 总体条件概率分布得出的输出样本；以及多个随机性支电路。每个随机性支电路包括零 个以上输入次端子以及至少一个输出次端子，并且被配置为根据以该零个以上输入次端子上接收的输入为条件的条件概率分布、从它的至少一个输出次端子生成样本。在该设 备中，多个随机性支电路被相互连接，以形成根据总体条件概率分布生成样本的随机性 电路。多个随机性支电路中的每一个至少部分地基于条件概率分布和随机性的来源而生 成样本。在该设备的一些实现方式中，总体概率分布是以多个随机性支电路的条件概率 分布为基础的联合概率分布。由多个随机性支电路中的每一个随机性支电路生成的样本 可以在至少一个输出端子上被输出，以根据联合概率分布生成样本；或者由多个随机性 支电路的子集生成的样本可以在至少一个输出端子上被输出，以根据联合概率分布的边 缘联合概率分布生成样本；或者任何其他适当的样本可以被生成。在另一个实施例中，提供了一种包括随机性电路的设备。该随机性电路包括零 个以上输入端子和至少一个输出端子，并且根据以该零个以上输入端子上提供的输入数 据为条件的条件概率分布、在至少一个输出线上生成样本。随机性电路生成样本至少部 分地基于条件概率分布和随机性的来源。在另外的实施例中，提供了一种操作随机性电路以根据总体条件概率分布生成 样本的方法，其中总体条件概率分布与多个条件概率亚分布有关。该方法包括同时操 作两个以上随机性支电路，从而使得每个随机性支电路根据条件概率亚分布生成样本。 同时操作包括在第一迭代期间从第一随机性支电路生成第一样本，第一样本是根据第 一条件概率分布生成的；在第二迭代期间从第二随机性支电路生成第二样本，第二样本 是根据以第一样本为条件的第二条件概率分布生成的。同时操作还包括在第二迭代期 间从第一随机性支电路生成下一个样本。该方法还包括从输出支电路生成作为从总体条 件概率分布得出的样本的样本。前述是本发明的非限制性概要，并且本发明由所附的权利要求来限定。
附图不是按比例画出的。在附图中，不同附图中示出的每个相同或者基本相同 的部件由相似的标号表示。为了清楚，没有在每个附图中标出全部部件。在附图中图1示出了用于操作随机数字电路以根据所关注的概率分布生成样本的示例性 处理的流程图；图2是包括解决随机性问题的随机部件的示例性计算装置的框图；图3A是随机数字电路的说明性实现方式的框图；图3B是通过随机性支电路的互相连接实现的随机性电路的框图；图4A是根据Bernoulli概率分布来生成样本的一种可能的随机性电路元件的框 图；图4B是示出图4A中所示的随机性电路元件的输出的概率分布的图表；图5A、图5B和图5C是利用Bernoulli分布进行操作的随机性电路元件的三种可 能的不同数字实现方式的示意图；图6A、图6B和图6C是两个随机性电路元件可以被如何相互连接以产生根据这 两个电路元件的联合分布来生成样本的随机性支电路的框图；图7A是包括随机性电路元件和确定性加法器的随机性支电路的框图，其根据由这些元件的 操作和它们的相互连接定义的概率分布来生成输出；图7B是图7A的随机性支电路的替代实现方式的框图；图8A是具有随机性电路元件和确定性电路元件的随机性支电路的框图，其中该 随机性电路元件和确定性电路元件被以反馈环的形式连接，以实现随机有限状态机；图9是用于实现随机采样算法的电路的高级框图；图10是可以用来执行拒绝性(rejection)采样算法的示例性电路的框图；图11是可以用来执行重要性(importance)采样算法的示例性电路的框图；图12是可以用来执行Metropolis-Hastings采样算法的示例性电路的框图；图13A、图13B、图13C和图13D示出了可以用来实现用于图像处理应用的 Gibbs采样算法的示例性随机数字电路的框图；图14是可以被实现用于提供对于图像处理问题的潜在解答并可以使用图13A、 图13B、图13C和图13D的随机数字电路实现的示例性随机加速器的框图；图15是既包括确定性计算元件也包括随机计算元件的计算装置的框图；以及图16是可以被用来实现本文中描述的随机性电路的现场可编程门阵列(FPGA) 的框图。
具体实施例方式申请人:已经认识并且意识到，电子地解决随机性问题的传统方法由于它们使用 确定性计算机而固有地受到限制。结果，这些解答基于对随机处理的确定性近似。这种 确定性解答往往使用高度精确的浮点算法。这种近似可能需要大量的时间和/或处理资 源，这是不可接受或者非常低效的。例如，随机性问题的确定性近似可以包括首先确定可能会产生一组观察数据 的每个潜在事件，然后在做出判决之前确定它们发生的可能性。对于给定问题，潜在事 件的数目可能非常巨大，并且其可能需要花费很多时间来计算所有事件的概率。当场景随时间改变时(例如，当输入发生变化或者被改进时)，有可能必须重新 计算这些概率。因为运算以一定精度(通常为64比特)来执行，所以每个计算都可能要 花费大量时间和处理资源。申请人已经意识到，除了增大执行每个计算所必须的处理资 源和时间的量以外，这种精确度不是必须的，因为随机性问题固有地具有一定程度的随 机性和不确定性。一般，问题中固有的不确定性的量遮蔽了用在这些问题的计算近似中 的高精确度，从而使得在解决随机性问题的过程中时间和空间被不必要地使用。申请人:已经意识到，由于用来执行这些计算的确定性电路的特性(它们需要清 楚定义的输入、输出和状态)，很多时间和处理资源被浪费。申请人还认识到了由本质上 随机且可以被用来根据概率分布而不是根据特定输入给出的特定输出来生成(和产生作 为输出的)样本的电路提供的优点。通过以一定程度的随机性进行操作并且从概率分布 产生不确定的概率性样本，这些电路可以被用来根据概率分布生成样本，从而被用来解 决随机性问题。另外，申请人还认识并意识到，可以通过随机逻辑元件的相互连接来开发本质 上随机的电路，这些随机逻辑元件中的每一个自身根据条件概率分布进行操作。通过以 这种方式表现更大的问题，提出问题的任务可以被简化，从而避免了计算将所观察出的数据与所关注的一组事件相关联的总体条件概率分布的需要。另外，得出的随机性电路 具有可以并行操作的部件，从而减少了解决随机性问题所需的时间。随机数字电路可以被用来生成与所关注的问题有关的概率分布，并可以被用来 根据这些概率分布生成样本。使用这些电路，可以根据概率分布高效地生成样本。结 果，对于随机性问题的解答可以被生成，并可以被用来快速并高效地针对随机性问题做 出判决，从而大大增加了解决随机性问题的潜在的可适用性。因此，在此公开了用于使用随机数字电路来根据所关注的分布生成样本的各种 技术，以及用于创建、结合以及使用随机数字电路来模拟并采样在产生对于随机性问题 的解答中有用的所关注的概率分布的设计模式。由随机数字电路产生的输出可以是任何 适当的格式，包括根据与场景相关联的条件概率密度函数表示事件的一个或多个样本、 基于条件概率分布函数计算出的一个或多个事件的概率或者条件概率分布函数。因此， 在一些实现方式中，可以输出单个样本，而在其他实现方式中，随时间可以输出多个样 本。在对多个样本进行操作的实现方式中，在一些情况下，样本可以被汇聚在一起，并 且与这些样本相关联的概率可以被计算出来。这些形式或者其他适当形式的输出然后可 以被用来以任何适当的方式来解决随机性问题，包括使用在随机系统作出判决的领域中 已知的技术。与 使用高精度浮点算法的常规系统相比，根据这里描述的原理进行操作的随机 性电路可以根据概率分布更高效地计算样本。例如，当使用随机性电路时，一般不必 计算所有可能事件的概率来解决随机性问题。而是，由于从随机样本估计各概率的速度 一致，所以对于随机性问题的有意义的解答是可以使用相对较小量的样本来频繁获取得 的。所以，当使用根据条件概率分布来生成样本的随机性电路时，可以针对每个最可能 的事件快速计算出多个可能事件的概率。另外，由于概率可以基于多个样本的汇聚结果 来确定，所以计算每个样本所需要的精确度比较�。佣档土硕杂诟〉闼惴ɑ蛘咂渌� 计算昂贵的技术的需求。随机数字电路可以以任何适当的方式实现来生成样本(下面描述随机数字电路 的示例)。这些电路可以被实现为在它们的输出中引入随机性，从而使得这些电路接收输 入并且基于输入来根据条件概率分布得出代表样本的输出。换言之，在本发明的一些实 施例中，随机数字电路的输出可以是根据概率分布P(EventAnput)(由特定输出代表的事 件引起特定输入的概率)得出的样本。按照以上给出的说明性示例中的一个示例，当被应用于立体视觉问题时，由随 机数字电路产生的样本(其可能导致描述观察对象的输入(例如，输入图像数据))可以 代表到特定对象的距离。在一些实现方式中，这些样本可以被处理以生成在决策中使用 的概率。例如，这种数据可以描述每个可能的距离实际引起所观察到的图像的确定性 (即，概率)。随机性电路可以使用任何适当的电路构建技术来实现。用在构建确定性数字逻 辑中的设计技术可以被使用。特别地，用于制造半导体芯片的已知处理可以被用来制造 随机性电路。类似地，已知的设计工具可以被使用。例如，可以使用可编程逻辑装置 (诸如，现场可编程门阵列(FPGA))来实现随机性电路。替代地，专用集成电路(ASIC) 设计技术可以被使用。但是，诸如用于分子/生物或者DNA计算机的其他技术也可以被使用。但是，随机数字电路与传统数字电路的不同在于其将对一些随机性的来源进行 操作。任何适当的随机性的来源可以被使用。例如，随机性电路可以从其固有设计中找 出一些固有的随机性，诸如电子电路中的轨迹线上的瞬间可变电荷或者用于分子/生物 或者DNA计算机的分子结构的可变性。作为另一个示例，一个或多个随机或者伪随机数 生成器可以被使用，诸如传统的伪随机数生成器。众所周知，伪随机数生成器可以被实 现为提供不包括可识别模式的比特的特定长度的比特流的电路。当比特流的长度大于诸 如生成随机样本的持续时间之类的目标间隔(interval ofinterest)时，伪随机数生成器的输 出可以被认为是随机的。但是，也可以使用其他的随机性的来源，因为本发明的实施例 不限于此。随机性电路可以被单独使用，也可以被以任何适当的方式与其他随机性电路和/ 或确定性电路结合使用以形成能够提供对于任何适当的随机性问题的解答的随机机器或 者处理器。例如，随机性电路可以被用作被定义用于解决特定的随机性问题的随机处理 器的部分。随机处理器可以接受代表对于特定场景的观察数据的输入，并且可以生成适 用于该场景的判决。但是在一些实施例中，随机性电路可以被用作更大的计算环境的一部分，例 如，当被实现为用于确定性处理器的协同处理器时，随机性电路是确定性计算机的一部 分。在一些这样的实现方式中，随机协同处理器可以根据概率分布函数提供样本流或者 样本，或者在其他实现方式中，随机处理器可以输出与随机性问题有关的某些事件的概 率(即，解答为正确解答的可能性)。这些样本和/或概率可以被确定性处理器用在决策 中。随机处理器或协同处理器可以通过包括根据与特定问题相关联的条件概率分布 函数生成样本的随机性电路而适用于解决特定的随机性问题。随机处理器或者协同处理 器可以具有固定的配置，或者在可编程电路被用来实现随机性电路的实施例中，可以被 配置为可用在不同时间解决不同问题。在一些情况下，随机数字电路可以使用多个随机性电路元件来实现，其中每个 随机性电路元件根据概率分布函数进行操作。这些随机性电路元件可以使用常规的确定 性逻辑设计中使用的技术和电路元件来相互连接。这些电路元件中的一些或者全部可以 同时进行操作，从而可以进一步减少解决随机性问题所需的时间。这种并行操作可以使 用例如寄存器、锁存以及常规的数字逻辑电路中用于提供流水线或者其他形式的并行操 作的已知的其他电路元件来实现。但是，引起并行电路操作的任何适当设计都可以被使 用。可以在随机性电路元件之间进行互连，以实现与要解决的随机性问题相关联的 总体条件概率分布。为了帮助创建这种随机性电路，已经识别出了在用于解决很多类型 的问题的随机性电路的设计中出现的一些随机设计模式。实现这些设计模式的随机性电 路元件的互连可以被定义。当解决特定问题时，随机性电路可以使用这些支电路来构建。随机性电路可以被构建在诸如现场可编程门阵列之类的可编程装置中。被定义 用于解决特定的随机性问题的随机处理器可以使用这种FPGA来实现。随机处理器可以完全解决随机性问题。在一些实施例中，随机处理器可以被用作更大的计算环境中的一 部分，例如，随机处理器是确定性计算机的部件。随机处理器可适用于解决确定性计算 机的随机性问题-或者可以被配置为解决确定性计算机的一个或多个随机性问题-从而 使得随机处理器可以作为确定性处理器的协同处理器进行操作。在一些这样的实现方式 中，随机处理器可以根据概率分布函数提供样本流，或者在其他实现方式中，随机处理 器可以输出与随机性问题有关的某些事件的概率(即，解答为正确的解答的可能性)。因此，除非被另外指定，当在这里提及“随机数字电路”时，应该被理解为其 可以等同地指代一个或多个随机性电路元件、随机性支电路、随机性电路和/或随机性 处理器或者可以体现在此描述的原理的任何其他方式。还应该理解，尽管下面描述了随 机性数字电路的说明性类别-包括这四种或者其他-本发明的实施例不限于以任何特定的 方式实现或者被实现为任何(一种或多种)特定类型的电路。图1示出了根据在此描述的原理的用于使用随机性电路来解决随机性问题的处 理的一个示例。为了容易理解本发明的一些实施例的操作，示出了图1的处理，但是图1 的处理不能表现本发明的所有实施例的操作的特征。因此，应该理解，图1的处理只是 说明性的，并且其他随机数字电路可以使用比图1中所示的动作更少或更多的动作来实 现，或者可以实现完全不同的处理。本发明的实施例不限于以任何特定方式实现在此描 述的原理。处理100在块102开始，其中数字电路被配置为充当用于所关注的概率分布的随 机性电 路。充当用于所关注的概率分布的随机性电路可意味着根据与随机性问题相关联 的条件概率密度函数(Pdf)来产生样本。随机性问题的Pdf指示针对所获取的表示场景的 输入的多个事件中的每个事件引起该场景的概率。所关注的具体条件概率分布将取决于正被解决的问题。例如，用于立体图像分 析问题的概率分布函数很可能不同于用于文本分析问题的概率分布函数。类似地，当选 择系统中的典型值时，将根据这些模型来选择pdf。当生成表示对于确定性问题的估计的 解答的样本时，pdf将被选择用来创建样本近似于确定性答案的高度可能性。因此，对于 任何给定的问题，可以以任何适当的途径确定适当的概率密度函数，包括使用本领域已 知的技术。然而应该明白，分布是确定的，并且分布可以是与问题相关联的任何适当的分 布。例如，问题可以是以诸如Bernoulli、二项式、指数、Gaussian之类的标准已知分布 为特征的问题，在这些情况下，分布是已知分布。然而在其他情况下，问题可以是以非 标准的概率分布为特征的，并且在块102中配置的概率分布可以是唯一的非标准分布。一旦所关注的概率分布函数被获得，电路可以被配置为根据该概率分布函数接 收输入并输出样本。块102的配置可以以任何适当的方式进行。在一些实施例中，块 102的配置可以包括配置可重新配置的数字电路，从而使其表示所关注的概率分布。此配 置可以根据提供给数字电路的配置值来执行，或者根据任何其他适当的数据来执行。替 代地，配置可以通过使用设计工具设计制造ASIC、对离散部件进行互连或者执行任何其 他操作(不论是现在已知的操作还是将来开发的操作)来创建随机性电路。不论所使用 的具体技术如何，在块102中，随机性电路是利用与要解决的随机性问题相关联的pdf配 置的。
一旦数字电路在块102中被配置，针对具体场景的处理可以被执行。在块104 中，输入可以被电路接收。该输入可以表示在特定场景中采取的测量。输入中的值的数 目以及这些值的特性取决于要解决的问题。在立体视觉问题中，输入可以是利用立体摄 像机收集的图像的像素值。在文档分类问题中，输入可以是要分类的文档中的单词。因 此，输入可以是任何适当的数值，并且可以与要解决随机性问题的场景有关。在块106中，随机数字电路基于在块104中提供的输入生成样本。每个样本可 以指示已经发生从而产生了输入的事件。电路可以根据在块102中配置的概率分布生成 样本，从而在随机性电路输出的样本流中，指示事件的输出将以与由所配置的事件产生 所观察到的输入的概率分布函数所定义的概率成比例的频率发生。采样可以至少部分地 基于块104中提供的输入生成。作为简单示例，对于特定的输入值IN= 1，输出值可以 基于 P(EVENT/IN = 1)的 pdf 生成。因此，如果 pdf 指示 P(EVENT = 1/IN = 1)= 0.4，则当输入为1时，随机数字电路生成样本值1的机会是40%。如上所述，随机性问题固有地存在一定程度的随机性，并且当生成样本时，随 机数字电路随机地进行操作。因此，应该理解，尽管随机数字电路生成1作为样本的机 会为40%，但是存在60%的机会随机数字电路不生成1作为样本，并且可以替代地生成 一些其他值(例如，0、2、10等)。针对每个样本，电路的随机性被用来生成适当的输 出值，从而使得输出值流表示根据所配置的概率密度函数得出的样本。这些样本中的一个或多个可以被用来解决随机性问题。例如，一些问题可以利 用单个样本解决，或者单个样本可以提供可独立于随后生成的其他样本使用的一些有用 信息-所以，在一些情况下，单个样本可以被单独处理。对于其他问题，单个样本可能 不能产生在解决问题的过程中有用的信息；不可能只使用单个值来计算概率分布。对于 这样的随机性问题，将需要多个样本来解决随机性问题。但是，样本的数目可取决于要 解决的问题的特性或者所观察到的特定值被随机生成的次序。因此，处理100包括判决 块108，在判决块108处理可以循环回到块106以生成多个样本，或者如果充足的样本已 经被获取到，则处理继续进行到块110以进行进一步处理。可以以任何适当的方式来判断是否已经有充足数目的样本被生成。如果多个样 本要被生成，则在一些情况下流中的样本数目可以取决于要解决的问题的特性。一些问 题可以在5个样本、10个样本、100个样本或者与要解决的问题/场景的细节有关的任何 其他数目之后被可靠地解决。要收集的样本的数目可以预先设置，或者可以基于要解决 的问题的特性被自适应地识别出。例如，如果需要各种事件的概率的粗略估计，则样本 的数目可以被设置得相对较低。如果需要较高的精确度，则需要采用较多的样本，从而 使得表示特定事件的样本的生成频率可以被更精确地计算出来。替代地，要采用的样本 的数目可以不被预先定义。而是，实际观察到的样本的分布可以被用来确定是否有充足 的样本已经被获得。例如，如果对于随机性问题的解答需要识别最可能产生输入数值的事件，则采 样可以继续，直到一个事件表示在以高于诸如0.75的某阈值的频率或者以比其他频率高 出某阈值量或者百分比的频率而采样的输出流中为止。作为另外的替代，获取的样本的 数目可能需要结合预定的自适应选择的限值。例如，可以定义要生成的样本的最大和/ 或最小数目。在这些限值内，样本可以被生成，直到条件被达到为止。
不论样本的数目被如何确定，如果在块108中确定此数目(例如，一个或多个) 的样本已经被收集，则处理可选地进行到次处理109。如果需要更多样本，则处理100返 回到块106，基于输入值生成另一个样本。如果不需要更多的样本，则次处理109可以被可选地执行，这取决于要解决的 问题的特性。这里，次处理109表示将所生成的一个或多个样本的流转换为关于这些样 本的一些有用信息的处理；例如，用于确定对于随机性问题的解答的一个或多个概率。 在其他实施例中，次处理109可以对样本值进行平均，以确定最可能的结果，或者根据 适用于要解决的问题的类型的处理来生成解答。当然，应该理解，如果所生成的一个或 多个样本值是期望的解答，则次处理109可以被完全省略。在所示出的实施例中，在次处理109中用于解决随机性问题的对样本的处理开 始于块110。此处理可以在同样的FPGA中执行，或者可以在用来生成样本的其他半导 体芯片中执行。然而，样本生成之后的处理可以是确定性的，并且可以在其他硬件中执 行或者使用软件部件执行。在一些实施例中，样本值可以被输出到随机性电路外的部件以随后进行处理。 此处理可以包括基于这些样本所采取的任何适当的(一个或多个)动作。在所示出的实 施例中，处理决定着一个或多个事件发生从而产生所观察到的输入的概率。因此，示出 了处理继续进行到块110，块110对随机性电路生成的样本进行聚合以确定由这些样本表 示的一个或多个事件的频率。在一些实施例中，块110的处理可以导致基于实际生成的样本来确定生成的值 作为样本的概率。作为只存在被识别为0和1的两个可能事件的简单示例，如果所收集的 样本的数目为10，并且6个样本具有值1，则块110中针对值1的输出频率可以为0.6， 这可以被作为事件1发生的概率为60%的指示。这样，由特定样本值表示的事件产生所 观察到的输入条件的概率可以被计算出来。但是，此同样的信息也可以被表达为概率分 布或者以任何其他适当的方式表达。不论表示样本值的方式如何，此信息可以被用在块112中生成对于随机性问题 的解答。如上所述，对于随机性问题的解答可以是关于随机性问题的任何适当的数据， 并且可以包括作为样本生成的结果的由随机性电路生成的数据。例如，解答可以是由更 大系统的一些其他部件使用的随机数字电路输出的一个或多个样本。在其他实施例中， 块112处的处理可以包括输出被确定为是最可能发生的事件的值(即，最频繁生成的样 本)或者被确定为是最可能发生的事件的一组值作为解答。块112中产生的解答还可以 是或者包括诸如计算出的概率之类的事件值以外的数据。应该理解，这些只是可以被生 成的解答的类型的示例，并且任何其他数据或信息可以附加地或者替代地在块112中被 生成作为对于随机性问题的(一个或多个)解答。本发明的实施例不限于输出任何特定 解答或者任何特定类型的解答。在块112中输出一个或多个解答之后，处理然后可以继续进行到块114，其中解 答被应用。解答被应用的方式可以取决于要解决的问题的特性。这可以涉及生成对于机 器人或者其他机器的控制信号。然而，对于其他问题，此解答可以涉及向人类用户提供 输出、向确定性计算机提供数据或其他动作。不论解答被应用的方式如何，处理100然
后结束。
应该理解，图1只示出了处理的一个迭代。一旦用于一个迭代的处理完成，另 一个迭代可以基于新的输入执行。随机处理器可以连续进行操作，以生成对于随机性问 题的解答。例如，在用于机器人或者其他机器的控制系统中，解答可以基于输入值而生 成。解答可以调整用于机器人的控制值。新的输入值然后可以被测量，并且新的控制值 可以被计算出来。这样，在本发明的一些实施例中，随机处理器可以被使用来响应于实 时输入提供实时解答。(应该理解，在使用的“连续地”只是指随时间重复执行动作，而不是只执行一 次动作。连续进行操作的一些随机数字电路可以基于或者响应于周期性的时钟信号进行 操作，并且可以只在时钟作响时生成样本/解答，但是本发明的其他实施例不限于此并 且可以在任何时间生成样本/解答)。应该理解，为了容易描述，上面被描述作为潜在事件和样本的值被给出为单比 特数值(例如，事件/样本可以为1)，但是本发明的实施例不限于利用为任何特定值的事 件进行操作。还可以存在两个以上的事件，从而使得每个事件可以由多个比特的数值来 识别。例如，在确定对象范围的情况下，可以存在很多可能的范围，并且每个范围可以 由多比特值来表示。然而，事件根本不需要对应于数值。样本值可以对文本或者字符或 者其他任何数据进行编码。另外，尽管很多数字计算机(例如，传统的电子计算机)以 两个状态的比特(即，高/低，1/0)进行操作，但是本发明的实施例可以在包括具有更多 状态(例如，三个或者四个等)的比特的电子或者非电子数字计算机中进行操作。还应该理解，图1只是可以被执行的处理的一个示例，并且各种替代实施例可以被构建。例如，处理步骤的次序是为了说明的简便。一些处理步骤的次序可以改变， 并且一些步骤可以被并行执行。例如，图1示出了在充足数目的样本被获取到之后在块 110中确定频率。频率在每个样本处可以被更新，甚至可以被用在确定是否有充足数目的 样本被获得的过程中。类似地，图1的处理指示出样本被迭代地计算出来。根据一些实 施例，随机性电路可以具有多个流水线阶段，从而当样本值被输出时，随机性电路的元 件已经部分地计算出下一个样本值。另外，图1分别示出了根据概率密度函数生成样本的处理以及针对所生成的样 本的处理。应该理解，可以替代地通过重新定义执行采样所根据的Pdf来实现任何后采 样处理的效果。因此，在一些实现方式中，图1的次处109可以不是单独的次处理，而 可以被包括在块106中的样本的生成中。然后应该理解，图1的具体处理流程只是对可 以在本发明的一些实施例中实现的处理的类型的说明，因而不限于此。作为替代处理流 程的具体示例，pdf可以被用来生成特定参数的值的样本，诸如，到对象的距离。然后， 这些样本可以通过被平均的处理，以输出估计的到对象的平均距离作为总体解答。相同 的结果也可以通过开发表示到对象的平均距离的pdf来实现。在这种情况下，可以在没 有后采样处理的情况下生成解答。图1的处理可以使用任何适当的硬件部件来实现。图2示出了可以执行图1的 处100的计算装置200的一个示例。图2的计算装置包括可以作为一个示例性的随机处 理器202的部件的随机样本生成器206和处理电路208。然而应该理解，图2的计算装置 200只说明了可以实现在此描述的技术的一些类型的计算装置，并且其他计算装置也是可 能的。例如，如结合图1所描述的，在一些实现方式中，样本处理电路208可能没有被实现，因为样本生成器206可以被配置为根据负责将由处理电路208执行的确定性处理的 概率分布而生成样本。另外，在其他实现方式中，各个样本可以提供有用信息，并且无 需对采样执行处理。因此，尽管图2的随机处理器包括随机样本生成器206和处理电路 208 二者，但是在本发明的一些实施例中，随机处理器202可以只包括样本生成器206或 者所示出的电路的一些其他部分。 图2的随机样本生成器206可以是被配置为根据由pdf P (Event/In)描述的概率分 布生成样本的随机性电路，pdf(Event/In)表示对于要解决的随机性问题所关注的分布。 在一些实施例中，随机采样生成器206可以通过将多个随机性电路元件互连而构建。这 些随机性电路元件可以根据预先定义的设计模式被相互连接，预先定义的设计模式的示 例在下面提供。然而，随机性电路元件可以以另一种适当的方式连接，或者随机采样生 成器206可以通过使用随机性电路元件以外的方式实现。不论如何实现，随机采样生成器206从场景输入部件204接收输入数据。场景 输入部件204可以是提供与计算装置200正在其中进行操作的场景有关的数据的计算装置 200的任何适当部件。输入部件204的特性可以取决于要解决的问题的特性。这种部件 可以使用任何适当的技术实现，包括本领域的已知的用于获取表示场景的参数的值的技 术。例如，场景输入部件204可以是接受来自用户的数据的用户接口。场景输入元件 204可以是收集有关环境的数据的一个或多个传感器，或者对生成的数据执行一个或多个 处理的计算装置的处理器，或者提供数据的任何其他部件。在立体视觉问题的示例中， 场景输入部件204可以是接口连接到立体摄像机的帧缓存器从而使得摄像机图像可以被 获取并被处理的接口电路。无论输入数据的特性以及获取该输入数据的方式如何，随机样本生成器206可 以使用此输入数据根据其所配置的Pdf来生成样本。每个样本可以与随机性问题的事件 相关联，并且样本可以与它们在随机性问题中发生的可能性成比例地被生成。在本发明的一些实施例中，样本可以由随机处理器202输出，并被直接提供给 场景处理部件218。场景处理部件218可以对这些样本执行任何适当的处理，包括以上 图1中所描述的生成解答的处理。在本发明的其他实施例中，诸如图2中所示的，随机 数字电路可以包括处理电路208，以对样本执行一个或多个处理动作，从而生成对于随机 性问题的解答。在图2中所示的本发明的实施例中，由于样本是由随机样本生成器206生成并输 出的，所以这些样本被处理电路208接收。处理电路208包括汇聚样本并且计算与样本 相关联的事件发生的概率的部件。在所示出的实施例中，这些部件包括映射逻辑209。映射逻辑209可以利用将样 本值映射到特定事件的传统数字逻辑部件来实现。在一些实施例中，诸如在样本表示定 义所关注的事件的数值的情况下，样本值和事件之间存在直接的对应关系。在其他实施 例中，样本值的范围可以映射到一个事件，并且映射逻辑209可以将该范围中的样本值 映射到适当的事件。在其他实施例中，尽管随机采样生成器206输出数值，但是事件可 以识别分类或者其他非数字参数。在此实施例中，映射逻辑209可以将数字样本值映射 到非数字类别。无论样本被映射到事件的方式如何，一种用于处理样本值的方法是对与每个事件相关联的样本值的数目进行计数。图2的示例实施例包括用于此目的的多个计数器。 当样本被处理电路208接收时，用于由样本表示的事件的相应计数器210增大(例如，如 果样本为1，则与事件1相关联的计数器增大；如果样本是2，则与事件2相关联的计数 器增大；等等)。事件计数器可以被以任何适当的方式组织。例如，可以由传统数字电路中所使 用的类型的控制逻辑(图2中未示出)在对应于事件的样本被生成时创建并分配事件计数 器210。替代地，可以基于随机处理器202的配置以及已知的有限数目的事件预先生成事 件计数器210。无论计数器是如何与具体事件相关联的，由于计数器210根据所接收的样本而 增大， 所以概率212也可以被更新，从而使得每个事件具有表示与该事件相关联的样本 的百分比的相关联的概率。计数器210和概率212可以在样本被生成时被连续更新。在 所示出的实施例中，事件概率部件212可以是具有将针对每个事件的计数除以所接收的 样本的总数的作用的算术或其他电路。但是，概率可以由任何适当的部件以任何适当的 方式来计算。在一些实施例中，对于随机性问题的解答不需要关于所有可能事件的数据。而 是，关于事件的某子集的数据可以被选择用于进一步处理。因此，处理电路208还可以 包括选择部件214，以分析概率212并作出选择。如上所讨论的，在一些情况下，由随机 数字电路进行的处理可以包括分析样本以确定最可能的事件或者最可能的事件的集合。 所以，选择部件214可以通过任何适当的方式来分析概率212以确定一个或多个事件的集 合，并且可以将这些事件指示给随机处理器202的解答部件216。解答部件216可以处理由选择部件214生成的相关联的概率以及事件，以得出解 答。如上所注解的，具体的处理可以取决于要解决的随机性问题的特性。这种处理可以 使用传统的处理技术来执行，尽管任何适当的处理都可以被执行。此解答然后可以被输出到场景处理部件218。以任何适当方式执行的处理的特 性，包括使用本领域的已知技术。场景处理部件128例如可以实现由解答部件216生成 的用于机器人或者其他机器的控制判决。在此实施例中，场景处理部件218可以是用于 机器人的控制传动机构(controlactuator)。在其他实施例中，解答可以表示基于文档中的 单词的文档的分类，并且场景处理部件218可以更新计算机存储器中表示所确定的分类 的数据结构。本发明的一些实施例提供的一个优点可以在图2的示例性电路中看出。图2的电 路可以提供比传统浮点技术更快且更简单的计算事件的概率的机制。以前，为了基于一 些输入确定特定事件/输出的概率，浮点处理器确定给定输入的所有可能的事件/输出， 然后高精确度地计算每个发生的可能性/概率。在图2的实施例中，这些概率可以改为 基于所生成的样本和相对简单的计数操作而计算出来。另外，不必要计算所有可能事件的概率，特别是在对于问题的解答仅涉及最可 能事件或者少量最可能事件的识别时。对于越可能的事件，样本越被频繁地生成，并且 这些事件发生的概率的合理近似可以被计算出来，即使在没有充足的样本来可靠地计算 不可能或者不太可能的事件的概率。另外，计算出的概率的可靠性对于电路的大部分的精确度相对不敏感。随机样本生成器206的输出通过设计而反映出随机处理。所以，包括处理误差在内的更多的不 准确性一般将对最终的计算产生可以忽略的影响。所以，包括不可靠的电路在内的相对 较低的精确度的电路可以被使用。对于精确度的较低要求可以简化用于解决随机性问题 的电路的设计、构造以及操作，并且可以减小这种电路的尺寸以及对它们进行操作以解 决随机性问题所必需的时间。对于精确度的较低要求还可以使得能够使用不太精确的计 算机(例如，分子计算机)。这样的处理的简化可以使得能够将随机处理用在此前传统处理不可实行的许多 应用中。例如，在基于立体视觉的机器人控制系统中，此更简单的处理可以使能实时 控制，或者使能在不具有支持传统随机处理方法的充足处理功率的更小设备中的实时控 制。作为另一个示例，加快解决随机性问题的速度可以使得随机处理能够被用于搜索引 擎或者用户正在等待答案的其他场景中。所以，尽管结合具体的示例性问题描述了随机 性问题解决，但是在此描述的这些方法可以被广泛应用。已经以对一些随机数字电路可以如何被操作以及它们可以如何被用在更大的计 算装置中的描述的形式提供了上下文，下面提供对可以如何实现随机数字电路的讨论。 应该理解，如上所述，随机数字电路可以通过各种方式实现。然而，随机性电路元件、 随机性支电路、随机性电路以及随机处理器是四种示例性实现方式，下面给出这些示例 性实现方式中的每一种实现方式的示例。另外，应该理解，尽管下面描述了示例性实现方式，但是这些示例性实现方式 仅被提供用于说明性的目的，以描述在此描述的原理可以被用在创建随机性电路和对它 们进行操作来解决随机性问题中的方式。这些原理可以通过任何适当的方式实现。本发 明的实施例不限于根据任何具体技术执行这些原理，并且不限于根据示例性技术和下面 描述的实现方式中的任何一种来执行这些原理。图3A示出了可以用来描述随机数字电路的一些实施例的框图。在所描述的实 施例中，随机性电路是利用诸如CMOS之类的数字逻辑实现的，尽管不要求使用数字逻 辑来实现随机性电路。如图3A中所示，随机数字电路300包括数据输入IN和数据输出 OUT以及某随机性来源。在此随机性电路利用可配置逻辑实现的实施例中，电路300可 以额外包括至少一个配置输入CONF，该配置输入CONF接收数据以将随机数字电路300 配置用于特定随机性问题和概率分布。数据输入IN —般接受可能涉及与随机性问题有关的场景的一个或多个输入值 (例如，有关场景的观察数据或者其他数据)。在本发明的一些实施例中，在诸如随机数 字电路在其上执行的概率密度函数(pdf)被描述为P(Out/In)的情况中，该pdf可以将涉 及场景/随机性问题的输入值作为条件。输出端子也可以是一个或多个端子，并且随机数字电路300可以在输出线上根 据概率分布函数输出一个或多个样本。在图3的示例中，这些输出Y可以是从pdfP(Out/ In)得出的样本。应该理解，不要求电路300的输入为表示场景的变量。在一些实施例中，随机 数字电路可以根据不以可变输入数据为条件的条件概率分布产生样本。所期望的概率分 布可以不以任何数据为条件，从而使得电路将根据不是条件概率分布的概率分布来生成 样本。因此，在一些这样的实施例中，图3A的电路300可以不包括(一个或多个)数据输入IN，并且可以不接收输入值，或者可以被看作接收NULL输入。在其他实施例 中，输入可以是预先定义的值，从而使得样本是根据给定所定义的条件的条件分布而生 成的。
如上面所讨论的，在本发明的一些实施例中，随机数字电路将一定程度的随机 性结合到它们的处理中，以解决随机性问题中固有的随机性。图3A示出了随机性电路 300可以包括额外部件，该额外部件可以当在输出处产生样本值时提供被结合到该电路的 操作中的随机值。应该理解，随机性可以被以任何适当的方式结合到随机数字电路300 中，并且其可以从随机数字电路300本身得出或者可以从数字电路300的外部提供。例 如，随机性可以基于随机数字电路本身的一些检测条件，诸如改变电路300的一些部分 的电条件。在传统的电子系统中，这样改变电条件有时被称为“噪声”。电路中的噪声 的一些部分归因于随机原因，诸如半导体衬底、随机数字电路中的热噪声，这种随机噪 声的大小、频率或者其他参数可以被检测出来并被映射到比特模式，从而创建随机比特 模式。替代地，随机性可以从电路外面提供，诸如由随机地或者伪随机地生成的比特流 提供。因此，应该理解，图3A的电路300的随机值输入被示出为部分在电路300内并且 部分在电路300外，以澄清在本发明的不同实施例中，输入可以是电路300的部件或者可 以远离电路300。因此，根据本文中描述的一些原理进行操作的随机数字电路可以进行操作以至 少部分地基于随机值根据概率分布生成并输出样本，随机数字电路的这种输出是不确定 的并且可以根据概率来被描述。这些样本是根据配置随机数字电路的概率分布函数而生 成的，并且可以按照值被生成作为样本的比例大致对应于这些值根据概率分布函数发生 的概率而被生成。尽管随机性电路300可以被以任何适当的方式构建，但是发明人已经认识到这 种电路的实现方式可以通过装配作为排列的随机性支电路的电路而实现，随机性支电路 可以由排列的一个或多个随机性电路元件构建。这些支电路可以可以通过确定性的或者 其他已知的逻辑元件被相互连接或者耦合。通过多个随机性支电路和电路元件排列在一起(每个随机性支电路或者电路元 件根据概率分布生成样本)，可以形成根据与所有这些概率分布有关的概率分布生成样本 的电路。支电路的功能之间的关系以及它们之间的相互连接可能会影响包括随机性支电 路和电路元件的随机性电路生成样本要根据的总体概率分布。例如，电路可以被构建为根据基于支电路(每个支电路执行边缘概率分布函数) 的概率分布的联合概率分布来产生样本。按照这种方式，可以通过将根据简单概率分布 生成样本的电路排列在一起来构建根据复杂概率分布生成样本的电路。下面提供对这些组合和排列的特性的详细讨论，包括随机性支电路和随机性电 路元件可以被如何实现的一些示例。然而，图3B—般地示出了可以由随机性支电路的组 合形成的随机性电路300’的示例。在此示例中，随机性电路300’被示出为包括四个 不同的随机性支电路302、304、306和308。这些随机性支电路中的每一个可以如上所述 从条件概率分布来生成样本；例如，随机性支电路302可以从概率分布P(OUT1AN1)生 成样本。如所示的，支电路302可以从提供给电路300’的输入值以及由支电路308生 成的输出(样本)接收其输入。因此，支电路302的输出是来自以被应用作为该支电路的输入的这些值为条件的概率分布P(OUT1AN1)的样本。因此，可以看出，当被排列在一起时，随机性支电路可以被构建为彼此依赖， 因为它们可以基于由其他支电路生成的样本来生成样本。但是，并不是每个随机性支 电路都必须从其他支电路或者甚至从输入到总体随机性电路的值接收输入。在一些情况 下一如上所述一随机性电路可以被实现为不接受任何数据输入。但是，这样的随机 性电路可以使用与实现条件概率分布的技术相同的技术来实现，这些支电路可以从不是 条件概率分布的概率分布生成样本。这样的电路在图3B中被示出为支电路306。当按照图3B所示的方式组合随机性支电路时，支电路可以被配置为同步产生样 本；即，每个电路可以同时或者在期望的时间产生样本。然而，在其他实现方式中，依 赖于支电路的特性，这些电路可以在不同时间产生样本。例如，这可以是因为支电路302 需要六个步骤或者时钟周期来生成样本，而支电路308需要两个步骤/周期来生成样本。 在一些这样的实现方式中，随机性支电路可以同时但异步地进行操作。为了方便进行异步操作，随机性支电路还可以包括指示样本已经被生成并且准 备好被消耗的“完成”或者“使能”信号，诸如图B中所示的EN信号。完成/使能 信号EN可以被作为输入提供给消耗来自包括这些随机性支电路中的任意一个在内的随机 性支电路的样本的任何部件(例如，由支电路308输出的EN信号被作为输入提供给支电 路 302)。如上面所提到的，图3B的电路300’中的随机性支电路的组合使得电路300’能 够从基于这些随机性支电路的概率分布生成并输出样本。在图3B的示例中，电路300’ 从总体概率分布P (Out/In)(其基于P (Out1An1)等因素)生成样本。如图3B中所示，支 电路304可以最终输出作为来自总体概率分布的样本的样本。由电路304输出的样本可 以在逻辑块310中经历任何适当的处理，并且被电路300’输出以便被以任何适当的方式 消耗。电路可以被以任何适当的方式构造和配置为实现图3A中所示的设计并且充当图 3B中所示的支电路，因为本发明的根据此种设计实现随机性数字电路的实施例不限于任 何特定实现方式。这样的随机性电路的具体构造依赖于其要实现的概率密度函数。在一 些实施例中，每个支电路可以由根据简单概率分布生成样本的随机性电路元件来构造。图4A示出了可以实现根据简单条件概率密度函数生成样本的随机性电路元件的 一种方式。在此示例中，电路元件400包括用于接收随机比特流的随机比特输入线(h比 特宽)和用于输入数据的输入线(m比特宽)。该电路可以根据预先定义的条件概率密度 函数(pdf)进行操作。对于每个周期的操作，电路元件400可以在其输出线上断言(assert) 根据以输入线上的值为条件的pdf所生成的样本。用来配置随机性电路元件400的概率分布可以与任何适当的概率分布相关联。 在一些实现方式中，电路400可以被配置为从由输入配置的Bernoulli分布生成样本。Bernoulli分布是一种已知的概率分布，其中第一事件(例如，1)的发生概率为 概率P，并且第二事件(例如，0)的发生概率为1-p。Bernoulli分布可以被用来模拟其结 果可以是两个事件中的一个事件的很多不同的问题，诸如投硬币(其中结果是头像面和 背面中的一面)。在投硬币的示例中，Bernoulli参数ρ可以被理解为硬币将以头像面着 地的可能性。对于公平的硬币，参数ρ可以是0.5，因为硬币将以其头像面着地的机会是50/50。对于不公平的硬币或者其中可能的事件不是均等可能的很多其他系统，参数ρ可 以不同于0.5，例如0.4或者0.6。被配置为根据Bernoulli分布进行操作的随机性电路元件的功能由图4B中所示的 条件概率表示出。该表指示给定每个可能输入的可能输出的概率。图4B的表的头两行 示出当输入为0000时0或1将被输出的概率。但是，该表的所有其他行指示响应于每个 输入存在两个可能的输出以及与每个输出发生相关联的概率。例如，第三行和第四行指 示当输入为0001时，输出的样本应该在15/16的时间包括值0并且在1/16的时间包括值 1。其他输入产生多个可能的输出，每个输出具有指定的概率。根据图4B的概率表进行操作的随机性电路元件可以以任何适当的方式来实现。 作为一个示例，电路元件可以被实现为具有与每个输入值相关联的多个值的查找表。基 于输入到电路元件的随机比特，多个值中的一个值可以被选择。通过以期望的分布存储 多个值，基于输入的随机选择得到了期望的样本分布。在图4B的示例中，16个值可以 被与输入0001相关联地存储，并且其中的15个为0，并且其中的1个为1。如果四个随 机比特被提供以选择这些值中的一个值，则如所期望的那样，15/16的时间应为值0被选 择，并且1/16的时间应为1被选择。但是，使用更少存储器或电路的其他实现方式也可以被使用。例如，当要根据 Bernoulli分布生成样本，电路元件可以按照图5A、图5B或图5C那样来实现。这些图 示出了随机性数字电路可以被实现为从Bernoulli分布生成样本的三种不同方式，但是这 些只是对随机性数字电路可以被如何实现为从一个说明性概率分布生成样本的说明性示 例。本发明的实施例不限于从任何特定分布以任何特定方式生成样本。图5A示出了随机性数字电路可以被实现为从Bernoulli分布生成样本的一种方 式。在图5A的示例中，电路接收分别为η比特宽的随机比特R和输入信号(这里表示 为P)。随机比特R可以来自以任何适当的方式生成的1和0的随机比特流。例如，此 比特流可以是由任何已知的伪随机数生成器生成的。可以通过将随机比特R与输入线ρ上输入的比特相比较从Bernoulli分布生成随 机样本。如图5A所示，这可以通过利用直接比特式比较电路元件(示出为“大于”门) 来实现。如果R的随机η比特的二进制值小于ρ的η比特指示的值，则1可以被输出。 另一方面，如果R的随机η比特的二进制值大于ρ的η比特指示的值，则0可以被输出。 大于门的输出可以被输出到存储器元件-图5Α中所示的D触发器-并且被输出作为样本 Y。图5Α的电路可以在每当D触发器被计时的时候生成样本。对此触发器进行计时 的信号可以由可与用于随机比特流R的来源的时钟同步进行操作的周期性时钟生成。但 是，替代地，此触发器也可以通过来自其他电路元件或者生成输入ρ的值的其他来源的 使能信号来计时。无论此触发器是如何被计时的，对于每个操作，新的η比特被接受作为随机比 特R，并且被与输入信号ρ的η比特进行比较。如图3Β中所示，输入可以来自诸如随机 性电路中的其他随机性支电路或对于随机性电路的输入等来源。在这些情况下，在电路 元件每次被使能时，输入可以不同。在一些实施例中，输入信号ρ可以在时钟作响之间被保持恒定。在此情形中，输入信号ρ可以充当Bernoulli参数，指示结果将是第一Bernoulli状态而不是第二Bernoulli
状态(例如，是1而不是0)的概率。所以，通过改变电路元件被互连至其他电路元件的 方式，该元件的功能可以被指定。图5A示出了电路元件包括由EN表示的使能输出。这里，EN输出具有固定值 1，指示有效输出一直存在。例如，如果图5A的电路元件在系统时钟的每个周期中都生 成新值，则这样的实施例可以被使用。在图5A的电路等待来自其他来源的输入以进行操 作或者不总是在其输出处具有有效值的实施例中，EN输出可以在使能和禁用状态之间交 替，以指示输出线Y上何时存在有效样本。图5B示出了随机性数字电路元件可以被实现为从Bernoulli分布生成样本的另一 种方式。在图5B的实现方式中，随机性数字电路可以使用比特串行比较器来实现，该比 特串行比较器如前一样将η比特信号ρ作为输入并且消耗仅1比特宽的随机信号R。图 5Β的电路使用多路复用器来从输入信号ρ递增地选择信号比特——类似于移位寄存器从 最低有效位向最高有效位(即，从右向左)移动——并且使用标准AND门来确定此时随 机信号R上输入的单比特是否等于当前从ρ中选择的比特。如果这两个比特相等，则从 ρ中选择下一个比特，并且多路复用器从最低有效位到最高有效位移动通过信号p，一直 循环，直到发现不相等。当不相等的值被发现时——即，当来自R的比特和来自ρ的当 前选择的比特不匹配时——AND门在输出线EN上断言假(逻辑低)值，向图5B的电路 外的部件指示样本正被生成。接收EN输出信号的部件然后可以从Y提取作为由电路输 出的样本的值，其中Y是来自ρ的当前选择的比特的值。当EN信号具有逻辑低时，重置信号RST被用来将移位寄存器重置回ρ的最低有 效位(即，最右侧)。图5B的电路使用比特串行比较操作来针对每个样本生成周期并且 对于在一个周期中目前为止已经检查的比特，来确定由ρ的被检查的比特生成的值较大 还是由来自R的输入比特形成的值较大。图5B的电路的操作的作用类似于图5A的电路的操作，因为它们都对两个η比 特值(P和R)执行大于比较来确定哪个更大。该电路然后基于比较生成样本。然而，图 5Α的电路需要两条η比特输入线并且需要电路处理那些较大的信号，而图5Β的电路可以 更�。蛭浣鲆缘ケ忍匚〗胁僮�。对于空间可能比较重要的环境或者大量随机 性数字电路可能会被一起使用的环境，更小的尺寸是有益的。但是，为了生成样本，要 遍及移位寄存器地移位比特，所以图5Β的电路可能需要多个时钟周期。图5C示出了本发明的一些实施例中的随机性数字电路被实现为从Bernoulli分布 生成样本的第三种方式。与可以在每个时钟信号周期生成输出的图5A的实现方式不同， 图5C的实现方式只是每η个时钟周期生成输出，其中η是输入信号ρ的比特宽度。这是 因为尽管图5C的电路接受η比特宽的信号作为输入ρ，但是该电路只接受单个比特作为 随机性的来源R。因此，图5C的电路包括η比特移位寄存器，该寄存器每次接收一个比 特作为输入，并且每个时钟周期移位到另一个比特。这样，每η个时钟周期，η比特移 位寄存器中的所有比特都已经被替换过。图5C的电路包括计数器电路，以随着计数器变量的增大来追踪何时已经经过η 个时钟周期、何时计数器变量不等于η。当计数器变量被检测出等于η(指示已经经过了 η个时钟周期)时，D触发器可以被提供输入以指示已经达到最大并且输出DONE(完成)信号作为重置指示。另外，传递给D触发器用于DONE信号的信号可以作为指示触发器 应该从对η比特移位寄存器中的当前值与ρ进行比较的小于或等于门接受新的输入的“使 能”信号传递给D触发器以用于样本输出。类似于图5Α的电路，如果η比特移位寄存 器的值小于或等于P，则1可以被该门输出并且被输入到D触发器，D触发器然后将其输 出作为样本Y。相反，如果η比特移位寄存器的值不小于或等于p( S卩，大于ρ)，则0可 以被输出作为Y。一旦样本被输出，该电路可以被重置，并且在η个时钟周期后新的样 本被生成。已经描述了用于从Bernoulli分布生成样本值的三种电路。然而，应该理解， 本发明的从Bernoulli分布生成样本的实施例不限于以任何具体的方式来实现，并且同样 不限于根据图5A、图5B以及图5C中所示的任何电路设计来实现。另外，应该理解， Bernoulli分布只是本发明进行操作可以利用的一种示例性概率分布。随机性数字电路可 以从任何适当的概率分布生成样本。然而，任何复杂性的条件概率分布都可以被实现为 Bernoulli分布的组合。所以，在一些实施例中，随机性电路可以由实现Bernoulli分布的 电路元件构建。但是还应该理解，实现任何其他概率分布的随机性电路元件可以类似地 被组合为更大的随机性电路。结合如上所述，根据在此描述的技术进行操作的两个以上随机性电路可以被以 任何适当的方式组合，以形成总体地从与这两个以上随机性电路的概率分布有关的概率 分布生成样本的随机性电路。例如，如图3B中所示，可以实现从与随机性支电路302、 304、306以及308的概率分布有关的总体概率分布来生成样本的随机性电路300’。随机性支电路可以以任何适当的方式被组合或者排列来创建从与随机性支电路 的概率分布有关的总体概率分布来生成样本的随机性电路。图6A示出了可以被排列来创建随机性电路的两个随机性支电路600和602。图 6B示出了随机性支电路可以被组合以形成更大的随机性电路的一种方式。在图6B中， 两个随机性支电路600和602被示出为分别从概率分布P (B|A)和P (C|B)来生成样本，如 上所述。这些电路中的每一个电路是根据图4A中所示的实现方式示出的，但是可以以任 何适当的方式被实现为任何适当的电路。例如，这些电路可以被实现为以上结合图5A、 图5B和图5C描述的任意一种示例性Bernoulli电路。图6B示出了通过将电路600的输出B连接到电路602的输入B而形成的随机性 电路604。电路604可以被当作包括随机性电路600和602的随机性电路，因为随机性电 路604从通过组合来自随机性电路元件600和602的两种概率分布而生成的新的第三概率 分布来生成样本。通过以电路604中所示的方式连接门，以其输入B为条件的电路602 的概率分布(即，P(C|B))现在以电路600的输出为条件。样本可以以任何适当的方式从电路604被提�。⑶铱梢曰谒谕拇悠浣� 行采样的分布。例如，通过从电路600和电路602 二者提取样本，样本可以从与它们各 自的概率分布有关的总体概率分布的联合分布被提取。例如，通过从随机性电路600和 602提取样本B和样本C，可以从联合概率分布提取样本B，C。如图6B中所示，当总 体概率分布以电路604的输入——即，输入A——为条件时，可以根据概率分布P(B， C|A)提取来自联合分布的样本。这是基于输入A生成输出B和输出C的概率。因此，在一些实现方式中，期望通过从两个以上随机性电路中的每一个提取样本来从通过组合这两个以上随机性电路形成的联合概率分布提取样本。然而，在其他实 现方式中，期望从通过组合随机性电路形成的边缘分布来提取样本。在图6B的电路604 中，由电路600生成的样本可以被作为输入提供给电路602;所以，电路602的概率分布 可以以这些样本为条件。当电路602的概率分布受如此条件制约时，从电路602提取的 样本可以被当作从总体概率分布的边缘分布(即，与电路600和602的各个概率分布有关 的联合分布的边缘分布)提取的样本。另外，由于电路元件602的输出是以由电路元件600生成的样本值为条件的，所 以电路元件602的概率分布被当作如图6C的电路606所指示的边缘分布P (C|A)。因此， 随机性电路可以被构建为通过组合随机性电路并且选择随机性电路之一作为输出电路而 以类似于图4A中所示的方式进行动作，S卩，从以输入为条件的条件概率分布P(C|A)生 成样本。在本发明的实施例中，多个随机性支电路被实现在随机性电路中，可以以这种 方式(即，从随机性支电路之一输出样本)从边缘分布提取样本，或者可以通过从所有随 机性支电路提取样本而从联合分布提取样本。另外，可以通过以任何适当的方式从两个 以上随机性支电路提取样本来采样联合边缘分布。图6B和图6C示出了随机性电路可以通过相互连接两个随机性电路元件或随机 性支电路来构建，并且条件概率分布可以通过组合随机性支电路来创建，其中所创建的 条件概率分布可以与随机性支电路的各个概率分布有关(例如，联合概率分布、边缘概 率分布等)。然而，对于可以被组合为支电路的随机性电路元件的数目没有限制。可以 以这种方式通过组合从其他概率分布生成样本的两个以上的随机性数字电路元件来形成 任何适当的概率分布。另外，支电路的形成不限于简单随机性电路元件的相互连接。随机性支电路也 可以通过组合随机性电路元件和确定性电路元件来形成。图7A示出了一个这样的示例， 其中随机性支电路700是通过组合两个以上随机性电路元件和传统的确定性加法器(例 如，实现对数加法器树的电路)而形成的。随机性支电路700可以允许从各种概率分布 (例如，相同的或者不同的)并行生成大量样本，这些概率分布可以被组合起来以从通过 组合这些随机性电路元件形成的概率分布函数生成样本。例如，支电路700可以是从已 知的Binomial分布生成样本的支电路。此Binomial分布可以被当作以Bernoulli分布的η 次试验为特征的分布。作为简单示例，如果多次硬币抛掷中的每次作为基于具有权重ρ的硬币的 Bernoulli分布的一次试验，则Binomial分布可以得出对于“在此具有权重ρ的硬币的η次 抛掷中将有多少次出现头面像”的问题的答案。因此，支电路700的每个随机性电路元 件可以是从以输入信号ρ为条件的Bernoulli分布生成样本的随机性数字电路，并且可以 有η个电路元件来对应用于生成Bemomial分布的η个样本的。每当随机性支电路700被 使能时(可以在系统时钟的每个周期使能一次)，η个随机性电路元件将分别从Bernoulli 分布生成样本，并且这些样本将被加和以提供根据Binomial分布的样本Y。因此，类似 于图6的示例，图7A的支电路700可以被当作从概率分布Ρ(Υ|ρ)生成样本的随机性支电 路，其中此概率分布是Binomial分布。此支电路可以被与其他随机性支电路和其他确定 性部件相组合，以创建根据更复杂的概率分布的随机性数字电路。
图7B示出了可以由随机性电路元件和确定性部件生成随机性支电路702的另一 个示例。图7B的示例如图7A的示例一样从Binomial分布生成样本，但是只包括一个随 机性电路元件。在图7A的示例中，在每个时钟周期上有多个电路元件允许从Binomial分 布生成样本，而图7B的支电路允许每η个周期从Binomial分布生成样本。与图7A的示 例中一样，图7B的随机性电路元件可以基于输入参数ρ从Bernoulli分布生成样本。支 电路702可以进行操作以从Bernoulli随机性元件生成η个样本，并可以使用确定性加法器 电路来将这些样本与先前的样本相组合。该加法器可以向图7Β中所示的确定性存储器元 件输出累积总和(raimingtotalM例如，对于硬币投掷示例，生成头像面的次数)。当样 本被生成时，存储器元件可以输出当前值(累积总和)并且将其反馈到加法器电路中，并 且可以在η个时钟周期后将样本本身输出作为总和。尽管图7Β中没有示出，但是支电路 702可以包括使能输出，以指示新样本值的计算何时完成。与图7Α的支电路实施例一样，支电路702可以被认为是根据Binomial分布生成 样本的随机性数字电路，并且根据图4A的规则还可以被看作是根据Binaumial分布生成 样本的单个随机性数字电路。此随机数字电路可以被用来从这种分布生成样本和/或可 以与其他部件相组合来得到根据一些其他的概率分布来生成样本的更大的随机性数字电 路。图7A和图7B示出了可以通过相互连接随机性电路元件从而创建新的概率函数 来构建的支电路。互连的特性可以依赖于要解决的随机性问题的特性。然而，申请人已 经认识并意识到，在构建随机性电路的过程中存在一些可能频繁出现的设计模式。在一 些实例中，这些设计模式可以被反映在预先定义的支电路中，这些支电路可以被选择来 设计随机性电路从而解决特定问题。在随机性电路要被实现在FPGA、ASIC或者其他半导体芯片中的实施例中，这 些设计模式可以被存储在帮助设计这些半导体芯片的计算机化的工具中。例如，为了 实现特定随机性函数，设计模式可以被存储为定义FPGA中的可编程逻辑元件的互连的 宏。类似地，这些设计模式可以被表示为ASIC设计工具可用的核心(core)，类似于确定 性功能元件被表示为用于ASIC设计的核心的方式。任何数目或类型的随机性设计元件都可以被定义。图8A提供了可以被实现为 随机性支电路的设计元件的示例。这些支电路如同以上支电路那样可以被实现为随机性 电路元件和确定性电路元件的组合。在图8A的支电路800中，随机性电路元件根据一些 概率分布生成样本，并且将这些样本输出到确定性存储器元件。在所示出的实施例中， 电路元件根据上述结合图4A描述的Bernoulli分布生成样本。然而，本发明不仅限于 Bernoulli随机性电路元件。在图8A的实施例中，确定性存储器元件是D触发器。该触发器可以在每次样 本被生成时输出这些样本，并且可以将这些样本递送回以反馈到随机性电路元件作为输 入数据IN的一些或全部。因此，支电路800形成了从依赖于当前状态的概率分布生成样 本来确定下一个状态的随机性数字电路。图8B中示出了这样的概念，其中支电路802的 随机性电路元件被示出为根据概率分布P(S[t+l]|S[t])——或者根据P(S[t]|S[t_l])——来 生成样本，从而使得新的输出以在前的输出为条件。实现类似于图8A和8B中所示的电路进行操作的电路，可以使用随机性数字电路来实现有 限状态机(FSM)。这种随机性FSM对于解决包括根据下面描述的马尔可夫链 蒙特卡尔(Markov Chain Monte Carlo ； MCMC)算法中的一些算法进行模拟的问题在内的
许多随机性问题是有用的。如下面更详细地描述的，在本发明的一些实施例中，随机数 字电路可以被实现为对MCMC转移核进行操作以确定Markov链的下一个状态并且包括 存储该链的当前状态的如图8A和图8B中所示的存储器元件的。下面描述了对于实现随机性算法并且生成可由这些算法模拟的针对复杂随机性 问题的样本有用的其他设计模式的示例。各种随机性采样算法可以被用来模拟随机性问题，并且可以被在此描述的随机 性电路用来解决这些随机性问题。这些采样算法一般落入了 Monte Carlo方法的分类 中，Monte Carlo方法包括随机地从概率分布提取样本并且对这些样本执行一些确定性 计算以获得结果。存在很多不同类型的Monte Carlo方法，在此描述的其中的三个示例 是拒绝性(rejection)采样算法、重要性(importance)采样算法以及被称为Markov Chain ManteCarI0(MCMC)算法的一类算法。在一些实施例中，用于实现这些采样算法中的一 种或多种的设计模式可以被识别并被用来构建支电路，这些支电路又被连接到其他部件 以实现随机性电路。图9示出了可以被用来实现随机性采样算法的随机性电路的概略图。如图9中所 示，电路900包括根据所提议的分布Q(X)生成样本并且可以以输入χ为条件从而使得对 于输入χ的给定值根据分布P (χ’ |x)在输出χ’处生成特定样本的数字随机性支电路。 实现这种概率分布的数字随机性支电路可以将值χ以及随机比特流R作为输入。在电路900的一些实现方式中，根据Q(X)输出的样本是可接受的样本，并且可 以被用作由电路900输出的样本。然而，在其他实现方式中，可以根据一些函数估计样 本χ’来确定样本χ’是否是可接受的样本。如图9中所示，值χ’ 一旦被生成就被提 供给EVAL电路，以确定该样本是否是可接受的。EVAL电路可以进行诸如确定性或者随 机性处理之类的任何适当的处理来确定样本是否是可接受的，并且可以在执行此处理的 过程中使用随机性和/或确定性电路元件。此处理可以基于正被实施的特定采样算法。 如果此处理是随机性的，则EVAL电路可以将另一个随机比特流R作为输入。EVAL电路可以生成指示样本χ’将是否被接受作为样本的ACCEPT信号或者 REJECT信号。如果样χ’本将被接受，则电路900可以将该值输出作为输出Y。如图 9中所示，当ACCEPT信号被断言时，可以从存储值χ’的存储器元件获取输出Y。在 正被实施的随机算法是下一个输出依赖于前一个输出的随机算法的情况下，该存储器元 件还允许值χ’被作为反馈提供给根据Q (χ)进行操作的随机性电路元件。图9的电路900可以以能够使用在此描述的原理来实现的一些算法的全部流程 为特征，但是不能以所有算法为特征。下面给出了可以使用随机性数字电路实现特定算 法的方式的示例；这些电路中的一些电路可以根据图9的设计进行操作。然而，应该理 解，本发明的实施例不限于以任何适当的特定方式实现随机性采样算法，并且可以基于 要解决的问题使用任何适当的实现方式。另外，图9没有清楚地示出指示何时生成样本的使能信号。应该理解，要被与 其他电路互相连接的支电路可以提供这样的信号，从而使得接收由该支电路生成的值的 其他支电路可以仅对有效值进行操作。在图9的实施例中，ACCEPT输出提供了对有效样本已经被生成从而可以被用来生成使能输出的指示。图10示出了在此描述的随机性数字电路可以被如何用来实现拒绝性采样算法的示例。拒绝性采样一般在本领域中是已知的，并且一般被用在直接采样所期望的概率 分布P(X)比较困难或者不可能但是采样包括所期望的概率分布的紧密相关的概率分布 Q(χ)——从而使得ρ(χ) < cQ(x)(其中，c是常数)——可能相对简单的情况。如图10的电路1000中所示，随机性数字电路可以被实现为从紧密相关的概率分 布QOO生成样本。该电路可以如上所述生成样本，并且可以通过根据以上所述的技术组 合合随机性和/或确定性电路元件来实现。当然，任何适当的实现方式都可以被使用。根据概率分布Q(X)的样本可以被输出到存储器元件(这里示出为D触发器)。 样本还可以被输出到对所生成的样本执行除法函数p(x)/CQ(x)的算术单元，此算术单元 被用来确定从概率分布QOO生成的样本是否可能处于所期望的概率分布p(X)中——如 果样本不处于所期望的概率分布中，则其被拒绝。这种数学(mathmetical)单元的输出 (即，样本是被接受还是被拒绝)被传递通过从Bernoulli分布进行采样的随机性电路元 件，从而使得样本有可能被接受或拒绝。如果Bernoulli电路的输出指示样本将被接受， 则DONE输出线可以被断言以向外界部件指示样本已经准备好在SAMPLE输出线上被读 取。相反，如果样本不被接受，则电路1000可以执行另一个迭代以生成另一个样 本，并且确定该样本是否将被接受或拒绝。迭代可以被重复，直到存储器元件拥有被接 受的样本为止。图11示出了用于另一种已知的采样算法的另一种示例性电路设计模式。在此 示例中，该电路实现了重要性采样器。与拒绝性采样中一样，在重要性采样中，诸如在 所期望的概率分布难以计算的情况下，值是根据近似于所期望的概率分布P(X)的概率分 布采样出来的。使用重要性采样，可以提出一种被认为是P(X)的良好近似的概率分布 q(x),并且从实现此所提议的分布的随机性数字电路可以生成k个样本。可以从这些随 机性数字电路中的每一个随机性数字电路得出各种被称为“粒子(particle)”的样本提 案，并且可以利用所提出的分布q(x)和所期望的分布p(x)之间的比率对这些粒子进行加 权。然后可以对经过加权的粒子执行重新采样处理，并且选择一个作为样本输出。可以 与粒子的权重大致成比例地选择粒子。图11示出了可以实现重要性采样的随机性电路的实现方式。如图所示，多个随 机性支电路并行地根据所提出的分布QOO生成样本。如图所示，多个随机性支电路各 自根据所提出的分布QOO生成样本，从而并行地从概率分布Q1 Och-Qk(X)生成多个样 本。可以使用数字算术电路对表示所提出的样本的每个支电路的输出进行加权，该 数字算术电路可以将样本值乘以一定的比例因子，此比例因子被表示为根据所期望的概 率分布生成样本值的概率相对于使用用来生成所提出的样本的所提出的概率分布生成样 本值的概率的比率。这些经过加权的值可以被锁存在存储器元件中，这些存储器元件在此被实现为 一组D触发器。一旦支电路Q1(X)H^Qk(X)中的每一个生成了样本，重采样器电路可以 选择这些值中的一个值作为样本输出。重采样器电路可以是确定性电路也可以本身是另一个随机性支电路，这依赖于要由电路1100实现的总体概率分布。在解决随机性问题的过程中也可以涉及的另一种设计模式是针对采样实施 Metropolis-Hastings (MH)算法的支电路。图 12 示出了 根据 Metropolis-Hastings (MH)算 法生成样本的电路的一种示例性实现方式。MH算法是可以被用来根据难以或者不可能 通过如下方式精确进行采样的概率分布来生成样本的Markov Chain Monte Carlo (MCMC) 算法通过带偏随机游走处理从所提出的分布创建样本的Markov链并且对样本进行评价 以确定这些样本是否是从所期望的概率分布得出的样本。在Markov链中，链的下一个状 态只依赖于当前状态，而不依赖于过去的状态。随机游走算法可以是这样的一种算法， 其中，很多可能的状态值(例如，潜在样本)被确定，并且在另一个样本之后每个值被生 成作为样本的概率被生成——换言之，对于与某个值相关联的每个状态，处理将从其他 状态游走或者“跳”到该状态的可能性。所以，Metropolis-Hastings算法在每次迭代中都生成样本，并且基于先前的针对
所提出的概率和所期望的概率生成的样本来确定该样本是否可能被生成。如果是，则新 生成的样本可以被“接受”并且被作为采本输出；否则，该样本被拒绝，先前生成的样 本被再次作为样本输出，并且处理重复进行以生成新样本。这样，Metropolis-Hastings算 法可以被考虑作为符合图9中所示一般形式的算法，其中样本被生成，并且一些函数被 执行以确定样本是否是可接受的。图12示出了使用在此描述的随机性电路的Metropolis-Hastings算法的一种实现 方式。在每次迭代中，从所提出的概率分布QOO生成样本，其中所提出的概率分布是 一些其他所期望的概率分布POO (其是所关注的分布)的模型。图12的元件1202是从 分布QOO生成样本的随机性电路元件。应该理解，分布QOO可以以各种输入数据为条 件；特别地，在一些实现方式中，针对第一迭代η的分布Q(X)可以以在前的迭代n-1中 生成的样本为条件，从而使得在第一迭代中生成的样本χ’以在在前的分布中生成的样本 χ为条件(即，概率分布为Q(χ，|χ))。当样本χ’被从随机性电路1202生成时，其可以被提供给存储元件1206进行存 储。然后，在此迭代中，存储元件1206存储χ’，并且存储元件1204存储χ。这些值 可以被每次一个值地提供给元件1220，元件1220对χ和χ’执行算术确定性运算以确定 这些值中的每一个值根据概率分布POO生成的概率。元件1220执行此操作两次，期间 元件1218充当分别将χ和χ’中的每一个提供给该操作的多路复用器。在元件1220执 行的操作中，对样本χ和χ’的值可以经过对数运算，以将它们转换到(log)域。此处理 可以进行是因为当利用概率进行工作时，这些值很可能在0和1之间，并且可能非常小并 接近于0 ；将它们转换到log域具有使这些数变大并使得能够执行更简单的算法(例如， 乘法变为加法，以及除法变为减法)的作用。生成X的概率被存储在存储元件1222中， 并且生成χ’的概率被存储在存储元件1226中。元件1226 (在log域)执行这些运算中 的减法运算，从而其(在实域)输出生成χ’的概率相对于生成χ的概率的比率P(χ’ )/ P (χ) 。此外还针对Q(x)分布计算概率的比率。元件1210是执行两次运算的确定性元 件。第一，元件1210使用针对Q(X)的概率密度函数来计算基于χ生成χ’的可能性。 对于第一次运算，其在第一输入上接受X’，在第二输入上接受X，并且使用给定的χ来评估针对Q(x’)的pdf(即，从针对χ的边缘分布生成样本)。此值被输出到存储元件 1212并被存储。第二，元件1210利用相反的值执行相同的运算；换言之，其使用给定 的χ’来评估针对QOO的pdf。此值然后被输出到存储元件1214。元件1212和1214中存储的这两个概率然后被数学元件1216(在log空间中)相 减，以生成这两个概率之间的比率Q(x，|x)/Q(x|x')。元件1226禾Π 1216计算出来的比率是Metropolis-Hastings算法的两项。对于 此算法，样本被接受的可能性被定义为a = ala2，其中al = P(x’ )/P(x),并且a2 = Q(x' |x)/Q(x|x')。因此，在块1228中，这两个比率——仍然在log空间——在加法 器元件1228中被加和以提供概率a。一旦计算出，加法器1228的输出被提供给数学元件 1230以对该值执行指数运算来将其转回真实值并将其从log域除去。由元件1230输出的值是在Metropolis-Hastings算法的此次迭代期间样本将被接 受作为样本的可能性。在快1232中，此概率被提供给随机性电路1232，随机性电路1232 进行操作以从以此概率为条件的Bernoulli分布生成样本。随机性电路1232生成指示该样 本是否已经被接受的输出值EN。如果该样本被接受，则样本X’被输出并被以任何适当的方式消耗。另外，此 样本χ’可以被作为输入提供给随机性电路1202，从而使得随机性电路的概率分布以新 生成的样本为条件。如果该样本被拒绝，则之前的样本χ被再次作为样本输出，并且之前的样本χ可 以被再次提供给元件1202，从而该值作为概率分布的条件。无论此样本是否被接受，一旦EN样本被生成，则处理就可以被重复并且随机性 电路1202可以生成另一个样本。使用图12中所示的随机性电路1200来执行Metropolis-Hastings算法提供了各种 优点。例如，当利用作为对称分布(例如，高斯分布)的QOO来实现Metropolis-Hastings 算法时，该算法可以被非�：玫刂葱小５闭庋姆植急皇褂檬保嚷蔘(x’ |x)/ Q(x|x’ )——在电路1200中由元件1208、1210、1212、1214以及1216计算出来的比 率——可以为1，因为χ将“跳”到给定的χ’以及χ’将跳到给定的χ的可能性是一样 的。然而，传统的实现方式并不允许使用高斯分布，因为利用传统技术使用高斯分布进 行采样需要在可接受的样本可以被生成之前从概率分布生成大量样本。需要这样做是因 为对称的高斯分布不能生成其他分布可以生成的多种样本，所以当使用高斯分布时有必 要生成更多的样本来获取有关所期望的概率分布POO的更多信息。生成更多样本需要大 量时间，并且利用传统的实现方式生成每个样本也将占用大量事件。因此，由于时间成 本的限制，传统 的实现方式一般不能使用高斯分布实现Metropolis-Hasting。然而，使用在此描述的本能地进行动作以从概率分布生成样本的随机性电路， 可以从包括高斯分布在内的很多分布迅速生成样本。因此，大量样本可以被迅速生成 (远远快于使用传统技术来生成)。由此，可以使用是高斯分布的所提出的分布Q00来 实现Metropolis-Hastings算法，从而电路可以被实现用于执行不需要计算比率Q (χ，|χ)/ Q(x|x，)的 Metropolis-Hastings 算法；比率 Q(x，|x)/Q(x|x，)可以总为 1。这样，可 以通过去除这些部件及他们的相关操作，可以使得实现Metropolis-Hastings算法并且根据 在此描述的技术进行操作的随机性电路更小、更快。
应该理解，图12的电路1200只是使用根据在此描述的技术进行操作的电路来实 现Metropolis-Hastings算法的一种示例性方式，并且其他方式也是可能的。另外，随机 性电路可以以任何适当的方式实现任何适当的采样技术。例如，可以根据以下引用的技 术中的任何技术来实现Metropolis-Hastings算法和其他MCMC算法，其中以下文件中的 对用于实现随机性采样算法的技术以及用于解决随机性问题的其他技术的讨论以及有关 随机性处理的教导通过引用被结合于本文中-Metropolis, N., Rosenbluth, Α., Rosenbluth, R., Teller, A.&Teller, Ε. (1953) .Equation of state calculations by fast computing machines.J.Chem.Phys。-Andrieu, C.，De Freitas, N.，Doucet, A., Jordan, M.I.An introduction toMCMC for machine learning.Machine Learning, 2003 年第 50 卷第 5-43 页。-Neal，R.M.Probabilistic inference using Markov chain Monte Carlomethods.计算机 科学系，多伦多大学，1993年。-Geman and Geman (1094) .Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images.IEEE Transactions on Pattern Analysisand Machine Intelligence
6 721-741。-Mackay, D.J.C.Information theory, inference and learning algorithms.Cambridge University Press.2003 年。-Μ.F.Tappen, W.T.Freeman.Comparison of Graph Cuts with BeliefPropagation for Stereo，using Identical MRF Parameters.In Proceedings of theNinth IEEE International Conference on Computer Vision (ICCV)，第 900-907 页，2003 年。以上的Geman and Geman参考文件描述了 Gibbs采样算法(MH算法的特殊情况)
在图像分析中的使用，并且描述了结合马可夫随机场(Markov Random Field，MRF)来实 现Gibbs算法。通过根据在此描述的技术并使用在此描述的随机性数字电路来实现随机性 采样算法所提供的一些优势在当这些技术和电路实现针对MRF的Gibbs采样算法时可以 被很好地示出。Gibbs/MRF算法一般被认为在概念上比较简单，但是计算上非常低效。 然而，当使用在此描述的技术实现时，多个Gibbs核可以被实现为随机性支电路，并且这 些支电路的至少一个子集可以在任何给定的时间被并行操作，以提供对于Gibbs/MRF算 法的非�？焖偾矣行У慕饩龇桨�。图13A至13D示出了可以使用在此描述的随机性数字电路的Gibbs/MRF算法的 一种实现方式。图13A和13B示出了可以形成实现Gibbs/MRF算法的随机性电路中的 支电路的Gibbs核的替代实现方式。每个Gibbs核可以分别操作，但是可以为其相邻的核 提供输出以及从其相邻的核接受输入。Gibbs采样算法对于模拟包括难以独立评估的很多随机性变量Xp X2>…、Xn 的随机性问题是有用的。Gibbs采样通过向所有而不是一个随机性变量分配特定值并且然 后基于某些随机变量从针对其余变量的条件概率生成样本来帮助建模随机性问题。Gibbs 核针对随机变量X1进行操作所利用概率分布从而可以被表征为P(X」X2，X3，…，Xn)。 根据此分布生成的针对X1的样本可以被提供给另一个Gibbs核，以根据类似分布)诸如 P(X2)X1, X3,…，Xn))执行对于另一个随机变量的计算。如图13A中所示，用于特定 随机变量的Gibbs核1300可以执行包括基于相邻核提供的输入值来计算对于每个可能事件的评分的处理。评分可以通过使用描述MRF的联 合概率密度函数(Gibbs核1300正利用其进行工作)并计算Gibbs核1300正在对其进行操 作的变量的条件概率来进行。一旦这些评分被计算出，它们可以被调节(tempered)，并 且(log)归一化常数可以被计算并用来对能量进行归一化。这些归一化的能量然后可以被 转换为针对每个可能事件的概率，并且可以基于这些样本来生成样本。可以基于Gibbs核 1300正在对其进行操作的随机变量的大小在线性时间内针对Gibbs核1300实施此处理， 并且可以使用于结合有用于采样的简单随机性累加器的标准技术来实施此处理。图13A的Gibbs核对传统技术提供了很多改进，因为其提供了快速计算并生成 输出，并且可以被并行实现。然而，当用于样本的条件概率表(CPT)比较小时可以达到 更大的效率一换言之，当潜在的输入和输出的数目较小时，给定一组输入时的每个事 件发生(即，每个输出被生成)的概率可以被简单地计算出来。在此情况下，这些概率 可以被用来预先计算权重(这些权重被输入到存储在随机性支电路的存储器中的查找表 中)，从而使得当输入从相邻核接收到时，可以通过在固定时间在查找表中访问该组可能 的输入和适当的经过加权的值来确定它们。这种实现方式在对于随机性问题所要求的随 机性的程度不太高并且MRF的程度不太大时是有用的。
如图13B中所示，当输入IV··!^被Gibbs核1302接收到时，Gibbs查找表检索
预先计算出的权重，并且在DOUT线上将它们提供给随机性电路元件，该随机性电路元 件选择输出，从而使得概率分布P(X1IX2, X3,…，Xn)被实现。该随机性电路元件(被 标记为Theta)在其输入线WEIGHT上接受权重，并且在随机信号线ENTROPY上接收随 机性的来源(诸如随机生成的比特流)。该随机性电路元件然后根据以输入权重为条件的 分布在其输出线OUT上生成样本，所述权重是由Gibbs核1302在其输出线DOUT上输出 的。这样，Gibbs核可以被以非常迅速的方式实现，并且可以允许实现非常高效地Gibbs/ MRF采样算法。如上所述，在GibbS采样算法中，大量随机变量被操作，并且可为每个变量计算 条件概率分布。因此，可以通过图13A和图13B之一中示出的方式实现的Gibbs核可以 被用于随机性问题中的每个随机变量。与随机变量X1相关联的每个核可以从与随机变量 X1所依赖的其他随机变量相关联的其他Gibbs核接受作为输入的值。每个Gibbs核可以 被配置为根据针对随机变量X1的条件概率分布(被给予其他随机变量的值)进行采样。 结果，总体Gibbs采样问题可以被表示为互连核的曲线图。使用这些Gibbs核通过开发随机性问题的马尔可夫随机场(MRF)中的条件独立 性可以实现更高效率。具体地，当MRF曲线图被着色从而使得没有两个相邻的节点具有 相同颜色时，相同颜色的所有节点有条件地独立于具有所有其他颜色的节点，所以可以 被并行采样。这首先在以上提供针对正方点阵MRF的Gemanand Geman参考文件中被观 察到，诸如图13C中所示。当对MRF进行着色时，并行性的程度相反地依赖于颜色的数 目，并且Gibbs核之间的通信成本由MRF中的横跨着色边界的总比特来决定。图13D示出了根据Gibbs/MRF采样算法进行操作的随机性电路的实现方式，其 中该随机性电路对当随机性问题具有如图13C中所示的MRF时实现的并行性进行了开发 使用。如图所示，存在两种“颜色”的Gibbs核，浅色和深色。如图13B中所示的核 可以被如图所示地相互连接。浅色核可以被并行操作，并且深色核可以被并行执行，因为可以看出它们的操作不直接取决于彼此所输出的值。换言之，如图所示，深色核的输 出被连接至浅色核的输入，并且浅色核的输出被连接至深色核的输入。深色核没有被相 互连接，并且浅色核没有被相互连接，所以它们可以被并行操作。因此，图13D的随机 性电路1306是并行周期单站点Gibbs核的二相结构。对于非常大的模型——大于图13C 和13D中所示——这种模式可以使用任意数目的相而随意铺制。与每种“颜色”相关联 的核可以被并行操作，从而在点阵区域中以线性空间为代价而维持了独立于点阵大小的 固定时间Gibbs扫描。这种使用MRF的Gibbs采样算法的实现方式对于解决各种随机性问题是有用 的。例如，使用这种实现方式可以有效解决一些立体视觉问题。图14示出了 Gibbs采 样器可以如何被用在执行立体视觉问题中的示例。如图14中所示，在立体视觉问题中可能生成了两个图像，例如来自两个数字摄 像机的右侧图像和左侧图像。由数字摄像机创建的数字信息可以被输入被配置为如上 所述地执行Gibbs采样算法的随机性电路。这种随机性电路可以从深度图生成并输出样本，这些样本是从针对特定对象的概率分布得出的样本，并且是由左侧和右侧图像观察 的到特定对象的距离的潜在“答案”。这可以通过将左侧和右侧图像输入每像素差异块 (disparity cube)中以进行分析并且将分析的结果输出到类似于图13D中所示的方式实现的 Gibbs核矩阵来进行。Gibbs核的点阵然后可以从Gibbs核产生样本。已经描述了若干种采样算法，并且已经示出了随机性电路的示例性实现方式。 然而，应该理解，本发明的实施例不限于实现任何特定的随机采样算法——或者任何采 样算法_并且可以以任何适当的方式实现算法。可以在本发明的实施例中实现的其他随机采样算法包括中国餐馆过程(Chinese Restaurant Process)和用于解决聚类问题的其他算法。例如，用于Bayesian聚类的有效
Gibbs采样算法可以使用中国餐馆过程混合模型实现，作为用于关联聚类的更加一般的 Gibbs采样算法的特殊情况。这种算法可以通过构建随机性有限状态机在使用本文中描述 的随机性数字电路的随机性电路中实现，所述随机有限状态机使用传统的存储器架构来 存储数据、充足的统计数据和Gibbs核以顺次进行评估，并且从针对每个数据点的聚类分 配中进行采样。这种算法是本领域已知的，并且可以以任何适当的方式使用随机性电路 实现。作为另一个示例，GibbS采样算法也可以使用主题模型而被用于文本分析。可 以在随机性电路中通过构建随机有限状态机来实现这种算法，其中该随机有限状态机 使用传统的存储器架构来存储文本集、充足的统计数据和Gibbs核以进行顺次评估， 并且从针对每个单词的主题分配进行采样。这些算法是本领域已知的，并且可以从可 在 Preceedings of Academy ofSciences, 101 卷，5228-5235 页得到的由 Griffiths，T.L.& Steyvers, Μ.所著的标题为“Finding Scientific topic”的2004年的出版物以及Erlbaum出 版的 Handbook of Latent SemanticAnalysis 中印刷的由 Steyvers，M.& Griffiths, Τ.所著的 标题为“Probabilistic topic models”的2007年的出版物中得到理解。这些文章通过引用 被全部结合于此(至少包括它们对用于文本分析的Gibbs采样算法以及用于解决随机性问 题的其他算法的讨论以及关于随机性过程的教导)。另外，以上描述了马尔可夫随机场(MRF)可以被用于根据Gibbs采样算法来执行采样算法。但是，应该理解，马尔可夫随机场也可以用于使用各种采样算法来解决随机性问题，而不只是可以使用Gibbs采样。本文中描述的模拟随机性过程的用于根据概率分布生成样本的技术可以在任何 适当的计算环境中以任何适当的方式实现。如上所述，在一些情况下，随机性数字电路 可以被实现为进行操作以根据概率分布生成样本的随机性处理器，这些样本是对于随机 性问题的解答或者被用在解决随机性问题中。在一些情况下，可以利用确定性处理器将 这些随机性处理器实现为协同处理器。这种计算环境1500在图15中示出，其中确定性处理器1502和随机性处理器 1504被实现为协同处理器。这些协同处理器1502和1504可以共享一些计算环境的资源， 诸如共享存储器1506。随机性处理器可以从确定性处理器1502接收输入，然后在其输 出线OUT上生成一个或多个值。这些值可以是根据为协同处理器1504配置以生成样本 的概率分布的样本。这种配置在概率分布近似于确定性问题的解答或者生成确定性处理 器1502被编程对其进行操作的参数的典型值时是有用的。在确定性处理器1502被编程 为基于样本来计算某个事件的概率并且基于计算出的概率来作出决定的情况下，这些样 本也是有用的。但是，处理可以在确定性处理器1502和随机性处理器1504之间被以任何适当的 方式划分。例如，定义由随机性处理器1504生成的样本的概率分布函数可以生成否则会 出现在确定性处理的任何阶段中的值的样本。在一些实施例中，随机性处理器1504可以被实现在可编程电路中。随机性处理 器1504的编程可以被改变，以解决任何期望的问题。例如，该编程可以指定一个或多个 随机性电路元件进行操作所根据的概率分布以及这些电路元件被相互连接的方式。在一 些实施例中，该编程可以在随机性处理器1504被制造的时候被指定。但是，在其他实 施例中，这种编程可以在诸如图15之类的计算环境中被动态地指定。如图15中所示， 确定性处理器1502可以被用来向随机性处理器1504提供可以对随机性处理器1504进行 配置以解决特定随机性问题的输入(CONF)、以及随机性处理器进行动作所根据的输入 (IN)0计算环境1500可以被以任何适当的方式用来执行任何适当的计算任务。例如， 如果计算环境1500被实现在机器人中，则确定性处理器1502可以执行确定性判决，并 且可以例如生成控制机器人的运动部件从而使得机器人能够运动通过对象领域的控制信 号。确定性处理器1502可以对随机性处理器1504进行配置以解决立体视觉问题，并且 可以将来自充当机器人眼睛的摄像机的信息作为输入提供给随机性处理器1504。随机性 处理器1504可以被用来生成表示由摄像机观察的对象的距离的样本，并且将这些样本作 为输出提供在输出线OUT上。确定性处理器1502然后可以审查这些样本，并且作出关 于如何控制或者指示运动部件的判决；例如，如果样本指示对象在机器人的路径中并且 机器人有撞击该对象的危险，则确定性处理器1502可以控制运动部件改变机器人速度和 /或方向以避免撞击该对象。配置随机性处理器的能力在图15所示的场景以外的场景中非常有用。在本发 明的一些实施例中，以上所述的设计原理可以被采用，以通过为随机性电路元件和确定 性电路元件提供它们之间的可重新配置的连接来创建可重新配置的随机性数字电路。例如，可以提供 一组随机性电路元件，其中这些随机性电路元件中的每一个元件都可以从 诸如Bernoulli分布、Binomial分布、指数分布之类的各种概率分布生成样本。这些随 机性电路元件可以是可编程的，以为这些元件中的每一个提供期望的配置(例如，用于 Bernoulli电路的ρ参数、用于Binomial电路的η等可以是可编程的)。诸如加法器和存 储器元件之类的确定性电路元件也可以被设置在可重新配置的部件中。这些电路元件中 的一些或全部然后可以根据配置命令被相互连接，该配置命令可以是电子输入信号的形 式、改变部件的互连的光脉冲的形式或者其他电路编程技术的形式。无论如何实现，编 程都可以形成根据与随机性问题有关的期望的概率分布来生成样本的随机性数字电路。 这样，可重新配置的随机性数字电路可以被配置并用在各种随机性问题的解答中。在一些实现方式中，通过在可重新配置的部件中提供大量Bernoulli随机性数字 电路，可以为可重新配置的电路提供很大灵活性。这是因为很多随机性问题可以被当作 复杂的Bernoulli问题。例如，如上面讨论的，由Binomial分布模拟的随机性问题可以被 当作多个相互关连的Bernoulli问题。其他随机性问题可以被类似地简化为Bernoulli问 题，这样与这些随机性问题相关联的概率分布可以被当作Bernoulli分布的复杂组合。因 此，如上所述的可重新配置的随机性部件可以利用Bernoulli电路(即，根据Bernoulli分 布生成样本的电路，诸如图5A、图5B、图5C的电路)的大矩阵来提供，这些Bernoulli 电路具有可以在Bernoulli电路元件间作出连接的可配置互连。确定性电路元件(包括存 储器元件)也可以被包括，以使得能够形成任何期望的概率分布。但是，应该理解，可重新配置的随机性部件可以具有可以通过可配置互连而联 合的任何期望的一种或多种形式的一个或多个随机性电路元件阵列。这种电路替代地或 者额外可以包括实现如上所述的设计模式的一个或多个支电路。这些部件结合可以包括 在这些部件中的存储器和其他确定性元件可以被配置以实现所期望的随机处理器。但是，应该理解，可重新配置的随机性部件可以根本不需要利用随机性元件的 阵列来实现。如上所述，随机性电路元件可以使用数字逻辑设计技术来实现。所以，用 于数字逻辑设计的传统可编程部件可以被配置以实现如上所述的随机性电路。例如，诸如随机性处理器1504之类的随机性处理器或者任何其它的随机性数字 电路可以在本领域已知的现场可编程门阵列(FPGA)中实现。图16中示出了 FPGA实现 方式，其中该实现方式包括多个FPGA以及多个存储部件(在图16中示出为DRAM存储 器元件)。FPGA可以被配置为以任何适当的方式从所关注的概率分布生成样本，诸如， 可以通过将FPGA配置为充当以上描述的任何示例性电路或者充当根据本文中描述的技 术进行动作的电路。可以通过对FPGA进行编程以将各种电路元件连接在一起从而形成 执行随机性和/或确定性功能的更大电路或者通过指定要被存储在查找表(该查找表可以 被用在计算对于随机性问题的解答中)中的值来配置FPGA。如图16中所示，FPGA可 以适用于经由以太网连接或者以任何其他适当的方式诸如经由外设组件互连(PCI-E)连 接之类将数据而输出到另一个计算装置。应该理解，图15的协同处理器实现方式和图16的FPGA实现方式只是说明性 的，并且本发明的实施例不限于以任何特定方式或者根据任何特定技术实现随机性数字 电路。在替代实现方式中，随机性数字电路可以被实现为专用集成电路(ASIC)，并且可 以被配置为解决各种不同的随机性问题或者被硬接线以解决具体的随机性问题。
以上已经描述了用于实现根据概率分布生成样本的随机性数字电路的技术。根 据这些技术，电路元件可以被设计为根据分布生成样本，并且这些电路元件可以被与其 他元件相结合(根据可重新配置电路的编程)生成对于其他分布的样本。任何类型的概 率分布都可以使用这些技术来构建并采样。以这种方式根据概率分布生成样本有助于提 供对于随机性问题的解答。关于这些技术的额外细节以及它们的操作理论可以在被作为 Massachusetts Institute of Technology Computer Science and ArtificialIntelligence Laboratory Technical Report No.MIT-CSAIL-TR-2008-069 (2008)出版的由 Vikash K.Mansinghka、Eric M.Jonas、Joshua B.Tenenbaum 所著的 Stochastic Digital Circuits for Probabilistic Inference 中 找到，其全部内容通过引用被结合于此(至少是其对于用于创建和操作随机性电路的理 论、处理、技术以及算法的讨论被结合于此)。电路可以根据本文中描述的理论、处理、 技术以及算法实现，也可以根据以上引用的技术报告中描述的任何理论、处理、技术以 及算法来实现。已经描述了本发明的实施例，其中这些技术是以电路和/或计算机可执行指令 实现的。应该理解，本发明可以被具体化为一种方法(已经提供了该方法的示例)。作 为该方法的一部分执行的动作可以被以任何适当的方式排序。因此，可以构建这样的实 施例，其中动作被以不同于所示出的顺序执行(这可以包括同时执行一些动作，即使这 些动作在说明性实施例中被示出为顺序动作)。本发明的各种方面可以被单独或结合使用，或者在前面描述的实施例中没有具 体讨论的各种排列中使用，所以其应用不限于前面的描述中阐述或者附图中示出的组件 的排列和细节。例如，在一个实施例中描述的方面可以通过任何方式与在其他实施例中 描述的方面相结合。权利要求书中的用来修饰权利要求元件的诸如“第一”、“第二”、“第三” 之类的顺序用语本身并不意味着一个权利要求元件相对于另一个权利要求元件的优先、 居先或者次序，也不意味着被执行的方法动作的时间次序，而只是被用作区别具有某个 名称的一个权利要求元件和具有相同名称的另一个权利要求元件的标签(使用顺序用语 来表示)。另外，本文中使用的措辞和术语都是为了描述，而不应该被看作限制。“包 括”、“包含”、“具有”、“含有”、“涉及”以及它们的变型用于覆盖其后列出的 项目及其等同物以及其他项目。 已经描述了本发明的至少一个实施例的一些方面，应该理解，本领域技术人员 很容易想到各种改变、修改以及改进。这些改变、修改以及改进都是本公开的一部分， 并且都落入本发明的精神和范围之内。因此，前面的描述和附图都只是示例。
权利要求
1.一种设备，包括零个以上输入端子；至少一个输出端子，从所述至少一个输出端子输出的是从以在所述零个以上输入端 子上接收的输入为条件的总体条件概率分布得出的样本；以及多个随机性支电路，每个随机性支电路包括零个以上输入次端子和至少一个输出次 端子，其中所述多个随机性支电路中的每一个被配置为根据以在所述零个以上输入次端 子上接收的输入为条件的条件概率分布从它的至少一个输出次端子生成样本，其中所述多个随机性支电路被相互连接，以形成根据所述总体条件概率分布生成样 本的随机性电路，并且其中所述多个随机性支电路中的每一个至少部分地基于所述条件概率分布和随机性 的来源生成所述样本。
2.根据权利要求1所述的设备，其中，所述总体概率分布是基于所述多个随机性支电 路的条件概率分布的联合概率分布。
3.根据权利要求2所述的设备，其中，由所述多个随机性支电路中的每一个生成的样 本在所述至少一个输出端子上被输出，以根据所述联合概率分布生成样本。
4.根据权利要求2所述的设备，其中，由所述多个随机性支电路的子集生成的样本在 所述至少一个输出端子上被输出，以根据所述联合概率分布的边缘概率分布生成样本。
5.根据权利要求1所述的设备，其中，所述多个随机性支电路中的一个是根据所述总 体概率分布生成样本的输出支电路，并且所述输出支电路被耦合到所述至少一个输出端 子以输出样本。
6.根据权利要求5所述的设备，其中，由所述输出支电路生成的样本是根据所述总体 概率分布的边缘分布生成的，所述边缘分布是以由至少一个其他随机性支电路生成的样 本为条件的输出支电路的条件概率分布。
7.根据权利要求6所述的设备，其中，所述多个随机性支电路中的第二支电路是根据 所述总体概率分布生成样本的第二输出支电路，并且所述第二输出支电路被耦合到所述 至少一个输出端子以输出所述样本，其中，由所述输出支电路输出的样本和由所述第二输出支电路输出的样本是从所述 总体概率分布的边缘概率分布得出的样本。
8.根据权利要求5所述的设备，其中，所述输出支电路被直接耦合到所述至少一个输 出端子。
9.根据权利要求5所述的设备，其中，所述输出支电路被耦合到执行至少一个评估操 作以确定由所述输出支电路生成的样本是否是可接受的样本的确定性评估电路，并且其中，只有被确定为可接受的样本的样本才在所述至少一个输出端子上被输出。
10.根据权利要求1所述的设备，其中，在所述零个以上输入端子中的至少一个输入 端子上接收的输入数据被提供给第一随机性支电路，从而使得所述第一随机性支电路的 条件概率分布是以所述输入数据为条件的。
11.根据权利要求1所述的设备，其中，没有输入数据被接收，并且所述总体条件概 率分布不以任何数据为条件。
12.根据权利要求1所述的设备，其中，所述设备不包括输入端子。
13.根据权利要求1所述的设备，其中，第一随机性支电路的输出次端子被耦合到第 二随机性支电路的输入次端子。
14.根据权利要求13所述的设备，其中，所述第二随机性支电路根据以所述第一随机 性支电路和所述第二随机性支电路的概率分布为基础的联合概率分布的边缘分布生成样 本。
15.根据权利要求13所述的设备，其中，至少部分地基于由所述零个以上输入端子接 收的配置数据，在所述第一随机性支电路和所述第二随机性支电路之间进行连接。
16.根据权利要求1所述的设备，其中，所述多个随机性支电路通过至少一个确定性 电路元件被相互连接。
17.根据权利要求16所述的设备，其中，所述至少一个确定性电路元件包括确定性加 法器电路。
18.根据权利要求17所述的设备，其中，所述确定性加法器电路是对数加法器电路。
19.根据权利要求16所述的设备，其中，所述至少一个确定性电路元件包括存储器元件。
20.根据权利要求19所述的设备，其中，随机性支电路和所述存储器元件的组合形成 了随机性有限状态机。
21.根据权利要求19所述的设备，其中，所述存储器元件被耦合到第一随机性支电路 的输出端，以存储由该随机支性电路生成的样本，并且由所述存储器元件存储的样本的 值被反馈回该随机性支电路。
22.根据权利要求1所述的设备，其中，第一随机性支电路包括多个随机性电路元件，其中所述随机性电路元件中的每一个包括零个以上元件输入端子，以及至少一个元件输出端子，其中，所述随机性电路元件中的每一个根据以在所述零个以上元件输入端子上接收 的输入为条件的条件概率亚分布生成样本，每个样本是基于所述条件概率亚分布和随机 性的来源生成的，其中，所述第一随机性电路的条件概率分布是基于所述多个条件概率亚分布的联合 分布，并且其中，所述多个随机性电路元件被相互连接，以形成根据所述联合分布的边缘分布 生成样本的所述第一随机性支电路。
23.根据权利要求22所述的设备，其中，所述第一随机性支电路的条件概率分布是 Binomial 分布。
24.根据权利要求23所述的设备，其中，所述多个随机性电路元件中的每一个根据 Bernoulli分布生成样本。
25.根据权利要求24所述的设备，其中，所述多个随机性电路元件被并行连接到确定 性加法器电路，其中所述确定性加法器电路对由所述多个随机性电路元件中的每一个生 成的样本执行求和运算，以确定总和。
26.根据权利要求25所述的设备，其中，所述总和被作为所述第一随机性电路的 Binomial分布的样本输出。
27.根据权利要求23所述的设备，其中，所述第一随机性电路的所述零个以上输入次 端子包括指定要被包括在所述第一随机性支电路中的随机性电路元件的数目的第一输入 线以及指定成功概率的第二输入线。
28.根据权利要求27所述的设备，其中，所述随机性电路元件的数目是Binomial分布 的η参数，并且所述成功概率是Binomial分布的ρ参数，并且所述Binomial分布是以所 述η参数和所述ρ参数为条件的。
29.根据权利要求23所述的设备，其中，在所述第一输入线上接收到值后，等于所述 值的数目的随机性电路元件被选择并被相互连接以形成Binomial分布，并且这些随机性 电路元件中的每一个被利用在所述第二输入线上接收的值进行配置以根据利用该值作为 参数的Bernoulli分布生成样本。
30.根据权利要求22所述的设备，其中，所述随机性电路元件中的每一个包括接收指 定Bernoulli概率分布的成功可能性的值的第一元件输入端子，并且所述随机性电路元件 中的每一个被配置为根据以该值为条件的概率分布生成样本。
31.根据权利要求30所述的设备，其中，所述第一随机性支电路还包括多个确定性电 路元件，并且其中，所述多个随机性电路元件和所述多个确定性电路元件可以被相互连接，以基 于配置输入形成期望的概率分布。
32.根据权利要求31所述的设备，其中，所述多个随机性电路元件和所述多个确定性 电路元件被相互连接，以形成Guassian分布。
33.根据权利要求1所述的设备，还包括处理部件，该处理部件接收根据所述总体分布电路生成的样本并且对这些样本执行 至少一个后采样处理动作。
34.根据权利要求33所述的设备，其中，所述至少一个后采样处理动作包括对样本进 行汇聚以及基于这些样本计算特定值将被生成作为样本的概率。
35.根据权利要求34所述的设备，其中，由所述处理部件计算出来的概率被从所述设 备输出。
36.根据权利要求1所述的设备，其中，所述随机性的来源是伪随机数生成器。
37.根据权利要求36所述的设备，其中，所述多个随机生成支电路中的每一个从所述 伪随机数生成器接收各自的值。
38.根据权利要求36所述的设备，其中，所述多个随机性支电路中的每一个被连接至 不同的伪随机数生成器。
39.根据权利要求1所述的设备，其中，所述多个随机性支电路被配置为实现随机性 采样算法。
40.根据权利要求39所述的设备，其中，所述随机性采样算法是MonteCarlo采样算法。
41.根据权利要求39所述的设备，其中，所述随机性采样算法是拒绝性采样算法。
42.根据权利要求39所述的设备，其中，所述随机性采样算法是重要性采样算法。
43.根据权利要求39所述的设备，其中，所述随机性采样算法是马尔可夫链蒙特卡尔 (MCMC)算法。
44.根据权利要求43所述的设备，其中，所述MCMC算法是MetropolisHastings算法。
45.根据权利要求43所述的设备，其中，所述MCMC算法是Gibbs采样算法。
46.根据权利要求45所述的设备，其中，所述Gibbs采样算法用于ChineseRestaurant Process混合模型。
47.根据权利要求46所述的设备，其中，所述多个随机性支电路中的每一个实现 Gibbs转移核。
48.根据权利要求39所述的设备，其中，所述多个随机性支电路中的每一个都与马尔 可夫随机场(MRF)的节点相关联。
49.根据权利要求48所述的设备，其中，所述MRF的相互依赖的节点是通过以下方 式被相互连接的将用于第一节点的第一随机性支电路的输出线与用于第二节点的第二 随机性支电路的输入线相连接，并且将所述第二随机性支电路的输出线与所述第一随机 性支电路的输入线相连接。
50.根据权利要求48所述的设备，其中，与所述MRF的独立节点相关联的随机性支 电路被同时操作，以并行地生成样本。
51.根据权利要求50所述的设备，其中，所述随机性电路被操作以生成对解决图像分 析问题有用的数据。
52.根据权利要求50所述的设备，其中，所述随机性电路被操作以生成对解决X线体 层照相术问题有用的数据。
53.根据权利要求50所述的设备，其中，所述随机性电路被操作以生成对解决立体视 觉问题有用的数据。
54.根据权利要求50所述的设备，其中，所述随机性支电路中的每一个实现Gibbs转移核。
55.根据权利要求47和54之一所述的设备，其中，每个随机性支电路包括存储预先 计算的条件概率表的存储器元件，通过所述预先计算的条件概率表，潜在样本被根据在 所述零个以上输入次端子上接收的输入而被选择出来。
56.根据权利要求1所述的设备，其中，所述随机性电路适用于生成指示与随机性问 题有关的事件的采样。
57.根据权利要求56所述的设备，其中，所述随机性问题是图像分析问题。
58.根据权利要求57所述的设备，其中，所述随机性问题是立体视觉问题，并且所述 零个以上输入线接收与两个以上图像有关的数据，并且其中由所述随机性电路生成的样 本指示在所述两个以上图像中观察到的到对象的可能距离。
59.根据权利要求56所述的设备，其中，所述随机性问题是文本分析问题，并且所述 零个以上输入线接收与要被分析的问题有关的数据。
60.根据权利要求59所述的设备，其中，所述文本分析问题是确定文本文档的主题， 并且由所述随机性电路生成的样本指示所述文档的可能主题。
61.根据权利要求60所述的设备，其中，所述随机性电路针对主题分析执行Latent DirichletAllocation 模型的 Gibbs 采样算法。
62.根据权利要求56所述的设备，其中，所述随机性问题是因果关系诊断问题。
63.根据权利要求56所述的设备，其中，所述随机性问题是X线体层照相术问题。
64.根据权利要求56所述的设备，其中，所述随机性问题是使用通过重新采样进行的 序贯重要性采样的对象追踪问题。
65.根据权利要求1所述的设备，其中，所述随机性电路被实现在现场可编程门阵列中。
66.根据权利要求1所述的设备，其中，所述随机性电路被实现在专用集成电路 (ASIC)中。
67.根据权利要求66所述的设备，其中，所述ASIC适用于生成指示与特定随机性问 题有关的事件的样本。
68.根据权利要求66所述的设备，其中，所述ASIC是可重新配置的，以生成指示与 多个随机性问题有关的事件的样本。
69.根据权利要求1所述的设备，其中，所述随机性电路被实现为随机性处理器，其 中该随机性处理器接受与随机性问题和/或场景有关的输入，并且根据与随机性问题相 关联的所述总体概率分布生成样本。
70.根据权利要求69所述的设备，其中，所述随机处理器被实现为包括至少一个确定 性处理器的计算环境中的协同处理器。
71.—种设备，包括随机性电路，该随机性电路包括零个以上输入端子以及至少一个输出端子，其中至 少一个随机性电路在至少一个输出线上根据以所述零个以上输入端子上提供的输入数据 为条件的条件概率分布生成样本，其中，所述样本的生成至少部分地基于所述条件概率分布以及随机性的来源。
72.根据权利要求71所述的设备，其中，所述随机性的来源是随机数生成器。
73.根据权利要求71所述的设备，接收形成所述概率分布的条件的输入数据。
74.根据权利要求71所述的设备，还包括第二随机性电路，该第二随机性电路包括零个以上第二输入端子和至少一个第二输 出端子，其中所述第二随机性电路在至少一个第二输出线上根据以所述零个以上第二输 入端子上提供的第二输入数据为条件的第二条件概率分布生成样本，其中，所述样本的生成至少部分地基于所述第二条件概率分布以及第二随机性的来源。
75.根据权利要求74所述的设备，其中，所述样本和所述第二样本形成了从以所述条 件概率分布和所述第二条件概率分布为基础的联合概率分布得出的样本。
76.根据权利要求74所述的设备，其中，由所述随机性电路生成的样本被提供在所述 零个以上第二输入端子上作为所述第二随机性电路的输入，从而使得所述第二条件概率 分布以所述样本为条件。
77.根据权利要求76所述的设备，其中，所述第二样本是根据以所述条件概率分布和 所述第二条件概率分布为基础的联合概率分布的边缘分布生成的。
78.根据权利要求71所述的设备，其中，所述随机性电路包括 多个随机性电路元件，其中所述随机性电路元件中的每一个包括 零个以上元件输入端子，以及至少一个元件输出端子，其中，所述随机性电路元件中的每一个根据以所述零个以上元件输入端子上接收的 输入为条件的条件概率亚分布生成样本，每个样本是根据所述条件概率亚分布和随机性 的来源生成的，其中，第一随机性电路的条件概率分布是基于多个所述条件概率亚分布的联合分 布，并且其中，所述多个随机性电路元件被相互连接，以形成根据所述联合分布的边缘分布 生成样本的第一随机性支电路。
79.一种操作随机性电路以根据总体条件概率分布生成样本的方法，其中所述总体条 件概率分布与多个条件概率亚分布有关，所述方法包括同时操作两个以上随机性支电路，从而使得每个随机性支电路根据条件概率亚分布 生成样本，其中所述同时操作包括在第一迭代期间从第一随机性支电路生成第一样本，所述第一样本是根据第一条件 概率分布生成的，在第二迭代期间从所述第二随机性支电路生成第二样本，所述第二样本是根据以所 述第一样本为条件的第二条件概率分布生成的，以及在所述第二迭代期间从所述第一随机性支电路生成下一个样本；从输出支电路生成作为根据所述总体条件概率分布得出的样本的样本。
80.根据权利要求1所述的方法，还包括重复同时操作、交换以及生成的动作，以根据所述总体条件概率分布生成多个样本。
81.根据权利要求1所述的方法，还包括对在所述生成的动作中生成的样本执行至少一个处理动作。
82.根据权利要求81所述的方法，其中，所述至少一个处理动作包括将所述样本与在 前生成的样本汇聚在一起，并且计算值被生成作为样本的概率。
83.根据权利要求79所述的方法，其中，所述生成的动作是基于随机性的来源随机执 行的。
84.根据权利要求83所述的方法，其中，所述随机性的来源是伪随机数生成器，并且 随机生成样本包括至少部分地基于由所述伪随机数生成器生成的随机数来生成样本。
85.根据权利要求79所述的方法，还包括接收输入数据；以及向随机性支电路提供所述输入数据，从而使得所述随机性支电路根据至少部分地以 所述输入数据为条件的条件概率分布生成样本。
86.根据权利要求79所述的方法，还包括接收与所期望的概率分布有关的配置数据；以及通过至少部分地基于所述配置数据相互连接所述两个以上随机性支电路对所述随机 性电路进行配置，以根据所期望的概率分布生成样本。
87.根据权利要求79所述的方法，还包括提供与所述随机性电路生成的样本有关的至少一个值作为所述随机性电路的输出。
88.根据权利要求87所述的方法，其中，所述至少一个值包括由所述随机性电路生成 的至少一个样本。
89.根据权利要求87所述的方法，其中，所述至少一个值包括所述随机性电路生成特 定值作为样本的概率。
90.根据权利要求87所述的方法，还包括至少部分地基于在输出的动作中提供的至少一个值来确定对于随机性问题的解答。
91.根据权利要求79所述的方法，其中，同时操作所述两个以上随机性支电路包括根据Gibbs转移核操作所述两个以上随机性支电路中的每一个，从而使得所述两个以 上随机性支电路分别根据所述条件概率亚分布来生成样本的马尔可夫链。
92.根据权利要求91所述的方法，还包括为多个随机性支电路分配马尔可夫随机场(MRF)中的相应节点；以及 确定哪些节点相互独立，其中，同时被操作的所述两个以上随机性支电路是与被确定为独立的节点相关联的 随机性支电路。
93.根据权利要求92所述的方法，还包括如果确定MRF的第一节点与MRF的第二节点相互依赖，则配置所述随机性电路通过 互相连接与所述第一节点相关联的第一随机性支电路和与所述第二节点相关联的第二随 机性支电路来反映相互依赖的关系，其中，所述相互连接包括将所述第一随机性支电路的输出端耦合到所述第二随机性 支电路的输入端，并且将所述第二随机性支电路的输入端耦合到所述第一随机性支电路 的输入端。
94.根据权利要求93所述的方法，其中，同时操作两个以上随机性支电路的动作包括同时操作两个以上随机性支电路，以执行Gibbs采样算法。
95.根据权利要求79所述的方法，其中，同时操作两个以上随机性支电路的动作包括同时操作两个以上随机性支电路，以执行Metropolis-Hastings采样算法。
96.根据权利要求79所述的方法，其中，同时操作两个以上随机性支电路的动作包括同时操作两个以上随机性支电路，以执行马尔克服链蒙特卡尔采样算法。
97.根据权利要求79所述的方法，其中，同时操作两个以上随机性支电路的动作包括同时操作两个以上随机性支电路，以执行舍选采样算法。
98.根据权利要求79所述的方法，其中，同时操作两个以上随机性支电路的动作包括同时操作两个以上随机性支电路，以执行重要性采样算法。
99.根据权利要求79所述的方法，其中，所述样本可以被用在解决立体视觉问题中。
全文摘要
提出了解决随机性问题的电路以及用于操作这些电路的技术。这些本能的随机性电路可以从针对特定随机性问题的所关注的概率分布来生成样本，并且可以被以任何适当的方式结合在一起来得出对于随机性问题的潜在解答。在一些实现方式中，随机性电路可以从以提供给随机性电路的输入数据为条件的条件概率分布来生成样本。电路可以由多个互连的随机性支电路构建，从而电路可以从联合概率分布或者从联合分布的边缘分布来生成样本。这些电路可以被用于实施随机性采样算法来解决随机性处理，并且可以包括同时进行操作的随机性支电路。
文档编号G01R31/28GK102016616SQ200980116076
公开日2011年4月13日 申请日期2009年3月4日 优先权日2008年3月4日
发明者维卡什·库马·曼西格卡, 艾瑞克·迈克尔·乔纳斯 申请人:麻省理工学院
专业数控铣床产品供应商
20年生产经验，实力工厂，精工品质，质量有保障
