Tuan Anh Le

Heuristic Factors

15 September 2017

In a typical sequential Monte Carlo (SMC) setting, we target a sequence of densities (defined on a sequence of supports ) while assuming we can only evaluate their unnormalized version where the normalizing constant is .

Given an initial proposal distribution and a sequence of proposal distributions from which we can sample and whose densities we can evaluate, the SMC algorithm proceeds by the propose-weight-resample loop. The full SMC algorithm using this notation is in the first part of this note.

Since SMC is a greedy algorithm, sampling according to the original sequence of targets isn’t the best thing to do if we want to target just . In this case we might want to use heuristic factors. Heuristic factors are a sequence of positive functions which modify the sequence of normalized and unnormalized targets as follows:

Recall that when using an original sequence of targets, the intermediate weights are calculated as follows: \begin{align} w_t = \frac{\gamma_t(x_{1:t})}{\gamma_{t - 1}(x_{1:t - 1}) q_t(x_t \given x_{1:t - 1})}. \end{align} If we include the heuristic factors, the weights would be calculated as follows: \begin{align} w_t’ &= \frac{\gamma_t’(x_{1:t})}{\gamma_{t - 1}’(x_{1:t - 1}) q_t(x_t \given x_{1:t - 1})} \\ &= \frac{\gamma_t(x_{1:t}) \cdot \prod_{\tau = 1}^t h_\tau(x_{1:\tau})}{\gamma_{t - 1}(x_{1:t - 1}) \cdot \left(\prod_{\tau = 1}^{t - 1} h_\tau(x_{1:\tau})\right) \cdot q_t(x_t \given x_{1:t - 1})} \\ &= w_t h_t(x_{1:t}). \end{align}

Example

[back]