(40-9)
贝叶斯网络中的独立关系
•利用变量间的条件独立关系可以将联合概率分布分解成多个复杂度较低的 概率分布，从而降低模型复杂度，提高推理效率。 •例如：由链规则可以把联合概率分布P(A, B, E, J, M)改写为： 独立参数：1+2+4+8+16=31
– E与B相互独立， 即P(E|B)=P(E) – 给定A时，J与B和E相互独立， 即P(J|B, E, A)=P(J|A) – 给定A时，M与J、B和E都相互独立，即P(M|J, A, B, E)=P(M|A)
– 条件独立 – 因果影响独立 – 环境独立
(40-11)
贝叶斯网络中的独立关系
(一)条件独立
•贝叶斯网络的网络结构表达节点间的条件独立关系。 •三种局部结构
– 顺连 (serial connection) – 分连(diverging connection) – 汇连(converging connection)
(40-15)
贝叶斯网络中的独立关系
(四)环境独立(context independence)
•环境独立是指在特定环境下才成立的条件独立关系。 •一个环境是一组变量及其取值的组合。设环境中涉及变量的集合用 C表示， C的一种取值用c表示，则C=c表示一个环境。 •定义5.8 设X，Y，Z，C是4个两两交空的变量集合，如果 P(X, Y, Z, C=c)>0 且 P(X|Y, Z, C=c)= P(X| Z, C=c) 则称X, Y在环境C=c下关于Z条件独立。若Z为空，则称X, Y在环境C=c下 环境独立。
得到联合概率边缘化分布：
再按照条件概率定义，得到
(40-8)
不确定性推理与联合概率分布
•问题：
•随着变量数目增加，联合概率分布的参数个数成指数级增长。
– n个二值随机变量的联合概率分布包含2n-1个独立参数。
•当变量很多时，联合概率的获取、存储和运算都十分困难。 •在六、七十年代，大多数学者认为概率论不适合于解决人工 智能中的不确定性问题。
•两类评分标准：
① 基于编码理论
– 最小描述长度(Minimum Description Length，MDL) – 贝叶斯信息标准(Bayesian Information Criterion，BIC)
②源于贝叶斯统计
– BDe评分方法
•最小描述长度函数MDL
MDL原理认为最优模型是总描述长度最短的模型。 贝叶斯网络B=<G,θ>描述每一个样本Di的概率，按编码策略对每个样本Di进行 编码。 网络结构G要使得网络描述长度和数据D的编码长度之和最小， 必须在网络结构的复杂性与网络结构的准确性之间确定平衡点。
(40-13)
贝叶斯网络中的独立关系
•定义5.2 X，Y，E是三个互不相交的节点集，说E有向分离X和Y，当且仅 当X和Y之间的通路都被E所阻塞。 •推论5.3 设X和Y为贝叶斯网络中的两个变量。Z为贝叶斯网络中一个不包 含X和Y的节点集合。如果Z分离X和Y，则X和Y在给定Z的条件下相互独立。
•推论5.4 一个节点的马尔科夫覆盖包括该节点的父节点，子节点，以及子 节点的父节点。
•推论5.5 在一个贝叶斯网中，给定变量X的马尔可夫覆盖时，则X条件独立 于网络中所有其它变量。 •推论5.6 在一个贝叶斯网中，给定变量X的父节点Pa(X)，则X条件独立于 它的所有非后代节点。
(40-14)
贝叶斯网络中的独立关系
(三)因果影响独立(causal independence)
因果影响独立指的是多个原因独立地影响同一个结果。
第5章
贝叶斯网络
贝叶斯网络
贝叶斯网络(Bayesian Networks)结合图论和统 计学方面的知识，提供了一种自然表达因果信息的方 法，用于表达随机变量之间复杂的概率不确定性，发 现数据间的潜在关系。 本章介绍如下几个方面的内 容： •贝叶斯网络基本概念 •不确定性推理与联合概率分布 •贝叶斯网络中的独立关系 •贝叶斯网络学习 •贝叶斯网络分类器
(40-6)
不确定性推理与联合概率分布
•5个随机变量：
– 盗窃(Burgle，B) – 地震(Earth Quake，E) – 警铃响(Alarm，A) 接到John的电话(John Call，J) 接到Marry的电话(Marry Call，M)
(40-7)
不确定性推理与联合概率分布
•从联合概率P(A, B, E, J, M)出发，先计算边缘分布 （5.4）
(40-16)
贝叶斯网络学习
贝叶斯网络由结构(有向无环图)和参数(条件概率)两部分构成，分别用 于定性与定量地描述依赖关系。网络中的有向边具有因果语义。 贝叶斯网络学习的核心问题是结构学习，包括结构和数据集参数。有 时网络学习和结构学习不加区分。
(一)结构学习
目标是基于训练数据找到数据匹配程度最高的贝叶斯网络结构。 无约束贝叶斯网络可归结为在给定数据集 T 后，寻找具有极大似然 P(G|T)的结构G的问题。
贝叶斯网络学习
•度量公式如下：
•先验概率分布的计算依据先验知识。 •优缺点：
– 使用先验知识，其对训练数据集的依赖性比MDL测度要低 – 没有明确地包含结构复杂性指标，会倾向于选择较复杂的网络结构。
(40-22)
贝叶斯网络学习
•(二)搜索算法
搜索算法在某个评分函数下搜索分值最高的网络结构。 •当数据完备时，搜索算法借助评分函数的“可分解性”来提高搜索效率。 •所谓评分函数可分解是指：G的分值可以通过其各个家族的分值之和求得。
•MDL优缺点：
•目标是结构简单、参数较少的稀疏网络 •具有一致性 •没有用到先验知识 •对两个具有等价性的结构，不能保证得到相同MDL测度值。
(40-20)
贝叶斯网络学习
•BDe函数
– Heckerman等扩展BD(Bayesian Dirichlet)度量，提出BDe函数。 – 定义一个离散变量G表示未知的网络结构，其取值范围是所有可能网络结构； – 估计G的先验概率P(G)； – 计算网络结构后验概率P(G|D)和参数后验概率P(θ|D, G)，并计算目标期望值。
– 家族即一个节点和其所有父节点始，对当前结构进行某些的修改； – 计算修改后结构的分值，根据分值决定是否更新结构。
•定义5.9. 如果给定某一问题领域的各个变量，用一个结点表示其中的一个 变量，由任意两个结点间的无向边连接构成的图模型，称为完全潜在图。 •定义5.10. 如果变量X、Y 和变量集Z之间存在以下关系： 即在变量集Z已知的条件下，变量Y 的状态和概率不会造成对变量X的影响， 称为在给定变量集Z的前提下，X条件独立于Y。
•定义5.7 节点Y的各个父亲节点X1,X2,…,Xn对于Y是因果影响独立的，如果 对应于X1,X2,…,Xn存在和Y有相同取值范围的随机变量 ，并且 下面两个条件成立： 1. 对任意i，依赖于Xi，在Xi已知条件下，独立于所有其它的和 (j≠i)； 2. 在ΩY上存在一个满足交换律和结合律的二元算子*，使得
(40-12)
贝叶斯网络中的独立关系
(二)有向分离和条件独立
•贝叶斯网络中任意两个节点之间的条件独立关系可由有向分离来判断。 •定义5.1 设E为节点集合，X和Y是不在E中的两个节点。X和Y之间的通路 α如果满足下面条件之一，则称α被E所阻塞 1. α上存在一个顺连节点Z，且Z在E中； 2. α上存在一个分连节点Z，且Z在E中； 3. α上存在一个汇连节点Z，且Z和Z的后代节点均不在E中。
(40-19)
贝叶斯网络学习
•贪婪搜索:
令E表示所有可能添加到网络中的候选边集合， 表示边e加入到网 络中后评分函数的变化。 •步骤1. 选择一个网络。 •步骤2. 选择集合E中的边e，使得 ，如果 找不到满足条件的边，则停止，否则继续。 •步骤3. 加入边e到网络中，并从集合E中删除e，转步骤2。
(40-3)
贝叶斯网络基本概念
•给定一个随机变量集X={X1,X2,…,Xn}，其中Xi是一个m维向量。贝叶斯网 络说明X上的联合条件概率分布。定义为 •G是有向无环图，节点分别对应于有限集X中的随机变量X1,X2,…,Xn ，每 条弧代表一个函数依赖关系。 •如果有一条由变量Y到X的弧，则Y是X的双亲(直接前驱)，X是Y的后继。 Xi的所有双亲变量用集合Pa (Xi)表示。 •一旦给定双亲，图G中的每个变量就与其非后继节点相独立。 • 代表用于量化网络的一组参数。对于Xi的取值xi，参数 •贝叶斯网络表明变量集合X上的联合条件概率分布：
(40-18)
贝叶斯网络学习
•网络结构的MDL测度由3部分组成：
1. 网络结构的描述长度：保存网络结构G，要记录各节点的父节点的编号。 贝叶斯网络包含n个节点， |πXi|为节点Xi的父节点数目。网络结构的描述 长度是： 2. 参数的描述长度：为描述局部条件概率表，须存贮每个节点的条件概率 表的所有参数。Xi的条件概率表需要存贮|πXi|(|Xi|-1)个参数，|Xi|表示变量 Xi所有可能状态的数目。存储每个参数，需要logn/2二进制位，其中N是训 练样本的数目。 3. 数据集合的描述长度：将数据D中每个样本Di建立Huffman编码，每个 码字的确切长度依赖于P(Di|G,θ)，其概率越大，编码长度越小，概率越小， 编码长度越大。Di的二进制编码长度近似等于log(1/ P(Di|G,θ))。因而数据 集合的描述长度为： •其中H(Xi|πXi)为条件熵。 •综上，结构MDL测度为：
(40-2)
引言
• 贝叶斯网络将图论和统计学相结合，用于表达随机变量之间 复杂的概率不确定性，发现数据间的潜在关系。 • 优点： (1)知识表示形式更加直观。 (2) 对于问题域的建模，当条件或行为等发生变化时，不需要 修正模型。 (3)以图形化表示随机变量间的联合概率，处理不确定性信息。 (4)没有确定的输入或输出结点，结点之间相互影响，可以用 于估计预测。 (5) 将知识表示与知识推理结合统一为整体。 • 1988年，Pearl建立了贝叶斯网基础理论体系，将概率理论 和图论有机结合，用一种紧凑的形式表示联合概率分布。