智能控制导论大作业

智能控制导论大作业（二）

—推理方法综述

班级： 姓名： 学号：

推理方法综述

——贝叶斯网络推理算法综述

摘 要:

贝叶斯网络是一种有效的不确定性知识表达和推理工具,概率推理是其重要研究内容之一。经过二十年的发展,贝叶斯网络已经有一些比较有效的精确和近似推理算法。对迄今为止的贝叶斯网络推理算法研究进行综述,从复杂度、适用性、精度等方面对它们进行比较分析,指出每种算法的关键环节,为实际应用中算法选择和研究提供参考。

关键词:

贝叶斯网络;精确推理;近似推理

引 言:

贝叶斯网络是由Pearl于1986年提出的一种不确定知识表示模型,它以坚实的

理论基础、自然的表达方式、灵活的推理能力和方便的决策机制,成为人工智能、专家系统、模式识别、数据挖掘和软件测试等领域的研究热点。具有N个节点的贝叶斯网络可用BNN=νV,Eμ,P>表示,其中:是一个具有N个节点的有向无环径的贝叶斯网络。

贝叶斯网络推理是指利用贝叶斯网络的结构及其条件概率表,在给定证据后计算某些节点取值的概率。概率推理和最大验后概率解释是贝叶斯网络推理的两个基本任务。Cooper证明了贝叶斯网络推理是NP2困难问题[2],但是针对特定类型的贝叶斯网络,近年来研究人员在精确的和近似的推理算法研究中取得了很大进展。下文从关键环节、复杂性、适用性、精度等方面对目前贝叶斯网络推理算法及其发展状况进行综述。

图(DAG),节点Vi∈V是部件状态、观测值、人员操作等的抽象,有向边(Vi,Vj)∈E表示节点Vi与Vj之间存在直接影响或因果关系,Vi称为Vj的父节点,Vj称为Vi的子节点。P表示与每个节点相关的条件概率分布(CPD),它表达了节点与其父节点的关联关系。根据网络的连通特性,可将贝叶斯网络分为单连通网络和多

连通网络。单连通网络是指任意两个节点之间最多有一条有向路径的贝叶斯网络;多连通网络是指存在两个节点之间有不止一条有向路

1 精确推理算法

1.1 消息传递算法

消息传递算法,是Pearl为解决单连通网络的推理问题于1986年提出的[1]。算法主要思想是给每个节点分配一个处理机,每个处理机利用相邻节点传递来的消息和存储于该处理机内部的条件概率进行计算,求得自身的后验概率,并将消息传递算法计算结果向相邻节点传播 。消息传递算法计算简单 , 复杂度正比于证据传播过程 中经历的路径长度 , 但只适用于单连通网络 。对多连通网络,由于消息可能在环路中循环传递而不能进入稳态 ,无法推理 。

1.2 条件算法

条件算法是 Pearl 于1986年提出[1] , 算法基本思想是通过实例化一些条件节点,使多连通网络结构满足单连通 特性 ,然后消息传递算法进行计算 ,最后对所有实例化计算结果求数学期望 , 得到后验概率 。1992 年 ,Diez 对条件算 法进行了改进 , 提出局部条件算法,当网络中有些节点通过与或门连接时 ,该算法非算法 。该算法利用链式乘积规则和条件独立性 ,将联合概率分解为一系列参数化的条件概率的乘积,然后对公式进行变换 ,通过改变求和与乘积运算的次序 ,选择求和时节 点消元顺序 ,减少运算量 。作为符号概率推理算法的特例 , Zhang等提出变量消元算法、Dechter 提 出 桶 消 元 算 法、 Kask 等提出桶树消元算法 等 ,也是基于组合优化 , 在计算时引入了相关割集和 wiche 又提 出 递 归 条 件 算 法 ,该算法利用节点间的条件独立关系 ,,利用贝叶斯网络的 D2分离原则 , 减少消 常有效 。Shachter 等随后提出的全局条件算法 ,可以与联结树算法结合 , 有效降低 了计算的复杂度 。由于一般条件算法的计算量与条件节点 集的指数成正比 ,对条件节点集较大的网络 ,条件算法计算 效率非常低 。为此 Darwiche 提出了动态条件算法 ( dynam2 局部割集的概念 , 使算法只有线性的复杂度 ; 近年来 ,Dar2 多个子网络 ,子网络再进行独立的递归计算 ,最后将计算结 果进行整合 。此外 ,与或门条件算法 ( AND/ OR cut set co n2 最小条件节点集求解是条件算法的关键 。Suermondt和Cooper 证明了寻找最小条件节点集是 N P2困难问题 , 并提出了一种启发式算法寻找最小条件节点集

[ 9 ] 。目前普遍采用贪婪算法 、改进贪婪算法等方法寻找较小的条件节 点集 。

1. 3联结树算法

联结树算法是 Lauritzen 和 Spiegelhalter 于 1988 年提出的。该算法首先将贝叶斯网络转换为一个联结树 ( 联结树是一个无向树 ,每个树节点是无向图的称为团的最大全连通子 图) ,然后通过消息传递来进行计算 , 消息会依次传遍联结 树的每个节点 ,最终使联结树满足全局一致性 。此时 ,团节点的能量函数就是该节点包含的所有变量的联合分布函 noy2Shafer 算法和 Hugin 算法。这两种算法各有优 数 。根据消息传递方案的不同 , 可将联结树算法分为 She2 点 , Hugin 算法由于 避 免 了一些冗余计算 , 速 度 更快 , 而 Shenoy2Shafer 算法能有效解决更多推理问题 。后来 , Park 和 Darwiche 综合这两种算法的优点 ,对联结树算法进行了 改进 ,大大提高了算法效率。一般联结树算法中消息要 在连接团节点的两条弧上传递两次 ,Jensen 等在 1998 年提出了一种基于惰性评价的联结树推理算法 、条件图算法也是基于条件实例化的消息传递算法 。

联结树算法是目前计算速度最快 , 应用最广的贝叶斯 网络精确推理算法 , 适用于单连通和多连通网络的推理 。 该算法的计算复杂度随联结树中最大团节点规模增大呈指 数增长 。但寻找最大团节点最小的联结树是 N P2困难问 题 ,目前主要采用启发式算法寻找近似最优解 。

1. 4 符号概率推理算法

符号概率推理算法是 Shachter 于 1990 年提出基于组合优化的推理的算法 ,它们与符号概率推理算法的区别在于寻找最优消 元顺序的方式不同 。 符号概率推理算法简单通用 , 降低复杂度的关键在于寻找最优消元顺序 , 这是一个 N P2困难问题 。目前的方法 主要 有 最 小 缺 陷 法 、 最小 度 法 等 。最小缺陷法的主要思想是消去一 个节点的时候 ,如果它连接的两个节点之间没有边 ,就添加 连接边 ,计算先消去那些消去后需要添加的边的个数最少 的节点 。最小度法的主要思想是把有向无环图中度数最小 的节点放在消元顺序队列的末尾 , 然后从网络中移去该节 点 ,并连接该节点的所有邻居节点 , 重复上述操作 , 直到网 络中的所有节点被选择 。

1. 5 弧反向/ 节点缩减算法

弧反向/ 节点缩减算法是 Shachter 于 1990 年提出的一种推理算法。 该算