1
$\begingroup$

I would like to know whether $E \perp\kern-5pt\perp A $ in the following Markov Network and would like to know if my reasoning is correct:

enter image description here

So, since this is a Pairwise Markov Network, it factorizes into potentials. We have that $P(A,B,C,D,E) = \phi (A,B) \phi (A,C) \phi(B,D)\phi (C,D)\phi(D,E)\frac{1}{Z}$

where $Z$ is a normalization constant.

And so we have that the marginal for $E$ and $A$ is $P(E,A) \propto \sum_{B,C,D}\phi (A,B) \phi (A,C) \phi(B,D)\phi (C,D)\phi(D,E)$

Since $\sum_{x_1} \phi(x_1,x_2) \phi(x_1,x_3) = \phi(x_2,x_3)$

We have that $ \sum_{B,C,D}\phi (A,B) \phi (A,C) \phi(B,D)\phi (C,D)\phi(D,E) = \sum_{C,A} \phi(A,B)\phi(A,C)\phi(B,E,C) = \phi(B,E,C,A)$. Since $E$ and $A$ are inside one potential, this makes them dependent.

Would this be a correct way to determine unconditional independence in Markov Networks? Is there a faster, non-formula way to solve this?

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

$\newcommand{\pperp}{\perp\kern-5pt\perp} \newcommand{\npperp}{\not\perp\kern-8pt\perp} $ I am not sure whether I understand your argument. In general, to show that $A\npperp E$, I don't think it is sufficient to show that $p(A, E) = \phi(A, E)$ for some potential $\phi$, but one has to show that this $\phi(A,E)$ cannot be factored as $\phi_A(A)\phi_B(B)$.

So my approach would be as follows:
To be extra precise, I think what you want to show is the following: The condition, that a probability density function (pdf) has as I-map your Markov Network (MN), is not sufficient to deduce $A\pperp E$. I.e., we have to show that there exists a pdf that has the MN as I-map and that has $A\npperp E$.

Thus, let's presume that all variables are binary. Then, such a pdf could be: $$ \begin{align} A &\sim U(\{0, 1\})\quad\mbox{(uniform binary random variable)}\\ B &= A\\ C &= A\\ D &= I(B+C-2)\\ E &= D, \end{align} $$ where $I()$ is the function that is zero everywhere except at zero where it is equal to one. Then: $$ \begin{align} p(E=0|A=0) &= 1 \\ p(E=0|A=1) &= 0, \end{align} $$ which means $A\npperp E$.
(If it vexes you a bit that some conditional probabilities are undefined in this MN, just jitter the Markov transition matrices only a tiny bit, so that all probabilities become positive. This would not change the dependence of $A$ and $E$.)


Your question: "Is there a faster, non-formula way to solve this?":
Yes, there is the easier, graph-based, way. For MNs, if you can presume that the graph is a P-map for the pdf, then $A \pperp E$ if and only if there is no path in the MN connecting $A$ and $E$.

$\endgroup$
4
  • $\begingroup$ Thanks a lot for this answer. I was wondering whether there is a simpler way to deduce this, without "rigorously" proving it? For example we can see from a BN whether some variables are d-separated, without constructing variables the way you did in your approach here $\endgroup$
    – user
    Aug 4, 2022 at 13:28
  • 1
    $\begingroup$ Sorry, I overlooked the last sentence of your post. I have extended my answer. $\endgroup$
    – frank
    Aug 4, 2022 at 15:27
  • $\begingroup$ Thanks. So in simple words, if there is a path from $A$ to $E$, then they are not unconditionally independent? $\endgroup$
    – user
    Aug 4, 2022 at 16:21
  • 1
    $\begingroup$ Yes, that is correct. $\endgroup$
    – frank
    Aug 4, 2022 at 16:26

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.