# Category Archives: Derivations

## Derivation: Maximum Likelihood for Boltzmann Machines

In this post I will review the gradient descent algorithm that is commonly used to train the general class of models known as Boltzmann machines. Though the primary goal of the post is to supplement another post on restricted Boltzmann machines, I hope that those readers who are curious about how Boltzmann machines are trained, but have found it difficult to track down a complete or straight-forward derivation of the maximum likelihood learning algorithm for these models (as I have), will also find the post informative.

First, a little background: Boltzmann machines are stochastic neural networks that can be thought of as the probabilistic extension of the Hopfield network. The goal of the Boltzmann machine is to model a set of observed data in terms of a set of visible random variables and a set of latent/unobserved random variables . Due to the relationship between Boltzmann machines and neural networks, the random variables are often are often referred to as “units.” The role of the visible units is to approximate the true distribution of the data, while the role of the latent variables it to extend the expressiveness of the model by capturing underlying features in the observed data. The latent variables are often referred to as hidden units, as they do not result directly from the observed data and are generally marginalized over to obtain the likelihood of the observed data, i.e.

,

where is the joint probability distribution over the visible and hidden units based on the current model parameters . The general Boltzmann machine defines through a set of weighted, symmetric connections between all visible and hidden units (but no connections from any unit to itself). The graphical model for the general Boltzmann machine is shown in Figure 1.

Given the current state of the visible and hidden units, the overall configuration of the model network is described by a connectivity function , parameterized by :

The parameter matrix defines the connection strength between the visible and hidden units. The parameters and define the connection strength amongst hidden units and visible units, respectively. The model also includes a set of biases and that capture offsets for each of the hidden and visible units.

The Boltzmann machine has been used for years in field of statistical mechanics to model physical systems based on the principle of energy minimization. In the statistical mechanics, the connectivity function is often referred to the “energy function,” a term that is has also been standardized in the statistical learning literature. Note that the energy function returns a single scalar value for any configuration of the network parameters and random variable states.

Given the energy function, the Boltzmann machine models the joint probability of the visible and hidden unit states as a Boltzmann distribution:

The partition function is a normalizing constant that is calculated by summing over all possible states of the network . Here we assume that all random variables take on discrete values, but the analogous derivation holds for continuous or mixed variable types by replacing the sums with integrals accordingly.

The common way to train the Boltzmann machine is to determine the parameters that maximize the likelihood of the observed data. To determine the parameters, we perform gradient descent on the log of the likelihood function (In order to simplify the notation in the remainder of the derivation, we do not include the explicit dependency on the parameters . To further simplify things, let’s also assume that we calculate the gradient of the likelihood based on a single observation.):

The gradient calculation is as follows:

Here we can simplify the expression somewhat by noting that , that , and also that is a constant:

If we also note that , and use the definition of conditional probability , we can further simplify the expression for the gradient:

Here is the expected value under the distribution . Thus the gradient of the likelihood function is composed of two parts. The first part is expected gradient of the energy function with respect to the conditional distribution . The second part is expected gradient of the energy function with respect to the joint distribution over all variable states. However, calculating these expectations is generally infeasible for any realistically-sized model, as it involves summing over a huge number of possible states/configurations. The general approach for solving this problem is to use Markov Chain Monte Carlo (MCMC) to approximate these sums:

Here is the sample average of samples drawn according to the process . The first term is calculated by taking the average value of the energy function gradient when the visible and hidden units are being driven by observed data samples. In practice, this first term is generally straightforward to calculate. Calculating the second term is generally more complicated and involves running a set of Markov chains until they reach the current model’s equilibrium distribution (i.e. via Gibbs sampling, Metropolis-Hastings, or the like), then taking the average energy function gradient based on those samples. See this post on MCMC methods for details. It turns out that there is a subclass of Boltzmann machines that, due to a restricted connectivity/energy function (specifically, the parameters ), allow for efficient MCMC by way of blocked Gibbs sampling. These models, known as *restricted Boltzman machines* have become an important component for unsupervised pretraining in the field of deep learning and will be the focus of a related post.

