《浙江大学研究生《人工智能引论》课件优秀PPT.ppt》由会员分享，可在线阅读，更多相关《浙江大学研究生《人工智能引论》课件优秀PPT.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、浙江高校探讨生人工智能引论课件浙江高校探讨生人工智能引论课件徐从富徐从富(Congfu Xu)PhD,Associate Professor Email:xucongfuzju.edu Institute of Artificial Intelligence,College of Computer Science,Zhejiang University,Hangzhou 310027,P.R.ChinaSeptember 11,2005第一稿第一稿Oct.8,2006其次次修改稿其次次修改稿第七讲 贝叶斯网络初步(Chapter7 Bayesian Networks)内容提纲内容提纲n何谓贝叶
2、斯网络？n贝叶斯网络的语义n条件分布的有效表达n贝叶斯网络中的精确推理n贝叶斯网络中的近似推理n课后习题、编程实现及研读论文7.1 何谓贝叶斯网络？何谓贝叶斯网络？A.贝叶斯网络的由来B.贝叶斯网络的定义C.贝叶斯网络的别名D.独立和条件独立E.贝叶斯网络示例“Above all else,guard your heart,for it is the wellspring of life.”from Proverbs 4:23 NIVA.贝叶斯网络的由来贝叶斯网络的由来 n全联合概率计算困难性特别巨大n朴实贝叶斯太过简洁n现实须要一种自然、有效的方式来捕获和推理不确定性学问n变量之间的独立性和
3、条件独立性可大大削减为了定义全联合概率分布所需的概率数目B.贝叶斯网络的定义贝叶斯网络的定义 n是一个有向无环图(DAG)n随机变量集组成网络节点，变量可离散或连续n一个连接节点对的有向边或箭头集合n每 节 点 Xi都 有 一 个 条 件 概 率 分 布 表：P(Xi|Parents(Xi)，量化其父节点对该节点的影响C.贝叶斯网络的别名贝叶斯网络的别名 n信念网(Belief Network)n概率网络(Probability Network)n因果网络(Causal Network)n学问图(Knowledge Map)n图模型(Graphical Model)或概率图模型(PGM)n决策
4、网络(Decision Network)n影响图(Influence Diagram)D.独立和条件独立独立和条件独立WeatherCavityCatchToothachen Weather和其它3个变量相互独立n 给定Cavity后，Toothache和Catch条件独立E.贝叶斯网络示例贝叶斯网络示例BurglaryEarthquakeMaryCallsJohnCallsAlarm B EP(A)t t t f f t f f0.950.940.290.001 AP(J)t f0.900.05 AP(M)t f0.700.01P(B)0.001P(E)0.0027.2 贝叶斯网络的语义贝叶
5、斯网络的语义n贝叶斯网络的两种含义贝叶斯网络的两种含义n对联合概率分布的表示对联合概率分布的表示 构造网络构造网络n对条件依靠性语句集合的编码对条件依靠性语句集合的编码 设计设计推理过程推理过程n贝叶斯网络的语义贝叶斯网络的语义nP(x1,.,xn)=P(x1|parent(x1).P(xn|parent(xn)贝叶斯网络的语义公式计算示例：贝叶斯网络的语义公式计算示例：n试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时John和Mary都给你打电话的概率。n解：P(j,m,a,b,e)=P(j|a)P(m|a)P(a|b,e)P(b)P(e)=0.90.70.0010.9990.9
6、98=0.00062 =0.062%贝叶斯网络的特性：贝叶斯网络的特性：n作为对域的一种完备而无冗余的表示，贝叶斯网络比全联合概率分布紧凑得多nBN的紧凑性是局部结构化(Locally structured,也称稀疏,Sparse)系统一个特别普遍特性的实例nBN中每个节点只与数量有限的其它节点发生干脆的相互作用n假设节点数n=30,每节点有5个父节点，则BN需30 x25=960个数据，而全联合概率分布须要230=10亿个！贝叶斯网络的构造原则：贝叶斯网络的构造原则：n首先，添加“根本缘由”节点n然后，加入受它们干脆影响的变量n依次类推，直到叶节点，即对其它变量没有干脆因果影响的节点n两节点
7、间的有向边的取舍原则：更高精度概率的重要性与指定额外信息的代价的折衷n“因果模型”比“诊断模型”须要更少的数据，且这些数据也更简洁得到贝叶斯网络中的条件独立关系：贝叶斯网络中的条件独立关系：n给定父节点，一个节点与它的非后代节点是条件独立的n给定一个节点的父节点、子节点以及子节点的父节点马尔可夫覆盖(Markov blanket)，这个节点和网络中的全部其它节点是条件独立的“But his delight is in the law of the LORD,and on his law he meditates day and night.”From Psalms 1:2 NIVU1UmXZ1
8、jZnjY1Yn【说明】：给定节点X的父节点U1.Um，节点X与它的非后代节点（即Zij）是条件独立的。U1UmXZ1jZnjY1Yn【说明】：给定马尔可夫覆盖（两圆圈之间的区域），节点X和网络中全部其它节点都是条件独立的。7.3 条件概率分布的有效表达条件概率分布的有效表达 Cold Flu MalariaP(Fever)P(Fever)F F F F F T F T F F T T T F F T F T T T F T T T0.00.90.80.980.40.940.880.9881.00.10.20.02=0.2 X 0.10.60.06=0.6 X 0.10.12=0.6 X 0.
9、20.012=0.6 X 0.2 X 0.1已知：P(fever|cold,flu,malaria)=0.6 P(fever|cold,flu,malaria)=0.2 P(fever|cold,flu,malaria)=0.1，可利用“噪声或噪声或”（Noisy-OR）关系得到下表：包含连续变量的贝叶斯网络包含连续变量的贝叶斯网络Hybrid BNSubsidyHarvestBuysCost S HP(C)t h f h高斯分布高斯分布高斯分布高斯分布 CP(B)c S型函数型函数P(S)xP(H)高斯分布高斯分布离散随机变量：离散随机变量：Subsidy,Buys;连续随机变量：连续随机变
10、量：Harvest,Cost.线性高斯分布：nP(c|h,subsidy)=N(ath+bt,t2)(c)=1/(t21/2)e 1/2c-(ath+bt)/tnP(c|h,subsidy)=N(afh+bf,f2)(c)=1/(f21/2)e 1/2c-(afh+bf)/t S型函数(Sigmoid function)np(buys|Cost=c)=1/1+exp-2(-u+)/7.4 贝叶斯网络中的精确推理贝叶斯网络中的精确推理变量分类：证据变量集E 特定事务e，查询变量X非证据变量集 Y隐变量（Hidden variable）全部变量的集合U=x E Y（1）通过枚举进行推理）通过枚举进
11、行推理BurglaryEarthquakeMaryCallsJohnCallsAlarm B EP(A)t t t f f t f f0.950.940.290.001 AP(J)t f0.900.05 AP(M)t f0.700.01P(B)0.001P(E)0.002n已知，一个事务e=JohnCalls=true,and MaryCalls=true，试问出现盗贼的概率是多少？n解：P(X|e)=P(X,e)=yP(X,e,y)n 而P(X,e,y)可写成条件概率乘积的形式。n 因此，在贝叶斯网络中可通过计算条件概率的乘积并求和来回答查询。n P(Burgary|JohnCalls=tr
12、ue,MaryCalls=true)简写为：n P(B|j,m)=P(B,j,m)=eaP(B,e,a,j,m)n =ea P(b)P(e)P(a|b,e)P(j|a)P(m|a)n =P(b)e P(e)a P(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)的自顶向下的计算过程nP
13、(B|j,m)=P(B,j,m)=eaP(B,e,a,j,m)=ea P(b)P(e)P(a|b,e)P(j|a)P(m|a)=P(b)e P(e)a P(a|b,e)P(j|a)P(m|a)=0.0010.002(0.950.90.7+0.050.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(
14、j|a)0.05P(m|a)0.70P(m|a)0.01P(m|a)0.01P(b|j,m)的自顶向下的计算过程nP(B|j,m)=P(B,j,m)=eaP(B,e,a,j,m)=ea P(b)P(e)P(a|b,e)P(j|a)P(m|a)=P(b)e P(e)a P(a|b,e)P(j|a)P(m|a)=0.9990.002(0.290.90.7+0.710.05 0.01)+0.998 (0.001 0.9 0.7+0.999 0.05 0.01)=0.0014919因此，P(B|j,m)=即在John和Mary都打电话的条件下，出现盗贼的概率约为28%。【课后习题1】国家政策国家政策（
15、C）学校政策学校政策（U）身体状况身体状况差（差（B）过劳死过劳死（D）工作压力工作压力大（大（W）W BP(A)t t t f f t f f0.3350.300.050.00 UP(W)t f0.900.05 CP(U)t f0.950.01P(C)0.50 UP(B)t f0.300.01n已知：一个事务e=学校政策U=true,and 工作压力大=true，n请依据上述枚举法计算出现过劳死的概率。n（2）变量消元算法n消退重复计算，提高枚举算法的效率 n保存中间结果，以备多次运用n从右到左（在树结构中为自底向上）的次序计算BN的计算公式n算法过程：参见人工智能：一种现代方法中的第14章
16、14.4.2节（3）Clustering算法（算法（Joint Tree算法）算法）单独节点联合起来形成单独节点联合起来形成Cluster节点，使得节点，使得BN结构成为一棵多树（结构成为一棵多树（Polytree）多树多树单连通网络，即任何两节点间至单连通网络，即任何两节点间至多只有一条路径相连多只有一条路径相连 概率推理包含命题逻辑推理作为其特殊状概率推理包含命题逻辑推理作为其特殊状况，故况，故BN的推理是一个的推理是一个NP问题问题在多连通的在多连通的BN结构中，刚好每个节点的父结构中，刚好每个节点的父节点个数有固定的界限，在最坏的状况节点个数有固定的界限，在最坏的状况下，变量消元算法仍
17、可能具有指数级时下，变量消元算法仍可能具有指数级时间和空间困难度间和空间困难度多连通网络及其CPT：CloudyRainWetGrassSprinkler S RP(W)t t t f f t f f0.990.900.900.00 CP(S)t f0.100.50P(C)0.50 CP(R)t f0.800.20等价的联合树及其CPT：CloudySpr+RainWetGrass S+RP(W)t t t f f t f f0.990.900.900.00P(C)0.50 CP(S+R=x)t t t f f t f f t f.08 .02 .72 .18.10 .40 .10 .407.
18、5 贝叶斯网络的近似推理贝叶斯网络的近似推理n大规模多连通大规模多连通BN的精确推理是不行操作的，的精确推理是不行操作的，n 必需通过近似推理来解决。必需通过近似推理来解决。n后验概率计算的主要采样方法后验概率计算的主要采样方法n干脆采样方法干脆采样方法n马尔可夫链蒙特卡罗（马尔可夫链蒙特卡罗（MCMC）方法）方法n变分法变分法(Variational method)n环传播环传播(Loopy propagation)方法方法 干脆采样方法：干脆采样方法：干脆采样算法干脆采样算法拒绝采样拒绝采样(Rejection sampling)算法算法似然加权似然加权(Likelihood weight
19、ing)算法算法上述方法的具体步骤请参见：上述方法的具体步骤请参见：人工智能：一种现代方法第人工智能：一种现代方法第14章章14.5.1节节Berkeley高校高校Russell等人制作的等人制作的PPT马尔可夫链蒙特卡罗（马尔可夫链蒙特卡罗（MCMC）算法思想：）算法思想：对前一个事务进行随机变更而生成事务样本对前一个事务进行随机变更而生成事务样本BN为每个变量指定了一个特定的当前状态为每个变量指定了一个特定的当前状态下一个状态是通过对某个非证据变量下一个状态是通过对某个非证据变量Xi进行采样进行采样来产生，取决于来产生，取决于Xi的马尔可夫覆盖中的变量当的马尔可夫覆盖中的变量当前值前值MC
20、MC方法可视为：在状态空间中方法可视为：在状态空间中全部可能全部可能的完整赋值空间的完整赋值空间的随机走动的随机走动每次变更一个每次变更一个变量，但是证据变量的值固定不变。变量，但是证据变量的值固定不变。MCMC算法执行过程示例：算法执行过程示例：CloudyRainWetGrassSprinkler S RP(W)t t t f f t f f0.990.900.900.00 CP(S)t f0.100.50P(C)0.50 CP(R)t f0.800.20【要求】：查询【要求】：查询P(Rain|Sprinkler=true,WetGrass=true)的概率的概率 MCMC算法执行步骤：
21、算法执行步骤：证据变量证据变量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
22、,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.5 0.50.8=0.04762 再由计算机生成一个随机数q0,1（可参照概率统计中的随机数生成方法）。比较转移概率值与随机数q的大小，以确定是接着停留在原状态，还是转移到下一个新的状态。判别方法如下：if q q=0.0389，所以，Cloudy由true状态转移到新状态false，即采样结果为：Cloudy=false。故新的当前状态为：C=false,S=true,R=false,W=true （2）
23、依据依据Rain节点的马尔可夫覆盖节点的马尔可夫覆盖(MB)变变量的当前值，对量的当前值，对Rain采样，即依据采样，即依据P(Rain|Cloudy=false,Sprinkler=true,WetGrass=true)来采样。假设采样结果为：来采样。假设采样结果为：Rain=true。故新的当前状态为：。故新的当前状态为：C=false,S=true,R=true,W=true【注】：【注】：上述过程中所访问的每一个状态都是上述过程中所访问的每一个状态都是一个样本，能对查询变量一个样本，能对查询变量Rain的估计有贡献。的估计有贡献。（3）重复上述步骤，直到所要求的访问次数）重复上述步骤，
24、直到所要求的访问次数N。若为若为true,false的次数分别为的次数分别为n1,n2，则查询，则查询解为：解为：Normalize()=若上述过程访问了若上述过程访问了20个个Rain=true的状态和的状态和60个个Rain=false的状态，则所求查询的解为的状态，则所求查询的解为。CloudyRainSprinklerWetGrassRainCloudyCloudyRainCloudyRainSprinklerSprinklerSprinklerWetGrassWetGrassWetGrass马尔可夫链蒙特卡罗（马尔可夫链蒙特卡罗（MCMC）算法描述：）算法描述：function MC
25、MC-Ask(X,e,bn,N)return P(X|e)local variables:NX,/关于查询变量关于查询变量X的的向量计数，初值向量计数，初值0 Z，/bn中的非证据变量中的非证据变量集集 x，/bn的当前状态的当前状态 利用利用Z中变量的随机值来初始化中变量的随机值来初始化x；for j=1 to N do N(x)N(x)+1;/x是当前状态是当前状态x中的中的查询变量查询变量X的值的值 for each Zi in Z do 给出给出Zi的马尔可夫覆盖的马尔可夫覆盖MB(Zi)，并，并依据依据P(Zi|mb(Zi)来采样的来采样的Zi值值;return Normalize(
26、NX)/对对NX进行归进行归一化一化关于关于MCMC算法的补充说明：算法的补充说明：MCMC方法的一种常用的简洁变体为：方法的一种常用的简洁变体为：吉布斯采样器（吉布斯采样器（Gibbs sampler）【注】：上述算法实质上就是吉布斯采样器。【注】：上述算法实质上就是吉布斯采样器。MCMC是概率模型计算中的一种强有力的方法，是概率模型计算中的一种强有力的方法，目前已发展出很多变形，包括：目前已发展出很多变形，包括：（1）模拟退火算法）模拟退火算法 （2）随机可满足性）随机可满足性(Stochastic satisfiability)算法算法【课后习题2】国家政策国家政策（C）学校政策学校政策
27、（U）身体状况身体状况差（差（B）过劳死过劳死（D）工作压力工作压力大（大（W）W BP(A)t t t f f t f f0.3350.300.050.00 UP(W)t f0.900.05 CP(U)t f0.950.01P(C)0.50 UP(B)t f0.300.01已知：事务e=学校政策U=true且工作压力大W=true问题：（1）请依据上述MCMC算法计算:P(过劳死|学校政策U=true,工作压力大W=true)的概率。（2）比较枚举算法和MCMC算法的计算结果。“No one can serve two masters.Either he will hate the one
28、and love the other,or he will be devoted to the one and despise the other.You cannot serve both God and Money.”From Matthew 6:24 NIV 本课程的编程实现题目之一：本课程的编程实现题目之一：请编程实现基于请编程实现基于MCMC方法的方法的BN近似推理算法近似推理算法MCMC算法算法并用若干实例来验证结果的正确性并用若干实例来验证结果的正确性【说明】：人工智能：一种现代方法一书【说明】：人工智能：一种现代方法一书中关于中关于MCMC算法（特殊是状态转移方法）算法（特殊是
29、状态转移方法）的论述不够具体，在编程实现时，请再参考的论述不够具体，在编程实现时，请再参考其它相关的文献资料。其它相关的文献资料。课后请研读论文：课后请研读论文：1 Tom M.Mitchell.Does machine learning really work?AI Magazine,18(3):11-20,Fall 1997.w :/aaai.org/Library/Magazine/Vol18/18-03/vol18-03.html 【必读】【必读】2 C.Andrieu et al.Jordan.An introduction to MCMC for machine learning.
30、Machine Learning,2003,5:5-43.【可选读】【可选读】【说明】【说明】对于准备编程实现，或以后可能要用对于准备编程实现，或以后可能要用MCMC算法的同学，请细致研读文献算法的同学，请细致研读文献2。马尔可夫链和MCMC方法的中文参考书：盛骤 等.概率论与数理统计(第三版).高等教化出版社,2001.龚光鲁 等.应用随机过程教程及在算法和智能计算中的随机模型.清华高校出版社,2004.“Do not judge,or you too will be judged.For in the same way you judge others,you will be judged
31、,and with the measure you use,it will be measured to you.”From Matthew 7:1-2 NIV THANKS FOR YOUR PRESENCE!“All Scripture is God-breathed and is useful for teaching,rebuking,correcting and training in righteousness,so that the man of God may be thoroughly equipped for every good work.”from 2 Timothy 3:16-17,NIV