《浙江大学研究生人工智能引论课件课件教学内容》由会员分享，可在线阅读，更多相关《浙江大学研究生人工智能引论课件课件教学内容（46页珍藏版）》请在金锄头文库上搜索。
1、浙江大学研究生人工智能引论课件,徐从富(Congfu Xu) PhD, Associate Professor Email: Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. China September 11, 2005第一稿 Oct. 8, 2006第二次修改稿,第七讲 贝叶斯网络初步(Chapter7 Bayesian Networks ),内容提纲,何谓贝叶斯网络？ 贝叶斯网络的语义 条件分布的有效表达 贝叶斯网络中
2、的精确推理 贝叶斯网络中的近似推理 课后习题、编程实现及研读论文,7.1 何谓贝叶斯网络？,贝叶斯网络的由来 贝叶斯网络的定义 贝叶斯网络的别名 独立和条件独立 贝叶斯网络示例,“Above all else, guard your heart, for it is the wellspring of life.” from Proverbs 4:23 NIV,贝叶斯网络的由来,全联合概率计算复杂性十分巨大 朴素贝叶斯太过简单 现实需要一种自然、有效的方式来捕捉和推理不确定性知识 变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目,C. 贝叶斯网络的别名,信念网(Bel
3、ief Network) 概率网络(Probability Network) 因果网络(Causal Network) 知识图(Knowledge Map) 图模型(Graphical Model)或概率图模型(PGM) 决策网络(Decision Network) 影响图(Influence Diagram),D. 独立和条件独立,Weather,Cavity,Catch,Toothache,Weather和其它3个变量相互独立 给定Cavity后，Toothache和Catch条件独立,E. 贝叶斯网络示例,Burglary,Earthquake,MaryCalls,JohnCalls,A
4、larm,7.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.90.70.0010.9990.998 = 0.00062 = 0.062%,贝叶斯网络的特性：,作为对域的一种完备而
5、无冗余的表示，贝叶斯网络比全联合概率分布紧凑得多 BN的紧凑性是局部结构化(Locally structured, 也称稀疏, Sparse)系统一个非常普遍特性的实例 BN中每个节点只与数量有限的其它节点发生直接的相互作用 假设节点数n=30, 每节点有5个父节点，则BN需30 x25=960个数据，而全联合概率分布需要230= 10亿个！,贝叶斯网络的构造原则：,首先，添加“根本原因”节点 然后，加入受它们直接影响的变量 依次类推，直到叶节点，即对其它变量没有直接因果影响的节点 两节点间的有向边的取舍原则：更高精度概率的重要性与指定额外信息的代价的折衷 “因果模型”比“诊断模型”需要更少的
6、数据，且这些数据也更容易得到,贝叶斯网络中的条件独立关系：,给定父节点，一个节点与它的非后代节点是条件独立的 给定一个节点的父节点、子节点以及子节点的父节点马尔可夫覆盖(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 NIV,U1,Um,X,Z1j,Znj,Y1,Yn,【说明】： 给定节点X的父节点U1. Um，节点X与它的非后代节点（即Zij）是条件独立的。,
7、U1,Um,X,Z1j,Znj,Y1,Yn,【说明】： 给定马尔可夫覆盖（两圆圈之间的区域），节点X和网络中所有其它节点都是条件独立的。,7.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; 连续随机变量：
8、Harvest, 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+)/ ,7.4 贝叶斯网络中的精确推理,变量分类： 证据变量集E 特定事件e， 查询变量X 非证据变量集 Y隐变量（Hidden variabl
9、e） 全部变量的集合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,
10、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),+,+,+,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)的自顶向下
11、的计算过程,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|
12、b,e) 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.00
13、1 0.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章1
14、4.4.2节,（3）Clustering算法（Joint Tree算法） 单独节点联合起来形成Cluster节点，使得BN结构成为一棵多树（Polytree） 多树单连通网络，即任何两节点间至多只有一条路径相连 概率推理包含命题逻辑推理作为其特殊情况，故BN的推理是一个NP问题 在多连通的BN结构中，及时每个节点的父节点个数有固定的界限，在最坏的情况下，变量消元算法仍可能具有指数级时间和空间复杂度,多连通网络及其CPT：,Cloudy,Rain,Wet Grass,Sprinkler,等价的联合树及其CPT：,Cloudy,Spr+Rain,Wet Grass,7.5 贝叶斯网络的近似推理,大
15、规模多连通BN的精确推理是不可操作的， 必须通过近似推理来解决。 后验概率计算的主要采样方法 直接采样方法 马尔可夫链蒙特卡罗（MCMC）方法 变分法(Variational method) 环传播(Loopy propagation)方法,直接采样方法： 直接采样算法 拒绝采样(Rejection sampling)算法 似然加权(Likelihood weighting)算法 上述方法的详细步骤请参见： 人工智能：一种现代方法第14章14.5.1节 Berkeley大学Russell等人制作的PPT http:/aima.cs.berkeley.edu/,马尔可夫链蒙特卡罗（MCMC）算法思想： 对前一个事件行随机改变而生成事件样本 BN为每个变量指定了一个特定的当前状态 下一个状态是通过对某个非证据变量行采样来产生，取决于的马尔可夫覆盖中的变量当前值 MCMC方法可视为：在状态空间中所有可能的完整赋值空间的随机走动每次改变一个变量，但是证据变量的值固定不变。,MCMC算法执行过程示例：,Cloudy,Rain,Wet Grass,Sprinkler,【要求】：查询P(Rain | Sprinkler = true, WetGrass = true)的概率,MCMC算法执行步骤： 证据变量Sprinkler, WetGrass固
