人工智能导论-第四章02-59

第四章非经典推理4.1概述4.2不确定性推理4.3非单调推理4.4概率方法4.5主观贝叶斯方法4.6贝叶斯网络4.7可信度方法4.8证据理论2022/10/13人工智能导论-刘珊1基本框架架2020-02-11人工智能能导论-刘珊2贝叶斯网络全联合概概率分布布贝叶斯网网络的定定义独立和条条件独立立贝叶斯网网络的构构造贝叶斯网络的应用精确推理理近似推理理2020-02-11人工智能能导论-刘珊34.6贝叶斯网网络全联合概概率分布布定义设X={X1,X2,…,,Xn}为任何随随机变量量集，其其全联合合概率分分布是指指当对每每个变量量取特定定值时xi（i=1,2,…,n）时的合合取概率率，即P(X1=x1∧X2=x2∧…∧Xn=xn)，其简化表示示形式为为P(x1,x2,…,xn)。重复使用用乘法法则2020-02-11人工智能能导论-刘珊4得到如下下全联合合概率分分布表示示4.6贝叶斯网网络贝叶斯网网络基本概念念一系列变变量的联联合概率率分布的的图形表示一个表示示变量之之间的相相互依赖赖关系的的数据结构构定义是一个有有向无环环图随机变量量集X={X1,X2,…,,Xn}组成网络节点点，变量量可离散散或连续续连接节点点对的有有向边组组成边集集合每节点Xi都有一个个条件概概率分布布表：P(Xi|par(Xi))，量化其其父节点点对该节节点的影响2020-02-11人工智能能导论-刘珊54.6贝叶斯网网络示例例1、假设学生在碰碰见难题题和遇到到干扰时时会产生生焦虑，，而焦虑虑又可导导致思维维迟缓和和情绪波波动。请请用贝叶叶斯网络络描述这这一问题题。解：在该该贝叶斯斯网络中中，大写写英文字字母A、D、I、C和E分别表示示节点““产生焦焦虑”、“碰见见难题””、“遇遇到干扰扰”、““认知迟迟缓”和和“情绪绪波动””，并将将各节点点的条件件概率表表置于相相应节点点的右侧侧。所有随机机变量取取布尔变变量，因因此可以以分别用用小写英英文字母母a、d、i、c和e来表示布布尔变量量A、D、I、C和E取逻辑值值为“True”，用﹁a、﹁d、﹁i、﹁c和﹁e来表示布布尔变量量A、D、I、C和E取逻辑值值为“False”。2020-02-11人工智能能导论-刘珊64.6贝叶斯网网络示例右图贝叶叶斯网络中每每个节点点的概率率表就是是该节点点与其父父节点之之间的一一个局部部条件概概率分布。由于节点点D和I无父节点点，故它它们的条条件概率率表由其其先验概概率来填填充2020-02-11人工智能能导论-刘珊7碰见难题产生焦虑遇到干扰思维迟缓情绪波动ADIECAP(C)T0.8AP(E)T0.9

