# Computing the likelihood gradient on a simple directed graphical model with hidden unit

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?

-
 Do you mean Z instead of Y in the first sentence? – Tyler Streeter Aug 22 '12 at 14:20 @TylerStreeter Looks that way and that is why i corrected it. There is no Y mentioned anywhere else. – Michael Chernick Aug 22 '12 at 20:32

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,

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.

-
 Thanks, it's certainly possible using the variational lower bound. I've added another solution using Monte Carlo integration. – dpkingma Aug 23 '12 at 15:35

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.

-