分布式因子图形系统

摘要

一种在数据处理系统中实现因子图形的方法，该因子图形具有通过边彼此连接的变量节点和函数节点，该方法包括：在第一计算机系统上实现第一函数节点，所述第一计算机系统与第二计算机系统网络通信；建立到多个处理系统中的每个的网络连接；在所述第一函数节点处接收来自在所述处理系统中的一个上实现的变量节点的软数据，所述软数据包括值的估计和表示相信所述估计对应于正确值的程度的信息；以及从所述第一函数节点向所述处理系统中的所述一个发送表示所述值的更新估计的软数据。

说明书

相关申请的交叉引用

本申请主张2010年2月22日提交的题为“DISTRIBUTED  FACTOR GRAPH SYSTEM”的美国临时申请No.61/306,876的权益， 其内容通过引用合并于此。

技术领域

本公开涉及数据处理系统，更特别地，涉及用于概率计算的数据 处理系统。

联邦赞助研究声明

本发明的完成得到了国防高级研究计划局（DARPA）给予的 FA8750-07-C-0231下的政府支持。政府具有本发明的某些权利。

背景技术

如今，大量的计算机时间主要用于实施贝叶斯公式以计算概率。 例如，有在线的内容分发服务，其执行应用以用于预测消费者可能高 度评级的内容，已知消费者先前已经对内容进行了评级。类似地，存 在零售服务，其执行应用以用于预测消费者可能想要购买什么产品， 已知消费者以前已经购买过该产品。于是，有搜索引擎尝试基于检索 历史来预测什么链接可能相关。这些应用实质上已知在先事件的发生， 计算条件概率，即事件的概率。

其他概率应用包括用于猜测如何将网页从一种语言翻译到另一种 语言的程序以及大规模贝叶斯推理，包括雷达成像中的合成孔径重构、 医疗层析成像中的图像重构以及预测与疾病相关联的核酸序列。

在通信领域，当例如蜂窝电话中的嵌入和移动应用基于所接收的 带噪声的信号预测最初发射了哪些比特时，发生概率计算。在机器人 技术中，存在用于预测穿过困难地形的最可能最佳路径的应用。

发明内容

本发明基于如下认识，即分布式计算机系统可以用于用软数据 （soft data）实现将要用于概率计算的图形。这里使用时，软数据指 的是相信值的估计是正确值的程度。在因子图形中，关于估计有多可 能符合正确值的这些置信从一个节点传播到另一个节点。这样做时， 置信逐渐变强，直到它逼近近乎确定。以此方式确定值的过程通常称 为“置信传播”。

置信从一个节点到另一节点的传播可以跨越通过局域网络、广域 网络或者甚至诸如因特网的全球网络连接的分布式计算机系统来进 行。可以通过从节点抽取消息或者通过使节点将其消息推送到另一节 点来使置信从一个节点传播到另一节点。在因特网的情况下，置信可 以通过采用已有的RSS馈送机制被推送，且可以通过采用已有的超链 接机制而被抽取。

在一方面中，本发明呈现为一种用于实现因子图形的方法，该因 子图形具有通过边（edge）彼此连接的变量节点和函数节点，该方法 包括在第一计算机系统上实现第一函数节点，所述第一计算机系统与 第二计算机系统网络通信；建立到多个处理系统中的每个的网络连接； 在所述第一函数节点处接收来自在所述处理系统中的一个上实现的变 量节点的软数据，所述软数据包括值的估计和表示相信所述估计对应 于正确值的程度的信息；以及从所述第一函数节点向所述处理系统中 的所述一个发送表示所述值的更新估计的软数据。

在一些实践中，接收所述软数据包括从软等于节点接收所述信息。

另一些实践包括向所述变量节点提供用于生成与所述变量节点相 关联的所述变量的所述值的新估计的信息。

替选实践包括其中所述边通过网络连接实现的那些实践，其中所 述变量节点包括等于门的那些实践，以及其中向所述变量节点分配唯 一识别符的那些实践。

在另一些实践中，接收所述软数据包括激活与所述第一函数节点 对应的超链接，并且发送所述软数据包括激活与所述第一变量节点对 应的超链接。