## Derivation: Derivatives for Common Neural Network Activation Functions

The material in this post has been migraged with python implementations to my github pages website.

## Derivation: Error Backpropagation & Gradient Descent for Neural Networks

The material in this post has been migraged with python implementations to my github pages website.

## The Statistical Whitening Transform

In a number of modeling scenarios, it is beneficial to transform the to-be-modeled data such that it has an identity covariance matrix, a procedure known as * Statistical Whitening*. When data have an identity covariance, all dimensions are statistically independent, and the variance of the data along each of the dimensions is equal to one. (To get a better idea of what an identity covariance entails, see the following post.)

Enforcing statistical independence is useful for a number of reasons. For example, in probabilistic models of data that exist in multiple dimensions, the joint distribution–which may be very complex and difficult to characterize–can factorize into a product of many simpler distributions when the dimensions are statistically independent. Forcing all dimensions to have unit variance is also useful. For instance, scaling all variables to have the same variance treats each dimension with equal importance.

In the remainder of this post we derive how to transform data such that it has an identity covariance matrix, give some examples of applying such a transformation to real data, and address some interpretations of statistical whitening in the scope of theoretical neuroscience.

## Decorrelation: Transforming Data to Have a Diagonal Covariance Matrix

Let’s say we have some data matrix composed of dimensions and observations ( has size ). Let’s also assume that the rows of have been centered (the mean has been subracted across all observations) . The covariance of each of the dimensions with respect to the other is

(1)

Where the covariance can be estimated from the data matrix as follows:

(2)

The covariance matrix , by definition (Equation 2) is symmetric and positive semi-definite (if you don’t know what that means, don’t worry it’s not terribly important for this discussion). Thus we can write the matrix as the product of two simpler matrices and , using a procedure known as **Eigenvalue Decomposition:**

(3)

The matrix is an -sized matrix, where each column is an eigenvector of , and is a diagonal matrix whose diagonal elements are eigenvalues that correspond to the eigenvectors of the -th column of . For more details on eigenvectors and eigenvalues see the following. From Equation (3), and using a little algebra, we can transform into the diagonal matrix

(4)

Now, imagine the goal is to transform the data matrix into a new data matrix

(5)

whose dimensions are uncorrelated (i.e. has a diagonal covariance ). Thus we want to determine the transformation that makes:

(6)

Here we derive the expression for using Equations (2), (4), (5), and (6):

(a la Equations (5) and (6))

(via Equation (2))

(via Equation (4))

now, because (see following link for details)

and thus

(7)

This means that we can transform into an uncorrelated (i.e. orthogonal) set of variables by premultiplying data matrix with the transpose of the the eigenvectors of data covariance matrix .

## Whitening: Transforming data to have an Identity Covariance matrix

Ok, so now we have a way of transforming our data so that the dimensions are uncorrelated. However, this only gives us a diagonal covariance matrix, not an Identity covariance matrix. In order to obtain an Identity covariance, we also need to scale each dimension so that its variance is equal to one. How can we determine this transformation? We know how to transform our data so that the covariance is equal to . If we can determine the transformation that leaves , then we can apply this transformation to our decorrelated covariance to give us the desired whitening transform. We can determine this from the somewhat trivial notion that

(8)

and further that

(9)

Now, using Equation (4) along with Equation (8), we can see that

(10)

Now say that we define a variable , where is the desired whitening transform, that leaves the covariance of equal to the identity matrix. Using essentially the same set of derivation steps as above to solve for , but starting from Equation (9) we find that

(11)

(12)

Thus, the whitening transform is simply the decorrelation transform, but scaled by the inverse of the square root of the (here the inverse and square root can be performed element-wise because is a diagonal matrix).

## Interpretation of the Whitening Transform

