Towards SMC: Sequential Importance Sampling

Review of Importance Sampling for Sequential Data

At time $t=1$ we receive data $x_1$, and at time $t>1$ we receive data $x_t$. Let ${\mathbf{x}}_t=(x_1,\dots ,x_t)$. Suppose that at each time $t$ our aim is to do inference based on the current posterior distribution ${\gamma }_t({\mathbf{x}}_t)$. Such inference could, for instance, be to approximate the current posterior expectation of a function of $h({\mathbf{x}}_t)$, i.e. ${\mathbb{E}}_{{\gamma }_t({\mathbf{x}}_t)}[h({\mathbf{x}}_t)]$. Importance sampling works as follows:

• Sample ${\mathbf{x}}_t^{(i)}$ from an importance distribution $q_t({\mathbf{x}}_t)$ for $i=1,\dots ,N$.
• Compute the unnormalized importance weights and normalize them, to find the normalized importance weights $${\tilde{w}}_t({\mathbf{x}}_t^{(i)})=\frac{\widetilde{{\gamma }_t}({\mathbf{x}}_t^{(i)})}{q_t({\mathbf{x}}^{(i)})}\text{and}{w}_t({\mathbf{x}}_t^{(i)})=\frac{{\tilde{w}}_t({\mathbf{x}}_t^{(i)})}{\sum _{j=1}^N{\tilde{w}}_t({\mathbf{x}}_t^{(i)})}\text{for }i=1,\dots ,N$$
• Use the importance weghts to approximate the expectation. $${\mathbb{E}}_{{\gamma }_t({\mathbf{x}}_t)}[h({\mathbf{x}}_t)]\approx \sum _{i=1}^N{w}_t({\mathbf{x}}_t^{(i)})h({\mathbf{x}}_t^{(i)})$$

Sequential Importance Sampling

Sequential Importance Sampling has two main differences with respect to Importance Sampling for sequential data.

• Importance distribution is autoregressive: $$q_t({\mathbf{x}}_t)=\underset{\begin{array}{c}\text{Importance}\\ \text{ Distribution}\\ \text{at time }t-1\end{array}}{\underbrace{q_{t-1}(x_{1:t-1})}}{q}_t(x_t\mid x_{1:t-1})$$
• Samples at time $t$ are found recursively using the samples at time $t-1$. Previously, at each time $t$ we were sampling ${\mathbf{x}}_t^{(1)},\dots ,{\mathbf{x}}_t^{(N)}$ from $q({\mathbf{x}}_t)=q_t(x_1,\dots ,x_t)$. Essentially, when we were sampling ${\mathbf{x}}_t^{(i)}$, we were sampling each component $x_1^{(i)},\dots ,x_t^{(i)}$ from time $1$ to $t$. In Sequential Importance Sampling, instead, at each time step $t$ we are sampling $x_t^{(1)},\dots ,x_t^{(N)}$ from $q_t(x_t\mid {\mathbf{x}}_{t-1})$, and append these values to ${\mathbf{x}}_{t-1}^{(1)},\dots ,{\mathbf{x}}_{t-1}^{(N)}$. In other words, for each sample $i$ we are sampling only the $t^{\text{th}}$ component $x_t^{(i)}$ rather than the whole history.
• Importance weights are also computed recursively. $$\begin{array}{rl}{\tilde{w}}_t({\mathbf{x}}_t^{(i)})& =\frac{{\tilde{\gamma }}_t({\mathbf{x}}_t^{(i)})}{q_t({\mathbf{x}}_t^{(i)})}\\ & =\frac{{\tilde{\gamma }}_t({\mathbf{x}}_t^{(i)})}{q_{t-1}({\mathbf{x}}_{t-1}^{(i)})q_t(x_t^{(i)}\mid {\mathbf{x}}_{t-1}^{(i)})}& & \text{Def of conditional probability}\\ & =\frac{{\tilde{\gamma }}_t({\mathbf{x}}_t^{(i)})}{q_{t-1}({\mathbf{x}}_{t-1}^{(i)})q_t(x_t^{(i)}\mid {\mathbf{x}}_{t-1}^{(i)})}\cdot \frac{{\tilde{\gamma }}_{t-1}({\mathbf{x}}_{t-1}^{(i)})}{{\tilde{\gamma }}_{t-1}({\mathbf{x}}_{t-1}^{(i)})}& & \text{Multiplying by }1\\ & =\frac{{\tilde{\gamma }}_{t-1}({\mathbf{x}}_{t-1}^{(i)})}{q_{t-1}({\mathbf{x}}_{t-1}^{(i)})}\frac{{\tilde{\gamma }}_t({\mathbf{x}}_t^{(i)})}{{\tilde{\gamma }}_{t-1}({\mathbf{x}}_{t-1}^{(i)})q_t(x_t^{(i)}\mid {\mathbf{x}}_{t-1}^{(i)})}& & \text{Rearranging terms}\\ & ={\tilde{w}}_{t-1}({\mathbf{x}}_{t-1}^{(i)})\cdot \frac{{\tilde{\gamma }}_t({\mathbf{x}}_t^{(i)})}{{\tilde{\gamma }}_{t-1}({\mathbf{x}}_{t-1}^{(i)})q_t(x_t^{(i)}\mid {\mathbf{x}}_{t-1}^{(i)})}& & \text{Def of }{\tilde{w}}_{t-1}({\mathbf{x}}_{t-1}^{(i)})\end{array}$$

Basically to obtain the next set of weights ${\tilde{w}}_t({\mathbf{x}}_t^{(i)})$ we “extend” the posterior in the numerator to include $x_t^{(i)}$ by multiplying the previous weight by $\frac{{\tilde{\gamma }}_t({\mathbf{x}}_t^{(i)})}{{\tilde{\gamma }}_{t-1}({\mathbf{x}}_{t-1}^{(i)})}$, and we “move” the importance distribution on the denominagor one step ahead by multiplying it by $q_t(x_t^{(i)}\mid {\mathbf{x}}_{t-1}^{(i)})$.

SIS Issue: One issue with Sequential Importance Sampling is that in practice as $t$ grows, all normalized weights tend to $0$ except for one large weight which tends to $1$. In these cases then the approximation is quite poor because it is essentially approximated using one sample (i.e. the sample of the non-degenerate weight). This effect is known as weight degeneracy. This issue is solve by Sequential Monte Carlo (SMC).