綦小龙 高 阳 王 皓 宋 蓓 周春蕾 张友卫

1(南京大学计算机科学与技术系 南京 210046)2(伊犁师范学院电子与信息工程学院 新疆伊宁 835000)3 (江苏方天电力技术有限公司 南京 211102) (qxl_0712@sina.com)

贝叶斯网络是个有向无圈图，图中节点表示随机变量，节点间的弧表示变量之间的直接依赖关系.每个节点都拥有一个概率分布，根节点所附的是它的边缘分布，而非根节点所附的是条件概率分布[1].

近几十年来，从数据中自动学习贝叶斯网络结构受到研究者的普遍关注[2-7].一般来说，目前有2类结构学习方式[2,8]:1)基于约束的结构学习.该方法根据整体Markov性，使用统计假设检验对数据中的条件依赖和条件独立性关系进行检验，找到对依赖和独立关系最好解释的某个结构[9-10].2)基于优化的结构学习.该方式定义了测量模型对观测数据拟合程度的评分函数，如贝叶斯评分和最小描述长度(minimum description length, MDL)评分[2].结构学习的任务是找到一个最大化该评分函数的结构.这2种方法有各自的优缺点：基于约束的方式是有效的，但是它对个体独立性检验中的失败敏感[8-9]；基于优化的方法每次都考虑整个网络，因此对于个体错误并不敏感，但是搜索的结构空间包含超指数个结构.一般来说，该问题是NP-hard问题[8,11].

针对上述2种方法的主要挑战，学者们做了大量的研究.对于基于搜索-评分的学习方法，根据寻找到的解是全局最优还是局部最优提出了精确学习方式和近似学习方式：精确方式[3,6,12-13]的解是全局最优，但是由于其指数级的时空复杂性，这些方法只适合于数据集规模小的领域；……