So what does the whitening transformation actually do to the data (below, blue points)? We investigate this transformation below: The first operation decorrelates the data by premultiplying the data with the eigenvector matrix , calculated from the data covariance. This decorrelation can be thought of as a rotation that reorients the data so that the principal axes of the data are aligned with the axes along which the data has the largest (orthogonal) variance. This rotation is essentially the same procedure as the oft-used * Principal Components Analysis (PCA)*, and is shown in the middle row.

The second operation, scaling by can be thought of squeezing the data–if the variance along a dimension is larger than one–or stretching the data–if the variance along a dimension is less than one. The stretching and squeezing forms the data into a sphere about the origin (which is why whitening is also referred to as “sphering”). This scaling operation is depicted in the bottom row in the plot above.

The MATLAB to make make the plot above is here:

% INITIALIZE SOME CONSTANTS mu = [0 0]; S = [1 .9; .9 3]; % SAMPLE SOME DATAPOINTS nSamples = 1000; samples = mvnrnd(mu,S,nSamples)'; % WHITEN THE DATA POINTS... [E,D] = eig(S); % ROTATE THE DATA samplesRotated = E*samples; % TAKE D^(-1/2) D = diag(diag(D).^-.5); % SCALE DATA BY D samplesRotatedScaled = D*samplesRotated; % DISPLAY figure; subplot(311); plot(samples(1,:),samples(2,:),'b.') axis square, grid xlim([-5 5]);ylim([-5 5]); title('Original Data'); subplot(312); plot(samplesRotated(1,:),samplesRotated(2,:),'r.'), axis square, grid xlim([-5 5]);ylim([-5 5]); title('Decorrelate: Rotate by V'); subplot(313); plot(samplesRotatedScaled(1,:),samplesRotatedScaled(2,:),'ko') axis square, grid xlim([-5 5]);ylim([-5 5]); title('Whiten: scale by D^{-1/2}');

The transformation in Equation (11) and implemented above whitens the data but leaves the data aligned with principle axes of the original data. In order to observe the data in the original space, it is often customary “un-rotate” the data back into it’s original space. This is done by just multiplying the whitening transform by the inverse of the rotation operation defined by the eigenvector matrix. This gives the whitening transform:

(13)

Let’s take a look an example of using statistical whitening for a more complex problem: whitening patches of images sampled from natural scenes.

## Example: Whitening Natural Scene Image Patches

Modeling the local spatial structure of pixels in natural scene images is important in many fields including computer vision and computational neuroscience. An interesting model of natural scenes is one that can account for interesting, high-order statistical dependencies between pixels. However, because natural scenes are generally composed of continuous objects or surfaces, a vast majority of the spatial correlations in natural image data can be explained by local pairwise dependencies. For example, observe the image below.

% LOAD AND DISPLAY A NATURAL IMAGE im = double(imread('cameraman.tif')); figure imagesc(im); colormap gray; axis image; axis off; title('Base Image')

Given one of the gray pixels in the upper portion of the image, it is very likely that all pixels within the local neighborhood will also be gray. Thus there is a large amount of correlation between pixels in local regions of natural scenes. Statistical models of local structure applied to natural scenes will be dominated by these pairwise correlations, unless they are removed by preprocessing. Whitening provides such a preprocessing procedure.

Below we create and display a dataset of local image patches of size extracted at random from the image above. Each patch is rastered out into a column vector of size . Each of these patches can be thought of as samples of the local structure of this natural scene. Below we use the whitening transformation to remove pairwise correlations between pixels in each patch and scale the variance of each pixel to be one.

On the left is the dataset of extracted image patches, along with the corresponding covariance matrix for the image patches on the right. The large local correlation within the neighborhood of each pixel is indicated by the large bright diagonal regions throughout the covariance matrix.

The MATLAB code to extract and display the patches shown above is here:

