Machine Learning Trick of the Day (2): Gaussian Integral Trick

Today's trick, the Gaussian integral trick, is one that allows us to re-express a (potentially troublesome) function in an alternative form, in particular, as an integral of a Gaussian against another function — integrals against a Gaussian turn out not to be too troublesome and can provide many statistical and computational benefits. One popular setting where we can exploit such an alternative representation is for inference in discrete undirected graphical models (think Boltzmann machines or discrete Markov random fields). In such cases, this trick lets us transform our discrete problem into one that has an underlying continuous (Gaussian) representation, which we can then solve using our other machine learning tricks. But this is part of a more general strategy that is used throughout machine learning, whether in Bayesian posterior analysis, deep learning or kernel machines. This trick has many facets, and this post explores the Gaussian integral trick and its more general form, auxiliary variable augmentation.

Gaussian integral trick state expansion.

Gaussian integral trick state expansion.

Gaussian Integral Trick

The Gaussian integral trick is one of the statistical flavour and allows us to turn a function that is an exponential in x^2 into an exponential that is linear in x. We do this by augmenting a linear function with auxiliary variables and then integrating over these auxiliary variables, hence a form of auxiliary variable augmentation. The simplest form of this trick is to apply the following identity:

\int \exp(-ay^2 + xy) dy = \sqrt{\frac{\pi}{a}} \exp\left(\frac{1}{4a}x^2\right)

We can prove this to ourselves by exploiting our knowledge of Gaussian distributions (which this looks strikingly similar to) and our ability to complete the square when we see such quadratic forms. Separating out the scaling factor a we get:

 \int \exp(-a y^2 + xy) dy =\int \exp \left\{-a\left(y^2 - \frac{x}{a}y\right) \right\}dy

Which by completing the square becomes:

 \int \exp \left\{-a\left(y - \frac{x}{2a}\right)^2 + \left(\frac{x^2}{4a}\right) \right\}dy

=\exp\left(\frac{x^2}{4a}\right) \int \exp\left\{-a\left(y - \frac{x}{2a}\right)^2 \right\} dy

=\exp\left(\frac{x^2}{4a}\right) \sqrt{\frac{\pi}{a}}

where the last integral is solved by matching it to a Gaussian with mean  \mu = \frac{x}{2a} and variance \sigma^2 = \frac{1}{2a}, which we know has a normalisation of \sqrt{2 \pi \sigma^2} — this last step shows how this trick got its name.

The 'Gaussian integral trick' was coined and initially described by Hertz et al. [Ch10, pg 253] [1], and is closely related to the Hubbard-Stratonovich transform (which provides the augmentation for \exp(-x^2)).

Transforming Binary MRFs

This trick is also valid in the multivariate case, which is what we will most often be interested in. One good place to see this trick in action is when applied to binary MRFs or Boltzmann machines. Binary MRFs have a joint probability, for binary random variables x:

 p(\mathbf{x}) = \frac{1}{Z} \exp\left( \boldsymbol{\theta}^\top \mathbf{x} +\mathbf{x}^\top \mathbf{W}\mathbf{x}\right)

where Z, is the normalising constant. The (multivariate) Gaussian integral trick can be applied to the quadratic term in this energy function allowing for an insightful analysis and interesting reparameterisation that allows for alternative inference methods to be used. For example:

Variable Augmentation

Graphical model for a general augmentation.

Graphical model for a general augmentation.

This trick is a special case of a more general strategy called variable (or data) augmentation — I prefer variable augmentation to data augmentation [4], since it will not be confused with observed data preprocessing and manipulation. In this setting, the introduction of auxiliary variables has been most often used to develop better mixing Markov chain Monte Carlo samplers. This is because after augmentation, the conditional distributions of the model often have highly convenient and easy-to-sample-from forms.

One recent example of variable augmentation (and that parallels our initial trick) is the Polya-Gamma variable augmentation. In this case, we can express the sigmoid function that appears when computing the mean of the Bernoulli distribution, as:

\sigma(x) = \frac{1}{1 + \exp(-x)} = \frac{1}{\sqrt{2}} \exp\left(\frac{x}{2} \right) \int_0^\infty\exp\left(-\frac{1}{2}yx^2 \right) p(y) dy

where p(y) has a Polya-Gamma distribution [5]. This nicely transforms the sigmoid into a Gaussian convolution (integrated against a Polya-Gamma random variable) — and gives us a different type of Gaussian integral trick. In fact, similar Gaussian integral tricks are abound, and are typically described under the heading of Gaussian scale-mixture distributions.

There are many examples of variable augmentation to be found, especially for binary and categorical distributions. Much guidance is available, and some papers that demonstrate this are:

Summary

The Gaussian integral trick is just one from a large class of variable augmentation strategies that are widely used in statistics and machine learning. They work by introducing auxiliary variables into our problems that induce an alternative representation, and that then give us additional statistical and computational benefits. Such methods lie at the heart of efficient inference algorithms, whether these be Monte Carlo or deterministic approximate inference schemes, making variable augmentation a favourite in our box of machine learning tricks.


Some References
[1] John Hertz, Anders Krogh, Richard G Palmer, Introduction to the theory of neural computation, , 1991
[2] Yichuan Zhang, Zoubin Ghahramani, Amos J Storkey, Charles A Sutton, Continuous relaxations for discrete hamiltonian monte carlo, Advances in Neural Information Processing Systems, 2012
[3] Ari Pakman, Liam Paninski, Auxiliary-variable exact Hamiltonian Monte Carlo samplers for binary distributions, Advances in Neural Information Processing Systems, 2013
[4] James H Albert, Siddhartha Chib, Bayesian analysis of binary and polychotomous response data, Journal of the American statistical Association, 1993
[5] Nicholas G Polson, James G Scott, Jesse Windle, Bayesian inference for logistic models using P\'olya--Gamma latent variables, Journal of the American Statistical Association, 2013

Leave a Reply