不确定贝叶斯网络推理的二阶循环信念传播

SOLBP: Second-Order Loopy Belief Propagation for Inference in Uncertain Bayesian Networks

SOLBP：用于不确定贝叶斯网络推理的二阶循环信念传播

https://arxiv.org/pdf/2208.07368

摘要

在二阶不确定贝叶斯网络中，条件概率仅以分布形式已知，即概率的概率。差分法（delta-method）已被应用于扩展精确的一阶推理方法，以通过从贝叶斯网络派生的求和-乘积网络传播均值和方差，从而表征模型本身的认知不确定性（epistemic uncertainty）。作为替代，二阶信念传播已在多项式树（polytree）中得到证明，但尚未应用于一般有向无环图（DAG）结构。在本工作中，我们将循环信念传播（Loopy Belief Propagation）扩展到二阶贝叶斯网络的设置中，从而提出了二阶循环信念传播（Second-Order Loopy Belief Propagation, SOLBP）。对于二阶贝叶斯网络，SOLBP生成的推理结果与求和-乘积网络生成的结果一致，同时在计算效率和可扩展性方面更具优势。

I. 引言

概率图模型（PGMs），如贝叶斯网络（BNs）和马尔可夫随机场，用于编码变量之间的条件依赖关系。特别是，贝叶斯网络（第II节）使用有向无环图（DAGs）编码变量之间的依赖关系，并通过条件概率进行参数化。贝叶斯网络通常用于根据一组证据变量的值推断未观测变量的值的概率。标准贝叶斯网络仅考虑一阶不确定性，其中网络的条件概率被假设为精确已知。在这些贝叶斯网络中，一阶推理方法被用于预测网络的条件概率为点估计值。

相反，不确定贝叶斯网络（BNs）（第III节）是条件概率未知或仅以区间或分布形式已知的贝叶斯网络。贝叶斯网络中的不确定性类型可以有多种形式，从而导致不同类别的不确定贝叶斯网络，例如信度网络（credal networks）[2]、基于估值的系统（valuation-based systems）[3]、主观贝叶斯网络（subjective BNs）[4] 和二阶贝叶斯网络（second-order BNs）[5]。关于不确定贝叶斯网络的学习和推理的全面综述在文献[6]中提供。

特别是，二阶贝叶斯网络[5]考虑了二阶概率，其中条件概率的知识通过后验分布来编码，这些分布是概率的概率。二阶推理的目标是捕捉模型中的认知不确定性。我们不仅希望进行准确的推理，还希望量化我们对推断值的信心水平。二阶贝叶斯网络的精确二阶推理是不可行的。最近的研究[7]、[8]推广了涉及将二阶贝叶斯网络转换为求和-乘积网络（SPNs）（第II-B节）的二阶推理方法，然后使用差分法（delta-method）（第III-A节）通过一阶泰勒展开[9]、[10]来近似查询概率的方差。通过差分法扩展精确一阶推理方法以传播均值和方差，可以很好地近似查询概率的分布[5]、[7]。然而，随着贝叶斯网络规模的增大，求和-乘积网络的可扩展性较差。作为差分法近似的替代方法，蒙特卡洛采样可以在一阶SPN推理中更准确地估计查询分布，但计算成本更高。

对任意贝叶斯网络进行推理的最有效机制之一是将信念传播（belief propagation）（第II-A节）推广到包含环路的网络中，即所谓的循环信念传播（loopy belief propagation, LBP）[11]。在这里，环路是任意两个节点之间的多条路径。LBP通常（但不一定是）会收敛到正确的推理结果[12]。

我们的主要贡献在第IV节，即将LBP扩展到二阶贝叶斯网络的设置中，其中变量是离散值，条件概率服从狄利克雷分布（Dirichlet-distributed）。我们将这种方法称为二阶循环信念传播（Second-Order Loopy Belief Propagation, SOLBP）。事实上，使用带有差分法近似的SPNs会限制我们希望进行推理的贝叶斯网络的大小。通常用于二阶推理的技术，如信念传播，迄今为止仅限于多项式树（polytree）网络，其中图结构不允许包含环路。第V节的实验结果表明，当LBP正确收敛时，SOLBP生成的推理结果与SPNs中差分法生成的结果一致，证实了SOLBP的正确性，同时计算成本更低。最后，我们在第VI节总结了我们的结论。

