人工智能原理不精确推理.ppt

人工智能原理 第7章 不精确推理,本章内容 7.1 不精确推理的必要性 7.2 贝叶斯概率推理 7.3 贝叶斯网络 7.4 可信度方法* 7.5 模糊推理 参考书目,第7章 不精确推理,7.1 不精确推理的必要性 不精确推理的原因 / 方法,第7章 不精确推理,4,为什么要不精确推理,做不精确推理的原因有多种： 推理所需的信息不完备：竞争双方不知道对方信息 背景知识不足：疑难病症的机理 多种原因导致同一结果：疾病的诊断 信息描述模糊：目击者对嫌疑犯的描述 信息中含有噪声：做假帐，虚假统计报表，采集数据当中的噪声（雷达、声纳/化验）等,第7章 不精确推理,5,不精确推理的原因,规则是模糊的：定性描述，如“如果刑事犯罪猖獗，就应加大打击力度”等 推理能力不足：天气预报的计算 解决方案不唯一：多个方案如何选优的问题 两种不确定性 环境的不确定性智能体几乎从来无法了解关于其环境的全部事实 反映环境的知识的不确定性过于复杂而无组织知识粥(knowledge soup),第7章 不精确推理,6,不确定环境下的智能体行动,从智能体角度看，他不得不在不确定的环境下行动 克服这种不确定性的解决方案 1)条件规划 2)使用简单而不完全正确的模型 大部分时间模型或者规划可行，但有时会出现矛盾 理性决策依赖于各种目标的相对重要性，也依赖于这些目标被实现的可能性,第7章 不精确推理,7,不确定性下的决策,不确定性的存在改变了智能体进行决策的方式 智能体要在各种规划的不同可能结果之间进行选择(有所偏好) 一种结果是一个被完全确定的状态任何状态对于智能体来说都具有一定程度的有用性即效用，智能体将偏好具有更高效用的状态 决策理论=概率理论+效用理论 理性智能体选择能产生最高效用的行动,第7章 不精确推理,8,不精确推理,现实不确定性需要不精确推理，将数值计算引入推理过程 继续使用逻辑联结词 真假值概率化，以表示某种可靠程度 在推理的前提和结论之间建立概率公式（解释） 前提称为证据，结论称为假设 应用：专家系统中的推理网络 (PROSPECTOR系统/ MYCIN系统),第7章 不精确推理,9,贝叶斯网络(Bayesian network),智能体使用概率对行动结果(用事件之间的联系表示)进行预测，进而选择期望效用最高的行动 贝叶斯网络(也叫贝叶斯信念网)是一个节点标注了定量概率信息的有向图，反映了一个事件对于另一个事件的影响程度/表示了变量之间的依赖关系和概率信息 贝叶斯网络是事件之间联系的全面而形象的表示,第7章 不精确推理,10,知识粥(Knowledge Soup),现实世界的复杂性和不确定性反映在智能体内部异质的、不固定的、经常不一致的知识称为知识粥 “粥体”包含小块(small chunk)对应于规则、框架等，大块(large chunk)对应于整个理论 这些“块”的内部是一致的，“块”之间可以是不一致的 从整体来说，知识往往具有这样的特性模糊、不确定、随机、无知,第7章 不精确推理,7.2 Bayes概率推理 7.2.1 有关概念和公式 7.2.2 几率和似然比 7.2.3 似然比应用,第7章 不精确推理,12,主观Bayes主义,主观Bayes主义： 将概率推理与归纳逻辑的解释联系起来，现实世界的一些因果关系可以形成一种信念，它并非在所有场合下都正确，可称为部分信念 / 表示这种信念的最好方法是概率方法，对概率的解释有若干种，其中Bayes创立了主观解释，也称为主观Bayes主义 其要点是：概率是个人的一种合理置信度，每个人的估计(概率)虽然各不相同，但应该满足概率的基本规律和其他某些客观规律，因而是合理的,第7章 不精确推理,13,7.2.1 有关概念和公式,在Bayes概率推理中，推理规则表示为 if E(前提/证据) then H(结论/假设)(LS, LN) 规则强度用LS/LN表示(也称为似然比) / 其不精确推理过程是：根据证据E的概率P(E)，利用规则的LS和LN，把结论的先验概率P(H)更新为后验概率P(H|E)，因而也称为概率传播,第7章 不精确推理,14,Bayes条件概率,Bayes条件概率：令假设H的先验概率为P(H)，P(H)是指定的 / 证据E为真时H的条件概率为P(H|E)，P(H|E)的一部分是指定的，一部分是根据P(H)和指定的P(H|E)计算出来的，这部分计算出的概率称为后验概率 条件概率P(H|E)可看作以一定概率成立的EH的推理规则,第7章 不精确推理,15,概率公理,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)互斥 这样的概率公理是不能违反的(p364论证),第7章 不精确推理,16,条件概率公式,条件概率公式 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章 不精确推理,17,全概率公式,全概率公式：一个假设的先验概率可以表示为两个假设的概率，其中后面一个假设遍历各种可能性且各个可能性之间是独立的，则有 P(H)=iP(H&Gi)=iP(H|Gi)P(Gi) 其解释为：假设H的概率等于从各种证据提供的信息所推出的条件概率之和 / 证据满足独立性和完全性 这个公式也称为全联合分布,第7章 不精确推理,18,边缘化,上述全概率公式从另一个角度可以视为通用化边缘规则： P(Y)=zP(Y,z)=zP(Y|z)P(z) 将随机变量的某个变量的分布抽取出来，求和从而得到该变量的无条件概率(或称为边缘概率) / 其过程称为边缘化或求和消元(summing out) 用于从多个变量的全概率分布中求取某个变量的概率，进行推理,第7章 不精确推理,19,归一化,在一定条件下某个随机变量的绝对概率值可以根据概率公理来归一化一种结果作为分子，同条件各种结果之和作为分母 通常，同条件下结果只有2个a/a，故有p(a|*)+p(a|*)=1 (*为某种条件) 引入归一化常数 =1/p(a)+p(a),第7章 不精确推理,20,逆概率公式,逆概率公式 从条件概率公式可得 如果有多个假设H1Hn，则上式化为,第7章 不精确推理,21,逆概率公式的例子,逆概率公式不仅是条件概率公式的一个简单变形，实际上很有用处如果某个条件概率不便计算，则可以先计算其逆概率，而后算出所要的条件概率 例子：求P(肺炎|咳嗽)可能比较困难，但统计P(咳嗽|肺炎)可能比较容易(因为要上医院)/ 假设P(肺炎)=1/10000，而P(咳嗽)=1/10，90%的肺炎患者都咳嗽，则 P(肺炎|咳嗽)= ,第7章 不精确推理,22,修正因子(1),可以将前面的逆概率公式写成 这说明先验概率P(H)可以通过方括号部分(作为修正因子)修正为后验概率P(H|E) (证据E为真时H的后验概率) 在上面的例子中，医生认为一个人得肺炎的可能性为万分之一，一旦发现患者咳嗽，就将调整为万分之九,第7章 不精确推理,23,修正因子(2),将E看作证据，先验概率P(E)越小，且H为真时E的条件概率P(E|H)越大，则修正因子所起作用越大 在上例中，如果 P(咳嗽)=0.0001 / P(咳嗽|肺炎)=0.9999 / P(肺炎)不变 则P(肺炎|咳嗽)=0.9999，远远超过原来的万分之九,第7章 不精确推理,24,后验概率递推公式,当有n个互相独立的证据，则有公式 上式可以写成递推公式形式： 上式说明：随着新证据的不断获得，从证据少时的后验概率推出证据多时的后验概率，且每一步都是把上一步的后验概率视为新证据到来时的先验概率,第7章 不精确推理,25,6.2.2 几率和似然比,引入相对量度 定义几率： 称为H的几率或先验几率，取值范围0,) 由此反过来有 定义条件几率：,第7章 不精确推理,26,后验几率和先验几率的关系,例子：O(晴天|冬天早晨有雾)=4.2，如果冬天早晨有雾，则该天为晴天的可能性是非晴天可能性的4.2倍 由几率定义、条件几率定义和条件概率公式可以推得后验几率和先验几率的关系：,第7章 不精确推理,27,似然比,定义似然比： LS=P(E|H)/P(E|H) LN=P(E|H)/P(E|H) 则可得下述关系： O(H|E)=LS*O(H) O(H|E)=LN*O(H) 有多个证据独立时，其公式是,第7章 不精确推理,28,似然比约束,对LS和LN的约束 对于LS和LN有如下约束要求：二者都是非负的，并且满足,第7章 不精确推理,29,6.2.3 似然比应用,似然比(规则强度)LS和LN的应用 当P(E)=1时，利用LS将先验几率O(H)更新为后验几率O(H|E) / 当P(E)=1时，利用LN来更新几率 在专家系统PROSPECTOR(一个用于探矿的ES)中同时应用了LS和LN，分别表示正面证据和反面证据的支持，称为充分因子和必要因子，并将LS、LN附着在每条规则之上,第7章 不精确推理,30,LS和LN的作用,当LS很大，说明证据成立时假设成立的可能性很大，否则LS1说明E排斥H；LN很小，说明证据不成立时假设不成立的可能性很大 LS和LN之值接近1时说明证据成立或不成立对于结论是否成立影响不大 一般情况下，LS和LN不是根据定义计算出来的，而是给定的,第7章 不精确推理,31,应用举例(1),例子：评职称的概率 设某副教授X要评正教授，现有4个指标，却有8人参与竞争 / 投票前夕，X作了如下预测：如果不考虑评委因素，则成功概率=1/2，此相当于先验几率O(H)=1；如果考虑评委因素，则情况如下： 校评委共15人，其中5人来自其他竞争者所在系，4人与X素有微隙，尤其是其中2人兼具来自其他竞争者所在系，对X的成功构成了极大威胁，但聊以自慰的是评委中有5位老朋友，估计会投X的票,第7章 不精确推理,32,应用举例(2),为此，X定义了如下的似然比： LS(评委Y1出席|X评上)=1/2 Y1来自其他竞争者所在系，同时令LN=2 (LS*LN=1) LS(评委Y2出席|X评上)=1/4 Y2与X素有微隙，同时令LN=4 LS(评委Y3出席|X评上)=1/8 Y3来自其他竞争者所在系兼与X素有微隙，同时令LN=8 LS(评委Y4出席|X评上)=4 Y4是X的老朋友，同时令LN=1/4 LS(评委Y5出席|X评上)=1 Y5不属于以上情况，LN=1,第7章 不精确推理,33,应用举例(3),若15人全体出席，且假定各条件互相独立，则按公式(6.11)，X评上的后验概率是： O(X评上|15人出席)= 根据几率和概率之间的关系，换为概率P=O/(1+O)=1/9，X评上的希望不大,第7章 不精确推理,34,应用举例(4),但是，当又有消息说，一位来自其他竞争者所在系兼与X素有微隙的评委A不能出席，而代之以一位态度中立的评委 / 此时，X又作了一番推测： LS(A出席|X评上)=LN(A出席|X评上)=8 LS(中立评委|X评上)=1 则在原结果的基础上乘上上述因子，使得后验几率=1，即后验概率=1/2，X评上的前景大大改观 ,第7章 不精确推理,7.3 贝叶斯网络 7.3.1 贝叶斯网络的表示 7.3.2 贝叶斯网络中的精确推理 7.3.3 贝叶斯网络的近似推理,第7章 不精确推理,36,贝叶斯网络定义,贝叶斯网络(Bayesian network)是一个有向图，其中每个节点都标注了定量概率信息 (1)一个随机变量集合组成网络节点，变量可以是离散的或者连续的 (2)一个连接节点对的有向边或者箭头的集合，如果存在从节点X指向节点Y的有向边，则称X是Y的一个父节点 (3)每个节点都存在一个条件概率分布P(Xi|Parent(Xi)，量化父节点对该节点的影响 (4)图中不存在有向环(是有向无环图DAG),第7章 不精确推理,37,6.3.1 贝叶斯网络的表示,从一个例子(防盗网)开始,第7章 不精确推理,38,条件概率表,每个节点旁的条件概率表(简称CPT)中的值对应一个条件事件的概率 如P(A)=0.94=P(A|BurglaryEarthquake) 条件事件是父节点取值的一个可能组合 每行的概率之和应改为1(表中只给出了为真的情况，为假的概率应为1-p) 一个具有k个布尔父节点的布尔变量的条件概率表中有2k个独立的可指定的概率(注意概率值是独立的) 没有父节点的节点的概率只有1行 / 为先验概率,第7章 不精确推理,39,全联合概率分布,贝叶斯网络给出了关于相关事件的完整描述，通过计算全联合概率分布求取 联合分布中的某项是对每个变量赋予一个特定值情况下的合取概率 就是条件概率表中适当元素的乘积 例子 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章 不精确推理,40,链式法则,初始的合取概率化为更小的条件概率和更小的合取式 / 这些条件概率的合取式实际上就是父节点到子节点的概率乘积 P(Xi|Xi-1,X1)=P(Xi|Parent(Xi) 如果父节点包含于条件Xi-1,X1之中 此为链式法则 父子节点的关系使得贝叶斯网络具有局部结构化的特性，即每个节点只和数量有限的其它部分产生直接的相互作用,第7章 不精确推理,41,局部结构化与节点顺序,由于贝叶斯网络的局部结构化，每个随机变量可以至多受到至多k个其它随即变量的影响(k=常数) 设网络中有n个节点(随机变量)，指定每个条件概率表所需信息量至多为2k个数据，则整个网络可以用n2k个数据完全描述/而全联合概率分布需要2n个数据 构造贝叶斯网络的次序：添加节点首先从“根本原因”开始，然后加入受其直接影响的变量，直到叶节点(不影响任何其它节点),第7章 不精确推理,42,条件独立关系,贝叶斯网络中节点相互独立(下面两个定义等价)： (1)给定父节点，一个节点与它的非后代节点是条件独立的 (2)给定一个节点的父节点、子节点以及子节点的父节点(Markov blanket)，这个节点对于其它节点都是条件独立的 图示,第7章 不精确推理,43,条件独立关系图示,第7章 不精确推理,44,噪声或关系(1),贝叶斯网络中尽管父节点个数k很小，但是要完成条件概率表仍需要O(2k)数据 如果找到了变量依赖的“噪声”逻辑关系，则可以用O(k)个参数完成条件概率表 噪声或(noisy-OR)关系用于刻画不确定关系，使逻辑或的推广 噪声或关系考虑到每个父节点引起子节点为真的能力的不确定性,第7章 不精确推理,45,噪声或关系(2),这种不确定性用一个例子表示： 发烧(fever)为真，当且仅当以下三者之一为真感冒(cold)/流感(flu)/疟疾(malaria) 但是可能病人得了以上疾病却没有发烧症状，这就是父节点为真其子节点未必真的不确定性即父子关系被抑制 此时可以认为：fever为假当且仅当所有为真的父节点被抑制，其概率为每个父节点被抑制的概率的乘积,第7章 不精确推理,46,噪声或关系(3),假设每个单独抑制的概率如下 P(fever|cold,flu,malaria)=0.6 P(fever|cold,flu,malaria)=0.2 P(fever|cold,flu,malaria)=0.1 则可以建立一个完整的条件概率表/大大减少了所需参数，成为一种有效表示 如P(fever|cold,flu,malaria)=0.2*0.1=0.02 P(fever|cold,flu,malaria)=0.6*0.2*0.1=0.012 P(fever|cold,flu,malaria)=1-0.012=0.988,第7章 不精确推理,47,6.3.2 贝叶斯网络中的精确推理,概率推理系统中的基本任务是计算被查询变量的后验概率 设X为待查询变量 / e为观察到的证据 / E=E1Em证据变量集合 / Y=Y1Yn非证据变量集合(也称隐变量) 全部变量集合=XEY 推理的任务是：求后验概率P(X|e) 实际上，根据边缘化规则可得 P(X|e)=P(X,e)=yP(X,e,y),第7章 不精确推理,48,查询实例(1),上式表明：在贝叶斯网络中计算条件概率的乘积并求和，以便回答查询 以防盗警报为例，求P(B|JohnCalls=T,M=F) 证据JohnCalls=True/MaryCalls=False 查询变量Burglary=True 隐含变量Earthquake/Alarm 用首字母简化式有： P(b|j,m)=P(b,j,m) =EAP(b,E,A,j,m),第7章 不精确推理,49,查询实例(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.90 P(m|a)=0.30 P(j|a)=0.05 P(m|a)=0.99 P(a|b,e)=0.95 P(a|b,e)=0.05 P(a|b,e)=0.94 P(a|b,e)=0.06,第7章 不精确推理,50,查询实例(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 =0.002*0.2565+0.0025+0.998*0.2538+0.0030 =0.002*0.2590+0.998*0.2568=0.2568,第7章 不精确推理,51,查询实例(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/100,第7章 不精确推理,52,变量消元法(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章 不精确推理,53,变量消元法(2),在这样的计算中只要做： 计算两个因子的点积 在因子乘积中对一个变量求和消元 由此消除了重复计算 在计算中，消除以下无关节点： 删除不是查询变量也非证据变量的叶节点 删除所有不是查询变量祖先也不是证据变量祖先的节点,第7章 不精确推理,54,精确推理的复杂度,单连通结构贝叶斯网络中任何两个节点都至多只有一条无向路径相连 此时，单连通上的精确推理的时间和空间复杂度都和网络规模呈线性关系 而对于多连通结构(见下图)，最坏情况下变量消元法可能具有指数级的时空复杂度此时贝叶斯网络的推理是一个NP问题 所以要寻找多连通网络中的近似算法,第7章 不精确推理,55,多连通网络,第7章 不精确推理,56,6.3.3 贝叶斯网络的近似推理,大规模多连通网络的精确推理是不可操作的，所以要考虑近似的推理方法 采用随机采样方法，也称蒙特卡罗算法(Monte Carlo algorithm)：给出问题的近似解答，近似的精度依赖于所生成采样点的多少 此处近似的含义不是通过计算求出网络中某个点的条件概率(因为复杂度高)，而是对该事件进行采样而获得概率,第7章 不精确推理,57,后验概率计算的采样方法,有两类采样方法： 直接采样方法计算样本的频率 马尔科夫链采样方法根据马尔科夫覆盖中的变量当前值来采样 直接采样方法依据已知概率来生成样本 拒绝采样算法 / 似然加权算法 马尔科夫链采样方法证据变量概率固定条件下随机生成样本,第7章 不精确推理,58,直接采样方法,直接采样方法是按照拓扑结构次序依次对每个变量进行采样，被采样变量值的概率分布依赖于父节点已取得的赋值 具体实现： 拒绝采样算法首先按照先验概率分布采样，然后排除所有与证据不匹配的样本，最后计算样本频率 似然加权证据变量的值用权值(条件概率)来表示，只对非证据变量进行采样,第7章 不精确推理,59,采样样本与概率分布,样本的向量表示 cloudy, sprinkler, rain, wetGrass F/T或者0/1表示为假或为真 / 如T, F, T, T 采样按照已知概率分布进行，但不是等于这个概率分布值，而是说分布与之相符 cloudy=0.5,0.5 / 第1次采样49/51，第2次采样52/48如此等等 每次采样应该在一定的条件下(这就是条件概率)进行，不满足条件的样本不再考虑,第7章 不精确推理,60,采样过程举例(1),通过例子说明采样过程 / 算法均省略 (1)因为P(cloudy)=, 故cloudy的采样样本T/F各占50%，假设(不妨)返回T (2)P(sprinkler|cloudy=T)=，故sprinkler的采样样本T/F各占10%和90%，应该返回F 注意：此时采样样本均为形式，其中占10%，占90% (3)P(rain|cloudy=T)=，故rain的采样样本T/F各占80%和20%, 应该返回T / 样本形式类似于(2),第7章 不精确推理,61,采样过程举例(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章 不精确推理,62,拒绝采样方法,从已知分布的采样出发(其计算如上)，通过去掉不满足证据条件的样本来计算(估计)那些未知分布的事件的概率 例子：P(Rain|Sprinkler=T)未知其概率 / 采样100个样本 其中73个为，不满足前提条件余下的27个中8个为rain=T / 19个为rain=F P(Rain|Sprinkler=T)= 拒绝采样方法的最大问题就是效率比较低,第7章 不精确推理,63,一致的估计,拒绝采样方法能产生真实概率的一致估计 估计的概率在无限多(大量样本的极限)条件下成为精确值，这样的估计称为一致的(consistent)，即 P(x1,xm)=NPS(x1,xm)/N,第7章 不精确推理,64,似然加权方法(1),对证据节点的概率进行似然加权，即按照先验概率的乘积进行计算 / 对非证据节点进行采样，采样样本服从先验概率分布 例子：求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章 不精确推理,65,似然加权方法(2),(4)P(rain|cloudy=T)=，据此进行采样，假设=T (5)wetGrass是证据变量，取值T，则有 ww*P(wetGrass=T|sprinkler=T,rain=T) =0.1*0.99=0.099 此即cloudy sprinkler rain wetGrass=T T T T =0.099 / 解释：sprinkler=T & wetGrass=T条件下rain=T的概率很低 似然加权方法也得到对于真实概率的一致估计 / 从采样与加权的乘积去理解联合分布概率的计算，依然是全部条件概率的乘积,第7章 不精确推理,66,马尔科夫链采样(1),直接采样法按照先验概率去采样 马尔科夫链采样对证据变量以外的变量每次随机地采样 举例：考虑求P(rain|sprinkler=T,wetGrass=T) 证据变量固定sprinkler=T/wetGrass=T 隐变量cloudy/rain则随机采样初始值不妨假设cloudy=T/rain=F 初始状态=,第7章 不精确推理,67,马尔科夫链采样(2),然后反复按照以下2个步骤采样 (1)当前条件下对cloudy随机采样，结果= (2)当前条件下对rain随机采样，结果= 最后得到若干样本，例如rain=T=20 / rain=F=60，则P(rain|sprinkler=T,wetGrass=T)= = (?),第7章 不精确推理,68,马尔科夫链采样的合理性(1),马尔科夫链采样过程最终会进入“动态平衡”状态被采样变量服从马尔科夫覆盖下的条件概率分布，且“稳态分布”=真实后验概率P(x|e) 我们所需要求解的正是给定证据变量e下某个变量的概率值P(x|e) 证明过程： 转移概率状态x到状态x q(xx) 时刻t处于状态x的概率 t(x),第7章 不精确推理,69,马尔科夫链采样的合理性(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 简单公式推导(求和)可证明细致平衡中蕴含着稳态分布,第7章 不精确推理,70,马尔科夫链采样的合理性(3),前述马尔科夫链采样过程称为Gibbs采样器，其转移概率写为： q(xx)=q(xi,xi)(xi,xi)=P(xi|xi,e) 由此证明满足细致平衡(p398)，也就是稳态分布 而P(xi|xi,e)正是所求的贝叶斯网络中条件概率最终每个时刻的状态概率值都相同,第7章 不精确推理,7.4 可信度方法* 7.4.1 可信度定义与性质 7.4.2 证据不确定下CF的计算 7.4.3 可信度推理例子,第7章 不精确推理,72,6.4 可信度方法,可信度方法的原则Mycin系统设计时考虑了如下一些原则： (1)用接近统计理论的近似方法； (2)用专家经验估计代替统计数据； (3)尽量减少经验估计； (4)适用于证据增量式增加的情况； (5)数据的轻微扰动不影响最终的推理结论 证据理论是其基础(Dempster-Shafer),第7章 不精确推理,73,确认理论为基础,以确认理论为基础，和概率理论的区别： 设E为证据，H为假设，则概率论公式为 P(H|E)+P(¬H|E)=1 CF(certainty factor)表示确认理论下的定量可信度，则有公式 CF(H|E)+CF(¬H|E)=0 含义：E肯定了H(=1)就同时否定了¬H (=-1),第7章 不精确推理,74,肯定和否定的程度,用两个量来表示在给定证据下，对某个假设的肯定和否定的程度 表示：MB(measure belief) / MD(disbelief) 含义： MB(H|E)=a 证据E的出现使假设H的可信度增加了数量a / MD(H|E)=b 证据E的出现使假设H的不可信度增加了数量b 显然a/b不能同时大于0 CF(H|E)=MB(H|E)-MD(H|E),第7章 不精确推理,75,6.4.1 可信度定义与性质,MB和MD的解释：其值应该由专家给出/ 但为了提供某种理论依据，给出其概率解释，一般不直接用于构造知识库,第7章 不精确推理,76,有关性质(1),MB和MD的性质 (1)由定义，当p(H)=1时MB(H|E)=p(H|E)=1 MD(H|E)=p(¬H|E)=0 (2)由定义，当p(¬H)=1时MB(H|E)=p(H|E)=0 MD(H|E)=p(¬H|E)=1 (3)恒有0MB(H|E)，MD(H|E)1 (4)互斥性：当MB(H|E)0时MD(H|E)=0 当MD(H|E)0时MB(H|E)=0 即恒有MB(H|E)*MD(H|E)=0 (5)若MB(H|E)=1时则对任何E有MD(H|E)=0；反之，若MD(H|E)=1时则对任何E有MB(H|E)=0,第7章 不精确推理,77,有关性质(2),复合证据的处理 (1)MB(H|E1&E2)=MB(H|E1)+MB(H|E2)-MB(H|E1)*MB(H|E2) MD(H|E1&E2)=MD(H|E1)+MD(H|E2)-MD(H|E1)*MD(H|E2) 多于2个证据的，可以进一步组合(E1&E2)&E3. (2)MB(H|E1&E2)=MB(H|E1) MD(H|E1&E2)=MD(H|E1) 其中E2为未知真假的证据,第7章 不精确推理,78,CF定义与性质,可信度因子CF(H|E)=MB(H|E)-MD(H|E) 根据MB/MD的互斥性知，CF只取MB或MD之一值 性质： (1)-1CF(H|E)1 (2)CF(H|E)+CF(¬H|E)=0 (3)令E+=E1&&En 为所有支持H的证据总和(即MB(H|Ei)0) / E-=E1&&Em 为所有不支持H的证据总和(即MD(H|Ej)0) CF(H|E+&E-)=MB(H|E+)-MD(H|E-),第7章 不精确推理,79,CF性质,当多个证据导出同一假设时，先求出各自MB/MD然后利用复合证据处理公式得出总的MB/MD，再得到CF (4)若H1Hk是k个互相独立的假设，E为对其有利的证据，则,第7章 不精确推理,80,6.4.2 证据不确定下的CF计算,不确定证据下CF的计算 证据E本身不确定，其可信度用CF(E)或CF(E|S)表示，S是证据E的观察 / 有性质如下： (1)当证据E以某种程度为真时，0CF(E)1以某种程度为假时，-1CF(E)0 (2)证据E肯定真时CF(E)=1 证据肯定假时CF(E)=-1 对证据一无所知时CF(E)=0,第7章 不精确推理,81,证据的CF计算(1),CF对复合证据的处理：同MB/MD的定义 (1)CF(H|E1&E2)=CF(H|E1)+CF(H|E2) CF(H|E1)*CF(H|E2) (2)CF(H|E1&E2)=CF(H|E1) 其中E2为未知真假的证据 证据的合取与析取 (1)E=E1 and and En CF(E1and and En)=minCF(E1),CF(En) (2)E=E1 or or En CF(E1 or or En)=maxCF(E1),CF(En),第7章 不精确推理,82,证据的CF计算(2),由证据与规则的可信度求假设的可信度 CF(H|S)=CF(H|E)max0,CF(E) (CF(E)0时则不能应用) MB(H|S)=MB(H|E)max0,CF(E) MD(H|S)=MD(H|E)max0,CF(E),第7章 不精确推理,83,可信度阈值,可信度阈值的设定 为了使专家数据的轻微扰动不影响推理结论，Mycin系统设置了最低阈值0.2，即只有CF0.2的证据才对信念函数MB/MD起作用 由此补充对假设可信度的计算 (1)MB(H|E)=0 如果MD(H|E)=1或CF(E)0.2 (2)MD(H|E)=0 如果MB(H|E)=1或CF(E)0.2 (3)MB/MD/CF(H|S)=MB/MD/CF(H|E)*CF(E) 如果CF(E)0.2 否则为0,第7章 不精确推理,84,6.4.3 可信度推理例子,推理规则形式 :=, 设有推理网络如下图所示，其推理规则为 (1)ABH, 0.7 (2)CH, 0.5 (3)(DE)F(GI)H, 0.9 (4)JH, 0.3 每个证据的可信度标在叶子节点的下面，节点分叉带弧者为与节点,第7章 不精确推理,85,推理网络,第7章 不精确推理,86,求解过程(1),求解步骤： (1)CF(H|AB)=0.7*min0.2,0.5=0.14 按照阈值规定可不考虑其对假设H推理的贡献，即下一步不参与计算 (2)CF(H|C)=0.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章 不精确推理,87,求解过程(2),(5)由定义可知 MB1=0.2 MB2=0.36 MB3=0 MD1=0 MD2=0 MD3=0.24 MB=0.2+0.360.2*0.36=0.488 MD=0.24 故CF=MB MD=0.488 0.24=0.248,第7章 不精确推理,88,求解过程(3),如果将CF=0.14计算在内，则 MB=0.14+0.2+0.36 0.14*0.2 0.14*0.36 0.2*0.36+0.14*0.2*0.36 =0.55968 MD=0.24 CF=0.55968 0.24=0.31968 注意：计算的步骤是分别求每个证据的CF或MB/MD，然后用复合证据公式计算MB/MD，最后得CF=MBMD ,第7章 不精确推理,7.5 模糊推理 7.5.1 模糊数据的确定 7.5.2 模糊关系及其投影 7.5.3 模糊推理的例子,第7章 不精确推理,90,7.5.1 模糊数据的确定,确定模糊数据即隶属函数的确定 如何确定隶属函数？有多种方法 调查投票根据投票统计所得的数据确定出隶属函数 用概率分布函数模拟分为3种 (1)正态分布 (2)戒上型函数 (3)戒下型函数,第7章 不精确推理,91,调查投票例子,调查投票根据投票统计所得的数据确定出隶属函数 例子古代选美：明末南京有“秦淮八艳”，要判断谁更漂亮？ 不同人有不同看法，现设有100人投票，可通过与其中一位比较的方法确定一种相对量度 / 设其他7位与李香君比较(得票数少于50者被认为不如她，多者则超过她)，根据每个人所得票数可得隶属函数