Introduction - Definition

• A Neural Network is a set of interconnected input and output units in which each connection has an associated weight

• During the learning phase, the weights are adjusted in such a way that the network is able to correctly predict the class of new examples

Biological Neuron

Artificial Neuron

Neural Networks - Example

Neural Networks - Notation

• A neural network is a directed graph \(R = \langle V, E \rangle\) with vertices \(V=\{1, 2, \dots, n\}\) and edges \(E=\{\langle i,j \rangle | 1 \leq i,j \leq n \}\), with the following restrictions
  • \(V\) is partitioned in a set of input nodes, \(V_i\), hidden nodes \(V_H\), and output nodes \(V_O\).
  • Edges are also partitioned in layers \(\{1, \dots, k\}\)
  • All input nodes are in layer \(1\) and all nodes in the output are in layer \(k\).
  • All hidden nodes are in layers \(2\) to \(k-1\) and are called hidden layers
  • Every edge \(\langle i, j \rangle\) has to have a node \(i\) in layer \(h-1\) and a node \(j\) in layer \(h\)
  • An edge \(\langle i,j \rangle\) has a numeric label with value \(w_{ij}\)
  • A node \(i\) has as label a function \(f_i\).

Neural Networks - General Characteristics

• Disadvantages
  • Large training times
  • Use many parameters,topology or structure
  • Difficult to interpret
• Advantages
  • Highly noise tolerant
  • Can extract rules from them

Neural Networks - How They Are Used

• Prediction
• Regression
• Adapt for the classification task

Neural Networks - As a Black Box

• Maps an array of \(n\)-dimensional real inputs to an \(m\)-dimensional real array of outputs \(F: R^n \rightarrow R^m\)

Neural Networks - The Perceptron

• Input:
  • A vector of real numbers
• Output:
  • \(1\) if the value is larger than a threshold
  • \(-1\) if it is not \[o(x_1, \dots, x_n) = \begin{cases} 1 & \text{ if } w_0 + w_1x_1 + \dots + w_nx_n > 0 \\ -1 & \text{otherwise} \end{cases}\]
• where \(w_i\) is a real value (or weight)

Neural Networks - The Perceptron

• Use a planar decision surface
• Ouputs \(1\) if the instances are on one side of the plane and \(-1\) if the instances are on the other side of the plane

Neural Networks - The Perceptron

\[o(x_1, \dots, x_n) = \begin{cases} 1 & \text{ if } \sum\limits_{i=0}^{n}w_ix_i > 0 \\ -1 & \text{otherwise} \end{cases}\]

Neural Networks - The Perceptron

• Functions that can be represented by the Perceptron
  • Any boolean function can be represented by a network of interconnected units based on these primitives
  • AND, OR, NAND (\(\neg\)AND), NOR (\(\neg\)OR)
• Cannot be represented:
  • XOR

Neural Networks - The Perceptron - Training Rule

• Learning:
  • Consists on finding the adecuate weights vector to produce the desired \(\pm 1\) for each of the input instances
• Starts with random numbers
• Applies the perceptron to each input example
  • Modifies the weights for each classification error
• Repeats the previous process until all examples are correctly classified

Neural Networks - The Perceptron - Training Rule

• \(w_i \rightarrow w_i + \Delta w_i\), where \(\Delta w_i = \eta(t-o)x_i\)
• \(t = c(x)\), the output value of an example
• \(o =\) the output of the perceptron
• \(\eta =\) a small constant known as the learning rate (i.e. \(0.1\))
• It is used for linearly separable examples

Neural Networks - Gradient Descent

• Considering a linear unit
  • \(o=w_0 + w_1x_1 + \dots + w_nx_n\)
• We are required to learn the weights \(w_i\) that minimize the square of the error
  • \(E[\vec{w}] \equiv \frac{1}{2}\sum\limits_{d \in D}(t_d - o_d)^2\)
