Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement a reasonable Griddy Gibbs #642

axch opened this issue Nov 11, 2016 · 1 comment

Implement a reasonable Griddy Gibbs #642

axch opened this issue Nov 11, 2016 · 1 comment


Copy link

@axch axch commented Nov 11, 2016

The basic idea called "Griddy Gibbs" is that one can (approximately) Gibbs-sample from any unnormalized 1-dimensional continuous posterior density by just doing the quadrature.

Somehow this idea has gotten metamorphosed (at least for hyperparameter inference in our crosscat implementations) into the workable but rather unsatisfying approximation "Approximate the hyper-prior as a discrete distribution on a grid of values, and do enumerative Gibbs on that."

The original Ritter, Tanner 1991 paper "The Griddy Gibbs Sampler" actually alludes to the possibility of doing one step better than that, namely using one's favorite quadrature technique to form an approximate cumulative distribution function (which, notably, need not be a step function) and sampling from that.

In fact, we can do better still: treat the sample from said approximate CDF as an M-H proposal (independent of the current state), and include the possibility of rejecting it. For approximate CDFs that are continuous (e.g., piecewise linear), the acceptance ratio is both well-defined and easy to compute. This variant stops being a Gibbs sampler, strictly speaking, but gains the benefit of being a transition operator with exactly the right invariant distribution. The quality of the quadrature approximation will determine the acceptance ratio (and, in fact, one can imagine auto-tuning the choice of grid fineness in order to reach good acceptance rates).

Why do this?

  • We will be able to write inference programs that we can trust to be exactly right on all single-variable subproblems that have occurred in our practice to date (we haven't had any infinite-support discrete distributions, at least that I noticed). Given how helpful enumerative Gibbs for finite-support discrete variables seems to be, I think this will represent material progress.

  • This can also be used to test simulator-assessor agreement for 1-D primitive stochastic procedures: just compare the sampling distribution to the distribution obtained by running Griddy Gibbs on a model that contains one unconstrained application of the SP in question. The latter yields samples in a way that only depends on the assessor.

    • It may be more efficient to extract the approximate CDF from the integration and do a 1-sample K-S against it
    • Failing that, we should at least cache the quadrature result in order to efficiently draw a sizeable sample

Open issues:

  • How to choose the points at which to compute the density function? I think any choice that doesn't depend on the current state should be fine. If it has some dependence on the current state, appropriate analysis would be called for to make sure it's reversible. In particular, I expect methods that are adaptive to the unnormalized PDF values would be quite reasonable, though the first implementation should strive for simplicity.

  • The boundary condition problem (#591) applies.

  • What to do if the integral is improper? Presumably we can adapt whatever tricks people already do to numerically compute improper integrals, e.g. a change of variables that makes it proper. Whatever we do will need to ensure that the current state's probability density under the approximate CDF formed by the integration can be computed.

  • How to derive an apprixmate CDF from the unnormalized PDF values evaluated during quadrature? The simplest option would be to make it piecewise linear. Higher-order polynomial approximations may make the approximation more accurate, leading ultimately to a faster sampler; but I don't know whether that matters.

Copy link
Contributor Author

@axch axch commented Oct 25, 2017

This is a variant of #581, except the latter omitted the possibility of using the quadrature CDF as an M-H proposal.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant