From Image Filtering to Learnable Convolutional Layers

When an image is filtered, the output is another image that contains the filter’s response at each spatial location, e.g., one with its edges emphasized. We could also think of such an image as a feature map that indicates where certain features were detected in the image—e.g., edges. However, in a deep network the initial filtered images or feature maps are subjected to many further levels of filtering. Over many successive filter applications this produces spatially organized neurons that respond to much more complex inputs, and the term “feature map” becomes more descriptive.

When viewed as layers in a neural network that takes an image as input, these filtering operations can be viewed as constraining spatially organized neurons to respond only to features that are within a limited region of the input known as the neuron’s receptive field. When groups of such neurons respond in the same way to the same types of input we say they have shared parameters—but each neuron forming the feature map responds only when certain inputs are detected at corresponding spatially restricted receptive fields in the image.

Consider a simple example with a 1D vector x. A filtering operation can be implemented by multiplying it by a matrix W that has a special structure, such as

$\begin{array}{ll}\mathbf{y}\hfill & =\mathbf{W}\mathbf{x}\hfill \\ \hfill & =\left[\begin{array}{cccccc}{w}_1& w_2& w_3& & & \\ & w_1& w_2& w_3& & \\ & & & \ddots & & \\ & & & w_1& w_2& w_3\end{array}\right],\hfill \end{array}$

where the blank elements are zero. This matrix corresponds to a simple filter having only three nonzero coefficients and a “stride” of one. To account for samples at the beginning and end of the input, or pixels at the edge of the image in the 2D case, zeros can be placed before the start and end, or around the image boundary—e.g., a zero could be added to the start and end of x above, in which case the output would have the same size as the input. If we dispensed with zero-padding, the valid part of the convolution would be restricted to filter responses computed from input data.

If the rows of a 2D image were packed into one long column vector, a version of this same 3×3 filter could be achieved by a much larger matrix W, having two other sets of three coefficients further along each row. The result would implement the multiplication and additions performed by the matrix encoding of a 2D filter. This could be thought of in another way, as an operation known in signal processing as the cross-correlation or sliding dot product, which is closely related to a computation known as convolution.

Suppose the filter above is centered by giving the first vector element an index of −1, or, in general, an index of −K, where K is the “radius” of the filter. The 1D filtering is then

$\mathbf{y}\left[n\right]=\sum _{k=-K}^K\mathbf{w}\left[k\right]\mathbf{x}[n+k].$

Directly generalizing this filtering to a 2D image X and filter W gives the cross-correlation, Y=WX, for which the result for row r and column c is

$\mathbf{Y}[r,c]=\sum _{j=-J}^J\sum _{k=-K}^K\mathbf{W}[j,k]\mathbf{X}[r+j,c+k].$

The convolution of an image with a filter, $\mathbf{Y}=\mathbf{W}*\mathbf{X}$, is obtained by flipping the sense of the filter,

$\mathbf{Y}[r,c]=\sum _{j=-J}^J\sum _{k=-K}^K\mathbf{W}[-j,-k]\mathbf{X}[r+j,c+k].$

As an example, consider the task of detecting edges in an image. A well-known technique is to filter it with so-called “Sobel” filters, which involve cross-correlating or convolving it with:

$\begin{array}{cc}{\mathbf{G}}_x=\left[\begin{array}{ccc}-1& 0& 1\\ -2& 0& 2\\ -1& 0& 1\end{array}\right],& {\mathbf{G}}_y=\left[\begin{array}{ccc}-1& -2& -1\\ 0& 0& 0\\ 1& 2& 1\end{array}\right].\end{array}$

These particular filters behave much like derivatives of the image. Fig. 10.8 shows the result: a photograph; a version filtered with the Sobel operator G_x, which emphasizes vertical edges; a version filtered with the Sobel operator G_y, which emphasizes horizontal edges; and the result of computing $\mathbf{G}=\sqrt{{\mathbf{G}}_x^2+{\mathbf{G}}_y^2}$. The center two images have been scaled so that midgray corresponds to zero, while the intensity is flipped in the last one to make large values darker and white zero.

Rather than using predetermined filters, convolutional networks jointly learn sets of convolutional filters and a classifier that takes them as input, everything being learned together by backpropagation. By convolving the image with filters successively within the layers of a neural network spatially organized hidden layers can be created, which, as discussed above, could be thought of as feature activity maps indicating where a given feature type has been detected within the image. While filters and activation functions are not specifically constructed as shown in Fig. 10.8, edge-like filters and texture-like filters are frequently observed in the early layers of CNNs that have been trained using natural images. Since each layer in a CNN involves filtering the feature map produced by the layer below, as one moves upwards the receptive field of any given neuron or feature detector becomes larger. As a result, after learning, higher-level layers detect larger features, which often correspond to small pieces of objects in midlevel layers, and quite large pieces of objects toward the top of the network. Fig. 10.9 shows examples of the strongest activation of some random neurons in each layer, projecting the activation back into image space using deconvolution.

Spatial pooling operations applied to the result of a convolutional network are frequently used to impart a degree of local spatial invariance to the precise locations where features have been detected. If pooling is done by averaging, it can be implemented using convolutions. CNNs often apply multiple layers of convolution, followed by pooling and decimation layers. It is common to have about three phases of pooling and decimation. After the last pooling and decimation layer the resulting feature maps are typically fed into a multilayer perceptron. Since decimation reduces the size of feature maps, each such operation reduces the size of subsequent activity maps. Extremely deep convolutional network architectures (having more than 8 layers) typically repeat convolutional layers many times before applying the pooling and decimation operations.

Fig. 10.10 shows a numerical example of the key operations of convolution, pooling, and decimation. First, an image is convolved with the (flipped) filter shown on the left. The curved rectangular regions in the image matrix depict a random set of image locations. The next matrix shows the result of the convolution operation, and here the maximum values within small 2×2 regions are indicated in bold. Next the result is pooled, using max-pooling in this case; and then the pooled matrix is decimated by a factor of two to yield the final result.

Convolutional Layers and Gradients

