智能控制导论大作业

智能控制导论大作业（二）—推理方法综述班级：姓名：学号：推理方法综述——贝叶斯网络推理算法综述摘要:贝叶斯网络是一种有效的不确定性知识表达和推理工具,概率推理是其重要研究内容之一。经过二十年的发展,贝叶斯网络已经有一些比较有效的精确和近似推理算法。对迄今为止的贝叶斯网络推理算法研究进行综述,从复杂度、适用性、精度等方面对它们进行比较分析,指出每种算法的关键环节,为实际应用中算法选择和研究提供参考。关键词:贝叶斯网络;精确推理;近似推理引言:贝叶斯网络是由Pearl于1986年提出的一种不确定知识表示模型,它以坚实的理论基础、自然的表达方式、灵活的推理能力和方便的决策机制,成为人工智能、专家系统、模式识别、数据挖掘和软件测试等领域的研究热点。具有N个节点的贝叶斯网络可用BNN=νV,Eµ,P表示,其中:V,E是一个具有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/ORcutsetcon2最小条件节点集求解是条件算法的关键。Suermondt和Cooper证明了寻找最小条件节点集是NP2困难问题,并提出了一种启发式算法寻找最小条件节点集[9]。目前普遍采用贪婪算法、改进贪婪算法等方法寻找较小的条件节点集。1.3联结树算法联结树算法是Lauritzen和Spiegelhalter于1988年提出的。该算法首先将贝叶斯网络转换为一个联结树(联结树是一个无向树,每个树节点是无向图的称为团的最大全连通子图),然后通过消息传递来进行计算,消息会依次传遍联结树的每个节点,最终使联结树满足全局一致性。此时,团节点的能量函数就是该节点包含的所有变量的联合分布函noy2Shafer算法和Hugin算法。这两种算法各有优数。根据消息传递方案的不同,可将联结树算法分为She2点,Hugin算法由于避免了一些冗余计算,速度更快,而Shenoy2Shafer算法能有效解决更多推理问题。后来,Park和Darwiche综合这两种算法的优点,对联结树算法进行了改进,大大提高了算法效率。一般联结树算法中消息要在连接团节点的两条弧上传递两次,Jensen等在1998年提出了一种基于惰性评价的联结树推理算法、条件图算法也是基于条件实例化的消息传递算法。联结树算法是目前计算速度最快,应用最广的贝叶斯网络精确推理算法,适用于单连通和多连通网络的推理。该算法的计算复杂度随联结树中最大团节点规模增大呈指数增长。但寻找最大团节点最小的联结树是NP2困难问题,目前主要采用启发式算法寻找近似最优解。1.4符号概率推理算法符号概率推理算法是Shachter于1990年提出基于组合优化的推理的算法,它们与符号概率推理算法的区别在于寻找最优消元顺序的方式不同。符号概率推理算法简单通用,降低复杂度的关键在于寻找最优消元顺序,这是一个NP2困难问题。目前的方法主要有最小缺陷法、最小度法等。最小缺陷法的主要思想是消去一个节点的时候,如果它连接的两个节点之间没有边,就添加连接边,计算先消去那些消去后需要添加的边的个数最少的节点。最小度法的主要思想是把有向无环图中度数最小的节点放在消元顺序队列的末尾,然后从网络中移去该节点,并连接该节点的所有邻居节点,重复上述操作,直到网络中的所有节点被选择。1.5弧反向/节点缩减算法弧反向/节点缩减算法是Shachter于1990年提出的一种推理算法。该算法首先利用贝叶斯原理对网络进行弧反向计算,改变节点的条件概率表,然后将非证据节点中无子节点的节点删除,重复上述操作直到网络的证据节点和询问节点为父Cheuk和Boutilier在1997年对该算法进行了改进,提出了子关系,最后对网络进行消元计算,求得节点的后验概率。基于树结构的弧反向算法,并将其应用于动态贝叶斯网络的仿真,取得了很好的效果。弧反向/节点缩减算法的主要操作包括弧反向和节点缩减。节点缩减可以大大减小计算复杂度,但需要一定的条件,为此需要进行弧反向操作。而弧反向操作的计算量随需改变概率分布的节点数的增加呈指数增长,因而对于连接关系非常复杂的网络,弧反向的计算量非常大,导致推理速度下降。Cheuk和Boutilier提出的树结构的弧反向方法可以解决这个问题。1.6微分算法微分算法是Darwiche于1999年提出的。计算时,首先将贝叶斯网络表示为一个包含节点状态指示变量和条件概率变量的网络多项式,然后通过计算网络多项式中各变量的偏导数来进行概率推理。网络多项式一般是指数规模,计算时先要将指数规模的网络多项式转化为线性规模的运算电路,然后对该电路进行微分运算。Darwiche还将微分算法和联结树算法结合起来,对微分算法进行了改进，也对微分算法进行改进,并将其用于动态贝叶斯网络的推理。两种改进都取得了很好的效果。微分算法简单、容易理解,通过将指数级规模的多项式用线性规模的运算电路来表示并进行计算,提高了计算效率。在得到变量的偏导数之后,微分算法可以快速计算出节点的后验概率、节点和其父节点的联合后验概率、改变证据节点集中某些变量之后节点的后验概率等,微分算法还可以有效地对网络进行模型有效性和敏感度分析、参数学习等。2.近似推理算法2.1随机抽样算法随机抽样算法也称蒙特卡罗方法,是最常用的贝叶斯网络近似推理算法。该算法不利用条件独立性,也不考虑概率分布的特征,而是通过抽样得到一组满足一定概率分布的样本,然后用这些样本进行统计计算。目前主要有两类随机抽样算法:重要性抽样法和马尔可夫链蒙特卡罗方法。最早的、也是最简单的一种重要性抽样法是Henrion提出的概率逻辑抽样法,它对没有证据变量的网络进行推理时非常有效,当网络中加入证据变量时,尤其是当证据变量的先验概率极小时,这种推理算法收敛将会非常慢,因此Fung等提出了似然加权法解决此问题。此后,Shacther等又提出自适应重要度抽样、启发式重要性抽样等方法。马尔可夫链蒙特卡罗抽样算法包括吉布斯抽样算法等,当网络中没有极端概率时,这类算法非常有效，否则收敛非常慢。随机抽样算法虽然简单通用,但该算法不能像其他近似推理算法那样给出一个误差的边界,而只能给出一个概率边界,即样本量越大,统计结果与真实结果的误差小于误差限的可能性就越大。2.2基于搜索的算法计算的节点变量取值看作一个状态空间,其中一些状态对该算法运用启发式搜索在整个状态空间中搜索这些影响较大的状态,并用这些状态代替整个状态空间进行计算。在此基础上,Henrion提出了Top2N”抽样及累积算法，Poole提出了自顶向下的搜索算法、Santos提出了确定性近似和抽样及累计算法、Cooper提出了界限条件算法。基于搜索的算法的精度与所考虑的状态有关,算法效率取决于两个因素:(1)快速寻找对结果影响较大的状态;(2)确定满足精度要求的状态集合。前者与搜索策略有关,后者则在很大程度上取决于网络规模及其概率分布特征。2.3模型化简算法模型化简算法的主要思想是通过消除小概率变量、去除较弱的依赖性等手段,将模型进行化简,直到精确推理算法能有效运用为止,然后采用精确算法推理。已经提出多种模型化简方法,其中,局部化偏序评估算法通过从网络中移除某些节点变量来简化模型;有界条件算法通过忽略一些割集的实例来计算概率的界限;状态空间抽象算法通过减少条件概率表集合的势来简化模型;变量逼近算法，它通过将一些节点依次从网络中删除,直到网络足够稀疏,有效的精确推理算法可用为止;上下文描述近似算法,通过考虑网络中节点的前后关系结构,消除概率之间的差别来简化计算;Sarkar算法通过找到最近似网络的最优树分解来对网络近似推理算法络进行近似计算。模型化简算法实际上是一种推理策略,该算法通过化简网络,使计算量大大减小,但是对于比较大的网络,算法精度的估计和分析的计算量比较大,很难评价简化模型的有效性。2.4循环消息传递算法对于多连通网络,如果采用消息传递算法,那么消息就会循环传递而无法进入稳态,Murphy等于1999年对消息传递算法进行了改进,提出了循环消息传递算法(loopybe2对多连通网络进行推理。循环消息传递算法在多数情况下都能收敛,而且近似效果比较好。但当网络中存在极端的先验概率时,该算法phy等提出两种解决方法:一种方法是取计算结果振动区,使其作为一种近似的算法能pling)和混合马尔可夫链蒙特卡罗算法。计算结果会产生较大影响,而另外一些状态则影响甚微。基于搜索的算法将网络中需、的计算结果会在两个值之间振动而无法收敛。对此Mur2间的中值,但这种方法的精确性不高,因为精确值有时并不在中值附近;另一种方法是利用t时刻和t-1时刻消息的加权平均代替t时刻的消息进行消息传递,这种方法非常有效,而且推理的结果不受影响。Tatikonda和Jordan则通过确保定义在计算树上的吉布斯度量的唯一性,使循环消息传递算法收敛。3、贝叶斯网络推理算法的比从适用性、复杂性、精度、影响算法效率的关键因素等方面,对上述精确和近似贝叶斯网络推理算法进行了比较。从中可以看出,目前还没有一种算法具有普遍的适用性和优势,而是各有优缺点。因此,在实际应用中,要针对特定的问题选择一种最优或近似最优的算法。4、结论通过对贝叶斯网络推理中存在问题的分析,以及对贝叶斯网络推理算法的研究,我认为贝叶斯网络推理算法将会向以下几个方