0
$\begingroup$

I was referring to this wiki article related to forward and backward algorithm

Actually, I didn't get this part $ \frac{P(o_1,o_2..o_T,X_t=x_i|\pi)}{P(o_1,o_2..o_T|\pi)} = \frac{f_{0:t}(i)*b_{t:T}(i)}{\prod_{s=1}^{T}c_s} $

where f denotes the forward algorithm and b denotes the backward algorithm. I didn't get how the probability became the factor of the two. I couldn't derive it. I tried to use chain rule of probability but somehow couldn't derive it. Any suggestions?

  • 0
    Here is a suggestion: make your post self-contained. Here is another one: show what you have done (for example, surely you replaced every factor in the RHS by its definition to see what was the result?).2012-07-10

1 Answers 1

1

Let $o_i^j=\{o_i,o_{i+1},\ldots,o_j\}$. By the chain rule for probability,

\begin{align*} \frac{P(o_1^T,X_t|\pi)}{P(o_1^T|\pi)}&=\frac{P(o_1^t,X_t|\pi)}{P(o_1^t|\pi)}\frac{P(o_{t+1}^T|\pi,o_1^t,X_t)}{P(o_{t+1}^T|\pi,o_1^t)}\\ &=\frac{P(o_1^t,X_t|\pi)}{P(o_1^t|\pi)}\frac{P(o_{t+1}^T|\pi,o_1^t,X_t)}{\sum_xP(X_t=x)P(o_{t+1}^T|\pi,o_1^t,X_t=x)}\\ &=\frac{P(o_1^t,X_t|\pi)}{P(o_1^t|\pi)}\frac{P(o_{t+1}^T|X_t)}{\sum_xP(X_t=x)P(o_{t+1}^T|\pi,X_t=x)}\\ &=\frac{P(o_1^t,X_t|\pi)}{P(o_1^t|\pi)}\frac{P(o_{t+1}^T|X_t)}{P(o_{t+1}^T|\pi)}\\ &=\frac{f_{0:t}(i)}{\prod_{s=1}^tc_s}\frac{b_{t:T}(i)}{\prod_{s=t+1}^Tc_s}, \end{align*} by definition. The third equality follows from the conditional independence of $o_{t+1}^T$ and $\{\pi,o_1^t\}$ given $X_t$.

  • 0
    @user34790 We have conditioning on the state $X_t$ above, which "links" the observations $o_1^t$ and $o_{t+1}^T$ (see [figure](http://bib.oxfordjournals.org/content/7/1/86/F10.small.gif)). This property - that $X_t$ "blocks" any path from $o_1^t$ to $o_{t+1}^T$ - is formally known as d-separation and implies conditional independence (for general [Bayesian networks](http://en.wikipedia.org/wiki/Bayesian_network)) given the blocking random variable. For a more detailed exposition, see [here](http://www.cse.ust.hk/bnbook/pdf/l03.h.pdf).2012-07-10