Recursion for conditional distributions: The Baum-Welch Algorithm

The recursion of section 1.3 have serious underflow problems in numerical applications, and $\alpha$ and $\beta$ do not represent useful variables. Introduce forward and backward variables $\tilde\alpha$ and $\tilde\beta$ :

$$\boxed{ \tilde\alpha_t(s) = p(s_t=s\vert x^t) }$$ (13)

which allows to write

$$\tilde\alpha_t(s_t) = p(s_t\vert x^t) = \frac{1}{p(x^t)} p(s_t,x^t)$$

$$= \frac{1}{p(x^t)}\sum_{s_{t-1}} \psi(s_t,s_{t-1},x_t) p(s_{t-1},x^{t-1})$$

$$= \frac{p(x^{t-1})}{p(x^t)} \sum_{s_{t-1}} \psi(s_t,s_{t-1},x_t) p(s_{t-1}\vert x^{t-1})$$

so the recursion is

$$\tilde\alpha_t(s) = \frac{1}{\kappa_t} \sum_{s^\prime} \psi(s,s^\prime,x_t) \, \tilde\alpha_{t-1}(s^\prime)$$ (14)

$$\kappa_t = \frac{p(x^t)}{p(x^{t-1})} = p(x_t\vert x^{t-1}) \quad .$$ (15)

The new variable $\kappa_t$ is just the normalizing constant for $\sum_{s^\prime} \psi(s,s^\prime,x_t)\tilde\alpha_{t-1}(s^\prime)$ , therefore

$$\tilde a_t(s) = \sum_{s^\prime} \psi(s,s^\prime,x_t) \, \tilde\alpha_{t-1}(s^\prime)$$ (16)

$$\kappa_t = \sum_s a_t(s)$$ (17)

$$\tilde\alpha_t(s) = \frac{1}{\kappa_t} \, a_t(s) \quad .$$ (18)

Next, normalise $\beta$ as follows:

$$\boxed{ \tilde\beta_t(s^\prime) = \frac{p(x^{[t+1}\vert s_t=s^\prime)}{p(x^{[t+1}\vert x^t)} }$$ (19)

and, using (19) and (12) the backward recursion for $\tilde\beta$ becomes

$$\tilde\beta_t(s^\prime) = \frac{1}{p(x^{[t+1}\vert x^t)} \, \beta_t(s^\prime)$$ (20)

$$= \frac{p(x^{[t}\vert x^{t-1})}{p(x^{[t+1}\vert x^t)} \sum_s \psi(s,s^\prime,x_{t+1}) \,\tilde\beta_{t+1}(s)$$ (21)

Because of

$$p(x^{[t}\vert x^{t-1}) = \frac{p(x)}{p(x^{t-1})} = \frac{p(x^{[t+1}\vert x^t) \, p(x^t)}{p(x^{t-1})}$$

$$= p(x^{[t+1}\vert x^t) \, p(x_t\vert x^{t-1}) = \kappa_t \, p(x^{[t+1}\vert x^t)$$

the recursion becomes

$$\boxed{ \tilde\beta_t(s^\prime) = \kappa_t \sum_s \psi(s,s^\prime,x_{t+1}) \,\tilde\beta_{t+1}(s) }$$ (22)

Since

$$\tilde\beta_{t-1}(s_{T-1}) = \frac{x_T\vert s_{T-1}}{p(x_T\vert x^{t-1})}$$

$$= \frac{\int ds_T p(x_T\vert s_T) \, p(s_T\vert s_{T-1})}{\kappa_T}$$

the backward iteration is properly initialised by defining

$$\tilde\beta_T(s_T) = 1$$ (23)

Finally, the desired quantities $\gamma$ and $\Omega$ in the M-step are related to $\tilde\alpha$ and $\tilde\beta$ via

$$\gamma_t(s_t) = p(s_t\vert x) = \frac{p(s_t x^t x^{[t+1})}{p(x)} = \frac{p(x^{[t+1}\vert s_t) \, p(s_t\vert x^t) \, p(x^t)}{p(x)}$$

$$= \frac{p(x^{[t+1}\vert s_t)}{p(x^{[t+1}\vert x^t)} \, p(s_t\vert x^t) = \tilde\alpha_t(s_t) \, \tilde\beta_t(s_t)$$

and

$$\Omega_t(s_{t-1}s_t) = p(s_{t-1}s_t\vert x) = \frac{1}{p(x)} \, p(s_{t-1}s_tx^{t-1}x^{[t})$$

$$= \frac{1}{p(x)} \, p(x^{t-1}) \, p(x^t\vert s_t) \, p(x^{[t+1}\vert s_t)$$

$$= \frac{1}{\kappa_t} \, \tilde\alpha_{t-1}(s_{t-1}) \, p(s_t\vert s_{t-1}) \, p(x_t\vert s_t) \, \tilde\beta(s_t) \quad .$$