定义

贝叶斯网络由有向图和条件概率分布函数构成。前者说明了各种条件之间的影响关系，后者说明了各种取值的概率。后者的表现形式有两种，函数形式和表形式。1

在贝叶斯网络确定之后，可以根据观察到的数据来做一系列假设。这些假设会改变网络中的先验数据，并逐步影响整个网络。联合树算法将有向图转换为树，从而减少计算的难度。2

步骤1、将有向图转换为无向图。

将每个有共同子节点的父节点连接起来，把所有的有向边改为无向边

2、将无向图三角化。

三角化问题，是指让图中不存在超过3个点的环。如果有，则需要增加边来破除。理想的三角化问题是指，通过增加最少的边来达到三角化的目的。然而这个问题是NPC的。三角化问题的解决比较简单，指定一个节点顺序，然后查看与这个节点相连的几个节点，是否属于三角区域。如果不属于的话，那么他们之间是否存在边。如果不存在则增加边将他们连接即可。三角化的结果是否简单，取决于查看节点的顺序。

3、将三角化的图转换为树。

每个三角都代表了一个节点。两个相临的三角具有共同的边。这条边就成为两个节点之间的中间节点。如此就组成一张联通图。

4、寻找这张图的根，并寻找最大生成树，从而得到最终的结果。

对于每个evidence variable，把它放到包括这个变量的表里，然后把所有不满足这个evidence的entry全设为0。接着做一个自底向上的迭代，对于每个叶子节点，给它的父节点发送一个信息，即相关的表，父节点得到信息后就将其跟自己的表相乘，依次往上迭代，直到根节点。之后再做一个自顶向下的迭代，类似的，父节点向子节点发送信息，子节点得到信息后将其与自己的表相乘，依次往下迭代，直到所有叶子节点收到信息。如果我们需要询问一个变量对应的概率，我们就找到跟这个变量相关的完全子图，把这些table加起来去除掉其它变量的干扰，然后就得到了答案。(这个陈述很可疑，因为想去掉别的变量根本不需要把所有变量都遍历一遍。我们可以直接在表中合并其它变量对应的维度，就得到某个变量的概率了。

应用3/2片联合树算法基于动态贝叶斯网络处理动态不确定性问题的过程中推理是非常重要的，而推理算法的优劣决定着推理的执行效率。联合树可以作为贝叶斯网络的第二结构，是将贝叶斯网络中的变量按联合树特性进行改造的无向树，对于动态贝叶斯网络还要将时间片间的连接点进行联合，利用贝叶斯规则计算出用户所关心的变量或变量集的概率分布。该方法需要不断扩充时间片，对于较多的贝叶斯网络，寻找一个非常好的消去顺序NP-hard问题。该文提出一种较简单的3/2片联合树算法，在不需要限制消去顺序且只作一次扩展的条件下构造联合树，所以算法简单且具有较小的复杂度。3

基于图的邻接点优先的联合树算法贝叶斯网络是以概率理论为基础的不确定知识表示模型,联合树算法是一种应用广泛的贝叶斯网络推理算法。提出了基于邻接点优先的联合树算法，从图模型和计算效率两个方面对联合树算法(JT)和基于图的邻接点优先的联合树(AD-JT)算法进行推理时间的比较，实验表明：基于图的邻接点优先的联合树算法能够有效地处理大规模数据，极大地减少了消耗时间，计算效率有显著改进。4

这里提出的基于图的邻接点优先的联合树算法，就是基于这个思想，具体思路如下：

①需要关注的节点常常是少数几个，每次输入的证据往往也是为数不多的几个节点，不妨称它们为关键节点；

②可以在每一次输入证据和观察的时候确定关键节点，如果关键节点可以得到想要的结果，那么其它的节点就可以忽略掉；

③要找出推理出关键节点结果的必需的那些节点，不妨称它们为重要节点，可以确定的是关键节点都是重要节点，与这些关键节点相连的上一个节点也是重要节点，以此类推，直到所有的重要节点都被找到为止；

④利用邻接点优先算法，遍历每一个关键节点外的点，找出来所有的重要节点；

⑤找出所有的重要节点， 用这些重要节点建立一个精简过后的贝叶斯网络，这样的推理势必在空间和时间上有大量节约。