The study of the theoretical size and node probability of the loop cutset in Bayesian networks

Jie Wei, Yufeng Nie, Wenxian Xie

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Pearl's conditioning method is one of the basic algorithms of Bayesian inference, and the loop cutset is crucial for the implementation of conditioning. There are many numerical algorithms for solving the loop cutset, but theoretical research on the characteristics of the loop cutset is lacking. In this paper, theoretical insights into the size and node probability of the loop cutset are obtained based on graph theory and probability theory. It is proven that when the loop cutset in a p-complete graph has a size of p - 2, the upper bound of the size can be determined by the number of nodes. Furthermore, the probability that a node belongs to the loop cutset is proven to be positively correlated with its degree. Numerical simulations show that the application of the theoretical results can facilitate the prediction and verification of the loop cutset problem. This work is helpful in evaluating the performance of Bayesian networks.

Original languageEnglish
Article number1079
JournalMathematics
Volume8
Issue number7
DOIs
StatePublished - 1 Jul 2020

Keywords

  • Bayesian inference
  • Conditioning method
  • Loop cutset
  • Node probability of loop cutset

Fingerprint

Dive into the research topics of 'The study of the theoretical size and node probability of the loop cutset in Bayesian networks'. Together they form a unique fingerprint.

Cite this