• Where
  • \(D\) is the training examples set
  • \(t_d\) is the correct classification of the example
  • \(o_d\) is the output of the linear unit

Neural Networks - The Perceptron - Training Rule

• We are required to reduce the error

Neural Networks - The Perceptron - Gradient Descent

• \(\bigtriangledown E[\vec{w}] \equiv [\frac{\delta E}{\delta w_0}, \frac{\delta E}{\delta w_1}, \dots, \frac{\delta E}{\delta w_n}]\)
• Training rule
  • \(w_i \leftarrow w_i + \Delta w_i\)
• Where
  • \(\Delta w_i = -\eta \frac{\delta E}{\delta w_i}\)

Neural Networks - The Perceptron - Gradient Descent

• The lowest error is obtained by altering each component \(w_i\) of \(\vec{w}\) in proportion to \(\frac{\delta E}{\delta w_i}\) \[\frac{\delta E}{\delta w_i}=\frac{\delta}{\delta w_i}\frac{1}{2} \sum\limits_{d}(t_d - o_d)^2\] \[=\frac{1}{2} \sum\limits_{d}\frac{\delta}{\delta w_i}(t_d - o_d)^2\] \[=\frac{1}{2}\sum\limits_{d}2(t_d - o_d)\frac{\delta}{\delta w_i}(t_d - o_d)\] \[=\sum\limits_{d}(t_d - o_d)\frac{\delta}{\delta w_i}(t_d - \vec{w} \cdot \vec{x}_d)\] \[\frac{\delta E}{\delta w_i}=\sum\limits_{d \in D}(t_d - o_d)(x_{id})\]
• \(x_{id}\) denotes the component
• \(x_i\) for example \(d\)

Neural Networks - The Perceptron - Gradient Descent

Neural Networks - The Perceptron - Summary

• We use the perceptron when
  • Examples are linearly separable
  • We use a small value for the learning rate \(\eta\)
• Gradient descent
  • Guarantees convergence to a hypothesis with a minimum quadratic error
  • Requires a small value for the learning rate \(\eta\)
  • Works well even if our data contains noise
  • Works well even if the training examples are not totally separable by \(H\), an approximation

Neural Networks - Back Propagation

• There were limitants with one layer networks
• It was discovered that multi-layer networks had good results
  • Rumelhart, Hinton, & Williams 1986
  • McClelland & Rumelhart 1988
• Backpropagation (of errors) appears
  • Also known as the generalized delta rule

Neural Networks - Back Propagation

• Training in three steps
  • Feedforward of the input pattern
  • Computation and retro-propagation of the associated error
  • Weights adjustment
• Application in only one step
  • Computations of the feedforward phase

Neural Networks - Back Propagation

• Capabilities
  • Multilayer Network with one or more hidden layers
  • Can learn continuous mappings (with certain efficiency)
  • More than a hidden layer may be good for several applications but one has shown to be enough

Neural Networks - Back Propagation

• Architecture (with a single hidden units layer)
  • Input layer
  • Hidden layer
  • Output layer
  • Introduces biases

Neural Networks - Back Propagation

• Activation function
  • Continuous
  • Differentiable
  • Monotonically non-decreasing
  • Derivative easy to compute (for efficiency of the computation)
  • The most used is the sigmoid function
    • Binary sigmoid, range (0, -1)
    • Bipolar sigmoid, range (-1, 1)

Neural Networks - Back Propagation

Neural Networks - Back Propagation

• \(\sigma(X)\) is the sigmoid function
• The sigmoid function computes the output as \(\sigma(w \cdot x)\)
  • where \[\sigma(x) = \frac{1}{1+e^{-x}}\]
• Property \[\frac{\delta \sigma(x)}{\delta x}=\sigma(x) \cdot (1-\sigma(x))\]
• We can derive the gradient descent
  • One sigmoid unit
  • Multilayer network of sigmoid units \(\rightarrow\) Backpropagation

