Comments (20)
I'm reopening this for now until the issues mentioned in this comment are resolved.
from webppl.
Was this closed by 8688ffa? (We have #118 for the PF with rejuvenation case.)
from webppl.
Not entirely. The commits referenced deal with one particular case of variable-number-of-factors; one where the particles are all in sync across observations except at the end, where some of the particles can have extra observations. The more general case of what to do when, say, one particle takes off on some sequence of observations different from other particles, and then syncs back at some later observation, is still not dealt with.
from webppl.
Aren't all cases of variable numbers of factors such that you have extra factors at the end for some particles? Yes, you might synchronize factors that have very different meanings, which could lead to bad statistical efficiency, but is there a problem with correctness?
from webppl.
I'm trying to understand how we handle this so I can make sure I get it right in #64. If anyone can answer either of the following I'd find it helpful:
- Ignoring rejuvenation, can we say for which models we think the current implementation is correct? (For both the distribution and the normalizing constant estimate.) There seems to be confusion about this in the previous two comments. I'm starting to think it might be correct in general but I only have a rough sketch of an argument which needs more thought.
- I'm not so confident that rejuvenating particles which are at different factor statements is correct. In the case where all particles are at the same factor statement, and we rejuvenate with a kernel which is the program truncated at that factor statement, it makes sense that we end up with particles from the distribution we're interested in. This seems to break down though when we have particles at different factor statements. Is this why we don't test
varFactors1
with rejuvenation?
Thanks!
from webppl.
No rejuvenation
My guess is that the current implementation (in particlefilter.js
) results in the correct distribution for any model.
Consider running the particle filter without intermediate resampling steps, only doing a single resampling step at the end based on the total weight for each particle. In this case, it's clear that the distribution is (approximately) correct -- our final step simply changes how we represent the distribution, from being represented in terms of (particle counts, factor weights)
to being fully represented in terms of particle counts.
What happens if you introduce an intermediate resampling step? We can think of the original representation as (particle counts, [weights1 + weights2])
; the first resampling step changes the representation of the distribution such that the information in weights1
is now represented using particle counts. The second resampling step includes the information in weights2
in the counts representation as well. This is a general argument that intermediate resampling steps are okay.
For this argument, it doesn't matter how many factors (if any) resulted in the weights, whether the number of factors differs between particles, or whether we already applied resampling steps previously. We can always apply resampling to transform the part of the distribution that's represented using weights to being represented using particle counts.
I don't have very high confidence in this argument (both in its correctness and in the fact that it applies to our implementation), but I think it's probably right. I'd guess that a similar argument applies to the normalization constant estimate, but I haven't thought much about it and so have even less confidence there.
Rejuvenation
A first reaction might be: "A particle is approximately sampled from some distribution, and all rejuvenation does is increase the quality of this sample, i.e., make it less approximate. How could this not be correct?"
For models with structural change, this is subtle, though. In our current implementation, the distribution that the particle is sampled from ("program truncated at the factor statement") isn't well-defined for some models.
Consider a model like this:
if (flip(.5)){
factor(-1);
} else {
factor(-2);
}
// ... more program here ...
Suppose we run our particle filter and get a particle that arrives at factor(-1)
. When we run rejuvenation on this particle, we may change the value of flip(.5)
. In this case, we will never make it to factor(-1)
, our test for when to stop rejuvenation never succeeds, and we run the program till the end. If we use the trace that results from such rejuvenation in our particle filter, we essentially skip over some factors (we don't accumulate their weights), so I don't expect the distribution to be correct.
One way around this problem would be to only allow proposals to non-structural choices in rejuvenation steps (assuming we can detect such choices, e.g. using static analysis).
from webppl.
so I don't expect the distribution to be correct. One way around this problem would be to only allow proposals to non-structural choices in rejuvenation steps
To alert users to the possible incorrectness in the interim, should we consider throwing an error (or warning) if we try to rejuvenate particles which are out of sync? (i.e. at different factor statements.)
from webppl.
Yes, I think it's a good idea to throw an error in this case.
from webppl.
Does this mean it will now throw an error in the extra-factors-at-the-end situation that we currently handle? If so, could we have the option to override the error throwing?
I'm thinking the example @andreas mentions as being suspect in the rejuvenation case could potentially be handled by using setProposalBoundary
.
// ....
var ifTest = flip(0.5)
setProposalBoundary();
if (ifTest){
// some code
factor(-1);
} else {
// some other code
factor(-2);
}
// ....
from webppl.
Does this mean it will now throw an error in the extra-factors-at-the-end situation
By extra-factors-at-the-end do you mean something like extra factor statements at the end of the program without intervening sample statements? For example:
var x = flip(0.5);
factor(-1);
if (x) {
factor(-2);
}
// End of program
that we currently handle?
Do you mean we're confident that rejuvenation in this case doesn't run into the problem Andreas mentioned?
from webppl.
Well there could be intervening sample statements
var x = flip(0.5);
setProposalBoundary()
var a1 = flip(0.2);
factor(a1 ? 0 : -Infinity);
if (x) {
var a2 = flip(0.4);
factor(a2 ? 0 : -Infinity);
}
The point being that if you could move the structural random choices outside the rejuvenation boundary, then the fact that you could have particles with one or two factors wouldn't break things.
I wanted the option to override throwing the error because there are cases (as above, and when constructing sequences involving heuristic factors) where rejuvenating particles that appear out of sync is not wrong.
from webppl.
I'm not opposed to having an option (such as allowDangerousOutOfSyncRejuvenation
) that disables throwing the error. This would be temporary and would be removed once we implement a coherent strategy for rejuvenation in models with structural change.
from webppl.
One way around this problem would be to only allow proposals to non-structural choices in rejuvenation steps
I'm not sure that's enough, assuming the rest of the algorithm is unchanged. Consider this model:
var model = function() {
var x = flip(0.5);
var y = flip(0.5);
setProposalBoundary()
var z = flip(0.5);
if (x) {
factor(x ? 0 : -1);
}
if (y) {
factor(y ? 0 : -1);
}
return [x, y]
};
Here, I think we still have particles failing to exit at the correct limitAddress
during rejuvenation, even though we don't propose to x
or y
. This is because not all particles see every factor statement but we currently use the same limitAddress
for each particle during rejuvenation.
If that's correct, it suggests setting limitAddress
per-particle to the address of the last factor
statement reached.
(I'm thinking about this because in #64 I assert
that particles reach limitAddress
during rejuvenation, and I'm trying to understand whether I need to relax that.)
from webppl.
If that's correct, it suggests setting
limitAddress
per-particle to the address of the lastfactor
statement reached.
Yes, if we want to allow use of SMC for models with structural change (even if the actual rejuvenation steps only propose to non-structural choices), we would have to keep track of limitAddress
per particle.
(Just to be clear: Since we don't have a way of limiting proposals to non-structural choices for now, we should continue throwing an error by default if we try to rejuvenate particles that are out of sync. Working out rejuvenation for models with structural change is a separate task from getting plain particle filtering working - now issue #176.)
from webppl.
If that's correct, it suggests setting limitAddress per-particle to the address of the last factor statement reached.
As Sid just pointed out to me: the current implementation does this.
from webppl.
As Sid just pointed out to me: the current implementation does this.
Oops, sorry! I did check before suggesting it, I must have misunderstood what's happening.
I looked here and thought that it looked like rejuvenation was using limitAddress = a
where a
is the address of the factor statement reached by the final particle. What am I missing?
from webppl.
No, sorry, you're right. I should have checked -- turns out it's just Sid's local branch that saves the current factor address for each particle and then use that as limit address.
from webppl.
we should continue throwing an error by default if we try to rejuvenate particles that are out of sync
I've added an allowOutOfSyncRejuv
option to the SMC
implementation in #169 that does this. It also now tracks a limitAddress
per-particle. And just to clarify, it's still the case that it checks that particles reach their limitAddress
during rejuvenation, and errors otherwise.
I don't have any more related changes planned for #169. @iffsid Are you happy this leaves things in a usable state for you?
from webppl.
Yeah, looks like that will help. Thanks!
I'll take a closer look at things soon; haven't followed the changes over the last couple of weeks.
from webppl.
I've added an allowOutOfSyncRejuv option to the SMC implementation
To clarify, as of #245 this option no longer exists and "out of sync" rejuvenation is allowed by default.
Are we ok to close this? (If not, we should maybe open new tickets for specific issues as this thread is pretty convoluted at this point.)
from webppl.
Related Issues (20)
- Add reparameterisation for logNormal HOT 3
- Variable going out of scope when other variables are defined HOT 2
- Nested map and reduce HOT 3
- Support of multinomial broken by deprecated object() method from lodash
- Add Student's t-distribution HOT 9
- get statistics from RVs HOT 2
- Pretty printing of distributions doesn't work as expected under Node 12 HOT 1
- `let` unexpectedly parsed as variable declaration
- [tutorial] unnecessary function wrapping HOT 1
- Documentation for Distribution.support() lacking HOT 2
- Support ES6 default parameters
- Is there a forum or help desk to ask some beginner questions? HOT 1
- Still maintained and StudentT distribution HOT 1
- REPL shell ? HOT 3
- Creating a new distribution ? Combinatorics ? HOT 1
- Unexpected output in installation from github HOT 3
- Usage help: observed data HOT 2
- .some() method behaves unexpectedly HOT 2
- reduce function processes arguments in the wrong order
- Set up HTTPS for WebPPL website
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from webppl.