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

第四章非经典推理•4.1概述•4.2不确定性推理•4.3非单调推理•4.4概率方法•4.5主观贝叶斯方法•4.6贝叶斯网络•4.7可信度方法•4.8证据理论2019/8/1人工智能导论-刘珊1基本框架2019/8/1人工智能导论-刘珊2贝叶斯网络•全联合概率分布•贝叶斯网络的定义•独立和条件独立•贝叶斯网络的构造•贝叶斯网络的应用–精确推理–近似推理2019/8/1人工智能导论-刘珊34.6贝叶斯网络全联合概率分布•定义–设X={X1,X2,…,Xn}为任何随机变量集，其全联合概率分布是指当对每个变量取特定值时xi（i=1,2,…,n）时的合取概率，即P(X1=x1∧X2=x2∧…∧Xn=xn)，其简化表示形式为P(x1,x2,…,xn)。•重复使用乘法法则2019/8/1人工智能导论-刘珊4121211(,,...,)(|,,...,)nniiiiPxxxPxxxx得到如下全联合概率分布表示12121121(,,...,)(|,,...,)(,,...,)nnnnnnPxxxPxxxxPxxx4.6贝叶斯网络贝叶斯网络•基本概念–一系列变量的联合概率分布的图形表示–一个表示变量之间的相互依赖关系的数据结构•定义–是一个有向无环图–随机变量集X={X1,X2,…,Xn}组成网络节点，变量可离散或连续–连接节点对的有向边组成边集合–每节点Xi都有一个条件概率分布表：P(Xi|par(Xi))，量化其父节点对该节点的影响2019/8/1人工智能导论-刘珊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”。2019/8/1人工智能导论-刘珊64.6贝叶斯网络示例•右图贝叶斯网络中每个节点的概率表就是该节点与其父节点之间的一个局部条件概率分布。•由于节点D和I无父节点，故它们的条件概率表由其先验概率来填充2019/8/1人工智能导论-刘珊7碰见难题产生焦虑遇到干扰思维迟缓情绪波动ADIECAP(C)T0.8AP(E)T0.9P(D)0.15P(I)0.05DIP(A)TT0.8TF0.4FT0.5FF0.14.6贝叶斯网络联合概率分布表示•贝叶斯网络的联合概率分布表示–用par(Xi)表示Xi的所有父节点的相应取值，P(Xi|par(Xi))是节点Xi的一个条件概率分布函数，则对X的所有节点，有如下联合概率分布：2019/8/1人工智能导论-刘珊8121(,,...,)(|())nniiiPxxxPxparX•局部化特征•每个节点只受到整个节点集中少数别的节点的直接影响，而不受这些节点外的其它节点的直接影响。贝叶斯网络的语义4.6贝叶斯网络独立和条件独立Weather和其它3个变量相互独立。给定Cavity后，Toothache和Catch条件独立2019/8/1人工智能导论-刘珊9WeatherCavityCatchToothache贝叶斯网络能实现简化计算的最根本基础-----条件独立性。两个判别准则1）给定父节点，一个节点与非其后代的节点之间是条件独立的。2）给定一个节点，该节点与其父节点、子节点和子节点的父节点一起构成了一个马尔科夫覆盖，则该节点与马尔科夫覆盖以外的所有节点之间都是条件独立的。4.6贝叶斯网络条件独立2019/8/1人工智能导论-刘珊10U1UmXZ1jZnjY1Yn【说明】：给定节点X的父节点U1...Um，节点X与它的非后代节点（即Zij）是条件独立的。4.6贝叶斯网络……条件独立2019/8/1人工智能导论-刘珊11【说明】：给定马尔可夫覆盖（两圆圈之间的区域），节点X和马尔可夫覆盖中所有其它节点都是条件独立的。U1UmXZ1jZnjY1Yn4.6贝叶斯网络贝叶斯网络的构造•构造过程–(1)首先建立不依赖于其它节点的根节点，并且根节点可以不止一个。–(2)加入受根节点影响的节点，并将这些节点作为根节点的子节点。此时，根节点已成为父节点。–(3)进一步建立依赖于已建节点的子节点。重复这一过程直到叶节点为止。–(4)对每个根节点，给出其先验概率；对每个中间节点和叶节点，给出其条件概率表。•主要原则–忽略过于微弱的依赖关系–利用变量间的因果关系2019/8/1人工智能导论-刘珊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.058142019/8/1人工智能导论-刘珊134.6贝叶斯网络贝叶斯网络推理•概念–在给定一组证据变量观察值的情况下，利用贝叶斯网络计算一组查询变量的后验概率分布。•变量分类–查询变量X–证据变量集E={E1,E2,…,En}–观察到的特定事件s–非证据变量集Y={y1,y2,…,ym}–全部变量的集合V={x}EY•其推理就是要查询后验概率P(X|s)。2019/8/1人工智能导论-刘珊144.6贝叶斯网络贝叶斯网络推理•步骤–首先确定各相邻节点之间的初始条件概率分布；–然后对各证据节点取值；–接着选择适当推理算法对各节点的条件概率分布进行更新；–最终得到推理结果。•分类–精确推理：一种可以精确地计算查询变量的后验概率的推理方法，适用于单连通贝叶斯网络。–近似推理：在不影响推理正确性的前提下，通过适当降低推理精确度来提高推理效率的一类方法。2019/8/1人工智能导论-刘珊154.6贝叶斯网络贝叶斯网络精确推理•主要方法–基于枚举的算法–基于变量消元的算法–基于团树传播的算法等•基于枚举的算法–利用全联合概率分布去推断查询变量的后验概率2019/8/1人工智能导论-刘珊16(|)(,)(,,),YPXsPXsPXsY是归一化常数4.6贝叶斯网络示例•例3、以例1所示的贝叶斯网络为例，假设目前观察到的一个事件s={c,e}，求在该事件的前提下碰见难题的概率P(D|c,e)是多少？•解：按照精确推理算法，该询问可表示为：2019/8/1人工智能导论-刘珊17IAecAIDPecDPecDP),,,,(),,(),|(先对D的不同取值d和﹁d分别进行处理，当D取值d时，有IAecAIdPecdP),,,,(),|(4.6贝叶斯网络示例2019/8/1人工智能导论-刘珊18(|,)()()(|,)(|)(|)()[()((|,)(|)(|)(|,)(|)(|))()((|,)(|)(|)(|,)(|)(|))]0.0519IAPdcePdPIPAdIPcAPeAPdPiPadiPcaPeaPadiPcaPeaPiPadiPcaPeaPadiPcaPea当D取值﹁d时，有(|,)(,,,,)()[()((|,)(|)(|)(|,)(|)(|))()((|,)(|)(|)(|,)(|)(|))]0.0901IAPdcePdIAcePdPiPadiPcaPeaPadiPcaPeaPiPadiPcaPeaPadiPcaPea取α=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方法可视为：在状态空间中的随机走动，但是证据变量的值固定不变。2019/8/1人工智能导论-刘珊194.6贝叶斯网络示例•例4、学习情绪会影响学习效果。假设有一个知识点，考虑学生在愉快学习状态下对该知识点的识记、理解、运用的情况，得到了如右图所示的贝叶斯网络。如果目前观察到一个学生不但记住了该知识，并且还可以运用该知识，询问这位学生是否理解了该知识。2019/8/1人工智能导论-刘珊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/N2019/8/1人工智能导论-刘珊214.6贝叶斯网络示例•解：在上述采样过程中，每次采样都需要两步。以对隐变量E的采样为例，每次采样步骤如下：–1、先依据该隐变量的马尔科夫覆盖所包含的变量的当前值，计算该状态转移概率p；–2、确定状态是否需要改变。其基本方法是，生成一个随机数r∈[0,1]，将其与第一步得到的转移概率p进行比较，若rp，则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.460.871，则E取﹁e，转移到下一状态{﹁e,m,﹁u,a}2019/8/1人工智能导论-刘珊224.6贝叶斯网络第四章非经典推理•4.1概述•4.2不确定性推理•4.3非单调推理•4.4概率方法•4.5主观贝叶斯方法•4.6贝叶斯网络•4.7可信度方法•4.8证据理论2019/8/1人工智能导论-刘珊23基本概念•可信度：根据经验对一个事物或现象为真的相信程度。•C－F模型：基于可信度表示的不确定性推理的基本方法。•主要内容–1、C-F模型中规则的不确定性表示–2、C-F模型中证据的不确定性表示–3、C-F模型中组合证据不确定性的计算–4、C-F模型中不确定性的更新–5、C-F模型中结论的不确定性合成–6、带加权因子的可信度推理2019/8/1人工智能导论