index   next  | Test 0.1 documentation »

Contents

- LICENSE

- Deep Learning Tutorials

- Getting Started

- Datasets

- Notation

- A Primer on Supervised Optimization for Deep Learning

- Classifying MNIST digits using Logistic Regression

- The Model

- Defining a Loss Function

- Creating a LogisticRegression class

- Learning the Model

- Testing the model

- Putting it All Together

- Introduction to Multi-Layer Perceptrons (Feedforward Neural Networks)

- Multi-Layer Neural Networks

- Most Common Training Criteria and Output Non-Linearities

- The Back-Propagation Algorithm

- Logistic Regression

- Training Multi-Layer Neural Networks

- Problème fondamentalement difficile d’optimisation

- Choix de l’architecture

- Normalisation des entrées

- Traitement des sorties désirées

- Codage des sorties désirées et des entrées discrètes

- Algorithme d’optimisation

- Initialisation des paramètres

- Contrôle de la saturation

- Contrôle de la capacité effective

- Convolutional Neural Networks (LeNet)

- Motivation

- The Model

- Going from MLP to convolutional MLP

- Putting it All Together

- References

- Stacked Denoising Autoencoders (SdA)

- Autoencoders

- Denoising Autoencoders (dA)

- Stacked Autoencoders

- Putting it all together

- Running the Code

- References

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   next  | previous  | Test 0.1 documentation »

LICENSE

Copyright (c) 2008–2009, Theano Development Team All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

- Neither the name of Theano nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ‘’AS IS’’ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   next  | previous  | Test 0.1 documentation »

Deep Learning Tutorials

Deep Learning is about learning multiple levels of representation and abstraction that help to make sense of data such as images, sound, and text. For more about deep learning algorithms, see for example:

