智能控制导论大作业

《智能控制导论大作业》由会员分享，可在线阅读，更多相关《智能控制导论大作业（9页珍藏版）》请在金锄头文库上搜索。

1、智能控制导论大作业（二）推理方法综述班级：姓名：学号：推理方法综述贝叶斯网络推理算法综述摘要:贝叶斯网络是一种有效的不确定性知识表达和推理工具,概率推理是其重要研究内容之一。经过二十年的发展,贝叶斯网络已经有一些比较有效的精确和近似推理算法。对迄今为止的贝叶斯网络推理算法研究进行综述,从复杂度、适用性、精度等方面对它们进行比较分析,指出每种算法的关键环节,为实际应用中算法选择和研究提供参考。关键词:贝叶斯网络;精确推理;近似推理引言:贝叶斯网络是由Pearl于1986年提出的一种不确定知识表示模型,它以坚实的理论基础、自然的表达方式、灵活的推理能力和方便的决策机制,成为人工智能、专家系统、模式

2、识别、数据挖掘和软件测试等领域的研究热点。具有N个节点的贝叶斯网络可用BNN=V,E,P表示,其中:是一个具有N个节点的有向无环径的贝叶斯网络。贝叶斯网络推理是指利用贝叶斯网络的结构及其条件概率表,在给定证据后计算某些节点取值的概率。概率推理和最大验后概率解释是贝叶斯网络推理的两个基本任务。Cooper证明了贝叶斯网络推理是NP2困难问题2,但是针对特定类型的贝叶斯网络,近年来研究人员在精确的和近似的推理算法研究中取得了很大进展。下文从关键环节、复杂性、适用性、精度等方面对目前贝叶斯网络推理算法及其发展状况进行综述。图(DAG),节点ViV是部件状态、观测值、人员操作等的抽象,有向边(Vi,V

3、j)E表示节点Vi与Vj之间存在直接影响或因果关系,Vi称为Vj的父节点,Vj称为Vi的子节点。P表示与每个节点相关的条件概率分布(CPD),它表达了节点与其父节点的关联关系。根据网络的连通特性,可将贝叶斯网络分为单连通网络和多连通网络。单连通网络是指任意两个节点之间最多有一条有向路径的贝叶斯网络;多连通网络是指存在两个节点之间有不止一条有向路1精确推理算法1.1消息传递算法消息传递算法,是Pearl为解决单连通网络的推理问题于1986年提出的1。算法主要思想是给每个节点分配一个处理机,每个处理机利用相邻节点传递来的消息和存储于该处理机内部的条件概率进行计算,求得自身的后验概率,并将消息传递算

4、法计算结果向相邻节点传播 。消息传递算法计算简单 , 复杂度正比于证据传播过程 中经历的路径长度 , 但只适用于单连通网络 。对多连通网络,由于消息可能在环路中循环传递而不能进入稳态 ,无法推理 。1.2 条件算法条件算法是 Pearl 于1986年提出1 , 算法基本思想是通过实例化一些条件节点,使多连通网络结构满足单连通 特性 ,然后消息传递算法进行计算 ,最后对所有实例化计算结果求数学期望 , 得到后验概率 。1992 年 ,Diez 对条件算 法进行了改进 , 提出局部条件算法,当网络中有些节点通过与或门连接时 ,该算法非算法 。该算法利用链式乘积规则和条件独立性 ,将联合概率分解为一

5、系列参数化的条件概率的乘积,然后对公式进行变换 ,通过改变求和与乘积运算的次序 ,选择求和时节 点消元顺序 ,减少运算量 。作为符号概率推理算法的特例 , Zhang等提出变量消元算法、Dechter 提 出 桶 消 元 算 法、 Kask 等提出桶树消元算法 等 ,也是基于组合优化 , 在计算时引入了相关割集和 wiche 又提 出 递 归 条 件 算 法 ,该算法利用节点间的条件独立关系 ,利用贝叶斯网络的 D2分离原则 , 减少消 常有效 。Shachter 等随后提出的全局条件算法 ,可以与联结树算法结合 , 有效降低 了计算的复杂度 。由于一般条件算法的计算量与条件节点 集的指数成正

