APP下载

基于l1惩罚加速的贝叶斯网贪婪搜索算法

2020-06-18徐平峰

长春工业大学学报 2020年2期

徐平峰, 杨 哲

(长春工业大学 数学与统计学院, 吉林 长春 130012)

0 引 言

贝叶斯网是由Pearl J[1]在上世纪80年代提出的一个概率模型,目前被广泛应用于因果推断、机器学习、心理学、社会学等领域[2]。贝叶斯网的结构是一个有向无圈图(DAG),可清晰直观地表示变量间的条件独立关系和因果关系。研究贝叶斯网非常重要的问题是从观测数据出发探求这些关系,称为结构学习或因果结构学习。结构学习方法大致分为三类[3]:

1)基于约束方法。该方法先进行条件独立关系检验,在条件独立关系约束条件下,寻找一个DAG。例如,PC算法先进行低阶条件独立性检验,然后逐步进行高阶条件独立性检验,逐步排除不可能的边,建立DAG的骨架,确定v-结构,最后尽可能地为边添加方向,找到DAG一个等价类[1]。Kalisch等[4]证明了PC算法在高维度情形中的相合性。Colombo[5]提出了PC-stable算法,消除了PC算法对于变量顺序的依赖。

2)基于评分搜索方法。为每个DAG赋一个评分,然后搜索一个得分最低的DAG或等价类。Chickering[6]提出了贪婪等价类搜索方法,通过逐步向前和向后搜索l0得分最小的等价类。Peters[7]在误差等方差的条件下,利用贪婪搜索求最小BIC评分的高斯贝叶斯网。

3)约束和搜索结合方法。该方法先进行一些条件独立性检验,然后在这些条件独立性关系约束下,搜索评分最低的DAG。例如,MMHC先采用基于约束的方法找到一个顶点可能的父顶点和子顶点,然后通过似然比来确定边的方向,进而确定DAG[8]。Han等[3]提出了邻域选择-禁忌搜索法。该方法第一步利用邻居选择方法找出一个顶点可能的邻居(本质上为学习高斯图模型的结构),然后利用禁忌搜索方法避免生成有向圈来选择DAG,并用该方法探索基因间的关系。……

登录APP查看全文