Page 264 - Contributed Paper Session (CPS) - Volume 4

CPS2220 David Degras et al.
3.1 E-step
Given a current estimate of , the E-step consists in taking the
̂
conditional expectation of the complete data log-likelihood given the
̂
observed data 1: while assuming that is the true model parameter. This
yields the −function
̂
(; ) = ̂ (log ()| 1: )

which serves as an approximation to the (incomplete data) log-likelihood
function. The calculation of (; ) requires the following quantities:
̂

= ̂ ( = | ), = ̂ ( ′ | = , ),
| 1: | 1:
()
= ̂ ( = , = | ), = ̂ ( ′ | = , ), (4)
−1,| −1 1: −1| −1 −1 1:
= ̂ ( | = | ), = ̂ ( ′ | = , ),
| 1: ,−1| −1 1:

where = − 1 for prediction, = for filtering, and = for
smoothing. The quantities in (4) can be computed approximately with the Kim
filtering algorithm, also known as Hamilton filtering [7, 10]. In essence, the
calculation of (4) relies on a forward-backward algorithm similar to the Kalman
filter and Rauch-Tung-Striebel smoother for SSMs. Here however, exact
calculations in the filtering step require conditioning at each time on all
possible histories of the switching variables , … , , meaning that the

1
computational cost grows exponentially with time, which is not feasible.
Instead, at each time the Kim filter only considers the recent history of the
2
switching variables (say, the possible values of ( −1 , )) to calculate

relevant probabilities and expectations, which it then collapses to
(approximately) recover (4) (for = ). Further approximations are required
in the smoothing step to make calculations tractable. In practice the Kim
filter/smoother saves considerable computational time and provides accurate
approximations to the −function and the log-likelihood, at least in low
dimensional settings. Up to additive constants, the −function expresses as

1
̂
−1
′
−1
(; ) = ∑ ∑ (log| | − ( ′ − 2 + ′ ))

|
|
|
2
=1 =1

1
−1
−1
′
+ ∑ ∑ (log| | − ( − 2 + () ′ ))

2 | | ,−1| −1|
=2 =1
(5)
1
′
−1
′
+ ∑ | (|∑ | − ∑ −1 ( 1| − 2x 1| + ))

2
=1

+ ∑ log + ∑ ∑ ∑ log .
1| −1,|
=1 =2 =1 =1
253 | I S I W S C 2 0 1 9