Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [importance-sampling]

Importance sampling is a variance reduction technique to approximate integrals/expectations which are not directly computable.

1
vote
2answers
39 views

in reinforcement learning off policy mc may not work

I noticed off-policy mc prediction(or control) will not work, as being descripted by boxed algorithm in page 110 of the book "reinforcement learning an introduction". The weight W should before C's(...
1
vote
1answer
46 views

Generalization performance in Bayesian errors-in-covariates model

I'm working on a model with this basic structure: The square nodes are data, and the round nodes are parameters and/or latent variables. The left plate represents the "training observations" we ...
8
votes
1answer
96 views

Would an “importance Gibbs” sampling method work?

I suspect this is a fairly unusual and exploratory question, so please bear with me. I am wondering if one could apply the idea of importance sampling to Gibbs sampling. Here's what I mean: in Gibbs ...
1
vote
1answer
16 views

importance sampling and exponential moving average

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$...
1
vote
1answer
61 views

Given unnormalized weights in logs, how do I compute normalized weights in logs?

Setting Given a set of positive weights $\{w_i\}_{i=1}^n$, I can normalize them by computing $$W_i = \frac{w_i}{\sum_{j=1}^nw_j}\quad \forall i=1,...,n.$$ Easy enough. But for numerical reasons, it ...
1
vote
0answers
34 views

Flatten the target density in the Metropolis-Hastings algorithm

