3
$\begingroup$

I have just started working through Michael Jordan's notes on Probabilistic Graphical Models and seem to be stuck on the exercise on page 5. I summarize the question here:

Suppose $G = (V,E)$ is a DAG with $n$ nodes. Corresponding to each node $i \in V$, let $X_i$ be a random variable. Denote the set of random variables that belong to the parent nodes of $X_i$ by $X_{\pi_i}$. To each note $i$, let $f_i(x_i, x_{\pi_i})$ be a function that behaves like a pdf on $X_i$ conditioned on $X_{\pi_i}$. Let $p(x_1, \ldots , x_n) = \prod_{i=1}^n f_i(x_i, x_{\pi_i})$.

It can be shown that $p$ is a joint distribution on $X_1, \ldots, X_n$. Show that for every $i \in V, \> p(x_i \mid x_{\pi_i}) = f_i(x_i, x_{\pi_i})$. My idea for a proof was to use induction.

We can assume without loss in generality that the nodes are ordered topologically. Then: $$ \begin{align*} p(x_n \mid x_1, \ldots, x_{n-1}) &= \frac{p(x_1, \ldots, x_n)}{p(x_1, \ldots, x_{n-1})} \\ &= \frac{\prod_{i=1}^n f_i(x_i, x_{\pi_i})}{\prod_{i=1}^{n-1} f_i(x_i, x_{\pi_i})} \\ &= f_n(x_n, x_{\pi_n}) \end{align*} $$

The last (EDIT:second*) equality follows from $x_n$ not being a parent of any node. Now, I wish to show that $p(x_n \mid x_1, \ldots, x_{n-1}) = p(x_n \mid x_{\pi_n})$ and it is intuitive to me because no other node but the parents of $x_n$ have any sort of bearing on $p(x_n \mid x_1, \ldots, x_{n-1}) = f_n(x_n, x_{\pi_n})$. But how would I show this formally? The rest of the result follows quickly from induction since we can just remove $x_n$ from the graph.

$\endgroup$
  • $\begingroup$ Unfortunately this approach won't work, because you haven't shown why $\tilde{p}(x_1, \dots, x_{n-1}) = \prod_{i=1}^{n-1} f_i(x_i, x_{\pi_i})$ is the same as $p(x_1, \dots, x_{n-1}) = \sum_{x_n} p(x_1, \dots, x_n)$. Both $p$ and $\tilde{p}$ are valid probability distributions, but it's not clear why the latter is necessarily the marginal of the former. $\endgroup$ – tddevlin Mar 7 at 8:31
1
$\begingroup$

The notation is quite horrendous but I think this is what you're looking for. I recommend trying this out on a small example of say 4 nodes to get a more concrete feeling for what's going on. I briefly explain the following equations at the bottom. $$ \begin{align} p(x_i | x_{\pi_i}) & = \frac{p(x_i, x_{\pi_i})}{p(x_{\pi_i})} \\ & = \frac{\sum_{ \{x_j \mid\ j \neq i, \ j \notin \pi_i \} } p(x_1, \dots, x_n)}{\sum_{ \{x_j \mid \ j \notin \pi_i \} } p(x_1, \dots, x_n)} \\ & = \frac{\sum_{ \{x_j \mid\ j \neq i, \ j \notin \pi_i \} } \prod_{k=1}^n f_k(x_k, x_{\pi_k}) }{\sum_{ \{x_j \mid \ j \notin \pi_i \} } \prod_{k=1}^n f_k(x_k, x_{\pi_k})} \\ & = \frac{f_i(x_i, x_{\pi_i}) \sum_{ \{x_j \mid\ j \neq i, \ j \notin \pi_i \} } \prod_{k\neq i} f_k(x_k, x_{\pi_k}) }{\sum_{ \{x_j \mid \ j \notin \pi_i \} } \prod_{k=1}^n f_k(x_k, x_{\pi_k})} \\ & = \frac{f_i(x_i, x_{\pi_i}) \phi(x_{\pi_i}) }{\phi(x_{\pi_i})} \\ & = f_i(x_i, x_{\pi_i}). \end{align} $$

  1. Definition of conditional probability.
  2. Marginalize the full joint distribution.
  3. Definition of the joint distribution as the product of the factors.
  4. Upper sum doesn't depend on $x_i$ or $x_{\pi_i}$ so we can factor out $f_i$.
  5. Push the sums into the product one at a time and use the fact that each $f_k(x_k, x_{\pi_k})$ sums to one over $x_k$. In the end you're left with some function $\phi(x_{\pi_i})$. This happens in both the numerator and the denominator.
  6. Cancel the $\phi$'s.
$\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.