{"action":"created","issue":{"url":"https://api.github.com/repos/probmods/webppl/issues/20","labels_url":"https://api.github.com/repos/probmods/webppl/issues/20/labels{/name}","comments_url":"https://api.github.com/repos/probmods/webppl/issues/20/comments","events_url":"https://api.github.com/repos/probmods/webppl/issues/20/events","html_url":"https://github.com/probmods/webppl/issues/20","id":47923309,"number":20,"title":"particle filters with variable number of sampling/factors in models","user":{"login":"iffsid","id":1027018,"avatar_url":"https://avatars.githubusercontent.com/u/1027018?v=3","gravatar_id":"","url":"https://api.github.com/users/iffsid","html_url":"https://github.com/iffsid","followers_url":"https://api.github.com/users/iffsid/followers","following_url":"https://api.github.com/users/iffsid/following{/other_user}","gists_url":"https://api.github.com/users/iffsid/gists{/gist_id}","starred_url":"https://api.github.com/users/iffsid/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/iffsid/subscriptions","organizations_url":"https://api.github.com/users/iffsid/orgs","repos_url":"https://api.github.com/users/iffsid/repos","events_url":"https://api.github.com/users/iffsid/events{/privacy}","received_events_url":"https://api.github.com/users/iffsid/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/probmods/webppl/labels/enhancement","name":"enhancement","color":"84b6eb"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2014-11-06T04:49:06Z","updated_at":"2015-08-21T15:18:46Z","closed_at":null,"body":"A model that involves incremental sampling and factoring of elements, where the number of elements and factors itself can vary across particles, results in the construction of a marginal distribution that has `undefined` as an element of its support.\r\n\r\nThe example below illustrates this problem. When the variable `numl` in `inner` is set to a constant, the the code runs as expected. However, replacing the number by a call to a stochastic function that varies the number of elements produced, causes the marginal distribution have `undefined` in its support.\r\n``` javascript\r\nvar ds = [0,1,2,3,4,5,6,7,8,9]\r\n\r\nvar constructL = function(n,m,_l,pf) {\r\n  var _l = _l == undefined ? [] : _l\r\n  var pf = pf == undefined ?  0 : pf\r\n  if (n == 0) {\r\n    factor(-pf)\r\n    return _l\r\n  } else {\r\n    var e = ds[randomInteger(ds.length)]\r\n    var nl = _l.concat([e])\r\n    var nf = m(nl) ? 0 : -30\r\n    factor(nf - pf)\r\n    return constructL(n-1,m,nl,nf)\r\n  }\r\n}\r\n\r\nvar inner = function(m){\r\n  ParticleFilter(function(){\r\n    var numl = 4 // binomial(0.7,4)+1\r\n    var nl = constructL(numl,m)\r\n    factor(m(nl) ? 0 : -Infinity)\r\n    return nl\r\n  }, 10)\r\n}\r\n\r\nvar evenM = function(l) {\r\n  // checks if every element in the list is even\r\n  var f = function(a,b){ return a & b }\r\n  var g = function(v) {return v%2 == 0}\r\n  return reduce(function(a,b) { return f(g(a),b) }, g(l[l.length-1]), l.slice(0,-1))\r\n}\r\nvar d = inner(evenM)\r\nconsole.log(d.support([]))\r\nprint(d)\r\n```\r\n"},"comment":{"url":"https://api.github.com/repos/probmods/webppl/issues/comments/133460681","html_url":"https://github.com/probmods/webppl/issues/20#issuecomment-133460681","issue_url":"https://api.github.com/repos/probmods/webppl/issues/20","id":133460681,"user":{"login":"stuhlmueller","id":382515,"avatar_url":"https://avatars.githubusercontent.com/u/382515?v=3","gravatar_id":"","url":"https://api.github.com/users/stuhlmueller","html_url":"https://github.com/stuhlmueller","followers_url":"https://api.github.com/users/stuhlmueller/followers","following_url":"https://api.github.com/users/stuhlmueller/following{/other_user}","gists_url":"https://api.github.com/users/stuhlmueller/gists{/gist_id}","starred_url":"https://api.github.com/users/stuhlmueller/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stuhlmueller/subscriptions","organizations_url":"https://api.github.com/users/stuhlmueller/orgs","repos_url":"https://api.github.com/users/stuhlmueller/repos","events_url":"https://api.github.com/users/stuhlmueller/events{/privacy}","received_events_url":"https://api.github.com/users/stuhlmueller/received_events","type":"User","site_admin":false},"created_at":"2015-08-21T15:18:46Z","updated_at":"2015-08-21T15:18:46Z","body":"*No rejuvenation*\r\n\r\nMy guess is that the current implementation (in `particlefilter.js`) results in the correct distribution for any model. \r\n\r\nConsider 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.\r\n\r\nWhat 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. \r\n\r\nFor 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.\r\n\r\nI 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.\r\n\r\n*Rejuvenation*\r\n\r\nA 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?\" \r\n\r\nFor 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.\r\n\r\nConsider a model like this:\r\n\r\n    if (flip(.5)){\r\n      factor(-1);\r\n    } else {\r\n      factor(-2);\r\n    }\r\n    // ... more program here ...\r\n\r\nSuppose 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.\r\n\r\nOne 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)."}}