系统的有效贝叶斯网络模型 (1).docx

系统的有效贝叶斯网络模型贝叶斯网络在建立系统性能的概率论模型时是一个方便的工具，其方便性尤其体现在 当需要根据观测信息提升系统或其组分的稳定性的情况下在本文中，研究了以最小链接 集或者最小割集定义的系统性能的 BN 结构模型标准 BN 结构把系统节点定义为其组成 成分或最小链接/割集的子节点，从而会导致收敛结构，这种结构不利于计算，并且可能会 严重阻碍 BN 在实际系统中的应用本文发展了一套系统化的方法，它所创造的链状 BN 结构比标准结构的计算效率高几个数量级，对于计算存储量尤为如此这一构想运用了整 数最优算法以确定最有效的 BN 结构一些应用实例论证了所提方法并且量化了获得的计 算优势1. 引言 工程决策经常涉及对正在演化和具有不确定信息的系统状态的概率论评估比如说， 在一次自然灾害，比如说影响了一个城市社区的一次地震过后，必须要作出关于派遣救援 队和视察小组，继续使用或者关闭设施，修复的优先性以及恢复服务的决定，所有这些都 依赖与对不同的基础系统运行状态的评估这些评估会受到所获得信息的强烈影响，而这 些灾后信息却具有相当高的不确定性，并且可能会随着所观测到的不同系统组分状态的改 变而发生迅速的演化。

另一个例子是对正在恶化的系统的操控，在这里需要依据观察频率 和程度，以及维持、修复和更换行为作出一些决定，然而系统未来的性能和需求仍然是不 确定的在这两个例子中，需要有一种方法，以更新系统状态的概率评估，因为信息，通 常是不定类型，可以通过测量、检查以及其他对系统及其组成的观察得到 贝叶斯网络对于分析这类系统，尤其是当需要考虑变化不定的信息而更新系统概率模 型时是一个理想的组织架构BN 是一个包含描述随机变量的节点和描述节点概率相关性 的链接的图像模型变量可以描述系统组分的状态、它们的容量和需求BN 为建立组分 状态之间相关性提供了一个方便的方法，而这在大多数经典的系统可靠性分析方法之中都 是相当困难的此外，当输入一个或更多变量，比如说一系列组分的观察状态、容量和需 求，根据贝叶斯规则，信息就会通过网络传播并且更新其他随机变量的分布，比如其他组 分和系统的状态最后，通过添加决策和实用节点，BN 依据最大期望效益的原则，给出 一个便于作出决策的图表 这篇文章聚焦于发展一套使用 BN 为系统行为建模的系统化的方法，系统性能以他们 的最小链接集或者最小割集的形式定义这篇文章中描述的方法来源于我们在为受到地震 灾害影响的民用基础设施的行为建模的工作，它尤其重视了灾后风险评估和决策制定。

对 于这样的一个应用，有效的计算和近乎实时的对大型系统模型的推断是很有必要的此外， 相比于其他方法，比如故障树、事件树或者可靠性流程图等，被考虑的系统更容易用 MLS/MCS 方式来刻画虽然这篇文章的动机来自这个具体的应用，但是这里描述的方法 可以应用于很多 问题 BN 曾经被用于系统可靠性分析这些工作中的一部分以直觉的方式将系统建立为 BN 模型其他的则把故障树，或者可靠性流程图作为系统信息的根本来源一些论文为相对 简单的系统发展 BN，对于这些系统，计算量不是特别关键这项工作区别与先前工作的 地方在于，其定义了一种用于发展一个有效 BN 结构的系统化处理方式，使得在当 MLS 或 者 MCS 是系统信息的根本来源时，用于为复杂系统的可靠性建立模型这一方法在处理 具有拓扑性质的系统时尤为有用，在这样的系统里，系统的分解通常是通过 MLS 或者 MCS 来完成的尽管其他的作者已经使用 BN 为通过可靠性流程图拓扑定义的系统建立模 型，但却没有做出系统化的尝试以使得 BN 结构达到最优化，在处理大型、多状态系统时尤为如此传统的 BN 模型在尺寸和密度上都会随着系统尺寸的增加而迅速增加，所以即 便是对于中等尺寸的系统，计算和存储的需求都会使得模型变得不可行，特别是在使用具 有多状态节点的精确推算算法时。

