Bayesian Network Structure Learning And Its Applications

There are many types of uncertainty in the real world and building effective uncertainty modelsis crucial for making correct decisions on uncertain problems. A Bayesian network provides acompact, intuitive and effective graphical expression mode for uncertain relationships of variables inapplication domains. Efficient and reliable algorithms for structure learning are essential forBayesian network applications. Both Bayesian networks and their applications have been hotresearch topics in China and abroad in recent years. After an extensive review on related work inBayesian networks on dealing with two major problems, low convergence rates and convergence tolocal optima faced by existing structure learning algorithms, this thesis studies structure learningunder two scenarios: when the data is complete and when there are missing data items. In addition,the applications of Bayesian networks in sensitivity analysis and frequent patterns mining areinvestigated in the thesis. The main contributions of the thesis are as follows.1. Bayesian network structure learningâ‘ Bayesian network structure learning with complete data. Exisiting research has shown thatthe Markov Chain Monte Carlo (MCMC) is a stochastic simulation that ensures ergodicity andreaches solutions with a long term frequency equal to the Boltzmann. The Metropolis-Hastingssampler (MHS) is the most frequently used MCMC method. But the Markov chain of MHS has theproblem of poor mixing and low convergence rates. This thesis improves the MHS algorithm on itsinitial structure, proposal distribution, and sub-structure sampling, and presents an improvedalgorithm PCMHS for learning Bayesian networks. The PCMHS algorithm runs multiMetropolis-Hasting samplers simultaneously, and each sampler is a Markov chain simulating asystem converging to Boltzmann distribution. Firstly, the PCMHS algorithm, based on the mutualinformation between nodes, initializes all Markov chains. In the process of each iteration, thealgorithm, based on the population from parallel Metropolis-Hasting samplers, generates theproposed distribution for the next generation, and uses edge sampling and sub-structure sampling toproduce the individuals of the next generation. The PCMHS algorithm converges to a stabledistribution and has a better learning accuracy. In addition, PCMHS provides an initial distributionand a proposed distribution as close as possible to the stable distribution, and improves theconvergence rate significantly. The experimental results on benchmark datasets also demonstrate thatthe learning accuracy and efficiency of the PCMHS algorithm outperform state-of-the-art algorithmsMHS and PopMCMC.â‘¡Bayesian network structure learning with missing data. Exisitng methods for learningBayesian networks from missing data have the problems of getting stuck on local optima and lowlearning efficiency in the case of a large percentage of missing data. To solve these problems, an algorithm BC-ISOR is proposed for learning Bayesian networks from datasets with missing data.BC-ISOR firstly estimates the probability distribution of a variable set from missing data based onthe Bound and Collapse method. Then, BC-ISOR learns Bayesian networks based on dependencyanalysis. When a dataset has no more than30attributes, BC-ISOR can obtain realistic instances andprobable instances through one dataset scan, and its missing data processing efficiency is irrelevantto the missing rate. In addition, through using heuristic ideas for searching cut-sets and orienting allthe edges before removing redundant edges, BC-ISOR can reduce the number and order ofconditional independence tests. So the BC-ISOR algorithm has a good learning performance.Experimental results on benchmark datasets show that BC-ISOR learns more efficiently andaccuracily than the well-known algorithm SEM.2. Applications of Bayesian networksâ‘ Sensitivity analysis of Bayesian networks. Sensitivity analysis of Bayesian networks is basedon a tree-join algorithm and mainly includes evidence sensitivity analysis and parameter sensitivityanalysis. The Shafer-Shenoy algorithm and the Hugin algorithm provide two different messagepropagation modes for reasoning-analysizing algorithms based on joint trees. Compared with theShafer-Shenoy algorithm, the Hugin algorithm is more efficient, but cannot guarantee sensitivityanalysis through a local calculation in the case of zero-division. To overcome the limitation of theHugin algorithm in the case of zero-division, a refined Hugin algorithm, R-Hugin, is proposed in thisthesis for sensitivity analysis, which introduces a zero-division flag and a zero-division processingmechanism in the message propagation process of the Hugin algorithm. Meanwhile, the correctnessand efficiency of the R-Hugin algorithm are validated by both theoretic analysis and experiments.â‘¡Frequent pattern discovery based on Bayesian networks. Based on background knowledgerepresented as a Bayesian network, this thesis presents a BN-EJTR method for computing theinterestingness of frequent items and frequent attributes, and for pruning. BN-EJTR seeks to findinconsistent knowledge relative to the background knowledge and to resolve the problems ofun-interestingness and redundancy faced by frequent pattern mining. To deal with the demand ofbatch reasoning in Bayesian networks during computing interestingness, BN-EJTR provides areasoning algorithm based on extended junction tree elimination for computing the support of a largenumber of items in a Bayesian network. In addition, BN-EJTR is equipped with a pruningmechanism based on a threshold for topological interestingness. Experimental results demonstratethat BN-EJTR has a good time performance compared with the same classified methods, andBN-EJTR has effective pruning results. Our analysis indicates that both the pruned frequentattributes and the pruned frequent items are un-interesting with respect to the backgroundknowledge.