Let us consider how to compute the gradients needed to optimize a convolutional network. At a given layer we have i=1,…, N^(l) feature filters and corresponding feature maps. The convolutional kernel matrices K_i contain flipped weights with respect to kernel weight matrices W_i. With activation function act(), and for each feature type i a scaling factor g_i and bias matrix B_i, the feature maps are matrices H_i(A_i(X)) and can be visualized as a set of feature map images given by

${\mathbf{H}}_i=g_i\text{act}[{\mathbf{K}}_i*\mathbf{X}+{\mathbf{B}}_i]=g_i\text{act}[{\mathbf{A}}_i(\mathbf{X})].$

The loss $L=L({\mathbf{H}}_1^{(l)},\cdots ,{\mathbf{H}}_{N^{(l)}}^{(l)})$ is a function of the N^(l) feature maps for a given layer. Define h=vec(H), x=vec(X), a=vec(A), where the vec() function returns a vector with stacked columns of the given matrix argument. Choose an act() function that operates elementwise on an input matrix of preactivations and has scale parameters of 1 and biases of 0. The partial derivatives of the hidden layer output with respect to X of the convolutional units are

$\frac{\partial L}{\partial \mathbf{X}}=\sum _i\sum _j\sum _k\frac{\partial a_{ijk}}{\partial \mathbf{X}}\frac{\partial {\mathbf{H}}_i}{\partial a_{ijk}}\frac{\partial L}{\partial {\mathbf{H}}_i}=\sum _i\frac{\partial {\mathbf{a}}_i}{\partial \mathbf{x}}\frac{\partial {\mathbf{h}}_i}{\partial {\mathbf{a}}_i}\frac{\partial L}{\partial {\mathbf{h}}_i}=\sum _i[{\mathbf{W}}_i*{\mathbf{D}}_i],$

where ${\mathbf{D}}_i=dL/\partial {\mathbf{A}}_i$ is a matrix containing the partial derivative of the elementwise act() function’s input with respect to its preactivation value for the ith feature type, organized according to spatial positions given by row j and column k. Intuitively, the result is a sum of the convolution of each of the (zero padded) filters W_i with an image-like matrix of derivatives D_i. The partial derivatives of the hidden layer output are

$\frac{\partial L}{\partial {\mathbf{W}}_i}=\sum _j\sum _k\frac{\partial a_{ijk}}{\partial {\mathbf{W}}_i}\frac{\partial {\mathbf{H}}_i}{\partial a_{ijk}}\frac{\partial L}{\partial {\mathbf{H}}_i}=\left[{\mathbf{X}}^{†}*{\mathbf{D}}_i\right],$

where ${\mathbf{X}}^{†}$ is the row- and column-flipped version of the input X (if the convolution is written as a linear matrix operation, this will involve just a matrix transpose).

Pooling and Subsampling Layers and Gradients

Consider applying a pooling operation to a spatially organized feature map. The input consists of matrices H_i for each feature map, with elements h_ijk. The max pooled and average pooled feature maps are matrices P_i with elements p_ijk given by

$\begin{array}{cc}{p}_{i,j,k}={\displaystyle \underset{\begin{array}{l}r\in R_{j,k},\\ c\in C_{j,k}\end{array}}{\max }}{h}_{i,r,c},& p_{i,j,k}=\frac{1}{m}\sum _{{\displaystyle \underset{c\in C_{j,k}}{r\in R_{j,k},}}}{h}_{i,r,c},\end{array}$

respectively, where R_j,k and C_j,k are sets of indices that encode the pooling regions for each location j, k, and m is the number of elements in the pooling region. Although these pooling operations do not include a subsampling step, they typically account for boundary effects either by creating a matrix P_i that is slightly smaller than the input matrix H_i, or by padding with zeros. The subsampling step either samples every nth output, or avoids needless computation by only evaluating every nth pooling computation.

What are the consequences of backpropagating gradients through layers consisting of max or average pooling? In the former case, the units that are responsible for the maximum within each zone j, k —the “winning units”—are given by

${\{r^{*},c^{*}\}}_{j,k}=\underset{r\in R_{j,k},c\in C_{j,k}}{\arg \max }{h}_{i,r,c}.$

For nonoverlapping zones, the gradient is propagated back from the pooled layer P_i to the original spatial feature layer H_i, flowing from each p_ijk to just the winning unit in each zone. This can be written

