5
$\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$
1
  • $\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$ May 1, 2016 at 19:31

5 Answers 5

3
$\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$
2
  • $\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$ Jan 19, 2015 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$ Jan 19, 2015 at 3:10
3
$\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$
6
  • $\begingroup$ Is there a reason you chose three variables? This argument should work for two variables too right? Or I overlooked something in the case of two variables? $\endgroup$
    – manav
    Jan 23, 2021 at 20:30
  • $\begingroup$ @manav I think that also works for two variables. $\endgroup$ Jan 24, 2021 at 4:57
  • $\begingroup$ maybe factorization needs to be like this? p(a0 b0 c0) = p(a0) p(b0|a0) p(c0|a0) Then they would sum to 1 ?? $\endgroup$
    – hotohoto
    Apr 23, 2022 at 12:01
  • $\begingroup$ @hotohoto Could you please explain a little bit? Specifically, why the term $p(c_0|a_0)$? $\endgroup$ Apr 23, 2022 at 13:04
  • $\begingroup$ I just used the chain rule of conditional probabilities which is always true. So p(a0 b0 c0) = p(a0) p(b0|a0) p(c0|a0, b0). After then applied the dependency described in the Graph. So it's equal to p(a0) p(b0|a0) p(c0|a0) since c0 doesn't depend on b0 in the Graph. Maybe I'm on the same page with @Nick Theme as he said "You're not going to find any contradictions". And the difference between two ways of understanding may come from what we think the Graph is for? 🙂 $\endgroup$
    – hotohoto
    Apr 25, 2022 at 3:50
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$
1
  • $\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, 2018 at 23:33
1
$\begingroup$

Cycles are redundant, that's all. And it is pretty easy to show if you think about the transitivity.

  • A -> B -> C -> A implies A -> B and B -> A

So the directionality is immediately lost (for every pair in the loop).

  • A -> B -> C -> A is also deterministic, the multiplier is one.

For example:

Say B = (1/3)A + e1 and C = (1/2)B + e2; then A = A implies that A = 6C + e3, where 0 = e3 + 6e2 + 3*e1.

So cycles like this may be solved deterministically by simultaneous equations, and all nodes are basically transformations of the same distribution. You might as well collapse the cycle to one node only, because there is no more information in the three of them than there is in any one.

For a formal proof like this it would be nice to replace the constant multipliers with functions, then using something like this simplest of cycles as the basis for an induction argument, but you get the idea.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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