Understanding Bayesian Networks - bnlearn

1 Understanding Bayesian Networkswith Examples in RMarco of StatisticsUniversity of OxfordJanuary 23 25, 2017 DefinitionsMarco ScutariUniversity of OxfordDefinitionsA Graph and a Probability DistributionBayesian Networks (BNs) are defined by: a network structure, a directed acyclic graphG= (V,A), in whicheach nodevi Vcorresponds to a random variableXi; a global probability distributionXwith parameters , which canbe factorised into smaller local probability distributions according tothe arcsaij Apresent in the main role of the network structure is to express the conditionalindependence relationships among the variables in the model throughgraphical separation, thus specifying the factorisation of the globaldistribution:P(X) =N i=1P(Xi| Xi; Xi)where Xi={parents ofXi}Marco ScutariUniversity of OxfordDefinitionsWhere to Look: Book References(Best perused as ebooks, the Koller & Friedman is 21/2inches thick.)

2 Marco ScutariUniversity of OxfordDefinitionsHow to Use: Software ReferencesDISCLAIMER: I am the author of thebnlearnR packageand I will use it for the most part in this (" bnlearn ")For displaying graphs, I will use theRgraphvizfromBioConductor:source(" ")biocLite(c("graph", "Rgraphviz"))For exact inference on discrete Bayesian Networks :source(" ")biocLite(c("graph", "Rgraphviz", "RBGL")) ("gRain")Other packages from (c("pcalg", "catnet", "abn"))Marco ScutariUniversity of OxfordDefinitionsGraphsThe first component of a BN is a graph. AgraphGis a mathematical object with: a set of nodesV={v1.}

3 ,vN}; a set of arcsAwhich are identified bypairs for nodes inV, (vi,vj).GivenV, a graph is uniquely identified arcs inAcan be: undirected if(vi,vj)is an unordered pairand the arcvi vjhas no direction; directed if(vi,vj)6= (vj,vi)is an orderedpair and the arc has a specific directionvi assumption is that there is at most onearc between a pair of ScutariUniversity of OxfordDefinitionsDirected Acyclic GraphsBNs use a specific kind of graph called a directed acyclic graph, that: contains only directed arcs; does not contain any loop ( an arcvi vifrom a node toitself); does not contain any cycle ( a sequence of arcsvi vj.)

4 Vk vithat starts and ends in the same node).ABCDEABCDEABCDEM arco ScutariUniversity of OxfordDefinitionsHow the DAG Maps to the Probability DistributionCABDEFDAGG raphicalseparationProbabilisticindepende nceFormally, the DAG is an independence map of the probabilitydistribution ofX, with graphical separation ( G) implying probabilisticindependence ( P).Marco ScutariUniversity of OxfordDefinitionsMapsLetMbe the dependence structure of the probability distributionPofX, that is, the set of conditional independence relationships linking anytripletA,B,Cof subsets ofX. A graphGis a dependency map (orD-map) ofMif there is a one-to-one correspondence between therandom variables inXand the nodesVofGsuch that for all disjointsubsetsA,B,CofXwe haveA PB|C= A GB| ,Gis an independency map (or I-map) ofMifA PB|C =A GB| said to be a perfect map ofMif it is both a D-map and an I-map,that isA PB|C A GB|C,and in this caseGis said to be faithful or isomorphic ScutariUniversity of OxfordDefinitionsGraphical Separation in DAGs (Fundamental Connections)separation (undirected graphs)d-separation (directed acyclic graphs)

5 CABCABCABCABM arco ScutariUniversity of OxfordDefinitionsGraphical Separation in DAGs (General Case)Now, in the general case we can extend the patterns from thefundamental connections and apply them to every possible path betweenAandBfor a givenC; this is how d-separation is ,BandCare three disjoint subsets of nodes in a directedacyclic graphG, thenCis said to d-separateAfromB,denotedA GB|C, if along every path between a node inAand a node inBthere is a nodevsatisfying one of thefollowing two converging edges ( there are two edges pointingtovfrom the adjacent nodes in the path) and none ofvor its descendants ( the nodes that can be reachedfromv) are inCand does not have converging definition clearly does not provide a computationally feasibleapproach to assess d-separation.