$\frac{\partial L}{\partial h_{i,r_j,c_k}}=\{\begin{array}{cc}0& r_j\ne r_j^{*},c_k\ne c_k^{*}\\ \frac{\partial L}{\partial p_{i,j,k}}& r_j=r_j^{*},c_k=c_k^{*}\end{array}.$

In the latter case, average pooling, the averaging operation is simply a special type of convolution with a fixed kernel that computes the (possibly weighted) average of pixels in a zone, so the required gradients are computed using the result above. These various pieces are the building blocks that allow for the implementation of a CNN according to a given architecture.

Implementation

Convolutions are particularly well suited to implementation on graphics hardware. Since graphics hardware can accelerate convolutions by an order of magnitude or more over CPU implementations, it plays an important role in training CNNs. An experimental turn-around time of days rather than weeks makes a huge difference to model development times.

It can also be challenging to construct software for learning a CNN in such a way that alternative architectures can be explored. Although early GPU implementations were hard to extend, newer tools allow for both fast computation and flexible high-level programming primitives. Some of these tools are discussed at the end of this chapter; many of them allow gradient computations and the backpropagation algorithm for large networks to be almost completely automated.

Pretraining Deep Autoencoders With Rbms

Deep autoencoders are an effective framework for nonlinear dimensionality reduction. Once such a network has been built, the top-most layer of the encoder, the code layer h_c, can be input to a supervised classification procedure. If a neural network classifier is used, the entire deep autoencoder network can be discriminatively fine-tuned using gradient descent. In effect, the autoencoder approach is used to pretrain a neural network classifier.

However, it is difficult to optimize autoencoders with multiple hidden layers in both encoder and decoder. It is well known that initializing any deep neural network with weights that are too large leads to poor local minima; while initialization with weights that are too small can lead to small gradients that make learning slow. One approach is to be very careful about the choices of activation function and initialization. However, this has been found difficult in practice.

Another approach is based on pretraining by stacking two-layered RBMs. RBMs are a generalized form of probabilistic PCA with binary hidden variables and binary or continuous observed variables that can perform unsupervised learning; they are discussed further in Section 10.5; To use them for pretraining, start by learning a 2-layer RBM from the data, project the data into its hidden-layer representation, use that to train another RBM, and repeat the process until the encoding layer is reached. The details of how this is done is described in Section 10.5. The parameters of each two-layer network are then used to initialize the parameters of an autoencoder with a similar structure that has nonstochastic sigmoid hidden units.

Denoising Autoencoders and Layerwise Training

One can also use greedy layerwise training strategies involving plain autoencoders to train deep autoencoders, but attempts to do this for networks of even moderate depth have encountered difficulties. Procedures based on stacking denoising autoencoders have been found to work better. Denoising autoencoders are trained to remove different types of noise that has been added synthetically to their inputs. Autoencoder inputs can be corrupted with noise such as: Gaussian noise; masking noise, where some elements are set to 0; and salt-and-pepper noise, where some elements are set to minimum and maximum input values (such as 0 and 1).

Using autoencoders with stochastic hidden units involves fairly minor modifications to backpropagation based learning. In essence, these procedures resemble dropout. In contrast, more general stochastic models like RBMs rely on approximate probabilistic inference techniques, and the procedures for learning deep stochastic models tend to be quite elaborate (see Section 10.5).

Combining Reconstructive and Discriminative Learning

When an autoencoder is used to learn a feature representation intended for classification or regression, a model can be defined that both reconstructs inputs and classifies inputs. This hybrid model has a composite loss that consists of a reconstructive (unsupervised) and a discriminative (supervised) criterion, $L(\theta )=(1-\lambda )L_{\mathrm{s}\mathrm{up}}(\theta )+\lambda L_{\mathrm{unsup}}(\theta )$, where the hyperparameter $\lambda \in [0,1]$ controls the balance between the two objectives. In the extreme cases, $\lambda =0$ yields a purely supervised training procedure, while $\lambda =1$ yields a purely unsupervised training procedure. If some data is only available without labels, one can optimize just a reconstructive loss. For the hybrid model, one could imagine augmenting the deep autoencoder of Fig. 10.12 to make predictions using h_c as input, either with a single set of weights leading to an activation function and final prediction, or with multiple layers prior to making a prediction. Training with a combined objective function appears to provide a form of regularization that can lead to increased performance on the discriminative task. When combined with more numerically well-behaved activation functions like ReLUs this procedure has been found to allow deeper models to be learned with fewer problems. Of course, one must be careful to tune $\lambda$ on a validation set. Some similar approaches can be taken with the stochastic methods below, which can be defined in both generative and discriminative forms.

Boltzmann Machines

To create a Boltzmann machine we begin by partitioning variables into ones that are visible, defined by a D-dimensional binary vector $\mathbf{v}\in {\{0,1\}}^D$, and ones that are hidden, defined by a K-dimensional binary vector $\mathbf{h}\in {\{0,1\}}^K$. Then a Boltzmann machine is a joint probability model of the form

$\begin{array}{c}p(\mathbf{v},\mathbf{h};\theta )=\frac{1}{Z(\theta )}\exp (-E(\mathbf{v},\mathbf{h};\theta )),\\ Z(\theta )={\displaystyle \sum _{\mathbf{v}}}{\displaystyle \sum _{\mathbf{h}}}\exp (-E(\mathbf{v},\mathbf{h};\theta )),\\ E(\mathbf{v},\mathbf{h};\theta )=-\frac{1}{2}{\mathbf{v}}^T\mathbf{A}\mathbf{v}-\frac{1}{2}{\mathbf{h}}^T\mathbf{B}\mathbf{h}-{\mathbf{v}}^T\mathbf{W}\mathbf{h}-{\mathbf{a}}^T\mathbf{v}-{\mathbf{b}}^T\mathbf{h},\end{array}$

where $E(\mathbf{v},\mathbf{h};\theta )$ is the energy function, $Z(\theta )$ normalizes E so that it defines a valid joint probability, the matrices A, B, and W encode the visible-to-visible, hidden-to-hidden, and visible-to-hidden variable interactions, respectively, and vectors a and b encode the biases associated with each variable. Matrices A and B are symmetric, and their diagonal elements are 0. This structure is effectively a binary Markov random field with pairwise connections between all variables, illustrated in Fig. 10.14A.

A key feature of Boltzmann machines (and binary Markov random fields in general) is that the conditional distribution of one variable given the others is a sigmoid function whose argument is a weighted linear combination of the states of the other variables:

$\begin{array}{c}p(h_j=1|\mathbf{v},{\mathbf{h}}_{\neg j};\theta )=\mathrm{sigmoid}\left(\sum _{i=1}^D{W}_{ij}{v}_i+\sum _{k=1}^K{B}_{jk}{h}_k+b_j\right),\\ p(v_i=1|\mathbf{h},{\mathbf{v}}_{\neg i};\theta )=\mathrm{sigmoid}\left(\sum _{j=1}^K{W}_{ij}{h}_j+\sum _{d=1}^D{A}_{id}{v}_d+c_i\right),\end{array}$

where the notation $\neg i$ indicates all elements with subscript other than i. The diagonal elements of A and B are zero, so there is no need for the sum to skip terms involving $h_{k=j}$ and $v_{d=i}$, since they are zero anyway. The fact that these equations are separate sigmoid functions for each variable makes it easy to construct a Gibbs’ sampler (Section 9.5), which can be used to compute approximations to the conditional probability $p(\mathbf{h}|\tilde{\mathbf{v}})$ and the joint probability $p(\mathbf{h},\mathbf{v})$.

Define the loss as the negative log-likelihood of the marginal probability for a single example $\tilde{\mathbf{v}}$ under the Boltzmann machine model: $L=-\log p(\tilde{\mathbf{v}};\theta )=-\log {\sum }_{\mathbf{h}}p(\tilde{\mathbf{v}},\mathbf{h};\theta )$. Then, based on some calculus, the partial derivatives can be shown to be

$\begin{array}{l}\frac{\partial L}{\partial \mathbf{W}}=-[\mathrm{E}{\left[\tilde{\mathbf{v}}{\mathbf{h}}^T\right]}_{P(\mathbf{h}|\tilde{\mathbf{v}})}-\mathrm{E}{\left[\mathbf{v}{\mathbf{h}}^T\right]}_{P(\mathbf{h},\mathbf{v})}],\hfill \\ \frac{\partial L}{\partial \mathbf{A}}=-[\tilde{\mathbf{v}}{\tilde{\mathbf{v}}}^T-\mathrm{E}{\left[\mathbf{v}{\mathbf{v}}^T\right]}_{P(\mathbf{h},\mathbf{v})}],\hfill \\ \frac{\partial L}{\partial \mathbf{B}}=-[\mathrm{E}{\left[\mathbf{h}{\mathbf{h}}^T\right]}_{P(\mathbf{h}|\tilde{\mathbf{v}})}-\mathrm{E}{\left[\mathbf{h}{\mathbf{h}}^T\right]}_{P(\mathbf{h},\mathbf{v})}],\hfill \\ \frac{\partial L}{\partial \mathbf{a}}=-[\tilde{\mathbf{v}}-\mathrm{E}{\left[\mathbf{v}\right]}_{P(\mathbf{h},\mathbf{v})}],\hfill \\ \frac{\partial L}{\partial \mathbf{b}}=-[\mathrm{E}{\left[\mathbf{h}\right]}_{P(\mathbf{h}|\tilde{\mathbf{v}})}-\mathrm{E}{\left[\mathbf{h}\right]}_{P(\mathbf{h},\mathbf{v})}].\hfill \end{array}$

The distributions $p(\mathbf{h}|\tilde{\mathbf{v}})$ and $p(\mathbf{h},\mathbf{v})$ needed to compute the expectations in these derivatives are not available in analytic form, but samples approximating them can be used instead. To compute the gradient of the negative log-likelihood over an entire training set with N examples, the sum of the terms is N times a single expectation using the empirical distribution of the data $P_{data}(\tilde{\mathbf{v}})$, or the distribution obtained by placing a delta function on each example and dividing by N. A sum over a training set involving expectations of the form $p(\mathbf{h}|\tilde{\mathbf{v}})$ is sometimes written as a single expectation and referred to as the data-dependent expectation, whereas the expectations involving $p(\mathbf{h},\mathbf{v})$ do not depend on the data and are referred to as the model’s expectation.

Using these equations and approximations for the distributions, one can implement optimization via gradient descent. Gradients in probabilistic models often come down to computing differences of expectations, as in models such as logistic regression, conditional random fields, and even probabilistic principal component analysis, as we saw in Chapter 9, Probabilistic methods.

Restricted Boltzmann Machines

Eliminating connections between hidden variables, and connections between visible variables, yields a restricted Boltzmann machine (RBM), with the same distribution $p(\mathbf{v},\mathbf{h};\theta )=Z^{-1}(\theta )\exp (-E(\mathbf{v},\mathbf{h};\theta ))$ but this energy function:

$E(\mathbf{v},\mathbf{h};\theta )=-{\mathbf{v}}^T\mathbf{W}\mathbf{h}-{\mathbf{a}}^T\mathbf{v}-{\mathbf{b}}^T\mathbf{h}.$

Fig. 10.14B shows the result of this transformation on Fig. 10.14A; while Fig. 10.14C shows a more general form.

Eliminating the coupling matrices A and B means that that the exact inference step for h, the entire vector of hidden variables, can be performed in one shot. $p(\mathbf{h}|\mathbf{v})$ becomes the product of a different sigmoid for each dimension, each sigmoid depending only on the observed input vector v. $p(\mathbf{v}|\mathbf{h})$ has a similar form.

$\begin{array}{c}p(\mathbf{h}|\mathbf{v})=\prod _{k=1}^{K}p(h_k|\mathbf{v})=\prod _{k=1}^K\text{Bern}(h_k;\mathrm{sigmoid}(b_k+{\mathbf{W}}_{\cdot k}^T\mathbf{v})),\\ p(\mathbf{v}|\mathbf{h})=\prod _{i=1}^{D}p(v_i|\mathbf{h})=\prod _{i=1}^D\text{Bern}(v_i;\mathrm{sigmoid}(a_i+{\mathbf{W}}_{i\cdot }\mathbf{h})),\end{array}$

where ${\mathbf{W}}_{\cdot k}^{\mathrm{T}}$ is a vector consisting of the transpose of the kth column of the weight matrix $\mathbf{W}$, while ${\mathbf{W}}_{i\cdot }$ is the ith row of $\mathbf{W}$. These are conditional distributions that are derived from the underlying joint model, and the equations can be used to compute the gradient of the loss with respect to W, a, and b. The expectations needed for learning are easier to compute than for an unrestricted model: an exact expression can be obtained for $p(\mathbf{h}|\tilde{\mathbf{v}})$, but $p(\mathbf{h},\mathbf{v})$ remains intractable and must be approximated.

Contrastive Divergence

Running a Gibbs sampler for a Boltzmann machine often requires many iterations, and a technique called “contrastive divergence” is a popular alternative that initializes the sampler to the observed data instead of randomly and performs a limited number of Gibbs updates. In an RBM, a sample ${\stackrel{\mathbf{ˆ}}{\mathbf{h}}}^{(0)}$ can be generated from the distribution $p(\mathbf{h}|{\stackrel{\mathbf{ˆ}}{\mathbf{v}}}^{(0)}=\tilde{\mathbf{v}})$ followed by a sample for ${\stackrel{\mathbf{ˆ}}{\mathbf{v}}}^{(1)}$ from $p(\mathbf{v}|{\stackrel{\mathbf{ˆ}}{\mathbf{h}}}^{(1)})$. This single step often works well in practice, although the process of alternating the sampling of hidden and visible units can be continued for multiple steps.

Categorical and Continuous Variables

The RBMs discussed so far have been composed of binary variables. However, they can be extended to categorical or continuous attributes by encoding r=1,…, R visible categorical variables using one-hot vectors ${\mathbf{v}}_{(r)}$ and defining hidden binary variables h with the following energy function

$E(\mathbf{v},\mathbf{h};\theta )=-\sum _{r=1}^R\left[{\mathbf{v}}_{(r)}^T{\mathbf{W}}_{(r)}\mathbf{h}+{\mathbf{a}}_{(r)}^T{\mathbf{v}}_{(r)}\right]-{\mathbf{b}}^T\mathbf{h}.$

The joint distribution defined by this model is complex, but as for binary RBMs the conditional distributions under the model for one layer given the other have simple forms:

$\begin{array}{l}p(\mathbf{h}|{\mathbf{v}}_{(r=1,\dots ,R)})=\prod _{k=1}^K\mathrm{Bern}\left(h_k;\mathrm{sigmoid}\left(b_k+\sum _{r=1}^R{\mathbf{W}}_{(r)\cdot k}^T{\mathbf{v}}_{(r)}\right)\right),\hfill \\ p({\mathbf{v}}_{(r=1,\dots ,R)}|\mathbf{h})=\prod _{r=1}^R\mathrm{Cat}\left({\mathbf{v}}_{(r)};\text{softmax}({\mathbf{a}}_{(r)}+{\mathbf{W}}_{(r)\cdot }\mathbf{h})\right),\hfill \end{array}$

A model with a layer of continuous observed variables v and a layer of hidden binary variables h can be constructed using this energy function:

$E(\mathbf{v},\mathbf{h};\theta )=-{\mathbf{v}}^T\mathbf{W}\mathbf{h}-\frac{1}{2}{(\mathbf{v}-\mathbf{a})}^2-{\mathbf{b}}^T\mathbf{h}.$

The conditional distributions are

$\begin{array}{l}p(\mathbf{h}|\mathbf{v})=\prod _{k=1}^K\mathrm{Bern}\left(h_k;\mathrm{sigmoid}(b_k+{\mathbf{W}}_{\cdot k}^T\mathbf{v})\right),\\ p(\mathbf{v}|\mathbf{h})=\prod _{i=1}^{D}N(v_i;a_i+{\mathbf{W}}_{i\cdot }\mathbf{h},1)=N(\mathbf{v};\mathbf{a}+\mathbf{W}\mathbf{h},\mathbf{I}),\end{array}$

where the conditional distribution of the observed variables given the hidden is a Gaussian whose mean depends on a bias term plus a linear transformation of the binary hidden variable. This Gaussian has an identity covariance matrix and can therefore be written as a product of independent Gaussians for each dimension.

Deep Boltzmann Machines

Deep Boltzmann machines involve coupling layers of random variables using RBM connectivity, as illustrated in Fig. 10.15A. Assuming Bernoulli random variables, the energy function is

$\begin{array}{ll}E(\mathbf{v},{\mathbf{h}}^{(1)},\dots ,{\mathbf{h}}^{(L)};\theta )\hfill & =-{\mathbf{v}}^T{\mathbf{W}}^{(1)}{\mathbf{h}}^{(1)}-{\mathbf{a}}^T\mathbf{v}-{\mathbf{b}}^{(1)T}{\mathbf{h}}^{(1)}\hfill \\ \hfill & -\left[\sum _{l=2}^L\left[{\mathbf{h}}^{(l-\text{1})T}{\mathbf{W}}^{(l)}{\mathbf{h}}^{(l)}+{\mathbf{b}}^{(l)T}{\mathbf{h}}^{(l)}\right]\right],\hfill \end{array}$

where the layers are coupled with matrices ${\mathbf{W}}^{(l)}$, and $\mathbf{a}$ and ${\mathbf{b}}^{(l)}$ are the biases for the visible layer and each hidden layer. The gradients for the intermediate layer matrices are

$\begin{array}{l}\frac{\partial L}{\partial {\mathbf{W}}^{(l)}}=-[\mathrm{E}{\left[{\mathbf{h}}^{(l-1)}{\mathbf{h}}^{(l)T}\right]}_{P({\mathbf{h}}^{(l-1)},{\mathbf{h}}^{(l)T}|\tilde{\mathbf{v}})}-\mathrm{E}{\left[{\mathbf{h}}^{(l-1)}{\mathbf{h}}^{(l)T}\right]}_{P({\mathbf{h}}^{(l-1)},{\mathbf{h}}^{(l)T},\mathbf{v})}],\hfill \\ \frac{\partial L}{\partial {\mathbf{b}}^{(l)}}=-[\mathrm{E}{\left[{\mathbf{h}}^{(l)}\right]}_{P({\mathbf{h}}^{(l)}|\tilde{\mathbf{v}})}-\mathrm{E}{\left[{\mathbf{h}}^{(l)}\right]}_{P({\mathbf{h}}^{(l)},\mathbf{v})}],\hfill \end{array}$

where the probability distributions needed for the expectations can be computed using approximate inference techniques such as Gibbs sampling or variational methods.

Examining the Markov blanket of a layer in this network shows that, given the layers above and below, variables in a given layer are independent of other layers. The conditional distribution is

$\begin{array}{l}p({\mathbf{h}}^{(l)}|{\mathbf{h}}^{(l-1)},{\mathbf{h}}^{(l+1)})=\prod _{k_l=1}^{K_l}p(h_k^l|{\mathbf{h}}^{(l-1)},{\mathbf{h}}^{(l+1)})\hfill \\ =\prod _{k=1}^{K_l}\mathrm{Bern}\left(h_k^l;\mathrm{sigmoid}(b_k^l+{\mathbf{W}}_{\cdot k}^{(l)T}{\mathbf{h}}^{(l-1)}+{\mathbf{W}}_{k\cdot }^{(l+1)}{\mathbf{h}}^{(l+1)})\right).\hfill \end{array}$

This enables all variables in a layer to be updated in parallel using a method known as “block Gibbs sampling.” This is quicker than standard Gibbs sampling, but yields samples of sufficient quality for fast learning.

The overall learning procedure in deep Boltzmann machines using sampling or variational methods can be slow, and consequently greedy, incremental approaches are often used to initialize weights prior to learning. Deep Boltzmann machines can be trained incrementally by stacking two-layer Boltzmann machines, and learning the two-layer models using gradient descent and the contrastive divergence-based sampling procedure.

When training a deep RBM incrementally by stacking, to deal with the lack of top-down connections in the model, one can double the input variables of the lower-level model and constrain the associated matrix to be the same as the original; double the output variables of the higher-level model and constrain its matrix in the same way. Once the first Boltzmann machine has been learned, the next can be learned using either a sample from independent Bernoulli distributions for the dimensions of $p({\mathbf{h}}^{(1)}|\mathbf{v})$ based on the sigmoid models of the rewritten Boltzmann machine, or using the value of the sigmoid activations. In both cases a fast approximate inference upward pass can be performed using a doubled weight matrix to compensate for the fact that the top-down influence of the model is not captured. When generating a sampler or sigmoid activity for the final layer, it is not necessary to double the weights. Subsequent levels can be learned similarly.

Deep Belief Networks

While any deep Bayesian network is technically a deep belief network, the term “deep belief network” has become strongly associated with a particular type of deep architecture that can be constructed by training RBMs incrementally. The procedure is based on converting the lower part of a growing model into a Bayesian belief network, adding an RBM for the upper part of the model, then continuing the training, conversion, and stacking process. As we have seen above, an RBM is a two-layer joint model for which we can use some algebra to write conditional models of observed given hidden, or hidden given observed layers that are consistent with the underlying joint distribution. It therefore follows that a deep belief network can be obtained through a procedure of learning a joint RBM model for two layers, converting the model into its conditional formulation for the layer below given the layer above, then adding a new layer on top to the model, parameterizing the top two layers as a new joint RBM model, then learning the new parameters. Fig. 10.15B illustrates the general form, which can be written

$P(\mathbf{v},{\mathbf{h}}^{(1)},\dots ,{\mathbf{h}}^{(L)};\theta )=P(\mathbf{v}|{\mathbf{h}}^{(1)})\left[\prod _{l=1}^{L-2}P({\mathbf{h}}^{(l)}|{\mathbf{h}}^{(l+1)})\right]P({\mathbf{h}}^{(L-1)},{\mathbf{h}}^{(L)}),$

where as before the model is defined in terms of a visible layer $\mathbf{v}$ and l=l,…,L hidden layers ${\mathbf{h}}^{(l)}$. The conditional distributions are all products of Bernoulli distributions with sigmoidal parameterizations.

The top two layers are parameterized as an RBM. If they have directed rather than undirected connections, they can be decomposed into the form $P({\mathbf{h}}^{(L-1)},{\mathbf{h}}^{(L)})=P({\mathbf{h}}^{(L-1)}|{\mathbf{h}}^{(L)})P({\mathbf{h}}^{(L)})$, where the conditional distribution is another sigmoidally parameterized Bernoulli product and $P({\mathbf{h}}^{(L)})$ is the product over a separate distribution for each $P({\mathbf{h}}^{(L)})$. The result is known as a deep sigmoidal belief network.

The network shown in Fig. 10.15B can be constructed and trained in a layer-by-layer manner. To see this, consider a RBM with visible variables $\mathbf{v}$ and two layers of hidden variables ${\mathbf{h}}^{(1)}$ followed by ${\mathbf{h}}^{(2)}$ on top. A joint model for $P(\mathbf{v},{\mathbf{h}}^{(1)},{\mathbf{h}}^{(2)})$ can be defined as either a 3-layer Boltzmann machine, or, by restructuring the parameterization of the lower two layers, as a belief network with an RBM at the top using

$\begin{array}{l}P(\mathbf{v},{\mathbf{h}}^{(1)},{\mathbf{h}}^{(2)})=P(\mathbf{v}|{\mathbf{h}}^{(1)})P({\mathbf{h}}^{(1)},{\mathbf{h}}^{(2)})\hfill \\ =\prod _{i=1}^D\mathrm{Bern}\left(v_i;\mathrm{sigmoid}(a_i+{\mathbf{W}}_i^{(1)}\mathbf{h})\right)\cdot \frac{1}{Z(\theta )}\exp (-E({\mathbf{h}}^{(1)},{\mathbf{h}}^{(2)};\theta )),\hfill \end{array}$ (10.2)

(10.2)

where $P({\mathbf{h}}^{(1)},{\mathbf{h}}^{(2)})$ has the usual form

$\begin{array}{l}Z(\theta )={\displaystyle \sum _{{\mathbf{h}}^{(1)}}}{\displaystyle \sum _{{\mathbf{h}}^{(2)}}}\exp (-E({\mathbf{h}}^{(1)},{\mathbf{h}}^{(2)};\theta )),\hfill \\ -E({\mathbf{h}}^{(1)},{\mathbf{h}}^{(2)};\theta )={\mathbf{h}}^{(1)\mathrm{T}}{\mathbf{W}}^{(2)}{\mathbf{h}}^{(2)}+{\mathbf{b}}^{(1)T}{\mathbf{h}}^{(1)}+{\mathbf{b}}^{(2)T}{\mathbf{h}}^{(2)},\hfill \end{array}$

and the parameters ${\mathbf{W}}^{(1)}$ and $\mathbf{a}$ of $P(\mathbf{v}|{\mathbf{h}}^{(1)})$ are independent of the parameters ${\mathbf{W}}^{(1)}$, ${\mathbf{b}}^{(1)}$, and ${\mathbf{b}}^{(2)}$ of $P({\mathbf{h}}^{(1)},{\mathbf{h}}^{(2)})$.

Such networks can be trained as follows: first train a 2-layer Boltzmann machine using the observed data. Then add a layer on top, and initialize its weights to the transpose of the weights learned in the layer below. To train the next layer, compute the conditional distribution for the layer above given the layer below, and either generate a sample or use the activation of the sigmoid function to transform each example of the training data into the first hidden layer representation. The properties of a RBM can be further exploited to obtain the conditional distribution of the lower layer given the upper layer, and the parameters of the conditional model in this direction can be fixed. Once the second Boltzmann machine has been trained, the model has the form (Eq. 10.2), and the process of transforming the data, transforming the top-level Boltzmann machine into a conditional model, adding a layer, and training a top layer Boltzmann machine can be repeated as desired.

If the layer above has a different number of units, the transpose of the matrix below cannot be used for initialization and certain theoretical guarantees no longer apply. However, in practice the procedure is known to work well with random initialization.

Exploding and Vanishing Gradients

The use of L₁ or L₂ regularization can mitigate the problem of exploding gradients by encouraging weights to be small. Another strategy is to simply detect if the norm of the gradient exceeds some threshold and, if so, scale it down. This is sometimes called gradient (norm) clipping. That is, for a gradient vector $\mathbf{g}=\partial L/\partial \mathbf{\theta }$ and threshold T,

$\begin{array}{c}\mathrm{if}\Vert \mathbf{g}\Vert \ge T\mathrm{then}\\ \mathbf{g}\leftarrow \frac{T}{\Vert \mathbf{g}\Vert }\mathbf{g}\end{array}$

T is a hyperparameter, which can be set to the average norm over several previous updates where clipping was not used.

The so-called “LSTM” recurrent neural network architecture was specifically created to address the vanishing gradient problem. It uses a special combination of hidden units, elementwise products and sums between units to implement gates that control “memory cells.” These cells are designed to retain information without modification for long periods of time. They have their own input and output gates, which are controlled by learnable weights that are a function of the current observation and the hidden units at the previous time step. As a result, backpropagated error terms from gradient computations can be stored and propagated backwards without degradation. The original LSTM formulation consisted of input gates and output gates, but forget gates and “peephole weights” were added later. The architecture is complex, but has produced state-of-the-art results on a wide variety of problems. Below we present the most popular variant of LSTM RNNs, which does not include peephole weights but does use forget gates.

LSTM RNNs work as follows: at each time step there are three types of gate, input ${\mathbf{i}}_t$, forget ${\mathbf{f}}_t$, and output ${\mathbf{o}}_t$, each being a function of the underlying input ${\mathbf{x}}_t$ at time t and the hidden units at time t–1, ${\mathbf{h}}_{t-1}$. Gates multiply ${\mathbf{x}}_t$ by their own gate-specific W matrix ${\mathbf{h}}_{t-1}$, by their own U matrix, and add their own bias vector b, followed by the application of a sigmoidal elementwise nonlinearity.

At each time step t, input gates ${\mathbf{i}}_t=\mathrm{sigmoid}({\mathbf{W}}_i{\mathbf{x}}_t+{\mathbf{U}}_i{\mathbf{h}}_{t-1}+{\mathbf{b}}_i)$ are used to determine whether a potential input given by ${\mathbf{s}}_t=\tan \mathrm{h}({\mathbf{W}}_c{\mathbf{x}}_t+{\mathbf{U}}_c{\mathbf{h}}_{t-1}+{\mathbf{b}}_c)$ is sufficiently important to be placed into the memory unit ${\mathbf{c}}_t$. The computation of ${\mathbf{s}}_t$ itself is a linear combination of the current input value ${\mathbf{x}}_t$ and the previous hidden unit vector ${\mathbf{h}}_{t-1}$, using weight matrices ${\mathbf{W}}_c$ and ${\mathbf{U}}_c$ along with a bias vector ${\mathbf{b}}_c$. Forget gates ${\mathbf{f}}_t$ allow the content of memory units to be erased using ${\mathbf{f}}_t=\mathrm{sigmoid}({\mathbf{W}}_f{\mathbf{x}}_t+{\mathbf{U}}_f{\mathbf{h}}_{t-1}+{\mathbf{b}}_f)$, involving a similar linear input based on ${\mathbf{W}}_f$ and ${\mathbf{U}}_f$ matrices, plus a bias ${\mathbf{b}}_f$. Output gates ${\mathbf{o}}_t$ determine whether ${\mathbf{y}}_t$, the content of the memory units transformed by activation functions, should be placed in the hidden units ${\mathbf{h}}_t$. They are typically controlled by a sigmoidal activation function ${\mathbf{o}}_t=\mathrm{sigmoid}({\mathbf{W}}_o{\mathbf{x}}_t+{\mathbf{U}}_o{\mathbf{h}}_{t-1}+{\mathbf{b}}_o)$ applied to a linear combination of the current input value ${\mathbf{x}}_t$ and the previous hidden unit vector ${\mathbf{h}}_{t-1}$, using weight matrices ${\mathbf{W}}_o$ and ${\mathbf{U}}_o$ along with a bias vector ${\mathbf{b}}_o$.

This final gating is implemented as an elementwise product between the output gate and the transformed memory contents, ${\mathbf{h}}_t={\mathbf{o}}_t\circ {\mathbf{y}}_t$, where memory units are typically transformed by the tanh function prior to the gated output: ${\mathbf{y}}_t=\tan \mathrm{h}({\mathbf{c}}_t)$. Memory units are updated by ${\mathbf{c}}_t={\mathbf{f}}_t\circ {\mathbf{c}}_{t-1}+{\mathbf{i}}_t\circ {\mathbf{s}}_t$, an elementwise product between the forget gates ${\mathbf{f}}_t$ and the previous contents of the memory units ${\mathbf{c}}_{t-1}$, plus the elementwise product of the input gates ${\mathbf{i}}_t$, and the new potential inputs ${\mathbf{s}}_t$. Table 10.5 defines these components, and Fig. 10.17 shows a computation graph for the intermediate quantities.

Table 10.5

Components of a “Long Short-Term Memory” Recurrent Neural Network

LSTM unit output	${\mathbf{h}}_t={\mathbf{o}}_t\circ {\mathbf{y}}_t$
Output gate units	${\mathbf{o}}_t=\mathrm{sigmoid}({\mathbf{W}}_o{\mathbf{x}}_t+{\mathbf{U}}_o{\mathbf{h}}_{t-1}+{\mathbf{b}}_o)$
Transformed memory cell contents	${\mathbf{y}}_t=\tan \mathrm{h}({\mathbf{c}}_t)$
Gated update to memory cell units	${\mathbf{c}}_t={\mathbf{f}}_t\circ {\mathbf{c}}_{t-1}+{\mathbf{i}}_t\circ {\mathbf{s}}_t$
Forget gate units	${\mathbf{f}}_t=\mathrm{sigmoid}({\mathbf{W}}_f{\mathbf{x}}_t+{\mathbf{U}}_f{\mathbf{h}}_{t-1}+{\mathbf{b}}_f)$
Input gate units	${\mathbf{i}}_t=\mathrm{sigmoid}({\mathbf{W}}_i{\mathbf{x}}_t+{\mathbf{U}}_i{\mathbf{h}}_{t-1}+{\mathbf{b}}_i)$
Potential input to memory cell	${\mathbf{s}}_t=\tanh ({\mathbf{W}}_c{\mathbf{x}}_t+{\mathbf{U}}_c{\mathbf{h}}_{t-1}+{\mathbf{b}}_c)$

Other Recurrent Network Architectures

A wide variety of other recurrent network architectures have been proposed. For example, the network given by Eq. (10.3) can be used with rectified linear activation functions, using scaled versions of the identity matrix to initialize the recurrent weight matrix, and initializing biases to zero. The identity initialization means that error derivatives flow through the network unmodified. Initializing with smaller, scaled versions of the identity matrix has the effect of causing the model to forget longer range dependencies. This approach is known as an IRNN. Another possibility is to simplify LSTM networks by dispensing with separate memory cells and using gated recurrent units or GRUs. For some problems GRUs can provide performance comparable with LSTMs, but with a lower memory requirement.

Recurrent networks can be made bidirectional, propagating information in both directions: Fig. 10.18A shows the general structure. Bidirectional networks have been used for a wide variety of applications, including protein secondary structure prediction and handwriting recognition. Modern software tools determine the gradients required for learning via backpropagation automatically, by manipulating computation graphs.

Fig. 10.18B shows an “encoder-decoder” network. Such networks allow the creation of fixed-length vector representations for variable-length inputs, and can use the fixed-length encoding to generate another variable-length sequence as the output. This is particularly useful for machine translation, where the input is a string in one language and the output is the corresponding string in another language. Given enough data, a deep encoder-decoder architecture such as that of Fig. 10.19 can yield results that compete with those of systems that have been hand-engineered over decades of research. The connectivity structure means that partial computations in the model can flow through the graph in a wave, illustrated by the darker nodes in the figure.

Theano

Theano is a library in the Python programming language that has been developed with the specific goal of facilitating research in deep learning (Bergstra et al., 2010; Theano Development Team, 2016). It is also a powerful general purpose tool for mathematical programming. Theano extends NumPy (the fundamental Python package for scientific computing) by adding symbolic differentiation and GPU support, among various other functions. It provides a high-level language for creating the mathematical expressions that underlie deep learning models, and a compiler that takes advantage of deep learning techniques, and calls to GPU libraries, to produce code that executes quickly. Theano supports execution on multiple GPUs. It allows the user to declare symbolic variables for inputs and targets, and supply numerical values only when they are used. Shared variables such as weights and biases are associated with numerical values stored in NumPy arrays. Theano creates symbolic graphs as a result of defining mathematical expressions involving the application of operations to variables. These graphs consist of variable, constant, apply, and operation nodes. Constants, and constant nodes, are a subclass of variables, and variable nodes, which hold data that will remain constant—and can therefore be subjected to various optimizations by the compiler. Theano is an open-source project using a BSD license.

Tensor Flow

Tensor Flow is a C++ and Python-based software library for the types of numerical computation typically associated with deep learning (Abadi et al., 2016). It is heavily inspired by Theano and, like it, uses dataflow graphs to represent the ways in which multidimensional data arrays communicate between one another. These multidimensional arrays are referred to as “tensors.” Tensor Flow also supports symbolic differentiation and execution on multiple GPUs. It was released in 2015 and is available under the Apache 2.0 license.

Torch

Torch is an open-source machine learning library built using C and a high-level scripting language known as Lua (Collobert, Kavukcuoglu, & Farabet, 2011). It uses multidimensional array data structures, and supports various basic numerical linear algebra manipulations. It has a neural network package with modules that permit the typical forward and backward methods needed for training neural networks. It also supports automatic differentiation.

Computational Network Toolkit

The Computational Network Toolkit (CNTK) is a C++ library for manipulating computational networks (Yu et al., 2014). It was produced by Microsoft Research, but has been released under a permissive license. It has been popular for speech and language processing, but also supports convolutional networks of the type used for images. It supports execution on multiple machines and using multiple GPUs.

Caffe

Caffe is a C++ and Python-based BSD-licensed CNN library (Jia et al., 2014). It has a clean and extensible design that makes it a popular alternative to the original open-source implementation of Krizhevsky et al.’s (2012) famous AlexNet that won the 2012 ImageNet challenge.

Deeplearning4j

Deeplearning4j is a Java-based open-source deep learning library available under the Apache 2.0 license. It uses an multidimensional array class and provides linear algebra and matrix manipulation support similar to that provided by Numpy.

Other Packages: Lasagne, Keras, and cuDNN

Lasagne is a lightweight Python library built on top of Theano that simplifies the creation of neural network layers. Similarly, Keras is a Python library that runs on top of either Theano or TensorFlow (Chollet, 2015). It allows one to quickly define a network architecture in terms of layers and also includes functionality for image and text preprocessing. cuDNN is a highly optimized GPU library for NVIDIA units that allows deep networks to be trained more quickly. It can dramatically accelerate the performance of a deep network and is often called by the other packages above.