

![0_image_0.png](0_image_0.png)

Figure 4: A hypothetical situation where neither of the two particles γ i k is optimal. We would obtain eventually a higher likelihood configuration by interchanging 73 between particles.

## 3.5 Smc And Estimation Of The Map Trajectory

Like MCMC, SMC is a sampling method. Hence comments made in Section 3.1 about the eventual suboptimality of estimating the MAP trajectory from particles as arg max p ( γ [ , κ | Yo , κ )
also apply here. An hypothetical situation is shown in figure 4.

One obvious solution is to employ the SA "trick" and raise the proposal distribution to a power p ( γ k | ) γ . However, such a proposal will be peaked on a very few γ at each time slice. Consequently, most of the particles will become identical in time and the algorithm eventually degenerates to greedy filtering.

An algorithm for estimating the MAP trajectory from a set of SMC samples is recently proposed in the literature (Godsill, Doucet, & West, 2001). The algorithm relies on the observation that once the particles x [j] are sampled during the forward pass, one is left with a discrete distribution defined on the (discrete) support X 1 : K = Sk =1 X k . Here X k denotes is the support of the filtering distribution a time k and B is the Cartesian product between sets. Formally, X k is the set of distinct samples at time k and is given by X k = U,{xf,}}.

The distribution p ( X 1 : K | Y 1 : K ) 3 is Markovian because the original state transition model is Markovian, i.e., the posterior can be represented exactly by

$$p(X_{1:K}|y_{1:K})\propto\prod_{k=1}^{K}p(y_{k}\,|X_{k}\,)p(X_{k}\,|X_{k\,-\,1})$$

Consequently, one can find the best MAP trajectory arg maxp(X 1:K ) by using an algorithm that is analogous to the Viterbi algorithm for hidden Markov models (Rabiner, 1989).

However, this idea does not carry directly to the case when one applies Rao-Blackwellization. In general, when a subset of the hidden variables is integrated out, all time slices of the posterior p ( Γ 1 : κ | Y 1 : κ ) are coupled, where Γ 1 : κ = S k = 1 Γ k and Γ k = U i { γ ( γ } .

One can still employ a chain approximation and run Viterbi, (e.g.,  Cemgil & Kappen, 2002), but this does not guarantee to find arg max p ( Γ 1 : κ | Y 1 : κ ).

On the other hand, because γ [i] are drawn from a discrete set, several particles become identical so Γ k has usually a small cardinality when compared to the number of particles N. Consequently, it becomes feasible to employ SA or II on the reduced state space Γ 1 : κ ;
possibly using a proposal distribution that extends over several time slices L .