Abstract
Bayesian networks are a powerful approach for representing and reasoning under conditions of uncertainty. Many researchers aim to find good algorithms for learning Bayesian networks from data. And the heuristic search algorithm is one of the most effective algorithms. Because the number of possible structures grows exponentially with the number of variables, learning the model structure from data by considering all possible structures exhaustively is infeasible. PSO (particle swarm optimization), a powerful optimal heuristic search algorithm, has been applied in various fields. Unfortunately, the classical PSO algorithm only operates in continuous and real-valued space, and the problem of Bayesian networks learning is in discrete space. In this paper, two modifications of updating rules for velocity and position are introduced and a Bayesian networks learning based on binary PSO is proposed. Experimental results show that it is more efficient because only fewer generations are needed to obtain optimal Bayesian networks structures. In the comparison, this method outperforms other heuristic methods such as GA (genetic algorithm) and classical binary PSO.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Pearl J (1988) Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufman, San Mateo
Heckerman D (1997) Bayesian networks for data mining. Data Mining Knowl Discov 1: 79–119
Heckerman D, Geiger D et al (1995) Learning Bayesian networks: the combination of knowledge and statistical data. Mach Learn 2: 197–243
Etxeberria R, Larrañaga P, Picaza JM (1997) Analysis of the behaviour of genetic algorithms when learning Bayesian network structure from data. Pattern Recognit Lett 18: 1269–1273
Suzuki J (1999) Learning Bayesian belief networks based on the minimum description length principle: basic properties. IEICE Trans Fundam Electron Commun Comput Sci E82-A: 2237–2245
Cheng J, Greiner R, Kelly J, Bell D, Liu W (2002) Learning Bayesian network from data: an information-theory based approached. Artif Intell 137: 43–90
Robinson RW (1977) Counting unlabeled acyclic digraphs. In: Little CHC (ed) Combinatorial mathematics. Springer Lecture Notes in Math., vol 622, pp 28–43
Chickering DM, Geiger D, Heckerman D (1994) Learning Bayesian networks is NP-hard. Microsoft Res., Redmond, WA, MSR-TR-94–17
Reeves CR (1993) Modern heuristic techniques for combinatorial problems. Blackwell Scientific Publications, Oxford
Alcobé JR (2004) Incremental Hill-climbing search applied to Bayesian network structure learning. In: Proceedings of the 15th European Conference on Machine Learning, Pisa, Italy
Larrañaga P, Murga RH, Poza M, Kuijpers CMH (1995) Structure learning of Bayesian networks by hybrid genetic algorithms. In: Preliminary Papers of the Fifth International Workshop on Artificial Intelligence and Statistics, pp 310–316
Larrañaga P, Poza M, Yurramendi Y, Murga RH, Kuijpers CMH (1996) Structure learning of Bayesian networks by genetical algorithms: a performance analysis of control parameters. IEEE Trans Pattern Anal Mach Intell 18: 912–926
Larrañaga P, Kuijpers CMH, Murga RH, Yurramendi Y (1996) Learning Bayesian network structures by searching for best ordering with genetic algorithm. IEEE Trans Syst Man Cybernet 26(4): 487–493
Lam W, Bacchus F (1994) Learning Bayesian belief networks-an approach based on the MDL principle. Comput Intell 10: 269–293
Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, Perth, pp 1942–1948
Senthil Arumugam M, Rao MVC, Chandramohan A (2008) A new and improved version of particles warm optimization algorithm with global–local best parameters. Knowl Inform Syst 16(3): 331–357
Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Michigan
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 264(5163): 1297–1301
Salman A, Ahmad I, Al-Madani S (2002) Particle swarm optimization for task assignment problem. Microprocessors Microsyst 26: 363–371
Heng X-C, Qin Z, Wang X-H, Shao L-P (2006) Research on learning Bayesian networks by particle swarm optimization. Inform Technol J 5(3): 540–545
Heng X-C, Qin Z, Tian L, Shao L-P (2007) Learning bayesian network structures with discrete particle swarm optimization algorithm. FOCI 2007, pp 47–52
Heng X-C, Qin Z, Tian L, Shao L-P (2007) Research on structure learning of dynamic bayesian networks by particle swarm optimization. CI-ALife 2007, pp 85–91
Li X-L, Wang S-C, He X-D (2006) Learning Bayesian networks structures based on memory binary particle swarm optimization. SEAL 2006, LNCS 4247, pp 568–574
Cooper GF, Herskovits EA (1992) A Bayesian method for the induction of probabilistic networks from data. Mach Learn 9: 309–347
Shi Y, Eberhart RC (1998) A modified particle swarm optimizer. Proc. IEEE Int. Conf. On Evolutionary Computation. Anchorage, AK, USA, pp. 69–73.
Kennedy J, Eberhart RC (1997) A Discrete binary version of the particle swarm algorithm. In: Proceedings of IEEE conference on systems, man and cybernetics, pp 4104–4108
Wang XY, Yang J, Teng XL, Xia WJ, Jensen R (2007) Feature selection based on rough sets and particle swarm optimization. Pattern Recognit Lett 28: 459–471
Beinlinch IA, Suermondt HJ, Chavez RM, and Cooper GF (1989) The ALARM Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks. In: Proceedings of the Second European Conf. Artificial Intelligence in Medicine, pp. 247–256
Henrion M (1988) Propagating uncertainty in Bayesian networks by logic sampling. In: Lemmar J, Kanal L (eds) Proceedings of the 2nd conference on uncertainty artificial intelligence, Amsterdam, pp 149–163
Herskovits E (1991) Computer based probabilistic-network construction. Doctoral dissertation. Medical Information Sciences, Stanford University
Kennedy J, Eberhart RC (1995) A new optimizer using particle swarm theory. In: Sixth international symposium on micro machine and human science, Nagoya, pp 39–43
Wang Z, Wang Q, Wang D-W (2009) Bayesian network based business information retrieval model. Knowl Inform Syst 20(1): 63–79
Kjaulff U (1992) A computational scheme for reasoning in dynamic probabilistic networks. In: Proceedings of the eighth conferebce on uncertainty in artificial intelligence, pp 121–129
Wang KJ, Zhang JY, Shen FS, Shi LF (2008) Adaptive learning of dynamic Bayesian networks with changing structures by detecting geometric structures of time series. Knowl Inform Syst 17(1): 121–133
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, T., Yang, J. A heuristic method for learning Bayesian networks using discrete particle swarm optimization. Knowl Inf Syst 24, 269–281 (2010). https://doi.org/10.1007/s10115-009-0239-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10115-009-0239-6