For a bayes network which has $n$ nodes, $X_1, X_2, ... , X_n$. Is there any efficient way to calculate $P(X_i|X_1,X_2,...,X_{i-1},X_{i+1},...X_n)$, without constructing the full joint distribution?
1
-
$\begingroup$ I think I have found something. But the site doesn't allow me to answer my own question until tomorrow. I will post my thought tomorrow. $\endgroup$– xdaiApr 24, 2014 at 22:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Well, it is almost one month late but better than nothing. Here is my thought.
Given $x_1, ..., x_{i-1}, x_{i+1}, ... , x_n$, \begin{align*} P(X_i|x_1, ..., x_{i-1}, x_{i+1}, ... , x_n) = \alpha P(x_1, ..., x_{i-1}, X_i, x_{i+1}, ... , x_n) \end{align*} where $\alpha=\frac{1}{P(x_1, ..., x_{i-1}, x_{i+1}, ... , x_n)}$ is a constant normalization factor.
Let $C$ be the set of $X_i$ and all its children, $Q$ be the set of all the other nodes, $F_k$ be the CPD function on node $X_k$. The full joint distribution $P(X_1, ..., X_n)$ can be factorized over all the nodes: \begin{align*} P(X_1, ..., X_n) = \prod_{X_m \in C} F_m \prod_{X_n \in Q} F_n \end{align*} However, given $x_1, ..., x_{i-1}, x_{i+1}, ... , x_n$, notice that $F_n$, where $X_n \in Q$, are constants, therefore $\beta = \prod_{X_n \in Q} F_n$ is also a constant, so \begin{align*} P(X_i|x_1, ..., x_{i-1}, x_{i+1}, ... , x_n) = \alpha\beta \prod_{X_m \in C} F_m \end{align*} which means what we need to do is to calculate $\prod_{X_m \in C} F_m$ for every possible value of $X_i$ and then normalize them.