Let $(E,\mathcal E,\mu)$ be a measure space $F$ be a $\mathbb R$-Banach space $f\in\mathcal L^1(\mu;F)$ $f^\ast:E\to[0,\infty)$ be $\mathcal E$-measurable with $$b:=\int f^\ast\:{\rm d}\mu\in(0,\...
2
votes
1answer
47 views

importance sampling strategies

I am trying to approximate the expectation of the "complete-data likelihood" with respect to the distribution of some missing data, and I am having some trouble. This expectation can be written as $$ ...
2
votes
1answer
51 views

What's done with the expectations in this proof?

This is a proof of the per-decision importance sampling (theorem 1) from the appendix of: https://www.google.co.uk/url?sa=t&source=web&rct=j&url=http://scholarworks.umass.edu/cgi/...
2
votes
2answers
50 views

A doubt on the formula for updating the weights in Sequential Importance Sampling in a State-Space model

Let $x_{0:t}^{(i)}$ be the states from time $0$ to $t$ from sample $i$. Similarly for the observations $y_{1:t}$. The normalized weights are updated according to Where does the term $p(y_t|x_t^{(i)})...
4
votes
3answers
79 views

Conditional expectation on an estimator for defensive sampling

In Introducing Monte Carlo Methods, by Robert and Casella, we have How do we derive the second equality? Shouldn't it be $$E\left[\frac{f(X_i)}{g_{Y_i}(X_i)}|X_i\right]=\frac{f(X_i)}{g_1(X_i)}\rho+...
2
votes
1answer
53 views

SIR explanation in Robert and Casella Intro to Monte Carlo Methods - How to do this derivation?

Why is it an exact simulation from $f$, and not only an approximation? I get $\begin{split} P(X^*\in A) & = \sum_i^n P(X^*\in A , X^* = X_i)=\sum_i^n P(X^*\in A | X^* = X_i)P(X^* = X_i) \\ & ...
3
votes
0answers
29 views

Looking for a recursive formula for asymptotic variance of importance sampling estimator (self-normalized)

Looking for a recursive formula to approximate variance of importance sampling estimator $Var_q\big[\delta_{IS}\big]\approx\sum_{i=1}^n\tilde w(X_i)^2\big[h(X_i)-\delta_{IS}\big]^2$. This is an ...
0
votes
0answers
262 views

Optimal proposal for self-normalized importance sampling

Consider a function $f: \mathcal X \to \mathbb R$ and a probability distribution $p$ with the support on $\mathcal X$ which we can evaluate up to a normalizing constant, i.e. we can only evaluate $\...
2
votes
1answer
453 views

Why does Off-Policy Monte Carlo Control only learn from the “Tails of Episodes”?

I was reading through section 5.7 of the second edition of Sutton and Barto's "Reinforcement Learning: An Introduction" when I came across this passage: where the "method" that the author is ...
0
votes
0answers
28 views

How to prove that $\hat{\rm{var}} \left\{ w^*(X) \right\} = \hat{\rm{cv}}^2 \left\{ w(X) \right\}$? (Importance Sampling)

Text: Computational Statistics 2E by Givens and Hoeting Let $f$ be the target distribution and $g$ be an envelope for $f$. Let $X_1, \ldots, X_n \overset{\text{iid}}{\sim} g$ represent a sample. ...
0
votes
1answer
52 views

Derivation of squared coefficient of variation (Importance Sampling)

Text: Computational Statistics 2E by Givens and Hoetings Section: 6.3.2.3 Weight Degeneracy, Rejuvenation, and Effective Sample Size I am having trouble following another result in the text. Below ...
3
votes
1answer
55 views

Stuck on part of proof that a random variable $\bf X$ drawn with the SIR algorithm has distribution that converges to $f$ as $m \rightarrow \infty$

Text: Computational Statistics by Givens and Hoeting Section 6.3.1: Sampling Importance Resampling Algorithm The authors provide a proof that random variable $\bf X$ drawn with the SIR algorithm has ...
2
votes
0answers
32 views

Hyper-parameters which minimize the variance of transformed multi-variate Guassian variable

Let $k < p$ be positive integers and $g: \mathbb R^k \rightarrow \mathbb R^p$ be a smooth Lipschitz continuous function. Let $y_1,\ldots, y_N \in \mathbb R^p$ and $a = (a_1,\ldots,a_N) \in \mathbb ...
6
votes
1answer
48 views

how to sample data for regression that is the most informative?

Background I have a unknown function $$f(x_1, x_2)$$ But I have access to evaluate this function finite $L$ times, $$y_j = f(x_1^j, x_2^j), j=1,\ldots,L $$ Then I have a model $\hat{f}$ which I ...
3
votes
2answers
372 views

Understanding Sequential Importance Sampling and Particle Filtering

I am struggling with SIS for particle filtering in the following aspect: In particle filtering (as per this book), the objective is to estimate the full posterior $p( x_{0:k} \mid y_{1:k} )$ rather ...
1
vote
0answers
22 views

Low-variance estimate for the mean of the sotfmax transformation of a variable

Consider a set of infintiely-differentiable convex functions real-valued functions $f_i: \mathcal X \rightarrow \mathbb R$, where $i$ varies from $1$ to $m$, and suppose we know all the moments of $...
0
votes
0answers
34 views

how to prove that estimator converges to posterior distribution

Let $X_1, X_2, \dots X_n \sim f(x|\theta)$, $\theta$ has prior $\pi$. Generate $\theta_1, ... \theta_m$ from $\pi$, calculate $q_i = L(\theta_i|\textbf{x}) / \sum_j L(\theta_j|\textbf{x})$ where $L(\...
3
votes
1answer
552 views

Off-policy importance sampling for TD(0)

Consider the off-policy value update $V(s) \leftarrow V(s) + \alpha\frac{\pi(a\mid s)}{b(a\mid s)}[r_t+\gamma V(s') - V(s)]$ Where $\pi$ is the target policy (from which greedy actions are determined)...
2
votes
1answer
132 views

Monte Carlo - Importance sampling using normal distribution as sampling distribution

Suppose that I want to approximate an integral over finite range, say for example 0 to 10 using the Monte Carlo method. Can I choose a normal distribution as the sampling distribution even though the ...
5
votes
1answer
61 views

About the variance of a weighted sum

What can be said about the variance of the following quantity $$ \frac{1}{n}\sum_{i=1}^n \left(\frac{f(x_i)}{\sum_{j=1}^nf(x_j)}-b\right)g(x_i) ? $$ Here, $b \in [0, 1]$, and the $x_i$s are i.i.d ...
2
votes
2answers
178 views

ABC with non-uniform prior

I had asked some similar questions in the past, but I never got either the answers or the discussion I was hopping for. So I will rephrase the problem to see if I can understand it myself. I'm trying ...
1
vote
0answers
30 views

How can I use importance sampling to estimate $p$? [duplicate]

I have two density functions, $f$ and $g$. I generated a sample $X_1,\ldots, X_n$ using the distribution corresponding to density function $f$. I'm interested in the parameter $p_g = \operatorname{P}...
0
votes
1answer
106 views

Time limits in the Importance Sampling formula for Expected SARSA algorithm

In the Reinforcement Learning book (Prof. Sutton et al.) the authors explain a few basic algorithms of Reinforcement Learning. A particular kind of algorithms called n-step Temporal Difference ...
1
vote
1answer
39 views

In importance sampling, why do we “reapply” the trial distribution?

We are interested in the value of $\mu = \int f(x)dx$, and we have a factorization of $f$ as $f(x) = h(x)p(x)$, where $p(x)$ is a density. The general way to apply importance sampling is to follow the ...
0
votes
0answers
49 views

Exponential Tilting and Importance sampling

I am studying by myself a book about importance sampling. I am confused with the topic about exponential tilt. According to the algorithm is stated that I need to generate random variables $Z_1L_1,...
0
votes
0answers
75 views

Importance Sampling for n dimensions

EDIT: I edited the question in order to make it clear. I'm having a problem with Importance Sampling and calculation of weights in more than one dimension. Because for me this is not obvious, I will ...
1
vote
2answers
137 views

How is this minimum variance worked out for this importance sampling estimator?

I was stuck with the function 17.13 in the open source book deep learning on page 590. For short, the question is that, For the importance sampling estimator: $$\hat s_q = \frac{1}{n}\sum_{i=1, x^{i}...
2
votes
0answers
158 views

Importance sampling: what is this bias?

I am experiencing what seems to be a bias in importance sampling, which, given that it's an unbiased procedure, should not be there. Consider linear regression $$ y = X\beta+\epsilon $$ where there ...
4
votes
0answers
37 views

Expected value of a “logistic uniform” multivariate

Let $\mathbf{a}_1,\ldots,\mathbf{a}_n \in \mathbb R^d$ and $b_1,\ldots,b_n \in \mathbb R$ be fixed. For $\mathbf{x} \sim \mathcal U([0,1]^d)$ and $j \in \{1,\ldots,n\}$, consider the real variable ...
2
votes
1answer
155 views

Importance Sampling

I want to solve the integral $$I =\int_{0}^{3} \frac{\exp(-s)}{1+\frac {1}{s}} \text{d}s $$ using importance sampling. I'm unsure as to how implement it. I have sampled random variables from an ...
1
vote
1answer
132 views

Exponential Twisting

I am with a difficult to prove the next relation about exponential twisting. According to Monte Carlo Methods and Models in Finance and Insurance by Ralf Korn, Elke Korn, Gerald Kroisandt. The ...
0
votes
0answers
17 views

Adjusting uniform sampling by relative weights

Assume a population of businesses, each given a size value which is proportional to their popularity. The sampling design is as follows, and cannot be changed: 1. Choose a random business uniformly, ...
2
votes
2answers
472 views

Off-policy evaluation of reinforcement learning: How to compute importance weights

I am working on a project that will use reinforcement learning to recommended products to customers in a mobile app. We have a few years of historical data available, which I would like to use for ...
2
votes
1answer
207 views

Sampling / Importance Resampling Poisson Weights

Another question from Introducing Monte Carlo Methods with R by Robert and Casella. Exercise 3.6 basically says the following. Suppose $f$ and $g$ are densities. Draw a random sample $X_1, \ldots,...
2
votes
1answer
65 views

Confusion: Conditioning a Discrete rv on a Continuous rv, “Sampling Importance Resampling”

Background In Introducing Monte Carlo Methods with R by Robert and Casella, in the discussion on "Sampling Importance Resampling", I'm confused by the following argument. Suppose $f$ and $g$ are ...
2
votes
1answer
118 views

Rejection/Importance Sampling for logit model

$\newcommand{\logit}{\operatorname{logit}}$I have the following model: ${y}_{j}\sim \operatorname{Bin}({n}_{j},{\theta}_{j})$, where ${\theta}_{j}={\logit}^{-1}(\alpha+\beta{x}_{j})$, for $j=1,...,J$,...
5
votes
0answers
92 views

Probabilistic upper bounds on importance sampling error

Consider the importance sampling estimation error $$ e_n(f) = \int f d\mu - \frac{1}{n}\sum_{i=1}^n f(x_i) \rho(x_i), \qquad x_i \sim \lambda,\, \rho = \tfrac{d\mu}{d\lambda}, $$ where $\mu$ and $\...
1
vote
1answer
146 views

Can someone explain Importance Sampling to me? [duplicate]

So even the combined efforts of my professor, my book and the internet have not been able to make me understand the concept of Importance Sampling. I know that it is a way to help with estimating the ...
0
votes
0answers
184 views

Under what conditions does off-policy SARSA with importance sampling converge?

Under what conditions does off-policy SARSA with importance sampling converge? I know function approximation can cause problems. In the tabular case, what is needed to get convergence (to the true Q)?...
1
vote
0answers
31 views

Can weighted sampling be more efficient than sampling?

Suppose that you have a normal distribution D with density f, which you sample. An estimator produces the maximum likelihood normal distribution $G_n$ given n samples. On the other hand you could ...
1
vote
0answers
195 views

How can we use importance sampling for drawing posterior distribution samples?

Today I read that Importance Sampling can be used to draw posterior distribution samples just like Rejection Sampling. However, my understanding of Importance Sampling is that its main purpose is to ...
4
votes
1answer
71 views

Difference between contrastive divergence and importance sampling

The terms Contrastive Divergence and Importance Sampling are sometimes used interchangeably. I understand that both are used to approximate partition functions (normalization terms for probabilities)...
2
votes
0answers
69 views

Discrete Kernel for Sequential Monte Carlo (population monte carlo)

I'm attempting understand, and use, the population Monte Carlo algorithm found here https://arxiv.org/abs/0805.2256 for approximate Bayesian computation. However I think this is a general SMC question,...
2
votes
1answer
474 views

Importance sampling: form of weights

My question is motivated by page 8 of http://www.stats.ox.ac.uk/~doucet/doucet_defreitas_gordon_smcbookintro.pdf but the jist is the following: We want to evaluate $\mathbb{E}_{\pi}(f(X))$ where $X\...
8
votes
1answer
220 views

Lower than expected coverage for importance sampling with simulation

I was trying to answer the question Evaluate integral with Importance sampling method in R. Basically, the user needs to calculate $$\int_{0}^{\pi}f(x)dx=\int_{0}^{\pi}\frac{1}{\cos(x)^2+x^2}dx$$ ...