P(D)0.15P(I)0.05DIP(A)TT0.8TF0.4FT0.5FF0.14.6贝叶斯网网络联合概率率分布表示贝叶斯网网络的联联合概率率分布表示用par(Xi)表示Xi的所有父父节点的的相应取值，P(Xi|par(Xi))是节点Xi的一个条条件概率率分布函函数，则则对X的所有节节点，有如下联合概概率分布布：2020-02-11人工智能能导论-刘珊8局部化特特征每个节点点只受到到整个节节点集中中少数别别的节点点的直接接影响，，而不受受这些节节点外的的其它节节点的直直接影响。贝叶斯网网络的语语义4.6贝叶斯网网络独立和条条件独立立Weather和其它3个变量相相互独立。给定Cavity后，Toothache和Catch条件独立立2020-02-11人工智能能导论-刘珊9WeatherCavityCatchToothache贝叶斯网网络能实实现简化化计算的的最根本本基础------条件独立立性。两个判别准准则1）给定父节点，，一个节节点与非非其后代代的节点点之间是是条件独独立的。2）给定一个节点点，该节节点与其其父节点点、子节节点和子子节点的的父节点点一起构构成了一一个马尔科夫夫覆盖，则该节节点与马马尔科夫夫覆盖以以外的所所有节点点之间都都是条件件独立的的。4.6贝叶斯网网络条件独立立2020-02-11人工智能能导论-刘珊10U1UmXZ1jZnjY1Yn【说明】：给定节点点X的父节点点U1...Um，节点X与它的非非后代节节点（即即Zij）是条件件独立的的。4.6贝叶斯网网络……条件独立立2020-02-11人工智能能导论-刘珊11【说明】：给定马尔可夫夫覆盖（两圆圈圈之间的的区域）），节点点X和马尔可夫夫覆盖中所有其它它节点都都是条件件独立的的。U1UmXZ1jZnjY1Yn4.6贝叶斯网网络贝叶斯网网络的构构造构造过程(1)首先建立不依依赖于其其它节点点的根节节点，并并且根节节点可以以不止一一个。(2)加入受根节点点影响的的节点，，并将这这些节点点作为根根节点的的子节点点。此时时，根节节点已成成为父节节点。(3)进一步建立依赖赖于已建建节点的的子节点点。重复复这一过过程直到到叶节点点为止。。(4)对每个根根节点，，给出其其先验概概率；对对每个中中间节点点和叶节节点，给给出其条条件概率率表。主要原则则忽略过于于微弱的的依赖关关系利用变量量间的因因果关系系2020-02-11人工智能能导论-刘珊124.6贝叶斯网网络贝叶斯网网络的简简单应用用例2、对例1所示的贝叶叶斯网络络，若假设某学学生已经经产生了焦焦虑情绪绪，但实实际上并并未碰见见难题，，也未遇遇到干扰扰，请计计算思维维迟缓和和情绪波波动的概概率。解：令相相应变量量的取值值分别为为：a,﹁d,﹁﹁i,c,e，P(c∧∧e∧a∧﹁d∧﹁i)=P(c|a)P(e||a)P((a||﹁d∧∧﹁i))P(﹁﹁d)P(﹁i)=0.8×0..9×0.1××0.85×0.95=0.05814即所求的的概率为为0.058142020-02-11人工智能能导论-刘珊134.6贝叶斯网网络贝叶斯网网络推理理概念在给定一组组证据变变量观察察值的情情况下，，利用贝贝叶斯网网络计算算一组查查询变量量的后验验概率分布。变量分类类查询变量X证据变量量集E={E1,E2,,…,,En}观察到的特定定事件s非证据变量集Y={y1,,y2,……,ym}全部变量的集集合V={x}EY其推理就是是要查询询后验概概率P(X||s)。2020-02-11人工智能能导论-刘珊144.6贝叶斯网网络贝叶斯网网络推理理步骤首先确定定各相邻邻节点之之间的初初始条件件概率分分布；然后对各证据据节点取取值；接着选择适当当推理算算法对各各节点的的条件概概率分布布进行更更新；最终得到推理理结果。分类精确推理：一一种可以精精确地计计算查询询变量的的后验概概率的推理方方法，适适用于单单连通贝贝叶斯网网络。近似推理理：在不影响推推理正确确性的前前提下，，通过适适当降低低推理精精确度来来提高推推理效率率的一类类方法。2020-02-11人工智能能导论-刘珊154.6贝叶斯网网络贝叶斯网网络精确确推理主要方法法基于枚举举的算法基于变量消元元的算法基于团树传播播的算法等基于枚举举的算法利用全联合概概率分布布去推断断查询变变量的后后验概率率2020-02-11人工智能能导论-刘珊164.6贝叶斯网网络示例例3、以例1所示的贝叶叶斯网络络为例，，假设目目前观察察到的一一个事件件s={{c,e}，求在该该事件的的前提下下碰见难难题的概概率P(D|c,e))是多少？？解：按照照精确推推理算法法，该询询问可表表示为：：2020-02-11人工智能能导论-刘珊17先对D的不同取取值d和﹁d分别进行行处理，当D取值d时，有4.6贝叶斯网网络示例2020-02-11人工智能能导论-刘珊18当D取值﹁d时，有取α=1//(0..0519+0.0901))=1//0.142。因此有P(D||c,e)=α(0..0519,0.0901)=((0..3655,0.6345)即在思维维迟缓和和情绪波波动都发发生时，碰见难难题的概率是是P(d||c,e)=0.3655,没有碰见见难题的概率是是P(﹁d|c,e)==0..63454.6贝叶斯网网络贝叶斯网络近似似推理马尔可夫夫链蒙特特卡罗（（MCMC）算法是是目前使使用较广广的一类贝叶斯网网络推理理方法。它通过对前前一个事件状状态作随机改改变来生生成下一一个问题题状态，，通过对对某个隐隐变量进进行随机机采样来来实现对对随机变变量的改改变。MCMC方法可视视为：在在状态空空间中的随机走动，但是证据据变量的的值固定定不变。2020-02-11人工智能能导论-刘珊194.6贝叶斯网网络示例例4、学习情情绪会影影响学习习效果。。假设有有一个知知识点，，考虑学学生在愉愉快学习习状态下下对该知知识点的的识记、、理解、、运用的的情况，，得到了了如右图所所示的贝叶斯斯网络。如如果目前前观察到到一个学学生不但但记住了了该知识识，并且且还可以以运用该该知识，，询问这这位学生生是否理理解了该该知识。。2020-02-11人工智能能导论-刘珊20愉快学习知识识记知识理解知识运用EUMAEP(M)T0.9F0.4P(E)0.75MUP(A)TT0.95TF0.5FT0.65FF0.1EP(U)T0.85F0.34.6贝叶斯网网络示例解：要求求的是P(U|m,a)。应用MCMC算法的推推理步骤骤如下：：(1)将“知识识识记””节点M和“知识识运用””节点A作为证据据变量，，并保持持它们的的观察值值不变；；(2)隐变量“愉愉快学习习”节点点E和查询变变量“知知识理解解”节点U进行随机初始始化。假假设，取取值分别别为e和﹁u，问题的的初始状状态为{e,,m,,﹁u,,a}}；(3)反复执行行如下步骤，①对隐变量量E进行采样样，由于于E的马尔科科夫覆盖盖（其父父节点、、子节点点和子节节点的父父节点））仅包含含节点M和U，可以按按照变量量M和U的当前值值进行采采样，若若采样得得到﹁e，则生成成下一状状态{﹁e,,m,,﹁u,,a}}；②对查查询变量量U进行采样样，由于于U的马尔科科夫覆盖盖包含节节点E、M和A，可以按按照变量量E、M和A的当前值值进行采采样，若若采样得得到u，则生成成下一状状态{﹁e,,m,,u,,a}。(4)重复以上上步骤直直到所要要求的访访问次数数N。若为true和false的次数分分别为n1,、n2，则查询询解为Normalize((<n1,n2>))=<<n1//N,n2/N>2020-02-11人工智能能导论-刘珊214.6贝叶斯网网络示例解：在在上述采采样过程程中，每每次采样样都需要要两步。。以对隐隐变量E的采样为为例，每每次采样样步骤如如下：1、先依据该隐隐变量的的马尔科科夫覆盖盖所包含含的变量量的当前前值，计计算该状状态转移移概率p；2、确定状态是否否需要改改变。其其基本方方法是，，生成一一个随机机数r∈[0,1]]，将其与与第一步步得到的的转移概概率p进行比较较，若r<p，则E取﹁e，转移到到下一状状态；否否则，还还处在原原状态不不变。在初始状态态下，对变量E进行采样样，第一一步计算P(E||m,﹁u)，以此判判断是否否转移到下一状状态{﹁e,,m,,﹁u,,a}。P(e|m,﹁﹁u))=P(e,m,﹁u)//P(m,﹁u)=P(e))P(m|e))P(﹁﹁u|e)//[[P(e))P(m|e))P(﹁﹁u|e)+P((﹁e))P(m|﹁﹁e))P(﹁﹁u|﹁﹁e))]=(0.75×0..9×0.3))//[0.75×0..9×0.3++0.25×0..4×0.3]]=0.2025//0.2325=0..8710第二步，，假设产产生的随随机数r=0..46，有0.46<0..871，则E取﹁e，转移到到下一状状态{﹁e,,m,,﹁u,,a}}2020-02-11人工智能能导论-刘珊224.6贝叶斯网网络第四章非非经经典推理理4.1概述4.2不确定性性推理4.3非单调推推理4.4概率方法法4.5主观贝叶斯方法4.6贝叶斯网网络4.7可信度方法4.8证据理论论2020-02-11人工智能能导论-刘珊23基本概念念可信度：：根据经经验对一一个事物物或现象象为真的的相信程程度。C－F模型：基基于可信信度表示示的不确确定性推推理的基基本方法。主要内容容1、C-F模型中规规则的不不确定性性表示2、C-F模型中证据的的不确定定性表示示3、C-F模型中组合证证据不确确定性的的计算4、C-F模型中不确定定性的更更新5、C-F模型中结论的的不确定定性合成成6、带加权权因子的的可信度度推理2020-02-11人工智能能导论-刘珊244.7可信度方方法1、规则不不确定性性的表示产生式规规则表示示IFETHENH((CF(H,E)))CF(H,E))：可信度度因子，，反映前提条件件与结论论的联系系强度。。CF(H，E)的取值范围：[-1,1]]。若由于相相应证据据的出现现增加结结论H为真的可可信度，，则CF(H，E)>0，证据的的出现越越是支持持H为真，就就使CF(H，E)的值越大。。反之，CF(H，E)<0，证据的的出现越越是支持持H为假，CF(H，E)的值就越小小。若证据的出出现与否否与H无关，则则CF(H，E)=02020-02-11人工智能能导论-刘珊254.7可信度方方法2、证据不确定性性的表示证据E的可信度度取值范范围：[-1，1]。对于初始始证据，，若所有有观察S能肯定它它为真，，则CF(E)=1；若肯定它为为假，则则CF(E)==–1。若以某种种程度为为真，则则0<CF((E)<<1。若以某种种程度为为假，则则－1<CF((E)<<0。若未获得得任何相相关的观观察，则则CF(E)==0。静态强度CF(H，E)：知识的强强度，即即当所对应应的证据据E为真时对H的影响程程度。动态强度CF(E)：证据E当前的不不确定性性程度2020-02-11人工智能能导论-刘珊264.7可信度方方法3、组合证据不确确定性的的算法组合证据据：多个个单一证证据的合取E=E1ANDE2AND…ANDEn则CF(E)=min{CF(E1),CF(E1),…,CF(En)}组合证据据：多个个单一证证据的析取E=E1ORE2OR…OREn则CF(E)=max{{CF((E1),CF(E1),……,CF(En)}2020-02-11人工智能能导论-刘珊274.7可信度方方法4、不确定定性的传递算法C-F模型中的的不确定定性推理理：从不不确定的的初始证证据出发发，通过过运用相相关的不不确定性性知识，，最终推推出结论论并求出出结论的的可信度度值。结论H的可信度度由下式式计算:2020-02-11人工智能能导论-刘珊28CF(E)<0时，CF(H)=0;CF(E)=1时，CF(H)=CF(H,E))4.7可信度方方法5、结论不确定性性的合成成算法设知识：：IFE1THENH((CF(H,,E1))IFE2THENH((CF(H,,E2))（1）分别对对每一条条知识求求出CF(H)：CF1(H)==CF((H,E1)×max{{0,CF((E1)}CF2(H)=CF(H,,E2)×max{{0,CF((E2)}(2)用如下公公式求E1与E2对H的综合可可信度2020-02-11人工智能能导论-刘珊294.7可信度方方法6、带加权因子子的可信信度推理理当知识的的前提条条件为多多个子条条件组合，且且这些子条件对结论的重重要程度不同同时，在前提条条件中加加入加权权因子，，以说明明每个前前提的重重要程度度。知识的不不确定性性表示ifE1(w1)andE2(w2)and……andEn(wn)thenHCF(H,E))其中w1,w2,…,wn为加权因因子，一一般满足足归一条条件即w1+w2+…+wn=12020-02-11人工智能能导论-刘珊304.7可信度方方法带加权因因子的可可信度推推理组合证据据不确定定性的计算若E=E1(w1)andE2(w2)and……andEn(wn)则E的可信度度因子可可以按如如下方式式计算CF(E)=∑∑wi*CF((Ei)不确定性性的更新直观的方法为：CF(H)=CF(H，E)*CF(E)2020-02-11人工智能能导论-刘珊314.7可信度方方法示例例1、已知规规则r1:ifE1(0.6)andE2(0.4)thenE5(0.8))r2:ifE3(0.5)andE4(0.3)andE5(0.2)thenH(0.9))以及CF(E1)=0..9,CF((E2)=0..8,CF((E3)=0..7,CF((E4)=0..6求CF(H)？2020-02-11人工智能能导论-刘珊324.7可信度方方法示例解：CF(E5)=CF(E5,E)**CF((E)==0.8*0..86==0.69CF(E3(0.5)andE4(0.3)andE5(0.2))==0.67CF(H)=0..9*0.67=0..6032020-02-11人工智能能导论-刘珊334.7可信度方方法第四章非非经经典推理理4.1概述4.2不确定性性推理4.3非单调推推理4.4概率方法法4.5主观贝叶斯方法4.6贝叶斯网网络4.7可信度方法4.8证据理论论2020-02-11人工智能能导论-刘珊34证据理论论又称D－S理论在证据理理论的基基础上已已经发展展了多种种不确定定性推理模型型主要内容容概率分配配函数信任函数似然函数数信任函数与似似然函数数的关系系概率分配函数数的正交交和（证证据的组合）基于证据据理论的的推理2020-02-11人工智能能导论-刘珊354.8证据理论论基本概念念证据理论论假设有有一个不不变的两两两相斥斥的完备备元素集集合U，如右图图所示，，其中2020-02-11人工智能能导论-刘珊36证据理论论说明图图4.8证据理论论例如,U={三轮车，，汽车，，火车}U={赤，橙，，黄，绿绿，青，，蓝，紫紫}U={马，牛，，羊，鸡鸡，狗，，兔}基本概念念证据理论论用集合合表示命命题。设D是变量x所有可能能取值的的集合，，且D中的元素素是互斥斥的，在在任一时时刻x都取D中的某一一个元素素为值，，称D为x的样本空空间。在证据理理论中，，D的任何一一个子集集A都对应于于一个关关于x的命题，，称该命命题为““x的值在A中”。设x：所看到到的颜色色，D={红，黄，，蓝}，则A={红}：“x是红色””；A={红，蓝}：“x或者是红红色，或或者是蓝蓝色”。。为了描述述和处理理不确定定性，引引入了概概率分配配函数、、信任函函数及似似然函数数等概念念。2020-02-11人工智能能导论-刘珊374.8证据理论论概率分配配函数设D为样本空空间，领领域内的的命题都都用D的子集表表示。定义：设函数M：,且满足2020-02-11人工智能能导论-刘珊384.8证据理论论则称M是上上的概概率分配配函数，，M(A)称为A的基本概概率函数数。对样本空空间D的任一子子集都分分配一个个概率值值。概率分配配函数2020-02-11人工智能能导论-刘珊39几点说明明：（1）样本空空间D中有n个元素，，则D中子集的的个数为2n个。2D：D的所有子子集。（2）概率分分配函数数：把D的任意一一个子集集A都映射为为[0,1]上的一个个数M（A）。AD，AD时，M（A）：对相相应命题题A的精确信信任度。。（3）概率分分配函数数与概率率不同。。例如，设设A={红}，M（A）=0.3：命题“x是红色”的信任度度是0.3。设D={红，黄，，蓝}M（{红}）=0.3，M（{黄}）=0，M（{蓝}）=0.1，M（{红，黄}）=0.2，M（{红，蓝}）=0.2，M（{黄，蓝}）=0.1，M（{红，黄，，蓝}）=0.1，M（Φ）=0但：M（{红}）+M（{黄}）+M（{蓝}）=0.4设D={红，黄，蓝}则其子集个数23＝8，具体为：A={红}，

