Page 127 - Classification Parameter Estimation & State Estimation An Engg Approach Using MATLAB

116 STATE ESTIMATION

Here, use has been made of the assumption that each measurement z(i)
only depends on x(i). P(Z(i)) follows from summation over all possible
state sequences:

X
PðZðiÞÞ ¼ PððXðiÞ; ZðiÞÞ ð4:58Þ
all XðiÞ
i
Since there are K different state sequences, the direct implementation of
(4.57) and (4.58) requires on the order of (i þ 1)K iþ1 operations. Even
for modest values of i, the number of operations is already impractical.
A more economical approach is to calculate P(Z(i)) by means of a
recursion. For that, consider the probability P(Z(i), x(i)). This probabil-
ity can be calculated from the previous time step i 1 using the follow-
ing expression:

K
X
PðZðiÞ;xðiÞÞ ¼ PðZðiÞ;xðiÞ;xði 1ÞÞ
xði 1Þ¼1
K
X
¼ PðzðiÞ;xðiÞjZði 1Þ;xði 1ÞÞPðZði 1Þ;xði 1ÞÞ
xði 1Þ¼1
K
X
¼ PðzðiÞ;xðiÞjxði 1ÞÞPðZði 1Þ;xði 1ÞÞ
xði 1Þ¼1
K
X
¼ PðzðiÞjxðiÞÞ P t ðxðiÞjxði 1ÞÞPðZði 1Þ;xði 1ÞÞ
xði 1Þ¼1
ð4:59Þ

The recursion must be initiated with P(z(0), x(0)) ¼ P 0 (x(0))P z (z(0)jx(0)).
The probability P(Z(i)) can be retrieved from P(Z(i), x(i)) by:

K
X
PðZðiÞÞ ¼ PðZðiÞ; xðiÞÞ ð4:60Þ
xðiÞ¼1
6
The so-called forward algorithm uses the array F(i, x(i)) ¼ P(Z(i), x(i))
to implement the recursion:

6
The adjective ‘forward’ refers to the fact that the algorithm proceeds forwards in time. Section
4.3.3 introduces the backward algorithm.