Neural Networks - Back Propagation - Algorithm

Neural Networks - Back Propagation - Characteristics

• Reduces the square of the sum of the errors of its outputs
• May fall in a local minima
• In practice, it is a good algorithm
• How can we avoid a local minima?
  • Train several networks with the same information
    • Initialize weights with different values in each network
    • Choose the network with the best behavior

Neural Networks - Back Propagation - Stop Criterion

• When should we stop the training phase?
• Until reducing the error as most as possible?
  • No, we loose the generalization power
  • Overfitting the training examples
  • Specialize the network to the training examples and the weights are adjusted to the particularities of the training examples that doesn’t apply in general

Neural Networks - Back Propagation - Stop Criterion

Neural Networks - Back Propagation - Stop Criterion

• How can we avoid the problem?
  • Use weights that decay (reduce weights at each iteration)
  • Use a validation examples set (only for the testing phase). The algorithm verifies the error according to these examples
  • \(k\)-fold cross validation

Neural Networks - Back Propagation - Stop Criterion

Example

• https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/

Deep Learning

• Deep Learning comes from Neural Networks
  • Antecedents many years ago
  • The Neocognitron by Kunihiko Fukushima, 1980
  • Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position

Deep Learning

• Deep Learning provides great models for Machine Learning
  • Speech recognition
  • Computer vision
  • Text processing

Deep Learning

• What is deep learning?
  • A set of algorithms that use neural networks as an architecture (Quoc V. Le, December 2015)
  • Successful due to
    • Availability of more computational resources
    • Parallelism (GPUs, clusters)
    • Massive ammounts of data
  • Usually more than 2 layers

Deep Learning

• Deep learning is a better option when the problem doesn’t show linear characteristics
  • A shallow network requires about 10x more connections in order to obtain the same performance of a deep network

Deep Learning

• Intuitively
  • In deep learning, functions computed by lower layered neurons are as subroutines
  • These subroutines are used many times to compute the final output
  • Subroutine used several times vs used only once
  • Then, a shallow network requires more connections (i.e. do not re-use subroutines)

Deep Learning

Deep Learning

• Reasons for success
  • Many parameters makes possible for NN to approximate very nonlinear functions (i.e. complex problem with a lot of data)
  • NN are very flexible
    • Change the architecture to adapt to specific problems or domains (i.e. convolutional NN and recurrent NN)
  • For many people, deep is associated to: there is no need for human invented features
  • Deep learning then means “a set of algorithms that use neural networks as an architecture, and learn the features automatically” (Quoc V. Le, 2015)

Deep Learning - Autoencoders

• An enhancement to neural networks around the year 2000
  • Pretrain deep networks
  • Random initialization of weights didn’t work well
  • Pretrain each layer using an unsupervised learning algorithm
    • Better initial weights
• Deep Belief Networks are an unsupervised algorithm of this type (to pretrain a deep network), based on
  • Restricted Boltzmann Machines
  • Deep Autoencoders, based on autoencoders

Deep Learning - Autoencoders

• Example: Data compression via autoencoders
  • Program to send data from phone to cloud
    • Optimize network usage
    • Optimize every bit sent to cloud
  • Data to be sent
    • Data points, 2 dimensions

Deep Learning - Autoencoders

• For these data points we can see that y is about the double of x
• We can send only the 1st data coordinate over the network and approximate the second one
  • Multiplying by 2 the 1st coordinate
  • Our compression is lossy (we loose some information)
  • Saves about 50% in network traffic (our goal)
  • This works via visualization

Deep Learning - Autoencoders

• Can we do this in a systematic way for high dimensional data?
  • Give a set of multidimensional data points \(X = \{x^{(1)}, x^{(2)}, \dots, x^{(m)}\}\)
  • Is there a general way to map these data points to another set of points \(Z = \{z^{(1)}, z^{(2)}, \dots, z^{(m)}\}\)
  • Such that \(z\)’s have lower dimensionality than \(x\)’s and \(z\)’s can reconstruct \(x\)’s

