Bounding the Test Log-Likelihood of Generative Models
Authors: Yoshua Bengio, Li Yao, KyungHyun Cho
ICLR 2014

Abstract: Several interesting generative learning algorithms involve a complex probability distribution over many random variables, involving intractable normalization constants or latent variable normalization. Some of them may even not have an analytic expression for the unnormalized probability function and no tractable approximation. This makes it difficult to estimate the quality of these models, once they have been trained, or to monitor their quality (e.g. for early stopping) while training. A previously proposed method is based on constructing a non-parametric density estimator of the model's probability function from samples generated by the model. We revisit this idea, propose a more efficient estimator, and prove that it provides a lower bound on the true test log-likelihood, and an unbiased estimator as the number of generated samples goes to infinity, although one that incorporates the effect of poor mixing (making the estimated likelihood worse, i.e., more conservative).


Peer review:
[Review]:
The paper proposes a method for estimating the log probability of any probabilistic
model that can generate samples.  The method builds a local density estimator around
the samples using the model's conditional probability, 
which is used to evaluate the log probability of a test set.  An important
selling point of the method is that it evaluates the probabilistic model and the 
sampling procedure jointly, and that it is asymptotically consistent, in the sense
that the estimates converge to the true likelihood as the number of samples approaches
infinity.

This work is quite novel, and it places the idea of used by Breuleux et al. in a 
rigorous framework.  Empirically, the method works well on small models, although
it exhibits very substantial divergence from AIS on larger models, as shown in Table 1.

Perhaps the greatest weakness of this method, which is worth discussing, is that
the number of samples that's needed in order to accurate compute a log probability
grows exponentially with the entropy of the distribution.  For an example, consider
the dataset consisting the concatenations of of 10 randomly chosen MNIST digits.  It is 
fairly clear any sample set <<< 10^10 will vastly underestimate the log probability
of a perfectly good sample. That is unfortunate, because it means that the method will
not work well on complicated models of high entropy distributions, such as images or speech. 

This weakness notwithstanding, the method is very adequate for model comparison.  

To summarize:  Pros:  interesting method for obtaining conservative underestimates of the log probability,
works with nearly any model.

Cons:  method's complexity is exponential in the distribution's entropy;  the proposed fix is no longer 
conservative.