# Heuristic Factors

*15 September 2017*

In a typical sequential Monte Carlo (SMC) setting, we target a sequence of densities \((\pi_t(x_{1:t}))_{t = 1}^T\) (defined on a sequence of supports \((\mathcal X_{1:t}))_{t = 1}^T\)) while assuming we can only evaluate their unnormalized version \(\gamma_t(x_{1:t}) = Z_t \pi_t(x_{1:t})\) where the normalizing constant is \(Z_t = \int_{\mathcal X_{1:t}} \gamma_t(x_{1:t}) \,\mathrm dx_{1:t}\).

Given an initial proposal distribution \(q_1(x_1)\) and a sequence of proposal distributions \((q_t(x_t \given x_{1:t - 1}))_{t = 2}^T\) 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 \(\pi_t\) isn’t the best thing to do if we want to target just \(\pi_T\).
In this case we *might* want to use heuristic factors.
Heuristic factors are a sequence of positive functions \((h_t(x_{1:t}))_{t = 1}^T\) which modify the sequence of normalized and unnormalized targets as follows:

- Unnormalized targets \(\gamma_t'(x_{1:t}) := \gamma_t(x_{1:t}) \cdot \prod_{\tau = 1}^t h_\tau(x_{1:\tau})\),
- Normalized targets \(\pi_t'(x_{1:t}) := \gamma_t'(x_{1:t}) / Z_t'\),
- Normalization constants \(Z_t' := \int_{\mathcal X_{1:t}} \gamma_t'(x_{1:t})\).
We require \(\prod_{t = 1}^T h_t(x_{1:t}) = 1\) so that we preserve \(\pi_T = \pi_T'\), \(\gamma_T = \gamma_T'\) and \(Z_T = Z_T'\).

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]