7.2贝叶斯网络结构学习

贝叶斯网络结构学习主讲人：李侃

贝叶斯网络结构学习从给定的数据集中学出贝叶斯网络结构，即各结点之间的依赖关系；只有确定了结构才能学习网络参数，即表示各结点之间依赖性的条件概率。根据训练数据是否存在缺失

完整数据结构学习

缺失数据结构学习贝叶斯网络结构学习网络结构学习基于搜索评分的方法基于约束的方法修复数据集的方法近似计算的方法

贝叶斯网络结构学习从给定的数据集中学出贝叶斯网络结构，即各结点之间的依赖关系；只有确定了结构才能学习网络参数，即表示各结点之间依赖性的条件概率。根据训练数据是否存在缺失

完整数据结构学习

缺失数据结构学习贝叶斯网络结构学习网络结构学习基于搜索评分的方法基于约束的方法修复数据集的方法近似计算的方法基于搜索评分的方法贝叶斯网络结构学习问题看成是优化问题，通过给定结构的评分函数，利用搜索算法，去寻找评分最优的网络结构。贝叶斯网络结构学习—完整数据结构学习关键点确定合适的搜索策略确定评分函数

基于搜索评分的方法

基于搜索评分的方法给定训练数据D及一个可能的结构G，如何去计算其评分f(G，D)。如果评分函数能够满足一些特性如一致性，则其评分效果更佳。评分函数

基于贝叶斯的评分基于信息论的评分基于搜索评分的方法基于贝叶斯的评分函数

基于搜索评分的方法基于贝叶斯的评分函数

基于搜索评分的方法基于贝叶斯的评分函数

基于搜索评分的方法BD（BayesianDirichlet）评分

基于搜索评分的方法基于贝叶斯的评分函数上式两边同时取对数，则BD(BayesianDirichlet)评分：基于搜索评分的方法

BD（BayesianDirichlet）评分基于贝叶斯的评分函数

基于搜索评分的方法K2评分基于贝叶斯的评分函数

基于搜索评分的方法BDeu评分基于贝叶斯的评分函数基于信息论的评分函数基于搜索评分的方法

基本思想：将训练数据进行压缩，利用最小描述长度MDL(minimumdescriptionlength)来挖掘其中的规则。

基于搜索评分的方法基于信息论的评分函数LL

(log-likelihood)评分函数

基于搜索评分的方法基于信息论的评分函数AIC(akaikeinformationcriterion)评分函数

基于搜索评分的方法基于信息论的评分函数BIC(bayesianinformationcriterion)评分函数

基于搜索评分的方法基于信息论的评分函数MDL评分函数

基于搜索评分的方法基于信息论的评分函数两种方法的比较基于搜索评分的方法能够更好地区分训练样本较大的贝叶斯网络结构。适用小样本的训练数据，尤其是BIC评分函数所学习到的结构效果更好。基于贝叶斯的评分函数基于信息论的评分函数搜寻最优结构定义评分函数寻找最高评价值的搜索最优问题采用启发式或元启发式搜索方法基于搜索评分的方法学习贝叶斯网络结构是NP一难问题搜索算法K2算法爬山算法GES算法基于进化计算的方法基于搜索评分的方法基于搜索评分的方法K2算法搜索算法基于贪婪搜索的结构学习算法采用评分来衡量结构的优劣性，并利用结点序以及正整数来限制搜索空间的大小

基于搜索评分的方法爬山（hillclimbing）算法搜索算法加边、减边以及删除边的局部操作，

根据评分确定是否选择该操作。通过贪婪选择来判断是否对模型结构进行更新。搜索过程简单，但无法保证搜索到的结构一定是最优的。GES

(greedyequivalentsearch)算法从一个空图出发，采用两个不同的搜索阶段来寻找评分最高的结构。采用贪心前向搜索法（GFS）来不断地在空图中加边，直至评分值无法提高为止；利用贪心反向搜索法（greedybackwardsearch，GBS）在图中不断地删除边，直至评分值不能提高为止。基于搜索评分的方法搜索算法基于约束的方法通过统计独立性测试来学习结点间的独立性和相关性，并根据独立性或相关性构建出相应的有向无环图结构。贝叶斯网络结构学习—完整数据结构学习

PC算法由Peter和Clark提出并以他们名字命名的贝叶斯网络结构学习方法基本思想：通过寻找结点

X的父结点和子结点集合

pc(X)，以及寻找v-结构来学习DAG结构。基于约束的方法基于约束的方法—PC算法从一个完全连接的无向图出发，以Z=ø作为第一次CI测试来限制潜在的邻居结点集。对于每个结点，首先考虑邻居结点集为l的子集结点来判断是否条件独立，然后结点集为2，不断增加结点集数目直至收敛。对于v-结构，通过检查将vi和vj分离的结点集合，不需要额外的CI测试来判断是否存在v-结构TPDA算法制定（drafting）增厚（thickening）变薄（thinning）基于约束的方法从一个空图出发，通过简单的互信息测试来产生一组初始边，从而形成一个单连接的无环图通过CI测试检查每对结点间是否能被有向分离，如果不能，则为其添加边对图中每条边进行检查，通过判断其对应的结点对之间是否存在条件独立，来决定是否移除边。基于三层独立性测试的结构学习方法两种结构学习方法的局限

基于约束的方法贝叶斯网络结构学习—完整数据对于数据的要求性较高，需要训练数据无噪声且真实，训练数据量需要足够大基于搜索评分的方法

复杂度高，当结点较多时，会使搜索空间巨大，从庞大搜索空间中搜索最优结构耗时混合约束和搜索评分的结构学习方法思想：通过独立性测试来降低搜索空间的大小，再利用搜索评分的方法来寻找最优的网络结构。贝叶斯网络结构学习—完整数据MMHC(max-minhillclimbing)算法：将局部学习、CI测试以及搜索评分方法进行融合，通过采用独立性测试来学习出结构的框架，然后采用搜索评分的方式来确定网络中的边以及边的方向。

贝叶斯网络结构学习从给定的数据集中学出贝叶斯网络结构，即各结点之间的依赖关系；只有确定了结构才能学习网络参数，即表示各结点之间依赖性的条件概率。根据训练数据是否存在缺失

完整数据结构学习

缺失数据结构学习贝叶斯网络结构学习网络结构学习基于搜索评分的方法基于约束的方法修复数据集的方法近似计算的方法缺失数据条件下学习网络结构所有评分函数无法分解成只与局部结构相关的因式需要执行非线性的优化过程为评判当前网络结构必须评估其所有的“邻居”贝叶斯网络结构学习缺失数据条件