Restricted Boltzmann machine

Machine learning and data mining

Problems Classification Clustering Regression Anomaly detection Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Supervised learning (classification • regression) Decision trees Ensembles (Bagging, Boosting, Random forest) k-NN Linear regression Naive Bayes Neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH Hierarchical k-means Expectation-maximization (EM) DBSCAN OPTICS Mean-shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA t-SNE
Structured prediction Graphical models (Bayes net, CRF, HMM)
Anomaly detection k-NN Local outlier factor
Neural nets Autoencoder Deep learning Multilayer perceptron RNN Restricted Boltzmann machine SOM Convolutional neural network
Theory Bias-variance dilemma Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine learning venues NIPS ICML JMLR ArXiv:cs.LG
Machine learning portal

Diagram of a restricted Boltzmann machine with three visible units and four hidden units (no bias units).

A restricted Boltzmann machine (RBM) is a generative stochastic artificial neural network that can learn a probability distribution over its set of inputs.

RBMs were initially invented under the name Harmonium by Paul Smolensky in 1986,^[1] but only rose to prominence after Geoffrey Hinton and collaborators invented fast learning algorithms for them in the mid-2000s. RBMs have found applications in dimensionality reduction,^[2] classification,^[3] collaborative filtering,^[4] feature learning^[5] and topic modelling.^[6] They can be trained in either supervised or unsupervised ways, depending on the task.

As their name implies, RBMs are a variant of Boltzmann machines, with the restriction that their neurons must form a bipartite graph: a pair of nodes from each of the two groups of units (commonly referred to as the "visible" and "hidden" units respectively) may have a symmetric connection between them; and there are no connections between nodes within a group. By contrast, "unrestricted" Boltzmann machines may have connections between hidden units. This restriction allows for more efficient training algorithms than are available for the general class of Boltzmann machines, in particular the gradient-based contrastive divergence algorithm.^[7]

Restricted Boltzmann machines can also be used in deep learning networks. In particular, deep belief networks can be formed by "stacking" RBMs and optionally fine-tuning the resulting deep network with gradient descent and backpropagation.^[8]

Structure

The standard type of RBM has binary-valued (Boolean/Bernoulli) hidden and visible units, and consists of a matrix of weights $W = (w_{i,j})$ (size m×n) associated with the connection between hidden unit $h_j$ and visible unit $v_i$ , as well as bias weights (offsets) $a_i$ for the visible units and $b_j$ for the hidden units. Given these, the energy of a configuration (pair of boolean vectors) $(v, h)$ is defined as

E(v,h) = -\sum_i a_i v_i - \sum_j b_j h_j -\sum_i \sum_j v_i w_{i,j} h_j

or, in matrix notation,

E(v,h) = -a^{\mathrm{T}} v - b^{\mathrm{T}} h -v^{\mathrm{T}} W h

This energy function is analogous to that of a Hopfield network. As in general Boltzmann machines, probability distributions over hidden and/or visible vectors are defined in terms of the energy function:^[9]

P(v,h) = \frac{1}{Z} e^{-E(v,h)}

where $Z$ is a partition function defined as the sum of $e^{-E(v,h)}$ over all possible configurations (in other words, just a normalizing constant to ensure the probability distribution sums to 1). Similarly, the (marginal) probability of a visible (input) vector of booleans is the sum over all possible hidden layer configurations:^[9]

P(v) = \frac{1}{Z} \sum_h e^{-E(v,h)}

Since the RBM has the shape of a bipartite graph, with no intra-layer connections, the hidden unit activations are mutually independent given the visible unit activations and conversely, the visible unit activations are mutually independent given the hidden unit activations.^[7] That is, for $m$ visible units and $n$ hidden units, the conditional probability of a configuration of the visible units $v$ , given a configuration of the hidden units $h$ , is

P(v|h) = \prod_{i=1}^m P(v_i|h)

Conversely, the conditional probability of $h$ given $v$ is

P(h|v) = \prod_{j=1}^n P(h_j|v)

The individual activation probabilities are given by

P(h_j=1|v) = \sigma \left(b_j + \sum_{i=1}^m w_{i,j} v_i \right)\,

and

\,P(v_i=1|h) = \sigma \left(a_i + \sum_{j=1}^n w_{i,j} h_j \right)

where $\sigma$ denotes the logistic sigmoid.

The visible units of RBM can be multinomial, although the hidden units are Bernoulli. In this case, the logistic function for visible units is replaced by the softmax function

P(v_i^k = 1|h) = \frac{\exp(a_i^k + \Sigma_j W_{ij}^k h_j)} {\Sigma_{k=1}^K \exp(a_i^k + \Sigma_j W_{ij}^k h_j)}

where K is the number of discrete values that the visible values have. They are applied in topic modeling,^[6] and recommender systems.^[4]

Relation to other models

