人工智能不确定推理ppt课件.ppt

第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,基本概念,不精确思维并非专家的习惯或爱好所至，而是客观现实的要求。很多原因导致同一结果推理所需的信息不完备背景知识不足信息描述模糊信息中含有噪声规划是模糊的推理能力不足解题方案不唯一,基本概念,什么是不确定性推理从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。事实与结论之间存在着不确定的因果关系，且事实也是不确定的。,基本概念不确定推理的基本问题,不确定问题的数学模型表示的3方面问题表示问题：采用什么方法描述不确定性，这是解决不确定推理关键的一步。计算问题：不确定性的传播和更新。也是获取新信息的过程。语义问题：上述表示和计算的含义是什么。,基本概念不确定推理的基本问题,表示问题：表达要清楚。表示不仅仅是数，还要有语义描述。通常有数值表示和非数值表示方法，两者都不够完善。数值表示便于计算、比较，再考虑到定性的非数值描述才能较好的解决不确定问题。知识的不确定性描述（静态强度）通常是一数值，一般由领域专家给出。证据的不确定性描述（动态强度）也是一数值，除初始证据由用户给定外，一般通过传递算法计算得到。,例： E H , 已知f (H , E)和C(E)，计算求得C(H)。,基本概念不确定推理的基本问题,计算问题：不确定性的传播和更新算法。包括已知规则 E H 的强度f (H , E)和前提的不确定性C(E)，如何计算结论的不确定性 C(H) = g1(C(E),f(H,E)已知某命题H的不确定性C1(H)，又根据新的证据求得C2(H),如何计算新的C(H) = g2(C1(H),C2(H)定义算法g3，使C(E1 E2) = g3(C(E1),C(E2)定义算法g4，使C(E1 E2) = g4(C(E1),C(E2),基本概念不确定推理的基本问题,语义问题：将各个公式解释清楚。例如规则 E H 的强度f (H , E)有E为真，H为真，则f (H , E) = ？E为真，H为假，则f (H , E) = ？E对H没有影响，则f (H , E) = ？前提 E 的不确定性度量C (E)有E为真，则C ( E) = ？E为假，则C ( E) = ？对E 一无所知，则C ( E) = ？,基本概念不确定推理方法的分类,模型方法：把不确定的证据和不确定的知识分别与某种度量标准对应起来，并且给出更新结论的算法，从而构成了相应的不确定性推理模型。,控制方法：通过识别领域中引起不确定性的某些特征及相应的控制策略来限制或减少不确定性对系统的影响，此类方法没有处理不确定性的统一模型，其效率极大地依赖于控制策略。,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,概率方法,经典概率方法 E H用概率P(H|E)表示结论H的确定性程度。问题：实际情况P(H|E)不容易求。而 P(E|H)较易求。逆概率方法 E Hi 用概率P(Hi|E)表示结论Hi的确定性程度。 P(Hi|E) = i=1,2,3,n优点：理论背景强。缺点：求P(Hi) 、P(E|Hi)困难,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,主观贝叶斯方法,概述在Prospector的探矿系统的研究过程中提出的。 原有贝叶斯公式只考虑E出现对H的影响，没有考虑E不出现的影响。 贝叶斯规则：当H为n个互不相容事件的集合时，Bayes公式可写为：,主观贝叶斯方法,思路采用Bayes公式必须有较多的有效 样本集，且存在“关联数据”问题，即要知道在Hi下E存在的概率。实际应用中无法实现，需“修正”。先定好应该怎么办，再凑公式。主要是避开P(E| H)的计算。,主观贝叶斯方法,修正的Bayes公式设只有一个证据E和一个结论H ，则（1）（2）相除，得,主观贝叶斯方法,修正的Bayes公式设 O(H) = P(H) / P(H)为H的先验机率， O(H|E) = P(H|E) / P( H|E)为H的后验机率。则（3）式为同理，有即为修正的Bayes公式 ,主观贝叶斯方法（规则的不确定性）,几率函数O(H),O(H)的性质P(H) = 0时, O(H) = 0假P(H) = 0.5时, O(H) = 1P(H) = 1时, O(H) = 真 ,主观贝叶斯方法,规则的不确定性定义：,表示E为真时，对H为真的影响。（规则成立的充分性）,表示E为假时，对H为真的影响。（规则成立的必要性）,主观贝叶斯方法（规则的不确定性）,则：O(H)与LN，LS的关系O(H|E) = LS O(H)O(H|E) = LN O(H),主观贝叶斯方法（规则的不确定性）,，且必须满足：,主观贝叶斯方法（规则的不确定性）,LS、LN，不是独立取值的。LS, LN不能同时 或 LS, LN可同时1在实际系统中， LS, LN的值是由专家凭经验给出的，而不是依LS, LN的定义来计算的。,主观贝叶斯方法（证据E的不确定性）,P(E)或O(E)表示证据E的不确定性,主观贝叶斯方法（推理计算1）,E必出现时：O(H|E) = LSO(H)O(H|E) = LNO(H) 若需要概率时：,主观贝叶斯方法（推理计算1）,例：有如下推理图，问当Ei(i-=1,2,3,4,5)存在或不存在时，H的先验概率P(H)=0.03应如何变化？,R2:300,1,R5:1,0.0002,R3:7.5,1,R4:6,1,主观贝叶斯方法（推理计算2）,E不确定时：即P(E) 1 （1976年的算法）向前看一步E， E 为与E有关的所有观察 P(H|E) = P(H|E)P(E| E)+P(H|E)P(E| E) P(E| E) = 1时，证据E必然出现（P168）P(E| E) = 0时，LN代替上式 的LS， P(E| E) = P(E) 时，(E对E无影响)，由上式 P(H| E) = P(H),主观贝叶斯方法（推理计算2）,P(E| E)与P(H| E)坐标系上的三点： 总之是找一些P(E| E)与P(H| E)的相关值， 两点也可以做曲线（或折线、直线）。由插值法从线上得到其它点的结果，具体过程见教科书上例题。,主观贝叶斯方法（推理计算2）,P(H|E) = P(H|E)P(E| E)+P(H|E)P(E| E) P.185,主观贝叶斯方法（推理计算2）,证据不确定的情况下的EH公式 (P.186),0 =P(E|E)= P(E),P(E) =P(E|E)= 1,主观贝叶斯方法（推理计算2）,例：求P(HY | E1)=?,300,0.001,P(H)=0.03,P(HY)=0.01,主观贝叶斯方法（推理计算3）,两个证据时：,主观贝叶斯方法,主观Bayes方法的评价优点：计算方法直观、明了。缺点：要求Hj相互无关（实际不可能）。P(E| H)与P(Hi) 很难计算。应用困难。,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,可信度方法（可信度的概念）,可信度（信任度Degree of confirmation）：又称证据强度，即一个证据对结论的支持程度。 可信度的完备条件Dc1: IF E H THEN Dc(H|E) = max （当E肯定H时，Dc值最大）Dc2: IF E H THEN Dc(H|E) = min （当E肯定 H时，Dc值最小）Dc3: Dc(HE|E) = Dc(H|E) （重复证据的获取不应该增加对结论的信任度）Dc4: IF E 、H 相互独立 THEN Dc(H|E) = 0,可信度方法（可信度的概念）,可信度的设计（能反映专家主观判断知识）便于专家使用，如取值范围要直观、方便。在证据不断出现时，可以累加修改，取得肯定的证据时其值增加，出现否定的证据时其值减少。当证据绝对肯定结论时，取最大值，否则取最小值。累加的最终值不应该超过度量的极限值。同一个证据对几个互斥的结论产生影响时，其度量值之和不应该超过极限值。能用于非确定证据的推理。重复的证据不应该改变其累加值。,可信度方法（确定性方法、C-F模型）,MYCIN系统研制过程中产生的不确定推理方法,第一个采用了不确定推理逻辑，70年代很有名。 提出该方法时应遵循的原则不采用严格的统计理论。使用的是一种接近统计理论的近似方法。用专家的经验估计代替统计数据尽量减少需要专家提供的经验数据，尽量使少量数据包含多种信息。新方法应适用于证据为增量式地增加的情况。专家数据的轻微扰动不影响最终的推理结论。,理论基础以定量法为工具，比较法为原则的相对确认理论。采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则规则的不确定性度量证据（前提）的不确定性度量。推理计算。,可信度方法,理论基础以定量法为工具，比较法为原则的相对确认理论。采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则规则的不确定性度量证据（前提）的不确定性度量。推理计算。,可信度方法,理论基础以定量法为工具，比较法为原则的相对确认理论。采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则规则的不确定性度量证据（前提）的不确定性度量。推理计算。,可信度方法,规则 (规则的不确定性度量）,规则 E H，可信度表示为CF(H,E)。定义 CF(H, E) = MB(H, E) - MD(H, E) 其中 MB(H, E) 为,规则 (规则的不确定性度量）,规则 E H，可信度表示为CF(H,E)。定义 CF(H, E) = MB(H, E) - MD(H, E) 其中 MD(H, E) 为,规则 (规则的不确定性度量）,规则 E H，可信度表示为CF(H,E)。定义 CF(H, E) = MB(H, E) - MD(H, E) 其中 MB(H, E)指示信任量度 MD(H, E)指示不信任量度 由定义知，MB和MD不可能同时 0，事实上如果MB0，则MD=0（E有利于H）；如果MD0，则MB=0 （E不利于H） 。,规则 (规则的不确定性度量）,当p(H/E)p(H)时，表示证据E支持结论H，则有MB0，MD=0； 反之，当p(H/E)0； 当p(H/E)p(H)时，表示E对H无影响，则有MBMD0。 值得注意的是，可信度CF(H, E)(即MB, MD)的值通常并不是经由p(H/E)和P(H)来计算的，而是在建立规则库时由领域专家凭经验主观确定的。,规则 (规则的不确定性度量）,规则可信度CF(H,E)有性质：1.因为0MB(H, E) 1,0 MD(H, E) 1,则-1 CF(H, E) 12.若E绝对肯定H，即P(H|E)=1，则MB(H, E) =1, MD(H, E) =0, CF(H, E) =1 .Dc13.若E绝对否定H，即P(H|E)=1，则MB(H, E) =0, MD(H, E) =1, CF(H, E) = -1 .Dc24.若E不能证实H或E、H独立，即P(H|E)=P(H)，则MB(H, E) =0, MD(H, E) =0, CF(H, E) = 0 .Dc45.对同一个证据E，支持若干个互斥的结论Hi，则 CF(Hi, E)1 .Dc3,规则 (规则的不确定性度量）,规则 E H，可信度表示为CF(H,E)。,规则 (规则的不确定性度量）,CF(H, E)表示的意义证据为真时相对于P(H) = 1 - P(H)来说，E对H为真的支持程度。即E发生更支持H发生。 此时 CF(H, E) 0。 或，相对于P(H)来说，E对H为真的不支持程度。即E发生不支持H发生。 此时 CF(H, E) 0。 结论-1 CF(H, E) 1,规则 (规则的不确定性度量）,CF(H, E)的特殊值：CF(H, E) = 1，前提真，结论必真CF(H, E) = -1，前提真，结论必假CF(H, E) = 0 ， 前提真假与结论无关实际应用中CF(H, E)的值由专家确定，并不是由P(H|E), P(H)计算得到的。,理论基础以定量法为工具，比较法为原则的相对确认理论。采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则规则的不确定性度量证据（前提）的不确定性度量。推理计算。,可信度方法,理论基础以定量法为工具，比较法为原则的相对确认理论。采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则规则的不确定性度量证据（前提）的不确定性度量。推理计算。,可信度方法,规则 (证据的不确定性度量）,证据E的可信度表示为CF( E )同样有：-1 CF( E ) 1特殊值：CF( E ) = 1， 前提肯定真 CF( E ) = -1， 前提肯定假CF( E ) = 0，对前提一无所知CF( E ) 0， 表示E以CF( E )程度为真CF( E ) 0， 表示E以CF( E )程度为假,理论基础以定量法为工具，比较法为原则的相对确认理论。采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则规则的不确定性度量证据（前提）的不确定性度量。推理计算。,可信度方法,理论基础以定量法为工具，比较法为原则的相对确认理论。采用此方法的MYCIN系统的诊断结果不是只给出一个最可信结论及其可信度，而是给出可信度较高的前几位，供人们比较选用。 规则规则的不确定性度量证据（前提）的不确定性度量。推理计算。,可信度方法,规则 (推理计算 1）,“与”的计算： E1 E2 HCF(E1 E2 ) = min CF(E1), CF(E2 )“或”的计算：E1 E2 HCF(E1 E2 ) = max CF(E1), CF(E2 ) “非”的计算：CF(E ) = - CF(E ) 由E， E H，求 H： CF(H) = CF(H,E ) max 0, CF(E) (CF(E) 0 时可以不算即为“0”),规则 (推理计算 2）,更新，由两条规则求出再合并： 由CF(H)、 CF(H)，求 CF(H),可信度方法,例：有以下规则R1: If e1 then h (0.9) R2: If e2 then h (0.7)R3: If e3 then h (-0.8)R4: If e4 and e5 then e1 (0.7)R5: If e6 and (e7 or e8) then e2 (1)设系统在问题求解过程中已经获得 CF(e3)=0.3,CF(e4)=0.9,CF(e5)=0.6,CF(e6)=0.7,CF(e7)=-0.3,CF(e8)=0.8求 CF(H)=?,可信度方法,评论可信度方法的宗旨不是理论上的严密性，而是处理实际问题的可用性。 不可一成不变地用于任何领域，甚至也不能适用于所有科学领域。推广至一个新领域时必须根据情况修改。,可信度方法,尽管确定性方法使MYCIN和其它一些专家系统能简单有效地实现不确定性推理，但仍存在不少问题。现归纳如下： （1）如何将人表示可信度的术语转变为数字化的CFs。例如，人的经验规则常涉及很可能、不大可能等术语，应对应到多大的CF值。 （2）如何规范化人们对可信度的估计，不同人所作的估计往往相差较大。,可信度方法,（3）为防止积累误差，需指定门槛值，但多大合适呢？太小固然不行，但太大也不好，因为可信度的传递需要累计较小的变化。 （4）为改进可信度的精确性，需提供从系统的实际执行反馈的信息，并基于反馈信息调整可信度。这实际上是一种机器学习问题，尚未较好地加以解决。 正因为这些问题的存在，限制了MYCIN提出的确定性方法只能用于对不确定推理的精度要求不高的场合。,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,第五章 不确定性推理,基本概念概率方法主观Bayes方法可信度方法证据理论,证据理论 (Evident Theory),概述证据的不确定性应用模型推理计算,证据理论 (Evident Theory),概述由Dempster首先提出，并由他的学生Shafer发展起来，也称D-S理论。在专家系统的不精确推理中已得到广泛的应用。 （也用在模式识别中）证据理论中引入了信任函数，它满足概率论弱公理。在概率论中，当先验概率很难获得，但又要被迫给出时，用证据理论能区分不确定性和不知道的差别。所以它比概率论更合适于专家系统推理方法。当概率值已知时，证据理论就成了概率论。因此，概率论是证据理论的一个特例，有时也称证据论为广义概率论。,证据理论 (Evident Theory),概述证据的不确定性应用模型推理计算,证据理论 (Evident Theory),概述证据的不确定性应用模型推理计算,证据理论 (证据的不确定性),证据： 用集合D来表示：如D中的每个元素代表一种疾病。讨论一组疾病A发生的可能性时，A变成了单元（某些假设）的集合。D内元素Ai间是互斥的，但Ai中元素间是不互斥的。,证据理论 (证据的不确定性),基本概率分配函数： M：D0,1（在D的幂集D上定义，取值0,1）M(A)表示了证据对D的子集A成立的一种信任度有： 空集为零 意义若A D，且A D，表示对A的精确信任度若A = D，表示这个数不知如何分配,证据理论 (证据的不确定性),基本概率分配函数：例，某个体的颜色只可能为红、兰、绿，则建立相应论域D = 红，兰，绿。可以给D的所有子集分配基本概率，如：M(红，兰，绿,红，兰, 红，绿, 兰，绿, 红, 兰, 绿, ) =( 0.2， 0.2， 0.2， 0， 0.3， 0， 0.1， 0)。则M(红,兰) = 0.2意指该个体颜色为红或兰的信任程度是0.2。0.2不是分配给红就是给兰。注意，M是2 D上而非 D上的概率分布，所以基本概率 M(A)不必等于概率P(A)，而且M(A) 1。,证据理论 (证据的不确定性),信任函数Bel：D0,1。 （在D的幂集D上定义，取值0,1）Bel(A) = 有: Bel() = M() = 0 , Bel(D) = = 1 Bel类似于概率密度函数，表示A中所有子集的基本概率分配数值的和，用来表示对A的总信任度。,证据理论 (证据的不确定性),信任函数在上例中， D = 红，兰，绿，M(红，兰，绿,红，兰, 红，绿, 兰，绿, 红, 兰, 绿, ) =( 0.2， 0.2， 0.2， 0， 0.3， 0， 0.1， 0)。 则 Bel(兰，绿) = M(兰) + M(绿) + M(兰，绿) = 0 + 0.1 + 0 = 0.1。 Pl(红,绿) = 1- Bel(兰) = 1- 0 = 1,证据理论 (证据的不确定性),似然函数（不可驳斥函数）Pl：D0,1。（在D的幂集D上定义，取值0,1）Pl(A) = 1 - Bel(A) = 性质：0 Bel(A) Pl(A) 1 ( Bel是Pl的一部分) 称Bel(A)和Pl(A)是A的下限不确定性值和上限不确定性值。,证据理论 (证据的不确定性),设函数ABel(A), Pl(A) ，则有如下特殊值： A0,1：表示对A一无所知 A1,1：表示A为真 A0,0：表示A为假Aa,1：表示对A的部分信任, 0a1A0,b：表示对A的部分信任, 0b1Aa,b：表示同时对A和A的部分信任,证据理论 (证据的不确定性),似然函数（不可驳斥函数）在上例中， D = 红，兰，绿，M(红，兰，绿,红，兰, 红，绿, 兰，绿, 红, 兰, 绿, ) =( 0.2， 0.2， 0.2， 0， 0.3， 0， 0.1， 0)。Bel(兰，绿) = 0.1则 Pl(红) = 1 - Bel(兰，绿) = 1 - 0.1= 0.9。 又 Bel (红) = 0.3 所以红0.3 , 0.9 表示 红的精确信任为0.3，不可驳斥部分为0.9，即肯定不是红为1-0.9=0.1。,证据理论 (推理计算),综合概率分配函数（正交和）（对于同样的证据，由于来源不同，得到二个概率分配函数M1, M2 ）定义：M = M1 M2 规定：M() = 0 ， M(A) = 其中 K1且 K 0。若K 0，认为M1，M2矛盾，没有联合基本概率分配函数 。,证据理论 (推理计算),综合概率分配函数（正交和）举例：设：D=p,q M1(p,q,p,q,)=(0.4,0.4,0.2,0) M2(p,q,p,q,)=(0.5,0.4,0.1,0)k=1-(M1(p)M2(q)+ M1(q)M2(p) =1-0.4*0.4-0.4*0.5 = 0.64M(p) = M1(p)M2(p)+M1(p)M2(p,q)+M1(p,q)M2(p)/k = (0.4*0.5+0.4*0.1+0.2*0.5)/0.64 = 0.53125M(q) = 0.4375 M(p,q) = 0.03125则 M( p , q , p,q , ) = ( 0.53 , 0.44 , 0.03 , 0 ),证据理论,概述证据的不确定性应用模型推理计算,证据理论,概述证据的不确定性应用模型推理计算,证据理论 (应用模型),针对一个特殊的概率分配函数讨论一种具体的不精确推理模型：设：D=s1,s2,sn,在D上定义的概率分配函数M满足 1）M(si) 0 对任何si D 2) M(si) 1 3) M(D) = 1- M(si) 4）M(A) = 0， 当A D 且 |A|1 或 |A|=0时,这里定义了基本理论的一个特殊情况，仅单个元素组成的子集的概率分配数大于等于0；由一个以上元素组成的子集概率分配数均为0。,证据理论 (应用模型),则： 1）Bel(A)= M(si) 对任何si A 2) Bel(D)=M(si) + M(D)=1 3) Pl(A)=1-Bel(A) = 1- M(si) 对任何si A =1-1-M(D)-Bel(A) =M(D) + Bel(A) 4）Pl(D)=1-Bel(D)= 1-Bel() =1,证据理论 (证据的不确定性),定义：命题A的类概率函数其中|A|、|D|为集合内元素个数。 性质： 对于A D f ( si ) = 1，i=1,2, ,nBel (A) f (A) Pl (A) f (A) = 1 - f (A),f () = 0， f (D) = 1， 0f (A)1,证据理论 (规则的不确定性),推理形式：设子集合E、A，其中E = e1, e2, , el, A = a1, a2, , ak，用相应的向量(c1, c2, , ck)描述 规则 EA ，其中：ci0, 1ik, 且cj1， 1jk 用于指示前提E成立时假设ai成立的可信度。已知事件E，由f (E)求M(ak) , M(ak) = f (E) ck,证据理论 (证据的不确定性),设规则 E A =a1，a2，am ,CF 其中 CF=C1，C2，Cm 证据E的不确定性可以用类概率函数f (E)表示，原始证据的f (E)应由用户给定，作为中间结果的证据则由下面的不确定性传递算法确定。,证据理论 (证据的不确定性),命题的确定性CER定义 设A是规则条件部分的命题，E是外部输入的证据和已证实的命题，命题A与E的匹配程度MD(A|E)为 若A的所有元素出现在E里，则MD(A|E)=1，否则MD(A|E)=0 则 CER(A)=MD(A|E)*f(A) 称为命题A的确定性。 可以证明 0 CER(A) 1,证据理论 (不确定性传递算法),对于上述具有不确定性的规则，定义 (i = 1,2,m)或缩简记为 规定 ，则对于U的所有其它子集H，均有 m(H)0；所以当A为U的真子集时，有 进一步可以计算Pl(A)和f(A)。,证据理论,概述证据的不确定性规则的不确定性推理计算,证据理论,概述证据的不确定性规则的不确定性推理计算,证据理论 (推理计算),f (E1E2) = min f (E1), f (E2) f (E1E2) = max f (E1), f (E2) 已知:f (E)，E A，(c1, c2, , ck)。 求:f (A)规定：M(a1, a2, ,ak) = (f (E)c1,f (E)c2, f (E)ck) M (D) = 1 ,证据理论 (推理计算),证据的组合：M1, M2在D上的合成 （对于同样的证据，由于来源不同，得到二个概率分配函数M1, M2 ）定义：M = M1 M2 规定：M() = 0 ，M(si) =其中 KM1(D)M2(D)+,证据理论 (举例),设有如下推理规则：,证据理论 (举例),Ei（i = 1,2,6）是原始证据，用户在系统运行时已给定它们的类概率如下： 设定|U|10，求假设 A的确定性。 这些规则形成与或形推理树（如图）。,证据理论 (举例),0.5 0.7 0.9 0.9 0.8 0.7,证据理论 (优缺点),优点：直观地表示了不了解的部分。 缺点： 推理（如辨别框的划分）较困难，缺乏实践检验。,第五章 不确定性推理,基本概念概率方法主观Bayes方法,可信度方法证据理论贝叶斯网络,第五章 不确定性推理,基本概念概率方法主观Bayes方法,可信度方法证据理论贝叶斯网络,贝叶斯网络,二十世纪八十年代贝叶斯网络（Bayes Network）成功地应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。基于贝叶斯方法的贝叶斯网络是一种适应性很广的手段和工具，具有坚实的数学理论基础。在综合先验信息（领域知识）和数据样本信息的前提下，还可避免只使用先验信息可能带来的主观偏见。虽然很多贝叶斯网络涉及的学习问题是NP难解的。但是，由于已经有了一些成熟的近似解法，加上一些限制后计算可大为简化，很多问题可以利用近似解法求解。,贝叶斯网络,贝叶斯网络方法的不确定性表示基本上是保持了概率的表示方式，可信度计算也是概率计算方法，只是在实现时，各具体系统根据应用背景的需要采用各种各样的近似计算方法。推理过程称为概率推理。因此，贝叶斯网络没有其它确定性推理方法拥有的确定性表示、计算、语义解释等问题。本节只介绍贝叶斯网络的基本概念和简单的推理方法。,贝叶斯网络（事件的独立性）,独立：如果X与Y相互独立，则 P(X,Y) = P(X)P(Y) P(X|Y) = P(X)条件独立：如果在给定Z的条件下，X与Y相互独立，则 P(X|Y, Z) = P(X|Z)实际中，条件独立比完全独立更重要,贝叶斯网络（联合概率）,联合概率：P(X1, X2, , XN)二值，则有2N可能的值，其中2N-1个独立。如果相互独立： P(X1, X2, , XN) = P(X1) P(X2) P(XN),贝叶斯网络（联合概率）,条件概率： P(X1, X2, , XN) = P(X1|X2, , XN) P(X2, , XN)迭代表示：P(X1, X2, , XN) = P(X1) P(X2| X1) P(X3| X2X1)P(XN|XN-1, , X1) = P(XN) P(XN-1| XN) P(XN-2| XN-1XN)P(X1|X2, , XN) 实际应用中就是利用条件独立性的性质简化网络复杂性的。,贝叶斯网络（基本概念）,贝叶斯网络：一系列变量的联合概率分布的图形表示。一个表示变量之间的相互依赖关系的数据结构；图论与概率论的结合。,贝叶斯网络（因果关系网络）,假设：命题S(smoker)：该患者是一个吸烟者命题C(coal Miner)：该患者是一个煤矿矿井工人命题L(lung Cancer)：他患了肺癌命题E(emphysema)：他患了肺气肿由专家给定的假设可知，命题S对命题L和命题E有因果影响，而C对E也有因果影响。,贝叶斯网络（因果关系图例）,命题之间的关系可以描绘成因果关系网。每一个节点代表一个证据，每一条弧代表一条规则（假设），连接结点的弧表达了有规则给出的，节点间的直接因果关系。,因果关系图例:其中，节点S，C是节点L和E的父节点或称双亲节点，同时，L，E也称为是S和C的子节点或称后代节点。,贝叶斯网络（贝叶斯网络）,贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络 。如果A是B的父结点，P(B|A)就是这两个结点的连接强度；如果C也是 B的一个双亲结点，则用联合概率P(B|AC)来描述。当结点没有父结点时，称为顶点。贝叶斯网必须指定顶点的先验概率。,贝叶斯网络（图例）,贝叶斯网络图例无环图和指定概率值P(A), P(C), P(B|AC), P(E|B), P(B|D), P(F|E), P(G|DEF),贝叶斯网络（图例）,贝叶斯网是一个有向无环图。如果结点间有反馈回路，从各个方向就可以得到不同的连接权值，而使得最后难以确定。右图是一个有环的网络，不是贝叶斯网。,非贝叶斯网络图例,贝叶斯网络（定义）,两个部分贝叶斯网络结构图，这是一个有向无环图（DAG: Directed Acyclic Graph），其中图中的每个节点代表相应的变量。当有向弧由节点A指向节点B时，则称：A是B的父节点；B是A的子节点。节点和节点之间的条件概率表（Conditional Probability Table, CPT），也就是一系列的概率值，表示了局部条件概率分布。P(node|parents) 。目的：由证据得出原因发生的概率。 即观察到P(Y)，求P(X|Y),贝叶斯网络（如何构造）,选择变量，生成节点 从左至右（从上到下），排列节点填充网络连接弧，表示节点之间的关系得到条件概率关系表,贝叶斯网络（计算）,有向非循环图是各个节点变量关系传递的合理表达形式。条件概率的引入使得计算较之全连接网络有了大大的简化。条件概率表（CPT表）相对比较容易得到。 有时可以用某种概率分布表示，需要做的指示计算表示的参数。,贝叶斯网络（计算续）,简单的联合概率可以直接从网络关系上得到如：P(X, Y) = P(X)P(Y|X)又如：P(X, Y, Z) = P(X)P(Y)P(Z|X, Y),贝叶斯网络（例）,条件概率（CPT）表为：P(S) = .04P(C) = 0.3(E|S, C) = 0.9P(E|S, C) = 0.3P(E|S, C) = 0.5 贝叶斯网络实例图P(E|S, C) = 0.1 。,贝叶斯网络（例续）,上图例中的联合概率密度为由图可知：E与L在S条件下独立，所以 P(E|S,C,L) P(E|S,C) L与C在S, E条件下独立，所以 P(L|S,C)= P(L|S) C与S在E条件下独立，所以 P(C|S)=P(C),贝叶斯网络（例续）,以上三条等式的正确性，可以从贝叶斯网的条件独立属性：每个变量与它在图中的非继承节点在概率上是独立的推出。同样，从后面给出的D分离的定义的特性中也可以得到相同的结论。简化后的联合概率密度为， 显然，简化后的公式比原始的数学公式更加简单明了，计算复杂度低很多。如果原贝叶斯网中的条件独立语义数量较多，这种减少更加明显。,贝叶斯网络（独立）,独立P(X, Y) = P(X)P(Y)P(X|Y) = P(X)P(Y|X) = P(Y)独立时求解 可以直接在网络图上求,贝叶斯网络（条件独立）,对于X, Y, E: X与Y在给定E的条件下独立P(X|Y,E) = P(X|E)P(Y|X,E) = P(Y|E)多个变量组：d分离（d-separate） P(X1,X2,Xn|Y1,Y2,Ym,E1,E2,Ep) =P(X1,X2,Xn|E1,E2,Ep) 如果一组节点X在给定E的条件下，从Xi到Yj的每一条通路都Ek d分离，则称X独立于另一组节点Y (节点组E d分离X与Y),贝叶斯网络（D分离）,图中有三个节点S，L，EL（结果）影响S（起因），S影响E（另一个结果）。如果给定原因S后，L并不能告诉我们有关E的更多事情。即对于S，L和E是相对独立的，那么在计算S和L的关系时就不用过多地考虑E，将会大大减少计算复杂度。称S能D分离L和E。D分离是一种寻找条件独立的有效方法。,贝叶斯网络（ D分离-串行连接）,Linear 串行连接中，事件X通过事件Z影响事件Y，反之事件Y也是通过事件Z影响事件X。但是，如果原因证据Z是给定的，X并不能给Y更多的东西，或者说，从X那里得到更多的信息。此时称，如果Z是已知的，那么通道就被阻塞，X和Y就是独立的了。则称X和Y是被Z节点D分离的。,贝叶斯网络（ D分离-分叉连接）,Diverging如果，父节点Z是已知的，没有更多的信息能够通过Z影响到所有子节点。同理，父节点Z是已知时，子节点X, , N是相互独立的。称子节点X, , N是被Z节点D分离的。,贝叶斯网络（ D分离-汇集连接）,汇集(Converging)略有不同如果不从父节点得到推断，子节点Z就一无所知，那么，父节点是相互独立的，它们之间没有相互影响。如果，某事件影响了Z，那么，各个父节点就不是相互独立的了。该事件可以直接影响Z，也可以通过它的后代节点影响Z。这种现象称作条件依存。总之，如果子节点有了变化，或子节点的后代节点发生变化，信息是可以通过汇集连接传播的。,贝叶斯网络（ D分离-条件依存）,事件e直接影响节点Z 事件e影响节点Z的后代节点,贝叶斯网络（ D分离(例1)）,贝叶斯网络（ D分离(例2)）,贝叶斯网络（ D分离(例3)）,贝叶斯网络（ D分离(例4）,Radio and Ignition, given Battery? YesRadio and Start, given Ignition? YesGas and Radio, given Battery? YesGas and Radio, given Start? NoGas and Battery, given Moves? No,贝叶斯网络（推理）,建立贝叶斯网络的目的有了网络。可以提出问题： P(问题|证据)， 如：P(肺癌|吸烟）进行概率推理与谓词逻辑有相似之处 。如：患病（吸烟，肺癌）在某些场合下有有效的推理方法。有一些工具包。,贝叶斯网络（推理）,一般情况下是很困难的，原因不是所有的CPT表都能够得到网络结构大且复杂NP-hard推理我们要做的是，将问题正确的表示为合理的网络形式，选用适合的算法。,贝叶斯网络（推理续）,贝叶斯网络通常使用因果或诊断规则与推理因果规则：X 导致 Y 的可能性诊断规则 ：Y 是 X 的证据的可能性因果推理：给定导致问题Q的原因 C, 计算 P(Q|C)诊断推理：给定问题Q的证据 E, 计算 P(Q|E),贝叶斯网络（推理续）,推理需求：P(X|Y)诊断推理是从效果到起因 证据是一些征兆：X是起因， Y是征兆因果推理是从起因到效果 证据是一些起因： X是征兆， Y是起因解释历史 X和Y是起因，Z是两个起因的征兆。这时可以用一个起因Y解释另一个起因X。,贝叶斯网络（推理例）,下雨、草湿、洒水,贝叶斯网络（推理例续）,条件：下雨(Raining)草湿出现虫子(Worm) 求：P(Raining|Worm Sighting),P(Y|X),下雨,草湿,Query : P(X|Z),P(X),出现虫子,P(Z|Y),贝叶斯网络（因果推理例）,给定患者是一个吸烟者（S），计算他患肺气肿（E）的概率P(E|S)。S称作推理的证据，E叫询问结点。 首先，E的另一个父结点（C），P(E|S)=P(E,C|S)+P(E,C|S);右边的第一项 ，P(E,C|S)P(E,C,S)/P(S)P(E|C,S)*P(C,S)/P(S)P(E|C,S)*P(C|S）同理可得公式的右边的第二