cardinality Restricted Boltzmann Machines

Overview

Restricted Boltzmann Machine (RBM) is a probabilistic model which is usually represented by a graphical model. RBM can encode a probability distribution and therefore can be used for density estimation. It can also be viewed as a generative stochastic model of a neural network (with one hidden layer). Although interesting by itself, popularity of RBM started from the time that Hinton and others used it as the building blocks of Deep Belief Networks (DBNs). From the computational point of view, the good characteristic of RBN is that the posterior over hidden variables is factorizable.

At least two notions of sparsity can be investigated for graphical models. The first notion is the sparsity of the graph (i.e., something related to the number of edges in the graph). In this sense, a sparse model is one that has a lot of independencies in its structure. However, this is not the focus of this paper. In fact, the structure of RBM is fixed.

The other notion of sparsity is the usual definition in the other approaches. In the neural network literature, it means that we do not want the entire neurons to be activated in the same time. For our RBM, we want that the values of hidden variables be sparse for (almost) all inputs.

Motivations and Challenges

Sparsity is usually regarded as a good property for modeling complex phenomenons. From theoretical point of view, statisticians sometimes relate it to the idea of shrinkage. Also, experimental analysis shows that it is certainly useful. In particular, it has been suggested that sparse deep architectures can be very efficient. Finally, sparsity increases the interpretability of data.

The problem is for RBM is that if we want to add sparsity constraints, then the hidden variables would be coupled together. Therefore, the posterior would not be factorizable anymore, which makes sparse RBM intractable.

RBM Formulation

Assume [math]\displaystyle{ v \in \{0,1\}^{N_v} }[/math] and [math]\displaystyle{ h \in \{0,1\}^{N_h} }[/math] are the vectors of binary valued variables, corresponding to visible and hidden variables respectively. For RBM, the joint probability over these variables is defined as follows:

[math]\displaystyle{ P(v,h) = \frac{1}{Z} exp(v^{T}Wh+v^{T}b_{v}+h^{T}b_{h}) }[/math]

where [math]\displaystyle{ Z }[/math] is just a normalization factor and [math]\displaystyle{ W,b_{v},b_{h} }[/math] are the parameters.

One way to find the parameters is to optimize the likelihood function. However, finding an exact solution is not tractable. Therefore, an approximation of the gradient, called "contrastive divergence", is used for learning the parameters.

The Sparse RBM (SpRBM)

The idea of SpRBM is simple. We add a penalty term to the log-likelihood objective in order to encourage sparsity. The penalty term used in SpRBM is

[math]\displaystyle{ \frac{}{} \lambda (\rho \log{q_{j}} + (1 - \rho) \log{(1-q_{j})}) }[/math]

where [math]\displaystyle{ q_{j} = \frac{1}{N}\sum{P(h_{j}=1|v_{n})} }[/math] reflects the average unit marginal.

The Cardinality RBM (CaRBM)

The difference between CaRBM and the standard RBM is in the joint probability model. In particular, it has an additional factor

[math]\displaystyle{ P(v,h) = \frac{1}{Z} exp(v^{T}Wh+v^{T}b_{v}+h^{T}b_{h}). \psi_k (\sum^{N_h}_{j=1} h_j ) }[/math]

where [math]\displaystyle{ \psi_k (.) }[/math] is the potential function and [math]\displaystyle{ \psi_k (c)=1 }[/math] if [math]\displaystyle{ c \le 1 }[/math]. Therefore, the potential function ensures that the hidden variables are sparse with sparsity parameter equal to [math]\displaystyle{ k }[/math].

Note that [math]\displaystyle{ P(v|h) }[/math] is still easy to compute. However, computing the posterior [math]\displaystyle{ P(h|v) }[/math] is not easy anymore. Fortunately, there is an efficient inference algorithm for computing the marginals and therefore the posterior. This algorithm can be regarded as a dynamic programming; also, it can be interpreted as the sum-product algorithm. The authors prefer the sum-product explanation and define some auxiliary variables [math]\displaystyle{ z_j }[/math] that encode the sum of the first [math]\displaystyle{ j }[/math] hidden variables. Now the new variables are easier to use for the cardinality potential due to the chain-type dependency between them. Finally, we have a chain-structured graphical model and we can perform exact inference using sum-product algorithm.

Using CaRBM for DBNs

The original DBN builds upon layers of RBMs. These layers are trained layer-by-layer in a greedy and unsupervised manner. Then, the learned parameters are used to initialize a typical gradient-descent algorithm for learning deep neural networks. The challenge for doing this is to select an appropriate non-linearity in the deep neural network. We can not simply use an arbitrary function (e.g., hyperbolic tangent) because in that case the solution of RBM will not be a good initialization for the deep network.

The non-linear function [math]\displaystyle{ \mu }[/math] should be selected in way that

[math]\displaystyle{ \mu (W^{T}v+b_{h}) = \mathbb{E}_{P(h|v)}[h] }[/math]

For RBM, this results in a simple sigmoid function for [math]\displaystyle{ \mu }[/math]. However, for CaRBM the solution is not clear. In fact, there does not seem to be a closed-form solution. Instead, we can still encorporate the above formula (i.e., the expectation of the hidden variables) and use message-passing algorithm as the non-linearity.

Furthermore, the gradient is hard to compute for back-propagation. The authors suggest using a finite difference method for computing the Jacobian and therefore the gradient.