考虑到这个缺点，在本文中我们针对二元和多元状态组 分，发展了一套生成有效 BN 拓扑的方法发展了一套离散最优化算法以最小化 BN 密度， 从而可以节约几个数量级的计算时间和存储容量 本文开篇对 BN 作出简要的介绍介绍被限定在对文章的后续内容有意义的几个方面 其次，陈述了为具有二元组分的串联和并联系统建模的有效贝叶斯网络构想这些构想然 后被拓展到具有二元和多元状态组分的一般性系统为了自动构建有效贝叶斯网络结构， 一个二元整数最优化问题被明确的表述出来此外，描述了两个启发式的改进方案以减小 最优化问题的尺寸最后列出了论述所提方法及其有效性的几个例子2. 贝叶斯网络简介 一个贝叶斯网络可以用包括一组描述随机变量的节点和一组描述概率依赖性的链接的 定向非周期性图表来描述本文中，我们局限与处理这样的 BN，其中所有的随机变量都 是离散的；对具有连续性随机变量的 BN 感兴趣的读者可以参考 Langseth考虑图 1 中的 简单 BN从 X1 和 X2 到 X3 的定向链接表示 X3 的分布是基于 X1 和 X3 定义的在 BN 术语中，随机变量 X3 称为随机变量 X1 和 X2 的子节点，而后者称为 X3 的父节点。

类似 的，X4 是 X1 的子节点，而 X5 是 X4 的子节点每一个节点与一组彼此独立且同时明确 的状态相联系，与离散随机变量的结局空间相对应每个节点都带有一个条件概率表 （CPT） ，提供了随机变量的条件概率函数根节点没有父节点，附带一个边缘概率表BN 中随机变量的联合分布以条件分布的乘积形式给出，例如：（1） 其中 Pa(Xi)是节点 Xi 的父集合，p 是 Xi 的 CPT，n 是 BN 中随机变量（节点）的数目 因此，对于图 1 中的 BN，联合概率分布函数为：（2）BN 在回答当观察到一个或多个变量时的概率性疑问时很有用处例如，假设在图 1 中的 BN 中，X3=x3,X4=x4,需要计算条件分布 p(x2|x3,x4)计算后面的分布时，首先要边 缘化（2）中的联合分布，以获得变量子集的联合分布：要计算的条件分布则为 p(x2|x3,x4)=p(x2,x3,x4)/p(x3,x4)虽然通过这种方法可能获得 更新的分布，但对非平庸的 BN 而言这却不是一个有效的计算方法一些用于在 BN 中作 出准确和近似概率推算的有效算法已经被发展起来这里列出了准确推算算法的一般性原 则，以强调发展有效 BN 拓扑的必要性。

BN 的有效性来源于将联合分布分解成局部条件分布，就像在等式(2)中的例子里一样 当对联合分布求和时，类似于等式(3)和(4)，并没有利用分解，且计算效率较低然而，通 过以乘积的形式写下联合分布，就有可能根据他们的分布和交换性质，重新安排这些求和 和乘积操作例如，等式(3)可以写成：求和操作可以被理解成节点的消除因为计算时从右往左进行的，等式(5)对应于 X5 的消除，接着是 X1 的消除很明显，解(5)的第二行比解第一行有效，因为求和是在较小 的区域中进行的遍及 X5 的求和只在 X4 和 X5 区域中（且在实际上可以被忽略，因为它 的结果是 1） 遍及 X1 的求和是在 X1、X2、X3 和 X4 区域中，为此有必要建立一个表 （称为 potential） ，表中的条目数量等于这些变量状态数的乘积通常情况下，potential 的 尺寸决定了推算算法的效率 Potentials，也即推算算法的效率，取决于节点消除的顺序计算上存在着最优消除序 列，所有这些序列都会导致相同的域集，例如在这一过程中产生的 potential 的域集都是相 同的与最优消除序列对应的域叫做 clique与这些 clique 相关的 potential 的总尺寸能很 好的反应出在贝叶斯网络中进行推算所需要的计算量，在本文中被用于评估和比较不同 BN 系统架构的效率。

