|
|
|
| A Dependency Analysis Based Algorithm for Learning Bayesian Networks |
| HU XueGang, HU ChunLing |
| School of Computer and Information, Hefei University of Technology, Hefei 230009 |
|
|
|
|
Abstract Bayesian network is a powerful knowledge representation and reasoning tool under uncertain conditions. Current algorithms for learning Bayesian networks structures are inefficient to a certain degree. Therefore,an efficient and reliable algorithm, ISOR, is proposed in this paper. Firstly, all the potential edges of the underlying network are produced by the maximum weight spanning tree algorithm and heuristic cut set searching algorithm. Then, methods based on identifying colliders and scoring search methods are integrated to orient all the edges in the network. Finally, redundant edges in the network are removed. Compared with other current algorithms based on dependency analysis, the proposed algorithm greatly reduces the number and the order of conditional independence tests. Algorithm analysis and experimental results on Alarm network show algorithm ISOR has good performance.
|
|
Received: 21 September 2005
|
|
|
|
|
|
[1] Chickering D M, Herkerman D, Meek C. Large-Sample Learning of Bayesian Networks is NP-Hard. Journal of Machine Learning Research, 2004, 5: 1287-1330
[2] Cooper G F, Herskovits E. A Bayesian Method for the Induction of Probabilistic Networks from Data. Machine Learning, 1992, 9(4): 309-347
[3] Cheng J, Greiner R, Kelly J. Learning Bayesian Networks from Data: An Efficient Information- Theory Based Approach. Artificial Intelligence, 2002, 137(1-2): 43-90
[4] Verma T, Pearl J. An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation. In: Dubois D, Wellman M P, et al, eds. Proc of the 8th Conference on Uncertainty in Artificial Intelligence. Stanford, USA: Morgan Kaufmann, 1992, 323-330
[5] Sprites P, Glymour C, Scheines R. Causality from Probability. In: Mckee G, ed. Evolving Knowledge in Natural and Artificial Intelligence. London, UK: Pitman, 1990,181-199
[6] Sprites P, Glymour C, Scheines R. An Algorithm for Fast Recovery of Sparse Causal Graphs. Social Science Computer Review, 1991, 9(1): 62-72
[7] Peng H C, Ding C. Structure Search and Stability Enhancement of Bayesian Networks. In: Proc of the 3rd IEEE International Conference on Data Mining. Melbourne, USA, 2003, 621-624
[8] Yao H L, Wang H, Hu X G, Wang R G. A Refinement Algorithm of Bayesian Network Structures Based on Genetic Algorithm and Minimum Description Length Principle. Journal of Nanjing University (Natural Sciences), 2002, 38(2): 23-27 (in Chinese)
(姚宏亮,王 浩,胡学钢,汪荣贵. 基于遗传算法和MDL原则的贝叶斯网络结构优化算法. 南京大学学报(自然科学版), 2002, 38(2): 23-27)
[9] Pearl J. Probabilistic Reasoning in Intelligente Systems: Networks of Plausible Inference. San Mateo, USA: Morgan Kaufmann, 1988
[10] Wong M L, Leung K S. An Efficient Data Mining Method for Learning Bayesian Networks Using an Evolutionary Algorithm-Based Hybrid Approach. IEEE Trans on Evolutionary Computation, 2004, 8(4): 378-404
[11] Chow C K, Liu C N. Approximating Discrete Probability Distributions with Dependence Trees. IEEE Trans on Information Theory, 1968, 14(3): 462-467
[12] Sprites P, Glymour C, Scheines R. Causation, Prediction and Search. 2nd Edition. Cambridge, USA: MIT Press, 2002 |
|
|
|
2006, Vol. 19 
