Importance sampling

Skill positionModule 2 of 3 · Topic 1 of 5

2.1 Importance sampling

—Lab score— / 100Total XP—Streak—

Estimating with weighted guesses

Often you want an average under a distribution $p$ that you cannot draw from. In filtering, $p$ is the belief about the hidden state after seeing today's data. The trick of importance sampling is to draw from an easy distribution $g$ instead, called the proposal, and to repair the mismatch with weights. A point $x_i$ that the proposal produces too often gets a small weight, and one it produces too rarely gets a large weight: $w_i=p(x_i)/g(x_i)$ . Usually $p$ is known only up to a constant, so the weights are divided by their sum, which makes them add to $1$ .

w_i=\frac{p(x_i)}{g(x_i)},\quad \tilde w_i=\frac{w_i}{\sum_j w_j},\quad E_p[f]\approx\sum_i\tilde w_i\,f(x_i),\quad \mathrm{ESS}=\frac{1}{\sum_i\tilde w_i^{2}}

(1)

In a filter, the proposal is the prediction (where the state is likely to be before seeing the data) and the target is the belief after the data. Their ratio is just the likelihood of the observation, so the weight of a particle is how well it explains $y$ . The effective sample size, ESS, tells how many equally weighted draws the weighted sample is worth. It equals $N$ when all weights are equal and $1$ when one point carries everything. When ESS is small the estimate rests on a few points and is noisy. This happens when the proposal misses the places where the target has most of its mass, for example when the data is a big surprise.

Four particles and one observationFour draws from the prediction are

x=-1,0,1,2

, and we observe

y=1

with noise variance

r=1

. The unnormalised weights are

e^{-(1-x)^2/2}=0.135,\ 0.607,\ 1,\ 0.607

, which sum to

2.348

. The normalised weights are

0.058,\ 0.258,\ 0.426,\ 0.258

. The weighted mean is

0.885

and the weighted second moment is

1.516

, so the variance is

1.516-0.885^{2}=0.734

. The effective sample size is

1/(0.058^2+0.258^2+0.426^2+0.258^2)=3.14

out of

4

Weights repair the mismatch: draw from an easy $g$ , weight by $p/g$ , divide by the sum.
In a filter the weight is the likelihood: the particle that explains the observation best gets the most weight.
Watch the ESS: $1/\sum\tilde w^{2}$ falls when a few points dominate, which is the warning sign of a poor proposal.

Lab · what's graded

A normalised weight15 pts
The weighted mean15 pts
The effective sample size15 pts
The weighted variance10 pts
A dangerous proposal10 pts
The steps of importance sampling10 pts
Match the vocabulary10 pts
Why weights are needed15 pts

0/ 8 answered

1Numeric answer15 ptsNot answered

The unnormalised weights of the four particles are $0.135,\ 0.607,\ 1,\ 0.607$ and they sum to $2.348$ . What is the normalised weight of the first particle? Give three decimals.

w =

accepted: ± 0.001

2Numeric answer15 ptsNot answered

The particles $x=-1,0,1,2$ have normalised weights $0.058,\ 0.258,\ 0.426,\ 0.258$ . What is the weighted mean $\sum\tilde w_i x_i$ ? Give three decimals.

m =

accepted: ± 0.003

3Numeric answer15 ptsNot answered

With normalised weights $0.058,\ 0.258,\ 0.426,\ 0.258$ , the sum of squared weights is $0.318$ . What is the effective sample size $1/\sum\tilde w_i^{2}$ ? Give two decimals.

ess =

accepted: ± 0.02

4Numeric answer10 ptsNot answered

The weighted second moment $\sum\tilde w_i x_i^{2}$ is $1.516$ and the weighted mean is $0.885$ . What is the weighted variance? Give three decimals.

v =

accepted: ± 0.004

5Choice10 ptsNot answered

Which proposal is most likely to give a tiny effective sample size?

6Order the steps10 ptsNot answered

Put the steps of self-normalised importance sampling in order.

Drag to reorder, or focus an item, press Space to lift it, the arrow keys to move it and Space to drop it.

1Divide each weight by the sum of the weights
2Draw points from the easy proposal
3Average the quantity with the normalised weights
4Compute a weight for each point: target over proposal

7Match10 ptsNot answered

Match each term with its meaning.

Pick the partner of each item on the left.

Proposal

Target

Importance weight

Effective sample size