本发明的另外一些方面包括一种计算机可读介质以及数据处理系 统，该计算机可读介质具有编码于其上的软件，该软件用于实现前述 方法中的任意方法，该数据处理系统包括服务器，该服务器配置成执 行其上编码有用于实现前述方法中的任意方法的软件的计算机可读介 质。

在另一方面，本发明的特征在于一种用于实现因子图形的分布式 计算机系统。这种系统包括：第一计算机系统，实现所述因子图形的 函数节点；第二计算机系统，实现所述因子图形的变量节点。所述第 一和第二计算机系统通过网络数据通信。

这些以及其他特征将从下面的详细描述和附图变得显然，附图中：

附图说明

图1示出用于实现数独因子图形的示范性DMPL代码；

图2示出图1实现的过程的迭代期间的数独阵列；

图3、4和5示出万维网解算器的示范性应用；

图6A和6B示出用于实现与图5中的示例对应的因子图形的 DMPL代码；

图7A和7B示出图5的示例中的电话位置的估计；

图8A、8B、8C、8D和8E示出连续的用于估计图5的示例中的 电话位置的概率分布；

图9示出用于实现因子图形的软等于门（soft equals gate）；

图10示出通过具有跨越网络的边（edge）而连接以形成更大因子 图形的两个因子图形；

图11示出经由网络彼此连接的两个因子图形之间的变量的复制； 以及

图12示出两个因子图形，其每个经由网络连接到第三因子图形的 公共等于节点（equals node）。

具体实施方式

标准编程语言如C和C++对于写代码而言是理想的，该代码旨在 汇编到且运行在独立计算机诸如PC上或者甚至在超级计算机集群 上。类似地，对于写将要在独立计算机上或者甚至在独立超级计算机 诸如Amazon云上解算的概率图形模型或生成模型而言，已有的概率 编程语言是良好的。

因为概率编程的重要性日益提高，在概率编程语言方面已经出现 了学术复兴。概率编程语言的早期示例是IBAL，其由Avi Pfeffer在 1997年创建。已知语言包括Alchemy、Bach、Blaise、Church、CILog2、 CP-Logic、Csoft、DBLOG、Dyna、Factorie、Infer.NET、PyBLOG、 IBAL、PMTK、PRISM、ProbLog、ProBT、R和S+。该列表中的大 多数其他编程语言在过去的5年内建立。关于概率编程语言的第一次 会议是NIPS 2008会议，其于2008年12月13日在加拿大的Whistler 召开。

一种这样的概率编程语言是分布式数学编程语言（DMPL），其 描述于2010年1月13日提交的题为“Implementation of Factor Graph  Circuitry”的美国临时申请No.61/294,740中。

DMPL已经用于建立许多有趣的演示。图1示出用于实现数独解 算器的示范性DMPL源代码。该DMPL源代码主要描述游戏的规则。 执行期间，解算器迭代地退火到约束的满意解。图2是在退火过程中 的中间点处解的快照。注意，某些方块中的猜测仍处于重叠中。

然而，还没有适于在跨越网络（network）诸如因特网连接的处理 器之间进行概率计算的基于万维网（web）的概率编程语言。也没有 万维网服务器用于进行概率计算，下文称为“万维网解算器”。

万维网解算器可以在实现其中约束节点和变量节点通过边而连接 的因子图形时被查看。典型地，约束节点将居于云中，变量节点将居 于本地设备上。给出变量之间的约束，因子图形提供已知的途径来确 定最可能的变量组合。这种因子图形的操作始于一组初始变量，并且 允许变量在多次迭代之后收敛到其最可能的值。

对于实现用于概率计算的因子图形的万维网服务，存在许多实际 应用。例如，在这种服务中，移动设备可以收集传感器数据流，诸如 音频和视频数据，并执行低水平推理（inference）以提取用于传输到 云的统计值。这些统计值可以包括特定事件发生的概率。云将接收来 自多个设备的数据流，如图3所示，然后跨越这些数据流联合地执行 推理。这种推理可包括活动（activity）集中和归类。云然后将边缘概 率（marginal probability）作为因子图形消息发送到移动设备从而为 进一步的推理做准备。

