Pattern Recognition and Machine Learning

626 13. SEQUENTIAL DATA

Figure 13.15 A simplified form of fac-
tor graph to describe the hidden Markov
model.

h fn

z 1 zn− 1 zn

To derive the alpha-beta algorithm, we denote the final hidden variablezNas

the root node, and first pass messages from the leaf nodehto the root. From the

general results (8.66) and (8.69) for message propagation, we see that the messages

which are propagated in the hidden Markov model take the form

μzn− 1 →fn(zn− 1 )=μfn− 1 →zn− 1 (zn− 1 ) (13.47)

μfn→zn(zn)=

∑

zn− 1

fn(zn− 1 ,zn)μzn− 1 →fn(zn− 1 ) (13.48)

These equations represent the propagation of messages forward along the chain and

are equivalent to the alpha recursions derived in the previous section, as we shall

now show. Note that because the variable nodesznhave only two neighbours, they

perform no computation.

We can eliminateμzn− 1 →fn(zn− 1 )from (13.48) using (13.47) to give a recur-

sion for thef→zmessages of the form

μfn→zn(zn)=

∑

zn− 1

fn(zn− 1 ,zn)μfn− 1 →zn− 1 (zn− 1 ). (13.49)

If we now recall the definition (13.46), and if we define

α(zn)=μfn→zn(zn) (13.50)

then we obtain the alpha recursion given by (13.36). We also need to verify that

the quantitiesα(zn)are themselves equivalent to those defined previously. This

is easily done by using the initial condition (8.71) and noting thatα(z 1 )is given

byh(z 1 )=p(z 1 )p(x 1 |z 1 )which is identical to (13.37). Because the initialαis

the same, and because they are iteratively computed using the same equation, all

subsequentαquantities must be the same.

Next we consider the messages that are propagated from the root node back to

the leaf node. These take the form

μfn+1→fn(zn)=

∑

zn+1

fn+1(zn,zn+1)μfn+2→fn+1(zn+1) (13.51)

where, as before, we have eliminated the messages of the typez → fsince the

variable nodes perform no computation. Using the definition (13.46) to substitute

forfn+1(zn,zn+1), and defining

β(zn)=μfn+1→zn(zn) (13.52)