贝叶斯网络初步

贝叶斯网络初步内容提纲何谓贝叶斯网络？贝叶斯网络的语义条件分布的有效表达贝叶斯网络中的精确推理贝叶斯网络中的近似推理课后习题、编程实现及研读论文7.1何谓贝叶斯网络？A.贝叶斯网络的由来B.贝叶斯网络的定义C.贝叶斯网络的别名D.独立和条件独立E.贝叶斯网络示例“Aboveallelse,guardyourheart,foritisthewellspringoflife.”fromProverbs4:23NIVA.贝叶斯网络的由来全联合概率计算复杂性十分巨大朴素贝叶斯太过简单现实需要一种自然、有效的方式来捕捉和推理——不确定性知识变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目B.贝叶斯网络的定义是一个有向无环图(DAG)随机变量集组成网络节点，变量可离散或连续一个连接节点对的有向边或箭头集合每节点Xi都有一个条件概率分布表：P(Xi|Parents(Xi))，量化其父节点对该节点的影响C.贝叶斯网络的别名信念网(BeliefNetwork)概率网络(ProbabilityNetwork)因果网络(CausalNetwork)知识图(KnowledgeMap)图模型(GraphicalModel)或概率图模型(PGM)决策网络(DecisionNetwork)影响图(InfluenceDiagram)D.独立和条件独立WeatherCavityCatchToothacheWeather和其它3个变量相互独立给定Cavity后，Toothache和Catch条件独立E.贝叶斯网络示例BurglaryEarthquakeMaryCallsJohnCallsAlarmBEP(A)tttfftff0.950.940.290.001AP(J)tf0.900.05AP(M)tf0.700.01P(B)0.001P(E)0.0027.2贝叶斯网络的语义贝叶斯网络的两种含义对联合概率分布的表示—构造网络对条件依赖性语句集合的编码—设计推理过程贝叶斯网络的语义P(x1,...,xn)=P(x1|parent(x1))...P(xn|parent(xn))贝叶斯网络的语义公式计算示例：试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时John和Mary都给你打电话的概率。解：P(j,m,a,~b,~e)=P(j|a)P(m|a)P(a|~b,~e)P(~b)P(~e)=0.9×0.7×0.001×0.999×0.998=0.00062=0.062%贝叶斯网络的特性：作为对域的一种完备而无冗余的表示，贝叶斯网络比全联合概率分布紧凑得多BN的紧凑性是局部结构化(Locallystructured,也称稀疏,Sparse)系统一个非常普遍特性的实例BN中每个节点只与数量有限的其它节点发生直接的相互作用假设节点数n=30,每节点有5个父节点，则BN需30x25=960个数据，而全联合概率分布需要230=10亿个！贝叶斯网络的构造原则：首先，添加“根本原因”节点然后，加入受它们直接影响的变量依次类推，直到叶节点，即对其它变量没有直接因果影响的节点两节点间的有向边的取舍原则：更高精度概率的重要性与指定额外信息的代价的折衷“因果模型”比“诊断模型”需要更少的数据，且这些数据也更容易得到贝叶斯网络中的条件独立关系：给定父节点，一个节点与它的非后代节点是条件独立的给定一个节点的父节点、子节点以及子节点的父节点——马尔可夫覆盖(Markovblanket)，这个节点和网络中的所有其它节点是条件独立的“ButhisdelightisinthelawoftheLORD,andonhislawhemeditatesdayandnight.”FromPsalms1:2NIVU1UmXZ1jZnjY1Yn【说明】：给定节点X的父节点U1...Um，节点X与它的非后代节点（即Zij）是条件独立的。U1UmXZ1jZnjY1Yn【说明】：给定马尔可夫覆盖（两圆圈之间的区域），节点X和网络中所有其它节点都是条件独立的。7.3条件概率分布的有效表达ColdFluMalariaP(Fever)P(~Fever)FFFFFTFTFFTTTFFTFTTTFTTT0.00.90.80.980.40.940.880.9881.00.10.20.02=0.2X0.10.60.06=0.6X0.10.12=0.6X0.20.012=0.6X0.2X0.1已知：P(~fever|cold,~flu,~malaria)=0.6P(~fever|~cold,flu,~malaria)=0.2P(~fever|~cold,~flu,malaria)=0.1，可利用“噪声或”（Noisy-OR）关系得到下表：包含连续变量的贝叶斯网络－HybridBNSubsidyHarvestBuysCostSHP(C)thfh高斯分布高斯分布CP(B)cS型函数P(S)xP(H)高斯分布离散随机变量：Subsidy,Buys;连续随机变量：Harvest,Cost.线性高斯分布：P(c|h,subsidy)=N(ath+bt,t2)(c)=1/(t21/2)e–1/2{[c-(ath+bt)]/t]}P(c|h,~subsidy)=N(afh+bf,f2)(c)=1/(f21/2)e–1/2{[c-(afh+bf)]/t]}S型函数(Sigmoidfunction)p(buys|Cost=c)=1/{1+exp[-2(-u+)/]}7.4贝叶斯网络中的精确推理变量分类：证据变量集E—特定事件e，查询变量X非证据变量集—Y隐变量（Hiddenvariable）全部变量的集合U={x}EY（1）通过枚举进行推理BurglaryEarthquakeMaryCallsJohnCallsAlarmBEP(A)tttfftff0.950.940.290.001AP(J)tf0.900.05AP(M)tf0.700.01P(B)0.001P(E)0.002已知，一个事件e={JohnCalls=true,andMaryCalls=true}，试问出现盗贼的概率是多少？解：P(X|e)=P(X,e)=yP(X,e,y)而P(X,e,y)可写成条件概率乘积的形式。因此，在贝叶斯网络中可通过计算条件概率的乘积并求和来回答查询。P(Burgary|JohnCalls=true,MaryCalls=true)简写为：P(B|j,m)=P(B,j,m)=eaP(B,e,a,j,m)=eaP(b)P(e)P(a|b,e)P(j|a)P(m|a)=P(b)eP(e)aP(a|b,e)P(j|a)P(m|a)+++P(b)0.01P(e)0.002P(~e)0.998P(a|b,e)0.95P(~a|b,e)0.05P(a|b,~e)0.94P(~a|b,~e)0.06P(m|a)0.70P(j|a)0.90P(j|~a)0.05P(j|a)0.90P(j|~a)0.05P(m|a)0.70P(m|~a)0.01P(m|~a)0.01P(b|j,m)的自顶向下的计算过程P(B|j,m)=P(B,j,m)=eaP(B,e,a,j,m)=eaP(b)P(e)P(a|b,e)P(j|a)P(m|a)=P(b)eP(e)aP(a|b,e)P(j|a)P(m|a)=0.001{[0.002(0.950.90.7+0.050.050.01)]+[0.998(0.940.90.7+0.060.050.01)]}=0.00059224+++P(~b)0.999P(e)0.002P(~e)0.998P(a|~b,e)0.29P(~a|~b,e)0.71P(a|~b,~e)0.001P(~a|~b,~e)0.999P(m|a)0.70P(j|a)0.90P(j|~a)0.05P(j|a)0.90P(j|~a)0.05P(m|a)0.70P(m|~a)0.01P(m|~a)0.01P(～b|j,m)的自顶向下的计算过程P(~B|j,m)=P(~B,j,m)=eaP(~B,e,a,j,m)=eaP(~b)P(e)P(a|~b,e)P(j|a)P(m|a)=P(~b)eP(e)aP(a|~b,e)P(j|a)P(m|a)=0.999{[0.002(0.290.90.7+0.710.050.01)]+[0.998(0.0010.90.7+0.9990.050.01)]}=0.0014919因此，P(B|j,m)=0.00059224,0.00149190.284,0.716即在John和Mary都打电话的条件下，出现盗贼的概率约为28%。Example:Tree-StructuredBayesianNetworkDABCFEGp(a,b,c,d,e,f,g)ismodeledasp(a|b)p(c|b)p(f|e)p(g|e)p(b|d)p(e|d)p(d)ExampleDABcFEgSaywewanttocomputep(a|c,g)ExampleDABcFEgDirectcalculation:p(a|c,g)=Sbdefp(a,b,d,e,f|c,g)ComplexityofthesumisO(m4)ExampleDABcFEgReordering:Sdp(a|b)Sdp(b|d,c)Sep(d|e)Sfp(e,f|g)ExampleDABcFEgReordering:Sbp(a|b)Sdp(b|d,c)Sep(d|e)Sfp(e,f|g)p(e|g)ExampleDABcFEgReordering:Sbp(a|b)Sdp(b|d,c)Sep(d|e)p(e|g)p(d|g)ExampleDABcFEgReordering:Sbp(a|b)Sdp(b|d,c)p(d|g)p(b|c,g)ExampleDABcFEgReordering:Sbp(a|b)p(b|c,g)p(a|c,g)ComplexityisO(m),comparedtoO(m4)（2）变量消元算法消除重复计算，提高枚举算法的效率保存中间结果，以备多次使用从右到左（在树结构中为自底向上）的次序计算BN的计算公式算法过程：参见《人工智能：一种现代方法》中的第14章14.4.2节（3）Clustering算法（JointTree算法）单独节点联合起来形成Cluster节点，使得BN结构成为一棵多树（Polytree）多树——单连通网络，即任何两节点间至多只有一条路径相连概率推理包含命题逻辑推理作为其特殊情况，故BN的推理是一个NP问题在多连通的BN结构中，及时每个节点的父节点个数有固定的界限，在最坏的情况下，变量消元算法仍可能具有指数级时间和空间复杂度多连通网络及其CPT：CloudyRainWetGrassSprinklerSRP(W)tttfftff0.990.900.900.00CP(S)tf0.100.50P(C)0.50CP(R)tf0.800.20等价的联合树及其CPT：CloudySpr+RainWetGrassS+RP(W)tttfftff0.990.900.900.00P(C)0.507.5贝叶斯网络的近似推理大规模多连通BN的精确推理是不可操作的，必须通过近似推理来解决。后验概率计算的主要采样方法直接采样方法马尔可夫链蒙特卡罗（MCMC）方法变分法(Variationalmethod)环传播(Loopypropagation)方法直接采样方法：直接采样算法拒绝采样(Rejectionsampling)算法似然加权(Likelihoodweighting)算法上述方法的详细步骤请参见：《人工智能：一种现代方法》第14章14.5.1节Berkeley