Bayesian Networks (BN) are probabilistic graphical models used to encode in a compact way a joint probability distribution over a set of random variables. The NP-complete problem of finding the most probable BN structure given the observed data has been largely studied in recent years. In the literature, several complete algorithms have been proposed for the problem; in parallel, several tests for statistical independence between the random variables have been proposed, in order to reduce the size of the search space. In this work, we study how to hybridize the algorithm representing the state-of-the-art in complete search with two types of independence tests, and assess the performance of the two hybrid algorithms in terms of both solution quality and computational time. Experimental results show that hybridization with both types of independence test results in a substantial gain in computational time, against a limited loss in solution quality, and allow us to provide some guidelines on the choice of the test type, given the number of nodes in the network and the sample size.

Bayesian Network structure learning: Hybridizing complete search with independence tests

BADALONI, SILVANA;SAMBO, FRANCESCO;
2015

Abstract

Bayesian Networks (BN) are probabilistic graphical models used to encode in a compact way a joint probability distribution over a set of random variables. The NP-complete problem of finding the most probable BN structure given the observed data has been largely studied in recent years. In the literature, several complete algorithms have been proposed for the problem; in parallel, several tests for statistical independence between the random variables have been proposed, in order to reduce the size of the search space. In this work, we study how to hybridize the algorithm representing the state-of-the-art in complete search with two types of independence tests, and assess the performance of the two hybrid algorithms in terms of both solution quality and computational time. Experimental results show that hybridization with both types of independence test results in a substantial gain in computational time, against a limited loss in solution quality, and allow us to provide some guidelines on the choice of the test type, given the number of nodes in the network and the sample size.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3148581
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact