2009高级人工智能大纲日历及教案4网络

1、2022/8/61高级人工智能 第四章 贝叶斯网络 4.1概述 4.2贝叶斯概率基础4.3贝叶斯学习理论4.4简单贝叶斯学习模型4.5贝叶斯网络的建造 4.6贝叶斯潜在语义模型 内容提要2022/8/63贝叶斯网络是什么贝叶斯网络是用来表示变量间连接概率的图形模式，它提供了一种自然的表示因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变量，有向边表示变量间的依赖关系。贝叶斯方法正在以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性等成为当前数据挖掘众多方法中最为引人注目的焦点之一。2022/8/64贝叶斯网络是什么贝叶斯（Reverend Thom

2、as Bayes 1702-1761）学派奠基性的工作是贝叶斯的论文“关于几率性问题求解的评论”。或许是他自己感觉到它的学说还有不完善的地方，这一论文在他生前并没有发表，而是在他死后，由他的朋友发表的。著名的数学家拉普拉斯（Laplace P. S.）用贝叶斯的方法导出了重要的“相继律”，贝叶斯的方法和理论逐渐被人理解和重视起来。但由于当时贝叶斯方法在理论和实际应用中还存在很多不完善的地方，因而在十九世纪并未被普遍接受。2022/8/65贝叶斯网络是什么二十世纪初，意大利的菲纳特（B. de Finetti）以及英国的杰弗莱（Jeffreys H.）都对贝叶斯学派的理论作出重要的贡献。第二次世

3、界大战后，瓦尔德（Wald A.）提出了统计的决策理论，在这一理论中，贝叶斯解占有重要的地位；信息论的发展也对贝叶斯学派做出了新的贡献。1958年英国最悠久的统计杂志Biometrika全文重新刊登了贝叶斯的论文，20世纪50年代，以罗宾斯（Robbins H.）为代表，提出了经验贝叶斯方法和经典方法相结合，引起统计界的广泛注意，这一方法很快就显示出它的优点，成为很活跃的一个方向。2022/8/66贝叶斯网络是什么随着人工智能的发展，尤其是机器学习、数据挖掘等兴起，为贝叶斯理论的发展和应用提供了更为广阔的空间。贝叶斯理论的内涵也比以前有了很大的变化。80年代贝叶斯网络用于专家系统的知识表示，9

4、0年代进一步研究可学习的贝叶斯网络，用于数据采掘和机器学习。近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涵盖了人工智能的大部分领域，包括因果推理、不确定性知识表达、模式识别和聚类分析等。并且出现了专门研究贝叶斯理论的组织和学术刊物ISBA2022/8/67贝叶斯网络的应用领域辅助智能决策数据融合模式识别医疗诊断文本理解数据挖掘2022/8/68统计概率 统计概率:若在大量重复试验中，事件A发生的频率稳定地接近于一个固定的常数p，它表明事件A出现的可能性大小，则称此常数p为事件A发生的概率，记为P(A), 即 pP(A) 可见概率就是频率的稳定中心。任何事件A的概率为不大于1的非负实数，即

5、 0P(A)1 2022/8/69条件概率 条件概率:我们把事件B已经出现的条件下，事件A发生的概率记做为P(A|B)。并称之为在B出现的条件下A出现的条件概率，而称P(A)为无条件概率。 若事件A与B中的任一个出现，并不影响另一事件出现的概率，即当P(A)P(AB)或P(B)P(BA)时，则称A与B是相互独立的事件。 2022/8/610加法定理 两个不相容(互斥)事件之和的概率,等于两个事件概率之和,即 P(A+B) P(A)P(B) 若A、B为两任意事件，则：P(A+B)P(A)P(B)P(AB)2022/8/611乘法定理 设A、B为两个任意的非零事件，则其乘积的概率等于A(或B)的概

