贝叶斯网络结构学习的CMIHC算法

CMIHC Algorithm for Bayesian Network Structure Learning

贝叶斯网络源于对人工智能领域不确定问题的研究,是进行不确定问题推理和数据分析的重要工具。自贝叶斯网络结构学习诞生以来,已有众多成熟的结构学习算法,包括基于依赖分析的方法、基于评分搜索的方法和混合搜索的方法。其中利用信息论进行结构修剪已成为常用手段,但条件互信息中条件集的选取并没有统一标准,导致网络结构的修剪不一致。爬山算法利用3种搜索算子对网络结构进行局部更新,通过评分函数得到最优结构。结合信息论和爬山算法思想,提出一种新的结构学习算法——CMIHC(Conditional Mutual Information Hill Climbing)算法。该算法利用互信息和创建的条件集修剪初始连通图,对其进行定向,进而得到初始网络结构,结合评分函数和爬山算法的贪婪搜索策略得到最优网络结构。通过实验分析,在精度和效率上,CMIHC算法效果优于其他对比算法。

Bayesian network originates from the research on uncertain problems in the field of artificial intelligence.It is an important tool for reasoning and data analysis of uncertain problems.Since the birth of Bayesian network structure learning,there have been many mature structure learning algorithms,including dependency analysis based method,score based search method and hybrid search method.Among them,structure pruning by information theory has become a common method,but there is no unified standard for the selection of condition set in conditional mutual information,resulting in inconsistent pruning of network structure.The hill climbing algorithm uses three search operators to update the network structure locally,and obtains the optimal structure through the scoring function.Combined with the idea of information theory and hill climbing algorithm,a new structure learning algorithm-conditional mutual information hill climbing(CMIHC)algorithm is proposed.The proposed algorithm prunes the initial connected graph by using mutual information and the created condition set,and orients it to obtain the initial network structure.Combined with the scoring function and the greedy search strategy of hill climbing algorithm,the optimal network structure is obtained.Experimental analysis shows that CMIHC algorithm is superior to other comparison algorithms in accuracy and efficiency.