Deep Learning - Autoencoders

• The proces to send data to the cloud has 3 steps
  • Encoding: map \(x^{(i)}\) to compressed data \(z^{(i)}\)
  • Sending: \(z^{(i)}\) to the cloud
  • Decoding: map from \(z^{(i)}\) to \(\tilde x^{(i)}\)

Deep Learning - Autoencoders

• We can make \(z\) and \(\tilde x\) be functions of their inputs:
  • \(z^{(i)} = W_1x^{(i)} + b_1\)
  • \(\tilde x^{(i)} = W_2 z{(i)} + b_2\)

Deep Learning - Autoencoders

• We can use gradient descent in order to find the values of \(W_i\), the weights
  • Our goal: have \(\tilde x^{(i)}\) approximate \(x^{(i)}\)
  • Use this objective function to minimize using gradient descent:

\(J(W_1, b_1, W_2, b_2) = \sum\limits_{i=1}^{m} (\tilde x^{(i)} - x^{(i)})^2\)
\(= \sum\limits_{i=1}^{m} (W_2z^{(i)} + b_2 - x^{(i)})^2\)
\(= \sum\limits_{i=1}^{m} (W_2(W_1 x^{(i)} + b_1) + b_2 - x^{(i)})^2\)

• This architecture is known as a linear autoencoder

Deep Learning - Autoencoders

• Uses a linear activation function (a linear autoencoder)
  • Good for data in a linear surface
  • If data lies on a nonlinear surface we can use a non-linear autoencoder:

• For highly non linear data we can use an autoencoder with more hidden layers
  • A deep autoencoder
• Autoencoders are unsupervised methods
  • Do not require labeled data

Deep Learning - Autoencoders as an initialization method

• Applications of autoencoders
  • Data compression
  • Visualization
  • Pretrain neural networks
• Why pretraining?
  • Magnitudes of gradients in lower and higher layers differ
  • Deep networks have many parameters (as weights), could overfit the data and not generalize well
• Pretrained achieved in these steps:
  • Pretraining step
    • Train a sequence of shallow autoencoders
    • We do this greedily, one layer at a time
    • We use unsupervised data
  • Fine tune step 1
    • Train the last layer with supervised data
  • Fine tune step 2
    • Use backpropagation to fine-tune the entire network
    • Uses supervised data

