Abstract: 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.

Key words: Bayesian network, Structure learning, Conditional mutual information, Hill climbing algorithm, CMIHC algorithm