基于联结树的贝叶斯网的推理结构及构造算法

BN(贝叶斯网)被认为是人工智能研究中不确定性知识表示和推理的重要工具，广泛应用到复杂系统的建模等领域，成为人工智能研究的热点问题之一。然而直接在BN上精确推理与近似推理都被证明是NP完全的。因此把在BN上推理转变为在SS(二次结构)上的推理。SS是由JT（联结树)与BP(信念势)组成，构造JT大体分为三步即：把BN对应的有向无环图G转变为一个道义图G^M；把G^M转变为弦化图G^T，识别和选择G^T图的圈；连接圈和边建立JT。因而提出了建立G^M、G^T与JT的方法原理和算法。最后通过案例分析了G^M、G^T与JT构造过程。

Inference Structure and Construction Algorithms of Bayesian Network Based on Junction Tree

BN (Bayesian network) is considered the important tool for uncertain knowledge representation and inference in the course of researching artificial intelligence and applied to complex system modeling etc., become one of hotspot problems about artificial intelligence research. Direct exact and approximate inference in BN was proved to be NP complete problem, therefore inference in BN is changed into inference in SS (secondary structure). SS is consisted of JT (junction tree) and BP (belief potentials), three steps of constructing JT are changing directed acyclic graph G into moral graph ,GM; changing GM into triangulation graph GT, identifying and selecting cliques; connecting cliques and sides, constructing JT. Therefore methods and principles on constructing GM, GT and JT are put forward, algorithms realizing them are put forward in this paper. The processes on constructing GM, GT and JT are analyzed in the case in the last.