贝叶斯网络的特性课件

贝叶斯网络初步

贝叶斯网络初步

内容提纲何谓贝叶斯网络？贝叶斯网络的语义条件分布的有效表达贝叶斯网络中的精确推理贝叶斯网络中的近似推理课后习题、编程实现及研读论文内容提纲何谓贝叶斯网络？7.1何谓贝叶斯网络？贝叶斯网络的由来贝叶斯网络的定义贝叶斯网络的别名独立和条件独立贝叶斯网络示例“Aboveallelse,guardyourheart,foritisthewellspringoflife.”fromProverbs4:23NIV7.1何谓贝叶斯网络？贝叶斯网络的由来“Aboveal贝叶斯网络的由来

全联合概率计算复杂性十分巨大朴素贝叶斯太过简单现实需要一种自然、有效的方式来捕捉和推理——不确定性知识变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目贝叶斯网络的由来全联合概率计算复杂性十分巨大B.贝叶斯网络的定义

是一个有向无环图(DAG)随机变量集组成网络节点，变量可离散或连续一个连接节点对的有向边或箭头集合每节点Xi都有一个条件概率分布表：P(Xi|Parents(Xi))，量化其父节点对该节点的影响B.贝叶斯网络的定义是一个有向无环图(DAG)C.贝叶斯网络的别名

信念网(BeliefNetwork)概率网络(ProbabilityNetwork)因果网络(CausalNetwork)知识图(KnowledgeMap)图模型(GraphicalModel)或概率图模型(PGM)决策网络(DecisionNetwork)影响图(InfluenceDiagram)C.贝叶斯网络的别名信念网(BeliefNetworkD.独立和条件独立WeatherCavityCatchToothacheWeather和其它3个变量相互独立给定Cavity后，Toothache和Catch条件独立D.独立和条件独立WeatherCavityCatchToE.贝叶斯网络示例BurglaryEarthquakeMaryCallsJohnCallsAlarmBEP(A)tttfftff0.950.940.290.001AP(J)tf0.900.05AP(M)tf0.700.01P(B)0.001P(E)0.002E.贝叶斯网络示例BurglaryEarthquakeMa7.2贝叶斯网络的语义贝叶斯网络的两种含义对联合概率分布的表示—构造网络对条件依赖性语句集合的编码—设计推理过程贝叶斯网络的语义P(x1,...,xn)=P(x1|parent(x1))...P(xn|parent(xn))7.2贝叶斯网络的语义贝叶斯网络的两种含义贝叶斯网络的语义公式计算示例：

试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时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:2NIV贝叶斯网络中的条件独立关系：给定父节点，一个节点与它的非后U1UmXZ1jZnjY1Yn【说明】：给定节点X的父节点U1...Um，节点X与它的非后代节点（即Zij）是条件独立的。U1UmXZ1jZnjY1Yn【说明】：U1UmXZ1jZnjY1Yn【说明】：给定马尔可夫覆盖（两圆圈之间的区域），节点X和网络中所有其它节点都是条件独立的。U1UmXZ1jZnjY1Yn【说明】：7.3条件概率分布的有效表达

ColdFluMalariaP(Fever)P(~Fever)FFF

FFT

FTFFTT

TFFTFTTTFTTT0.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）关系得到下表：7.3条件概率分布的有效表达ColdFl包含连续变量的贝叶斯网络－HybridBNSubsidyHarvestBuysCostSHP(C)thfh高斯分布高斯分布CP(B)cS型函数P(S)xP(H)高斯分布离散随机变量：Subsidy,Buys;连续随机变量：Harvest,Cost.包含连续变量的贝叶斯网络－HybridBNSubsidyH线性高斯分布：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+)/]}线性高斯分布：P(c|h,subsidy)=N(a7.4贝叶斯网络中的精确推理变量分类：证据变量集E—特定事件e，查询变量X非证据变量集—Y隐变量（Hiddenvariable）全部变量的集合U={x}EY7.4贝叶斯网络中的精确推理变量分类：（1）通过枚举进行推理BurglaryEarthquakeMaryCallsJohnCallsAlarmBEP(A)tttfftff0.950.940.290.001AP(J)tf0.900.05AP(M)tf0.700.01P(B)0.001P(E)0.002（1）通过枚举进行推理BurglaryEarthquakeM已知，一个事件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)=eaP(B,e,a,j,m)=eaP(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)已知，一个事件e={JohnCalls=true,+++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)0.01P(e)P(~e)P(a|b,e)P(P(B|j,m)=P(B,j,m)=eaP(B,e,a,j,m)=eaP(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.950.90.7+0.050.050.01)]+[0.998(0.940.90.7+0.060.050.01)]}=0.00059224P(B|j,m)=P(B,j,m)=+++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)0.999P(e)P(~e)P(a|~b,eP(~B|j,m)=P(~B,j,m)=eaP(~B,e,a,j,m)=eaP(~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.290.90.7+0.710.050.01)]+[0.998(0.0010.90.7+0.9990.050.01)]}=0.0014919因此，P(B|j,m)=<0.00059224,0.0014919><0.284,0.716>即在John和Mary都打电话的条件下，出现盗贼的概率约为28%。P(~B|j,m)=P(~B,j,m)=Example:Tree-StructuredBayesianNetworkDABCFEG

