PDF《贝叶斯网络》

(一)连接是顺序的或者分支的,V在E中.

(二)连接是汇合的,则V和它的子节点都不在E中. d-可分 问题:a与b是否在c条件下独立? 路径:a到b的路径为a?e?f?b,考虑e,f的性 质

(一)f是分支连接类型.f未知,路径没有被 阻断.

(二)e是汇合连接类型的.e的后继节点c已知, 路径没有被阻断. 因此:a与b在c条件下不独立 d-可分 问题:a与b是否在f条件下独立? 路径:a到b的路径为a?e?f?b,考虑e,f的性 质

(一)f是分支连接类型.f已知,路径被阻断.

(二)e是汇合连接类型的.e的后继节点c未知, 路径被阻断. 因此:a与b在f条件下独立 例子的再考察 假设从仙林开车去鼓楼,发现交通很拥堵.你试图寻找交通差 的可能的解释. ?用d-可分化简 ? 对于第二项P(A|C),其是汇合连接.在T未知下,A和C相互独立.因此 P(A|C)=P(A). ? 对于第三项P(B|A,C),在B到A的路径上有T.T是汇合连接.在T未知下, 路径堵塞,B和A相互独立.因此P(B|A,C)=P(B|C). ? 对于第四项P(T|B,A,C),在T到B的路径上有C.如果C已知,路径阻断.T,B 在C已知情况下条件独立.因此P(T|B,A,C)=P(T|A,C). ? 对于第五项P(L|T,B,A,C),在L到B,C,T的路径上有A.如果A已知,路径阻 断.L分别与B,C,T在A已知情况下条件独立.因此P(L|T,B,A,C)=P(L|A). 例子的再考察 贝叶斯网络的构建 ?定义变量 ? 在领域专家指导下选取合适变量,或从中选择重要的因子. ?结构学习 ? 构建有向无环图. ? 能够很好的解释数据,反应变量间的依赖关系或者独立性. ? 不造成过拟合. ?参数学习 ? 学习节点的分布参数,即每条边对应的条件概率分布. 网络结构确定 ?选择一组刻画问题的随机变量{X1,X2,…,Xn} ?确定一个变量顺序a=<

X1,X2,…,Xn >

?参数学习从一个空图出发,按照顺序a逐个将变量加入ξ 中 ?假设当前需要加入的是变量Xi,此时ξ中已包含变量X1, X2,…,Xi-1 ? 在X1,X2,…,Xi-1选择一个尽可能小的子集π(Xi),使得假设 给定π(Xi), Xi与ξ中的其他变量条件独立 合理 ? 从π(Xi)中的每一个节点添加一条指向Xi的有向边 例子回顾-警报 ? 防盗警报响A可能是窃贼B引起的;

? 防盗警报响A也可能是地震E引起的;

? 窃贼和地震是相互独立的;

? 听到了警报响,邻居Mary会打电话;

? 听到了警报响,邻居John会打电话;

定义序为a1= 例子回顾-警报 ? 将B加入空图;

定义序为a1= 例子回顾-警报 ? 将B加入空图;

? 加入E.π(E)=Φ 定义序为a1= 例子回顾-警报 ? 将B加入空图;

? 加入E.π(E)=Φ ? 加入A.π(A)={B,E} 定义序为a1= 例子回顾-警报 ? 将B加入空图;

? 加入E.π(E)=Φ ? 加入A.π(A)={B,E} ? 加入M.π(M)={A} 定义序为a1= 例子回顾-警报 ? 将B加入空图;

? 加入E.π(E)=Φ ? 加入A.π(A)={B,E} ? 加入M.π(M)={A} ? 加入J.π(J)={A} 定义序为a1= 序的影响 不同的序产生不同的网络结构 定义序为a2=, 并假定变量出现的次序代表 因果关系 贝叶斯网络的结构学习 结构学习 结构学习 ? 在数据中推断变量之间的依赖关系,在可能的结构空间中搜 索最优结构 (基于专家的结构学习 vs 基于数据的结构学习) ? 基于搜索和评分的方法 ? 评分函数 ? 空间搜索策略 ? 基于评分函数,搜索与样本数据匹配程度最高的网络结构 ? 基于约束的方法 结构学习 ? 利用训练样本集,尽可能结合先验知识,确定和训练样本集 合匹配最好的贝叶斯网络结构 ? 对于有n个变量,可能的结构数目 ? 结构学习是一个典型的NP难问题 基于搜索和评分的方法 ? 利用评分函数,寻找与训练样本匹配最好的贝叶斯网络结构 ? 贪婪算法 ? 从一个特定的网络出发(如一个没有任何连接边的网络) ? 利用搜索算法对网络进行操作(增加边,删除边,反转边的方向) ? 根据评分函数对网络进行评分 ? 检查新的网络结构是否优于旧的,如是,则继续…… 搜索算子 评分函数和搜索策略 ? 评分函数 ? 最早是由Cooper and Herskovits等人在1992年提出的K2评分 函数,该评分函数假设观测到的数据是完备的,且服从多项 式分布 ? 基于K2评分函数,Heckerman等人在1995年提出了BD评分函 数,该评分函数假设观测数据服从Dirichlet分布 ? 搜索策略 ? 贪婪搜索、模拟退火、禁忌搜索、遗传算法等 贝叶斯网络的推理 贝叶斯信念网络推理 ? 因果推理(自顶向下的推理) ? 由原因推出结论,即根据一定的原因,推理出在该原因 情况下结果发生的概率. ? 诊断推理(自底向上的推理) ? 由结论推出原因,即根据产生的结果,利用贝叶斯网推 理算法,得出导致该结果的原因的概率. ? 支持推理 ? 对所发生的现象提供解释,目的是分析原因之间的相互 影响. 贝叶斯信念网络推理 贝叶斯网络推理 P(S)=0.4 P(? S)=0.6 P(C)=0.8 P(? C)=0.2 P(T | S, C)=0.35 P(T | ? S, C)=0.25 P(T | S, ? C)=0.1 P(T | ? S, ? C)=0.05 P(O |T )=0.6 P(O |? T )=0.15 P(A |T)=0.5 P(A |? T)=0.1 因果推理 ? 已知网络中的祖先节点而计算后代节点的条件概 率?假设已知某人吸烟(S), 计算他患气管炎(T)的概率 P(T|S) ? 由于T还有另一个因节点感冒(C), 对概率P(T|S)进 行扩展 P(T |S) = P(T, C |S) + P(T, ? C |S) 因果推理 ?扩展第一项 ?同理 P(T, C |S)........