Learning Bayesian Networks with the bnlearn R …

1 JSSJ ournal of Statistical SoftwareMMMMMM YYYY, Volume VV, Issue Bayesian Networks with thebnlearnRPackageMarco ScutariUniversity of PadovaAbstractbnlearnis anRpackage (R Development Core Team 2009) which includes several algo-rithms for Learning the structure of Bayesian Networks with either discrete or continuousvariables. Both constraint-based and score-based algorithms are implemented, and canuse the functionality provided by thesnowpackage (Tierneyet ) to improve theirperformance via parallel computing. Several network scores and conditional independencealgorithms are available for both the Learning algorithms and independent use. Advancedplotting options are provided by theRgraphvizpackage (Gentryet ).Keywords: Bayesian Networks ,R, structure Learning algorithms, constraint-based algorithms,score-based algorithms, conditional independence IntroductionIn recent years Bayesian Networks have been used in many fields, from On-line AnalyticalProcessing (OLAP) performance enhancement (Margaritis 2003) to medical service perfor-mance analysis (Acidet ), gene expression analysis (Friedmanet ), breastcancer prognosis and epidemiology (Holmes and Jain 2008).

2 The high dimensionality of the data sets common in these domains have led to the develop-ment of several Learning algorithms focused on reducing computational complexity while stilllearning the correct network . Some examples are theGrow-Shrinkalgorithm in Margaritis(2003), theIncremental Associationalgorithm and its derivatives in Tsamardinoset al.(2003)and in Yaramakala and Margaritis (2005), theSparse Candidatealgorithm in Friedmanet al.(1999), the Optimal Reinsertion in Moore and Wong (2003) and the Greedy Equivalent Searchin Chickering (2002).The aim of thebnlearnpackage is to provide a free implementation of some of these structurelearning algorithms along with the conditional independence tests and network scores [ ] 10 Jul 20102 Learning Bayesian Networks with thebnlearnRPackageto construct the Bayesian network .

3 Both discrete and continuous data are supported. Fur-thermore, the Learning algorithms can be chosen separately from the statistical criterion theyare based on (which is usually not possible in the reference implementation provided by thealgorithms authors), so that the best combination for the data at hand can be Bayesian networksBayesian Networks are graphical models where nodes represent random variables (the twoterms are used interchangeably in this article) and arrows represent probabilistic dependenciesbetween them (Korb and Nicholson 2004).The graphical structureG= (V,A) of a Bayesian network is adirected acyclic graph(DAG),whereVis thenode(orvertex)setandAis thearc(oredge)set. The DAG defines afactorization of the joint probability distribution ofV={X1,X2.}

4 ,Xv}, often called theglobal probability distribution, into a set oflocal probability distributions, one for each form of the factorization is given by theMarkov propertyof Bayesian Networks (Korb andNicholson 2004, section ), which states that every random variableXidirectly dependsonly on its parents Xi:P(X1,..,Xv) =v i=1P(Xi| Xi)(for discrete variables)(1)f(X1,..,Xv) =v i=1f(Xi| Xi)(for continuous variables).(2)The correspondence between conditional independence (of the random variables) and graph-ical separation (of the corresponding nodes of the graph) has been extended to an arbitrarytriplet of disjoint subsets ofVby Pearl (1988) with thed-separation(fromdirection-dependents eparation). Therefore model selection algorithms first try to learn the graphical structure ofthe Bayesian network (hence the name ofstructure Learning algorithms) and then estimatethe parameters of the local distribution functions conditional on the learned structure.

5 Thistwo-step approach has the advantage that it considers one local distribution function at atime, and it does not require to model the global distribution function explicitly. Anotheradvantage is that Learning algorithms are able to scale to fit high-dimensional models withoutincurring in the so-calledcurse of there are many possible choices for both the global and the local distribution func-tions, literature have focused mostly on two cases: multinomial data(thediscrete case): both the global and the local distributions aremultinomial, and are represented as probability or contingency tables. This is by farthe most common assumption, and the corresponding Bayesian Networks are usuallyreferred to asdiscrete Bayesian Networks (or simply asBayesian Networks ).