II. 贝叶斯网络的背景知识

请注意，贝叶斯网络（BN）中概率的计算是条件概率集合Θ的非线性函数。以下小节回顾了计算（4）的方法。

A. 信念传播

信念传播在文献[1]中被引入，它通过消息传递高效地在多树结构（polytrees）上进行精确推理。即使贝叶斯网络不是树结构，也可能将其划分为多个树结构，从而引出连接树算法（junction-tree algorithm）[14]，该算法在无环网络中简化为信念传播。在信念传播中，贝叶斯网络中的每个节点既向相邻节点发送消息，也从相邻节点接收消息。具体来说，每个节点从其子节点接收λ消息，从其父节点接收π消息，然后利用这些消息计算传出的λ和π消息。

父节点X1向子节点Y发送的π消息编码了在来自X1的证据条件下父变量的概率。如果证据中包含Y的特定值，则内部πY值是一个独热向量，即πY(y)=δy,eY，其中eY是证据e中Y的值。否则，节点Y从其父节点X=[X1,...,XNp]收集其π消息。一旦节点Y接收到这些消息，节点Y就可以计算其内部π值：

其中，πY,Xi是从父节点Xi发送到节点Y的π消息。最初，只有那些没有父节点的节点可以计算它们的内部πY值，此时公式（5）简化为πY(y)=θy。同样，没有子节点的节点可以将其内部λY值分配为乘法融合的非信息性单位值，即λY(y)=1。

没有父节点的节点不会发送λ消息，类似地，没有子节点的节点不会发送π消息。

一旦网络中的所有节点都发送了它们各自的λ和π消息，每个节点Y将有一个与实例化变量相关的信念p(y|e)。实例化变量也称为证据，我们用粗体e表示，其中粗体符号用于表明证据是一个包含多个变量的向量。

信念传播旨在为多树结构贝叶斯网络提供精确推理。可以证明，对于多树网络，所有节点都能够相互发送它们的π和λ消息，并且通过公式（7）计算的概率与公式（4）等价。

一种扩展——循环信念传播（Loopy Belief Propagation）[11]——基于在包含环的图上运行信念传播的想法，使用固定点迭代过程，尽管环的存在并不能保证收敛。由于我们的贡献直接扩展了LBP，我们将在第四节中结合我们的提议详细说明其细节。

B. 用于推理的求和-乘积网络

另一种在贝叶斯网络（BNs）中进行推理的方法利用了一种已知的技术，即将贝叶斯网络转换为求和-乘积网络（Sum-Product Networks, SPNs），这一方法由Darwiche [15]首次提出。求和-乘积网络由一个有根的有向无环图（DAG）组成，其中包含内部操作节点（例如求和或乘积运算）和与指示变量相关的叶节点。为了将贝叶斯网络转换为求和-乘积网络，基本思想是引入指示变量λyi，i = 1, ..., n，使得

当与贝叶斯网络的参数变量θ结合时，我们可以为任何特定的贝叶斯网络写出一个规范多项式。给定规范多项式后，通过变量消去法，相对容易地形成一个相关的求和-乘积网络（SPN）图模型。具体的SPN结构并不是唯一的，它取决于变量消去的顺序。SPN中叶节点的指示变量表示从SPN导出的原始贝叶斯网络中变量的赋值状态。通过将SPN的指示节点设置为1或0，我们可以高效地计算p(e)，其中e表示证据，即观测变量的值。为了实现这一点，如果每个叶节点相关的条件概率与证据不一致，我们将叶指示变量的值设置为0。从SPN的叶节点到根节点的前向传播过程对所有未观测变量执行了（公式1）的边缘化：

III. 背景：不确定性贝叶斯网络