虽然所有的精确推算算法都旨在寻找最优节点消除顺序，但是他们遵循不同的方式 特别值得一提的是，有些算法旨在为一个具体的推算任务最优化消除，而其他的算法，比 如说交叉树算法，则具有普适性利用后者，部分计算可以被重新利用我们感兴趣的是 一般性的推算应用这些算法中的一部分已经在现有的软件应用程序中得到了使用，为在 复杂贝叶斯网络中进行推算带来了便利 虽然这篇文章集中于提高精确推算算法的计算效率，但是这里所发展的方法对于通过 减小存储的 CPT 尺寸的近似算法而言同样有用就像 Nielsen 等谈到的，在当 BN 模型的 确定性部分可以用一个布尔型函数描述时，高级的布尔计算可以用于提高精确算法的运行 效率这样一种方法可以用于进一步提高我们通过拓扑最优化得到的 BN 模型的计算效率3.通过贝叶斯网络为系统性能建立模型 考虑一个具有 Nc 个组分的系统，第 i 个组分具有 ni 个离散状态系统的不同状态的个数从而是我们把通过组分状态直接定义系统状态的 BN formulation 称为naive BN formulation图2展示了这样的一种 BN，其中节点 Ci 定义的是第 i 个组分的状态， 节点 Ssys 定义的是系统的状态。

如果系统有 Ns 个离散状态，那么与该系统节点相关联的CPT 就具有 Ns*个条目虽然这种 formulation 曾经也被使用，但是对于一个系统，哪怕是只具有中等数量组分和组分状态的系统，CPT 的尺寸都会变得相当大以至于 BN 在计算上变得很棘手很明显，我们需要一种更加有效的 BN 架构作为上述 naive 方式的一种替代，在这篇文章中我们描述了另外四种 BN formulation 前面两种利用了最小链接集和最小割集，以处理具有二元组分的系统，但是利用了和在 naive formulation 中相同的收敛结构可以看出，MCS 架构对于具有多元状态组分的一类 系统同样是适用的我们接着又发展了两种架构，它们对具有二元状态的系统使用了 MCS/MLS，但是导致了远比计算目标有效的多的链状 BN 拓扑结构这些架构首先用在串 并联系统上，然后推广到一般性的系统这些有效的 MCS 架构对于具有多元状态组分的 一类系统同样是适用的4.使用最小链接集和割集的 BN 系统模型4.1 二元组分和系统 考虑一个具有二元组分的系统和系统状态，例如存活/失败状态最小链接集(MLS)是 组分的最小集合，其节点存活状态组成了系统的存活状态。

最小链接集 BN 架构在组分和 系统节点间引入了中间节点，其描述了 MLS 的状态，如图 3 所示TorresToledano 和 Sucar 用这样的一种 BN 架构为系统性能建模，尽管其方法比我们这 里使用的方法缺少规范性和一般性MLS 节点的二元状态被定义成，只有当它的所有的组 分存活时才处于存活状态，否则处于失败状态当任意一个 MLS 节点存活时，系统节点存活用 NMLS表示系统 MLS 的数量，NMLS,i表示在第 i 个 MLS 中组分的数量第 i 个 MLS 节点的 CPT 大小是 2NMLS,i+1，系统节点 CPT 的大小是 2NMLS+1很明显，当 MLS 数量 较大时，与系统节点关联的 CPT 尺寸也会变大对于 MLS 节点，当组分数量较大时也会 出现类似的问题 与 MLS 架构对应的是最小割集 BN 架构MCS 是组分的最小集合，其节点的失败组 成了系统的死亡在这种架构中，系统节点是代表 MCS 节点的子节点，每一个 MCS 节点 是代表其组分状态节点的子节点，如图 4 所示系统节点是所有 MCS 节点的串联系统（例如，如果至少有一个 MCS 节点处于失败状 态，那么系统节点就处于失败状态） ，然而每一个 MCS 都是其父节点的并联系统（例如， 所有的组分必须处于失败状态时，MCS 节点才会处于失败状态） 。

类似于 MLS 架构，处于 这种架构中的 CPT 会随着 MCS 数量的增加，且/或 MCS 中组分的数量（用 NMCS,i表示第 i。