《人工智能5.ppt》由会员分享，可在线阅读，更多相关《人工智能5.ppt（112页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能原理人工智能原理第第5 5章章 不确定性推理不确定性推理 本章内容本章内容5.1 不确定性的表示5.2 贝叶斯概率推理5.3 贝叶斯网络5.4 决策网络参考书目第5章 不确定性推理5.1 不确定性的表示5.1.1 不确定性推理的必要性 5.1.2 概率及其公理5.1.3 概率推理第5章 不确定性推理45.1.1 5.1.1 不确定性推理的必要性不确定性推理的必要性不确定性推理也可称为不精确推理对不确定性推理的需求多种多样：推理所需的信息不完备：竞争双方不知道对方信息背景知识不足：疑难病症的机理多种原因导致同一结果：疾病的诊断信息描述模糊：目击者对嫌疑犯的描述信息中含有噪声：做假帐，虚假
2、统计报表，采集数据当中的噪声（雷达、声纳/化验）等第5章 不确定性推理5不确定性推理的原因不确定性推理的原因(1)(1)规则是模糊的：定性描述，如“如果刑事犯罪猖獗，就应加大打击力度”等推理能力不足：天气预报的计算解决方案不唯一：多个方案如何选优的问题确定性推理失败的原因惰性如涉及例外的规则太多，无法枚举理论的无知如人类对于疾病和智能的探索实践的无知如对一个病人的病况的了解和测试第5章 不确定性推理6不确定性推理的原因不确定性推理的原因(2)(2)两种不确定性(uncertainty)环境的不确定性智能体几乎从来无法了解关于其环境的全部事实反映环境的知识的不确定性过于复杂而无组织知识粥(kno
3、wledge soup)对不确定性的描述概率理论统计数据证据组合信度第5章 不确定性推理7不确定环境下的智能体行动不确定环境下的智能体行动从智能体角度看，他不得不在不确定的环境下行动克服这种不确定性的解决方案(1)条件规划(2)使用简单而不完全正确的模型大部分时间模型或者规划可行，但有时会出现矛盾理性决策依赖于各种目标的相对重要性，也依赖于这些目标被实现的可能性第5章 不确定性推理8不确定性下的智能体决策不确定性下的智能体决策不确定性的存在改变了智能体进行决策的方式智能体要在各种规划的不同可能结果之间进行选择(有所偏好)一种结果是一个被完全确定的状态任何状态对于智能体来说都具有一定程度的有用性
4、即效用，智能体将偏好具有更高效用的状态决策理论=概率理论+效用理论理性智能体选择能产生最高效用的行动第5章 不确定性推理9不确定性推理不确定性推理现实的不确定性需要不确定性推理：将数值计算引入推理过程继续使用逻辑联结词真假值概率化，以表示某种可靠程度在推理的前提和结论之间建立概率公式应用：专家系统中的推理网络PROSPECTOR系统MYCIN系统第5章 不确定性推理10贝叶斯网络贝叶斯网络(Bayesian network)(Bayesian network)智能体使用概率对行动结果(用事件之间的联系表示)进行预测，进而选择期望效用最高的行动贝叶斯网络(也叫贝叶斯信念网)是一个节点标注了定量概
5、率信息的有向图，反映了一个事件对于另一个事件的影响程度/表示了变量之间的依赖关系和概率信息贝叶斯网络是事件之间联系的全面而形象的表示第5章 不确定性推理11主观主观BayesBayes主义主义(概率从何而来概率从何而来)主观Bayes主义：现实世界的一些因果关系可以形成一种信念，它并非在所有场合下都正确，可称为部分信念表示这种信念的最好方法是概率方法对概率的解释有若干种，其中一种称为主观Bayes主义/要点：概率是个人的一种合理置信度，每个人的估计(概率)虽然各不相同，但应该满足概率的基本规律和其他某些客观规律，因而是合理的第5章 不确定性推理12知识粥知识粥(Knowledge Soup)(
6、Knowledge Soup)现实世界的复杂性和不确定性反映在智能体内部异质的、不固定的、经常不一致的知识称为知识粥“粥体”包含小块(small chunk)对应于规则、框架等，大块(large chunk)对应于整个理论这些“块”的内部是一致的，“块”之间可以是不一致的从整体来说，知识往往具有这样的特性模糊、不确定、随机、无知第5章 不确定性推理135.1.2 5.1.2 概率及其公理概率及其公理随机变量布尔随机变量定义域=离散随机变量定义域=可数域连续随机变量定义域=实数集合原子事件组成世界的所有随机变量的特定赋值/构成无法确定的世界状态的完整详细描述如X的世界由weather=和 今 天
7、 是 否 喝 酒 drink_today=组成，则有4*2种不同原子事件第5章 不确定性推理14原子事件的性质原子事件的性质(1)原 子 事 件 是 互 斥 的 sunnydrink_today 和sunnydringk_today不能同时成立(2)由 所 有 原 子 事 件 组 成 的 集 合 是 穷 尽 的 至 少 有 一 个 原 子 事 件 一 定 成 立 /所有原子事件的逻辑析取=T(3)任何特定的原子事件与每个命题(简单或者复合命题)的真或假一一对应任何一个表示所在世界状态的命题都可以用原子事件的逻辑联结表示(4)任何一个命题逻辑上都等价于所有蕴涵该命题真值得原子事件的析取sunny
8、等价于sunny drink_todaysunnydrink_today第5章 不确定性推理15先验概率的表示先验概率的表示先验概率：没有任何其它信息存在情况下关于某个命题的信度用向量表示随机变量的先验概率分布P(weather)=同样用向量表示一个离散随机变量集合中全部组合的概率全联合概率分布全联合概率分布用概率表表示P用4*2表格表示第5章 不确定性推理16条件概率的表示条件概率的表示一旦得到先前未知的随机变量的某些证据，先验概率就不再可用条件概率定义由此有乘法定理P(ab)=P(a|b)P(b)=P(b|a)P(a)如果a和b相互独立，则P(a|b)=P(a)P(b|a)=P(b)P(a
9、b)=P(a)P(b)第5章 不确定性推理17概率公理概率公理Bayes概率服从如下公理(Kolmogorov公理)：(1)0P(a)1(2)P(T)=1/P(F)=0(3)P(ab)=P(a)+P(b)P(ab)当a/b互斥有P(ab)=P(a)+P(b)此为加法定理互斥性也就是独立性这样的概率公理是不能违反的(参见p364论证)第5章 不确定性推理18全概率公式全概率公式任何命题a等价于所有a在其中成立的原子事件的析取事件集合记为e(a)由所有原子事件是互斥的，得到如下全联合概率分布一个命题的概率等于所有它在其中成立的 原 子 事 件 的 概 率 和 /满足独立性和完全性第5章 不确定性推
10、理195.1.3 5.1.3 概率推理概率推理全联合概率分布是知识库，从中可得到所有概率的计算命题在其中成立的所有原子事件的概率和P(cavitytoothache)=0.108+0.012+0.072+0.008+0.016+0.064=0.28P(catch)=0.012+0.064+0.008+0.576=0.66第5章 不确定性推理toothachetoothachecatchcatchcatchcatchcavity0.1080.0120.0720.008cavity0.0160.0640.1440.57620边缘化边缘化上述全概率公式从另一个角度可以视为通用化边缘规则：P(Y)=z
11、P(Y,z)=zP(Y|z)P(z)将随机变量的某个变量的分布抽取出来，求和从而得到该变量的无条件概率(或称为边缘概率)/其过程称为边缘化或求和消元(summing out)用于从多个变量的全概率分布中求取某个变量的概率，进行推理第5章 不确定性推理21归一化归一化在一定条件下某个随机变量的绝对概率值可 以 根 据 概 率 公 理 来 归 一 化 一种结果作为分子，同条件各种结果之和作为分母通常，同条件下结果只有2个a/a，故有p(a|*)+p(a|*)=1(*为某种条件)引入归一化常数=1/p(a)+p(a)一般公式：P(X|e)=P(X,e)=yP(X,e,y)解释为：e固定条件下X/Y遍
12、历所有值，构成此时的所有原子事件第5章 不确定性推理22BayesBayes公式公式Bayes公式(也称逆概率公式)从条件概率公式可得在某些场合下引入一个证据e以后，得更通用的Bayes公式第5章 不确定性推理23逆概率公式的例子逆概率公式的例子逆概率公式不仅是条件概率公式的一个简单 变 形，实 际 上 很 有 用 处 如果某个条件概率不便计算，则可以先计算其逆概率，而后算出所要的条件概率例子：求P(肺炎|咳嗽)可能比较困难，但统计P(咳嗽|肺炎)可能比较容易(因为要上医院)/假设P(肺炎)=1/10000，而P(咳嗽)=1/10，90%的肺炎患者都咳嗽，则P(肺炎|咳嗽)=第5章 不确定性推
13、理24修正因子修正因子(1)(1)可以将前面的逆概率公式写成这说明先验概率P(H)可以通过方括号部分(作为修正因子)修正为后验概率P(H|E)(证据E为真时H的后验概率)在上面的例子中，医生认为一个人得肺炎的可能性为万分之一，一旦发现患者咳嗽，就将调整为万分之九第5章 不确定性推理25修正因子修正因子(2)(2)将E看作证据，先验概率P(E)越小，且H为真时E的条件概率P(E|H)越大，则修正因子所起作用越大在上例中，如果P(咳嗽)=0.0001/P(咳嗽|肺炎)=0.9999/P(肺炎)不变则P(肺炎|咳嗽)=0.9999，远远超过原来的万分之九第5章 不确定性推理26后验概率递推公式后验概
14、率递推公式当有n个互相独立的证据，则有公式上式可以写成递推公式形式：上式说明：随着新证据的不断获得，从证据少时的后验概率推出证据多时的后验概率，且每一步都是把上一步的后验概率视为新证据到来时的先验概率第5章 不确定性推理27独立性条件下的推理独立性条件下的推理使用全联合分布表，可以进行查询(推理)/但只适用于变量少的情况N个可能证据变量，则相关条件概率的组合数达到2N条件独立性一旦某个变量的取值确定下来，则其余变量就相互独立对于toothache/cavity/catch三者，cavity决定了其余两者，而它们彼此之间无关系P(toothachecatch|Cavity)=P(toothach
15、e|Cavity)*P(catch|Cavity)第5章 不确定性推理28条件独立性条件独立性给定第3个随机变量Z后，X/Y的条件独立定义为：P(X,Y|Z)=P(X|Z)P(Y|Z)或P(X|Y,Z)=P(X|Z)P(Y|X,Z)=P(Y|Z)则牙科领域3个随机变量有：P(Toothache,Catch|Cavity)=P(Toothache|Cavity)P(Catch|Cavity)和P(Toothache,Cavity,Catch)=P(To,Cat|Cav)P(Cav)=P(To|Cav)P(Cat|Cav)P(Cav)第5章 不确定性推理29条件独立性的结果条件独立性的结果条件概率
16、表(CPT)的分解原概率表有7个彼此独立的数值(23-1)新概率表有5个独立数值(2+2+1)n个变量彼此独立后，表示的规模从O(2n)变为O(n)条件独立性允许概率系统进行规模的扩展；条件独立性比绝对独立性更容易获得此结论导致了朴素贝叶斯模型P(Cause,Effect1,Effectn)=(P(Ei|C)P(C)第5章 不确定性推理5.2 贝叶斯概率推理5.2.1 几率和似然比 5.2.2 贝叶斯概率推理第5章 不确定性推理315.2.1 5.2.1 几率和似然比几率和似然比引入概率的相对量度定义几率：称为H的几率或先验几率，取值范围0,)由此反过来有定义条件几率：第5章 不确定性推理32
17、后验几率和先验几率的关系后验几率和先验几率的关系例子：O(晴天|冬天早晨有雾)=4.2，如果冬天早晨有雾，则该天为晴天的可能性是非晴天可能性的4.2倍由几率定义、条件几率定义和条件概率公式可以推得后验几率和先验几率的关系：第5章 不确定性推理33BayesBayes条件概率条件概率Bayes条件概率：令假设H的先验概率为P(H)，P(H)是指定的/证据E为真时H的条件概率为P(H|E)，P(H|E)的一部分是指定的，一部分是根据P(H)和指定的P(H|E)计算出来的，这部分计算出的概率称为后验概率条件概率P(H|E)可看作以一定概率成立的EH的推理规则第5章 不确定性推理34似然比似然比定义似
18、然比：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)有多个证据独立时，其公式是第5章 不确定性推理35似然比约束似然比约束对LS和LN的约束对于LS和LN有如下约束要求：二者都是非负的，并且满足第5章 不确定性推理365.2.2 5.2.2 贝叶斯概率推理贝叶斯概率推理在Bayes概率推理中，推理规则表示为if E(前提/证据)then H(结论/假设)(LS,LN)括号内LS/LN表示规则强度规则强度=似然比LS=P(E|H)/P(E|H)LN=P(E|H)/P(E|H)其不确定性推理过程是：根据证据E
19、的概率P(E)，利用规则的LS和LN，把结论的先验概率P(H)更新为后验概率P(H|E)，因而也称为概率传播第5章 不确定性推理37似然比应用似然比应用规则强度LS和LN的应用当P(E)=1时，利用LS将先验几率O(H)更新为后验几率O(H|E)/当P(E)=1时，利用LN来更新几率在专家系统PROSPECTOR(一个用于探矿的ES)中同时应用了LS和LN，分别表示正面证据和反面证据的支持，称为充分因子和必要因子，并将LS、LN附着在每条规则之上第5章 不确定性推理38LSLS和和LNLN的作用的作用当LS很大，说明证据成立时假设成立的可能性很大，否则LS1说明E排斥H；LN很小，说明证据不成
20、立时假设不成立的可能性很大LS和LN之值接近1时说明证据成立或不成立对于结论是否成立影响不大一般情况下，LS和LN不是根据定义计算出来的，而是给定的第5章 不确定性推理39应用举例应用举例(1)(1)例子：评职称的概率设某副教授X要评正教授，现有4个指标，却有8人参与竞争/投票前夕，X作了如下预测：如果不考虑评委因素，则成功概率=1/2，此相当于先验几率O(H)=1；如果考虑评委因素，则情况如下：校评委共15人，其中5人来自其他竞争者所在系，4人与X素有微隙，尤其是其中2人兼具来自其他竞争者所在系，对X的成功构成了极大威胁，但聊以自慰的是评委中有5位老朋友，估计会投X的票第5章 不确定性推理4
21、0应用举例应用举例(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=1第5章 不确定性推理41应用举例应用举例(3)(3)若15人全体出席，且假定各条件互相独立，则按公式(6.11)，X评上的后验概率是：O(X评上|15人出席)=
22、根据几率和概率之间的关系，换为概率P=O/(1+O)=1/9，X评上的希望不大第5章 不确定性推理42应用举例应用举例(4)(4)但是，当又有消息说，一位来自其他竞争者所在系兼与X素有微隙的评委A不能出席，而代之以一位态度中立的评委/此时，X又作了一番推测：LS(A出席|X评上)=LN(A出席|X评上)=8LS(中立评委|X评上)=1则在原结果的基础上乘上上述因子，使得后验几率=1，即后验概率=1/2，X评上的前景大大改观第5章 不确定性推理5.3 贝叶斯网络5.3.1 贝叶斯网络的表示5.3.2 贝叶斯网络中的精确推理5.3.3 贝叶斯网络的近似推理第5章 不确定性推理446.3.1 6.3
23、.1 贝叶斯网络的表示贝叶斯网络的表示定义：贝叶斯网络(Bayesian network)是一个有向图，其中每个节点都标注了定量概率信息(1)一个随机变量集合组成网络节点，变量可以是离散的或者连续的(2)一个连接节点对的有向边或者箭头的集合，如果存在从节点X指向节点Y的有向边，则称X是Y的一个父节点(3)每个节点都存在一个条件概率分布P(Xi|Parent(Xi)，量化父节点对该节点的影响(4)图中不存在有向环(是有向无环图DAG)第5章 不确定性推理45例子：防盗警报网例子：防盗警报网从一个例子(防盗警报网)开始第5章 不确定性推理BurglaryEarthquakeAlarmJohnCal
24、lMaryCallP(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 .0146条件概率表条件概率表每个节点旁的条件概率表(简称CPT)中的值对应一个条件事件的概率如P(A)=0.94=P(A|BurglaryEarthquake)条件事件是父节点取值的一个可能组合每行的概率之和应改为1(表中只给出了为真的情况，为假的概率应为1-p)一个具有k个布尔父节点的布尔变量的条件概率表中有2k个独立的可指定的概率(注意概率值是独立的)没 有 父 节 点 的 节 点 的 概 率
25、 只 有 1行 /为先验概率第5章 不确定性推理47全联合概率分布全联合概率分布贝叶斯网络给出了关于相关事件的完整描述，通过计算全联合概率分布求取联合分布中的某项是对每个变量赋予一个特定值情况下的合取概率就是条件概率表中适当元素的乘积例子 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第5章 不确定性推理48链式法则链式法则初始的合取概率化为更小的条件概率和更小的合取式/这些条件概率的合取式实际上就是父节点到子节点的概率乘积链式法则：P(Xi|Xi-1,X1)=P(Xi|Parent(Xi)如果父
26、节点包含于条件Xi-1,X1之中父子节点的关系使得贝叶斯网络具有局部结构化的特性，即每个节点只和数量有限的其它部分产生直接的相互作用第5章 不确定性推理49局部结构化与节点顺序局部结构化与节点顺序由于贝叶斯网络的局部结构化，每个随机变量可以至多受到至多k个其它随即变量的影响(k=常数)设网络中有n个节点(随机变量)，指定每个条 件 概 率 表 所 需 信 息 量 至 多 为 2k个 数 据，则 整 个 网 络 可 以 用 n*2k个数据完全描述/而全联合概率分布需要2n个数据构造贝叶斯网络的次序：添加节点首先从“根本原因”开始，然后加入受其直接影响的变量，直到叶节点(不影响任何其它节点)第5章
27、 不确定性推理50条件独立关系条件独立关系贝叶斯网络中节点相互独立(下面两个定义等价)：(1)给定父节点，一个节点与它的非后代节点是条件独立的(2)给定一个节点的父节点、子节点以及子节点的父节点(Markov blanket)，这个节点对于其它节点都是条件独立的图示第5章 不确定性推理51条件独立关系图示条件独立关系图示第5章 不确定性推理U1UmXZ1jZnjY1YnU1UmXZ1jZnjY1Yn52减少数据量减少数据量利用噪声或关系利用噪声或关系贝叶斯网络中尽管父节点个数k很小，但是要完成条件概率表仍需要O(2k)数据如果找到了变量依赖的某种关系，则可以用O(k)个参数完成条件概率表使用噪
28、声或(noisy-OR)关系用于刻画不确定关系(逻辑或的推广)噪声或关系考虑到每个父节点引起子节点为真的能力的不确定性父节点条件为真但子节点的结果未必为真第5章 不确定性推理53噪声或关系例子噪声或关系例子(1)(1)例子：发烧(fever)为真，当且仅当至少以下三者之一为真：感冒(cold)/流感(flu)/疟疾(malaria)但是可能病人得了以上疾病却没有发烧症状：这就是父节点为真其子节点未必真的不确定性，即父子关系被抑制fever为假：当有多个为真的父节点被抑制，其概率为每个父节点被抑制的概率的乘积两条假设所有原因已经列出每个父节点的抑制独立于其他父节点的抑制第5章 不确定性推理54噪
29、声或关系例子噪声或关系例子(2)(2)假设每个单独抑制的概率如下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第5章 不确定性推理55噪声或关系例子噪声或关系例子
30、(3)(3)第5章 不确定性推理Cold Flu MalariaP(Fever)P(Fever)F F F0.01.0 F F T1-0.1=0.90.1 F T F1-0.2=0.80.2 T F F1-0.6=0.40.6 F T T1-0.02=0.980.1*0.2=0.02 T F T1-0.06=0.940.1*0.6=0.06 T T F1-0.12=0.880.2*0.6=0.12 T T T1-0.012=0.9880.1*0.2*0.6=0.012565.3.2 5.3.2 贝叶斯网络中的精确推理贝叶斯网络中的精确推理概率推理系统中的基本任务：计算被查询变量的后验概率设X为
31、待查询变量/e为观察到的证据(已知)/E=E1Em证据变量集合/Y=Y1Yn既非证据也非查询变量的集合(也称隐变量)全部变量集合=XEY推理的任务是：求后验概率P(X|e)实际上，根据边缘化规则可得P(X|e)=P(X,e)=yP(X,e,y)第5章 不确定性推理57防盗警报网中的查询防盗警报网中的查询防盗警报网第5章 不确定性推理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 .015
32、8查询实例查询实例(1)(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)第5章 不确定性推理59查询实例查询实例(2)(2)进一步代入条件概率：P(b|j,m)=EAP(b)P(E)P(A|b,e)P(j|A)P(m|A)上式最坏复杂度仍然是O(n2n)对所有变量求和改
33、进将相对常数移到求和符号以外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(a|b,e)=0.06第5章 不确定性推理60查询实例查询实例(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
34、)*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第5章 不确定性推理61查询实例查询实例(4)(4)相应地有P(b|j,m)=P(b)*0.2568=0.001*0.2568=*0.000256
35、8类似地有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第5章 不确定性推理62变量消元法变量消元法(1)(1)在计算中我们发现P(j|a)*P(m|a)和P(j|a)*P(m|a)重复计算了两次，如何消除重复？只要保留一次计算结果既可(动态规划)通过点积(pointwise product)求和的方法消去隐含变量二元向量fM(A)=P(m|
36、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)第5章 不确定性推理63变量消元法变量消元法(2)(2)在这样的计算中只要做：计算两个因子的点积在因子乘积中对一个变量求和消元由此消除了重复计算在计算中，消除以下无关节点：删除不是查询变量也非证据变量的叶节点删除所有不是查询变量祖先也不是证据变量祖先的节点第5章 不确定性推理64精确推理的复杂度精确推理的复杂度单连通结构贝叶斯网络中任何两个节点都至多只有一条无向路径相连此时，单连通上的精确推理的时间和空间复杂度都和网络
37、规模呈线性关系而对于多连通结构(见下图)，最坏情况下变量消元法可能具有指数级的时空复杂度此时贝叶斯网络的推理是一个NP问题所以要寻找多连通网络中的近似算法第5章 不确定性推理65多连通网络多连通网络第5章 不确定性推理S R P(W)T T .99T F .90F T .90F F .00C P(R)T .80F .20sprinklerRainWet grassC P(S)T .10F .50P(C)=.5cloudy666.3.3 6.3.3 贝叶斯网络的近似推理贝叶斯网络的近似推理大规模多连通网络的精确推理是不可操作的，所以要考虑近似的推理方法采用随机采样方法，也称蒙特卡罗算法(Mont
38、e Carlo algorithm)：给出问题的近似解答，近似的精度依赖于所生成采样点的多少此处近似的含义不是通过计算求出网络中某个点的条件概率(因为复杂度高)，而是对该事件进行采样而获得概率第5章 不确定性推理67蒙特卡罗蒙特卡罗(Monte Carlo)算法算法一种概率算法当算法在执行过程中面临一个选择时，随机性选择常比最优选择节省时间特点：对所求解问题的同一个实例用同一个概率算法求解两次，可能得到完全不同的效果蒙特卡罗算法用于求问题的精确解保证对问题所有实例都以高概率给出正确解，但通常无法判定一个具体解是否正确正确解的概率依赖于算法所用时间第5章 不确定性推理68蒙特卡罗蒙特卡罗(Mon
39、te Carlo)算法思想算法思想设1/2p1是一个实数，如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该算法是p正确的，且称p-1/2是该算法的优势如果对同一实例，蒙特卡罗算法不会给出两个不同的正确解答，则称该算法是一致的对于一个一致的p正确蒙特卡罗算法，要提高获得正确解的概率，只要执行该算法若干次，选择出现频次最高的解即可第5章 不确定性推理69后验概率计算的采样方法后验概率计算的采样方法有两类采样方法：直接采样方法计算样本的频率马尔科夫链采样方法根据马尔科夫覆盖中的变量当前值来采样直接采样方法依据已知概率来生成样本拒绝采样算法/似然加权算法马尔科夫链采样方法证据变量
40、概率固定条件下随机生成样本第5章 不确定性推理70直接采样方法直接采样方法直接采样方法是按照拓扑结构次序依次对每个变量进行采样，被采样变量值的概率分布依赖于父节点已取得的赋值具体实现：拒绝采样算法首先按照先验概率分布采样，然后排除所有与证据不匹配的样本，最后计算样本频率似然加权证据变量的值用权值(条件概率)来表示，只对非证据变量进行采样第5章 不确定性推理71采样样本与概率分布采样样本与概率分布样本的向量表示cloudy,sprinkler,rain,wetGrass F/T或者0/1表示为假或为真/如T,F,T,T采样按照已知概率分布进行，但不是等于这个概率分布值，而是说分布与之相符clou
41、dy=0.5,0.5/第1次采样49/51，第2次采样52/48如此等等每次采样应该在一定的条件下(这就是条件概率)进行，不满足条件的样本不再考虑第5章 不确定性推理72采样过程举例采样过程举例(1)(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/样
42、本形式类似于(2)第5章 不确定性推理73采样过程举例采样过程举例(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第5章 不确定性推理74拒绝采样方法拒绝采样方法从已知分布的采样出发(其计算如上)，通过去掉不满足证据条件的样本来计算(估计)那些未知分布的事件的概率例子：P(Rain|Sprinkler=T)未知其概率/采样100个样本其中73个为，不满足
43、前提条件余下的27个中8个为rain=T/19个为rain=FP(Rain|Sprinkler=T)=拒绝采样方法的最大问题就是效率比较低(相当一部分样本被拒绝了)第5章 不确定性推理75一致的估计一致的估计拒绝采样方法能产生真实概率的一致估计估计的概率在无限多(大量样本的极限)条件下成为精确值，这样的估计称为一致的(consistent)，即P(x1,xm)=NPS(x1,xm)/N第5章 不确定性推理76似然加权方法似然加权方法(1)(1)对证据节点的概率进行似然加权，即按照先验概率的乘积进行计算/对非证据节点进行采样，采样样本服从先验概率分布例子：求P(rain|sprinkler=T,
44、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第5章 不确定性推理77似然加权方法似然加权方法(2)(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/解释：s
45、prinkler=T&wetGrass=T条件下rain=T的概率很低似然加权方法也得到对于真实概率的一致估计/从采样与加权的乘积去理解联合分布概率的计算，依然是全部条件概率的乘积第5章 不确定性推理78马尔科夫链采样马尔科夫链采样(1)(1)直接采样法按照先验概率去采样马尔科夫链采样对证据变量以外的变量每次随机地采样举例：考虑求P(rain|sprinkler=T,wetGrass=T)证据变量固定sprinkler=T/wetGrass=T隐变量cloudy/rain则随机采样初始值不妨假设cloudy=T/rain=F初始状态=第5章 不确定性推理79马尔科夫链采样马尔科夫链采样(2)(
46、2)然后反复按照以下2个步骤采样(1)当前条件下对cloudy随机采样，结果=(2)当前条件下对rain随机采样，结果=最后得到若干样本，例如rain=T=20/rain=F=60，则P(rain|sprinkler=T,wetGrass=T)=第5章 不确定性推理80马尔科夫链采样的合理性马尔科夫链采样的合理性(1)(1)马尔科夫链采样过程最终会进入“动态平衡”状态被采样变量服从马尔科夫覆盖下的条件概率分布，且“稳态分布”=真实后验概率P(x|e)我们所需要求解的正是给定证据变量e下某个变量的概率值P(x|e)证明过程：转移概率状态x到状态xq(xx)时刻t处于状态x的概率t(x)第5章 不
47、确定性推理81马尔科夫链采样的合理性马尔科夫链采样的合理性(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简单公式推导(求和)可证明细致平衡中蕴含着稳态分布第5章 不确定性推理82马尔科夫链采样的合理性马尔科夫链采样的合理性(3)(3)前述马尔科夫链采样过程称为Gibbs采样器，其转移概率写为：q(xx)=q(xi,xi)(
48、xi,xi)=P(xi|xi,e)由此证明满足细致平衡(p398)，也就是稳态分布而P(xi|xi,e)正是所求的贝叶斯网络中条件概率最终每个时刻的状态概率值都相同第5章 不确定性推理5.4 决策网络5.4.1 效用函数 5.4.2 决策网络第5章 不确定性推理845.4.1 5.4.1 效用函数效用函数不确定性常常反映在决策时用多种可能结果供选择怎样选择？取决于决策者偏好表示为效用(utility)决策理论=效用+概率效用表示=效用函数效用+行动结果的概率每个行动(决策)的期望效用EU决策智能体选择具有最大期望效用(MEU,Maximum Expected Utility)的行动第5章 不确
49、定性推理85最大化期望效用最大化期望效用期望效用计算公式EU(A|E)=iP(Resulti(A)|Do(A),E)*U(Resulti(A)A=行动/E=关于环境的可用证据最大期望效用MEU一个理性智能体应该选择最大化期望效用的那个行动A*=argmax A P*UMEU原则如果一个智能体最大化一个效用函数，而此效用函数是关于智能体行为判断的正确性能度量，则当在智能体放置环境中取平均时，该智能体获得可能性能分数的最高值第5章 不确定性推理86期望效用所涉及的计算期望效用所涉及的计算回顾第1章基于效用的智能体结构一个智能体所要做的全部就是计算各种量值，在行动上使效用最大化，然后采取行动为实现M
50、EU，必须计算其中的各种量值，通常是非常复杂和很难形式化的行动序列枚举对于长序列来说不可行分为单个行动的决策(简单决策)/序列行动决策(复杂决策)感知环境因果模型搜索或者规划第5章 不确定性推理87理性偏好及约束理性偏好及约束关于一个理性智能体偏好的定义A B 偏好A甚于BA B 无偏向A或B皆可A B 上述两者的或偏好关系上的合理约束，也称效用公理有序性传递性连续性可替换性单调性可分解性A/B的典型例子是彩票第5章 不确定性推理88效用原则效用原则效用原则：如果一个智能体的偏好遵守效用公理，那么存在一个状态上进行运算的实值函数U，使得如下关系成立：最大期望效用原则：总效用等于把每个结果的概率