基于演化序搜索的混合贝叶斯网络结构学习方法

Hybrid Bayesian Network Structure Learning via Evolutionary Order Search

贝叶斯网络是一种不确定性知识表示与推理的有效工具,学习其结构是利用这一工具进行推理的基础。现有的贝叶斯网络结构学习算法,在智能教育等应用场景中往往面临着难以权衡有效性与高效性的问题。一方面,评分搜索类方法能搜索到高质量的解,但面临着算法复杂度高的挑战。另一方面,混合类方法效率高,但所找到的解的质量不尽如人意。针对上述问题,提出了一种基于演化序搜索的混合贝叶斯网络结构学习方法(EvOS)。该方法首先通过约束类算法构建无向图骨架,然后利用演化算法搜索最优节点序,最后使用该节点序指导贪婪搜索得到贝叶斯网络结构。基于常用基准数据集以及教育知识结构发现任务,验证了所提方法的有效性与高效性。实验结果表明,所提方法相较于评分搜索类方法,能够在保持相仿精度的情况下最高加速百倍,且有效性显著高于混合类方法。

Bayesian network is an effective tool for uncertainty knowledge representation and reasoning.Learning and discovering its structure is the basis of reasoning via this tool.Existing Bayesian network structure learning algorithms often encounter the dilemma of balancing effectiveness and efficiency in real-world applications such as intelligent education.On the one hand,score-and-search methods can find out the high-quality solutions,but they suffer from the high algorithmic complexity.On the other hand,hybrid methods are highly efficient but the quality of the found solutions is not satisfactory.To address the above dilemma,this paper proposes an evolutionary order search based hybrid Bayesian network structure learning method called EvOS.First,the proposed EvOS constructs an undirected graph skeleton through a constraint algorithm,and then applies an evolutionary algorithm to search for the optimal node order,and finally uses the found node order to guide the greedy search so as to obtain the Bayesian network structure.This paper conducts the empirical study to verify the effectiveness and efficiency of the proposed EvOS in the commonly-used benchmark datasets as well as the real-world task of educational knowledge structure discovery.Experimental results show that,compared with the score-and-search methods,EvOS is able to achieve up to 100 times speedup while maintaining the similar accuracy,and its effectiveness is significantly better than that of the hybrid methods.