p(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)

Example:Tree-StructuredBayesExampleDABcFEgSaywewanttocomputep(a|c,g)ExampleDABcFEgSaywewanttocExampleDABcFEgDirectcalculation:p(a|c,g)=Sbdefp(a,b,d,e,f|c,g)ComplexityofthesumisO(m4)ExampleDABcFEgDirectcalculatiExampleDABcFEgReordering:

Sdp(a|b)Sdp(b|d,c)Sep(d|e)Sfp(e,f|g)ExampleDABcFEgReordering:ExampleDABcFEgReordering:

Sb

p(a|b)Sdp(b|d,c)Sep(d|e)Sfp(e,f|g)p(e|g)ExampleDABcFEgReordering:p(e|gExampleDABcFEgReordering:

Sb

p(a|b)Sdp(b|d,c)Sep(d|e)p(e|g)p(d|g)ExampleDABcFEgReordering:p(d|gExampleDABcFEgReordering:

Sb

p(a|b)Sdp(b|d,c)p(d|g)p(b|c,g)ExampleDABcFEgReordering:p(b|cExampleDABcFEgReordering:

Sb

p(a|b)p(b|c,g)p(a|c,g)ComplexityisO(m),comparedtoO(m4)ExampleDABcFEgReordering:p(a|c（2）变量消元算法消除重复计算，提高枚举算法的效率保存中间结果，以备多次使用从右到左（在树结构中为自底向上）的次序计算BN的计算公式算法过程：参见《人工智能：一种现代方法》中的第14章14.4.2节贝叶斯网络的特性课件（3）Clustering算法（JointTree算法）单独节点联合起来形成Cluster节点，使得BN结构成为一棵多树（Polytree）多树——单连通网络，即任何两节点间至多只有一条路径相连概率推理包含命题逻辑推理作为其特殊情况，故BN的推理是一个NP问题在多连通的BN结构中，及时每个节点的父节点个数有固定的界限，在最坏的情况下，变量消元算法仍可能具有指数级时间和空间复杂度（3）Clustering算法（JointTree算法）多连通网络及其CPT：CloudyRainWetGrassSprinklerSRP(W)tttfftff0.990.900.900.00CP(S)tf0.100.50P(C)0.50CP(R)tf0.800.20多连通网络及其CPT：CloudyRainWetSprink等价的联合树及其CPT：CloudySpr+RainWetGrassS+RP(W)tttfftff0.990.900.900.00P(C)0.50等价的联合树及其CPT：CloudySpr+RainWet7.5贝叶斯网络的近似推理大规模多连通BN的精确推理是不可操作的，必须通过近似推理来解决。后验概率计算的主要采样方法直接采样方法马尔可夫链蒙特卡罗（MCMC）方法变分法(Variationalmethod)环传播(Loopypropagation)方法7.5贝叶斯网络的近似推理大规模多连通BN的精确推理是不

直接采样方法：直接采样算法拒绝采样(Rejectionsampling)算法似然加权(Likelihoodweighting)算法上述方法的详细步骤请参见：《人工智能：一种现代方法》第14章14.5.1节Berkeley大学Russell等人制作的PPT

/直接采样方法：马尔可夫链蒙特卡罗（MCMC）算法思想：对前一个事件进行随机改变而生成事件样本BN为每个变量指定了一个特定的当前状态下一个状态是通过对某个非证据变量Xi进行采样来产生，取决于Xi的马尔可夫覆盖中的变量当前值MCMC方法可视为：在状态空间中—所有可能的完整赋值空间—的随机走动—每次改变一个变量，但是证据变量的值固定不变。马尔可夫链蒙特卡罗（MCMC）算法思想：

MCMC算法执行过程示例：CloudyRainWetGrassSprinklerSRP(W)tttfftff0.990.900.900.00CP(S)tf0.100.50P(C)0.50CP(R)tf0.800.20【要求】：查询P(Rain|Sprinkler=true,WetGrass=true)的概率MCMC算法执行过程示例：CloudyRainWetSp

MCMC算法执行步骤：证据变量Sprinkler,WetGrass固定为true隐变量Cloudy和查询变量Rain随机初始化，例如，Cloudy=true,Rain=false，初始状态为：[C=true,S=true,R=false,W=true]反复执行如下步骤：

（1）根据Cloudy的马尔可夫覆盖(MB)变量的当前值，对Cloudy采样，即根据P(Cloudy|Sprinkler=true,Rain=false)（即转移概率）来采样。即：P(C|S,~R)=P(C,S,~R)/P(S,~R)=P(C)P(S|C)P(~R|C)/[P(C)P(S|C)P(~R|C)+P(~C)P(S|~C)P(~R|~C)]=(0.50.10.2)/[0.50.10.2+0.50.50.8]=0.04762MCMC算法执行步骤：

再由计算机生成一个随机数q[0,1]（可参照《概率统计》中的随机数生成方法）。比较转移概率值与随机数q的大小，以决定是继续停留在原状态，还是转移到下一个新的状态。判别方法如下：

ifq<P(C|S,~R)then转移到下一个新状态；

otherwise停留在原状态.

对于本例子，假设生成的随机数q=0.0389，可知，转移概率P(Cloudy|Sprinkler=true,Rain=false)=0.04762>q=0.0389，所以，Cloudy由true状态转移到新状态false，即采样结果为：Cloudy=false。故新的当前状态为：

[C=false,S=true,R=false,W=true]再由计算机生成一个随机数q[0,1]（可参照《概率

（2）根据Rain节点的马尔可夫覆盖(MB)变量的当前值，对Rain采样，即根据P(Rain|Cloudy=false,Sprinkler=true,WetGrass=true)来采样。假设采样结果为：Rain=true。故新的当前状态为：

[C=false,S=true,R=true,W=true]【注】：上述过程中所访问的每一个状态都是一个样本，能对查询变量Rain的估计有贡献。（3）重复上述步骤，直到所要求的访问次数N。若为true,false的次数分别为n1,n2，则查询解为：Normalize(<n1,n2>)=<n1/N,n1/N>若上述过程访问了20个Rain=true的状态和60个Rain=false的状态，则所求查询的解为<0.25,0.75>。（2）根据Rain节点的马尔可夫覆盖(MB)变量的CloudyRainSprinklerWetGrassRainCloudyCloudyRainCloudyRainSprinklerSprinklerSprinklerWetGrassWetGrassWetGrassCloudyRainSprinklerWetRainClou马尔可夫链蒙特卡罗（MCMC）算法描述：

functionMCMC-Ask(X,e,bn,N)returnP(X|e)

localvariables:N[X],

//关于查询变量X的向量计数，初值0

Z，//bn中的非证据变量集

x，//bn的当前状态利用Z中变量的随机值来初始化x；

for

j=1toNdoN(x)N(x)+1;//x是当前状态x中的查询变量X的值

foreachZiinZdo

给出Zi的马尔可夫覆盖MB(Zi)，并根据P(Zi|mb(Zi))

来采样的Zi值;

returnNormalize(N[X])//对N[X]进行归一化马尔可夫链蒙特卡罗（MCMC）算法描述：关于MCMC算法的补充说明：MCMC方法的一种常用的简单变体为：

吉布斯采样器（Gibbssampler）【注】：上述算法实质上就是吉布斯采样器。MCMC是概率模型计算中的一种强有力的方法，目前已发展出很多变形，包括：

（1）模拟退火算法（2）随机可满足性(Stochasticsatisfiability)算法关于MCMC算法的补充说明：

课后请研读论文：[1]TomM.Mitchell.Doesmachinelearningreallywork?AIMagazine,18(3):11-20,Fall1997.w/Library/Magazine/Vol18/18-03/vol18-03.html【必读】[2]C.Andrieuetal.Jordan.AnintroductiontoMCMCformachinelearning.MachineLearning,2003,5:5-43.

【可选读】【说明】对于打算编程实现，或以后可能要用MCMC算法的同学，请认真研读文献[2]。课后请研读论文：

马尔可夫链和MCMC方法的中文参考书：盛骤等.《概率论与数理统计》(第三版).高等教育出版社,2001.龚光鲁等.《应用随机过程教程及在算法和智能计算中的随机模型》.清华大学出版社,2004.“Donotjudge,oryoutoowillbejudged.Forinthesamewayyoujudgeothers,youwillbejudged,andwiththemeasureyouuse,itwillbemeasuredtoyou.”

FromMatthew7:1-2NIV

马尔可夫链和MCMC方法的中文参考书：“Dono贝叶斯网络初步

贝叶斯网络初步

内容提纲何谓贝叶斯网络？贝叶斯网络的语义条件分布的有效表达贝叶斯网络中的精确推理贝叶斯网络中的近似推理课后习题、编程实现及研读论文内容提纲何谓贝叶斯网络？7.1何谓贝叶斯网络？贝叶斯网络的由来贝叶斯网络的定义贝叶斯网络的别名独立和条件独立贝叶斯网络示例“Aboveallelse,guardyourheart,foritisthewellspringoflife.”fromProverbs4:23NIV7.1何谓贝叶斯网络？贝叶斯网络的由来“Aboveal贝叶斯网络的由来

全联合概率计算复杂性十分巨大朴素贝叶斯太过简单现实需要一种自然、有效的方式来捕捉和推理——不确定性知识变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目贝叶斯网络的由来全联合概率计算复杂性十分巨大B.贝叶斯网络的定义

是一个有向无环图(DAG)随机变量集组成网络节点，变量可离散或连续一个连接节点对的有向边或箭头集合每节点Xi都有一个条件概率分布表：P(Xi|Parents(Xi))，量化其父节点对该节点的影响B.贝叶斯网络的定义是一个有向无环图(DAG)C.贝叶斯网络的别名

信念网(BeliefNetwork)概率网络(ProbabilityNetwork)因果网络(CausalNetwork)知识图(KnowledgeMap)图模型(GraphicalModel)或概率图模型(PGM)决策网络(DecisionNetwork)影响图(InfluenceDiagram)C.贝叶斯网络的别名信念网(BeliefNetworkD.独立和条件独立WeatherCavityCatchToothacheWeather和其它3个变量相互独立给定Cavity后，Toothache和Catch条件独立D.独立和条件独立WeatherCavityCatchToE.贝叶斯网络示例BurglaryEarthquakeMaryCallsJohnCallsAlarmBEP(A)tttfftff0.950.940.290.001AP(J)tf0.900.05AP(M)tf0.700.01P(B)0.001P(E)0.002E.贝叶斯网络示例BurglaryEarthquakeMa7.2贝叶斯网络的语义贝叶斯网络的两种含义对联合概率分布的表示—构造网络对条件依赖性语句集合的编码—设计推理过程贝叶斯网络的语义P(x1,...,xn)=P(x1|parent(x1))...P(xn|parent(xn))7.2贝叶斯网络的语义贝叶斯网络的两种含义贝叶斯网络的语义公式计算示例：

试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时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:2NIV贝叶斯网络中的条件独立关系：给定父节点，一个节点与它的非后U1UmXZ1jZnjY1Yn【说明】：给定节点X的父节点U1...Um，节点X与它的非后代节点（即Zij）是条件独立的。U1UmXZ1jZnjY1Yn【说明】：U1UmXZ1jZnjY1Yn【说明】：给定马尔可夫覆盖（两圆圈之间的区域），节点X和网络中所有其它节点都是条件独立的。U1UmXZ1jZnjY1Yn【说明】：7.3条件概率分布的有效表达

ColdFluMalariaP(Fever)P(~Fever)FFF

FFT

FTFFTT

TFFTFTTTFTTT0.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）关系得到下表：7.3条件概率分布的有效表达ColdFl包含连续变量的贝叶斯网络－HybridBNSubsidyHarvestBuysCostSHP(C)thfh高斯分布高斯分布CP(B)cS型函数P(S)xP(H)高斯分布离散随机变量：Subsidy,Buys;连续随机变量：Harvest,Cost.包含连续变量的贝叶斯网络－HybridBNSubsidyH线性高斯分布：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+)/]}线性高斯分布：P(c|h,subsidy)=N(a7.4贝叶斯网络中的精确推理变量分类：证据变量集E—特定事件e，查询变量X非证据变量集—Y隐变量（Hiddenvariable）全部变量的集合U={x}EY7.4贝叶斯网络中的精确推理变量分类：（1）通过枚举进行推理BurglaryEarthquakeMaryCallsJohnCallsAlarmBEP(A)tttfftff0.950.940.290.001AP(J)tf0.900.05AP(M)tf0.700.01P(B)0.001P(E)0.002（1）通过枚举进行推理BurglaryEarthquakeM已知，一个事件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)=eaP(B,e,a,j,m)=eaP(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)已知，一个事件e={JohnCalls=true,+++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)0.01P(e)P(~e)P(a|b,e)P(P(B|j,m)=P(B,j,m)=eaP(B,e,a,j,m)=eaP(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.950.90.7+0.050.050.01)]+[0.998(0.940.90.7+0.060.050.01)]}=0.00059224P(B|j,m)=P(B,j,m)=+++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)0.999P(e)P(~e)P(a|~b,eP(~B|j,m)=P(~B,j,m)=eaP(~B,e,a,j,m)=eaP(~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.290.90.7+0.710.050.01)]+[0.998(0.0010.90.7+0.9990.050.01)]}=0.0014919因此，P(B|j,m)=<0.00059224,0.0014919><0.284,0.716>即在John和Mary都打电话的条件下，出现盗贼的概率约为28%。P(~B|j,m)=P(~B,j,m)=Example:Tree-StructuredBayesianNetworkDABCFEG

