Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Pattern Analysis and Applications
Published in: Pattern Analysis and Applications 2/2020

05-04-2019 | Short paper

Parallel cycle-based branch-and-bound method for Bayesian network learning

Authors: Youcef Benmouna, Mohand Said Mezmaz, Said Mahmoudi, Med Amine Chikh

Published in: Pattern Analysis and Applications | Issue 2/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Bayesian networks (BNs) are one of the most commonly used models for representing uncertainty in medical diagnosis. Learning the exact structure of a BN is a challenging problem. This paper proposes a multi-threaded branch-and-bound (B&B) method, called parallel cycle-based branch-and-bound (parallel CB-B&B). On the one hand, CB-B&B improves the standard B&B method by leveraging two heuristics, namely the branching strategy and the bounding operators; on the other hand, the learning procedure is alleviated by executing CB-B&B over a set of parallel processors. In comparison with conventional exact structure learning approaches for BN, the obtained results demonstrate that the proposed CB-B&B is efficient. On average, it produces the exact structure for BN three times faster than the standard B&B version. We also present simulations on parallel CB-B&B which show a significant gain in terms of execution time.
previous article A novel contextual memory algorithm for edge detection
next article Finding patterns in the degree distribution of real-world complex networks: going beyond power law

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Li J, Fu AWC, He H, Chen J, Jin H, McAullay D, Kelman C (2005) Mining risk patterns in medical data. In: Proceedings of the eleventh ACM SIGKDD international conference on knowledge discovery in data mining. ACM, pp. 770–775
2.
3.
Pearl J (2014) Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, San FranciscoMATH
4.
Hurn MA, Mardia KV, Hainsworth TJ, Kirkbride J, Berry E (1996) Bayesian fused classification of medical images. IEEE Trans Med imaging 15(6):850–858CrossRef
5.
Arias J, Martínez-Gómez J, Gámez JA, de Herrera AGS, Müller H (2016) Medical image modality classification using discrete Bayesian networks. Comput Vis Image Underst 151:61–71CrossRef
6.
Al-Aidaroos KM, Bakar AA, Othman Z (2012) Medical data classification with Naive Bayes approach. Inf Technol J 11(9):1166CrossRef
7.
Wolfson J, Bandyopadhyay S, Elidrisi M, Vazquez-Benitez G, Vock DM, Musgrove D, O’Connor PJ (2015) A Naive Bayes machine learning approach to risk prediction using censored, time-to-event data. Stat Med 34(21):2941–2957MathSciNetCrossRef
8.
Wang KJ, Makond B, Wang KM (2014) Modeling and predicting the occurrence of brain metastasis from lung cancer by Bayesian network: a case study of Taiwan. Comput Biol Med 47:147–160CrossRef
9.
Klement W, Wilk S, Michalowski W, Farion KJ, Osmond MH, Verter V (2012) Predicting the need for CT imaging in children with minor head injury using an ensemble of Naive Bayes classifiers. Artif Intell Med 54(3):163–170CrossRef
10.
Chickering DM, Heckerman D, Meek C (2004) Large-sample learning of Bayesian networks is NP-hard. J Mach Learn Res 5:1287–1330MathSciNetMATH
11.
Silander T, Myllymaki P (2012) A simple approach for finding the globally optimal Bayesian network structure. arXiv preprint arXiv:​1206.​6875
12.
Singh AP, Moore AW (2005) Finding optimal Bayesian networks by dynamic programming
13.
14.
Cussens J (2014) Integer programming for Bayesian network structure learning. Qual Technol Quant Manag 11(1):99–110CrossRef
15.
Yuan C, Malone B, Wu X (2011) Learning optimal Bayesian networks using A* search. In: IJCAI proceedings-international joint conference on artificial intelligence, vol 22, no. 3, p 2186
16.
Yuan C, Malone B (2012) An improved admissible heuristic for finding optimal Bayesian networks. In: Proceedings of the 28th conference on uncertainty in artificial intelligence
17.
18.
De Campos CP, Ji Q (2011) Efficient structure learning of Bayesian networks using constraints. J Mach Learn Res 12:663–689MathSciNetMATH
19.
Chow CK, Liu CN (1968) Approximating discrete probability distributionswith dependence trees. Inf Theory 14:462–467MATHCrossRef
20.
Meila M, Jaakkola T (2000) Tractable Bayesian learning of tree belief networks. In: Proceedings of the sixteenth conference on uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., pp 380–388
21.
Spirtes P, Glymour C (1991) An algorithm for fast recovery of sparse causal graphs. Soc Sci Comput Rev 9(1):62–72CrossRef
22.
Kalisch M, Buhlmann P (2007) Estimating high-dimensional directed acyclic graphs with the PC-algorithm. J Mach Learn Res 8:613–636MATH
23.
Cooper GF, Herskovits E (1992) A Bayesian method for the induction of probabilistic networks from data. Mach Learn 9(4):309–347MATH
24.
Liu F, Zhu Q (2007) The max-relevance and min-redundancy greedy Bayesian network learning algorithm. In: International Work Conference on the Interplay Between Natural and Artificial Computation. Springer, Berlin, Heidelberg, pp 346–356
25.
26.
Zhang Q, Li Z, Zhou CJ, Wei XP (2013) Bayesian network structure learning based on the chaotic particle swarm optimization algorithm. Genet Mol Res 12(4):4468–4479CrossRef
27.
Dos Santos EB, Hruschka Jr ER, Hruschka ER, Ebecken NF (2010) A distance-based mutation operator for learning Bayesian network structures using evolutionary algorithms. In: 2010 IEEE congress on evolutionary computation (CEC). IEEE, pp 1–8
28.
29.
30.
Teyssier M, Koller D (2005) Ordering-based search: a simple and effective algorithm for learning Bayesian networks. In: Proceedings of the 21st conference on uncertainty in artificial intelligence, UAÍ05, pp 584–590
31.
Melab N (2005) Contributions à la résolution de problèmes d’optimisation combinatoire sur grilles de calcul. LIFL, USTL, Novembre. Thèse HDR
32.
Cung VD et al (1994) Parallel and distributed branch-and-bound/A* algorithms. Laboratoire PRISM, Universite de Versailles, Techncial report, p 94
33.
34.
Miller Donald L, Pekny Joseph F (1993) Commentary—the role of performance metrics for parallel mathematical programming algorithms. ORSA J Comput 5(1):26–28CrossRef
35.
Janakiram Virendra K (1988) A randomized parallel branch-and-bound algorithm. Int J Parallel Program 17(3):277–301MATHCrossRef
36.
Krivelevich M et al (2007) Approximation algorithms and hardness results for cycle packing problems. ACM Trans Algorithms (TALG) 3(4):48MathSciNetMATHCrossRef
37.
Cooper GF (1984) NESTOR: a computer-based medical diagnostic aid that integrates causal and probabilistic knowledge. No. STAN-CS-84-1031. STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, 1984
Metadata
Title
Parallel cycle-based branch-and-bound method for Bayesian network learning
Authors
Youcef Benmouna
Mohand Said Mezmaz
Said Mahmoudi
Med Amine Chikh
Publication date
05-04-2019
Publisher
Springer London
Published in
Pattern Analysis and Applications / Issue 2/2020
Print ISSN: 1433-7541
Electronic ISSN: 1433-755X
DOI
https://doi.org/10.1007/s10044-019-00815-1

Other articles of this Issue 2/2020

Pattern Analysis and Applications 2/2020 Go to the issue

Industrial and commercial application

Synchronization correction-based robust digital image watermarking approach using Bessel K-form PDF

Theoretical advances

A novel CT image segmentation algorithm using PCNN and Sobolev gradient methods in GPU frameworks

Industrial and commercial application

Manifold ranking graph regularization non-negative matrix factorization with global and local structures

Industrial and commercial application

An automatic multi-camera-based event extraction system for real soccer videos

Short paper

Text area segmentation from document images by novel adaptive thresholding and template matching using texture cues

Theoretical advances

Smooth estimates of multiple quantiles in dynamically varying data streams

Premium Partner

    Image Credits