Binary Sparse Coding

Question

In this binary sparse coding paper referenced in the Goodfellow/Bengio/Courville deep learning book (https://fias.uni-frankfurt.de/~bornschein/papers/HennigesEtAl_lva2010.pdf), the parameter $\pi=p(s_i = 1)$ is learned and not a hyperparameter. As far as I can tell, there is no prior imposed on the value of $\pi$.

My question is: why should we expect the learned codes to be sparse? Couldn't $\pi$ be quite large? I suppose if $\pi$ is close to 1.0, then we can consider the "opposite" code as being sparse. But I don't see why $\pi$ shouldn't want to be 0.50.

If there is no reason to expect that $\pi$ is far from 0.50, I don't understand why the scheme is called Binary Sparse Coding or why the codes values are mostly 0s or mostly 1s.

Thank you humans of CrossValidated for your help!

Answer 1

After corresponding with the author, I think I understand.

If we have too many hidden units, it is entirely possible that the weights for these units may be used to model noise in the dataset.

However, even when we recover exactly the correct factors, and if the code values are real numbers instead of binary values, then the best code $h$ for a visible $v$ will use some small values on the irrelevant factors for this example, simply because every factor has probability $1.0$ of being not-orthogonal to the noise in $v$.

The binary sparse coding technique avoids this simply by disallowing you from using "small" scalings of factors. Every factor is either in or out.

Answer 2

Binary Sparse Coding is just the method itself. This method has to be trained, for instance using variational EM.

The model selection prior $p(s|\Theta) = \prod_h^H (\pi_h)^{s_h} (1-\pi_h)^{1-s_h}$ however does imply a specific sparsity due to the selection of the design variables $x$ (if given) and coefficients $w_{ij}$.

In fact, minimizing the Kullback-Leibler divergence between the approximated posterior $q(\theta)$ and the real posterior $p(s|y,\Theta)$ does imply minimizing the noise deviation, which is $||y-Ws||^2_2$ for Gaussian noise.

But the sparsity, assuming the noise distribution hits the real noise good enough, does come from the selection prior and the data itself. The model is forced to describe as many data $y$ as possible by turning on and off the right components and refining them in order to the data.

The more independent those components are from each other, the better the model can do so and the higher the approximate posterior probability for specific units given a specific data point $y^{(n)}$. (see https://www.researchgate.net/publication/220848054_Binary_Sparse_Coding)

The less the true noise differs from a Gaussian the the less the weights should look like noise, except if the data is too occupied. For example, if knowing the exact causes and generating target data $y$ with around $\bar\pi=0.5$ or higher, the number of latents must be higher than the exact number of causes. And even than it might be too occupied to extract the right causes, especially with very less data.

For example, in regression problems, the design variable intersection per data point might be very high, but the true causes are considered sparse (see https://arxiv.org/abs/1904.07150).