3
$\begingroup$

I am struggling to prove that Bayesian Network must be acyclic. Could anyone help me in proving this? I am trying to prove by constructing a cyclic graph and showing some contradiction of probability distribution. But it's getting nowhere

$\endgroup$
  • $\begingroup$ @william, please stop spamming the site w/ tag edits. This shouldn't be done this way. You should raise the issue on meta.CV & we can make it a synonym. $\endgroup$ – gung May 1 '16 at 19:31
1
$\begingroup$

You're not going to find any contradictions by creating a cyclic graph. It's not that Bayes nets (or as I've heard them called, conditional independence networks since they really don't have anything to do with Bayesianism besides conditional independence rules) "have to be acyclic". We assume them to be acyclic to get certain properties and simplify calculation of probabilities. In fact, if we relax the acyclic restriction as well the directed restriction we get a more general model called a Markov network.

$\endgroup$
  • $\begingroup$ I meant directed cyclic graph. I am just trying to show conditional parametrization based on cyclic directed graph can lead to improper probability distributions. $\endgroup$ – hi15 Jan 19 '15 at 2:45
  • $\begingroup$ The same thing is still true. We make the assumption that the underlying topology is a DAG because it simplifies the calculations of probabilities but you won't find any any more improper distributions in networks built off of DCGs than you would in DAGs. What makes DAG's so much more convinient is that if you want to calculate probabilities in a DCG you have to treat the networks as markov processes and you end up having to find stationary states to find the probabilities whereas in DAGs you can just use conditional probability rules. $\endgroup$ – Nick Thieme Jan 19 '15 at 3:10
1
$\begingroup$

I am afraid that Nick's answer might be incomplete.

BNs must be acyclic in order to guarantee that their underlying probability distribution is normalized to 1. It is quite easy to prove that this is the case, by starting at a vertex with no parents (which must exist, otherwise the graph would contain a cycle) and marginalizing it out, then repeating the procedure until all vertices have been accounted for.

This is no longer guaranteed to be the case if the graph has a cycle and a counterexample is also readily found. Consider the cyclic graph $A \to B \to C$ where the value of each parent fully determines the value of its child, e.g., $p(B=x|A=x)=1$. If we now sum the joint distribution over all possible states $(A,B,C)$, then all states of type $(x,x,x)$ have joint probability 1, and all other states have probability 0. Clearly, the sum over multiple "ones" is larger than one.

Of course this argument only holds for stationary distributions, which I assume was the premise of the OP's question.

$\endgroup$
  • $\begingroup$ Could I get some more clarification about this: if I have a network which is cyclic ($A \rightarrow B \rightarrow \rightarrow C \rightarrow A$) to compute the joint query $P(A = x, B = x, C = x)$ you decompose it into a product of the conditionals i.e. $P(B = x | A = x) \times P(C = x | B = x) \times P(A = x | C = x) = 1$. Am I missing something here? $\endgroup$ – PSub Jul 9 '18 at 23:33
1
$\begingroup$

Bayesian Network is defined to be a DAG (Directed Acyclic Graph), you cannot prove a definition. Take a look at this explanation.

$\endgroup$
0
$\begingroup$

A Bayesian Network can be viewed as a data structure that provides the skeleton for representing a joint distribution compactly in a factorized way. For any valid joint distribution two restrictions should be satisfied:

1) All probabilities in the distribution should be non negative;
2) All the probabilities should sum to one.

Normally a graph is determined by the ordering of the factorization and the conditional independencies assumed in the independency structure of the distribution. Since we are dealing with an invalid Bayes Network we don't need to follow the procedure, and we can design many counterexamples to verify that the sum of the distribution would be not 1. For instance, assume that we have such a graph over three binary variables:
enter image description here

And we can obtain the joint distribution easily: in all $2^3$ possibilities at least two are 1: $P(a_0, b_0, c_0) = P(a_0|c_0)P(b_0|a_0)P(c_0|b_0)=1$
$P(a_1, b_1, c_1) = P(a_1|c_1)P(b_1|a_1)P(c_1|b_1)=1$

Then $\sum_{A,B,C} P(A, B, C)\ge2>1$, so the distribution is invalid(indicating the cyclic Bayes Network is invalid).

If we remove any one of the directions in the graph and adjust the parameters in the CPTs accordingly we can find that the joint distribution will be valid.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.