8Explain in words15 ptsNot answered

In one or two sentences, explain why we must weight the draws by $p/g$ when we sample from the proposal $g$ instead of the target $p$ .

Graded on:The draws come from the wrong distribution, so some regions appear too often and others too rarelyThe weights p over g scale each point down or up to correct this0 / 400 characters

Math modeKeyboard or LaTeX inputTask 1 of 8 · Ctrl ⏎ to check

Importance sampling

Skill positionModule 2 of 3 · Topic 1 of 5

2.1 Importance sampling

—Lab score— / 100Total XP—Streak—

Estimating with weighted guesses

w_i=\frac{p(x_i)}{g(x_i)},\quad \tilde w_i=\frac{w_i}{\sum_j w_j},\quad E_p[f]\approx\sum_i\tilde w_i\,f(x_i),\quad \mathrm{ESS}=\frac{1}{\sum_i\tilde w_i^{2}}

(1)

Four particles and one observationFour draws from the prediction are

x=-1,0,1,2

, and we observe

y=1

with noise variance

r=1

. The unnormalised weights are

e^{-(1-x)^2/2}=0.135,\ 0.607,\ 1,\ 0.607

, which sum to

2.348

. The normalised weights are

0.058,\ 0.258,\ 0.426,\ 0.258

. The weighted mean is

0.885

and the weighted second moment is

1.516

, so the variance is

1.516-0.885^{2}=0.734

. The effective sample size is

1/(0.058^2+0.258^2+0.426^2+0.258^2)=3.14

out of

4

Weights repair the mismatch: draw from an easy $g$ , weight by $p/g$ , divide by the sum.
In a filter the weight is the likelihood: the particle that explains the observation best gets the most weight.
Watch the ESS: $1/\sum\tilde w^{2}$ falls when a few points dominate, which is the warning sign of a poor proposal.

Lab · what's graded

A normalised weight15 pts
The weighted mean15 pts
The effective sample size15 pts
The weighted variance10 pts
A dangerous proposal10 pts
The steps of importance sampling10 pts
Match the vocabulary10 pts
Why weights are needed15 pts

0/ 8 answered

1Numeric answer15 ptsNot answered

The unnormalised weights of the four particles are $0.135,\ 0.607,\ 1,\ 0.607$ and they sum to $2.348$ . What is the normalised weight of the first particle? Give three decimals.

w =

accepted: ± 0.001

2Numeric answer15 ptsNot answered

The particles $x=-1,0,1,2$ have normalised weights $0.058,\ 0.258,\ 0.426,\ 0.258$ . What is the weighted mean $\sum\tilde w_i x_i$ ? Give three decimals.

m =

accepted: ± 0.003

3Numeric answer15 ptsNot answered

With normalised weights $0.058,\ 0.258,\ 0.426,\ 0.258$ , the sum of squared weights is $0.318$ . What is the effective sample size $1/\sum\tilde w_i^{2}$ ? Give two decimals.

ess =

accepted: ± 0.02

4Numeric answer10 ptsNot answered

The weighted second moment $\sum\tilde w_i x_i^{2}$ is $1.516$ and the weighted mean is $0.885$ . What is the weighted variance? Give three decimals.

v =

accepted: ± 0.004

5Choice10 ptsNot answered

Which proposal is most likely to give a tiny effective sample size?

6Order the steps10 ptsNot answered

Put the steps of self-normalised importance sampling in order.

Drag to reorder, or focus an item, press Space to lift it, the arrow keys to move it and Space to drop it.

1Divide each weight by the sum of the weights
2Draw points from the easy proposal
3Average the quantity with the normalised weights
4Compute a weight for each point: target over proposal

7Match10 ptsNot answered

Match each term with its meaning.

Pick the partner of each item on the left.

Proposal

Target

Importance weight

Effective sample size

8Explain in words15 ptsNot answered

In one or two sentences, explain why we must weight the draws by $p/g$ when we sample from the proposal $g$ instead of the target $p$ .

Graded on:The draws come from the wrong distribution, so some regions appear too often and others too rarelyThe weights p over g scale each point down or up to correct this0 / 400 characters

Math modeKeyboard or LaTeX inputTask 1 of 8 · Ctrl ⏎ to check

Importance sampling

Estimating with weighted guesses

Lab · what's graded

Log in to run your code.

Importance sampling

Estimating with weighted guesses

Lab · what's graded

Log in to run your code.