资源描述：
《智能控制导论大作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、智能控制导论大作业（二）—推理方法综述班级：姓名：学号：推理方法综述——贝叶斯网络推理算法综述摘 要:贝叶斯网络是一种有效的不确定性知识表达和推理工具,概率推理是其重要研究内容之一。经过二十年的发展,贝叶斯网络已经有一些比较有效的精确和近似推理算法。对迄今为止的贝叶斯网络推理算法研究进行综述,从复杂度、适用性、精度等方面对它们进行比较分析,指出每种算法的关键环节,为实际应用中算法选择和研究提供参考。关键词:贝叶斯网络;精确推理;近似推理引 言: 贝叶斯网络是由Pearl于1986年提出的一种不确定知识表示模型,它以坚实的理论基础、自然的表达方式、灵活的推理能力和方便的决策机制,成为
2、人工智能、专家系统、模式识别、数据挖掘和软件测试等领域的研究热点。具有N个节点的贝叶斯网络可用BNN=νV,Eµ,P>表示,其中:是一个具有N个节点的有向无环径的贝叶斯网络。贝叶斯网络推理是指利用贝叶斯网络的结构及其条件概率表,在给定证据后计算某些节点取值的概率。概率推理和最大验后概率解释是贝叶斯网络推理的两个基本任务。Cooper证明了贝叶斯网络推理是NP2困难问题[2],但是针对特定类型的贝叶斯网络,近年来研究人员在精确的和近似的推理算法研究中取得了很大进展。下文从关键环节、复杂性、适用性、精度等方面对目前贝叶斯网络推理算法及其发展状况进行综述。图(DAG),节点Vi∈
3、V是部件状态、观测值、人员操作等的抽象,有向边(Vi,Vj)∈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/ORcutsetcon2最小条件节点集求解是条件算法的关键。Suermondt和Cooper证明了寻找最小条件节点集是NP2困难问题,并提出了一种启发式算法寻找最小条件节点集[9]。目前普遍采用贪婪算法、改进贪婪算法等方法寻找较小的条件节点集。1.3联结树算法联结树算法是Lauritzen和Spiegelhalter于1988年提出的。该算法首先将贝叶斯网络转换为一个联结树(
7、联结树是一个无向树,每个树节点是无向图的称为团的最大全连通子图),然后通过消息传递来进行计算,消息会依次传遍联结树的每个节点,最终使联结树满足全局一致性。此时,团节点的能量函数就是该节点包含的所有变量的联合分布函noy2Shafer算法和Hugin算法。这两种算法各有优数。根据消息传递方案的不同,可将联结树算法分为She2点,Hugin算法由于避免了一些冗余计算,速度更快,而Shenoy2Shafer算法能有效解决更多推理问题。后来,Park和Darwic