p(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)

Example:Tree-StructuredBayesExampleDABcFEgSaywewanttocomputep(a|c,g)ExampleDABcFEgSaywewanttocExampleDABcFEgDirectcalculation:p(a|c,g)=Sbdefp(a,b,d,e,f|c,g)ComplexityofthesumisO(m4)ExampleDABcFEgDirectcalculatiExampleDABcFEgReordering:

Sdp(a|b)Sdp(b|d,c)Sep(d|e)Sfp(e,f|g)ExampleDABcFEgReordering:ExampleDABcFEgReordering:

Sb

p(a|b)Sdp(b|d,c)Sep(d|e)Sfp(e,f|g)p(e|g)ExampleDABcFEgReordering:p(e|gExampleDABcFEgReordering:

Sb

p(a|b)Sdp(b|d,c)Sep(d|e)p(e|g)p(d|g)ExampleDABcFEgReordering:p(d|gExampleDABcFEgReordering:

Sb

p(a|b)Sdp(b|d,c)p(d|g)p(b|c,g)ExampleDABcFEgReordering:p(b|cExampleDABcFEgReordering:

Sb

p(a|b)p(b|c,g)p(a|c,g)ComplexityisO(m),comparedtoO(m4)ExampleDABcFEgReordering:p(a|c（2）变量消元算法消除重复计算，提高枚举算法的效率保存中间结果，以备多次使用从右到左（在树结构中为自底向上）的次序计算BN的计算公式算法过程：参见《人工智能：一种现代方法》中的第14章14.4.2节贝叶斯网络的特性课件（3）Clustering算法（JointTree算法）单独节点联合起来形成Cluster节点，使得BN结构成为一棵多树（Polytree）多树——单连通网络，即任何两节点间至多只有一条路径相连概率推理包含命题逻辑推理作为其特殊情况，故BN的推理是一个NP问题在多连通的BN结构中，及时每个节点的父节点个数有固定的界限，在最坏的情况下，变量消元算法仍可能具有指数级时间和空间复杂度（3）Clustering算法（JointTree算法）多连通网络及其CPT：CloudyRainWetGrassSprinklerSRP(W)tttfftff0.990.900.900.00CP(S)tf0.100.50P(C)0.50CP(R)tf0.800.20多连通网络及其CPT：CloudyRainWetSprink等价的联合树及其CPT：CloudySpr+RainWetGrassS+RP(W)tttfftff0.990.900.900.00P(C)0.50等价的联合树及其CPT：CloudySpr+RainWet7.5贝叶斯网络的近似推理大规模多连通BN的精确推理是不可操作的，必须通过近似推理来解决。后验概率计算的主要采样方法直接采样方法马尔可夫链蒙特卡罗（MCMC）方法变分法(Variationalmethod)环传播(Loopypropagation)方法7.5贝叶斯网络的近似推理大规模多连通BN的精确推理是不

直接采样方法：直接采样算法拒绝采样(Rejectionsampling)算法似然加权(Likelihoodweighting)算法上述方法的详细步骤请参见：《人工智能：一种现代方法》第14章14.5.1节Berkeley大学Russell等人制作的PPT

/直接采样方法：马尔可夫链蒙特卡罗（MCMC）算法思想：对前一个事件进行随机改变而生成事件样本BN为每个变量指定了一个特定的当前状态下一个状态是通过对某个非证据变量Xi进行采样来产生，取决于Xi的马尔可夫覆盖中的变量当前值MCMC方法可视为：在状态空间中—所有可能的完整赋值空间—的随机走动—每次改变一个变量，但是证据变量的值固定不变。马尔可夫链蒙特卡罗（MCMC）算法思想：

MCMC算法执行过程示例：CloudyRainWetGrassSprinklerSRP(W)tttfftff0.990.900.900.00CP(S)tf0.100.50P(C)0.50CP(R)tf0.800.20【要求】：查询P(Rain|Sprinkler=true,WetGrass=true)的概率MCMC算法执行过程示例：CloudyRainWetSp

MCMC算法执行步骤：证据变量Sprinkler,WetGrass固定为true隐变量Cloudy和查询变量Rain随机初始化，例如，Cloudy=true,Rain=false，初始状态为：[C=true,S=true,R=false,W=true]反复执行如下步骤：

（1）根据Cloudy的马尔可夫覆盖(MB)变量的当前值，对Cloudy采样，即根据P(Cloudy|Sprinkler=true,Rain=false)（即转移概率）来采样。即：P(C|S,~R)=P(C,S,~R)/P(S,~R)=P(C)P(S|C)P(~R|C)/[P(C)P(S|C)P(~R|C)+P(~C)P(S|~C)P(~R|~C)]=(0.50.10.2)/[0.50.10.2+0.50.50.8]=0.04762MCMC算法执行步骤：

再由计算机生成一个随机数q[0,1]（可参照《概率统计》中的随机数生成方法）。比较转移概率值与随机数q的大小，以决定是继续停留在原状态，还是转移到下一个新的状态。判别方法如下：

ifq<P(C|S,~R)then转移到下一个新状态；

otherwise停留在原状态.

对于本例子，假设生成的随机数q=0.0389，可知，转移概率P(Cloudy|Sprinkler=true,Rain=false)=0.04762>q=0.0389，所以，Cloudy由true状态转移到新状态false，即采样结果为：Cloudy=false。故新的当前状态为：

[C=false,S=true,R=fals