贝叶斯网络（BNs）的条件概率要么是主观的，即由领域专家提供，要么是从历史数据中学习得到的。这里，历史数据代表通过贝叶斯网络描述的分布采样的变量值的实例化。由于使用有限数据集进行学习，条件概率并不能被精确地知晓。尽管如此，条件概率通常通过最大似然估计从数据中估计出来，并在推理过程中被视为精确值。

二阶推理方法则认为，对条件概率的知识表现出认知不确定性，这种不确定性被编码为给定训练数据的条件概率的后验分布。正如在[13]中描述的，当数据集是完整的，即每个实例化中所有变量的值都可见时，条件概率的后验分布可以分解为狄利克雷分布的乘积，使得θYi|xi的后验分布是

A. Delta方法

一般来说，贝叶斯网络中的推理可以被视为将条件概率通过一个非线性操作传递，例如（公式4）。在[9]中引入的Delta方法通过一阶泰勒级数近似非线性操作输出的均值和方差。

在[10]中引入的MeanVAR使用Delta方法直接从条件概率的均值和方差计算（公式4）。作为替代，[5]中的二阶信念传播（SOBP）通过将Delta方法应用于每一步来计算π和λ消息的均值和协方差（见公式（5）-（9）），从而提供了一个更具可扩展性的解决方案。最后，[7]和[8]将Delta方法应用于概率电路中的每个求和和乘积操作。

Delta方法可以将一个精确的一阶贝叶斯网络（BN）推理引擎扩展为一个二阶推理方法，该方法能够计算查询变量的均值和协方差。根据公式（19），均值被视为一阶推理中的点概率。

任何精确的一阶推理方法都可以通过Delta方法扩展为二阶方法。例如，二阶信念传播最初在[5]中为二值多树贝叶斯网络开发。同样，[7]为一般离散值贝叶斯网络提供了求和-乘积网络的二阶扩展。需要注意的是，任何精确的一阶贝叶斯网络推理方法都是由操作组成的，这些操作将条件概率转化为推理结果。正如在[8]中所论证的，通过Delta方法计算的这些推理方法的方差是等价的，这是由于微积分的链式法则。

IV. SOLBP 方法

本文的主要贡献是通过 Delta 方法扩展循环信念传播（LBP）以适用于一般的贝叶斯网络（BNs），我们将其称为 SOLBP。这一扩展的动机在于信念传播比基于求和-乘积网络的推理更具可扩展性。当 LBP 收敛到精确推理时，它代表了一系列操作的组合，这些操作导致了精确的推理函数。然后，根据 [8] 中的链式法则论证，SOLBP 应该与其他精确的二阶扩展方法得到相同的方差。

基本概念是，所有从父节点到子节点以及从子节点到父节点的消息都被索引化。首先，消息被初始化为无信息的中性值。随机且不重复地选择一条消息。根据其依赖消息的当前值，更新该消息的均值和协方差。一旦所有消息的选择都已完成，一轮迭代就结束了。如果消息的均值变化很小，则计算终止。否则，将开始另一轮迭代。在一轮迭代中，一旦所有父节点或子节点的输入消息都已更新，节点将分别更新其内部的 π 或 λ 消息。算法 1 总结了 SOLBP 的步骤。每个节点 Y 发送给每个子节点 Z 的初始 π 消息被设置为使得单个消息的均值和协方差矩阵

一旦所有节点之间 π 和 λ 消息之间的二阶统计量以及内部值都已更新，一轮迭代就完成了。然后，通过公式(7)计算每个节点的查询概率的均值，协方差则由以下公式给出：

V. 数值评估

本节提供了实证证据，证明 SOLBP 确定的查询形式为 p(xi|e) 的均值和方差与通过二阶求和-乘积网络（SOSPN）计算的结果一致，如 [7] 和 [8] 中所述。此外，实证结果展示了 SOLBP 相对于 SOSPN 的计算效率，从而证明了 SOLBP 在较大有向无环图（DAG）贝叶斯网络中的优势。

