1
$\begingroup$

Lets say i have got a random variable $X$ with samples $x_t\sim X$ and density $p_X(x)$ and want to compute its mean via a moving average

$ \mu_{t+1}=(1-c)\mu_t + c x_t$

Assume, I can not observe $X$ directly, but instead a random variable $Y$ with density $p_Y(y)$ and samples $y_t\sim Y$. I would like to use importance sampling to compute the mean.

The naive approach is with $w_t=\frac{p_X(y_t)}{p_Y(y_t)}$

$ \mu_{t+1}=\left(1- cw_t\right)\mu_t + c w_t y_t$

This works, as long as the importance weights are small. However, if $w_t> \frac 1 c$ the above formula is obviously not correct any more. Is there a way to correct for this? It should be clear that as $w_t \rightarrow \infty$, $\mu_{t+1}\rightarrow y_t$

//edit the approach I tried to is using a sample-size estimate, but i am not sure this is correct.

The initial estimate has an estimated $1/c$ samples stored. Assuming we can interpret $w_t$ as sample-size correction, we can just try to average according to how many samples we got:

$ \mu_{t+1}=\left(1- \frac{w_t}{w_t + \frac 1 c -1}\right)\mu_t + \frac{w_t}{w_t+\frac 1 c-1} y_t$

for $w_t=1$ this gives the original update $\frac 1 c-1$ is the totally stored number of samples in the path after "forgetting the oldest"

but i have no idea how to show that this is correct, this is just an educated guess

$\endgroup$
0
$\begingroup$

I am answering myself. Still not with a proof, but with a better solution.

Assume first a slightly different setup, where instead of a single number $y_t$, we get a sample average $\bar{y}_t$ from $n_t$ samples. Clearly, if $n_t$ is large, we would like to trust it a lot and unlearn much of the previous samples. if afterwards, $n_{t+1}$ is small, we would not want to unlearn the good sample quickly.

The correct way to handle this is to have two variables: one which is an exponentially decaying sum of the number of samples

$N_{t+1}= (1-c) N_t + n_t$ Note that when $n_t=1$ for all $t$, this will converge to $N=1/c$.

The update of the mean $\mu_{t+1}$ is just the correctly weighted average of two means with different number of samples: $\mu_{t+1}=(1-\frac {n_t}{N_{t+1}}) \mu_t + \frac {n_t}{N_{t+1}} \bar{y}_t$

The same now holds trivially when replacing $n_t$ with $w_t$.

I have no doubt about the $\mu_{t+1}$ update and it also makes sense with importance sampling. I am not sure about the $N_t$, but I think it is probably hard to come up with a perfect justification for any type of exponential moving average.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.