6 Multivariate normal data(thecontinuous case): the global distribution is multivariatenormal, and the local distributions are normal random variables linked by linear con-straints. These Bayesian Networks are calledGaussian Bayesian networksin Geiger andHeckerman (1994), Neapolitan (2003) and most recent literature on the of Statistical Software3 Other distributional assumptions lead to more complex Learning algorithms (such as the non-parametric approach proposed by Bach and Jordan (2003)) or present various limitations dueto the difficulty of specifying the distribution functions in closed form (such as the approach tolearn Bayesian network with mixed variables by Boettcher and Dethlefsen (2003), which doesnot allow a node associated with a continuous variable to be the parent of a node associatedwith a discrete variable).

7 3. Structure Learning algorithmsBayesian network structure Learning algorithms can be grouped in two categories: constraint-based algorithms: these algorithms learn the network structure by analyzingthe probabilistic relations entailed by the Markov property of Bayesian Networks withconditional independence tests and then constructing a graph which satisfies the corre-sponding d-separation statements. The resulting models are often interpreted ascausalmodelseven when learned from observational data (Pearl 1988). score-based algorithms: these algorithms assign a score to each candidate Bayesiannetwork and try to maximize it with some heuristic search algorithm. Greedy searchalgorithms (such ashill-climbingortabu search) are a common choice, but almost anykind of search procedure can be algorithmsare all based on theInductive Causation(IC) algorithm by Vermaand Pearl (1991), which provides a theoretical framework for Learning the structure causalmodels.

8 It can be summarized in three steps:1. first theskeletonof the network (the undirected graph underlying the network structure)is learned. Since an exhaustive search is computationally unfeasible for all but the mostsimple data sets, all Learning algorithms use some kind of optimization such as restrictingthe search to theMarkov blanketof each node (which includes the parents, the childrenand all the nodes that share a child with that particular node).2. set all direction of the arcs that are part of av-structure(a triplet of nodes incident ona converging connectionXj Xi Xk).3. set the directions of the other arcs as needed to satisfy the acyclicity algorithmson the other hand are simply applications of various general purposeheuristic search algorithms, such ashill-climbing,tabu search,simulated annealingand variousgenetic algorithms.

9 The score function is usuallyscore-equivalent(Chickering 1995), so thatnetworks that define the same probability distribution are assigned the same Bayesian Networks with thebnlearnRPackage4. Package Structure Learning algorithmsbnlearnimplements the following constraint-based Learning algorithms (the respective func-tion names are reported in parenthesis): Grow-Shrink(gs): based on theGrow-Shrink Markov Blanket, the simplest Markovblanket detection algorithm (Margaritis 2003) used in a structure Learning algorithm. Incremental Association(iamb): based on the Incremental Association Markov blanket(IAMB) algorithm (Tsamardinoset ), which is based on a two-phase selectionscheme (a forward selection followed by an attempt to remove false positives). Fast Incremental Association( ): a variant of IAMB which uses specula-tive stepwise forward selection to reduce the number of conditional independence tests(Yaramakala and Margaritis 2005).

10 Interleaved Incremental Association( ): another variant of IAMB whichuses forward stepwise selection (Tsamardinoset ) to avoid false positives in theMarkov blanket detection phase. Max-Min Parents and Children(mmpc): a forward selection technique for neighbourhooddetection based on the maximization of the minimum association measure observed withany subset of the nodes selected in the previous iterations (Tsamardinoset ). Itlearns the underlying structure of the Bayesian network (all the arcs are undirected, noattempt is made to detect their orientation).Three implementations are provided for each algorithm: an optimized implementation (used by default) which uses backtracking to roughly halvethe number of independence tests. an unoptimized implementation (used when theoptimizedargument is set toFALSE)which is faithful to the original description of the algorithm.