{'fraction_non_alphanumeric': 0.04538004027537114, 'fraction_numerical': 0.009085374420456142, 'mean_word_length': 3.9442000463070155, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reading Dependencies from Polytree-Like Bayesian Networks

We present a graphical criterion for reading dependencies from the minimal directed independence map G of a graphoid p when G is a polytree and p satisfies composition and weak transitivity. We prove that the criterion is sound and complete. We argue that assuming composition and weak transitivity is not too restrictive.


INTRODUCTION
A minimal directed independence map G of an independence model p is used to read independencies that hold in p. Sometimes, however, G can also be used to read dependencies holding in p. For instance, if p is a graphoid that is faithful to G then, by definition, lack of vertex separation is a sound and complete graphical criterion for reading dependencies from G. If p is simply a graphoid, then there also exists a sound and complete graphical criterion for reading dependencies from G [Bouckaert, 1995]. However, this criterion cannot be applied to check whether two set of nodes X and Y are dependant given a third set Z unless X and Y are adjacent in G, i.e. unless there is an edge in G from some A ∈ X to some B ∈ Y. In this paper, we try to overcome this shortcoming so that X and Y are not required to be adjacent in G. We do so by constraining G and p. Specifically, we present a sound and complete graphical criterion for reading dependencies from G under the assumptions that G is a polytree and p is a graphoid that satisfies composition and weak transitivity. We argue that assuming composition and weak transitivity is not too restrictive. Specifically, we show that there exist important families of probability distributions, among them Gaussian probability distributions, that satisfy these two properties.
The rest of the paper is organized as follows. We start by reviewing some concepts in Section 2. We show in Section 3 that assuming composition and weak transitivity is not too restrictive. We present our graphical criterion in Section 4 and prove that it is sound and complete. Finally, we close with some discussion in Section 5.

PRELIMINARIES
The definitions and results in this section are taken from [Lauritzen, 1996, Pearl, 1988, Studený, 2005. We use the juxtaposition XY to denote X ∪ Y, and X to denote the singleton {X}. Let U denote a set of random variables. Unless otherwise stated, all the independence models and graphs in this paper are defined over U.
Let X, Y, Z and W denote four mutually disjoint subsets of U. An independence model p is a set of independencies of the form X is independent of Y given Z. We represent that an independence is in p by X ⊥ ⊥ Y|Z and that an independence is not in p by X ⊥ ⊥ Y|Z. In the latter case, we may equivalently say that the dependence X ⊥ ⊥ Y|Z is in p. An independence model is a graphoid when it satisfies the following five properties: Any strictly positive probability distribution is a graphoid.
Let sep(X, Y|Z) denote that X is separated from Y given Z in a graph G. Specifically, sep(X, Y|Z) holds when every path in G between X and Y is blocked by Z. If G is an undirected graph (UG), then a path in G between X and Y is blocked by Z when there exists some Z ∈ Z in the path. We say that a node is a head-to-head node in a path if it has two parents in the path. If G is a directed and acyclic graph (DAG), then a path in G between X and Y is blocked by Z when there exists a node Z in the path such that either (i) Z is not a head-to-head node in the path and Z ∈ Z, or (ii) Z is a head-to-head node in the path and neither Z nor any of its descendants in G is in Z. An independence model p is faithful to an UG or DAG G when X ⊥ ⊥ Y|Z iff sep(X, Y|Z). Any independence model that is faithful to some UG or DAG is a graphoid. An UG (resp. DAG) G is an undirected (resp. directed) independence map of an independence model p when X ⊥ ⊥ Y|Z if sep(X, Y|Z). Moreover, G is a minimal undirected (resp. directed) independence map of p when removing any edge from G makes it cease to be an independence map of p. We abbreviate minimal undirected (resp. directed) independence map as MUI (resp. MDI) map. If G is a MUI map of p, then two nodes X and Y are adjacent in G iff X ⊥ ⊥ Y |U \ (XY ). On the other hand, if G is a MDI map of p, then the parents of a node X in G, P a(X), are the smallest subset of the nodes preceding X in a given total ordering of U, P re(X), such that X ⊥ ⊥ P re(X) \ P a(X)|P a(X). We denote the children of a node X by Ch(X).
Let Cl denote the set of cliques of an UG G. A Markov network (MN) is a pair (G, θ) where G is an UG and θ are parameters specifying a non-negative function for the random variables in each C ∈ Cl, φ(C). The MN represents the probability distribution p = K C∈Cl φ(C) where K is a normalizing constant. If a probability distribution p can be represented by a MN with UG G, then G is an undirected independence map of p. When p is strictly positive, the opposite also holds.
A Bayesian network (BN) is a pair (G, θ) where G is a DAG and θ are parameters specifying a multinomial probability distribution for each X ∈ U given its parents in G, p(X|P a(X)). The BN represents the multinomial probability distribution p = X∈U p(X|P a(X)). A probability distribution p can be represented by a BN with DAG G iff G is an directed independence map of p.
Given an UG (resp. DAG) G, we denote by M(G) all the multinomial probability distributions that can be represented by a MN (resp. BN) with UG (resp. DAG) G. Finally, recall that a polytree is a directed graph without undirected cycles. In other words, there exists at most one undirected path between any two nodes X and Y . We denote that path by X : Y if it exists. Recall also that a directed tree is a polytree where every node has at most one parent.

CWT GRAPHOIDS
Let X, Y, Z and W denote four mutually disjoint subsets of U. We call CWT graphoid to any graphoid that satisfies composition X ⊥ ⊥ Y|Z ∧ X ⊥ ⊥ W|Z ⇒ X ⊥ ⊥ YW|Z, and weak transitivity . We now argue that there exist important families of probability distributions that are CWT graphoids and, thus, that WT graphoids are worth studying. For instance, any probability distribution that is Gaussian or faithful to some UG or DAG is a CWT graphoid [Pearl, 1988, Studený, 2005. The theorem below proves that the marginals and conditionals of a probability distribution that is a CWT graphoid are CWT graphoids, although they may be neither Gaussian nor faithful to any UG or DAG. We give an example at the end of this section. We refer the reader to [Peña et al., 2006a, Peña et al., 2006b, Peña et al., 2007 for the proofs of the theorems in this section.

Theorem 1 Let p be a probability distribution that is a CWT graphoid and let
Hereinafter, we say that a probability distribution p has context-specific independencies if there exists some W ⊆ U such that p(U \ W|W = w) does not have the same independencies for all w. We now show that it is not too restrictive to assume, as in the theorem above, that a probability distribution is a CWT graphoid that has no context-specific independencies, because there exist important families of probability distributions whose all or almost all the members satisfy such assumptions. For instance, a Gaussian probability distribution is a CWT graphoid [Studený, 2005], and has no context-specific independencies because its independencies are determined by its covariance matrix [Lauritzen, 1996]. The theorems below prove that this is also the case for almost all the probability distributions in M(G) where G is an UG or DAG.
Theorem 2 Let G be an UG. M(G) has non-zero Lebesgue measure wrt R n , where n is the number of MN parameters corresponding to G. The probability distributions in M(G) that are not faithful to G or have context-specific independencies have zero Lebesgue measure wrt R n .
Theorem 3 Let G be a DAG. M(G) has non-zero Lebesgue measure wrt R n , where n is the number of BN parameters corresponding to G. The probability distributions in M(G) that are not faithful to G or have context-specific independencies have zero Lebesgue measure wrt R n .
The theorems above imply that, for any UG or DAG G, almost all the probability distributions in M(G) are CWT graphoids [Pearl, 1988], and that all the marginals and conditionals of almost all the probability dis-tributions in M(G) are CWT graphoids as well due to Theorem 1.
Finally, we give an example of a probability distribution that is a CWT graphoid although it is neither Gaussian nor faithful to any UG or DAG. Let p be a multinomial probability distribution that is faithful and that has no context-specific independencies. Such a probability distribution exists due to Theorem 3 and, moreover, it is a CWT graphoid [Pearl, 1988]. Then, p(X, Y, Z, V, A, B, C|W = w) for any w is a CWT graphoid by Theorem 1, but it is neither Gaussian nor faithful to any UG or DAG, because it is multinomial and faithful to the graph [Chickering & Meek, 2002, Peña et al., 2006b].

READING DEPENDENCIES
In this section, we propose a sound and complete criterion for reading dependencies from a polytree-like MDI map of a CWT graphoid. If G is a MDI map of a CWT graphoid p then we know, by construction of G, that X ⊥ ⊥ (P re(X) \ P a(X))Y |P a(X) \ Y for all X ∈ U and Y ∈ P a(X). We call these dependencies the dependence base of p for G. Further dependencies in p can be derived from this dependence base via the CWT graphoid properties. For this purpose, we rephrase the CWT graphoid properties as follows. Let X, Y, Z and W denote four mutually disjoint subsets of U.
problematic for deriving new dependencies because it contains a disjunction in the right-hand side and, thus, it should be split into two properties: Note that inter-section1 and intersection2 are equivalent and, thus, we refer to them simply as intersection. Likewise, compo- Since composition1 and composition2 are equivalent, we refer to them simply as composition. Finally, weak The independence in the left-hand side of any of the properties above holds if the corresponding sep statement holds in G. This is the best solution we can hope for because sep is sound and complete. By definition, sep is sound in the sense that it only identifies independencies in p. Furthermore, sep is complete in the sense that it identifies all the independencies in p that can be identified by studying G alone because (i) there exist multinomial and Gaussian probability distributions that are faithful to G [Meek, 1995], and (ii) such probability distributions are CWT graphoids [Pearl, 1988], G is a MDI map for them, and they only have the independencies that sep identifies from G. Moreover, this solution does not require more information about p than what it is available, because G can be constructed from the dependence base of p for G. We call the CWT graphoid closure of the dependence base of p for G to the set of dependencies that are in the dependence base of p for G plus those that can be derived from it by applying the CWT graphoid properties.
We now introduce our criterion for reading dependencies from a polytree-like MDI map G of a CWT graphoid p.
Definition 1 Let X, Y and Z denote three mutually disjoint subsets of U. We say that dep(X, Y|Z) holds if there exist some A ∈ X and B ∈ Y such that (i) sep(A, B|Z) does not hold, and (ii) for every headto-head node C in A : B, either Z contains C or Z contains exactly one descendant of C that is not a descendant of another descendant of C that is in Z.
We now prove that dep is sound, i.e. it only identifies dependencies in p. Actually, it only identifies dependencies in the CWT graphoid closure of the dependence base of p for G.

Theorem 4 Let G be a MDI map of a CWT graphoid p. If G is a polytree then, if dep(X, Y|Z) then X ⊥ ⊥ Y|Z is in the CWT graphoid closure of the dependence base of p for G.
Proof: Let us assume that every head-to-head node in A : B is in Z. We prove that dep(A, B|Z) implies A ⊥ ⊥ B|Z. We prove it by induction over the length of A : B.
We first prove the result for length one, i.e. A : B is A → B or A ← B. Assume without loss of generality that A : B is A → B. Let Z A denote the nodes in Z that are in P a(A) or connected to A by an undirected path that passes through P a(A). Let Z A denote the nodes in Z that are in Ch(A) \ B or connected to A by an undirected path that passes through Ch(A) \ B. Let Z B denote the nodes in Z that are in P a(B) \ A or connected to B by an undirected path that passes through P a(B) \ A. Let Z B denote the nodes in Z that are in Ch(B) or connected to B by an undirected path that passes through Ch (B). Note that the nodes in Z \ (Z A Z A Z B Z B ) are not connected to A or B by any undirected path. Then, (1) and (2) (
Assume as induction hypothesis that the result holds when the length of A : B is smaller than l. We now prove the result for length l. Let C be any node in A : B except A and B. If C is not a head-to-head node in A : B, then On the other hand, if C is a head-to-head node in A : B, then C must be in Z due to the assumption made at the beginning of this proof. Let Z C denote the nodes in Z that are in Ch(C) or connected to C by an undirected path that passes through Ch(C). Then, (27) and (28). Let us now assume that for every head-to-head node C in A : B, either Z contains C or Z contains exactly one descendant of C that is not a descendant of another descendant of C that is in Z. We prove that dep(A, B|Z) implies A ⊥ ⊥ B|Z. We prove it by induction over the number of head-to-head nodes in A : B that are not in Z. As proven above, the result holds when this number is zero. Assume as induction hypothesis that the result holds when this number is smaller than l. We now prove the result for l. Let C be any head-to-head node in A : B that is not in Z. Then, Z must contain exactly one descendant of C, say D, that is not a descendant of another descendant of C that is in Z. Let Z D denote the nodes in Z that are in Ch(D) or connected to D by an undirected path that passes through Ch(D). Then, Therefore, we have proven that dep(A, B|Z) implies A ⊥ ⊥ B|Z which, in turn, implies X ⊥ ⊥ Y|Z by decomposition. Since dep(X, Y|Z) implies dep(A, B|Z), dep(X, Y|Z) implies X ⊥ ⊥ Y|Z. Moreover, this last dependence must be in the CWT graphoid closure of the dependence base of p for G, because we have only used in the proof the dependence base of p for G and the CWT graphoid properties.
We now prove that dep is complete for reading dependencies from a polytree-like MDI map G of a CWT graphoid p, in the sense that it identifies all the dependencies in p that follow from the information about p that is available, namely the dependence base of p for G and the fact that p is a CWT graphoid.
Theorem 5 Let G be a MDI map of a CWT graphoid p. If G is a polytree, then if X ⊥ ⊥ Y|Z is in the CWT graphoid closure of the dependence base of p for G then dep(X, Y|Z).
Proof: It suffices to prove (i) that all the dependencies in the dependence base of p for G are identified by dep, and (ii) that dep satisfies the CWT graphoid properties. Since the first point is trivial, we only prove the second point. Let X, Y, Z and W denote four mutually disjoint subsets of U.
• Symmetry dep(Y, X|Z) ⇒ dep(X, Y|Z). The path A : B in the left-hand side also satisfies the right-hand side.
• Decomposition dep(X, Y|Z) ⇒ dep(X, YW|Z). The path A : B in the left-hand side also satisfies the right-hand side.
• Weak union dep(X, Y|ZW) ⇒ dep(X, YW|Z). The path A : B in the left-hand side also satisfies the right-hand side unless there exists some headto-head node C in A : B such that neither C nor any of its descendants is in Z (if several such nodes exist, let C be the closest to A). However, C or some descendant D of C must be in W for dep(X, Y|ZW) to hold. Then, A : C or A : D satisfies the right-hand side.
• Contraction1 dep(X, YW|Z) ∧ sep(X, Y|ZW) ⇒ dep(X, W|Z). Let C denote the closest node to A that is in both W and the path A : B in the left-hand side. Such a node must exist for sep(X, Y|ZW) to hold. For the same reason, no node in A : C can be in Y. Then, A : C satisfies the right-hand side.
• Contraction2 dep(X, YW|Z) ∧ sep(X, W|Z) ⇒ dep(X, Y|ZW). Let C denote the closest node to A that is in both Y and the path A : B in the left-hand side. Such a node must exist for sep(X, W|Z) to hold. For the same reason, no node in A : C can be in W. Then, A : C satisfies the right-hand side.
• Composition dep(X, YW|Z) ∧ sep(X, W|Z) ⇒ dep(X, Y|Z). Consider the same reasoning as in contraction2. XYZ). Let A : V and V : B denote the paths in the first and second, respectively, dep statements in the left-hand side. For sep(X, Y|Z) to hold, V must be a head-to-head node in A : B or the descendant of a head-to-head node in A : B that neither is in Z nor has any descendant in Z. Then, A : B satisfies the right-hand side. XYZ). Let A : V and V : B denote the paths in the first and second, respectively, dep statements in the left-hand side. Note that V must be a nonhead-to-head node in A : B for sep(X, Y|ZV ) to hold. Then, A : B satisfies the right-hand side.
Finally, the soundness of dep allows us to prove the following theorem.
Theorem 6 Let G be a MDI map of a CWT graphoid p. If G is a directed tree, then p is faithful to it.
Proof: Any independence in p for which the corresponding separation statement does not hold in G contradicts Theorem 4.
The theorem above has been proven by [Becker et al., 2000] for the case where G is a tree-like MUI map and p is either a Gaussian probability distribution or a multinomial probability distribution over binary random variables. In [Peña et al., 2006a], we have proven the theorem above for the case where G is a tree-like MUI map and p is a graphoid that satisfies weak transitivity.

DISCUSSION
We have presented a sound and complete graphical criterion for reading dependencies from a polytreelike MDI map G of a CWT graphoid. We have shown that there exist important families of probability distributions, among them Gaussian probability distributions, that are CWT graphoids. We think that this work complements previous works addressing the same question, e.g. [Bouckaert, 1995] which proposes sound and complete graphical criteria for reading dependencies from a MUI or MDI map of a graphoid, and [Peña et al., 2006a, Peña et al., 2006b, Peña et al., 2007 which propose a sound and complete graphical criterion for reading dependencies from the MUI map of graphoid that satisfies weak transitivity. See also [Peña et al., 2007] for a real-world application of the graphical criterion developed in that paper to read biologically meaningful gene dependencies.
Our end-goal is to apply the results in this paper to our project on atherosclerosis gene expression data analysis in order to learn dependencies between genes. We believe that it is not unrealistic to assume that the probability distribution underlying our data is a CWT graphoid. We base this belief on the following argument. The cell is the functional unit of all the organisms and includes all the information necessary to regulate its function. This information is encoded in the DNA of the cell, which is divided into a set of genes, each coding for one or more proteins. Proteins are required for practically all the functions in the cell. The amount of protein produced depends on the expression level of the coding gene which, in turn, depends on the amount of proteins produced by other genes. Therefore, a dynamic BN or Gaussian network (GN) seems to be a relatively accurate model of the cell: The nodes represent the genes and proteins, and the edges and parameters represent the causal relations between the gene expression levels and the protein amounts. As a matter of fact, dynamic BNs and GNs have become very popular models of gene networks for the last few years [Bernard & Hartemink, 2005, Friedman et al., 1998, Husmeier, 2003, Kim et al., 2003, Murphy & Mian, 1999, Ong et al., 2002, Perrin et al., 2003, Zou & Conzen, 2005.
It is important that the BN or GN is dynamic because a gene can regulate some of its regulators and even itself with some time delay. Since the technology for measuring the state of the protein nodes is not widely available yet, the data in most projects on gene expression data analysis is a finite sample of the probability distribution represented by the dynamic BN or GN after marginalizing the protein nodes out.
The probability distribution with no node marginalized out is almost surely faithful to the dynamic BN or GN [Meek, 1995] and, thus, it satisfies composition and weak transitivity (see Section 3) and, thus, so does the probability distribution after marginalizing the protein nodes out (see Theorem 1).
Other graphical models that have received increasing attention from the bioinformatics community as a means to gain insight into gene networks are the so-called graphical Gaussian models [Castelo & Roverato, 2006, Dobra et al., 2004, Li & Gui, 2006, Schäfer & Strimmer, 2005a, Schäfer & Strimmer, 2005b, Toh & Horimoto, 2002, Wang et al., 2003, Wu et al., 2003. A graphical Gaussian model is nothing else but the MUI map of the probability distribution underlying the gene network under the assumption that this is Gaussian and, thus, a CWT graphoid. This again supports our belief that the theory developed in this paper may be relevant within bioinformatics.