另一示例将涉及汽车中的引擎故障的预测，如图4所示。在这样 的例子中，每个用户将对云注册其汽车的年份、制造商和型号。然后 移动设备将收集引擎噪声音频和来自车载计算机的信息。移动设备将 使用该数据来提取用于传输到云的统计值。然后云将基于汽车的状况 来集中汽车，并将边缘概率作为因子图形消息发送到移动设备。这些 消息将使设备为寻找数据中的特定签名（signature）做准备。

另一示例是使多个适当配置的移动设备诸如个人数字助理或蜂窝 电话能够通过发射超声波并测量从相邻设备接收的声波的幅度来相互 三角测量它们的相对位置，如图5所示。用于实施该功能的示范性 DMPL代码示于图6A-6B中。

图7A-7B示出解（solution）从图7A中的两次迭代之后的估计进 展到图7B中的五次迭代之后的改善的估计。设备的实际位置示为蓝 十字，解算器的位置估计示为绿圈。解算器的连续估计实际上是两个 空间变量的概率分布。这些分布的方差（variance）随着解算器的每 次迭代而减小。五次连续的估计示于图8A-8E中。

在所有这些例子中，移动设备或其他客户机设备（诸如膝上计算 机、PC或嵌入式处理器）具有传感器或使它们能与物理世界互动的 其他I/O器件。

前面的例子还涉及计算“云”。计算云一般理解为可通过万维网 （例如通过因特网和/或无线网络）访问的一组服务器群。然而，计算 云也可以是较不复杂一些的装置，诸如结合图5描述的装置，其中“云” 可以简单地是电话附近的膝上计算机，其具有比电话更多的处理能力。 客户机和云因此能通过通信协议诸如http协议相互通信。

在云和客户机设备之间可以存在各种其他关系。例如，在一实施 例中，通信是单向的：客户机仅向云发送，而云不向客户机发送。在 另一实施例中，通信是双向或多向的。在另一实施例中，根本没有“云” 或“服务器”，而是相互通信的设备的“网状（mesh）”或“对等（ad hoc）”网络。

在一实施例中，概率程序员将建立将变量彼此关联的贝叶斯模型 （诸如概率图形模型或生成模型）。例如，在结合图5描述的蜂窝电 话声学定位示例中，该模型将是一组三角约束，已知关于一组电话相 对于彼此的距离的（噪声）信息，该三角约束强制该组电话的允许位 置的一致性。该模型可以居于云上。在该示例中，云可以仅是通过网 络与电话通信的膝上型计算机。

实现图5描述的过程的另一途径是对于每个客户机（即，每个电 话）具有仅带单个变量的概率图形模型，该变量表示客户机在欧几里 德空间中的位置。与该变量相关联的将是来自客户机的GPS接收器子 系统的客户机位置的先前估计。为了方便，将表示第一电话的位置的 变量称为“1”。第二和第三电话将分别具有名为“2”和“3”的变量 以识别它们的位置。

在概率图形模型中最流行的种类之一（Forney因子图形）中，变 量节点也称为等于门。然而，与它叫什么无关，变量节点的功能是相 同的：聚集对变量值的各种估计并且对于该值重分配一个新值。例如 对于二元变量，｛0、1｝中的X，等于门将是图9所示的形式。

每个客户机具有用于其位置的模型。该模型体现于单个变量节点 或等于门中。该节点可以估计客户机的位置，并且向外发送客户机位 置的消息（边缘概率）。该节点还可以接收消息，所接收的消息将影 响其对客户机位置的估计。

在常规概率图形模型中，这些客户机位置节点1、2...中的每个将 通过边（edge）连接到模型中的一个或更多约束节点（也称为“函数 节点”）。在图5的客户机定位示例中，约束节点将通过强制三角恒 等式对于欧几里德空间中存在的客户机而言保持为真，来强制客户机 的允许位置的一致性。用于实现这些约束的示范性DMPL源代码示于 图6A-6B中。

已知因子图形和一些或全部变量的在先信息，然后解算器算法（诸 如和-积算法）可以跨越图形中的边执行迭代消息传递以产生对客户机 位置的估计。这一般都发生于一台计算机上。在过去，算法如和-积通 过多个线程、批量列队等在多核计算机或超级计算机上并行。