A={黄}，

A={蓝}，

A={红，黄}，A={红，蓝}，

A={黄，蓝}，A={红，黄，蓝}，A={}4.8证据理论论信任函数数

2020-02-11人工智能能导论-刘珊40

设D={红，黄，蓝}M（{红}）=0.3，

M（{黄}）=0，M（{红，黄}）=0.2,由信任函函数及概概率分配配函数的的定义推推出：4.8证据理论论似然函数数似然函数数定义为为Pl：2D[0,,1]且pl(A)==1-Bel(A))，AD2020-02-11人工智能能导论-刘珊41设D={红，黄，，蓝}M({红})=0.3，M({黄})=0，M({红，黄})=0.2，Bel({红,黄})=M({红})+M({黄})+M({红,黄})=0.5Pl({蓝})=1-Bel({蓝})=1--Bel({红,黄})=1-0..5=0.54.8证据理论论信任函数数与似然然函数的的关系Pl(A)Bel(A)Bel(A)：对A为真的信信任程度度。Pl(A)：对A为非假的的信任程程度。A(Bel(A),Pl(A))：对A信任程度度的下限限与上限限。例如{红}：[0.3,0..9]表示{红}的精确信信任度为为0.3，不可驳驳斥部分分为0.9典型值A[0,,1]：对A一无所知知A[0,,0]：说明A为假A[1,,1]：说明A为真2020-02-11人工智能能导论-刘珊424.8证据理论论概率分配配函数的的正交和和2020-02-11人工智能能导论-刘珊43如果K0，则正交和和M也是一个个概率分配配函数；如果K=0，则不存在在正交和和M，即没有有可能存存在概率率函数，，称M1与M2矛盾。4.8证据理论论设M1和M2是两个概概率分配配函数，，则其正正交和定定义为概率分配配函数的的正交和和设M1,M2,…,Mn是n个概率分配配函数，则其正交和和M=M1M2…Mn为M()=0,,2020-02-11人工智能能导论-刘珊44其中：4.8证据理论论实例设D={黑，白}，且2020-02-11人工智能能导论-刘珊45则，4.8证据理论论实例同理可得得：2020-02-11人工智能能导论-刘珊46组合后得得到的概概率分配配函数：：4.8证据理论论一类特殊殊的概率率分配函函数设D={s1,s2,…,sn}，M为定义在2D上的概率分分配函数数，且M满足：M({si})≥0,对任给si∊D∑i=1nM({si})≤1M(D))=1-∑i=1nM({si})当A⊆D，且A的元素多多于1个或没有有元素，M(A)=0。2020-02-11人工智能能导论-刘珊474.8证据理论论一类特殊殊的概率率分配函函数对这类概率分配函数数，其信任任函数和似似然函数数的性质为：：Bel(A)=∑si∊AM({si})Bel(D)=∑si∊DM({si})++M(D)=1Pl(A)=1-Bel(¬A)=1-∑si∊¬AM({si})==1-∑si∊DM({si})+∑si∊AM({si})==M((D)+Bel(A)Pl(D)=1-Bel(¬D)=12020-02-11人工智能能导论-刘珊484.8证据理论论类概率函函数设D为有限域，，对任何何命题A⊆D，其类概率函数数定义为为f(A))=Bel(A)++||A|/||D|[Pl(A)--Bel(A)]]其中|A|和|D|表示A和D中的元素个个数。类概率函函数的性性质∑si∊Df({si})=1对任何A⊆D，有Bel(A)≤f(A)≤≤Pl(A)对任何A⊆D，有f(¬A)=1-f((A)则，f(Φ)=0；f(D)=1；对任何A⊆D，0≤f(A))≤12020-02-11人工智能能导论-刘珊494.8证据理论论规则不确确定性的表示D-S理论中，，不确定性性规则的的表示形式式为ifEthenH=={h1,h2,…,hn}CF={{c1,c2,…,cn}其中：E为前提条条件，可以是简单条条件，也也可以是复合条条件；H是结论，用样本空间间的子集集表示，，h1,h2,…,hn是该子集集的元素素；CF是可信度度因子，，用集合合的方式式表示。。c1,c2,…,cn用来表示示h1,h2,…,hn的可信度度。2020-02-11人工智能能导论-刘珊504.8证据理论论证据不确确定性的的表示证据E的不确定定性由证据的类类概率函函数给出：CER((E)=f(E)2020-02-11人工智能能导论-刘珊514