ai-05-15-贝叶斯网络-----人工智能课程--浙江大学研究生

1、徐从富,浙江大学人工智能研究所 2005年9月11日,贝叶斯网络 Bayesian Network,研究生人工智能补充课件,内容提纲,什么是贝叶斯网络？ 贝叶斯网络的语义 条件分布的有效表达 贝叶斯网络中的精确推理 贝叶斯网络中的近似推理 课后习题、编程实现及研读论文,1、什么是贝叶斯网络？,贝叶斯网络的由来 贝叶斯网络的定义 贝叶斯网络的别名 独立和条件独立 贝叶斯网络示例,贝叶斯网络的由来,全联合概率计算复杂性十分巨大 朴素贝叶斯太过简单 现实需要一种自然、有效的方式来捕捉和推理不确定性知识 变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目,B. 贝叶斯网络的定义

2、,是一个有向无环图(DAG) 随机变量集组成网络节点，变量可离散或连续 一个连接节点对的有向边或箭头集合 每节点Xi都有一个条件概率分布表：P(Xi|Parents(Xi)，量化其父节点对该节点的影响,C. 贝叶斯网络的别名,信念网(Belief Network) 概率网络(Probability Network) 因果网络(Causal Network) 知识图(Knowledge Map) 图模型(Graphical Model)或概率图模型 决策网络(Decision Network) 影响图(Influence Diagram),D. 独立和条件独立,Weather,Cavity,Ca

3、tch,Toothache,Weather和其它3个变量相互独立 给定Cavity后，Toothache和Catch条件独立,E. 贝叶斯网络示例,Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,贝叶斯网络的语义,贝叶斯网络的两种含义 对联合概率分布的表示 构造网络 对条件依赖性语句集合的编码 设计推理过程 贝叶斯网络的语义 P(x1,., xn) = P(x1|parent(x1). P(x1|parent(xn),贝叶斯网络的语义公式计算示例：,试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时John和Mary都给你打电话的概率。 解：

4、 P(j,m,a,b,e) = P(j|a)P(m|a)P(a|b,e)P(e) = 0.9x0.7x0.001x0.999x0.998 = 0.00062 = 0.062%,贝叶斯网络的特性：,作为对域的一种完备而无冗余的表示，贝叶斯网络比全联合概率分布紧凑得多 BN的紧凑性是局部结构化(Locally structured, 也称稀疏, Sparse)系统一个非常普遍特性的实例 BN中每个节点只与数量有限的其它节点发生直接的相互作用 假设节点数n=30, 每节点有5个父节点，则BN需30 x25=960个数据，而全联合概率分布需要230= 10亿个。,贝叶斯网络的构造原则：,首先，添加“根

5、本原因”节点 然后，加入受它们直接影响的变量 依次类推，直到叶节点，即对其它变量没有直接因果影响的节点 两节点间的有向边的取舍原则：更高精度概率的重要性与指定额外信息的代价的折衷 “因果模型”比“诊断模型”需要更少的数据，且这些数据也更容易得到,贝叶斯网络中的条件独立关系：,给定父节点，一个节点与它的非后代节点是条件独立的 给定一个节点的父节点、子节点以及子节点的父节点马尔可夫覆盖(Markov blanket)，这个节点和网络中的所有其它节点是条件独立的,U1,Um,X,Z1j,Znj,Y1,Yn,【说明】： 给定节点X的父节点U1. Um，节点X与它的非后代节点（即Zij）是条件独立的。,

6、U1,Um,X,Z1j,Znj,Y1,Yn,【说明】： 给定马尔可夫覆盖（两圆圈之间的区域），节点X和网络中所有其它节点都是条件独立的。,3、条件概率分布的有效表达,已知：P(fever | cold, flu, malaria) = 0.6 P(fever | cold, flu, malaria) = 0.2 P(fever | cold, flu, malaria) = 0.1， 可利用“噪声或”（Noisy-OR）关系得到下表：,包含连续变量的贝叶斯网络Hybrid BN,Subsidy,Harvest,Buys,Cost,离散随机变量：Subsidy, Buys; 连续随机变量：Ha

7、rvest, Cost.,线性高斯分布：,P(c | h, subsidy) = N(ath + bt, t2)(c) = 1/ (t21/2) e 1/2c-(ath + bt)/t P(c | h, subsidy) = N(afh + bf, f2)(c) = 1/ (f21/2) e 1/2c-(afh + bf)/t S型函数(Sigmoid function) p(buys | Cost = c) = 1 / 1 + exp-2(-u+)/ ,4、贝叶斯网络中的精确推理,变量分类： 证据变量集E 特定事件e， 查询变量X 非证据变量集 Y隐变量（Hidden variable） 全

8、部变量的集合U = x E Y,（1）通过枚举进行推理,Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,已知，一个事件e = JohnCalls = true, and MaryCalls = 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)

9、= 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),+,+,+,P(b)0.01,P(e) 0.002,P(e) 0.998,P(a|b,e) 0.95,P(a|b,e) 0.05,P(a|b,e) 0.94,P(a|b,e) 0.06,P(m|a) 0.70,P(j|a) 0.90,P(j|a) 0.05,P(j|a) 0.90,P(j|a) 0.05,P(m|a) 0.70,P(m|a) 0.01,P(m|a) 0.01,P(b | j, m)的自顶向下的计算

10、过程,P(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.999,P(e) 0.002,P(e) 0.998,P(a|b,e) 0.29,P(a|b,e) 0.71,P(a|b,e) 0.001,P(a|b,e

11、) 0.999,P(m|a) 0.70,P(j|a) 0.90,P(j|a) 0.05,P(j|a) 0.90,P(j|a) 0.05,P(m|a) 0.70,P(m|a) 0.01,P(m|a) 0.01,P(b | j, m)的自顶向下的计算过程,P(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

12、.9 0.7+0.999 0.05 0.01) = 0.0014919 因此，P(B|j, m) = 即在John和Mary都打电话的条件下，出现盗贼的概率约为28%。,【课后习题1】,国家政策 （C）,学校政策 （U）,身体状况 差（B）,过劳死 （D）,工作压力 大（W）,已知：一个事件e = 学校政策U = true, and 工作压力大 = true， 请根据上述枚举法计算出现过劳死的概率。 （2）变量消元算法 消除重复计算，提高枚举算法的效率 保存中间结果，以备多次使用 从右到左（在树结构中为自底向上）的次序计算BN的计算公式 算法过程：参见人工智能：一种现代方法中的第14章14.4

13、.2节,（3）Clustering算法（Joint Tree算法） 单独节点联合起来形成Cluster节点，使得BN结构成为一棵多树（Polytree） 多树单连通网络，即任何两节点间至多只有一条路径相连 概率推理包含命题逻辑推理作为其特殊情况，故BN的推理是一个NP问题 在多连通的BN结构中，及时每个节点的父节点个数有固定的界限，在最坏的情况下，变量消元算法仍可能具有指数级时间和空间复杂度,多连通网络及其CPT：,Cloudy,Rain,Wet Grass,Sprinkler,等价的联合树及其CPT：,Cloudy,Spr+Rain,Wet Grass,5、贝叶斯网络的近似推理,大规模多连通

14、BN的精确推理是不可操作的， 必须通过近似推理来解决。 后验概率计算的主要采样方法 直接采样方法 马尔可夫链蒙特卡罗（MCMC）方法 变分法(Variational method) 环传播(Loopy propagation)方法,直接采样方法： 直接采样算法 拒绝采样(Rejection sampling)算法 似然加权(Likelihood weighting)算法 上述方法的详细步骤请参见： 人工智能：一种现代方法第14章14.5.1节 Berkeley大学Russell等人制作的PPT /,马尔可夫链蒙特卡罗（MCMC）算法思想： 对

15、前一个事件进行随机改变而生成事件样本 BN为每个变量指定了一个特定的当前状态 下一个状态是通过对某个非证据变量Xi进行采样来产生，取决于Xi的马尔可夫覆盖中的变量当前值 MCMC方法可视为：在状态空间中所有可能的完整赋值空间的随机走动每次改变一个变量，但是证据变量的值固定不变。,MCMC算法执行过程示例：,Cloudy,Rain,Wet Grass,Sprinkler,【要求】：查询P(Rain | Sprinkler = true, WetGrass = true)的概率,MCMC算法执行步骤： 证据变量Sprinkler, WetGrass固定为true 隐变量Cloudy和查询变量Rai

16、n随机初始化，例如， 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.5 0.50

17、.8=0.04762,再由计算机生成一个随机数q0,1（可参照概率统计中的随机数生成方法）。比较转移概率值与随机数q的大小，以决定是继续停留在原状态，还是转移到下一个新的状态。判别方法如下： if q P(C|S, R) then 转移到下一个新状态； otherwise 停留在原状态. 对于本例子，假设生成的随机数q=0.0489，可知， 转移概率P(Cloudy|Sprinkler= true, Rain=false)= 0.04762 q=0.0489，所以，Cloudy由true状态转移到新状态false，即采样结果为：Cloudy = false。故新的当前状态为： C=false,

18、 S=true, R=false, W=true,（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

19、() = 若上述过程访问了20个Rain=true的状态和60个Rain = false的状态，则所求查询的解为。,Cloudy,Rain,Sprinkler,Wet Grass,Rain,Cloudy,Cloudy,Rain,Cloudy,Rain,Sprinkler,Sprinkler,Sprinkler,Wet Grass,Wet Grass,Wet Grass,马尔可夫链蒙特卡罗（MCMC）算法描述： function MCMC-Ask(X, e, bn, N) return P(X | e) local variables: NX, /关于查询变量X的向量计数，初值0 Z，/bn中的

20、非证据变量集 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(NX) /对NX进行归一化,关于MCMC算法的补充说明： MCMC方法的一种常用的简单变体为： 吉布斯采样器（Gibbs sampler） MCMC是概率模型计算中的一种强有力的方法，目前已发展出很多变形，包括： （1）模拟退火算法 （2）随机可满足性(Stochastic satisfiability)算法,【课后习题2】,国家政策 （C）,学校政策 （U）,身体状况 差（B）,过劳死 （D）,工作压力 大（W）,已知：事件e