k2,爬山.ppt

文档介绍：图分隔与变量独立
贝叶斯网是概率论和图论相结合的产物。在一个贝叶斯网中,一方面可以从概率论的角度谈论变量之间的依赖与独立,另一方面也可以从图论的角度谈论节点之间的连通与分隔。
d –分隔
u –分隔
d –分隔与u –分隔关系
结构学****br/>结构学****一般分为两步讨论,即模型选择( model selection)和模型优化( model optimization)。
模型选择是要回答用什么样的准则评价不同模型的优劣。
模型优化是要把最优的模型结构找出来。
基于搜索评分的方法:模型选择常用的评分准则:1、最优参数对数似然函数:基于似然函数的评分准则(使似然函数达到最大);2、 Cooper-Herskovits 评分:基于贝叶斯框架;3、BIC评分( Bayesian Information Criterion):基于大样本前提。
模型优化:评价网络结构的优劣可以用一个评分函数( Scoring Function)来度量,选择得分高的模型。
模型优化的常见方法(基于评分函数的可分解结构)( 1)穷举法:逐一计算每个结构的评分,选出得分最高的;( 2) K2算法:通过逐渐加边寻找评分高的模型 前提-参数的先验分布都为均匀分布 -事先确定变量的顺序及父节点数的上限
( 3)爬山法:从无边模型出发,利用搜索算子(加边、减边、转边)逐步对模型做局部修改(不能形成有向圈),考察模型评分是否变大。( 4)结构EM算法:当数据有缺失值时 基本思想:从初始模型结构和参数出发,首先进行数据修补,使之完善,然后模型及参数进行优化,依次迭代。
K2算法