对于许多实际应用问题来说,使用精确推断是不可行的,因此我们需要研究有效的近似方法。这种近似方法中,一个重要的类别被称为变分(variational)方法,将在第10章详细讨论。作为这些确定性方法的补充,有一大类取样(sampling)方法,也被称为蒙特卡罗(Monte Carlo)方法。这些方法基于从概率分布中的随机数值取样,将在第11章中详细讨论。

这里,我们考虑带有环的图中的近似推断的一个简单方法,它直接依赖于之前对树的精确推 断的讨论。主要思想就是简单地应用加-乘算法,即使不保证能够产生好的结果。这种方法被称为循环置信传播(loopy belief propagation)(Frey and MacKay,1998)。这种方法是可行的,因为加和-乘积算法的信息传递规则(8.66)和(8.69)完全是局部的。然而,由于现在图中存在环,因此信息会绕着图流动多次。对于某些模型,算法会收敛,而对于其他模型则不会。

为了应用这种方法,我们需要定义一个信息传递时间表(message passing schedule)。让我们假设在任意给定的链接以及任意给定的方向上,每次传递一条信息。从一个结点发送的每条信息替换了之前发送的任何沿着同一链接的同一方向的信息,并且本身是一个函数,这个函数只与算法的前一步的结点接收到的最近的信息有关。

我们已经看到,只有当结点从所有其他的链接接收到所有其他的信息之后,它才会沿着一条链接发送信息。由于图中存在环,因此这就产生了如何初始化信息传递算法的问题。为了解决这个问题,我们假设由单位函数给出的初始信息已经在所有方向上通过了每个链接。这样,每 个结点都处在了发送信息的位置上。

现在有许多可能的方法来组织信息传递时间表。例如,洪水时间表(flooding schedule)在每一步同时向两个方向沿着每条链接同时传递信息,而每次只传递一个信息的时间表被称为连 续时间表(serial schedule)。

根据Kschischnang et al.(2001),对于结点(变量结点或因子结点)和结点,如果自从上次向发送信息后,从任何其他的链接接收到了任何信息,那么我们说结点在到结点的链接上有一个信息挂起(pending)。因此,当一个结点接收到了它的一个链接发送的信息,就在所有其他的链接上产生了挂起的信息。只有挂起的信息需要被传送,因为其他的信息仅仅复制了同样链接上的前一条信息。对于具有树结构的图来说,任何只发送挂起信息的时间表最后会终止于一条在任意方向上沿着任意链接发送过的信息。此时,没有挂起信息,并且每个变量接收到的信息给出了精确的边缘概率分布。然而,在具有环的图中,算法永远不会终结,因为总可能存在挂起信息,虽然在实际应用中发现,对于大部分应用,它都会在一个合理的时间内收敛。一旦算法收敛,或者如果未观测到收敛时算法停止,那么(近似)局部边缘概率分布可以使用每条链接上的每个变量结点或因子结点最近接收到的输入信息的乘积进行计算。

在一些应用中,循环置信传播算法会给出很差的结果,而在其他应用中,它被证明非常有效。特别地,对特定类型的误差修正编码的最好的解码算法等价于循环置信传播算法(Gallager, 1963; Berrou et al., 1993; McEliece et al., 1998; MacKay and Neal, 1999; Frey, 1998)。

results matching ""

    No results matching ""