数据分析方法及模型.ppt

1、1,分析技术及模型贝叶斯网,2,贝叶斯网（Bayesian Network，BN）,贝叶斯网是一种帮助人们将概率、统计应用于复杂领域、进行不确定性推理和数据分析的有效工具 它起源于20世纪80年代中期对人工智能中的不确定性问题的研究，已经成为人工智能的一个重要领域 近年来在国际上的影响不断扩大，对众多其它领域也产生了重要影响 贝叶斯网的主要应用是进行概率推理，即计算一些事件发生的概率 主要介绍贝叶斯网的基本概念、贝叶斯网推理、贝叶斯网学习,3,图论的基本概念,介绍贝叶斯网的定义之前，先引入几个图论中的基本概念 父节点、子节点：在一个有向图中，如果从节点X到节点Y有一条边，那么X为Y的父节点，Y

2、为X的子节点 邻居节点：一个节点的所有父节点和子节点称为它的邻居节点 根节点：没有父节点的节点 叶节点：没有子节点的节点,祖先节点：一个节点的祖先节点包括其父节点及父节点的祖先节点 根节点无祖先节点 B、E、A都是J的祖先节点,4,图论的基本概念,后代节点：一个节点的后代节点包括其子节点及子节点的后代节点 叶节点无后代节点 非后代节点：一个节点的非后代节点包括所有不是其后代节点的节点 有向环：在一个有向图中，若某节点是它自己的祖先节点，则该图包含一个有向环 有向无环图：不包含有向环的有向图,5,贝叶斯网定义,贝叶斯网是一个有向无环图 其中节点代表随机变量，节点间的边代表变量之间的直接依赖关系