6、率与在A(或B)出现的条件下B(或A)出现的条件概率的乘积。 P(AB)P(A)P(B|A) 或 P(AB)P(B)P(A|B)2022/8/612贝叶斯网络定义图形描述概率描述ColdAllegoryCatSneezeScratch贝叶斯网络是表示变量间概率依赖关系的有向无环图，这里每个节点表示领域变量，每条边表示变量间的概率依赖关系，同时对每个节点都对应着一个条件概率分布表(CPT) ，指明了该变量与父节点之间概率依赖的数量关系。2022/8/613几点说明贝叶斯网络的特点：双向推理能力（预测和诊断）快速的调试和重构能力具有较强的概率统计基础用于人工智能和专家系统的不确定推理（优于早期的基

7、于规则的模式）。这种网络支持任何变量子集相对于另一子集的条件概率计算。贝叶斯网络是领域中变量关系的直接表示，而不是推理过程。网络中的方向表示变量间真正的因果关系而不是推理过程的信息流向。 因此在贝叶斯推理过程中，推理过程可以沿任何方向进行（预测、诊断、解释。从知识工程的角度讲，贝叶斯网络是用图形结构和数值参数来表示不确定性知识的知识系统，因而有时也称为因果网、信任网络和影响图。2022/8/614贝叶斯规则基于条件概率的定义p(Ai|E) 是在给定证据下的后验概率p(Ai) 是先验概率P(E|Ai) 是在给定Ai下的证据似然p(E) 是证据的预定义后验概率=iiiiiiii)p(AA|p(E)

8、p(AA|p(Ep(E)p(AA|p(EE)|p(A=p(B)A)p(A)|p(Bp(B)B)p(A,B)|p(AA1A2A3A4A5A6E2022/8/615贝叶斯网络的概率解释任何完整的概率模型必须具有表示（直接或间接）该领域变量联合分布的能力。完全的枚举需要指数级的规模（相对于领域变量个数）贝叶斯网络提供了这种联合概率分布的紧凑表示：分解联合分布为几个局部分布的乘积： 从公式可以看出，需要的参数个数随网络中节点个数呈线性增长，而联合分布的计算呈指数增长。网络中变量间独立性的指定是实现紧凑表示的关键。这种独立性关系在通过人类专家构造贝叶斯网中特别有效。 2022/8/616Industri

9、alProcessor Fault Diagnosis - by IntelAuxiliary Turbine Diagnosis - GEMS by GE Diagnosis of space shuttle propulsion systems - VISTA by NASA/RockwellSituation assessment for nuclear power plant - NRCMilitaryAuBmatic Target Recognition - MITREAuBnomous control of unmanned underwater vehicle - Lockhee

10、d MartinAssessment of IntentMedical DiagnosisInternal MedicinePathology diagnosis - Intellipath by Chapman & HallBreast Cancer Manager with IntellipathCommercialFinancial Market AnalysisInformation RetrievalSoftware troubleshooting and advice - Windows 95 & Office 97, and Software debugging - Americ

11、an Airlines SABRE online reservation system贝叶斯网络的应用2022/8/617贝叶斯网络来自医疗诊断的例子Visit To AsiaTuberculosisTuberculosisor CancerXRay ResultDyspneaBronchitisLung CancerSmokingPatient InformationMedical DifficultiesDiagnostic TestsMedical DifficultiesTub or CanTrueTrueFalseFalseBronchitisPresentAbsentPresent

12、AbsentPresent0.900.700.800.10Absent0.l00.300.200.90Dyspnea2022/8/618构建贝叶斯网BayesianNetworkBayesianNetworkBayesianNetworkProblemDomainProblemDomainProblemDomainExpertKnowledgeExpertKnowledgeTrainingDataTrainingDataProbabilityElicitorLearningAlgorithmLearningAlgorithm2022/8/619从数据中学习共轭分布族先验与后验属于同一分布族预先

13、给定一个似然分布形式对于变量定义在0-1之间的概率分布，存在一个离散的样本空间Beta 对应着 2 个似然状态多变量 Dirichlet 分布对应 2个以上的状态2022/8/6201)n(nm/n)m(1variance+-=nmmean=x)(1xm)(n(m)(n)n)m,|(xp1mn1mBeta-=-GGG先验分布的选取beta分布2022/8/621先验分布的选取多项Dirichlet分布1)m(m)m/m(1mstate i theof variancemmstate i theofmean .xxx)(m).(m)(m)m()m,.,m,m|(xpN1iiN1iiN1iiiit

14、hN1iiith1m1-m1mN21N1iiN21DirichletN21+-=GGGG=-=2022/8/622贝叶斯网络的结构学习基于搜索评分的方法: 初始化贝叶斯网络为孤立节点使用启发式方法为网络加边使用评分函数评测新的结构是否为更好 贝叶斯评分 基于熵的评分 最小描述长度（MDL）重复这个过程，直到找不到更好的结构 基于依赖分析的方法:通过使用条件独立性检验conditional independence (CI) 找到网络的依赖结构2022/8/623基于MDL的贝叶斯网结构学习计算每一点对之间的互信息：建立完全的无向图，图中的顶点是变量，边是变量之间的互信息建立最大权张成树根据一定

15、的节点序关系，设置边的方向2022/8/624基于CI的贝叶斯网络学习假定：节点序已知第一阶段 (Drafting)计算每对节点间的互信息，建立完整的无向图. 第二阶段 (Thickening)如果节点对不可能d-可分的话，把这一点对加入到边集中。第三阶段 (Thinning)检查边集中的每个点对，如果两个节点是d-可分的，那么移走这条边。2022/8/625贝叶斯网中的证据推理目的：通过联合概率分布公式，在给定的网络结构 和已知证据下，计算某一事件的发生的概率。E网络证据查询推理贝叶斯推理可以在反复使用贝叶斯规则而获得=p(B)A)p(A)|p(Bp(B)B)p(A,B)|p(A2022/8

16、/626推理方法概述精确推理 网络的拓扑结构是推理复杂性的主要原因； 当前的一些精确算法是有效地，能够解决现实中的大部分问题 由于对知识的认知程度，精确推理还存在一些问题近似推理 证据的低似然性和函数关系 是近似推理中复杂性的主要原因NP Hard2022/8/627影响推理的因素网络结构的特征 网络的拓扑结构 网络的大小 网络中变量的类型（离散、连续） 变量的分布熵相关查询的特征任务查询类型 （批处理、异步执行）可用的计算资源（嵌入式系统、并行处理）相关证据的特征证据的特征2022/8/628查询的任务类型预测 对给定的模型，将要发生什么给定证据下的后验计算所有的边界后验指定的边界后验指定的

17、联合条件查询最可能的假设 一个最可能的 n 个最可能的决策策略2022/8/629继续前面的医疗诊断例子贝叶斯推理中非条件分布和边界分布是常见的查询模式一个节点的边界分布也称为该节点的信任函数2022/8/630推理过程中的信任传播2022/8/631推理算法精确推理联合概率计算Nave Bayesian图约简算法Polytree算法 近似推理前向模拟推理随机模拟推理 The algorithms purpose is “ fusing and propagating the impactof new evidence and beliefs through Bayesian networks

18、 so that each proposition eventually will be assigned a certainty measure consistent with the axioms of probability theory.” (Pearl, 1988, p 143)2022/8/632精确推理计算联合概率任何查询都可以通过联合概率回答步骤：计算联合概率 P(AB)=P(A)*P(B|A)边界化不在查询中的变量 P(B)=AP(AB)效率低AB2022/8/633精确推理Nave Bayesian结构简单只有两层结构推理复杂性与网络节点个数呈线性关系2022/8/634H

19、ow a naive Bayes classifies?Bayes Decision rule : Find the c that maximizes (1)(1)Given an instance vector Calculate for all class c2022/8/635How to train a naive Bayes?(discrete case)Suppose Xj is a discrete variable whose value is xj then usually we can estimateWhere is # of the training examples

20、belonging to class c and is # of training examples belonging to class c and having their Xj=xj; j , are “prior parameters.”from training data. (Dirichlet priors;Cooper,1999)2022/8/636How to train a naive Bayes?continuous case Parameter estimationAssuming is Gaussian (Duda & Hart 1973) Discretization

21、Equal width interval binningBin log l (Spector, 1990)1-R (Holts, 1994)Entropy-based (Fayyad & Irani, 1993)2022/8/637图约简算法一般原理基本观点任何概率查询可以表示成网络的子网，推理的目的是把网络分解成几个子网三个基本操作拟转弧操作（Arc Reversal）贝叶斯公式孤寡点移出(Barren node removal)求和公式值节点归并(Merge with Value node)期望最大化2022/8/638约简算法拟转弧操作X1X3X2X1X3X2X1X3X2X1X3X2p(

22、x1, x2, x3) = p(x3 | x1) p(x2 | x1) p(x1) p(x1, x2, x3) = p(x3 | x2, x1) p(x2) p( x1)p(x1, x2, x3) = p(x3 | x1) p(x2 , x1) = p(x3 | x1) p(x1 | x2) p( x2)p(x1, x2, x3) = p(x3, x2 | x1) p( x1) = p(x2 | x3, x1) p(x3 | x1) p( x1)2022/8/639约简算法孤寡点移出孤寡点没有孩子的节点2022/8/640约简算法值节点归并值节点证据节点或赋值节点2022/8/641Polyt

23、ree算法介绍该算法由Pearl 于1982年首次提出基本观点 计算边界后验的消息传递机制 Lambda 算子：消息向上传向父亲 pi 算子：消息向下传向孩子2022/8/642Polytree算法单连通网定义： 在任何两个节点之间存在且仅存在一条路径（忽略方向）XMultiple parents and/ormultiple children2022/8/643单连通网的表示X 表示 m维随机向量; x 表示随机向量可能的取值e 表示m维向量的一个取值My|x 是条件概率p(y|x)的似然矩阵p(y1|x1) p(y2|x1) . . . p(yn|x1) p(y1|x2) p(y2|x2)

24、 . . . p(yn|x2) . . . . . . . . . p(y1|xm) p(y2|xm) . . . p(yn|xm)y= xBel (x) = p(x|e) 表示随机向量的后验；f(x) g(x) 表示向量的叉积f(x) g(x)表示向量的点积 是标准化常量2022/8/644概率的双向传播e+e-XYZ(e+)(x)(y)(y)(z)(e-)每个节点向儿子节点发送 pi 消息 向父节点发送 lambda消息Bel(Y) = p(y|e+, e-) = (y)T (y)其中(y) = p(y|e+), 先验证据(y) = p(e-|y), 似然证据(y) = x p(y|x,

25、e+) p(x| e+) = x p(y|x) (x) = (x) My|x(y) = z p(e-|y, z) p(z| y) = z p(e-|z) p(z| y) = z (z) p(z| y) = Mz|y (z)2022/8/645传播算法对每个节点引入证据时，产生:沿着弧的方向传播一组 “p” 消息逆着弧的方向传播一组 “l” 消息对接收 “p” or “l” 消息的每个节点:节点修正它的“p”或 “l”，并发送到网络中使用修正的“p”或 “l” ，更改结点的信任函数 BELTBEL(t)p(t) l(t)UBEL(t)p(t) l(t)XBEL(t)p(t) l(t)YBEL(t

26、)p(t) l(t)ZBEL(t)p(t) l(t)Mu|tMx|uMy|xMz|y2022/8/646实例描述p(A1) = 0.9p(A2) = 0.1M B|A = M C|B = A1A2B1B2C1C2C3ABC.8 .2.1 .9.5 .4 .1.1 .3 .6ChDiA1A2C1C2C3B1B22022/8/647实例算子设定ABC(1) 初始化 lambda 算子为单位向量; Bel(A) = (A) (A)(A) Bel(A) (A)A1 0.9 0.9 1.0A2 0.1 0.1 1.0(2) (B) = (A) MB|A; Bel(B) = (B) (B)(B) Bel(

27、B) (B)B1 0.73 0.73 1.0B2 0.27 0.27 1.0(3) (C) = (B) MC|B; Bel(C) = (C) (C)(C) Bel(C) (C)C1 0.39 0.40 1.0C2 0.35 0.36 1.0C3 0.24 0.24 1.02022/8/648实例第一次传播tTRT=05l(). 1 .6 t=0(lR)=.8 .2pt = 1(A) = (IR)(A) Bel(A) (A)A1 0.8 0.8 1.0A2 0.2 0.2 1.0 (B) Bel(B) (B)B1 0.73 0.73 1.0B2 0.27 0.27 1.0(C) Bel(C) (C)C1 0.39 0.3 0.5C2 0.35