Restricted Boltzmann machines are a special case of Boltzmann machines and Markov random fields.^[10]^[11] Their graphical model corresponds to that of factor analysis.^[12]

Training algorithm

Restricted Boltzmann machines are trained to maximize the product of probabilities assigned to some training set $V$ (a matrix, each row of which is treated as a visible vector $v$ ),

\arg\max_W \prod_{v \in V} P(v)

or equivalently, to maximize the expected log probability of $V$ :^[10]^[11]

\arg\max_W \mathbb{E} \left[\sum_{v \in V} \log P(v)\right]

The algorithm most often used to train RBMs, that is, to optimize the weight vector $W$ , is the contrastive divergence (CD) algorithm due to Hinton, originally developed to train PoE (product of experts) models.^[13]^[14] The algorithm performs Gibbs sampling and is used inside a gradient descent procedure (similar to the way backpropagation is used inside such a procedure when training feedforward neural nets) to compute weight update.

The basic, single-step contrastive divergence (CD-1) procedure for a single sample can be summarized as follows:

Take a training sample $v$ , compute the probabilities of the hidden units and sample a hidden activation vector $h$ from this probability distribution.
Compute the outer product of $v$ and $h$ and call this the positive gradient.
From $h$ , sample a reconstruction $v'$ of the visible units, then resample the hidden activations $h'$ from this. (Gibbs sampling step)
Compute the outer product of $v'$ and $h'$ and call this the negative gradient.
Let the weight update to $w_{i,j}$ be the positive gradient minus the negative gradient, times some learning rate: $\Delta w_{i,j} = \epsilon (vh^\mathsf{T} - v'h'^\mathsf{T})$ .

The update rule for the biases $a$ , $b$ is defined analogously.

A Practical Guide to Training RBMs written by Hinton can be found in his homepage.^[9]

References

↑ Smolensky, Paul (1986). "Chapter 6: Information Processing in Dynamical Systems: Foundations of Harmony Theory" (PDF). In Rumelhart, David E.; McLelland, James L. Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Volume 1: Foundations. MIT Press. pp. 194–281. ISBN 0-262-68053-X.
↑ Hinton, G. E.; Salakhutdinov, R. R. (2006). "Reducing the Dimensionality of Data with Neural Networks" (PDF). Science 313 (5786): 504–507. doi:10.1126/science.1127647. PMID 16873662.
↑ Larochelle, H.; Bengio, Y. (2008). Classification using discriminative restricted Boltzmann machines (PDF). Proceedings of the 25th international conference on Machine learning - ICML '08. p. 536. doi:10.1145/1390156.1390224. ISBN 9781605582054.
1 2 Salakhutdinov, R.; Mnih, A.; Hinton, G. (2007). Restricted Boltzmann machines for collaborative filtering. Proceedings of the 24th international conference on Machine learning - ICML '07. p. 791. doi:10.1145/1273496.1273596. ISBN 9781595937933.
↑ Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). An analysis of single-layer networks in unsupervised feature learning (PDF). International Conference on Artificial Intelligence and Statistics (AISTATS).
1 2 Ruslan Salakhutdinov and Geoffrey Hinton (2010). Replicated softmax: an undirected topic model. Neural Information Processing Systems 23.
1 2 Miguel Á. Carreira-Perpiñán and Geoffrey Hinton (2005). On contrastive divergence learning. Artificial Intelligence and Statistics.
↑ Hinton, G. (2009). "Deep belief networks". Scholarpedia 4 (5): 5947. doi:10.4249/scholarpedia.5947.
1 2 3 Geoffrey Hinton (2010). A Practical Guide to Training Restricted Boltzmann Machines. UTML TR 2010–003, University of Toronto.
1 2 Sutskever, Ilya; Tieleman, Tijmen (2010). "On the convergence properties of contrastive divergence" (PDF). Proc. 13th Int'l Conf. on AI and Statistics (AISTATS).
1 2 Asja Fischer and Christian Igel. Training Restricted Boltzmann Machines: An Introduction. Pattern Recognition 47, pp. 25-39, 2014
↑ María Angélica Cueto; Jason Morton; Bernd Sturmfels (2010). "Geometry of the restricted Boltzmann machine" (PDF). Algebraic Methods in Statistics and Probability (American Mathematical Society) 516. arXiv:0908.4425.
↑ Geoffrey Hinton (1999). Products of Experts. ICANN 1999.
↑ Hinton, G. E. (2002). "Training Products of Experts by Minimizing Contrastive Divergence" (PDF). Neural Computation 14 (8): 1771–1800. doi:10.1162/089976602760128018. PMID 12180402.

External links

Introduction to Restricted Boltzmann Machines. Edwin Chen's blog, July 18, 2011.
A Beginner's Guide to Restricted Boltzmann Machines. Deeplearning4j Documentation
Understanding RBMs. Deeplearning4j Documentation, August 4, 2015.

This article is issued from Wikipedia - version of the Saturday, April 30, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.