3、每个节点都附有一个概率分布，根节点X所附的是它的边缘分布P(X)，非根节点X所附的是条件概率分布P(X/Par(X),结构图蕴含了条件独立假设，即给定一个变量的父节点集，该变量独立于它的非子孙节点 节点之间的连接关系代表了贝叶斯网络的条件语义,6,贝叶斯网定义,贝叶斯网也可以从定性和定量两个层面来理解 在定性层面，它用一个有向无环图描述了节点之间的依赖和独立关系 在定量层面，它用条件概率分布刻画了变量对其父节点的依赖关系 在语义上，贝叶斯网是联合概率分布的分解的一种表示：如果网络中的变量为 ，那么 的联合概率分布为各变量所附的概率分布的乘积，即 其中当 时， 就是边缘分布,7,贝叶斯网定义,贝

4、叶斯网的联合概率分布分解降低了概率模型的复杂度，使知识的获取与表达得以简化，为概率计算提供了很大方便,贝叶斯网 的优点： 是严格的数学语言，适合于计算机处理 直观易懂，方便人们讨论交流和建立模型 提供了人类推理过程的一个模型,因为依赖和独立关系是人们日常推理的基本工具，而且人类知识的基本结构也可以用依赖图来表达,8,贝叶斯网与概率推理,推理（inference）是通过计算回答查询（query）的过程 使用概率方法进行不确定性推理就是： （1）把问题用一组随机变量 来刻画 （2）把关于问题的知识表示为一个联合概率分布 （3）已知某些变量的取值，计算另外一些变量的后验概率分布 已知变量通常称为证据

5、变量，记为 （ ），它们的取值记为 ；需要计算其后验概率分布的变量称为查询变量，记为 ，（ ） 概率推理的根本任务就是给定证据变量集合后，计算查询变量集的概率分布，即：,9,贝叶斯网与概率推理,由于 和 可以根据联合概率P(X)的边缘化而求得，因此要在一些随机变量之间进行概率推理，理论上只需要一个联合概率分布P(X)即可 但是，直接使用联合概率分布P(X)进行不确定性推理的困难很明显，即它的复杂度极高 一般地，n个二值变量的联合概率分布包含2n-1个独立参数 所以，联合分布的复杂度相对于变量的个数成指数增长。当变量很多时，联合概率的获取、存储和运算都变得十分困难，推理变得不可行,10,贝叶斯网

6、与概率推理,贝叶斯网的提出就是要解决推理的复杂性问题，构造贝叶斯网的主要目的就是进行概率推理 从技术层面讲，贝叶斯网是一种系统地描述随机变量之间关系的语言，它利用变量间的独立关系将联合概率分布分解成多个复杂度较低的概率分布，从而大大降低了知识获取的难度和模型表达的复杂度，提高推理效率，使得人们可以应用概率方法来解决大型问题 贝叶斯网是概率论与图论相结合的产物，它一方面用图论的语言直观揭示问题的结构，另一方面又按照概率论的原则对问题的结构加以利用，降低推理的计算复杂度 利用贝叶斯网可以完成因果推理、诊断推理、原因关联推理及混合推理,11,贝叶斯网与概率推理,1.因果推理是从原因到结果的预测推理,

7、已知R=t，计算P(W=t/R=t),2.诊断推理是从结果到原因的预测推理,已知W=t，计算P(R=t/W=t),3.原因关联推理是对同一结果的不同原因之间的关联推理,已知R=t和S=t都是导致W=t的原因，已知W=t后，对R=t的信度为P(R=t/W=t)，如果又知道S=t，对R=t的信度为P(R=t/W=t,S=t),4.混合推理是上述3种类型的混合,已知C=t和W=t，计算P(S=t/W=t,C=t) 有因果推理，又有诊断推理,12,贝叶斯网与概率推理,贝叶斯网推理算法包括精确推理和近似推理两类 精确推理得到精确的概率值，近似推理得到近似的概率值 常用的精确推理算法有变量消元算法和团树传

8、播算法 变量消元算法是首先设置证据变量E的值，然后逐步消除非查询变量，得到一个关于查询变量A的概率函数，基于此函数计算P(A/E=e),证据F=0，计算P(A/F=0) 消去变量（C，E，B，D），获得h(A)，利用h(A)计算P(A/F=0),变量消元算法逐一处理推理问题，不考虑多次推理步骤共享，效率较低 团树传播算法能利用步骤共享加快推理，它能用大约两倍于变量消元法计算一个变量的后验概率的时间，计算出网络中每个变量的后验概率,13,贝叶斯网与概率推理,精确推理算法精度高，但是当网络节点众多并且连接稠密时，它们的计算复杂度高，不适用 近似推理算法降低了对精度的要求，以求在限定的时间内得到一个

9、近似解 随机抽样算法是一种常用的近似推理算法，其基本思想是从某个概率分布随机抽样，生成一组样本，然后从样本出发近似估计要计算的量 随机抽样算法可以分为重要性抽样算法和马尔科夫链蒙特卡洛算法（MCMC算法） 两种算法的主要区别在于重要性抽样算法产生的样本之间相互独立，而MCMC算法产生的样本却互相关联,14,重要性抽样法,N：贝叶斯网 X ：N中所有变量的集合 P(X)：N所表示的联合概率分布 E=e：观测到的证据 Q：查询变量 推理就是求Q取某个值q的后验概率P(Q=q/E=e) 设W是一些变量的集合，Y是W的一个子集，Z=WY，y是Y的一个取值，定义函数 按条件概率的定义，有 P(Q=q,E

10、=e)和P(E=e)可以表示成,15,重要性抽样法,使用重要性抽样法求解P(Q=q,E=e)和P(E=e)，需要选择重要性分布和抽样样本的拓扑序 有向无环图的拓扑序是图中所有节点的一个线性序，其中每个节点都在它的子节点之前出现 有2种具体方法：逻辑抽样法、似然加权法 1.逻辑抽样法 逻辑抽样法使用联合概率分布P(X)作为重要性分布 由于P(X)可以分解 因此可以按照贝叶斯网N的拓扑序对其中的变量逐个进行抽样：若待抽样变量是根节点，则按分布P(X)进行抽样；若是非根节点，则按分布P(X|Par(X)进行抽样,X的父节点 对X抽样时是已知的,16,重要性抽样法,抽样过程需要从一些单变量概率分布随机

11、抽样，这可以借助一个随机数产生器来实现,首先对根节点C抽样，抽样分布是P(C) 设抽样结果C=t 对R、S抽样，抽样分布是P(R|C=t)和P(S|C=t) 设抽样结果R=t, S=f 对叶节点W抽样 抽样分布为P(W|R=t,S=f) 设抽样结果W=t 最终生成的样本为C=t，R=t，S=f，W=t,17,重要性抽样法,假设通过抽样过程获得了m个独立样本D1，D2，Dm，其中满足E=e的有me个，而在这me个样本中，进一步满足Q=q的有mq,e，有,计算P(R=t|S=t） m=100，其中有75个满足S=f，舍弃；在另外满足S=t的样本中，有18个满足R=f P(R=t|S=t）18/25

12、=0.72 （精确值是0.7）,因此,在所有满足E=e的样本中，进一步满足Q=q的样本所占的比例 与E=e不一致的样本被舍弃,简单易行，当P(E=e)很小时，算法效率低，收敛速度慢,18,重要性抽样法,2.似然加权法 避免逻辑抽样因舍弃样本而造成的浪费 按拓扑序对每个变量X进行抽样：当X不是证据变量时，抽样方式与逻辑抽样法一样；当X是证据变量时，则以X的观测值作为抽样结果 保证了每个样本都与证据E=e一致，从而可以利用，不必舍弃,19,重要性抽样法,计算P(R=t|S=t） 对根节点C，从P(C)抽样，设抽样结果C=t 对节点S，因S是证据变量，故S=t 对R，抽样分布是P(R|C=t) ，设

13、抽样结果R=t 对叶节点W抽样，抽样分布为P(W|R=t,S=t) 设抽样结果W=t 最终生成的样本为D=C=t，R=t，S=t，W=t,20,重要性抽样法,假设通过抽样过程获得了m个独立样本D1，D2，Dm ：当变量取Di中的值时，这个函数的函数值 w(Di)：样本Di的权,因此,与逻辑抽样相比，似然加权法相当于为每个样本Di都赋予一个权重w(Di) 不同样本之间相互独立，每个样本都被利用，效率比逻辑抽样有很大提高,21,重要性抽样法,likelihoodWeighting(N,m,E,e,Q,q) 输入：N一个贝叶斯网；m样本量 E证据变量； e证据变量的取值； Q查询变量； q查询变量的

14、取值 输出：对P(Q=q|E=e)的近似 1.N的一个拓扑序 2.we0； wq,e0 3.for(i=1 to m) Di for(中的每个变量X) if(XE) xX的观测值 else x从P(X|Par(X)抽样的结果 end if,end for Di Di X=x wiXEP(X|Par(X)|Di wewe+wi if(D与D=q一致) wq,ewq,e+wi end if end for return wq,e/we,22,MCMC抽样法（吉布斯抽样法）,吉布斯抽样法首先随机生成一个与证据E=e相一致的样本D1作为起始样本，此后每一步都从当前样本出发产生下一个样本 设当前在i-1

15、步，为了从Di-1出发得到Di，抽样算法首先设Di=Di-1 然后按照某个顺序对非证据变量逐个进行抽样，改变Di中变量的取值 设Z是下一个待抽样变量，Y是Z的马尔科夫边界上的变量集合，yi是Y在Di中的当前取值 抽样算法根据分布P(Z|Y=yi)对Z进行抽样，并用抽样结果替代Di中Z的当前取值,23,MCMC抽样法（吉布斯抽样法）,计算P(R=t|S=t） 随机生成一个与S=t一致的样本D1 ，设D1=C=t,R=t,S=t,W=f 生成D2：从D2=D1=C=t,R=t,S=t,W=f 出发，对非证据变量逐个抽样，设抽样顺序为,(1)对C进行抽样，抽样分布为P(C|R=t,S=t)(0.44

16、4,0.556)，设抽样结果为C=f，于是D2=C=f,R=t,S=t,W=f (2)对R进行抽样，抽样分布为P(R|C=f,S=t,W=f)(0.024,0.976)，设抽样结果为R=f，于是D2=C=f,R=f,S=t,W=f (3)对W进行抽样，抽样分布为P(W|R=f,S=t)(0.9,0.1)，设抽样结果为W=f，于是D2=C=f,R=f,S=t,W=f,24,MCMC抽样法（吉布斯抽样法）,设抽样共得到m个样本，其中满足Q=q的有mq个，那么P(Q=q|E=e)mq/m 吉布斯抽样实际上是在贝叶斯网所有变量的联合状态空间中与E=e一致的那个子空间里进行随机漫步 它先任意选择一个起点

17、，以后的每一步都只依赖于前一步的状态，即上一个样本，因此，吉布斯抽样的不同样本之间不是相互独立的 在数学上，这是一个马尔科夫链，简称马氏链，它是一个离散时间随机过程，其基本性质为“给定现在，将来与过去无关” 吉布斯抽样的缺点是收敛速度慢，当网络中存在极端概率0和1时，无法保证马氏链存在平稳分布，此时，吉布斯抽样将给出错误结果,25,MCMC抽样法（吉布斯抽样法）,GibbsSampling(N,m,E,e,Q, ) 输入：N一个贝叶斯网；m样本量 E证据变量； e证据变量的取值； Q查询变量； q查询变量的取值 非证据变量的抽样顺序 输出：对P(Q=q|E=e)的近似 1. mq0 2.随机生

18、成一个与E=e一致的样本D1 3.if (D1与Q=q一致) 4. mq mq +1 5. end if 6. for (i=2 to m) Di Di-1 for(中的每一个变量Z),9. 设Y=mb(Z),yi是Y在Di中的当前取值，从P(Z|Y=yi)抽样 用抽样结果替代Di中Z的取值 end for if(Di与Q=q一致) mq mq+1 end if end for return mq/m,26,贝叶斯网学习,贝叶斯网学习是指通过分析数据而获得贝叶斯网的过程，它包括参数学习和结构学习两种情况 参数学习是指已知网络结构，只需确定网络参数 结构学习既要确定网络结构，又要确定网络参数 当

19、已知网络结构时，网络参数（节点间的条件概率）可以基于学习样本集通过统计计算获得。最大似然估计和贝叶斯估计是两种基本的估计方法 贝叶斯网结构学习算法大致可以分为两类：基于打分搜索的算法和基于依赖分析的算法 基于依赖分析的算法通过分析样本中蕴含的依赖关系来构造网络,27,贝叶斯网学习,基于打分搜索的算法使用一个评分函数来度量模型与样本数据的拟合程度，然后使用搜索算法把最优的模型结构找出来 基于打分搜索的算法要解决2个问题（1）给出评分函数，用于比较不同网络结构的好坏（2）给出一个搜索所有潜在网络结构的算法 常用的评分函数有：最优参数对数似然函数（Parameters Maximized Logli

20、kelihood Function）、Cooper-Herskovits（CH）评分、贝叶斯信息准则（Bayesian Information Criterion, BIC）、最短描述长度（Minimum Description Length, MDL）等 K2算法、蚁群优化算法、爬山法都是常用的搜索算法,28,MDL评分函数,D：数据集，包含m个采样值v1，v2，vm，每个vi都是一个n维向量 P(D)：联合概率P(v1，v2，vm) L(D,N)：网络N的MDL评分函数,网络参数个数,29,爬山法,爬山法可以使用任何评分函数，它的目标是要找出评分最高的网络结构 它从一个无边模型开始搜索，在

21、搜索的每一步使用加边（在网络结构中增加一条边）、减边（减去一条边）和转边（把一条边的方向翻转）操作对当前网络结构进行局部修改，得到一系列候选网络结构 然后计算每个候选网络的评分，并将最优网络与当前网络比较 若最优候选网络的评分大，则以它为下一个当前模型，继续搜索；否则停止搜索并返回当前网络 需要注意的是，加边和转边操作有一个前提，即不能在网络中形成环,30,爬山法,31,爬山法,LearnBN-HC(X,D,f,y0) 输入：X一组变量； D一组关于X的完整数据 f一个罚项似然度评分函数； y0一个初始贝叶斯网络结构 输出：一个贝叶斯网 1. y y0 ； y的参数的最大似然估计 2. old

22、Score f(y, |D) 3.while(true) 4. y* null; * null; newScore - for(每个对y做一次加边、减边或转边而得到的模型结构y) 6. y的参数的最大似然估计 tempScore f(y, |D) if(tempScorenewScore) y* y; * ; newScore tempScore,32,爬山法,end if end for if(newScoreoldScore) y y*; * *; oldScore newScore else return(y, ) end if end while,爬山法可能陷入局部最优或是爬不过坪区而

23、找不到全局最优 多次运行爬山法，每次都从一个随机产生的新结构开始，最后取各次运行结果中最优的那个作为最后结果 也可使用模拟退火、遗传算法等,33,贝叶斯网的应用,1.医疗诊断 从一系列临床观测和化验结果出发，对病人所患疾病的类别及其程度进行判断,PATHFINDER网络 疾病节点有63取值，代表淋巴结的63种不同的疾病 其它节点代表病人的症状 疾病节点是所有症状节点的父节点,用PATHFINDER网络进行诊断： 给定症状变量的取值，计算疾病变量的后验分布，然后把后验概率最大的那个疾病作为诊断结果,34,贝叶斯网的应用,2.工业应用 贝叶斯网在工业中的应用很广，涉及金融分析、产品设计、生产制作工

24、艺、工业过程监控管理、在线故障诊断、可靠性分析,故障诊断目的是找出导致一个控制系统失灵的故障部件 自动故障诊断往往需要在系统中嵌入各种传感器，以监视系统部件的运行状态，并通过实时推理，及时发现出故障的部件,汽车启动故障诊断贝叶斯网 导致汽车无法启动的原因有多个，故障诊断就是根据观测到的证据进行概率推理，找出后验概率最大的那个原因,35,贝叶斯网的应用,3.金融分析 在金融分析中，贝叶斯网被用于解决石油价格预测、证券风险与回报、风险投资决策、运筹风险分析等问题,证券风险回报分析的贝叶斯网 ABX、AEM、BGO是3家从事黄金开采的公司，图中表示各自的股票回报 回报都依赖于股票市场、黄金价格及与各

25、自股票相关的一个效应因子,基于这个贝叶斯网进行分析的结果是一个证券回报概率分布，进一步还可以计算回报的期望值、期望方差及风险等信息,36,贝叶斯网的应用,4.计算机系统 贝叶斯网在计算机系统中的应用包括程序理解、软件测试、垃圾邮件过滤、决策信息显示、信息提取、用户特征提取等,打印机故障诊断贝叶斯网局部 当出现打印颜色过浅的问题时，可能的故障有多个，包括墨粉不均匀、墨盒故障、数据出错、打印驱动故障等 这些故障可以采取措施修复：摇晃重置墨盒、换墨盒、关电源重启,37,贝叶斯网的应用,5.军事应用 战场上局势复杂多变，充满不确定性，涉及的问题往往具有实时性、动态性及离散和连续变量相混合的特点 贝叶斯

26、网在军事上的应用包括目标识别、多目标跟踪、自动防御、战场推理、训练仿真等,作战飞机身份识别的贝叶斯网 分类：飞机类型 雷达：飞机的雷达信号类型 身份：敌、友、中性 根据收集到的证据，计算飞机身份的后验概率分布，最终决定是否射击,38,贝叶斯网的应用,6.生态学 生态学家和野生动物学家面临的一个任务是分析人类活动对环境及濒临灭绝物种的影响 数据采集比较困难，需要有效地将珍贵数据与专家的主观评价结合起来支持有关决策,河口藻化现象的贝叶斯网 藻化现象指的是由于人为因素的影响使得某个水域的藻类植物过分生长的现象 藻化现象涉及在不同时空尺度上多个过程的相互作用，传统方法效果不好 网络描述了藻化现象中多个

27、变量之间的因果关系，为生态环境的监控和干涉后果的预测提供了可行的方法,39,分析技术及模型影响图,40,影响图（Influence Diagrams，IDs）,影响图是Howard 和Matheson于1984提出的一种不确定环境中描述复杂决策问题的图模型，它表达了变量间的依赖关系、条件独立关系和决策者的偏好信息 影响图在决策问题的定性描述和定量说明之间搭建了桥梁，既能被计算机处理，也容易被不同层次的技术人员理解 基于影响图，决策者在理解变量语义时冲突较小，不容易混淆，而且能够有效地进行决策分析和不确定性推理，找出能使自己获得最大期望效用的优化决策 由于影响图具有直观、表达信息量较多而模型规模

28、较小的优点，在许多领域得到了广泛应用 主要介绍影响图的基本概念、影响图的评价、影响图的学习,41,影响图（Influence Diagrams，IDs）,影响图包含图形部分和数字部分，图形部分也称为影响图结构，数字部分也称为影响图参数 图形部分用一个有向无环图定性描述了节点之间的依赖、独立、时序关系；数字部分定量表达了变量间的依赖强度和决策者的偏好,1.图形部分 影响图的图形部分用有向无环图（DAG）定义，记为G=(N,A)，其中是N节点集，A是弧集 N中的节点用于表示决策过程中的变量和效用，被分为三个子集，分别记为C，D和V：,42,影响图（Influence Diagrams，IDs）,C

29、=C1,C2,Cm是自然节点集。在图中用圆表示自然节点，代表决策过程中的随机变量，描述那些不被人们的行为影响的可能发生的事件 自然节点的状态只依赖于它的直接前驱，跟其前驱的前驱无关 D=D1,D2,Dp是决策节点集。在图中用矩形表示决策节点，描述决策系统可能采取的行动 每个决策节点的决策行动是可控制的行为，每个决策都产生一个回报 V=V1,V2,Vq是效用节点集。在图中用菱形表示效用节点，描述当前状态下决策产生的效用 每个决策节点和自然节点都包含有限种状态,43,影响图（Influence Diagrams，IDs）,A中的有向弧表达了节点间的依赖关系或决策时序，箭头所指的节点称为孩子节点，箭

30、尾处的节点称为父节点 弧有两种类型： 条件弧：条件弧指向效用节点和自然节点，代表效用节点和自然节点对其父节点的依赖关系。它们不蕴含节点间的因果关系或先后顺序。这意味着在决策过程中，决策者对于两个或多个自然节点中哪一个应该先于其它节点之前可以不作限制 信息弧：信息弧指向决策节点，蕴含先后顺序。决策节点进行决策的时候，其父节点的信息必须是已知的,44,影响图（Influence Diagrams，IDs）,2.数字部分 影响图的每一个自然节点C对应一张形如P(C|Pa(C)的条件概率表，它描述了自然节点表示的随机变量的不同状态的概率，概率表的值由事先知道的数据统计得到 自然节点Ci的条件概率表为C

31、i的每个状态ci指定一个条件概率P(ci|par(Ci)。 P(ci|par(Ci)满足P(ci|par(Ci)=1 每一个效用节点V都有一张效用分配表与之对应，它描述当前状态下采用不同行动的效用情况 f:uR（实数集） 决策节点不被量化，因为决策节点是决策者可控制的行为描述，决策节点的概率或可能性没有意义,节点C的直接前驱,节点V的直接前驱节点输出信息的所有可能组合,45,影响图（Influence Diagrams，IDs）,影响图的限制： 有向图不能有环 效用节点不能有后继,所有决策变量是有先后顺序的，该顺序与DAG中决策节点间的有向路径一致。如果影响图存在包含所有决策节点的有向路径，则

32、称该影响图是规则的 变量是非“忘记”的，即节点的状态一旦确定，就不再改变,46,影响图（Influence Diagrams，IDs）,一旦建立影响图，决策者就能利用它找到能使自己获得最大期望效用的决策 利用影响图寻找具有最大期望效用的决策的过程称为影响图评价 影响图评价方法分为直接方法和间接方法两类。直接方法直接在影响图上操作，间接方法将影响图转化为一种从属结构，然后评价从属结构 直接方法中使用的主要技术有节点约简和遗传算法；间接方法中使用的从属结构有贝叶斯网和决策树。使用贝叶斯网作为从属结构时，评价技术又包括Cooper变换、Shachter和Peot的算法、Zhang的算法,47,影响图

33、（Influence Diagrams，IDs）,节点约简方法适用于只有一个效用节点的影响图 约简可以通过冗余节点删除、自然节点删除、决策节点删除以及弧的反转等步骤来完成 当影响图只剩下效用节点时，删除停止 在逐个删除这些节点时不改变最优策略的期望值，并在删除节点的同时得到一系列最优决策 1.冗余节点删除 没有后继结点的自然节点（或决策节点）称为冗余节点。冗余节点对别的节点以及决策的总体目标没有影响，可以直接从影响图中删除,48,影响图（Influence Diagrams，IDs）,节点V变化后的效用,2.自然节点删除 如果效用节点V是自然节点C的唯一后继，那么C的删除可以通过信息传递保持价

34、值不变。C删除后，V接纳C的所有直接前序节点，V的新效用值为： 其中， 表示C删除前节点V的父节点集 3.决策节点删除 如果决策节点D是效用节点V的直接前序节点，且V的所有直接前序也是的D直接前序，那么节点D可以删除。D删除后，效用节点V的值取D的最大期望效用，即,49,节点约简,2. 自然节点间弧的转向 设弧（X，Y）从自然节点X发出指向自然节点Y ，通过信息传递将弧的方向翻转为（ Y ，X） ，同时两个节点相互接纳对方的直接前序节点 弧（X，Y）转向后，影响图的结构变化表示为：,50,节点约简,C中是冗余节点，直接删除,弧(S,R)的转向 添加弧(T,S)和弧(O,R),S的唯一后继是V

35、S被删除,由于S和O没有前序， 故弧(S,O)直接转向 故弧(S,R)直接转向,V的所有直接前序也是D的直接前序，D被删除,删除R,51,遗传算法,1. 遗传编码 评价影响图的目的是获得影响图的一个最优决策序列 因此一个遗传个体应表示序列中每个决策节点采用某种行动而得到的行动序列 可以采用实值编码方式 假设n为决策节点序中节点的数目，用长度为n的串代表一个个体，个体的每个基因位用整数描述，表示该位对应的决策节点选择的行为编号 每个个体就是决策序列上的一条行动路径,52,遗传算法,设影响图有D1，D2，D3，D4四个决策节点，它们的拓扑序为D1D2 D3 D4 设D1可以采取的行动为：d1(1)

36、,d1(2)；D2可采取的行动为：d2(1),d2(2),d2(3),d2(4)；D3的行动为：d3(1),d3(2)；D4的行动为d4(1) 整个个体空间的个体数为23 2 1=12 个体的形式为 d1 d2 d3 d4 1 1 1 1 1 2 2 1 2 3 2 1,53,遗传算法,设个体X为行为路径path j=(d1(1),d2(2),d3(2),d4(1)，即（1，2，2，1），其适应度函数F(X)为： F(X)=EU(path j)=EU1(d1(1)+EU2(d2(2)+EU3(d3(2)+EU4(d4(1),2. 适应度函数 适应度函数是评价个体好坏的依据 具有较高适应度值的行

37、为路径应是较优良的个体 决策行动路径的优良用其累积效用来衡量,54,遗传算法,A，B，C三个自然节点的可能状态为A=a1,a2,B=b1,b2,C=c1,c2,D1,D2两个决策节点的可能行动有D1=d1,d2,D2=e1,e2,55,遗传算法,56,遗传算法,3. 选择算子 设有n个个体，个体j即路径path j的选择概率Pj为： 选择方法可以采用轮盘赌方法 4. 交叉算子和变异算子 单点交叉 （2 3 2 1）-（1 2 1 1）（2 3 1 1）、（1 2 2 1） 原来的两条决策行为路径被两条新的决策行为路径取代 变异操作采用基位变异算子，随机选定某一基因位变异 （2 3 2 1） （

38、2 3 1 1）用D3的第一种行动代替第二中行动 5. 算法终止条件 进化代的数目达到预先设定的值时终止,57,Cooper变换,Cooper变换属于间接评价方法，它将影响图变换为贝叶斯网，利用贝叶斯网的推理来完成影响图的评价 Cooper变换适用于只有一个效用节点的影响图 变换过程中，所有节点间的依赖关系和所有自然节点及其参数保持不变，只是将决策节点和效用节点变换为自然节点 变换后，影响图变成了贝叶斯网，利用贝叶斯网的推理寻找最优决策 决策路径的最大期望效用可以通过由最后一个决策节点开始逆向地向第一个决策节点的方向进行计算而得到,58,Cooper变换,，,效用节点变换：效用节点变换为一个具

39、有false(f)或true(t)两个值的自然节点，该节点的条件概率为:,决策节点与效用节点的变化方法为： 决策节点变换：每个决策节点变换为一个等概率分布的自然节点,59,Cooper变换,，,通过贝叶斯网推理算法完成,决策节点Dk的最大期望效用和最优决策规则定义为：,决策节点Dk的最优决策是使MEU(Dk)获得最大值的d*,60,Cooper变换,61,影响图学习,使用影响图作为某一决策问题描述和求解的模型时，首先面临的问题就是影响图学习 影响图学习是指通过分析数据而获得影响图的过程，它包括结构学习和参数学习两种情况 结构学习的任务是确定有向无环图，即确定节点间的连接关系 参数学习是指对已知结构的影响图，确定自然节点的依赖函数和效用节点的效用函数,62,影响图学习,一种直接的学习方法是由领域专家对要建模的问题域内的各个因素进行分析和计算，然后给