Pattern Recognition and Machine Learning

628 13. SEQUENTIAL DATA

From the product rule, we then have

p(x 1 ,...,xn)=

∏n

m=1

cm (13.57)

and so

α(zn)=p(zn|x 1 ,...,xn)p(x 1 ,...,xn)=

(n

∏

m=1

cm

)

α̂(zn). (13.58)

We can then turn the recursion equation (13.36) forαinto one for̂αgiven by

cn̂α(zn)=p(xn|zn)

∑

zn− 1

̂α(zn− 1 )p(zn|zn− 1 ). (13.59)

Note that at each stage of the forward message passing phase, used to evaluateα̂(zn),

we have to evaluate and storecn, which is easily done because it is the coefficient

that normalizes the right-hand side of (13.59) to givêα(zn).

We can similarly define re-scaled variableŝβ(zn)using

β(zn)=

( N

∏

m=n+1

cm

)

̂β(zn) (13.60)

which will again remain within machine precision because, from (13.35), the quan-

titieŝβ(zn)are simply the ratio of two conditional probabilities

̂β(zn)= p(xn+1,...,xN|zn)

p(xn+1,...,xN|x 1 ,...,xn)

. (13.61)

The recursion result (13.38) forβthen gives the following recursion for the re-scaled

variables

cn+1̂β(zn)=

∑

zn+1

̂β(zn+1)p(xn+1|zn+1)p(zn+1|zn). (13.62)

In applying this recursion relation, we make use of the scaling factorscnthat were

previously computed in theαphase.

From (13.57), we see that the likelihood function can be found using

p(X)=

∏N

n=1

cn. (13.63)

Similarly, using (13.33) and (13.43), together with (13.63), we see that the required
Exercise 13.15 marginals are given by

γ(zn)=α̂(zn)β̂(zn) (13.64)

ξ(zn− 1 ,zn)=cn̂α(zn− 1 )p(xn|zn)p(zn|z− 1 )̂β(zn). (13.65)