人工智能原理第7章不精确推理.ppt课件

资源描述

《人工智能原理第7章不精确推理.ppt课件》由会员分享，可在线阅读，更多相关《人工智能原理第7章不精确推理.ppt课件（108页珍藏版）》请在金锄头文库上搜索。

1、人工智能原理人工智能原理第第7 7章章不精确推理不精确推理本章内容本章内容7.1 不精确推理的必要性7.2 贝叶斯概率推理7.3 贝叶斯网络7.4 可信度方法*7.5 模糊推理参考书目第7章不精确推理7.1 不精确推理的必要性不精确推理的原因 / 方法第7章不精确推理为什么要不精确推理为什么要不精确推理做不精确推理的原因有多种：推理所需的信息不完备：竞争双方不知道对方信息背景知识不足：疑难病症的机理多种原因导致同一结果：疾病的诊断信息描述模糊：目击者对嫌疑犯的描述信息中含有噪声：做假帐，虚假统计报表，采集数据当中的噪声（雷达、声纳/化验）等第7章不精确推理4不精确推理的原因不精确推理

2、的原因规则是模糊的：定性描述，如“如果刑事犯罪猖獗，就应加大打击力度”等推理能力不足：天气预报的计算解决方案不唯一：多个方案如何选优的问题两种不确定性环境的不确定性智能体几乎从来无法了解关于其环境的全部事实反映环境的知识的不确定性过于复杂而无组织知识粥(knowledge soup)第7章不精确推理5不确定环境下的智能体行动不确定环境下的智能体行动从智能体角度看，他不得不在不确定的环境下行动克服这种不确定性的解决方案1)条件规划2)使用简单而不完全正确的模型大部分时间模型或者规划可行，但有时会出现矛盾理性决策依赖于各种目标的相对重要性，也依赖于这些目标被实现的可能性第7章不精确推理6不确定

3、性下的决策不确定性下的决策不确定性的存在改变了智能体进行决策的方式智能体要在各种规划的不同可能结果之间进行选择(有所偏好)一种结果是一个被完全确定的状态任何状态对于智能体来说都具有一定程度的有用性即效用，智能体将偏好具有更高效用的状态决策理论=概率理论+效用理论理性智能体选择能产生最高效用的行动第7章不精确推理7不精确推理不精确推理现实不确定性需要不精确推理，将数值计算引入推理过程继续使用逻辑联结词真假值概率化，以表示某种可靠程度在推理的前提和结论之间建立概率公式（解释）前提称为证据，结论称为假设应用：专家系统中的推理网络 (PROSPECTOR系统/ MYCIN系统)第7章不精确推理8贝

4、叶斯网络贝叶斯网络(Bayesian network)(Bayesian network)智能体使用概率对行动结果(用事件之间的联系表示)进行预测，进而选择期望效用最高的行动贝叶斯网络(也叫贝叶斯信念网)是一个节点标注了定量概率信息的有向图，反映了一个事件对于另一个事件的影响程度/表示了变量之间的依赖关系和概率信息贝叶斯网络是事件之间联系的全面而形象的表示第7章不精确推理9知识粥知识粥(Knowledge Soup)(Knowledge Soup)现实世界的复杂性和不确定性反映在智能体内部异质的、不固定的、经常不一致的知识称为知识粥“粥体”包含小块(small chunk)对应于规则、框架等

5、，大块(large chunk)对应于整个理论这些“块”的内部是一致的，“块”之间可以是不一致的从整体来说，知识往往具有这样的特性模糊、不确定、随机、无知第7章不精确推理107.2 Bayes概率推理7.2.1 有关概念和公式7.2.2 几率和似然比7.2.3 似然比应用第7章不精确推理主观主观BayesBayes主义主义主观Bayes主义：将概率推理与归纳逻辑的解释联系起来，现实世界的一些因果关系可以形成一种信念，它并非在所有场合下都正确，可称为部分信念 / 表示这种信念的最好方法是概率方法，对概率的解释有若干种，其中Bayes创立了主观解释，也称为主观Bayes主义其要点是：概率是个人

6、的一种合理置信度，每个人的估计(概率)虽然各不相同，但应该满足概率的基本规律和其他某些客观规律，因而是合理的第7章不精确推理127.2.1 7.2.1 有关概念和公式有关概念和公式在Bayes概率推理中，推理规则表示为if E(前提/证据) then H(结论/假设)(LS, LN)规则强度用LS/LN表示(也称为似然比) / 其不精确推理过程是：根据证据E的概率P(E)，利用规则的LS和LN，把结论的先验概率P(H)更新为后验概率P(H|E)，因而也称为概率传播第7章不精确推理13BayesBayes条件概率条件概率Bayes条件概率：令假设H的先验概率为P(H)，P(H)是指定的 /

