Backward Algorithm

#maths The backward algorithm is a mirror of the Forward Algorithm, where instead of computing the likelihood of being in a certain state given the observations that came before it, we compute the likelihood of being in a certain state knowing future observations.

$$\begin{array}{rlr}\text{Initialization:}& {\beta }_T(X_i)=1,& 1\le i\le N\\ \text{Recursion:}& {\beta }_{t-1}(i)=\sum _{j=1}^N{\beta }_t(X_j)P(X_j|X_i)P(Y^t|X_j),& 1\le t\le T-1,1\le i\le N\\ \text{Termination:}& P(O)=\sum _{j=1}^N\pi [j]P(Y^0|X_j){\beta }_1(j),& \end{array}$$

Example

Let’s say we got observer $O=\{😫,😃\}$. To compute the likelihood of this observation with the backward algorithm, we will have:

$$\begin{array}{rl}\underline{Initialization:}& \\ & \\ t=1:& {\beta }_2(☀\stackrel{◯}{R})=1,\\ & {\beta }_2(☁\stackrel{◯}{R})=1,\\ & {\beta }_2(⛈)=1\\ & \\ \underline{Recursion:}& \\ & \\ t=2:& {\beta }_1(☀\stackrel{◯}{R})=[{\beta }_2(☀\stackrel{◯}{R})P(☀\stackrel{◯}{R}|☀\stackrel{◯}{R})+{\beta }_2(☁\stackrel{◯}{R})P(☀\stackrel{◯}{R}|☁\stackrel{◯}{R})+{\beta }_1(⛈)P(☀\stackrel{◯}{R}|⛈)]P(😃|☀\stackrel{◯}{R})\\ & {\beta }_1(☁\stackrel{◯}{R})=[{\beta }_2(☀\stackrel{◯}{R})P(☁\stackrel{◯}{R}|☀\stackrel{◯}{R})+{\beta }_2(☁\stackrel{◯}{R})P(☁\stackrel{◯}{R}|☁\stackrel{◯}{R})+{\beta }_2(⛈)P(☁\stackrel{◯}{R}|⛈)]P(😃|☁\stackrel{◯}{R})\\ & {\beta }_1(⛈)=[{\beta }_2(☀\stackrel{◯}{R})P(⛈|☀\stackrel{◯}{R})+{\beta }_2(☁\stackrel{◯}{R})P(⛈|☁\stackrel{◯}{R})+{\beta }_2(⛈)P(⛈|⛈)]P(😃|⛈)\\ & \\ \underline{Termination:}& \\ & \\ P(O)=& {\beta }_1(☀\stackrel{◯}{R})\pi [☀\stackrel{◯}{R}]P(😫|☀\stackrel{◯}{R})\\ +& {\beta }_1(☁\stackrel{◯}{R})\pi [☁\stackrel{◯}{R}]P(😫|☁\stackrel{◯}{R})\\ +& {\beta }_1(⛈)\pi [⛈]P(😫|⛈)\end{array}$$