1
$\begingroup$

SHORT VERSION:

We have a ('visible') random variable $X$ and a ('hidden') random variable $Z$. We have chosen appropriate distributions $P(X|Z)$ and $P(Z;w)$ where $w$ is the parameter of the model. The distributions are possibly not in the exponantial family, and the variables possibly high-dimensional, so there is no practical analytical way to integrate out $Z$. Now, we receive an observation from $X$, $x$. How do we compute or estimate the gradient $d(P(X=x))/dw$?

LONG VERSION:

Take the following situation where we want to perform maximum likelihood estimation (MLE) using stochastic gradient descent (SGD).

We have a very simple directed graphical model with two random variables $X$ and $Z$, where $X$ is observed and $Z$ is latent ('hidden'), and a directed edge from $Z$ to $X$. Both are (possibly high-dimensional) real-valued random vectors. The graphical model comes with a prior distribution distribution $P(Z;w)$ parameterized by some parameters/weights $w$, and a conditional distribution $P(X|Z)$ . The form of distributions don't matter now (except that they're not necessarily in the exponential family, and they're real-valued and high-dimensional, so integrating Z out is too expensive).

We want to do MLE, so we want to maximize the likelihood of the data (observations of $X$) by tuning $w$. We know that: $P(x) = \int P(x,z) dz = \int P(x|z)P(z) dz$

Now we are given one observation $x$ of $X$, and want to compute the likelihood gradient w.r.t. the weights for that datapoint: $\delta_x = d(P(X))/dw$

How can this be done?

The main problem is obviously that we need to integrate out $Z$ in order to compute $P(X)$. However, this is intractable for high-dimensional $Z$.

It would be possible to approximate the integral by taking MCMC samples from $Z$. However, it's not entirely clear to me how to compute the gradient w.r.t. $w$ in that case since $w$ influences the samples through $P(Z;w)$. Anyone an idea?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

I believe it is not possible in general. I don't have a proof right now, but even the famous expectation maximization algorithm (which is the general approach for your problem) makes use of a variational lower bound to the likelihood instead of the true likelihood. This guarantees to increase the likelihood as well for most cases.

I suggest you approach the problem in the following way:

  1. Use an EM style variational lower bound to obtain a substitute for the likelihood,
  2. Differentiate that,
  3. Ascent the gradient.

My knowledge is based on chapter 11.2 of David Barber's "Bayesian Reasoning and Machine Learning" of which you can get a free ebook here. It should contain everything you need to know to make the above work.

$\endgroup$
1
  • $\begingroup$ Thanks, it's certainly possible using the variational lower bound. I've added another solution using Monte Carlo integration. $\endgroup$
    – dpkingma
    Commented Aug 23, 2012 at 15:35
0
$\begingroup$

After some thought, it's possibly to compute a stochastic gradient by Monte Carlo integration, e.g. by:

$P(X) = \int P(x|z)P(z;w)dz ≃ \frac{1}{N} \sum_z P(x|z)P(z;w)$

where in the RHS, $z$ is sampled from $\Omega$. Thus, the likelihood gradient is approximated by:

$ \frac{\partial \frac{1}{N} \sum_z P(x|z)P(z;w)}{\partial w} = \frac{1}{N} \sum_z ( P(x_z) \frac{\partial P(z;w)}{\partial w} ) $

There are more efficient versions of Monte Carlo integration, but above method seems the simplest.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.