7、证据E为真时H的条件概率为P(H|E)，P(H|E)的一部分是指定的，一部分是根据P(H)和指定的P(H|E)计算出来的，这部分计算出的概率称为后验概率条件概率P(H|E)可看作以一定概率成立的EH的推理规则第7章不精确推理14概率公理概率公理Bayes概率服从如下公理(Kolmogorov公理)：(1)0P(H)1(2)P(H=T)=1 / P(H=F)=0(3)P(HG)=P(H)+P(G)P(HG) / 当H和G互斥有P(HG)=P(H)+P(G) 特别有P(H)+P(H)=1 / 一般地有P(Hi|E)=1即证据E下Hi的全体构成了一切可能的假设，其中任意Hi和Hj (ij)互斥这样

8、的概率公理是不能违反的(p364论证)第7章不精确推理15条件概率公式条件概率公式条件概率公式P(H&G)=P(H|G)P(G)=P(G|H)P(H)该公式指明了H和G两个假设之间存在着相关性如果H和G相互独立，则P(H|G)=P(H)P(G|H)=P(G)P(H&G)=P(H)P(G)第7章不精确推理16全概率公式全概率公式全概率公式：一个假设的先验概率可以表示为两个假设的概率，其中后面一个假设遍历各种可能性且各个可能性之间是独立的，则有P(H)=iP(H&Gi)=iP(H|Gi)P(Gi)其解释为：假设H的概率等于从各种证据提供的信息所推出的条件概率之和 / 证据满足独立性和完全性这个

9、公式也称为全联合分布第7章不精确推理17边缘化边缘化上述全概率公式从另一个角度可以视为通用化边缘规则：P(Y)=zP(Y,z)=zP(Y|z)P(z)将随机变量的某个变量的分布抽取出来，求和从而得到该变量的无条件概率(或称为边缘概率) / 其过程称为边缘化或求和消元(summing out)用于从多个变量的全概率分布中求取某个变量的概率，进行推理第7章不精确推理18归一化归一化在一定条件下某个随机变量的绝对概率值可以根据概率公理来归一化一种结果作为分子，同条件各种结果之和作为分母通常，同条件下结果只有2个a/a，故有p(a|*)+p(a|*)=1(*为某种条件)引入归一化常数=1/p(a)

10、+p(a)第7章不精确推理19逆概率公式逆概率公式逆概率公式从条件概率公式可得如果有多个假设H1Hn，则上式化为第7章不精确推理20逆概率公式的例子逆概率公式的例子逆概率公式不仅是条件概率公式的一个简单变形，实际上很有用处如果某个条件概率不便计算，则可以先计算其逆概率，而后算出所要的条件概率例子：求P(肺炎|咳嗽)可能比较困难，但统计P(咳嗽|肺炎)可能比较容易(因为要上医院)/ 假设P(肺炎)=1/10000，而P(咳嗽)=1/10，90%的肺炎患者都咳嗽，则P(肺炎|咳嗽)= 第7章不精确推理21修正因子修正因子(1)(1)可以将前面的逆概率公式写成这说明先验概率P(H)可以通过方括

11、号部分(作为修正因子)修正为后验概率P(H|E) (证据E为真时H的后验概率)在上面的例子中，医生认为一个人得肺炎的可能性为万分之一，一旦发现患者咳嗽，就将调整为万分之九第7章不精确推理22修正因子修正因子(2)(2)将E看作证据，先验概率P(E)越小，且H为真时E的条件概率P(E|H)越大，则修正因子所起作用越大在上例中，如果P(咳嗽)=0.0001 / P(咳嗽|肺炎)=0.9999 / P(肺炎)不变则P(肺炎|咳嗽)=0.9999，远远超过原来的万分之九第7章不精确推理23后验概率递推公式后验概率递推公式当有n个互相独立的证据，则有公式上式可以写成递推公式形式：上式说明：随着新证据

12、的不断获得，从证据少时的后验概率推出证据多时的后验概率，且每一步都是把上一步的后验概率视为新证据到来时的先验概率第7章不精确推理246.2.2 6.2.2 几率和似然比几率和似然比引入相对量度定义几率：称为H的几率或先验几率，取值范围0,)由此反过来有定义条件几率：第7章不精确推理25后验几率和先验几率的关系后验几率和先验几率的关系例子：O(晴天|冬天早晨有雾)=4.2，如果冬天早晨有雾，则该天为晴天的可能性是非晴天可能性的4.2倍由几率定义、条件几率定义和条件概率公式可以推得后验几率和先验几率的关系：第7章不精确推理26似然比似然比定义似然比：LS=P(E|H)/P(E|H)LN=P