为了进行适当的比较，我们在 MATLAB 中设置了一个测试框架，该框架以贝叶斯网络（BNs）作为输入。在每次实验中，基础事实贝叶斯网络的条件概率 θ 分别从均匀狄利克雷分布中采样。然后，从与基础事实贝叶斯网络相关的离散分布中采样网络变量的一个稀疏但完整的观测集。这些 Ntrain 个样本构成了精确贝叶斯学习过程的训练数据。在每次试验中，第一步是利用网络的 Ntrain 个完整观测来通过计数与变量值一致的样本数量来计算狄利克雷分布的参数（见第三部分）。

在推理步骤中，我们将一组特定的贝叶斯网络变量实例化为观测证据 e，其余变量保持未观测状态。然后，我们通过在具有基础事实条件概率的贝叶斯网络上运行求和-乘积网络（SPN）来推断 p(Yi|e)，以建立基础事实推理。最后，我们通过在通过 Ntrain 样本学习的不确定贝叶斯网络上运行 SOLBP 或 SOSPN 来推断查询的均值和方差。这些推断的均值和方差在 Nruns 次试验中被记录下来，我们使用 Nruns = 1000，并且每 100 次试验后生成一个新的基础事实贝叶斯网络。需要注意的是，尽管基础事实贝叶斯网络在 100 次试验中保持不变，但由于每次试验都会生成新的变量蒙特卡洛观测，因此每次试验都会学习一个新的不确定贝叶斯网络。

为了评估准确性，我们将 SOSPN 和 SOLBP 方法记录的均值和方差相互绘制。理想情况下，我们希望在所有情况下看到推理结果匹配，从而得到斜率为 1 的对角线。此外，我们遵循 [5] 中的方法，为每种二阶推理方法生成所需的置信边界发散度（DeCBoD）图，通过均值和方差建立置信边界。DeCBoD 确定了基础事实概率在推断概率周围显著性水平为 γ 的置信区间内的比率。对于 γ ∈ [0, 0.99]，我们计算在界内的比率并将其绘制在 γ 上。

我们在三组不同类型和大小的贝叶斯网络上测试了 SOLBP：（1）三节点网络；（2）小型循环网络；（3）大型循环网络。回想一下，SOLBP 的主要动机之一是，与 [7] 中的 SOSPN 方法类似，SOLBP 可以应用于包含循环的有向无环图（DAG），而不仅仅是多树。然而，我们首先希望验证 SOLBP 是否能够在多树上与 SOSPN 方法表现相当，因此我们在以下小节中展示了多树和包含循环的 DAG 的结果。我们在第五部分 D 节中讨论了相对计算工作量。

A. 三节点网络

我们首先测试了图1中所示的三个简单的三节点网络，其中变量为二值变量。SOLBP推断出的概率的均值和方差与SOSPN方法推断出的均值和方差进行了对比绘制。证据变量被选择为恰好与一条边相连的节点，无论边的方向如何，这些节点在贝叶斯网络图中用灰色标记以清晰显示。图2对比了两种方法对三节点链式网络推断出的均值和方差。其他两个网络也得到了类似的图表。

结果表明，对于这三种多树贝叶斯网络，SOLBP生成的推理结果在数值精度上与SPN方法生成的结果完全一致。鉴于推断出的均值和方差相匹配，我们也期望得到匹配的DeCBoD曲线。图3展示了图1(a)中三节点链网络的样本DeCBoD图，其中SOLBP的结果用红色叉号标识，SPN的结果用蓝色线标识。其余多树的DeCBoD图是类似的。DeCBoD曲线表明，实际置信度与期望置信度吻合得很好，这意味着推断出的分布（均值和方差）很好地校准到了真实的不确定性。

接下来，我们在两个基本的循环网络上验证了推理的准确性，这两个网络如图4所示。对于循环网络，SOLBP的迭代次数可能会根据使用的停止条件而影响最终的推断结果。在这里，我们运行SOLBP，直到当前迭代和上一次迭代中任何推断出的均值之间的绝对最大差异被限制在ε = 1×10⁻⁸以内。图4中用灰色阴影标记的观测节点是证据集中的节点。