- The monograph or review paper Learning Deep Architectures for AI [http://www.iro.umontreal.ca/~lisa/publications2/index.php/publications/show/239] (Foundations & Trends in Machine Learning, 2009).

- The ICML 2009 Workshop on Learning Feature Hierarchies webpage [http://www.cs.toronto.edu/~rsalakhu/deeplearning/index.html] has a reading list [http://www.cs.toronto.edu/~rsalakhu/deeplearning/references.html].

- The LISA public wiki [http://www.iro.umontreal.ca/~lisa/twiki/bin/view.cgi/Public/WebHome] has a reading list [http://www.iro.umontreal.ca/~lisa/twiki/bin/view.cgi/Public/ReadingOnDeepNetworks] and a bibliography [http://www.iro.umontreal.ca/~lisa/twiki/bin/view.cgi/Public/DeepNetworksBibliography].

- Geoff Hinton has readings [http://www.cs.toronto.edu/~hinton/deeprefs.html] from last year’s NIPS tutorial [http://videolectures.net/jul09_hinton_deeplearn/].

These tutorials will introduce you to some of the most important deep learning algorithms and will also show you how to run them using Theano [http://www.pylearn.org/theano]. Theano is a python library that makes writing deep learning models easy, and gives the option of training them on a GPU.

The algorithm tutorials have some prerequisites. You should know some python, and be familiar with numpy. Since this tutorial is about using Theano, you should read over the Theano basic tutorial [http://www.pylearn.org/theano/basic_tutorial] first. Once you’ve done that, read through our Getting Started chapter – it introduces the notation, and [downloadable] datasets used in the algorithm tutorials, and the way we do optimization by stochastic gradient descent.

The purely supervised learning algorithms are meant to be read in order:

1. Logistic Regression - using Theano for something simple

2. Multilayer perceptron - introduction to layers

3. Deep Convolutional Network - a simplified version of LeNet5

The unsupervised and semi-supervised learning algorithms are less co-dependent, they will make sense in any order.

- Restricted Boltzmann Macines and Deep Belief Networks

- Auto Encoders and Stacked Auto Encoders

- Denoising Auto Encoders and Stacked Denoising Auto Encoders

- encoder_decoder

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   next  | previous  | Test 0.1 documentation »

Getting Started

These tutorials do not attempt to make up for a graduate or undergraduate course in machine learning, but we do make a rapid overview of some important concepts (and notation) to make sure that we’re on the same page. You’ll also need to download the datasets mentioned in this chapter in order to run the example code the up-coming tutorials.

Datasets

MNIST Dataset

(mnist.pkl.gz [http://www.iro.umontreal.ca/~lisa/deep/data/mnist/mnist.pkl.gz])

The MNIST [http://yann.lecun.com/exdb/mnist] dataset consists of handwritten digit images and it is divided in 60 000 examples for the training set and 10 000 examples for testing. In many papers as well as in this tutorial, the official training set of 60 000 is divided into an actual training set of 50 000 examples and 10 000 validation examples (for selecting hyper-parameters like learning rate and size of the model). All digit images have been size-normalized and centered in a fixed size image of 28 x 28 pixels. In the original dataset each pixel of the image is represented by a value between 0 and 255, where 0 is black, 255 is white and anything in between is a different shade of grey.

Here are some examples of MNIST digits:

For convenience we pickled the dataset to make it easier to use in python. It is available for download here [http://www.iro.umontreal.ca/~lisa/deep/data/mnist/mnist.pkl.gz]. The pickled file represents a tuple of 3 lists : the training set, the validation set and the testing set. Each of the three lists is a pair formed from a list of images and a list of class labels for each of the images. An image is represented as numpy 1-dimensional array of 784 (28 x 28) float values between 0 and 1 (0 stands for black, 1 for white). The labels are numbers between 0 and 9 indicating which digit the image represents. When using the dataset, we usually divide it in minibatches (see Stochastic Gradient Descent). The code block below shows how to load the dataset and how to divide it in minibatches of a given size :

import cPickle, gzip, numpy

# Load the dataset

f = gzip.open('mnist.pkl.gz','rb')

train_set, valid_set, test_set = cPickle.load(f)

f.close()

# make minibatches of size 20

batch_size = 20    # sized of the minibatch

# Dealing with the training set

# get the list of training images (x) and their labels (y)

(train_set_x, train_set_y) = train_set

# initialize the list of training minibatches with empty list

train_batches = []

for i in xrange(0, len(train_set_x), batch_size):

# add to the list of minibatches the minibatch starting at

# position i, ending at position i+batch_size

# a minibatch is a pair ; the first element of the pair is a list

# of datapoints, the second element is the list of corresponding

# labels

train_batches = train_batches + \

[(train_set_x[i:i+batch_size], train_set_y[i:i+batch_size])]

# Dealing with the validation set

(valid_set_x, valid_set_y) = valid_set

# initialize the list of validation minibatches

valid_batches = []

for i in xrange(0, len(valid_set_x), batch_size):

valid_batches = valid_batches + \

[(valid_set_x[i:i+batch_size], valid_set_y[i:i+batch_size])]

# Dealing with the testing set

(test_set_x, test_set_y) = test_set

# initialize the list of testing minibatches

test_batches = []

for i in xrange(0, len(test_set_x), batch_size):

test_batches = test_batches + \

[(test_set_x[i:i+batch_size], test_set_y[i:i+batch_size])]

# accessing training example i of minibatch j

image = training_set[j][0][i]

label = training_set[j][1][i]

Notation

Dataset notation

We label data sets as . When the distinction is important, we indicate train, validation, and test sets as: , and . The validation set is used to perform model selection and hyper-parameter selection, whereas the test set is used to evaluate the final generalization error and compare different algorithms in an unbiased way.

The tutorials mostly deal with classification problems, where each data set is an indexed set of pairs . We use superscripts to distinguish training set examples: is thus the i-th training example of dimensionality . Similarly, is the i-th label assigned to input . It is straightforward to extend these examples to that has other types (e.g. Gaussian for regression, or groups of multinomials for predicting multiple symbols).

Math Conventions

- : upper-case symbols refer to a matrix unless specified otherwise

- : element at i-th row and j-th column of matrix

- : vector, i-th row of matrix

- : vector, j-th column of matrix

- : lower-case symbols refer to a vector unless specified otherwise

- : i-th element of vector

List of Symbols and acronyms

- : number of input dimensions.

- : number of hidden units in the -th layer.

- , : classification function associated with a model , defined as . Note that we will often drop the subscript.

- L: number of labels.

- : log-likelihood of the model defined by parameters .

- empirical loss of the prediction function f parameterized by on data set .

- NLL: negative log-likelihood

- : set of all parameters for a given model

Python Namespaces

Tutorial code often uses the following namespaces:

import theano

import theano.tensor as T

A Primer on Supervised Optimization for Deep Learning

What’s exciting about Deep Learning is largely the use of unsupervised learning of deep networks. But supervised learning also plays an important role. The utility of unsupervised pre-training is often evaluated on the basis of what performance can be achieved after supervised fine-tuning. This chapter reviews the basics of supervised learning for classification models, and covers the minibatch stochastic gradient descent algorithm that is used to fine-tune many of the models in the Deep Learning Tutorials.

Learning a Classifier

Zero-One Loss

The models presented in these deep learning tutorials are mostly used as for classification. The objective in training a classifier is to minimize the number of errors (zero-one loss) on unseen examples. If is the prediction function, then this loss can be written as:

where either is the training set (during training) or (to avoid biasing the evaluation of validation or test error). is the indicator function defined as:

In this tutorial, is defined as:

In python, using Theano this can be written as :

# zero_one_loss is a Theano variable representing a symbolic

# expression of the zero one loss ; to get the actual value this

# symbolic expression has to be compiled into a Theano function (see

# the Theano tutorial for more details)

zero_one_loss = T.sum(T.neq(T.argmax(p_y_given_x),y))

Negative Log-Likelihood Loss

Since the zero-one loss is not differentiable, optimizing it for large models (thousands or millions of parameters) is prohibitively expensive (computationally). We thus maximize the log-likelihood of our classifier given all the labels in a training set.

The likelihood of the correct class is not the same as the number of right predictions, but from the point of view of a randomly initialized classifier they are pretty similar. Remember that likelihood and zero-one loss are different objectives; you should see that they are corralated on the validation set but sometimes one will rise while the other falls, or vice-versa.

Since we usually speak in terms of minimizing a loss function, learning will thus attempt to minimize the negative log-likelihood (NLL), defined as:

The NLL of our classifier is a differentiable surrogate for the zero-one loss, and we use the gradient of this function over our training data as a supervised learning signal for deep learning of a classifier.

This can be computed using the following line of code :

# NLL is a symbolic variable ; to get the actual value of NLL, this symbolic

# expression has to be compiled into a Theano function (see the Theano

# tutorial for more details)

NLL = -T.sum(T.log(p_y_given_x)[y.shape[0],y])

# note on syntax: T.arange(y,shape[0]) is a vector of integers [0,1,2,...,len(y)].

# Indexing a matrix M by the two vectors [0,1,...,K], [a,b,...,k] returns the

# elements M[0,a], M[1,b], ..., M[K,k] as a vector.  Here, we use this

# syntax to retrieve the log-probability of the correct labels, y.

Stochastic Gradient Descent

What is ordinary gradient descent? it is a simple algorithm in which we repeatedly make small steps downward on an error surface defined by a loss function of some parameters. For the purpose of ordinary gradient descent we consider that the training data is rolled into the loss function. Then the pseudocode of this algorithm can be described as :

# GRADIENT DESCENT

while True:

loss = f(params)

d_loss_wrt_params = ... # compute gradient

params -= learning_rate * d_loss_wrt_params

if <stopping condition is met>:

return params

Stochastic gradient descent (SGD) works according to the same principles as ordinary gradient descent, but proceeds more quickly by estimating the gradient from just a few examples at a time instead of the entire training set. In its purest form, we estimate the gradient from just a single example at a time.

# STOCHASTIC GRADIENT DESCENT

for (x_i,y_i) in training_set:

# imagine an infinite generator

# that may repeat examples (if there is only a finite training set)

loss = f(params, x_i, y_i)

d_loss_wrt_params = ... # compute gradient

params -= learning_rate * d_loss_wrt_params

if <stopping condition is met>:

return params

The variant that we recommend for deep learning is a further twist on stochastic gradient descent using so-called “minibatches”. Minibatch SGD works identically to SGD, except that we use more than one training example to make each estimate of the gradient. This technique reduces variance in the estimate of the gradient, and often makes better use of the hierarchical memory organization in modern computers.

for (x_batch,y_batch) in train_batches:

# imagine an infinite generator

# that may repeat examples

loss = f(params, x_batch, y_batch)

d_loss_wrt_params = ... # compute gradient using theano

params -= learning_rate * d_loss_wrt_params

if <stopping condition is met>:

return params

There is a tradeoff in the choice of the minibatch size . The reduction of variance and use of SIMD instructions helps most when increasing from 1 to 2, but the marginal improvement fades rapidly to nothing. With large , time is wasted in reducing the variance of the gradient estimator, that time would be better spent on additional gradient steps. An optimal is model-, dataset-, and hardware-dependent, and can be anywhere from 1 to maybe several hundreds. In the tutorial we set it to 20, but this choice is almost arbitrary (though harmless). All code-blocks above show pseudocode of how the algorithm looks like. Implementing such algorithm in Theano can be done as follows :

# Minibatch Stochastic Gradient Descent

# assume loss is a symbolic description of the loss function given

# the symbolic variables params (shared variable), x_batch, y_batch;

# compute gradient of loss with respect to params

d_loss_wrt_params = T.grad(loss, params)

# compile the MSGD step into a theano function

updates = { params: params - learning_rate * d_loss_wrt_params}

MSGD = theano.function([x_batch,y_batch], loss, updates = updates)

for (x_batch, y_batch) in train_batches:

# here x_batch and y_batch are elements of train_batches and

# therefore numpy arrays; function MSGD also updates the params

print('Current loss is ', MSGD(x_batch, y_batch))

if <stopping condition is met>:

return params

Regularization

There is more to machine learning than optimization. When we train our model from data we are trying to prepare it to do well on new examples, not the ones it has already seen. The training loop above for MSGD does not take this into account, and may overfit the training examples. A way to combat overfitting is through regularization. There are several techniques for regularization; the ones we will explain here are L1/L2 regularization and early-stopping.

L1 and L2 regularization

L1 and L2 regularization involve adding an extra term to the loss function, which penalizes certain parameter configurations. Formally, if our loss function is:

then the regularized loss will be:

or, in our case

where

which is the norm of . is a hyper-parameter which controls the relative importance of the regularization parameter. Commonly used values for p are 1 and 2, hence the L1/L2 nomenclature. If p=2, then the regularizer is also called “weight decay”.

In principle, adding a regularization term to the loss will encourage smooth network mappings in a neural network (by penalizing large values of the parameters, which decreases the amount of nonlinearity that the network models). More intuitively, the two terms (NLL and ) correspond to modelling the data well (NLL) and having “simple” or “smooth” solutions (). Thus, minimizing the sum of both will, in theory, correspond to finding the right trade-off between the fit to the training data and the “generality” of the solution that is found. To follow Occam’s razor principle, this minimization should find us the simplest solution (as measured by our simplicity criterion) that fits the training data.

Note that the fact that a solution is “simple” does not mean that it will generalize well. Empirically, it was found that performing such regularization in the context of neural networks helps with generalization, especially on small datasets. The code block below shows how to compute the loss in python when it contains both a L1 regularization term weighted by and L2 regularization term weighted by

# symbolic Theano variable that represents the L1 regularization term

L1  = T.sum(abs(param))

# symbolic Theano variable that represents the squared L2 term

L2_sqr = T.sum(param**2)

# the loss

loss = NLL + lambda_1 * L1 + lambda_2 * L2

Early-Stopping

Early-stopping combats overfitting by monitoring the model’s performance on a validation set. A validation set is a set of examples that we never use for gradient descent, but which is also not a part of the test set. The validation examples are considered to be representative of future test examples. We can use them during training because they are not part of the test set. If the model’s performance ceases to improve sufficiently on the validation set, or even degrades with further optimization, then the heuristic implemented here gives up on much further optimization.

The choice of when to stop is a judgement call and a few heuristics exist***, but these tutorials will make use of a strategy based on a geometrically increasing amount of patience.

# PRE-CONDITION

# params refers to [initialized] parameters of our model

# early-stopping parameters

n_iter                = 100   # the maximal number of iterations of the

# entire dataset considered

patience              = 5000  # look at this many training examples regardless

patience_increase     = 2     # wait this much longer when a new best

# validation error is found

improvement_threshold = 0.995 # a relative improvement of this much is

# considered significant

validation_frequency  = 2500  # make this many SGD updates between validations

# initialize cross-validation variables

best_params = None

best_validation_loss = float('inf')

for iter in xrange( n_iter * len(train_batches) ) :

# get epoch and minibatch index

epoch           = iter / len(train_batches)

minibatch_index =  iter % len(train_batches)

# get the minibatches corresponding to `iter` modulo

# `len(train_batches)`

x,y = train_batches[ minibatch_index ]

d_loss_wrt_params = ... # compute gradient

params -= learning_rate * d_loss_wrt_params # gradient descent

# note that if we do `iter % validation_frequency` it will be

# true for iter = 0 which we do not want

if (iter+1) % validation_frequency == 0:

this_validation_loss = ... # compute zero-one loss on validation set

if this_validation_loss < best_validation_loss:

# improve patience if loss improvement is good enough

if this_validation_loss < best_validation_loss*improvement_threshold:

patience = iter * patience_increase

best_params = copy.deepcopy(params)

best_validation_loss = this_validation_loss

if patience <= iter:

break

# POSTCONDITION:

# best_params refers to the best out-of-sample parameters observed during the optimization

If we run out of batches of training data before running out of patience, then we just go back to the beginning of the training set and repeat.

Note

This algorithm could possibly be improved by using a test of statistical significance rather than the simple comparison, when deciding whether to increase the patience.

Testing

After the loop exits, the best_params variable refers to the best-performing model on the validation set. If we repeat this procedure for another model class, or even another random initialization, we should use the same train/valid/test split of the data, and get other best-performing models. If we have to choose what the best model class or the best initialization was, we compare the best_validation_loss for each model. When we have finally chosen the model we think is the best (on validation data), we report that model’s test set performance. That is the performance we expect on unseen examples.

Recap

That’s it for the optimization section. The technique of early-stopping requires us to partition the set of examples into three sets (training , validation , test ). The training set is used for minibatch stochastic gradient descent on the differentiable approximation of the objective function. As we perform this gradient descent, we periodically consult the validation set to see how our model is doing on the real objective function (or at least our empirical estimate of it). When we see a good model on the validation set, we save it. When it has been a long time since seeing a good model, we abandon our search and return the best parameters found, for evaluation on the test set.

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   next  | previous  | Test 0.1 documentation »

Classifying MNIST digits using Logistic Regression

Note

This sections assumes the reader is familiar with the following Theano concepts: shared variables [http://www.pylearn.org/theano/basic_tutorial] , basic arithmetic ops [http://www.pylearn.org/theano/basic_tutorial/adding.html] , T.grad [http://www.pylearn.org/theano/basic_tutorial/examples.html#computing-gradients] .

TODO: shared variables documentation not up !!

TODO: put shortcuts to the downloads right here (the download for the full source)

In this section, we show how Theano can be used to implement the most basic classifier: the logistic regression. We start off with a quick primer of the model, which serves both as a refresher but also to anchor the notation and show how mathematical expressions are mapped onto Theano graphs.

In the deepest of machine learning traditions, this tutorial will tackle the exciting problem of MNIST digit classification.

The Model

Logistic regression is a probabilistic, linear classifier. It is parametrized by a weight matrix and a bias vector . Classification is done by projecting data points onto a set of hyperplanes, the distance to which reflects a class membership probability.

Mathematically, this can be written as:

The output of the model or prediction is then done by taking the argmax of the vector whose i’th element is P(Y=i|x).

The code to do this in Theano is the following:

# generate symbolic variables for input (x and y represent a

# minibatch)

x = T.fmatrix()

y = T.lvector()

# allocate shared variables model params

b = theano.shared(numpy.zeros((10,)))

W = theano.shared(numpy.zeros((784,10)))

# symbolic expression for computing the vector of

# class-membership probabilities

p_y_given_x = T.softmax(T.dot(x,w)+b)

# compiled Theano function that returns the vector of class-membership

# probabilities

get_p_y_given_x = theano.function( x, p_y_given_x)

# print the probability of some example represented by x_value

# x_value is not a symbolic variable but a numpy array describing the

# datapoint

print 'Probability that x is of class %i is %f' % i, get_p_y_given_x(x_value)[i]

# symbolic description of how to compute prediction as class whose probability

# is maximal

y_pred = T.argmax(p_y_given_x)

# compiled theano function that returns this value

classify = theano.function(x, y_pred)

We first start by allocating symbolic variables for the inputs . Since the parameters of the model must maintain a persistent state throughout training, we allocate shared variables for . This declares them both as being symbolic Theano variables, but also initializes their contents. The dot and softmax operators are then used to compute the vector . The resulting variable p_y_given_x is a symbolic variable of vector-type.

Up to this point, we have only defined the graph of computations which Theano should perform. To get the actual numerical value of , we must create a function get_p_y_given_x, which takes as input x and returns p_y_given_x. We can then index its return value with the index to get the membership probability of the th class.

Now let’s finish building the Theano graph. To get the actual model prediction, we can use the T.argmax operator, which will return the index at which p_y_given_x is maximal (i.e. the class with maximum probability).

Again, to calculate the actual prediction for a given input, we construct a function classify. This function takes as argument a batch of inputs x (as a matrix), and outputs a vector containing the predicted class for each example (row) in x.

Now of course, the model we have defined so far does not do anything useful yet, since its parameters are still in their initial random state. The following section will thus cover how to learn the optimal parameters.

Note

For a complete list of Theano ops, see: list of ops [http://www.pylearn.org/theano/indexes/oplist.html]

Defining a Loss Function

Learning optimal model parameters involves minimizing a loss function. In the case of multi-class logistic regression, it is very common to use the negative log-likelihood as the loss. This is equivalent to maximizing the likelihood of the data set under the model parameterized by . Let us first start by defining the likelihood and loss :

While entire books are dedicated to the topic of minimization, gradient descent is by far the simplest method for minimizing arbitrary non-linear functions. This tutorial will use the method of stochastic gradient method with mini-batches (MSGD). See Stochastic Gradient Descent for more details.

The following Theano code defines the (symbolic) loss for a given minibatch:

loss = -T.sum(T.log(p_y_given_x)[T.arange(y.shape[0]), y])

# note on syntax: T.arange(y,shape[0]) is a vector of integers [0,1,2,...,len(y)].

# Indexing a matrix M by the two vectors [0,1,...,K], [a,b,...,k] returns the

# elements M[0,a], M[1,b], ..., M[K,k] as a vector.  Here, we use this

# syntax to retrieve the log-probability of the correct labels, y.

Note

In practice, we will use the mean (T.mean) instead of the sum. This allows for the learning rate choice to be less dependent of the minibatch size.

Creating a LogisticRegression class

We now have all the tools we need to define a LogisticRegression class, which encapsulates the basic behaviour of logistic regression. The code is very similar to what we have covered so far, and should be self explanatory.

class LogisticRegression(object):

def __init__(self, input, n_in, n_out):

""" Initialize the parameters of the logistic regression

:param input: symbolic variable that describes the input of the

architecture (e.g., one minibatch of input images)

:param n_in: number of input units, the dimension of the space in

which the datapoint lies

:param n_out: number of output units, the dimension of the space in

which the target lies

"""

# initialize with 0 the weights W as a matrix of shape (n_in, n_out)

self.W = theano.shared( value=numpy.zeros((n_in,n_out),

dtype = theano.config.floatX) )

# initialize the baises b as a vector of n_out 0s

self.b = theano.shared( value=numpy.zeros((n_out,),

dtype = theano.config.floatX) )

# compute vector of class-membership probabilities in symbolic form

self.p_y_given_x = T.nnet.softmax(T.dot(input, self.W)+self.b)

# compute prediction as class whose probability is maximal in

# symbolic form

self.y_pred=T.argmax(self.p_y_given_x, axis=1)

def negative_log_likelihood(self, y):

"""Return the negative log-likelihood of the prediction of this

model under a given target distribution.

.. math::

\mathcal{L} (\theta=\{W,b\}, \mathcal{D}) =

\sum_{i=0}^{|\mathcal{D}|} \log(P(Y=y^{(i)}|x^{(i)}, W,b)) \\

\ell (\theta=\{W,b\}, \mathcal{D})

:param y: corresponds to a vector that gives for each example the

correct label;

note: in practice we use mean instead of sum so that

learning rate is less dependent on the batch size

"""

return -T.mean(T.log(self.p_y_given_x)[T.arange(y.shape[0]),y])

We instantiate this class as follows:

# allocate symbolic variables for the data

x = T.fmatrix()  # the data is presented as rasterized images (each being a 1-D row vector in x)

y = T.lvector()  # the labels are presented as 1D vector of [long int] labels

# construct the logistic regression class

classifier = LogisticRegression( \

input=x.reshape((batch_size,28*28)), n_in=28*28, n_out=10)

Note that the inputs x and y are defined outside the scope of the LogisticRegression object. Since the class requires the input x to build its graph however, it is passed as a parameter of the __init__ function.

The last step involves defining a (symbolic) cost variable to minimize, using the instance method classifier.negative_log_likelihood.

cost = classifier.negative_log_likelihood(y)

Note that the return value of classifier.negative_log_likelihood is a vector containing the cost for each training example within the minibatch. Since we are using MSGD, the cost to minimize is the mean cost across the minibatch. Note how x is an implicit symbolic input to the symbolic definition of cost, here, because classifier.__init__ has defined its symbolic variables in terms of x.

Learning the Model

To implement MSGD in most programming languages (C/C++, Matlab, Python), one would start by manually deriving the expressions for the gradient of the loss with respect to the parameters: in this case , and , This can get pretty tricky for complex models, as expressions for can get fairly complex, especially when taking into account problems of numerical stability.

With Theano, this work is greatly simplified as it performs automatic differentiation and applies certain math transforms to improve numerical stability.

To get the gradients and in Theano, simply do the following:

# compute the gradient of cost with respect to theta = (W,b)

g_W = T.grad(cost, classifier.W)

g_b = T.grad(cost, classifier.b)

g_W and g_b are again symbolic variables, which can be used as part of a computation graph. Performing one-step of gradient descent can then be done as follows:

# set a learning rate

learning_rate=0.01

# specify how to update the parameters of the model as a dictionary

updates ={classifier.W: classifier.W - numpy.asarray(learning_rate)*g_W,\

classifier.b: classifier.b - numpy.asarray(learning_rate)*g_b}

# compiling a Theano function `train_model` that returns the cost, but in

# the same time updates the parameter of the model based on the rules

# defined in `updates`

train_model = theano.function([x, y], cost, updates = updates )

The updates dictionary contains, for each parameter, the stochastic gradient update operation. The function train_model is then defined such that:

- the inputs are the mini-batch with corresponding labels

- the return value is the cost/loss associated with inputs x, y

- on every function call, it will apply the operations defined by the updates dictionary.

Each time train_model(x,y) function is called, it will thus compute and return the appropriate cost, while also performing a step of MSGD. The entire learning algorithm thus consists in looping over all examples in the dataset, and repeatedly calling the train_model function.

Testing the model

As explained in Learning a Classifier, when testing the model we are interested in the number of misclassified examples (and not only in the likelihood). The LogisticRegression class therefore has an extra instance method, which builds the symbolic graph for retrieving the number of misclassified examples in each minibatch.

The code is as follows:

class LogisticRegression(object):

...

def errors(self, y):

"""Return a float representing the number of errors in the minibatch

over the total number of examples of the minibatch ; zero

one loss over the size of the minibatch

"""

return T.mean(T.neq(self.y_pred, y))

We then create a function test_model, which we can call to retrieve this value. As you will see shortly, test_model is key to our early-stopping implementation (see Early-Stopping).

test_model = theano.function([x,y], classifier.errors(y))

Putting it All Together

The finished product is as follows.

The user can learn to classify MNIST digits with SGD logistic regression, by typing, from within the DeepLearningTutorials folder:

python code/logistic_sgd.py

The output one should expect is of the form :

epoch 0, minibatch 2500/2500, validation error 10.720000 %

epoch 0, minibatch 2500/2500, test error of best model 11.050000 %

...

epoch 96, minibatch 2500/2500, validation error 7.010000 %

Optimization complete with best validation score of 7.01%, with test performance 7.61%

The code ran for 2.979333 minutes

On an Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00 Ghz the code runs with approximately 1.862083125 sec/epoch and it took 96 epochs to reach a test error of 7.61%.

Footnotes

[1]

For smaller datasets and simpler models, more sophisticated descent algorithms can be more effective. The sample code logistic_cg.py demonstrates how to use SciPy’s conjugate gradient solver with Theano on the logistic regression task.

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   next  | previous  | Test 0.1 documentation »

Introduction to Multi-Layer Perceptrons (Feedforward Neural Networks)

Multi-Layer Neural Networks

An MLP (for Multi-Layer Perceptron) or multi-layer neural network defines a family of functions. Let us first consider the most classical case of a single hidden layer neural network, mapping a -vector to an -vector (e.g. for regression):

where is a -vector (the input), is an matrix (called input-to-hidden weights), is a -vector (called hidden units offsets or hidden unit biases), is an -vector (called output units offset or output units biases), and is an matrix (called hidden-to-output weights).

The vector-valued function is called the output of the hidden layer. Note how the output is an affine transformation of the hidden layer, in the above network. A non-linearity may be tacked on to it in some network architectures. The elements of the hidden layer are called hidden units.

The kind of operation computed by the above can be applied on itself, but with different parameters (different biases and weights). This would give rise to a feedforward multi-layer network with two hidden layers. More generally, one can build a deep neural network by stacking more such layers. Each of these layers may have a different dimension ( above). A common variant is to have skip connections, i.e., a layer can take as input not only the layer at the previous level but also some of the lower layers.

Most Common Training Criteria and Output Non-Linearities

Let with representing the output non-linearity function. In supervised learning, the output can be compared with a target value through a loss functional . Here are common loss functionals, with the associated output non-linearity:

- for ordinary (L2) regression: no non-linearity (), squared loss .

- for median (L1) regression: no non-linearity (), absolute value loss .

- for 2-way probabilistic classification: sigmoid non-linearity (, applied element by element), and cross-entropy loss for binary. Note that the sigmoid output is in the (0,1) interval, and corresponds to an estimator of . The predicted class is 1 if .

- for multiple binary probabilistic classification: each output element is treated as above.

- for 2-way hard classification with hinge loss: no non-linearity () and the hinge loss is (again for binary ). This is the SVM classifier loss.

- the above can be generalized to multiple classes by separately considering the binary classifications of each class against the others.

- multi-way probabilistic classification: softmax non-linearity ( with one output per class) with the negative log-likelihood loss . Note that and . Note also how this is equivalent to the cross-entropy loss in the 2-class case (the output for the one of the classes is actually redundant).

The Back-Propagation Algorithm

We just apply the recursive gradient computation algorithm seen previously to the graph formed naturally by the MLP, with one node for each input unit, hidden unit and output unit. Note that each parameter (weight or bias) also corresponds to a node, and the final

Let us formalize a notation for MLPs with more than one hidden layer. Let us denote with the output vector of the i-th layer, starting with (the input), and finishing with a special output layer which produces the prediction or output of the network.

With tanh units in the hidden layers, we have (in matrix-vector notation):

- for to :

- where is a vector of biases and is a matrix of weights connecting layer to layer . The scalar computation associated with a single unit of layer is

In the case of a probabilistic classifier, we would then have a softmax output layer, e.g.,

where we used to denote the output because it is a vector indicating a probability distribution over classes. And the loss is

where is the target class, i.e., we want to maximize , an estimator of the conditional probability of class given input .

Let us now see how the recursive application of the chain rule in flow graphs is instantiated in this structure. First of all, let us denote

(for the argument of the non-linearity at each level) and note (from a small derivation) that

and that

.

Now let us apply the back-propagation recipe in the corresponding flow graph. Each parameter (each weight and each bias) is a node, each neuron potential and each neuron output is also a node.

- starting at the output node:

- then compute the gradient with respect to each pre-softmax sum :

- We can now repeat the same recipe for each layer. For down to 1

- obtain trivially the gradient wrt biases:

- compute the gradient wrt weights:

- back-propagate the gradient into lower layer, if :

Logistic Regression

Logistic regression is a special case of the MLP with no hidden layer (the input is directly connected to the output) and the cross-entropy (sigmoid output) or negative log-likelihood (softmax output) loss. It corresponds to a probabilistic linear classifier and the training criterion is convex in terms of the parameters (which garantees that there is only one minimum, which is global).

Training Multi-Layer Neural Networks

Many algorithms have been proposed to train multi-layer neural networks but the most commonly used ones are gradient-based.

Two fundamental issues guide the various strategies employed in training MLPs:

- training as efficiently as possible, i.e., getting training error down as quickly as possible, avoiding to get stuck in narrow valleys or even local minima of the cost function,

- controlling capacity so as to achieve the largest capacity avoids overfitting, i.e., to minimize generalization error.

Problème fondamentalement difficile d’optimisation

L’optimisation du critère d’apprentissage dans les réseaux de neurones multi-couches est difficile car il y a de nombreux minima locaux. On peut même démontrer que de trouver les poids optimaux est NP-dur. Cependant on se contente de trouver un bon minimum local, ou même simplement une valeur suffisamment basse du critère. Comme ce qui nous intéresse est la généralisation et non pas l’erreur d’apprentissage (ce qu’on minimise n’est pas ce qu’on voudrait vraiment minimiser), la différence entre “près d’un minimum” et “au minimum” est souvent sans importance. Par ailleurs, comme il n’y a pas de solution analytique au problème de minimisation, on est forcé de faire cette optimisation de manière itérative.

Choix de l’architecture

En principe, une manière d’accélérer la descente de gradient est de faire des choix qui rendent la matrice Hessienne mieux conditionnée. La dérivée second dans une certaine direction indique la courbure de la fonction de coût dans cette direction. Plus la courbure est grande (vallée étroite) et plus petites doivent être les mises à jour des paramètres si on éviter que l’erreur augmente. Plus précisement, le pas de gradient optimal est 1 sur la courbure. On peut voir cela par une simple expansion de Taylor du coût et est derrière le fameux algorithme de Newton pour l’optimisation. Mettons que l’on soit à et que l’on veuille choisir pour qu’il soit un minimum:

Donc on veut un pas de gradient égal à l’inverse de la dérivée seconde. On peut montrer que le nombre d’itération d’un algorithme de descente de gradient sera proportionnel au ratio de la plus grande à la plus petite valeur propre de la matrice Hessienne (avec une approximation quadratique de la fonction de coût). La raison de base en est que la plus grande valeur propre limite le pas de gradient maximum (on ne peut aller plus vite que la courbure la plus forte parmi toutes les directions possibles, sinon l’erreur remonte), mais qu’en utilisant le même pas de gradient dans toutes les directions, la convergence sera la plus longue dans la direction la plus “plate” (valeur propre la plus petite).

- En théorie une couche cachée suffit, mais cette théorie ne dit pas que cette représentation de la fonction sera efficace. En pratique cela a été le choix le plus commun avant 2006, sauf pour les réseaux de neurones à convolution (qui peuvent avoir 5 ou 6 couches par exemple). Parfois on obtient de bien meilleurs résultats avec 2 couches cachées. En fait on peut obtenir une bien meilleure généralisation avec encore plus de couches, mais une initialisation aléatoire ne fonctionne pas bien avec plus de deux couches (mais voir les travaux depuis 2006 sur l’initialisation non-supervisée vorace pour les architectures profondes).

- Pour la régression ou avec des cibles réelles et non-bornées en général, il vaut généralement mieux utiliser des neurones linéaires à la couche de sortie. Pour la classification, il vaut généralement mieux utiliser des neurones avec non-linéralité (sigmoide ou softmax) à la couche de sortie.

- Dans certains cas une connexion directe entre l’entrée et la sortie peut être utile. Dans le cas de la régression, elle peut aussi être initialisée directement par le résultat d’une régression linéaire des sorties sur les entrées. Les neurones cachées servent alors seulement à apprendre la partie non-linéaire manquante.

- Une architecture avec poids partagés, ou bien le partage de certains éléments de l’architecture (e.g., la première couche) entre les réseaux associés à plusieurs tâches connexes, peuvent significativement améliorer la généralisation. Voir aussi la discussion à venir sur les réseaux à convolution.

- Il vaut mieux utiliser utiliser une non-linéarité symétrique dans les couches cachées (comme la tanh, et non pas la sigmoide), afin d’améliorer le conditionnement du Hessien et éviter la saturation des couches cachées.

Normalisation des entrées

Il est impératif que les entrées soient de moyenne pas trop loin de zéro et de variance pas trop loin de 1. Les valeurs en entrées devraient aussi ne pas avoir une magnitude trop grande. On peut faire certaines transformations monotones non-linéaires qui réduisent les grandes valeurs. Si on a une entrée très grande, elle fait saturer plusieurs neurones et bloque l’apprentissage pour cet exemple. Les magnitudes (variances) des entrées de chaque couche devraient aussi être du même ordre quand on utilise un pas de gradient commun pour toute les couches, pour éviter que l’une des couches devienne le goulot d’étranglement (plus lent à entraîner). En fait, dans le cas linéaire, le conditionnement du Hessien est optimal quand les entrées sont normalisées (donc avec matrice de covariance = identité), ce qui peut se faire en les projetant dans l’espace des vecteurs propres de la matrice , où est la matrice de dimension nombre d’exemples par nombre d’entrées.

Traitement des sorties désirées

Dans le cas d’apprentissage par minimisation d’un coût quadratique, on doit s’assurer que les sorties désirées

- sont toujours dans l’intervalle des valeurs que la non-linéarité de la couche de sortie peut produire (et sont à peu près normales N(0,1) dans le cas linéaire),

- ne sont pas trop proches des valeurs limites de la non-linéarité de la couche de sortie: pour la classification, une valeur optimale est près d’un des deux points d’inflexion (i.e., les points de courbure (dérivée seconde) maximale, environ -0.6 et 0.6 pour tanh, 0.2 et 0.8 pour la sigmoide).

- Il vaut mieux utiliser le critère d’entropie croisée (ou la vraisemblance conditionnelle) pour la classification probabiliste, ou bien le critère de marge “hinge” (comme pour le perceptron et les SVMs, mais en pénalisant les écarts à la surface de décision au-delà d’une marge). Dans le cas multiclasse, ça donne

où est la partie positive et est la sortie (sans non-linéarité) pour la classe .

Codage des sorties désirées et des entrées discrètes

En entrée comme en sortie, on va généralement représenter les variables discrètes par des groupes d’unités (un groupe de k unités par variable discrète pouvant prendre k valeurs). L’exception pratique est le cas d’une variable binaire, qu’on encode généralement avec une seule unité. Dans le cas des sorties on va associer à chaque groupe une distribution discrète (binomiale pour un seul bit, multinomiale pour une variable discrète générale).

Algorithme d’optimisation

Quand le nombre d’exemples est grand (plusieurs milliers) la descente de gradient stochastique est souvent le meilleur choix (surtout pour la classification), en terme de vitesse et en terme de contrôle de la capacité (il est plus difficile d’avoir de l’overfitting avec la descente de gradient stochastique. En effet, la descente de gradient stochastique ne tombe pas facilement dans les minima très pointus (qui ne généralisent pas bien, car une légére perturbation des données déplaçant la surface d’erreur donnerait une très mauvaise performance), à cause du bruit induit par le pas de gradient et le gradient “bruité”. Ce gradient bruité aide aussi à sortir de certains minima locaux, pour la même raison.

Quand la descente de gradient stochastique est utilisée, il est IMPÉRATIF que les exemples soient bien mélangés: par exemple si on a beaucoup d’exemples consécutifs de la même classe, la convergence sera très lente. Il suffit de permuter aléatoirement les exemples une fois pour toute, pour éliminer toute dépendence entre les exemples successifs. Avec certaines architectures qui captent des dépendences temporelles (signaux, musique, parole, séries chrono, vidéo) on a pas le choix de présenter des séquences dont les éléments sont fortement dépendents, mais on peut mélanger les séquences (l’ensemble d’apprentissage est une suite de séquences).

En principe le pas de gradient devrait être graduellement réduit pendant l’apprentissage pour garantir la convergence asymptotique. Pour certains problèmes (surtout de classification) cela ne semble pas nécessaire, et peut même nuire. Une cédule de descente raisonnable est par exemple comme discuté ici. Si on pouvait le calculer, le pas de gradient optimal serait , i.e., l’inverse de la valeur propre la plus grande de la matrice Hessienne, et le pas de gradient maximal (avant divergence) est deux fois plus grand. Le Cun propose une méthode pour estimer efficacemenet (voir son tutorial sur le sujet), mais cette technique ne semble pas courramment utilisée.

Quand le nombre d’exemples (et donc de paramètres) est plus petit, et surtout pour la régression, les techniques du second degré (surtout la technique des gradients conjugués) permettent une convergence beaucoup plus rapide. Ces techniques sont batch (modification des paramètres après calcul de l’erreur et gradient sur tous les exemples). Ces techniques sont généralement plus facile à ajuster que la descente de gradient stochastique (moins d’hyper-paramètres ou moins nécessaire de les ajuster par rapport à une valeur par défaut), mais la généralisation est parfois moins bonne à cause de la facilité de tomber dans des minima pointus.

Jusqu’à quelques dizaines de milliers d’exemples, la descente de gradient conjugués reste une des meilleures techniques pour l’optimisation des réseaux de neurones. Au-delà il vaut généralement mieux s’en tenir au gradient stochastique ou à sa version minibatch.

Initialisation des paramètres

On ne peut initialiser tous les poids à zéro sans quoi tous les neurones cachés sont condamnés à toujours faire la même chose (qu’on peut voir par un simple argument de symétrie). On veut aussi éviter la saturation des neurones (sortie près des limites de la non-linéarité, donc gradient presque 0), mais ne pas être trop près initialement d’une fonction linéaire. Quand les paramètres sont tous près de 0, le réseau multicouche calcule une transformation affine (linéaire), donc sa capacité effective par sortie est égale au nombre d’entrées plus 1. En se basant sur ces considérations, le point idéal d’opération du neurone devrait être proche du point d’inflexion de la non-linéarité (entre la partie linéaire près de l’origine et la partie saturation). Par ailleurs, on aimerait que la variance moyenne des valeurs des unités cachées soit préservée quand on propage les “activations” de l’entrée vers la sortie, et de la même manière on aimerait que la variance des gradients le soit aussi quand on les propage de la sortie vers l’entrée. Pour atteindre cet objectif, on peut argumenter que les poids initiaux devraient être initialisés de manière uniforme dans un intervalle , où est le fan-in, i.e., le nombre d’entrées du neurone, le nombre de neurones de la couche précédente, et est le fan-out, i.e., le nombre de neurones de la couche visée. Cela suppose que les entrées sont approximativement uniformes dans l’intervalle (-1,1) (et remarquez comme les sorties des unités cachées tanh sont aussi dans le même intervalle).

Contrôle de la saturation

Un des problèmes fréquents pendant l’apprentissage est la saturation des neurones, souvent dûe à une mauvaise normalisation des entrées ou des sorties désirées ou une mauvaise initialisation des poids, ou bien à l’utilisation de la sigmoide plutôt qu’une fonction de non-linéarité symétrique comme la tanh. On peut contrôler cela on observant la distribution des sorties des neurones (en particulier, la moyenne des valeurs absolues de la somme pondérée est un bon indice). Quand les neurones saturent fréquemment, l’apprentissage est bloqué sur un plateau de la fonction de coût dû à de très petits gradients sur certains paramètres (donc un très mauvais conditionnement du Hessien).

Contrôle de la capacité effective

La théorie du structural risk minimization de Vapnik nous dit qu’il existe une capacité optimale autour de laquelle l’erreur de généralisation augmente (c’est un minimum global et unique). Les techniques de contrôle de la capacité effective visent donc à chercher ce minimum (evidemment de façon approximative).

- early stopping: il s’agit d’une des techniques les plus populaires et les plus efficaces, mais elle ne marche pas bien quand le nombre d’exemples disponibles est très petit. L’idée est très simple: on utilise un ensemble d’exemples de validation non-utilisés pour l’apprentissage par descente de gradient pour estimer l’erreur de généralisation au fur et à mesure que l’apprentissage itératif progresse (normalement, après chaque époque on mesure l’erreur sur l’ensemble de validation). On garde les paramètres correspondant au minimum de cette courbe d’erreur de généralisation estimée (et on peut s’arrêter quand cette erreur commence à remonter sérieusement ou qu’un minimum a été atteint depuis un certain nombre d’époques). Cela a l’avantage de répondre à une des questions difficile de l’optimisation, qui est: quand arrêter? De plus on remarque qu’on a ainsi choisi pour pas cher (en temps de calcul) un hyper-paramètre important (le nombre d’itérations d’entraînement) qui touche à la fois l’optimisation et la généralisation.

- contrôle du nombre d’unités cachées: ce nombre influence directement la capacité. Dans ce cas il faut malheureusement faire plusieurs d’expériences d’apprentissage, à moins d’utiliser un algorithme d’apprentissage constructif (qui rajoute des ressources au fur et à mesure), voir l’algorithme de cascade-correlation (Fahlman, 1990). On peut utiliser un ensemble de validation ou la validation croisée pour estimer l’erreur de généralisation. Il faut faire attention au fait que cet estimé est bruité (d’autant plus qu’il y a peu d’exemples de validation). Quand on a plusieurs couches cachées, choisir le même nombre d’unités par couche semble bien fonctionner. Le prix à payer pour un nombre d’unités trop grand est surtout que les calculs sont plus longs, car le nombre accru de paramètre est généralement compensé par le early stopping. Par contre quand le nombre d’unités cachées est trop petit, l’effet sur l’erreur de généralisation et sur l’erreur d’apprentissage peut être beaucoup plus grand. On va généralement choisir la taille des réseau de façon empirique, en gardant ces considérations à l’esprit pour éviter d’avoir à essayer trop de valeurs de la taille.

- weight decay: c’est une méthode de régularisation (pour contrôler la capacité, empêcher l’overfitting) dont le but est de pénaliser les poids forts. En effet, on peut montrer que la capacité est bornée par la magnitude des poids du réseau de neurones. On rajoute la pénalité

à la fonction de coût. On l’appelle régularisation L2 car on minimise la norme 2 des paramètres. Certains l’appliquent uniquement aux poids et non pas au biais.

Comme dans le cas précédent, il faut faire plusieurs expériences d’apprentissage et choisir le facteur de pénalité (un hyper-paramètre) qui minimise l’erreur de généralisation estimée. On l’estime avec un ensemble de validation ou bien par validation croisée.

Une forme de régularisation de plus en plus utilisée comme alternative à la régularisation L2 est la régularisation L1, qui a comme avantage que les petits paramètres seront carrément amenés à 0, donnant lieu à un vecteur de paramètres qui est sparse. On va donc minimiser la somme des valeurs absolues des paramètres.

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   next  | previous  | Test 0.1 documentation »

Convolutional Neural Networks (LeNet)

Note

This section assumes the reader has already read through Classifying MNIST digits using Logistic Regression and Introduction to Multi-Layer Perceptrons (Feedforward Neural Networks). Additionally, it uses the following new Theano functions and concepts: TODO

Motivation

Convolutional Neural Networks (CNN) are variants of MLPs which are inspired from biology. From Hubel and Wiesel’s early work on the cat’s visual cortex [Hubel], we know there exists a complex arrangement of cells within the visual cortex. These cells are sensitive to small sub-regions of the input space, called a receptive field, and are tiled in such a way as to cover the entire visual field. These filters are local in input space and are thus better suited to exploit the strong local correlation present in natural images.

Additionally, two basic cell types have been identified: simple cells (S) and complex cells (C). Simple cells (S) respond maximally to specific edge-like stimulus patterns within their receptive field. Complex cells (C) have larger receptive fields and are locally invariant to the exact position of the stimulus.

The visual cortex being the most powerful “vision” system in existence, it seems natural to emulate its behavior. Many such neurally inspired models can be found in the litterature. To name a few: the NeoCognitron [Fukushima], HMAX [Serre] and LeNet-5 [LeCun]. LeNet-5 will be the topic of this tutorial.

The Model

Sparse Connectivity

CNNs exploit local correlation by enforcing a local connectivity pattern between neurons of adjacent layers. The input hidden units in the i-th layer are connected to a local subset of units in the (i-1)-th layer, which are spatially contiguous. We can illustrate this graphically as follows:

TODO FIGURE

This architecture thus confines the learnt filters to be local. Stacking many such layers leads to filters which become increasingly “global” (i.e spanning a larger region of pixel space) and abstract (as in any MLP).

Shared Weights

In CNNs, each sparse filter is additionally replicated across the entire visual field. These “replicated” units form a feature map, which share the same parametrization, i.e. the same weight vector and the same bias. Replicating units in this way allows for features to be detected regardless of their position in the visual field. Each feature map can thus be modeled as the convolution of a single filter with the input image.

Note

Recall the following definition of convolution for a 1D signal. . This can be extended to 2D as follows: .

In terms of notation, each feature map is denoted as , where is the index of the feature map (Important: not to be confused with the notation , referring to the k-th hidden layer). Each feature map has a weight matrix and bias . Note that the matrix is different in nature than the weight matrix of traditional MLPs. For MLPs, is a matrix whose entries refer to the weight connecting unit to . For CNNs, is a matrix of weights from the K-th feature map to the input pixel with coordinates (i,j). A CNN layer is thus fully determined by the set of all such matrices, and the bias vector .

The k-th feature map is determined as follows:

Going from MLP to convolutional MLP

Putting it All Together

Note

TODO introduce API for sparse filters

References

[Hubel]

Hubel, D. and Wiesel, T. (1968). Receptive fields and functional architecture of monkey striate cortex. Journal of Physiology (London), 195, 215–243.

[Fukushima]

Fukushima, K. (1980). Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position. Biological Cybernetics, 36, 193–202.

[Serre]

Serre, T., Wolf, L., Bileschi, S., and Riesenhuber, M. (2007). Robust object recog- nition with cortex-like mechanisms. IEEE Trans. Pattern Anal. Mach. Intell., 29(3), 411–426. Member-Poggio, Tomaso.

[LeCun]

LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. (1998d). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278–2324.

Footnotes

[1]

For clarity, we use the word “unit” or “neuron” to refer to the artificial neuron and “cell” to refer to the biological neuron.

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   previous  | Test 0.1 documentation »

Stacked Denoising Autoencoders (SdA)

Note

This section assumes the reader has already read through Classifying MNIST digits using Logistic Regression and Introduction to Multi-Layer Perceptrons (Feedforward Neural Networks). Additionally it uses the following Theano functions and concepts : TODO

The Stacked Denoising Autoencoder (SdA) is an extension of the stacked autoencoder [Bengio07] and it was introduced in [Vincent08]. We will start the tutorial with a short discussion on Autoencoders and then move on to how classical autoencoders are extended to denoising autoencoders (dA). Throughout the following subchapters we will stick as close as possible to the original paper ( [Vincent08] ).

Autoencoders

See section 4.6 of [Bengio09] for an overview of auto-encoders. An autoencoder takes an input and first maps it (with an encoder) to a hidden representation through a deterministic mapping:

The latent representation , or code is then mapped back (with a decoder) into a reconstruction of same shape as through a similar transformation, namely:

where ‘ does not indicate transpose, and should be seen as a prediction of . The weight matrix of the reverse mapping may be optionally constrained by , which is an instance of tied weights. The parameters of this model (namely , , and, if one doesn’t use tied weights, also ) are optimized such that the average reconstruction error is minimized. The reconstruction error can be measured using the traditional squared error , or if the input is interpreted as either bit vectors or vectors of bit probabilities by the reconstruction cross-entropy defined as :

The hope is that the code is a distributed representation that captures the coordinates along the main factors of variation in the data: because is viewed as a lossy compression of , it cannot be a good compression (with small loss) for all , so learning drives it to be one that is a good compression in particular for training examples, and hopefully for others as well (and that is the sense in which an auto-encoder generalizes), but not for arbitrary inputs.

If there is one linear hidden layer (the code) and the mean squared error criterion is used to train the network, then the hidden units learn to project the input in the span of the first principal components of the data. If the hidden layer is non-linear, the auto-encoder behaves differently from PCA, with the ability to capture multi-modal aspects of the input distribution.

We want to implement an auto-encoder using Theano, in the form of a class, that could be afterwards used in constructing a stacked autoencoder. The first step is to create shared variables for the parameters of the autoencoder ( , and , since we are using tied weights in this tutorial ):

class AutoEncoder(object):

def __init__(self, n_visible= 784, n_hidden= 500, input = None):

# initial values for weights and biases

# note : W' was written as `W_prime` and b' as `b_prime`

# W is initialized with `initial_W` which is uniformely sampled

# from -6./sqrt(n_visible+n_hidden) and 6./sqrt(n_hidden+n_visible)

# the output of uniform if converted using asarray to dtype

# theano.config.floatX so that the code is runable on GPU

initial_W = numpy.asarray( numpy.random.uniform( \

low = -numpy.sqrt(6./(n_visible+n_hidden)), \

high = numpy.sqrt(6./(n_visible+n_hidden)), \

size = (n_visible, n_hidden)), dtype = theano.config.floatX)

initial_b       = numpy.zeros(n_hidden)

initial_b_prime= numpy.zeros(n_visible)

# theano shared variables for weights and biases

self.W       = theano.shared(value = initial_W,       name = "W")

self.b       = theano.shared(value = initial_b,       name = "b")

# tied weights, therefore W_prime is W transpose

self.W_prime = W.T

self.b_prime = theano.shared(value = initial_b_prime, name = "b'")

Note that we pass the input to the autoencoder as a parameter. This is such that later we can concatenate layers of autoencoders to form a deep network: the symbolic output (the above, self.y in the code below) of the k-th layer will be the symbolic input of the (k+1)-th.

Now we can compute the latent representation and the reconstructed signal :

self.y    = T.nnet.sigmoid(T.dot(self.x, self.W      ) + self.b)

self.z    = T.nnet.sigmoid(T.dot(self.y, self.W_prime) + self.b_prime)

# note : we sum over the size of a datapoint; if we are using minibatches,

#        L will  be a vector, with one entry per example in minibatch

self.L    = - T.sum( self.x*T.log(self.z) + (1-self.x)*T.log(1-self.z), axis=1 )

# note : L is now a vector, where each element is the cross-entropy cost

#        of the reconstruction of the corresponding example of the

#        minibatch. We need to compute the average of all these to get

#        the cost of the minibatch

self.cost = T.mean(self.L)

Training the autoencoder consist now in updating the parameters W, b and b_prime by stochastic gradient descent such that the cost is minimized.

train = theano.function( [x], cost, updates = { \

self.W       : self.W       - T.grad(self.cost, self.W      )*learning_rate,

self.b       : self.b       - T.grad(self.cost, self.b      )*learning_rate,

self.b_prime : self.b_prime - T.grad(self.cost, self.b_prime)*learning_rate})

Note that for the stacked denoising autoencoder we will not use the train function as defined here, this is here just to illustrate how the autoencoder would work. In [Bengio07] autoencoders are used to build deep networks.

One serious potential issue with auto-encoders is that if there is no other constraint besides minimizing the reconstruction error, then an auto-encoder with inputs and an encoding of dimension at least could potentially just learn the identity function, for which many encodings would be useless (e.g., just copying the input). Surprisingly, experiments reported in [Bengio07] suggest that in practice, when trained with stochastic gradient descent, non-linear auto-encoders with more hidden units than inputs (called overcomplete) yield useful representations (in the sense of classification error measured on a network taking this representation in input). A simple explanation is based on the observation that stochastic gradient descent with early stopping is similar to an L2 regularization of the parameters. To achieve perfect reconstruction of continuous inputs, a one-hidden layer auto-encoder with non-linear hidden units needs very small weights in the first layer (to bring the non-linearity of the hidden units in their linear regime) and very large weights in the second layer. With binary inputs, very large weights are also needed to completely minimize the reconstruction error. Since the implicit or explicit regularization makes it difficult to reach large-weight solutions, the optimization algorithm finds encodings which only work well for examples similar to those in the training set, which is what we want. It means that the representation is exploiting statistical regularities present in the training set, rather than learning to replicate the identity function.

There are different ways that an auto-encoder with more hidden units than inputs could be prevented from learning the identity, and still capture something useful about the input in its hidden representation. One is the addition of sparsity (forcing many of the hidden units to be zero or near-zero), and it has been exploited very successfully by many. Another is to add randomness in the transformation from input to reconstruction. This is exploited in Restricted Boltzmann Machines (discussed later in this tutorial), as well as in Denoising Auto-Encoders, discussed below.

Denoising Autoencoders (dA)

The idea behind denoising autoencoders is simple. In order to enforce the hidden layer to discover more roboust features we train the autoencoder to reconstruct the input from a corrupted version of it. The denoising auto-encoder is a stochastic version of the auto-encoder. Intuitively, a denoising auto-encoder does two things: try to encode the input (preserve the information about the input), and try to undo the effect of a corruption process stochastically applied to the input of the auto-encoder. The latter can only be done by capturing the statistical dependencies between the inputs. The denoising auto-encoder can be understood from different perspectives ( the manifold learning perspective, stochastic operator perspective, bottom-up – information theoretic perspective, top-down – generative model perspective ), all of which are explained in [Vincent08]. See also section 7.2 of [Bengio09] for an overview of auto-encoders.

In [Vincent08], the stochastic corruption process consists in randomly setting some of the inputs (as many as half of them) to zero. Hence the denoising auto-encoder is trying to predict the missing values from the non-missing values, for randomly selected subsets of missing patterns. Note how being able to predict any subset of variables from the rest is a sufficient condition for completely capturing the joint distribution between a set of variables.

To convert the autoencoder class into a denoising autoencoder one, all we need to do is to add a stochastic corruption step operating on the input. The input can be corrupted in many ways, in this tutorial we will stick to the original corruption mechanism of randomly masking entries of the input by making them zero. The code below does just that :

from theano.tensor.shared_randomstreals import RandomStreams

theano_rng = RandomStreams()

corrupted_x = x * theano.rng.binomial(x.shape, 1, 0.9)

The final denoising autoencoder class becomes :

class dA(object):

def __init__(self, n_visible= 784, n_hidden= 500, input= None):

self.n_visible = n_visible

self.n_hidden  = n_hidden

# create a Theano random generator that gives symbolic random values

theano_rng = RandomStreams()

# create a numpy random generator

numpy_rng = numpy.random.RandomState()

# initial values for weights and biases

# note : W' was written as `W_prime` and b' as `b_prime`

initial_W = numpy.asarray( numpy.random.uniform( \

low = -numpy.sqrt(6./(n_visible+n_hidden)), \

high = numpy.sqrt(6./(n_visible+n_hidden)), \

size = (n_visible, n_hidden)), dtype = theano.config.floatX)

initial_b       = numpy.zeros(n_hidden)

initial_b_prime= numpy.zeros(n_visible)

# theano shared variables for weights and biases

self.W       = theano.shared(value = initial_W,       name = "W")

self.b       = theano.shared(value = initial_b,       name = "b")

# tied weights, therefore W_prime is W transpose

self.W_prime = self.W.T

self.b_prime = theano.shared(value = initial_b_prime, name = "b'")

# if no input is given, generate a variable representing the input

if input == None :

# we use a matrix because we expect a minibatch of several examples,

# each example being a row

self.x = T.dmatrix(name = 'input')

else:

self.x = input

self.tilde_x  = theano_rng.binomial( self.x.shape,  1,  0.9) * self.x

self.y   = T.nnet.sigmoid(T.dot(self.tilde_x, self.W      ) + self.b)

self.z        = T.nnet.sigmoid(T.dot(self.y, self.W_prime) + self.b_prime)

self.L = - T.sum( self.x*T.log(self.z) + (1-self.x)*T.log(1-self.z), axis=1 )

# note : L is now a vector, where each element is the cross-entropy cost

#        of the reconstruction of the corresponding example of the

#        minibatch. We need to compute the average of all these to get

#        the cost of the minibatch

self.cost = T.mean(self.L)

# note : y is computed from the corrupted `tilde_x`. Later on,

#        we will need the hidden layer obtained from the uncorrupted

#        input when for example we will pass this as input to the layer

#        above

self.hidden_values = T.nnet.sigmoid( T.dot(self.x, self.W) + self.b)

Stacked Autoencoders

The denoising autoencoders can now be stacked to form a deep network by feeding the latent representation (output code) of the denoising auto-encoder found on the layer below as input to the current layer. The unsupervised pre-training of such an architecture is done one layer at a time. Each layer is trained as a denoising auto-encoder by minimizing the reconstruction of its input (which is the output code of the previous layer). Once the first layers are trained, we can train the -th layer because we can now compute the code or latent representation from the layer below. Once all layers are pre-trained, the network goes through a second stage of training called fine-tuning. Here we consider supervised fine-tuning where we want to minimize prediction error on a supervised task. For this we first add a logistic regression layer on top of the network (more precisely on the output code of the output layer). We then train the entire network as we would train a multilayer perceptron. At this point, we only consider the encoding parts of each auto-encoder. This stage is supervised, since now we use the target during training (see the Introduction to Multi-Layer Perceptrons (Feedforward Neural Networks) for details on the multilayer perceptron).

This can be easily implemented in Theano, using the class defined before for a denoising autoencode :

class StackedAutoencoder():

def __init__(self, input, n_ins, hidden_layers_sizes, n_outs):

""" This class is made to support a variable number of layers.

:param input: symbolic variable describing the input of the SdA

:param n_ins: dimension of the input to the sdA

:param n_layers_sizes: intermidiate layers size, must contain

at least one value

:param n_outs: dimension of the output of the network

"""

Next step, we create an denoising autoencoder for each layer and link them together:

self.layers =[]

if len(hidden_layers_sizes) < 1 :

raiseException (' You must have at least one hidden layer ')

# add first layer:

layer = dA(n_ins, hidden_layers_sizes[0], input = input)

self.layers += [layer]

# add all intermidiate layers

for i in xrange( 1, len(hidden_layers_sizes) ):

# input size is that of the previous layer

# input is the output of the last layer inserted in our list

# of layers `self.layers`

layer = dA( hidden_layers_sizes[i-1],             \

hidden_layers_sizes[i],               \

input = self.layers[-1].hidden_values )

self.layers += [layer]

self.n_layers = len(self.layers)

Note that during the second stage of training (fine-tuning) we need to use the weights of the autoencoders to define a multilayer perceptron. This is already given by the above lines of code, in the sense that the hidden_values of the last denoising autoencoder already computes what should be the input of the logistic regression layer that sits at the top of the MLP. All we need now is to add the logistic layer. We will use the LogisticRegression class introduced in Logistic Regression.

# add a logistic layer on top

self.logLayer = LogisticRegression(\

input = self.layers[-1].hidden_values,\

n_in = hidden_layers_sizes[-1], n_out = n_outs)

The negative log likelihood of this MLP (formed from reusing the weights of the denoising autoencoders) is given by the negative log likelihood function of the logistic layer :

def negative_log_likelihood(self, y):

"""Return the mean of the negative log-likelihood of the prediction

of this model under a given target distribution. In our case this

is given by the logistic layer.

:param y: corresponds to a vector that gives for each example the

:correct label

"""

return self.logLayer.negative_log_likelihood(y)

def errors(self, y):

"""Return a float representing the number of errors in the minibatch

over the total number of examples of the minibatch

"""

return self.logLayer.errors(y)

Putting it all together

The few lines of code below constructs the stacked denoising autoencoder :

# construct the logistic regression class

classifier = SdA( input=x, n_ins=28*28, \

hidden_layers_sizes = [500, 500, 500], n_outs=10)

There are two stages in training this network, a layer wise pre-training and fine-tuning afterwads.

For the pre-training stage, we will loop over all the layers of the network. For each layer we will compile a theano function that implements a SGD step towards optimizing the weights for reducing the reconstruction cost of that layer. This function will be apllied to the training set for a fixed number of epochs given by pretraining_epochs

## Pre-train layer-wise

for i in xrange(classifier.n_layers):

# compute gradients of layer parameters

gW       = T.grad(classifier.layers[i].cost, classifier.layers[i].W)

gb       = T.grad(classifier.layers[i].cost, classifier.layers[i].b)

gb_prime = T.grad(classifier.layers[i].cost, \

classifier.layers[i].b_prime)

# updated value of parameters after each step

new_W       = classifier.layers[i].W      - gW      * pretraining_lr

new_b       = classifier.layers[i].b      - gb      * pretraining_lr

new_b_prime = classifier.layers[i].b_prime- gb_prime* pretraining_lr

cost = classifier.layers[i].cost

layer_update = theano.function([index], [cost], \

updates = {

classifier.layers[i].W       : new_W \

, classifier.layers[i].b       : new_b \

, classifier.layers[i].b_prime : new_b_prime },

givens = {

x :train_set_x[index*batch_size:(index+1)*batch_size]})

# go through pretraining epochs

for epoch in xrange(pretraining_epochs):

# go through the training set

for batch_index in xrange(n_train_batches):

c = layer_update(batch_index)

print 'Pre-training layer %i, epoch %d'%(i,epoch)

The fine-tuning loop is very similar with the one in Introduction to Multi-Layer Perceptrons (Feedforward Neural Networks), we just have a slighly more complex training function. The reason is that now we need to update all parameters of the network in one call of the training function ( this includes the weight and baiases of the denoising autoencoders plus those of the logistic regression layer). To create this function, we will loop over the layers and create an update list containing pairs of the form (parameter before the SGD step, paramter after the SGD step). The new value of a paramter can be easily computed by calling T.grad to compute the corresponding gradient, multiply it with the learning rate and subtract the result from the old value of the parameter:

# Fine-tune the entire model

# the cost we minimize during training is the negative log likelihood of

# the model

cost = classifier.negative_log_likelihood(y)

# compute the gradient of cost with respect to theta and add them to the

# updates list

updates = []

for i in xrange(classifier.n_layers):

g_W   = T.grad(cost, classifier.layers[i].W)

g_b   = T.grad(cost, classifier.layers[i].b)

new_W = classifier.layers[i].W - learning_rate * g_W

new_b = classifier.layers[i].b - learning_rate * g_b

updates += [ (classifier.layers[i].W, new_W) \

, (classifier.layers[i].b, new_b) ]

# add the gradients of the logistic layer

g_log_W   = T.grad(cost, classifier.logLayer.W)

g_log_b   = T.grad(cost, classifier.logLayer.b)

new_log_W = classifier.logLayer.W - learning_rate * g_log_W

new_log_b = classifier.logLayer.b - learning_rate * g_log_b

updates += [ (classifier.logLayer.W, new_log_W) \

, (classifier.logLayer.b, new_log_b) ]

# compiling a theano function `train_model` that returns the cost, but

# in the same time updates the parameter of the model based on the rules

# defined in `updates`

train_model = theano.function([index], cost, updates=updates,

givens = {

x: train_set_x[index*batch_size:(index+1)*batch_size],

y: train_set_y[index*batch_size:(index+1)*batch_size]})

Now we pass this training_model (together with a validate_model and a test_model generated as in the other tutorials) to the early stopping loop and we are done.

Running the Code

TODO

References

[Bengio07]

Bengio Y., Lamblin P., Popovici D. and Larochelle H. Greedy Layer-Wise Training of Deep Networks. Advances in Neural Information Processing Systems 19 (NIPS‘06), pages 153-160, MIT Press 2007.

[Vincent08]

Vincent, P., Larochelle H., Bengio Y. and Manzagol P.A. Extracting and Composing Robust Features with Denoising Autoencoders. Proceedings of the Twenty-fifth International Confrence on Machine Learning (ICML‘08), pages 1096 - 1103, ACM, 2008.

[Bengio09]

Bengio Y. Learning deep architectures for AI, Foundations and Trends in Machine Learning 1(2) pages 1-127.

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   Test 0.1 documentation »

Index

D | E | L | M | N | P | R | S | T | Z

D

Dataset notation

Datasets

E

Early-Stopping

L

L1 and L2 regularization

List of Symbols and acronyms

Logistic Regression

M

Math Convetions

MNIST Dataset

N

Negative Log--Likelihood Loss

Notation

P

Python Namespaces

R

Regularization

S

Stochastic Gradient Descent

T

Testing

Z

Zero-One Loss

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   Test 0.1 documentation »

Introduction to Deep Learning Algorithms

See the following article for a recent survey of deep learning:

Yoshua Bengio, Learning Deep Architectures for AI, Foundations and Trends in Machine Learning, 2(1), 2009 [http://www.iro.umontreal.ca/%7Elisa/publications2/index.php/publications/show/239]

Depth

The computations involved in producing an output from an input can be represented by a flow graph: a flow graph is a graph representing a computation, in which each node represents an elementary computation and a value (the result of the computation, applied to the values at the children of that node). Consider the set of computations allowed in each node and possible graph structures and this defines a family of functions. Input nodes have no children. Output nodes have no parents.

The flow graph for the expression could be represented by a graph with two input nodes and , one node for the division taking and as input (i.e. as children), one node for the square (taking only as input), one node for the addition (whose value would be and taking as input the nodes and , and finally one output node computing the sinus, and with a single input coming from the addition node.

A particular property of such flow graphs is depth: the length of the longest path from an input to an output.

Traditional feedforward neural networks can be considered to have depth equal to the number of layers (i.e. the number of hidden layers plus 1, for the output layer). Support Vector Machines (SVMs) have depth 2 (one for the kernel outputs or for the feature space, and one for the linear combination producing the output).

Motivations for Deep Architectures

The main motivations for studying learning algorithms for deep architectures are the following:

- Insufficient depth can hurt

- The brain has a deep architecture

- Cognitive processes seem deep

Insufficient depth can hurt

Depth 2 is enough in many cases (e.g. logical gates, formal [threshold] neurons, sigmoid-neurons, Radial Basis Function [RBF] units like in SVMs) to represent any function with a given target accuracy. But this may come with a price: that the required number of nodes in the graph (i.e. computations, and also number of parameters, when we try to learn the function) may grow very large. Theoretical results showed that there exist function families for which in fact the required number of nodes may grow exponentially with the input size. This has been shown for logical gates, formal neurons, and RBF units. In the latter case Hastad has shown families of functions which can be efficiently (compactly) represented with nodes (for inputs) when depth is , but for which an exponential number () of nodes is needed if depth is restricted to .

One can see a deep architecture as a kind of factorization. Most randomly chosen functions can’t be represented efficiently, whether with a deep or a shallow architecture. But many that can be represented efficiently with a deep architecture cannot be represented efficiently with a shallow one (see the polynomials example in the Bengio survey paper [http://www.iro.umontreal.ca/%7Elisa/publications2/index.php/publications/show/239]). The existence of a compact and deep representation indicates that some kind of structure exists in the underlying function to be represented. If there was no structure whatsoever, it would not be possible to generalize well.

The brain has a deep architecture

For example, the visual cortex is well-studied and shows a sequence of areas each of which contains a representation of the input, and signals flow from one to the next (there are also skip connections and at some level parallel paths, so the picture is more complex). Each level of this feature hierarchy represents the input at a different level of abstraction, with more abstract features further up in the hierarchy, defined in terms of the lower-level ones.

Note that representations in the brain are in between dense distributed and purely local: they are sparse: about 1% of neurons are active simultaneously in the brain. Given the huge number of neurons, this is still a very efficient (exponentially efficient) representation.

Cognitive processes seem deep

- Humans organize their ideas and concepts hierarchically.

- Humans first learn simpler concepts and then compose them to represent more abstract ones.

- Engineers break-up solutions into multiple levels of abstraction and processing

It would be nice to learn / discover these concepts (knowledge engineering failed because of poor introspection?). Introspection of linguistically expressible concepts also suggests a sparse representation: only a small fraction of all possible words/concepts are applicable to a particular input (say a visual scene).

Breakthrough in Learning Deep Architectures

Before 2006, attempts at training deep architectures failed: training a deep supervised feedforward neural network tends to yield worse results (both in training and in test error) then shallow ones (with 1 or 2 hidden layers).

Three papers changed that in 2006, spearheaded by Hinton’s revolutionary work on Deep Belief Networks (DBNs):

- Hinton, G. E., Osindero, S. and Teh, Y., A fast learning algorithm for deep belief nets [http://www.cs.toronto.edu/%7Ehinton/absps/fastnc.pdf] Neural Computation 18:1527-1554, 2006

- Yoshua Bengio, Pascal Lamblin, Dan Popovici and Hugo Larochelle, Greedy Layer-Wise Training of Deep Networks [http://www.iro.umontreal.ca/%7Elisa/publications2/index.php/publications/show/190], in J. Platt et al. (Eds), Advances in Neural Information Processing Systems 19 (NIPS 2006), pp. 153-160, MIT Press, 2007

- Marc’Aurelio Ranzato, Christopher Poultney, Sumit Chopra and Yann LeCun Efficient Learning of Sparse Representations with an Energy-Based Model [http://yann.lecun.com/exdb/publis/pdf/ranzato-06.pdf], in J. Platt et al. (Eds), Advances in Neural Information Processing Systems (NIPS 2006), MIT Press, 2007

The following key principles are found in all three papers:

- Unsupervised learning of representations is used to (pre-)train each layer.

- Unsupervised training of one layer at a time, on top of the previously trained ones. The representation learned at each level is the input for the next layer.

- Use supervised training to fine-tune all the layers (in addition to one or more additional layers that are dedicated to producing predictions).

The DBNs use RBMs for unsupervised learning of representation at each layer. The Bengio et al paper explores and compares RBMs and auto-encoders (neural network that predicts its input, through a bottleneck internal layer of representation). The Ranzato et al paper uses sparse auto-encoder (which is similar to sparse coding) in the context of a convolutional architecture. Auto-encoders and convolutional architectures will be covered later in the course.

Since 2006, a plethora of other papers on the subject of deep learning has been published, some of them exploiting other principles to guide training of intermediate representations. See Learning Deep Architectures for AI [http://www.iro.umontreal.ca/%7Elisa/publications2/index.php/publications/show/239] for a survey.

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.

index   Test 0.1 documentation »

Introduction to Gradient-Based Learning

Consider a cost function which maps a parameter vector to a scalar which we would like to minimize. In machine learning the cost function is typically the average or the expectation of a loss functional:

(this is called the training loss) or

(this is called the generalization loss), where in supervised learning we have and is a prediction of , indexed by the parameters .

The Gradient

The gradient of the function of a single scalar is formally defined as follows:

Hence it is the variation induced by a change , when is very small.

When is a vector, the gradient is a vector with one element per , where we consider the other parameters fixed, we only make the change and we measure the resulting . When is small then becomes .

Gradient Descent

We want to find a that minimizes . If we are able to solve

then we can find the minima (and maxima and saddle points), but in general we are not able to find the solutions of this equation, so we use numerical optimization methods. Most of these are based on the idea of local descent: iteratively modify so as to decrease , until we cannot anymore, i.e., we have arrived at a local minimum (maybe global if we are lucky).

The simplest of all these gradient-based optimization techniques is gradient descent. There are many variants of gradient descent, so we define here ordinary gradient descent:

where represents our parameters at iteration and is a scalar that is called the learning rate, which can either be chosen fixed, adaptive or according to a fixed decreasing schedule.

Stochastic Gradient Descent

We exploit the fact that is an average, generally over i.i.d. (independently and identically distributed) examples, to make updates to much more often, in the extreme (and most common) case after each example:

where is the next example from the training set, or the next example sampled from the training distribution, in the online setting (where we have not a fixed-size training set but instead access to a stream of examples from the data generating process). Stochastic Gradient Descent (SGD) is a more general principle in which the update direction is a random variable whose expectations is the true gradient of interest. The convergence conditions of SGD are similar to those for gradient descent, in spite of the added randomness.

SGD can be much faster than ordinary (also called batch) gradient descent, because it makes updates much more often. This is especially true for large datasets, or in the online setting. In fact, in machine learning tasks, one only uses ordinary gradient descent instead of SGD when the function to minimize cannot be decomposed as above (as a mean).

Minibatch Stochastic Gradient Descent

This is a minor variation on SGD in which we obtain the update direction by taking the average over a small batch (minibatch) of examples (e.g. 10, 20 or 100). The main advantage is that instead of doing Vector x Matrix products one can often do a Matrix x Matrix product where the first matrix has rows, and the latter can be implemented more efficiently (sometimes 2 to 10 times faster, depending on the sizes of the matrices).

Minibatch SGD has the advantage that it works with a slightly less noisy estimate of the gradient (more so as increases). However, as the minibatch size increases, the number of updates done per computation done decreases (eventually it becomes very inefficient, like batch gradient descent). There is an optimal trade-off (in terms of computational efficiency) that may vary depending on the data distribution and the particulars of the class of function considered, as well as how computations are implemented (e.g. parallelism can make a difference).

Momentum

Another variation that is similar in spirit to minibatch SGD is the use of so-called momentum: the idea is to compute on-the-fly (online) a moving average of the past gradients, and use this moving average instead of the current example’s gradient, in the update equation. The moving average is typically an exponentially decaying moving average, i.e.,

where is a hyper-parameter that controls the how much weight is given in this average to older vs most recent gradients.

Choosing the Learning Rate Schedule

If the step size is too large – larger than twice the largest eigenvalue of the second derivative matrix (Hessian) of –, then gradient steps will go upward instead of downward. If the step size is too small, then convergence is slower.

The most common choices of learning rate schedule () are the following:

- constant schedule, : this is the most common choice. It in theory gives an exponentially larger weight to recent examples, and is particularly appropriate in a non-stationary environment, where the distribution may change. It is very robust but error will stop improving after a while, where a smaller learning rate could yield a more precise solution (approaching the minimum a bit more).

- schedule: .

This schedule is guaranteed to reach asymptotic convergence (as ) because it satisfies the following requirements:

and this is true for any but must be small enough (to avoid divergence, where the error rises instead of decreasing

A disadvantage is that an additional hyper-parameter is introduced. Another is that in spite of its guarantees, a poor choice of can yield very slow convergence.

Flow Graphs, Chain Rule and Backpropagation: Efficient Computation of the Gradient

Consider a function (in our case it is ) of several arguments, and we wish to compute it as well as its derivative (gradient) w.r.t. some of its arguments. We will decompose the computation of the function in terms of elementary computations for which partial derivatives are easy to compute, forming a flow graph (as already discussed there). A flow graph is an acyclic graph where each node represents the result of a computation that is performed using the values associated with connected nodes of the graph. It has input nodes (with no predecessors) and output nodes (with no successors).

Each node of the flow graph is associated with a symbolic expression that defines how its value is computed in terms of the values of its children (the nodes from which it takes its input). We will focus on flow graphs for the purpose of efficiently computing gradients, so we will keep track of gradients with respect to a special output node (denoted here to refer to a loss to be differentiated with respect to parameters, in our case). We will associate with each node

- the node value

- the symbolic expression that specifies how to compute the node value in terms of the value of its predecessors (children)

- the partial derivative of with respect to the node value

- the symbolic expressions that specify to how compute the partial derivative of each node value with respect to the values of its predecessors.

Let be the output scalar node of the flow graph, and consider an arbitrary node whose parents (those nodes taking the value computed at as input). In addition to the value (abuse of notation) associated with node , we will also associate with each node a partial derivative .

The chain rule for derivatives specifies how the partial derivative for a node can be obtained recursively from the partial derivatives for its parents :

Note that which starts the recursion at the root node of the graph (node that in general it is a graph, not a tree, because there may be multiple paths from a given node to the root – output – node). Note also that each is an expression (and a corresponding value, when the inputs are given) that is associated with an arc of the graph (and each arc is associated with one such partial derivative).

Note how the gradient computations involved in this recipe go exactly in the opposite direction compared to those required to compute . In fact we say that gradients are back-propagated, following the arcs backwards. The instantiation of this procedure for computing gradients in the case of feedforward multi-layer neural networks is called the **back-propagation algorithm**.

In the example already shown earlier, and there are two paths from to .

This recipe gives us the following nice guarantee. If the computation of is expressed with computations expressed through nodes (and each node computation requires a constant computation time) and arcs, then computing all the partial derivatives requires (at most) computations, using the above recursion (in general, with a bounded in-degree, this is also ). Furthermore, this is a lower bound, i.e., it is not possible to compute the gradients faster (up to an additive and multiplicative constant).

Note that there are many ways in which to compute these gradients, and whereas the above algorithm is the fastest one, it is easy to write down an apparently simple recursion that would instead be exponentially slower, e.g., in . In general can be written as a sum over all paths in the graph from to of the products of the partial derivatives along each path.

An illustration of this is with a graph with the following structure:

where there are such pairs of node, ending with and with input nodes and . The number of paths from to is . Note by mental construction how the number of paths doubles as we increase by 1.

© Copyright 2014, Andres Romero. Created using Sphinx 1.2.3.