13、(E|H)/P(E|H)则可得下述关系：O(H|E)=LS*O(H)O(H|E)=LN*O(H)有多个证据独立时，其公式是第7章不精确推理27似然比约束似然比约束对LS和LN的约束对于LS和LN有如下约束要求：二者都是非负的，并且满足第7章不精确推理286.2.3 6.2.3 似然比应用似然比应用似然比(规则强度)LS和LN的应用当P(E)=1时，利用LS将先验几率O(H)更新为后验几率O(H|E) / 当P(E)=1时，利用LN来更新几率在专家系统PROSPECTOR(一个用于探矿的ES)中同时应用了LS和LN，分别表示正面证据和反面证据的支持，称为充分因子和必要因子，并将LS、LN附着

14、在每条规则之上第7章不精确推理29LSLS和和LNLN的作用的作用当LS很大，说明证据成立时假设成立的可能性很大，否则LS1说明E排斥H；LN很小，说明证据不成立时假设不成立的可能性很大LS和LN之值接近1时说明证据成立或不成立对于结论是否成立影响不大一般情况下，LS和LN不是根据定义计算出来的，而是给定的第7章不精确推理30应用举例应用举例(1)(1)例子：评职称的概率设某副教授X要评正教授，现有4个指标，却有8人参与竞争 / 投票前夕，X作了如下预测：如果不考虑评委因素，则成功概率=1/2，此相当于先验几率O(H)=1；如果考虑评委因素，则情况如下：校评委共15人，其中5人来自其他竞争

15、者所在系，4人与X素有微隙，尤其是其中2人兼具来自其他竞争者所在系，对X的成功构成了极大威胁，但聊以自慰的是评委中有5位老朋友，估计会投X的票第7章不精确推理31应用举例应用举例(2)(2)为此，X定义了如下的似然比：LS(评委Y1出席|X评上)=1/2 Y1来自其他竞争者所在系，同时令LN=2(LS*LN=1)LS(评委Y2出席|X评上)=1/4Y2与X素有微隙，同时令LN=4LS(评委Y3出席|X评上)=1/8Y3来自其他竞争者所在系兼与X素有微隙，同时令LN=8LS(评委Y4出席|X评上)=4Y4是X的老朋友，同时令LN=1/4LS(评委Y5出席|X评上)=1Y5不属于以上情况，LN=

16、1第7章不精确推理32应用举例应用举例(3)(3)若15人全体出席，且假定各条件互相独立，则按公式(6.11)，X评上的后验概率是：O(X评上|15人出席)=根据几率和概率之间的关系，换为概率P=O/(1+O)=1/9，X评上的希望不大第7章不精确推理33应用举例应用举例(4)(4)但是，当又有消息说，一位来自其他竞争者所在系兼与X素有微隙的评委A不能出席，而代之以一位态度中立的评委 / 此时，X又作了一番推测：LS(A出席|X评上)=LN(A出席|X评上)=8LS(中立评委|X评上)=1则在原结果的基础上乘上上述因子，使得后验几率=1，即后验概率=1/2，X评上的前景大大改观第7章不精