% CREATE PATCHES DATASET FROM NATURAL IMAGE rng(12345) imSize = 256; nPatches = 400; % (MAKE SURE SQUARE) patchSize = 16; patches = zeros(patchSize*patchSize,nPatches); patchIm = zeros(sqrt(nPatches)*patchSize); % PAD IMAGE FOR EDGE EFFECTS im = padarray(im,[patchSize,patchSize],'symmetric'); % EXTRACT PATCHES... for iP = 1:nPatches pix = ceil(rand(2,1)*imSize); rows = pix(1):pix(1)+patchSize-1; cols = pix(2):pix(2)+patchSize-1; tmp = im(rows,cols); patches(:,iP) = reshape(tmp,patchSize*patchSize,1); rowIdx = (ceil(iP/sqrt(nPatches)) - 1)*patchSize + ... 1:ceil(iP/sqrt(nPatches))*patchSize; colIdx = (mod(iP-1,sqrt(nPatches)))*patchSize+1:patchSize* ... ((mod(iP-1,sqrt(nPatches)))+1); patchIm(rowIdx,colIdx) = tmp; end % CENTER IMAGE PATCHES patchesCentered = bsxfun(@minus,patches,mean(patches,2)); % CALCULATE COVARIANCE MATRIX S = patchesCentered*patchesCentered'/nPatches; % DISPLAY PATCHES figure; subplot(121); imagesc(patchIm); axis image; axis off; colormap gray; title('Extracted Patches') % DISPLAY COVARIANCE subplot(122); imagesc(S); axis image; axis off; colormap gray; title('Extracted Patches Covariance')

Below we implement the whitening transformation described above to the extracted image patches and display the whitened patches that result.

On the left, we see that the whitening procedure zeros out all areas in the extracted patches that have the same value (zero is indicated by gray). The whitening procedure also boosts the areas of high-contrast (i.e. edges). The right plots the covariance matrix for the whitened patches. The covarance matrix is diagonal, indicating that pixels are now independent. In addition, all diagonal entries have the same value, indicating the that all pixels now have the same variance (i.e. 1). The MATLAB code used to whiten the image patches and create the display above is here:

%% MAIN WHITENING % DETERMINE EIGENECTORS & EIGENVALUES % OF COVARIANCE MATRIX [E,D] = eig(S); % CALCULATE D^(-1/2) d = diag(D); d = real(d.^-.5); D = diag(d); % CALCULATE WHITENING TRANSFORM W = E*D*E'; % WHITEN THE PATCHES patchesWhitened = W*patchesCentered; % DISPLAY THE WHITENED PATCHES wPatchIm = zeros(size(patchIm)); for iP = 1:nPatches rowIdx = (ceil(iP/sqrt(nPatches)) - 1)*patchSize + 1:ceil(iP/sqrt(nPatches))*patchSize; colIdx = (mod(iP-1,sqrt(nPatches)))*patchSize+1:patchSize* ... ((mod(iP-1,sqrt(nPatches)))+1); wPatchIm(rowIdx,colIdx) = reshape(patchesWhitened(:,iP),... [patchSize,patchSize]); end figure subplot(121); imagesc(wPatchIm); axis image; axis off; colormap gray; caxis([-5 5]); title('Whitened Patches') subplot(122); imagesc(cov(patchesWhitened')); axis image; axis off; colormap gray; %colorbar title('Whitened Patches Covariance');

## Investigating the Whitening Matrix: implications for theoretical neuroscience

So what does the whitening matrix look like, and what does it do? Below is the whitening matrix calculated for the image patches dataset:

% DISPLAY THE WHITENING MATRIX figure; imagesc(W); axis image; colormap gray; colorbar title('The Whitening Matrix W')

Each column of is the operation that scales the variance of the corresponding pixel to be equal to one and forces that pixel independent of the others in the patch. So what exactly does such an operation look like? We can get an idea by reshaping a column of W back into the shape of the image patches. Below we show what the 86th column of W looks like when reshaped in such a way (the index 86 has no particular significance, it was chosen at random):

