Approximation of partition function (normalizer)

Question

Say we have a nasty probability distribution like, $$ P(x) = \frac{P^*(x)}{Z} $$ where we can easily compute $P^*(x)$ for a given $x$ but not $P(x)$ because partition function $Z$ is expensive to compute. There are approximation techniques like Monte Carlo which can be used to estimate the expectation of functions under this distribution.

Instead of some expectations, if we want a probability of some $x$, can we get it using some sampling techniques? Can we approximate the partition function $Z$ itself? I can't see resources which do these approximations, probably because it is not a standard thing to do.

Answer 1

In the context of restricted Boltzmann machines, a specialised form of annealed importance sampling has been developed by Salakhutdinov: http://www.cs.toronto.edu/~rsalakhu/papers/bm.pdf.

This TR also goes over some other schemes.

For latent variable models of the form $p(x) = \sum_z p(x|z)p(z)$ where a good approximation $q(z|x) \approx p(z|x)$ is available, Rezende et al propose an importance sampler in this paper: $$ p(x) \approx {1 \over S} \sum_{s=1}^S {p(x|z_s)p(z_s) \over q(z_s|x)}, \\ z_s \sim q(z|x) $$ This estimator works ridiculously well and fast. You might need to implement it using the log sum exp trick for numerical stability, though.

Answer 2

In the context of restricted Boltzmann machines there is one way to go about it: not to find an approximation to the partition function, but to approximate the gradients of the partition function (see Training products of experts by minimizing contrastive divergence by G. Hinton), which in addition is easy to implement.

The rationale is that, when learning a model of that kind, calculating the exact gradients of the partition function is computationally prohibitive. But because of a monotonicity condition, we can find an approximation of the gradients which is warranted not to get worse at every step (kind of like EM algorithm).

There are other approaches where one looks for a "good" approximation of the partition function (variational methods). But I am regretfully not familiar with them.

Answer 3

I'm not an expert on nasty distributions, but is there any reason why you can't estimate Z directly? And by directly I mean using numerical integration of p*(x) rather than using monte carlo.

The partition function is a multiplicative constant with respect to x, assuring that the probability integrates to 1, and as such you can easily estimate it and plug it into your density.

As as far I can tell the answers are: no sampling necessary, we can approximate Z, for a fixed set of parameters it's a scalar, and you can do it in any programming language, or online using wolfram alpha if you prefer.

Basically, if p*(x) is easy to compute so is Z.