17、确推理347.3 贝叶斯网络7.3.1 贝叶斯网络的表示7.3.2 贝叶斯网络中的精确推理7.3.3 贝叶斯网络的近似推理第7章不精确推理贝叶斯网络定义贝叶斯网络定义贝叶斯网络(Bayesian network)是一个有向图，其中每个节点都标注了定量概率信息(1)一个随机变量集合组成网络节点，变量可以是离散的或者连续的(2)一个连接节点对的有向边或者箭头的集合，如果存在从节点X指向节点Y的有向边，则称X是Y的一个父节点(3)每个节点都存在一个条件概率分布P(Xi|Parent(Xi)，量化父节点对该节点的影响(4)图中不存在有向环(是有向无环图DAG)第7章不精确推理366.3.1 6.3

18、.1 贝叶斯网络的表示贝叶斯网络的表示从一个例子(防盗网)开始第7章不精确推理BurglaryEarthquakeAlarmJohnCallMaryCallP(B).001P(E).002 B E P(A) T T .95 T F .94 F T .29 F F .001 A P(J) T .90 F .05 A P(M) T .70 F .0137条件概率表条件概率表每个节点旁的条件概率表(简称CPT)中的值对应一个条件事件的概率如P(A)=0.94=P(A|BurglaryEarthquake)条件事件是父节点取值的一个可能组合每行的概率之和应改为1(表中只给出了为真的情况，为假的概率应

19、为1-p)一个具有k个布尔父节点的布尔变量的条件概率表中有2k个独立的可指定的概率(注意概率值是独立的)没有父节点的节点的概率只有1行 / 为先验概率第7章不精确推理38全联合概率分布全联合概率分布贝叶斯网络给出了关于相关事件的完整描述，通过计算全联合概率分布求取联合分布中的某项是对每个变量赋予一个特定值情况下的合取概率就是条件概率表中适当元素的乘积例子 P(jmabe)=P(j|a)P(m|a)P(a|be)P(b)P(e)=0.90*0.70*0.001*0.999*0.998=0.00062第7章不精确推理39链式法则链式法则初始的合取概率化为更小的条件概率和更小的合取式 / 这些条

20、件概率的合取式实际上就是父节点到子节点的概率乘积P(Xi|Xi-1,X1)=P(Xi|Parent(Xi)如果父节点包含于条件Xi-1,X1之中此为链式法则父子节点的关系使得贝叶斯网络具有局部结构化的特性，即每个节点只和数量有限的其它部分产生直接的相互作用第7章不精确推理40局部结构化与节点顺序局部结构化与节点顺序由于贝叶斯网络的局部结构化，每个随机变量可以至多受到至多k个其它随即变量的影响(k=常数)设网络中有n个节点(随机变量)，指定每个条件概率表所需信息量至多为2k个数据，则整个网络可以用n2k个数据完全描述/而全联合概率分布需要2n个数据构造贝叶斯网络的次序：添加节点首先从“根本原因

21、”开始，然后加入受其直接影响的变量，直到叶节点(不影响任何其它节点)第7章不精确推理41条件独立关系条件独立关系贝叶斯网络中节点相互独立(下面两个定义等价)：(1)给定父节点，一个节点与它的非后代节点是条件独立的(2)给定一个节点的父节点、子节点以及子节点的父节点(Markov blanket)，这个节点对于其它节点都是条件独立的图示第7章不精确推理42条件独立关系图示条件独立关系图示第7章不精确推理U1UmXZ1jZnjY1YnU1UmXZ1jZnjY1Yn43噪声或关系噪声或关系(1)(1)贝叶斯网络中尽管父节点个数k很小，但是要完成条件概率表仍需要O(2k)数据如果找到了变量依赖的

22、“噪声”逻辑关系，则可以用O(k)个参数完成条件概率表噪声或(noisy-OR)关系用于刻画不确定关系，使逻辑或的推广噪声或关系考虑到每个父节点引起子节点为真的能力的不确定性第7章不精确推理44噪声或关系噪声或关系(2)(2)这种不确定性用一个例子表示：发烧(fever)为真，当且仅当以下三者之一为真感冒(cold)/流感(flu)/疟疾(malaria)但是可能病人得了以上疾病却没有发烧症状，这就是父节点为真其子节点未必真的不确定性即父子关系被抑制此时可以认为：fever为假当且仅当所有为真的父节点被抑制，其概率为每个父节点被抑制的概率的乘积第7章不精确推理45噪声或关系噪声或关系(3)

23、(3)假设每个单独抑制的概率如下P(fever|cold,flu,malaria)=0.6P(fever|cold,flu,malaria)=0.2P(fever|cold,flu,malaria)=0.1则可以建立一个完整的条件概率表/大大减少了所需参数，成为一种有效表示如P(fever|cold,flu,malaria)=0.2*0.1=0.02P(fever|cold,flu,malaria)=0.6*0.2*0.1=0.012 P(fever|cold,flu,malaria)=1-0.012=0.988第7章不精确推理466.3.2 6.3.2 贝叶斯网络中的精确推理贝叶斯网络中的

24、精确推理概率推理系统中的基本任务是计算被查询变量的后验概率设X为待查询变量 / e为观察到的证据 / E=E1Em证据变量集合 / Y=Y1Yn非证据变量集合(也称隐变量)全部变量集合=XEY推理的任务是：求后验概率P(X|e)实际上，根据边缘化规则可得P(X|e)=P(X,e)=yP(X,e,y)第7章不精确推理47查询实例查询实例(1)(1)上式表明：在贝叶斯网络中计算条件概率的乘积并求和，以便回答查询以防盗警报为例，求P(B|JohnCalls=T,M=F)证据JohnCalls=True/MaryCalls=False查询变量Burglary=True隐含变量Earthquake/A

25、larm用首字母简化式有：P(b|j,m)=P(b,j,m)=EAP(b,E,A,j,m)第7章不精确推理48查询实例查询实例(2)(2)进一步代入条件概率：P(b|j,m)=EAP(b)P(E)P(A|b,e)P(j|A)P(m|A)上式最坏复杂度仍然是O(n2n)对所有变量求和改进将相对常数移到求和符号以外P(b|j,m)=P(b)EP(E)AP(A|b,E)P(j|A)P(m|A)计算过程(遍历A=a/a和E=e/e)P(j|a)=0.90P(m|a)=0.30P(j|a)=0.05P(m|a)=0.99P(a|b,e)=0.95P(a|b,e)=0.05P(a|b,e)=0.94P(

26、a|b,e)=0.06第7章不精确推理49查询实例查询实例(3)(3)乘积求和过程EP(E)AP(A|b,E)P(j|A)P(m|A)=P(e)*AP(A|b,e)P(j|A)P(m|A)+P(e)*AP(A|b,e)P(j|A)P(m|A)=P(e)*P(a|b,e)*P(j|a)*P(m|a)+P(a|b,e)* P(j|a)*P(m|a)+P(e)*P(a|b,e)*P(j|a)* P(m|a)+P(a|b,e)* P(j|a)*P(m|a)=0.002*0.95*0.90*0.30+0.05*0.05*0.99+0.998*0.94*0.90*0.30+0.06*0.05*0.99=

27、0.002*0.2565+0.0025+0.998*0.2538+0.0030 =0.002*0.2590+0.998*0.2568=0.2568第7章不精确推理50查询实例查询实例(4)(4)相应地有P(b|j,m)=P(b)*0.2568=0.001*0.2568=*0.0002568类似地有P(b|j,m)=*P(b)EP(E)AP(A|b,E)P(j|A)P(m|A)=*P(b)*0.002*(0.0783+0.0351) +0.998*(0.0003+0.0495)=*0.999*0.0499=*0.0499归一化以后有P(B|j,m)=只有John打电话而出现盗贼的概率小于1/1

28、00第7章不精确推理51变量消元法变量消元法(1)(1)在计算中我们发现P(j|a)*P(m|a)和P(j|a)*P(m|a)重复计算了两次，如何消除重复？只要保留一次计算结果既可(动态规划)通过点积(pointwise product)求和的方法消去隐含变量二元向量fM(A)=P(m|a) P(m|a)T消去 A： fAJM(B,E)=fA(a,B,E)*fJ(a)*fM(a)=fA(a,B,E)*fJ(a)*fM(a)+fA(a,B,E)*fJ(a)*fM(a)第7章不精确推理52变量消元法变量消元法(2)(2)在这样的计算中只要做：计算两个因子的点积在因子乘积中对一个变量求和消元由此

29、消除了重复计算在计算中，消除以下无关节点：删除不是查询变量也非证据变量的叶节点删除所有不是查询变量祖先也不是证据变量祖先的节点第7章不精确推理53精确推理的复杂度精确推理的复杂度单连通结构贝叶斯网络中任何两个节点都至多只有一条无向路径相连此时，单连通上的精确推理的时间和空间复杂度都和网络规模呈线性关系而对于多连通结构(见下图)，最坏情况下变量消元法可能具有指数级的时空复杂度此时贝叶斯网络的推理是一个NP问题所以要寻找多连通网络中的近似算法第7章不精确推理54多连通网络多连通网络第7章不精确推理S R P(W)T T .99T F .90F T .90F F .00C P(R)T .80F

30、 .20sprinklerRainWet grassC P(S)T .10F .50P(C)=.5cloudy556.3.3 6.3.3 贝叶斯网络的近似推理贝叶斯网络的近似推理大规模多连通网络的精确推理是不可操作的，所以要考虑近似的推理方法采用随机采样方法，也称蒙特卡罗算法(Monte Carlo algorithm)：给出问题的近似解答，近似的精度依赖于所生成采样点的多少此处近似的含义不是通过计算求出网络中某个点的条件概率(因为复杂度高)，而是对该事件进行采样而获得概率第7章不精确推理56后验概率计算的采样方法后验概率计算的采样方法有两类采样方法：直接采样方法计算样本的频率马尔科夫链采样

31、方法根据马尔科夫覆盖中的变量当前值来采样直接采样方法依据已知概率来生成样本拒绝采样算法 / 似然加权算法马尔科夫链采样方法证据变量概率固定条件下随机生成样本第7章不精确推理57直接采样方法直接采样方法直接采样方法是按照拓扑结构次序依次对每个变量进行采样，被采样变量值的概率分布依赖于父节点已取得的赋值具体实现：拒绝采样算法首先按照先验概率分布采样，然后排除所有与证据不匹配的样本，最后计算样本频率似然加权证据变量的值用权值(条件概率)来表示，只对非证据变量进行采样第7章不精确推理58采样样本与概率分布采样样本与概率分布样本的向量表示cloudy, sprinkler, rain, wetGra

32、ss F/T或者0/1表示为假或为真 / 如T, F, T, T采样按照已知概率分布进行，但不是等于这个概率分布值，而是说分布与之相符cloudy=0.5,0.5 / 第1次采样49/51，第2次采样52/48如此等等每次采样应该在一定的条件下(这就是条件概率)进行，不满足条件的样本不再考虑第7章不精确推理59采样过程举例采样过程举例(1)(1)通过例子说明采样过程 / 算法均省略(1)因为P(cloudy)=, 故cloudy的采样样本T/F各占50%，假设(不妨)返回T(2)P(sprinkler|cloudy=T)=，故sprinkler的采样样本T/F各占10%和90%，应该返回F注

33、意：此时采样样本均为形式，其中占10%，占90%(3)P(rain|cloudy=T)=，故rain的采样样本T/F各占80%和20%, 应该返回T / 样本形式类似于(2)第7章不精确推理60采样过程举例采样过程举例(2)(2)(4)P(wetGrass|sprinkler=F, rain=T)=，则返回T / 采样样本形式占90%，占10%实际上如此生成的样本完全符合先验概率，即对于上例，cloudy sprinkler rain wetGrass =T F T T=0.5*0.9*0.8*0.9=0.324第7章不精确推理61拒绝采样方法拒绝采样方法从已知分布的采样出发(其计算如上)

34、，通过去掉不满足证据条件的样本来计算(估计)那些未知分布的事件的概率例子：P(Rain|Sprinkler=T)未知其概率 / 采样100个样本其中73个为，不满足前提条件余下的27个中8个为rain=T / 19个为rain=FP(Rain|Sprinkler=T)=拒绝采样方法的最大问题就是效率比较低第7章不精确推理62一致的估计一致的估计拒绝采样方法能产生真实概率的一致估计估计的概率在无限多(大量样本的极限)条件下成为精确值，这样的估计称为一致的(consistent)，即P(x1,xm)=NPS(x1,xm)/N第7章不精确推理63似然加权方法似然加权方法(1)(1)对证据节点的概

35、率进行似然加权，即按照先验概率的乘积进行计算 / 对非证据节点进行采样，采样样本服从先验概率分布例子：求P(rain|sprinkler=T,wetGrass=T)的概率采样过程如下：(1)权值w=1.0(2)P(cloudy)=，据此采样，返回T(3)Sprinkler是证据变量，取值T，则ww*P(sprinkler=T|cloudy=T)=1.0*0.1=0.1第7章不精确推理64似然加权方法似然加权方法(2)(2)(4)P(rain|cloudy=T)=，据此进行采样，假设=T(5)wetGrass是证据变量，取值T，则有ww*P(wetGrass=T|sprinkler=T,rai

36、n=T)=0.1*0.99=0.099此即cloudy sprinkler rain wetGrass=T T T T =0.099 / 解释：sprinkler=T & wetGrass=T条件下rain=T的概率很低似然加权方法也得到对于真实概率的一致估计 / 从采样与加权的乘积去理解联合分布概率的计算，依然是全部条件概率的乘积第7章不精确推理65马尔科夫链采样马尔科夫链采样(1)(1)直接采样法按照先验概率去采样马尔科夫链采样对证据变量以外的变量每次随机地采样举例：考虑求P(rain|sprinkler=T,wetGrass=T)证据变量固定sprinkler=T/wetGrass=T

37、隐变量cloudy/rain则随机采样初始值不妨假设cloudy=T/rain=F初始状态=第7章不精确推理66马尔科夫链采样马尔科夫链采样(2)(2)然后反复按照以下2个步骤采样(1)当前条件下对cloudy随机采样，结果=(2)当前条件下对rain随机采样，结果=最后得到若干样本，例如rain=T=20 / rain=F=60，则P(rain|sprinkler=T,wetGrass=T)= = (?)第7章不精确推理67马尔科夫链采样的合理性马尔科夫链采样的合理性(1)(1)马尔科夫链采样过程最终会进入“动态平衡”状态被采样变量服从马尔科夫覆盖下的条件概率分布，且“稳态分布”=真实后

38、验概率P(x|e)我们所需要求解的正是给定证据变量e下某个变量的概率值P(x|e)证明过程：转移概率状态x到状态xq(xx)时刻t处于状态x的概率t(x)第7章不精确推理68马尔科夫链采样的合理性马尔科夫链采样的合理性(2)(2)下一时刻处于状态x的概率 t+1(x)=xt(x)q(xx)稳态分布(stationary distribution)当t+1(x)=t(x)时，马尔科夫链达到稳态分布，即(省略t) (x)=x(x)q(xx)对于所有x细致平衡任意两个状态间沿两个方向转换概率相等 (x)q(xx)=(x)q(xx)对于所有x, x简单公式推导(求和)可证明细致平衡中蕴含着稳态分布第

39、7章不精确推理69马尔科夫链采样的合理性马尔科夫链采样的合理性(3)(3)前述马尔科夫链采样过程称为Gibbs采样器，其转移概率写为：q(xx)=q(xi,xi)(xi,xi)=P(xi|xi,e)由此证明满足细致平衡(p398)，也就是稳态分布而P(xi|xi,e)正是所求的贝叶斯网络中条件概率最终每个时刻的状态概率值都相同第7章不精确推理707.4 可信度方法*7.4.1 可信度定义与性质7.4.2 证据不确定下CF的计算7.4.3 可信度推理例子第7章不精确推理6 6. .4 4 可信度方法可信度方法可信度方法的原则Mycin系统设计时考虑了如下一些原则：(1)用接近统计理论的近似

40、方法；(2)用专家经验估计代替统计数据；(3)尽量减少经验估计；(4)适用于证据增量式增加的情况；(5)数据的轻微扰动不影响最终的推理结论证据理论是其基础(Dempster-Shafer)第7章不精确推理72确认理论为基础确认理论为基础以确认理论为基础，和概率理论的区别：设E为证据，H为假设，则概率论公式为P(H|E)+P(H|E)=1CF(certainty factor)表示确认理论下的定量可信度，则有公式CF(H|E)+CF(H|E)=0含义：E肯定了H(=1)就同时否定了H (=-1)第7章不精确推理73肯定和否定的程度肯定和否定的程度用两个量来表示在给定证据下，对某个假设的肯定和

44、D(H|Ej)0)CF(H|E+&E-)=MB(H|E+)-MD(H|E-)第7章不精确推理78CFCF性质性质当多个证据导出同一假设时，先求出各自MB/MD然后利用复合证据处理公式得出总的MB/MD，再得到CF(4)若H1Hk是k个互相独立的假设，E为对其有利的证据，则第7章不精确推理796.4.2 6.4.2 证据不确定下的证据不确定下的CFCF计算计算不确定证据下CF的计算证据E本身不确定，其可信度用CF(E)或CF(E|S)表示，S是证据E的观察 / 有性质如下：(1)当证据E以某种程度为真时，0CF(E)1以某种程度为假时，-1CF(E)0(2)证据E肯定真时CF(E)=1证据肯

47、=MB/MD/CF(H|E)*CF(E)如果CF(E)0.2 否则为0第7章不精确推理836.4.3 6.4.3 可信度推理例子可信度推理例子推理规则形式:=,设有推理网络如下图所示，其推理规则为(1)ABH, 0.7(2)CH, 0.5(3)(DE)F(GI)H, 0.9(4)JH, 0.3每个证据的可信度标在叶子节点的下面，节点分叉带弧者为与节点第7章不精确推理84推理网络推理网络第7章不精确推理85求解过程求解过程(1)(1)求解步骤：(1)CF(H|AB)=0.7*min0.2,0.5=0.14 按照阈值规定可不考虑其对假设H推理的贡献，即下一步不参与计算(2)CF(H|C)=0

48、.5*0.4=0.2(3)CF(H|(DE)F(GI)=0.9*min max0.4,0.2,0.6,max0.8,0.1=0.9*0.4=0.36(4)CF(H|J)=0.3*(-0.8)=-0.24第7章不精确推理86求解过程求解过程(2)(2)(5)由定义可知MB1=0.2MB2=0.36MB3=0MD1=0MD2=0MD3=0.24MB=0.2+0.360.2*0.36=0.488MD=0.24故CF=MB MD=0.488 0.24=0.248第7章不精确推理87求解过程求解过程(3)(3)如果将CF=0.14计算在内，则MB=0.14+0.2+0.36 0.14*0.2 0.1

49、4*0.36 0.2*0.36+0.14*0.2*0.36 =0.55968MD=0.24CF=0.55968 0.24=0.31968注意：计算的步骤是分别求每个证据的CF或MB/MD，然后用复合证据公式计算MB/MD，最后得CF=MBMD第7章不精确推理887.5 模糊推理7.5.1 模糊数据的确定7.5.2 模糊关系及其投影7.5.3 模糊推理的例子第7章不精确推理7.5.1 7.5.1 模糊数据的确定模糊数据的确定确定模糊数据即隶属函数的确定如何确定隶属函数？有多种方法调查投票根据投票统计所得的数据确定出隶属函数用概率分布函数模拟分为3种(1)正态分布(2)戒上型函数(3)戒下型函

50、数第7章不精确推理90调查投票例子调查投票例子调查投票根据投票统计所得的数据确定出隶属函数例子古代选美：明末南京有“秦淮八艳”，要判断谁更漂亮？不同人有不同看法，现设有100人投票，可通过与其中一位比较的方法确定一种相对量度 / 设其他7位与李香君比较(得票数少于50者被认为不如她，多者则超过她)，根据每个人所得票数可得隶属函数 / 显然，在隶属度函数中，李香君本人应该放在0.5的位置第7章不精确推理91调查投票结果表示调查投票结果表示第7章不精确推理92概率分布函数概率分布函数(1)(1)用概率分布函数来逼近隶属函数(1)中心强、两边弱、中间对称的隶属度分布可用正态分布来逼近，如“中年

51、”；(2)对于隶属度随某种属性值而增长的情况，可采用单调递增或非减函数，特别是当属性值足够大时隶属度恒为1的情况，可采用戒下型函数，如“老年”；(3)对于隶属度随某种属性值而减小的情况，可采用单调递减或非增函数，当属性值足够小时隶属度恒为1的情况，可采用戒上型函数，如“童年”第7章不精确推理93函数分布函数函数分布函数(2)(2)上述3种函数的公式为：(1)正态分布(x)=(2)戒下型函数第7章不精确推理94函数分布函数函数分布函数(3)(3)(3)戒上型函数三个函数的图形如下： 0 a 1 0 a b 1 0 a b 1第7章不精确推理957.5.2 7.5.2 模糊关系及其投影模糊关

52、系及其投影模糊关系：模糊关系是集合的笛卡尔积的子集+对集合的隶属函数(如第3章定义)设R为A1A2.An上的一个n元模糊关系，则 R中的元素表示为(a1,a2,an),(a1,a2,an)其中anAi，(a1,a2,an)是对R的隶属度构成了n维空间超矩阵第7章不精确推理96模糊关系的合成模糊关系的合成模糊关系的合成：设R是UV上的模糊关系，S是VW上的模糊关系，则R与S的合成关系Z=RS的元素为：Zij = (ui,w), 这里是(ui,vk),R(ui,vk)与(vk,wj), S(vk,wj)的合成，而V的元素个数为n(k=1n组合一遍)第7章不精确推理97模糊关系例子模糊关系例子例

53、1：设R模糊关系表示“天下乌鸦一般黑”定义在集合U2上，U中的每个元素是乌鸦，如俄罗斯乌鸦、美国乌鸦、科索沃乌鸦、南联盟乌鸦等等，R是U2中任意2只乌鸦之间是否一样黑的程度，其隶属度如(美国乌鸦, 科索沃乌鸦)=0.7 / 又设S模糊关系表示“天下乌鸦打仗一样激烈”(即任意2只乌鸦参与争斗时的激烈程度是否一致)，则对于第i只和第j只乌鸦来说，存在1只乌鸦c，c和第i只乌鸦一样黑、和第j只乌鸦打仗一样激烈的为真程度用RS的元素RS(ij)表示第7章不精确推理98模糊关系的投影模糊关系的投影模糊关系的投影：设R是A1.An上的一个模糊关系，则在Ak=Ai1.Aik上的一个k元模糊关系Rk定义为其

55、关系投影例子(1)(1)例2：设某公司有3个部门构成集合A1=a, b, c，新聘3位员工构成集合A2=d, e, f，令A=A1A2，A上的模糊关系R定义为“将新员工安排到各部门的合适人选”，这个二元模糊关系的隶属函数矩阵如下表示第7章不精确推理101模糊关系投影例子模糊关系投影例子(2)(2)R在A1上的胖投影RF(A1)=(a, 0.8), (b, 0.7), (c, 0.9)，表示各部门找到合适人选的乐观估计R在A1上的瘦投影RT(A1)=(a, 0.4), (b, 0.2), (c, 0.3)，表示相应的悲观估计另一方面，RF(A2)=(d, 0.9), (e, 0.6), (c,

56、 0.7)，表示各人能在各部门找到合适工作的乐观估计RF=(d, 0.2), (e, 0.4), (f, 0.3)为相应的悲观估计第7章不精确推理102模糊关系投影例子模糊关系投影例子(3)(3)注意：这里乐观估计并不能全部实现，因为会产生冲突，如果a部门安排了合适人选d，则c部门就找不到最合适人选；同样，d在c部门找到最合适工作，则e就找不到最合适工作了第7章不精确推理1037.5.3 7.5.3 模糊推理的例子模糊推理的例子模糊推理AB可看作A与B之间存在函数关系。实际应用中使用了第3章给出的计算方法，即模糊推理的例子规则A=“如果气候温和并且雨量充沛则适于种柑橘”第7章不精确推理1

57、04模糊推理的例子模糊推理的例子(1)(1)其中各模糊集表示为：气候温和C=(10, 0.5), (20, 1), (30, 0.5), (40, 0.2)，其个体元素构成的分明集记为#C=10, 20, 30,40是平均摄氏温度雨量充沛R=(100, 0.1), (200, 0.4), (300, 0.7), (400, 1)，对应的分明集#R=100, 200, 300, 400是年降雨量(毫米)适于种柑橘S=(100, 0.5), (200, 0.7), (300, 1)，对应的分明集#S=100, 200, 300是单株产量(斤)第7章不精确推理105模糊推理的例子模糊推理的例子(2

58、)(2)那么，模糊推理规则为CRS，显然隶属函数值v可通过如下公式求得：第7章不精确推理故可得出下页的模糊矩阵106模糊推理的例子模糊推理的例子(3)(3)矩阵中每个元素值表示在一定的气候和雨量组合下(每行)不同单株产量(列)的可能性(隶属函数值)第7章不精确推理107参考书目参考书目Stuart Russell / Peter Norvig: AIMA 第13章 / 第14章陆汝钤编著: 人工智能(下册) 第26章田盛丰、黄厚宽，人工智能与知识工程，中国铁道出版社，1999年8月第1版，第6章John F. Sowa: Knowledge Representation (English Version), 2003年5月, 机械工业出版社, 第6章第7章不精确推理108

展开阅读全文

人工智能原理第7章不精确推理.ppt课件

最新文档