• For this two layer network we pretrain
  • Hidden layer 1 of weights \(W_1\)
  • Hidden layer 2 of weights \(W_2\)
  • We use two autoencoders
    • We use autoencoder 1 to train weights \(W_1\) (we discard weights \(W'_1\))
    • We use autoencoder 2 to train weights \(W_2\), we take as input the output of the previous autoencoder (weights \(W'_2\) are then discarded)

Deep Learning - Convolutional Neural Networks

• Convolutional Neural Networks (CNN) perform very well in the task of object recognition
• Architecture of NN
  • In other NN neurons in first hidden layer are connected to all input neurons
  • This is a problem when \(X\) is high dimensional
  • Each neuron has too many connections (i.e. if \(X\) is an image with \(100 \times 100\) pixels, that’s \(10,000\) parameters)
  • We can make this architecture more efficient
  • Force each each neuron to have a small number of connections to the input
  • We can design connection patterns
    • In images we want neurons to be connected only to adjacent pixels from the input image
• NN architecture in general:

• CNN architecture:

• We extend this idea of local connectivity in many layers
  • We get a deep locally connected network
  • We can train with gradient descent, modify backpropagation to deal with local connectivity
    • Forward pass: assume empty connections have weights of zeros
    • Backward pass: do not compute the gradient of the empty connections
• These networks are known as
  • Local networks
  • Locally connected networks
  • Local receptive field networks

Deep Learning - Convolutional Neural Networks - Translational Invariance

• Translational invariance can be achieved with CNN
• We saw how we reduce the number of connections with CNN
• We can reduce the number of connections even more
  • Weight sharing
  • Some parameters of the model are constrained to be equal to each other
  • i.e. \(w_1 == w_4 == w_7\), \(w_2 == w_5 == w_8\), \(w_3 == w_6 == w_9\)

• Representation is now more compact
  • We only store parameters \(w_1, w_2, w_3\)
• Weight sharing is related to an important operation in signal processing
  • Convolution
  • We can apply a filter (or a set of weights) to many positions in the input signals
  • We have another layer known as the max-pooling layer
    • The max-pooling layer computes the max of a selected set of output neurons from the convolutional layer and uses these as inputs to higher layers

• The output of the max-pooling neurons are invariant to shifts in the inputs
  • Consider two examples (as if they were 1D images)
  • \(x_1 = [0, 1, 0, 0, 0, 0, 0, \dots]\)
  • \(x_2 = [0, 0, 0, 1, 0, 0, 0, \dots]\)

• Now the outputs are invariant to translation, translational invariance
• Translational invariance systems are good for working with
  • Images
  • Sounds
• These type of networks is known as Convolutional Neural Networks (also known as convnets)
  • The max pooling layer is also known as the subsampling layer (reduces the size of the input data)
  • The max operation can be replaced by the average operation
  • Recent convolutional neural networks have another type of layer, Local Contrast Normalization (LCN)
    • Allows brightness invariance
    • Good for image recognition
  • We can still use the backpropagation algorithm to train these networks

Convolutional Neural Networks with Multi-channel Inputs

• Images come with multiple channels (i.e. RGB)
• Modify convolutional architecture to work like this
• Add a filter that looks at the multiple channels
  • Weights are not usually shared between channels

Convolution

• Ref: https://leonardoaraujosantos.gitbooks.io/artificial-inteligence/content/convolution.html

Stride

Padding

https://towardsdatascience.com/applied-deep-learning-part-4-convolutional-neural-networks-584bc134c1e2

Pooling

https://www.quora.com/What-is-max-pooling-in-convolutional-neural-networks

CNN Layers

• Layers of a CNN
  • Input
  • Convolutional
  • Max-pooling or (Avg-pooling)
  • Dropout
  • Softmax
  • Dense
• Activation Functions of CNN
  • Sigmoid
  • Relu
• Error Function
  • Cross entropy error
• Concepts
  • Convolution
  • Padding vs No-padding
  • Stride
  • Pooling

Popular Convolutional Neural Networks

• LeNet (Yann LeCun, 1990)

Popular Convolutional Neural Networks

• AlexNet

Popular Convolutional Neural Networks

• GoogleNet

Popular Convolutional Neural Networks

• VGGNet

Popular Convolutional Neural Networks

• ResNet

Applications of CNNs

• Pedestrian detection

Applications of CNNs

• Objects detection/classification

Recurrent Neural Networks

• We can use recurrent NN for sequence prediction
  • Time Series Data

Software

• Caffe
• Tensorflow
• Keras
• Yolo

References

• Deep Learning Explained
  • edx.org (course)
• A Tutorial on Deep Learning, Quoc V. Le, Google Brain, Google Inc. October 19-20 2015
  • Part 1: Nonlinear Classifiers and The Backpropagation Algorithm
  • Part 2: Autoencoders, Convolutional Neural Networks and Recurrent Neural Networks
• Deep Learning, Ian Goodfellow, Yoshua Bengio, Aaron Courville, Book in preparation for MIT Press, 2016
  • http://www.deeplearningbook.org
  • https://github.com/HFTrader/DeepLearningBook
  • Introduction to the Math of Neural Networks, Jeff Heaton, Heaton Research Inc., 2012 (digital book)
• A Step by Step Backpropagation example
  • http://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/