然而，在图5的客户机定位示例中，客户机位置节点储存在与它 相关联的客户机上且在其上计算，而约束节点储存在云上且在其上计 算，云可以实现在附近的膝上计算机上。云还可以储存和计算依赖于 其他约束的先前知识的其他变量节点。在所示的特定示例中，一个约 束可以是全部客户机在具有已知尺寸和形状的桌子上。在该情况下， 对于所有客户机可以彼此离开多远将由限制。

没有容易的途径用已有的概率编程语言实现该系统，部分是因为 没有容易的途径在客户机与云之间或者客户机彼此之间传递消息。一 般必须超越概率编程语言并且发送概率到处理万维网通信的单独软 件。

前述缺点通过在图形中具有作为网络连接的边而得到克服。在该 方案中，每个变量接收URL或其他唯一识别符。概率程序本身如.XML 或.HTML文档一样，因为它居于万维网解算器上。万维网解算器在接 收到对变量值的请求，即对URL的请求时重新计算该变量。替选地， 该变量节点可以通过例如RSS馈送而被定期重新计算和通过辛迪加 发送。

该基于万维网的概率编程和概率解算基础结构使得建模者和解算 器的大规模分布式网络成为可能。例如，不同大陆上的气候建模者可 以每个建立一个他们大陆上的气象动力学模型。然后他们可以使用软 等于超链接（soft-equals-hyperlink）将他们的模型链接到其他模型。 如果他们将他们的模型安置于服务器上，并通过辛迪加发送他们的当 前气象预测，那么其他服务器将通过软等于超链接而使该信息对他们 可用。这些其他服务器又可以更新他们自己的预报。以此方式，概率 消息（边缘、颗粒、参数等）可以在网络上无缝传递，模型的所有部 分可以得到适当地更新，尽管居于不同位置的不同计算机上。

图10示出第一和第二因子图形，其中一个因子图形上的变量节点 连接到另一因子图形上的约束节点，连接边横跨网络。这两个节点之 间的消息传递通过超链接或RSS馈送方便地进行。净效果是更大的因 子图形，其存在是网络连接的结果。

图11示出第一和第二因子图形，其每个实现在经由网络彼此连接 的不同客户机上。第一因子图形中的一个变量节点经由两个客户机之 间的网络连接而有效地成为对于两个因子图形而言是公共的。虽然图 10所示的例子是简单的，但是显然的是，图10所示的架构可以容易 地扩展到多个因子图形之间的多个超链接。

图12示出类似的配置，其中两个客户机连接到服务器，公共变量 节点现在居于服务器上而不是在客户机上。图12中的变量节点可经由 超链接而从任何客户机访问。

在某些算法诸如Gibbs采样中，没有等于门。不过，有从相邻约 束节点接收更新的变量节点。在Gibbs采样万维网解算器中（以及在 类似实施例中），变量节点被超链接到约束节点且约束节点被超链接 到变量节点，而无需等于门。

在某些解算器算法诸如和-积算法中，图形中消息更新的顺序可以 使针对给定图形计算的最终结果产生差异。在常规实现中，消息更新 调度表通过单个计算机上的解算器算法而在全局控制之下。然而，在 分布式因子图形中，可能难以维持对更新特定消息和安排顺序的全局 控制。

洪水（flooding）调度是对于和-积算法而言最周知的调度。在洪 水调度中，从等于门到函数节点的初始消息被计算。然后，一旦这被 完成，消息就从约束节点传递到等于门。

针对上述调度问题的另一方法是具有集中服务器，其同步所有的 消息传递，如结合图5描述的那样。

当与较大且较少集中组织的系统一起使用时，集中服务器可具有 多个缺点。即使它可以跟踪巨大网络中的全部消息且以某种方式保证 它们遵守洪水调度，但是如果一个服务器失效或者不能从其变量传送 消息至它们的目的约束，或者其约束不能传送它们的消息至它们的对 应变量，则这种协议可能导致整个网络锁死。

针对上述调度问题的另一方法是随机调度，其中图形中的消息随 机更新。此类调度看起来更适于这里描述的网络上的分布式消息传递。

已经描述了本发明及其优选实施方式，主张为新颖的且通过专利 证书保护的本发明定义于所附权利要求及其等价物中。