6、比 ,对条件节点集较大的网络 ,条件算法计算 效率非常低 。为此 Darwiche 提出了动态条件算法 ( dynam2 局部割集的概念 , 使算法只有线性的复杂度 ; 近年来 ,Dar2 多个子网络 ,子网络再进行独立的递归计算 ,最后将计算结 果进行整合 。此外 ,与或门条件算法 ( AND/ OR cut set co n2 最小条件节点集求解是条件算法的关键 。Suermondt和Cooper 证明了寻找最小条件节点集是 N P2困难问题 , 并提出了一种启发式算法寻找最小条件节点集 9 。目前普遍采用贪婪算法 、改进贪婪算法等方法寻找较小的条件节 点集 。 1. 3联结树算法联结树算

7、法是 Lauritzen 和 Spiegelhalter 于 1988 年提出的。该算法首先将贝叶斯网络转换为一个联结树 ( 联结树是一个无向树 ,每个树节点是无向图的称为团的最大全连通子 图) ,然后通过消息传递来进行计算 , 消息会依次传遍联结 树的每个节点 ,最终使联结树满足全局一致性 。此时 ,团节点的能量函数就是该节点包含的所有变量的联合分布函 noy2Shafer 算法和 Hugin 算法。这两种算法各有优 数 。根据消息传递方案的不同 , 可将联结树算法分为 She2 点 , Hugin 算法由于 避 免 了一些冗余计算 , 速 度 更快 , 而 Shenoy2Shafer 算法

8、能有效解决更多推理问题 。后来 , Park 和 Darwiche 综合这两种算法的优点 ,对联结树算法进行了 改进 ,大大提高了算法效率。一般联结树算法中消息要 在连接团节点的两条弧上传递两次 ,Jensen 等在 1998 年提出了一种基于惰性评价的联结树推理算法 、条件图算法也是基于条件实例化的消息传递算法 。 联结树算法是目前计算速度最快 , 应用最广的贝叶斯 网络精确推理算法 , 适用于单连通和多连通网络的推理 。 该算法的计算复杂度随联结树中最大团节点规模增大呈指 数增长 。但寻找最大团节点最小的联结树是 N P2困难问 题 ,目前主要采用启发式算法寻找近似最优解 。 1. 4 符

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

10、该节点的所有邻居节点 , 重复上述操作 , 直到网 络中的所有节点被选择 。 1. 5 弧反向/ 节点缩减算法弧反向/ 节点缩减算法是 Shachter 于 1990 年提出的一种推理算法。 该算法首先利用贝叶斯原理对网络进行弧反向计算 , 改变节点的条件概率表 ,然后将非证据节点中无子节点的节点 删除 ,重复上述操作直到网络的证据节点和询问节点为父 Cheuk 和 Boutilier 在 1997 年对该算法进行了改进 , 提出了 子关系 ,最后对网络进行消元计算 , 求得节点的后验概率 。 基于树结构的弧反向算法 , 并将其应用于动态贝叶斯网络 的仿真 ,取得了很好的效果 。弧反向/ 节点

11、缩减算法的主要操作包括弧反向和节点 缩减 。节点缩减可以大大减小计算复杂度 , 但需要一定的条件 ,为此需要进行弧反向操作 。而弧反向操作的计算量 随需改变概率分布的节点数的增加呈指数增长 , 因而对于 连接关系非常复杂的网络 ,弧反向的计算量非常大 ,导致推 理速度下降 。Cheuk 和 Boutilier 提出的树结构的弧反向方 法可以解决这个问题 。 1. 6 微分算法 微分算法是 Darwiche 于 1999年提出的。计算时 ,首先将贝叶斯网络表示为一个包含节点状态指示变量和条件概率变量的网络多项式 , 然后通过计算网络多项式中各变量的偏导数来进行概率推理 。网 络多项式一般是指数规

12、模 , 计算时先要将指数规模的网络 多项式转化为线性规模的运算电路 , 然后对该电路进行微 分运算 。Darwiche 还将微分算法和联结树算法结合起来 , 对微分算法进行了改进，也对微分算法进 行改进 ,并将其用于动态贝叶斯网络的推理 。两种改进都 取得了很好的效果 。 微分算法简单 、 容易理解 ,通过将指数级规模的多项式 用线性规模的运算电路来表示并进行计算 , 提高了计算效 率 。在得到变量的偏导数之后 , 微分算法可以快速计算出 节点的后验概率 、 节点和其父节点的联合后验概率 、 改变证 据节点集中某些变量之后节点的后验概率等 , 微分算法还 可以有效地对网络进行模型有效性和敏感度

13、分析 、 参数学 习等 。2.近似推理算法2. 1 随机抽样算法 随机抽样算法 也称蒙特卡罗方法 ,是最常用的贝叶斯网络近似推理算法 。该 算法不利用条件独立性 ,也不考虑概率分布的特征 , 而是通 过抽样得到一组满足一定概率分布的样本 , 然后用这些样 本进行统计计算 。目前主要有两类随机抽样算法 : 重要性 抽样法和马尔可夫链蒙特卡罗方法 。最早的、也是最简单 的一 种 重 要 性 抽 样 法 是 Henrion 提 出 的 概 率 逻 辑 抽 样 法, 它对没有证据变量的网络进行推理时非常有效 , 当 网络中加入证据变量时 , 尤其是当证据变量的先验概率极 小时 ,这种推理算法收敛将会非

14、常慢 , 因此 Fung 等提出了 似然加权法解决此问题 。此后 , Shacther 等又提出自适 应重要度抽样 、 启发式重要性抽样等方法 。马尔可夫链 蒙特 卡 罗 抽 样 算 法 包 括 吉 布 斯 抽 样 算 法 等 ,当网络中没有极端概率时 , 这类算法非常有效，否则收敛非常慢。 随机抽样算法虽然简单通用 , 但该算法不能像其他近 似推理算法那样给出一个误差的边界 , 而只能给出一个概 率边界 ,即样本量越大 ,统计结果与真实结果的误差小于误 差限的可能性就越大 。 2. 2 基于搜索的算法 计算的节点变量取值看作一个状态空间 , 其中一些状态对 该算法运用启发式搜索在整个状态空间

15、中搜索这些影响较 大的状态 ,并用这些状态代替整个状态空间进行计算 。在此基础上 , Henrion 提出了 Top2N ”抽样及累积算法 ，Poole 提出了自顶向下的搜索算法 、 Santos 提出了确定性近似和抽样及累计算法、 Cooper 提出了界限条件算法。 基于搜索的算法的精度与所考虑的状态有关 , 算法效 率取决于两个因素 : ( 1) 快速寻找对结果影响较大的状态 ; ( 2) 确定满足精度要求的状态集合 。前者与搜索策略有关 ,后者则在很大程度上取决于网络规模及其概率分布 特征 。 2. 3 模型化简算法 模型化简算法 的主要思想是通过消除小概率变量 、 去除较弱的依赖性等手

16、段 ,将 模型进行化简 ,直到精确推理算法能有效运用为止 ,然后采 用精确算法推理 。已经提出多种模型化简方法 , 其中 ,局部化偏序评估算法通过从网络中移除某些节点变量来简 化模型 ; 有界条件算法通过忽略一些割集的实例来计算 概率的界限 ; 状态空间抽象算法通过减少条件概率表集 合的势来简化模型 ; 变量逼近算法， 它通过将一些节点 依次从网络中删除 ,直到网络足够稀疏 ,有效的精确推理算 法可用为止 ; 上下文描述近似算法 , 通过考虑网络中节 点的前后 关 系结 构 , 消 除 概 率 之 间 的 差 别 来 简 化 计 算 ; Sarkar 算法通过找到最近似网络的最优树分解来对网络近似推理算法 络进行近似计算 。模型化简算法实际上是一种推理策略 ,该算法通过化简网络 ,使计算量大大减小,