Number of hidden units in Restricted Boltzmann Machine?

In section 12.1 of Geoff Hinton's Practical Guide to Training RBM on how to choose the number of hidden units it is stated that one should

estimate how many bits it would take to describe each data-vector if you were using a good model (i.e. estimate the typical negative log2 probability of a datavector under a good model)."

What exactly does this mean? How does one estimate a negative log2 probability of a data vector?

That text, if it's this one, seems to be alluding to information theory entropy. By definition, it's the expectation of negative log of probability, in which case "find the expectation" is what he means by "estimate."

For some intuition on why this measure makes sense, consider this from the wiki introduction:

The entropy of the message is its amount of uncertainty; it increases when the message is closer to random, and decreases when it is less random. The idea here is that the less likely an event is, the more information it provides when it occurs.

In essence, Hinton seems to suggest that the more uncertain you are of the inputs, the more hidden units you should have. This gels well with his conclusion to the same paragraph:

If the training cases are highly redundant, as they typically will be for very big training sets, you need to use fewer parameters.

To the question of calculation, I don't see how one can do this without assuming some distribution for the vector. For instance, say your data are images of digits from 0-9, and that your input encodes pixels, in the form of a 256-length vector of binary values. If you assume every pixel is as likely to be a 0 as a 1, then this value will be 256.

But say you learn that the values nearer the corners are less likely, sensible given that most writers of western digits won't near the corners. If you adjust those probabilities down and the others up, you'll find that entropy falls slightly. That is, your measure of uncertainty drops. This example is a rather ad hoc application of subjective domain knowledge, but you could also be more rigorous. E.g., estimate the distribution from the training data.

The best way to determine the optimal number of hidden units is to perform cross-validation on your final supervised task using the new representation of your data. In other words, trial and error while monitoring the performance of your reconstructions (loss) on the unsupervised task and final error on the supervised task.

I believe Hinton refers to the log-loss (aka cross-entropy) which is often used during training also in autoencoders (instead of the mean squared error).

Optimizing the log-loss is interpretable to minimizing the description length -- aka compression, which is one way of interpreting RBMs, autoencoders (undercomplete) and other dimensionality reduction algorithms.

"The principle of maximum pseudo-likelihood is based on optimizing a product of one-dimensional conditional densities under a log loss" See these slides: http://www.cs.toronto.edu/~asamir/cifar/cifarss-marlin.pdf

The typical negative log$_2$ probability $P(x_i)$ of a data vector $x_i$ refers to the average of $-$log$_2P(x)$, namely the entropy, which is given by $$\text{Entropy}[P(x)]= -\sum_i P(x_i)\text{log}_2P(x_i),$$ where the sum is over all the possible data vectors. Basically, the expression tells you how many bits of information you get when you draw a typical sample out of the data set. Entropy also represents the minimum number of bits one can use to compress the data set without loss of information. If the probability distribution $P(x)$ is not known in advance, one can estimate it by analyzing the statistics of the data.

Principle component analysis (PCA) can be used to evaluate how redundant a data set is, and thus get you closer to the real value of the entropy, but it has its limits. PCA only yields the most compact linear representation for the data.

In one of his reviews on the topic, Yoshua Bengio mentions that it's always better to have an overcomplete set of parameters than an undercomplete set. When in doubt, use slightly more units! See http://arxiv.org/pdf/1206.5533v2.pdf, section 3.2; it's short and also somewhat vague, but that is just an indication of how neural networks depend so much on the application that there is always plenty of experimenting to do to reach the optimal strategy.

To find a more compressed nonlinear representation of the data, someone suggests using Projection Pursuit (http://cseweb.ucsd.edu/~dasgupta/254-deep/nakul.pdf), but I have never used it. It's maybe worth looking into.