% DISPLAY A COLUMN OF THE WHITENING MATRIX figure; imagesc(reshape(W(:,86),16,16)), colormap gray, axis image, colorbar title('Column 86 of W')

We see that the operation is essentially an impulse centered on the 86th pixel in the image (counting pixels starting in the upper left corner, proceeding down columns). This impulse is surrounded by inhibitory weights. If we were to look at the remaining columns of , we would find that that the same center-surround operation is being replicated at every pixel location in each image patch. Essentially, the whitening transformation is performing a convolution of each image patch with a center-surround filter whose properties are estimated from the patches dataset. Similar techniques are common in computer vision edge-detection algorithms.

## Implications for theoretical neuroscience

A theoretical function of the primate retina is data compression: a large number of photoreceptors pass data from the retina into a physiological bottleneck, the optic nerve, which has far fewer fibers than retinal photoreceptors. Thus removing redundant information is an important task that the retina must perform. When observing the whitened image patches above, we see that redundant information is nullified; pixels that have similar local values to one another are zeroed out. Thus, statistical whitening is a viable form of data compression

It turns out that there is a large class of ganglion cells in the retina whose spatial receptive fields exhibit…that’s right center-surround activation-inhibition like the operation of the whitening matrix shown above! Thus it appears that the primate visual system may be performing data compression at the retina by means of a similar operation to statistical whitening. Above, we derived the center-surround whitening operation based on data sampled from a natural scene. Thus it is seems reasonable that the primate visual system may have evolved a similar data-compression mechanism through experience with natural scenes, either through evolution, or development.

## Derivation: The Covariance Matrix of an OLS Estimator (and applications to GLS)

We showed in an earlier post that for the linear regression model

,

the optimal Ordinary Least Squares (OLS) estimator for model parameters is

However, because independent variables and responses can take on any value, they are both random variables. And, because is a linear combination of and , it is also a random variable, and therefore has a covariance. The definition of the covariance matrix for the OLS estimator is defined as:

where, denotes the expected value operator. In order to find an expression for , we first need an expression for . The following derives this expression:

,

where we use the fact that

.

It follows that

and therefore

Now following the original definition for …

where we take advantage of in order to rewrite the second term in the product of the expectation. If we take to be fixed for a given estimator of (in other words we don’t randomly resample the independent variables), then the expectation only depends on the remaining stochastic/random variable, namely . Therefore the above expression can be written as

.

where is the covariance of the noise term in the model. Because OLS assumes uncorrelated noise, the noise covariance is equal to , where is the variance along each dimension, and is an identity matrix of size equal to the number of dimensions. The expression for the estimator covariance is now:

,

which simplifies to

A further simplifying assumption made by OLS that is often made is that is drawn from a zero mean multivariate Guassian distribution of unit variances (i.e. ), resulting in a noise covariance equal to the identity. Thus

## Applying the derivation results to Generalized Least Squares

Notice that the expression for the OLS estimator covariance is equal to first inverse term in the expression for the OLS estimator. Identitying the covariance for the OLS estimator in this way gives a helpful heuristic to easily identify the covariance of related estimators that do not make the simplifying assumptions about the covariance that are made in OLS. For instance in Generalized Least Squares (GLS), it is possible for the noise terms to co-vary. The covariance is represented as a noise covariance matrix . This gives the model form

,

where .

In otherwords, under GLS, the noise terms have zero mean, and covariance . It turns out that estimator for the GLS model parameters is

.

Notice the similarity between the GLS and OLS estimators. The only difference is that in GLS, the solution for the parameters is scaled by the inverse of the noise covariance. And, in a similar fashion to the OLS estimator, the covariance for the GLS estimator is first term in the product that defines the GLS estimator:

## Derivation: Ordinary Least Squares Solution and Normal Equations

The material in this post has been migrated to a post by the same name on my github pages website.