6 But there are other ScutariUniversity of OxfordDefinitionsA Simple Algorithm to Check D-Separation (I)CABDEFCABDEFSay we want to check whetherAandEare d-separated byB. First, wecan drop all the nodes that are not ancestors ( parents, parents parents, etc.) ofA,EandBsince each node only depends on ScutariUniversity of OxfordDefinitionsA Simple Algorithm to Check D-Separation (II)CABECABET ransform the subgraph into its moral graph by1. connecting all nodes that have one parent in common; and2. removing all arc directions to obtain an undirected transformation has the double effect of making the dependencebetween parents explicit by marrying them and of allowing us to usethe classic definition of graphical ScutariUniversity of OxfordDefinitionsA Simple Algorithm to Check D-Separation (III)CABEF inally, we can just perform a depth-first or breadth-first search andsee if we can find an open path betweenAandB, that is, a path that isnot blocked ScutariUniversity of OxfordDefinitionsThe Local Markov Property (I)

7 If we use d-separation as our definition of graphical separation, assumingthat the DAG is an I-map leads to the general formulation of thedecomposition of the global distributionP(X):P(X) =N i=1P(Xi| Xi)(1)into the local distributions for theXigiven their parents Xi. IfXihastwo or more parents it depends on their joint distribution, because eachpair of parents forms a convergent connection centred onXiand wecannot establish their independence. This decomposition is preferable tothat obtained from the chain rule,P(X) =N i=1P(Xi|Xi+1,..,XN)(2)because the conditioning sets are typically ScutariUniversity of OxfordDefinitionsThe Local Markov Property (II)Another result along the same lines is called the local Markov property,which can be combined with the chain rule above to get thedecomposition into local nodeXiis conditionally independent of itsnon-descendants ( , nodesXjfor which there is no pathfromXitoXj) given its to the previous decomposition, it highlights the fact thatparents are not completely independent from their children in the BN.

8 Atrivial application of Bayes theorem to invert the direction of theconditioning shows how information on a child can change thedistribution of the ScutariUniversity of OxfordDefinitionsCompletely D-Separating: Markov BlanketsParentsChildrenChildren's other parents(Spouses)Markov blanket of AAFIHEDCBGWe can easily use the DAG to solvethe feature selection problem. Theset of nodes that graphicallyisolates a target node from the restof the DAG is called its Markovblanket and includes: its parents; its children; other nodes sharing a Gimplies P, we canrestrict ourselves to the Markovblanket to perform any kind ofinference on the target node, anddisregard the ScutariUniversity of OxfordDefinitionsDifferent DAGs, Same Distribution: Topological OrderingA DAG uniquely identifies a factorisation ofP(X); the converse is notnecessarily true.

9 Consider again the DAG on the left:P(X) = P(A) P(B) P(C|A,B) P(D|C) P(E|C) P(F|D).We can rearrange the dependencies using Bayes theorem to obtain:P(X) = P(A|B,C) P(B|C) P(C|D) P(D|F) P(E|C) P(F),which gives the DAG on the right, with a different topological ScutariUniversity of OxfordDefinitionsDifferent DAGs, Same Distribution: Equivalence ClassesOn a smaller scale, even keeping the same underlying undirected graphwe can reverse a number of arcs without changing the dependencestructure ofX. Since the tripletsA B CandA B Careprobabilistically equivalent, we can reverse the directions of their arcs aswe like as long as we do not create any new v-structure (A B C,with no arc betweenAandC).

10 This means that we can group DAGs into equivalence classes that areuniquely identified by the underlying undirected graph and thev-structures. The directions of other arcs can be either: uniquely identifiable because one of the directions would introducecycles or new v-structures in the graph (compelled arcs); completely result is a completed partially directed graph (CPDAG).Marco ScutariUniversity of OxfordDefinitionsWhat Are V-Structures, and What Are NotIt is important to note that even thoughA B Cis a convergentconnection, it is not a v-structure ifAandCare connected byA a result, we are no longer able to identify which nodes are theparents in the connection.