4.3.3 部分联结树推理算法
部分联结树(Partial Junction Tree，PJT)算法(以下使用缩写PJT表示)是联结树算法的一种变换，兼顾了联结树推理的精确性与效率，降低了对计算资源的要求。简单地说，联结树是一个贝叶斯网络结构的完整表示，而PJT则是贝叶斯网络中相互连接的一个子网，是贝叶斯网络结构的一部分，它是根据推理的具体需求，从贝叶斯网络对应联结树所截取出来的一个区域，而剩下的部分区域采取忽略其影响或者是由一个更为简单的结构来代替估算其影响的方式进行模拟。
1.基于PJT的推理过程
PJT的构建需要首先解决的问题有以下两个：
(1)PJT中包含贝叶斯网络中的哪些节点?
(2)PJT的规模有多大，其计算复杂性程度如何?
本书认为，利用PJT算法推理的主要过程包括：
(1)给定一个查询节点Q，寻找与贝叶斯网络结构中与Q相连接的其他节点，作为PJT中的节点，将这些节点与它们之间的边复制组织成新的子网W。其中，连接关系是指选取出的节点需要与查询节点或者与已选节点之间有“边”相连接。
(2)根据子网W中的节点构建PJT。
(3)建立一个近似模型M模拟贝叶斯网络中剩余节点对子网W的条件依赖关系。
(4)输入证据节点的值。
(5)计算近似模型M对于子网W的影响。
(6)计算由子网W构建的PJT的结构与相关参数的新值。
其中，第二步与第六步过程中应用的有关PJT的构建以及计算方法与普通的联结树是相同的。
在开始进行PJT构建的过程之前，PJT规模大小需要首先确定，这也是根据查询节点Q搜索连接节点的停止条件。PJT大小的规模限制条件可以从两种不同的角度进行定义。第一种，限制条件可以通过计算资源的范围来定义，例如以下几种指标：
(1)PJT包含贝叶斯网络的节点数；
(2)PJT中包含的串数；
(3)串集的状态空间大小，如PJT的宽度(Width)；
(4)PJT节点的状态空间数；
(5)PJT计算消耗的资源，如联结树代价(Junction Tree Cost，JTC)。
本书中使用的限制条件，重点关注了子网W的节点最大数，这也是最为直接的限制PJT规模的方式，因为上述的其他四个参数在没有构建PJT之前是不可用的。
其次，限制条件可以通过PJT的精度指标来制定。作为一种近似的贝叶斯网络推理算法，PJT具有一定的精度，随着PJT网络节点规模的不断缩小，其精度逐渐下降，因此，可通过划定PJT的精度指标，在保证其精度的范围以内，可以尽量考虑缩减PJT的网络规模。
2.最优化PJT
从保持贝叶斯网络结构所包含的信息量的角度，最优化的PJT是包含了贝叶斯网络中所有节点、边的联结树。然而，在保证计算效率的前提下，最优PJT应该是包含了这样节点的联结树，它们极大地提高了计算效率，并且最大限度地保证了计算的精度。因此，寻求一种有效的策略筛选出包含查询节点Q的节点集合是获得最优化的PJT的关键。假定PJT的规模限制条件为最多的节点数为n。以下几种搜索策略可供选择：
(1)从Q节点开始，基于广度优先的策略筛选n个节点；
(2)从Q节点开始，基于随机策略筛选n个节点；
(3)从Q节点开始，基于边权重最优策略筛选n个节点。
本书拟采取边权重最优策略筛选满足条件的节点构建PJT，以下首先引入一个概念定义。
定义4.5 互信息量(Mutual Information，MI)它是指两个变量Vi与Vj之间依赖性的一种度量标准，由于Vi已知或者取值发生变化，则Vj不确定性的减少程度。互信息量是变量之间相关程度的一种度量方式。
有了互信息量概念的定义，我们可以使用它来衡量节点之间边的权重关系，对于查询节点相关的节点集合Z0→Z1→Z2…Zm→Q，有向边Z0到Z1之间的边权重为：(https://www.daowen.com)
其中，Pl(Z0，Q)是Z0到Q的路径长度。
3.关于PJT以外节点的影响模拟
丢弃了贝叶斯网络中PJT以外的节点和边虽然降低了计算量，但同时也损失了许多有用的信息，降低了推理算法的精度。因此，需要考虑一种对于这些节点、边对于查询节点Q产生的影响模拟的方法。由于本书使用PJT对空间上下文的推理，依据构建贝叶斯网络的前提3，即当两个空间上下文相差的层数越过阈值D时，忽略两个空间上下文之间的推理关系，文中在构建空间上下文的PJT时，已经把阈值D考虑进节点的选择上来，因此本书忽略了PJT以外节点对于PJT的影响。
4.面向空间上下文推理的PJT构建算法
(1)算法输入：
①一个由空间上下文构建的贝叶斯网络G＝{NG，EG}，其中，节点集合NG，有向边集合EG；
②查询节点集合QG，NG；
③PJT包含的核心节点数u；
④搜索策略，T1。
(2)算法输出：
一个PJT近似表示原有贝叶斯网络G，包含了u个核心节点。
(3)算法过程：
①创建一个空的子网W＝{NW，EW}，NW＝EW＝空集。NW＝{CW∈MW}，CW表示的是核心节点的集合，MW是与之相关的马尔可夫空白节点集合。
②将查询节点QG，QW添加到CW中，此时，CW＝{QW}。
③将QG使用“w”加以标识，标明该节点已添加到NW中。
④选择核心节点：
for i＝2；i＜＝u；i＋＋
a)根据策略T1，从NG中选出与标识节点相连接的未标识的节点XG；
b)将节点XG添加到NW中；
c)使用“w”标识XG；
d)i＋＋。
⑤复制有向关系边和条件概率分布
对于任意两个已作标识的节点XG和YG之间的边E∈EG：
a)如果所有的父节点都被标识，直接取XG的条件概率分布；
b)如果只有部分父节点被标识，需要从与未标识的父节点处取条件概率分布的平均数。
最后，将这些条件概率分布与边复制到子网中去。
⑥对于新构建的PJT，使用标准的联结树算法重新进行一致性计算。
⑦返回PJT。