图5对比了在钻石网络上SOLBP和SOSPN推断出的均值和方差的结果。三角形网络产生了类似的图表。图6展示了三角形和钻石贝叶斯网络的DeCBoD曲线。

图5表明，SOLBP和SPN方法产生的均值和方差的推断结果是相似的。然而，与多树网络不同的是，这些值并没有完全匹配，这意味着一些散点位于对角线之外。在这种特定情况下，对于所选择的证据变量，仅仅使用一个更严格的停止条件就可以在有限次迭代中实现完全匹配，我们已经验证了这一点。然而，对于一般性的多循环网络，SOLBP可能永远不会收敛到正确的值，这与一阶LBP的情况类似。另一方面，对于多树网络，经过几次消息传递后，所有节点都将发送和接收具有与精确推理方法一致的均值和协方差的λ和π消息。对于单循环贝叶斯网络，我们期望SOLBP在无限次迭代后最终收敛，类似于一阶LBP。尽管存在理论上的局限性，但实证证据表明，我们为SOLBP选择的停止条件能够产生接近SPN方法生成的值的近似均值和方差，对于小型单循环网络尤其如此。

C. 一个大型循环网络

在更实际的层面上，我们希望验证SOLBP在一个具有更多参数和多个循环的大型网络中的推理近似准确性。因此，我们创建了一个包含21个节点的贝叶斯网络，如图7所示。大约一半的贝叶斯网络节点被随机选为证据变量，并在图中用灰色阴影标记。尽管之前的实验仅限于二值贝叶斯网络变量，但我们在本实验中允许贝叶斯网络变量为二值或三值，以增加贝叶斯网络中的总参数数量。我们之所以对测试更多参数感兴趣，一方面是因为增加自由度可能会引入潜在的噪声，另一方面是为了展示SOLBP或SOSPN方法可能存在的潜在局限性。

在21节点网络上使用相同的实验设置运行SOLBP，得到的推断均值和方差如图8和图9所示。我们发现，尽管在较大的网络环境中引入了明显的噪声，但SOLBP的推断仍然相对准确地近似了SOSPN方法生成的推断值。正如在[11]和[12]中针对一阶LBP所讨论的那样，在具有多个循环的贝叶斯网络中，收敛并不能得到保证，这可能还取决于条件概率的值，而不仅仅是网络的结构。这种情况也适用于SOLBP。此外，证据节点的选择还会影响SOLBP收敛的速度。事实证明，人们可以简单地降低用作停止条件的阈值ε，或者强制SOLBP运行更多的迭代，这将提高SOLBP的近似精度。

D. 计算工作量

重要的是，SOLBP产生的推断结果与SOSPN方法产生的结果几乎完全相同，而且在计算工作量方面，SOLBP的可扩展性要好得多。根据[15]中的描述，求和-乘积网络（SPN）的大小会随着贝叶斯网络（BN）的大小呈指数增长。表I列出了运行时间指标，显示对于中等规模的贝叶斯网络，SOLBP能够比SOSPN方法多次更快地执行二阶推理过程。这证实了我们的直觉，即SOLBP应该比SPN方法更具可扩展性。

VI. 结论

我们展示了使用循环信念传播进行二阶推理。这使得二阶信念传播更具可扩展性，同时允许对所有贝叶斯网络进行推理。实证结果表明，SOLBP能够准确捕捉由于有限训练数据导致的认知不确定性。其校准精度与SOSPN相当。此外，SOLBP比SOSPN更具显著的可扩展性。

SOLBP与SOSPN之间的一致性会随着SOLBP的更多次迭代而增加，但计算效率会有所下降。幸运的是，DeCBoD曲线表明，即使在少量迭代的情况下，对于认知不确定性的估计也具有足够的准确性。未来的工作将系统地研究SOLBP在更大和更复杂的贝叶斯网络中的准确性和效率。此外，我们计划进行理论分析，以证明为什么SOLBP的方差应该与SOSPN相当。

原文链接：https://arxiv.org/pdf/2208.07368