Deep Learning and Reinforcement Learning

Module 1
Introduction to Deep Learning

Prepared By:
Dr. Rajesh Nayak
Associate Professor
Dept. of Artificial Intelligence and Data Science
 Contents
1. Introduction to Deep Learning

– 1.1 Introduction

– 1.2 Shallow Learning

– 1.3 Deep Learning

– 1.4 Why to use Deep Learning

– 1.5 How Deep Learning works

– 1.6 Deep Learning Challenges

8. Optimization for Training Deep Models

– 8.1 How Learning Differs from Pure Optimization

– 8.2 Challenges in Neural Network Optimization

2
1 Introduction to Deep Learning
1.1 Introduction
• Machine Learning (ML) systems, with shallow or deep
architectures, have ability to learn and improve with
experience.
• The process of ML begins with the raw data which is used for
extracting useful information that helps in decision-making.
• The primary aim is to allow a machine to learn useful
information just like humans do.

3
1.1 Introduction
• At abstract level, machine learning can be carried out using
following approaches:
– Supervised learning
• It adapts a system such that for a given input data it produces a target output. The
learning data is made up of tuples (attributes, label) where “attributes” represent
the input data and “label” represents the target output.
• The goal here is to adapt the system so that for a new input the system can
predict the target output. Supervised learning can use both continuous and
discrete types of input data.
– Unsupervised learning
• It involves data that comprises of input vectors without any target output. There
are different objectives in unsupervised learning, such as clustering, density
estimation, etc.
• The goal of clustering is to discover groups of similar data items on the basis of
measured or perceived similarities between the data items. The purpose of
density estimation is to determine the distribution of the data within the input
space. In visualization, the data is projected down from a high-dimensional space
to two or three dimensions to view the similar data items.

4
1.1 Introduction
• At abstract level, machine learning can be carried out using
following approaches:
– Semi-supervised learning
• It first uses unlabeled data to learn a feature representation of the input data and
then uses the learned feature representation to solve the supervised task. The
training dataset can be divided into two parts: the data samples with
corresponding labels and the data samples where the labels are not known.
• Semi-supervised learning can involve not providing with an explicit form of error
at each time but only a generalized reinforcement is received giving indication of
how the system should change its behavior, and this is sometimes referred to as
reinforcement learning.

1.2 Shallow Learning

• Shallow architectures are well understood and perform good
on many common machine learning problems, and they are
still used in a vast majority of today’s machine learning
applications.
5
1.3 Deep Learning
• Deep Learning (DL) refers to the architectures which contain
multiple hidden layers (deep networks) to learn different
features with multiple levels of abstraction.
• DL algorithms seek to exploit the unknown structure in the
input distribution in order to discover good representations,
often at multiple levels, with higher level learned features
defined in terms of lower level features.
• Conventional machine learning techniques are restricted in the
way they process the natural data in its raw form. For decades,
constructing a pattern recognition or machine learning system
required considerable domain expertise and careful hand
engineering to come up with a feature extractor that
transformed the raw data (such as pixel values of an image)
into suitable internal representation or feature vector from
which the learning system, such as a classifier, could detect or
classify patterns in the input. 7
1.3 Deep Learning
• DL allows inputting the raw data (pixels in case of image
data) to the learning algorithm without first extracting
features or defining a feature vector.
• DL algorithms can learn the right set of features, and it does
this in a much better way than extracting these features
using hand-coding. Instead of handcrafting a set of rules and
algorithms to extract features from raw data, DL involves
learning these features automatically during the training
process.
• In DL, a problem is realized in terms of hierarchy of concepts,
with each concept built on the top of the others. The lower
layers of the model encode some basic representation of the
problem, whereas higher level layers build upon these lower
layers to form more complex concepts.
8
1.3 Deep Learning
• Given an image, the pixel intensity values are fed as inputs to
the DL system. A number of hidden layers then extract
features from the input image. These hidden layers are built
upon each other in a hierarchal fashion.
• At first, the lower level layers of the network detect only
edge-like regions. These edge regions are then used to define
corners (where edges intersect) and contours (outlines of
objects).
• The layers in the higher level combine corners and contours
to lead to more abstract “object parts” in the next layer. The
key aspect of DL is that these layers of features are not
handcrafted and designed by human engineers; rather, they
are learnt from data gradually using a general-purpose
learning procedure.
9
• Finally, the output layer
classifies the image and obtains
the output class label—the
output obtained at the output
layer is directly influenced by
every other node available in
the network. This process can
be viewed as hierarchical
learning as each layer in the
network uses the output of
previous layers as “building
blocks” to construct
increasingly more complex
concepts at the higher layers.
• Figure 1.1 compares traditional
ML approach based on
handcrafted features to DL
approach based on hierarchical
representation learning. 10
• Although DL has been around since 1980s, it was relatively
unpopular for several years as the computational infrastructure
(both hardware and software) was not adequate and the available
datasets were quite small.
• With the decline in the popularity of the conventional neural
networks, it was only recently that deep networks made a big
reappearance by achieving spectacular results in speech
recognition and computer vision tasks. Some of the aspects that
helped in the evolution of deep networks are listed below:
– Improved computational resources for processing massive amounts of data
and training much larger models.
– Automatic feature extraction.
• The learning mechanisms used by deep learning models are in no
way comparable to the human brain, but can be described as a
mathematical framework for learning representations from data.
11
12
13
1.4 Why to use Deep Learning:
• Deep learning has surpassed those conventional algorithms in
accuracy as the features are learnt from the data using a general-
purpose learning procedure instead of being designed by human
engineers.
• Deep networks have demonstrated dramatic improvements in
computer vision and have dramatically improved machine
translation, and have taken off as an effective AI technique that
has the ability to recognize spoken words nearly as good as a
person can.
• It has achieved not only the excellent accuracy in machine
learning modeling, but it has also demonstrated outstanding
generalization power that has even attracted scientists from other
academic disciplines.
• Deep learning grew to prominence in 2007, with promising results
on perceptual problems such as hearing and seeing problems that
humans are very good at, but have long been subtle for the
machines. 15
1.4 Why to use Deep Learning:
• It has enabled the computer scientists to harness the vast
computational power and use large volumes of data—audio,
video, to teach computers how to do things that seem natural and
intuitive for humans, such as spotting objects in the photos,
recognizing words or sentences, and translating a document into
other language.
• It has made it possible for machines to output the transcript from
an audio clip–speech recognition, to identify whether a mail is
spam or not, likelihood of whether a customer will repay his loan
and so on; as long as there is enough data to train machines, the
possibilities are endless.
• It has achieved state-of-the-art results on many applications, such
as natural language parsing, language modeling, image and
character recognition, playing the challenging game of Go, pixels-
to-controls video game playing, and in other applications.
16
1.4 Why to use Deep Learning:
• In particular, deep learning has made good impact in historically
difficult areas of machine learning:
– Near-human-level image classification;
– Near-human-level speech recognition;
– Near-human-level handwriting transcription;
– Improved self-driving cars;
– Digital assistants such as Google Now, Microsoft Cortana, Apple’s Siri, and
Amazon Alexa;
– Improved ad targeting, as used by Google, Baidu, and Bing;
– Improved search results on the web;
– Ability to answer natural language questions;
– Superhuman Go, Shogi, and Chess playing.
• The exceptional performance of deep models can be mainly
attributed to their flexibility in representing a rich set of highly
nonlinear functions as well as the devised methods for efficient
training of these powerful networks.
17
1.4 Why to use Deep Learning:
• Furthermore, employing various regularization techniques
ensured that deep models with huge numbers of free parameters
are statistically desirable in the sense that they will generalize well
to unseen data.
• The automatic and generic approach of feature learning in deep
models enables one to use them across different applications
(e.g., image classification, speech recognition, language modeling,
and information retrieval) with relatively little adjustments.
• Therefore, deep models seem to be domain-oblivious in the sense
that in order to use it across different applications, only a small
amount of domain specific customizations is required.
• Ideally, the domain-obliviousness of deep networks is
advantageous, as having access to a universal and generic model
reduces the hassles of adapting for new applications.

18
1.5 How Deep Learning Works:
• Deep networks map input to target via a sequence of layered
transformations, and that these layered transformations are
learned by exposure to the training examples.
• The transformations that a layer applies to its input are
determined by the layer’s weights, which are basically a bunch of
numbers. In other words, transformations implemented by a layer
are parameterized by its weights.
• In this context, learning can be defined as the process of finding
the values of the weights of all layers in the network in such a
manner that input examples can be correctly mapped to their
associated targets.
• A deep learning network contains thousands of parameters, and
finding the right values of these parameters is not an easy task,
particularly when the value of one parameter has an impact on
the value of another parameter.
19
1.5 How Deep Learning Works:
• In order to train a deep network one needs to find out how far the
calculated output of the network is from the desired value. This
measure is obtained by using a loss function, also called as
objective function.
• The objective function calculates the difference between the
predicted output obtained from the network and the true target
value for a specific example. This gives a measure of how well the
network has learnt a specific example.
• The objective of the training is to find the values for the weights
that minimize the chosen error function.
• The difference obtained is then used as a feedback signal to adjust
the weights of the network, in a way that loss score for the current
example is lowered. This adjustment is done by the optimizer—
backpropagation algorithm, the central algorithm in deep
learning.
20
1.5 How Deep Learning Works:
• Backpropagation algorithm involves assigning random values to
the weight vectors initially, so that the network just implements a
series of random transformations.
• Initially, the output obtained from the network can be far from
what it should be, and accordingly the loss score may be very high.
• With every example that is fed to the network, the weights are
adjusted in such a direction that makes the loss score to decrease.
• This process is repeated a number of times, until the weight
values that minimize the loss function are obtained.
• A network is said to have learned when the output values
obtained from the network are as close as they can be to the
target values.

21
1.6 Deep Learning Challenges:
• Training these architectures for general use was impractically
slow. With limited computational power, deep learning networks
were already overtaken by other approaches such as kernel
methods.
• With the significant growth in computational power (particularly in
GPUs and distributed computing) and access to large labeled
datasets paved the way for its return.
• Despite the remarkable advances in this area, training deep
models with a huge number of free parameters is an intricate and
ill-posed optimization problem.
• The strategies reported in the literature that deal with the
difficulties of training deep networks include developing better
optimizers, using well-designed initialization strategies, using
activation functions based on local competition and using skip
connections between layers with the aim to improve the flow of
information. 22
1.6 Deep Learning Challenges:
• However, deep network training still faces problems which are
caused by the stacking of several nonlinear transformations and
need to be addressed.
• Deep learning involves using large amounts of data to learn
progressively. While large amounts of data are available in many
applications, however, in some areas copious amount of data are
rarely available.
• More flexible models are required to achieve an enhanced
learning ability when only a limited amount of data is available.
• Deep learning networks are very good at solving one problem;
however, using deep networks to solve a very similar problem
requires retraining and reassessment.
• Although there are many advancements in this aspect, more work
is required in developing deep learning models which can perform
multitasks without the need of reworking on the whole
architecture. 23
Optimization for Training Deep Models

24
8.1 How Learning Differs from Pure Optimization:
• Optimization algorithms used for training of deep models differ from
traditional optimization algorithms in several ways.
• Machine learning usually acts indirectly. In most machine learning
scenarios, we care about some performance measure P, that is defined
with respect to the test set and may also be intractable.
• We therefore optimize P only indirectly. We reduce a different cost
function J(θ) in the hope that doing so will improve P.
• This is in contrast to pure optimization, where minimizing J is a goal in
and of itself. Optimization algorithms for training deep models also
typically include some specialization on the specific structure of machine
learning objective functions.

• Where L is the per-example loss function, f (x; θ) is the predicted output

when the input is x, ˆpdata is the empirical distribution. In the supervised
learning case, y is the target output. 25
8.1 How Learning Differs from Pure Optimization:
• Eq. 8.1 defines an objective function with respect to the training set. We
would usually prefer to minimize the corresponding objective function
where the expectation is taken across the data generating distribution
pdata rather than just over the finite training set:

26
8.1 How Learning Differs from Pure Optimization:
8.1.1 Empirical Risk Minimization

27
8.1.1 Empirical Risk Minimization
• The training process based on minimizing this average training error is
known as empirical risk minimization.
• In this setting, machine learning is still very similar to straightforward
optimization. Rather than optimizing the risk directly, we optimize the
empirical risk, and hope that the risk decreases significantly as well.
• A variety of theoretical results establish conditions under which the true
risk can be expected to decrease by various amounts.
• However, empirical risk minimization is prone to overfitting. Models with
high capacity can simply memorize the training set. In many cases,
empirical risk minimization is not really feasible.
• The most effective modern optimization algorithms are based on
gradient descent, but many useful loss functions, such as 0-1 loss, have
no useful derivatives.
• These problems mean that, in the context of deep learning, we rarely use
empirical risk minimization. Instead, we must use a slightly different
approach, in which the quantity that we actually optimize is even more
different from the quantity that we truly want to optimize 28
8.1.2 Surrogate Function and Early Stopping
• Sometimes, the loss function we actually care about (say classification
error) is not one that can be optimized efficiently. For example, exactly
minimizing expected 0-1 loss is typically intractable (exponential in the
input dimension), even for a linear classifier.
• In such situations, one typically optimizes a surrogate loss function
instead, which acts as a proxy but has advantages. For example, the
negative log-likelihood of the correct class is typically used as a surrogate
for the 0-1 loss.
• The negative log-likelihood allows the model to estimate the conditional
probability of the classes, given the input, and if the model can do that
well, then it can pick the classes that yield the least classification error in
expectation.
• In some cases, a surrogate loss function actually results in being able to
learn more. For example, the test set 0-1 loss often continues to
decrease for a long time after the training set 0-1 loss has reached zero,
when training using the log-likelihood surrogate.
29
8.1.2 Surrogate Function and Early Stopping
• This is because even when the expected 0-1 loss is zero, one can improve
the robustness of the classifier by further pushing the classes apart from
each other, obtaining a more confident and reliable classifier, thus
extracting more information from the training data than would have been
possible by simply minimizing the average 0-1 loss on the training set.
• A very important difference between optimization in general and
optimization as we use it for training algorithms is that training algorithms
do not usually halt at a local minimum.
• Instead, a machine learning algorithm usually minimizes a surrogate loss
function but halts when a convergence criterion based on early stopping is
satisfied.
• Typically the early stopping criterion is based on the true underlying loss
function, such as 0-1 loss measured on a validation set, and is designed to
cause the algorithm to halt whenever overfitting begins to occur. Training
often halts while the surrogate loss function still has large derivatives,
which is very different from the pure optimization setting, where an
optimization algorithm is considered to have converged when the gradient
becomes very small. 30
8.1.3 Batch and Minibatch Algorithms

31
8.1.3 Batch and Minibatch Algorithms
• Compare two hypothetical estimates of the gradient, one based on 100
examples and another based on 10,000 examples. The latter requires 100
times more computation than the former, but reduces the standard
error of the mean only by a factor of 10. Most optimization algorithms
converge much faster (in terms of total computation, not in terms of
number of updates) if they are allowed to rapidly compute approximate
estimates of the gradient rather than slowly computing the exact
gradient.
• Another consideration motivating statistical estimation of the gradient
from a small number of samples is redundancy in the training set. In the
worst case, all m samples in the training set could be identical copies of
each other.
• A sampling-based estimate of the gradient could compute the correct
gradient with a single sample, using m times less computation than the
naive approach. In practice, we are unlikely to truly encounter this worst-
case situation, but we may find large numbers of examples that all make
very similar contributions to the gradient.
32
8.1.3 Batch and Minibatch Algorithms
• Optimization algorithms that use the entire training set are called batch
or deterministic gradient methods, because they process all of the
training examples simultaneously in a large batch.
• Optimization algorithms that use only a single example at a time are
sometimes called stochastic or sometimes online methods.
• Most algorithms used for deep learning fall somewhere in between,
using more than one but less than all of the training examples. These
were traditionally called minibatch or minibatch stochastic methods and
it is now common to simply call them stochastic methods.

33
8.2 Challenges in Neural Network Optimization
• Local Minima: One of the most prominent features of a convex
optimization problem is that it can be reduced to the problem of finding
a local minimum. Any local minimum is guaranteed to be a global
minimum.
• Some convex functions have a flat region at the bottom rather than a
single global minimum point, but any point within such a flat region is an
acceptable solution.
• When optimizing a convex function, we know that we have reached a
good solution if we find a critical point of any kind.
• With non-convex functions, such as neural nets, it is possible to have
many local minima. Indeed, nearly any deep model is essentially
guaranteed to have an extremely large number of local minima.
• Neural networks and any models with multiple equivalently
parametrized latent variables all have multiple local minima because of
the model identifiability problem.
• A model is said to be identifiable if a sufficiently large training set can
rule out all but one setting of the model’s parameters. 34
• Local Minima:
• Models with latent variables are often not identifiable because we can
obtain equivalent models by exchanging latent variables with each other.
• For example, we could take a neural network and modify layer 1 by
swapping the incoming weight vector for unit i with the incoming weight
vector for unit j, then doing the same for the outgoing weight vectors. If
we have m layers with n units each, then there are n!m ways of arranging
the hidden units. This kind of non-identifiability is known as weight space
symmetry.
• These model identifiability issues mean that there can be an extremely
large or even uncountably infinite amount of local minima in a neural
network cost function. However, all of these local minima arising from
non-identifiability are equivalent to each other in cost function value. As
a result, these local minima are not a problematic form of non-convexity.
• Local minima can be problematic if they have high cost in comparison to
the global minimum. One can construct small neural networks, even
without hidden units, that have local minima with higher cost than the
global minimum. If local minima with high cost are common, this could
pose a serious problem for gradient-based optimization algorithms. 35
• Cliffs and Exploding Gradients:
• Neural networks with many layers often have extremely steep regions
resembling cliffs, as illustrated in Fig. 8.3. These result from the
multiplication of several large weights together.
• On the face of an extremely steep cliff structure, the gradient update
step can move the parameters extremely far, usually jumping off of the
cliff structure altogether.

Fig. 8.3
36
• Cliffs and Exploding Gradients:
• The cliff can be dangerous whether we approach it from above or from
below, but fortunately its most serious consequences can be avoided
using the gradient clipping heuristic.
• The basic idea is that the gradient does not specify the optimal step size,
but only the optimal direction within an infinitesimal region.
• When the traditional gradient descent algorithm proposes to make a
very large step, the gradient clipping heuristic intervenes to reduce the
step size to be small enough that it is less likely to go outside the region
where the gradient indicates the direction of approximately steepest
descent.
• Cliff structures are most common in the cost functions for recurrent
neural networks, because such models involve a multiplication of many
factors, with one factor for each time step. Long temporal sequences
thus incur an extreme amount of multiplication.

37
• Long-term Dependencies:
• Another difficulty that neural network optimization algorithms must
overcome arises when the computational graph becomes extremely
deep.
• Feedforward networks with many layers have such deep computational
graphs. So do recurrent networks, which construct very deep
computational graphs by repeatedly applying the same operation at each
time step of a long temporal sequence. Repeated application of the same
parameters gives rise to especially pronounced difficulties.

38
• Long-term Dependencies:
• Recurrent networks use the same matrix W at each time step, but
feedforward networks do not, so even very deep feedforward networks
can largely avoid the vanishing and exploding gradient problem.
• Inexact Gradients:
• Most optimization algorithms are primarily motivated by the case where
we have exact knowledge of the gradient. In practice, we usually only
have a noisy or even biased estimate of these quantities.
• Nearly every deep learning algorithm relies on sampling-based estimates
at least insofar as using a minibatch of training examples to compute the
gradient.
• In other cases, the objective function we want to minimize is actually
intractable. When the objective function is intractable, typically its
gradient is intractable as well. In such cases we can only approximate the
gradient.

39
• Poor Correspondence between Local and Global Structure:
• Many of the problems we have discussed so far correspond to properties of the
loss function at a single point—it can be difficult to make a single step if J(θ) is
poorly conditioned at the current point θ, or if θ lies on a cliff, or if θ is a saddle
point hiding the opportunity to make progress downhill from the gradient.
• Many existing research directions are aimed at finding good initial points for
problems that have difficult global structure, rather than developing algorithms
that use non-local moves.
• Gradient descent and essentially all learning algorithms that are effective for
training neural networks are based on making small, local moves.
• We may be able to compute some properties of the objective function, such as its
gradient, only approximately, with bias or variance in our estimate of the correct
direction.
• In these cases, local descent may or may not define a reasonably short path to a
valid solution, but we are not actually able to follow the local descent path.
• The objective function may have issues such as poor conditioning or
discontinuous gradients, causing the region where the gradient provides a good
model of the objective function to be very small.
• In these cases, local descent may or may not define a path to the solution, but the
path contains many steps, so following the path incurs a high computational cost.
40
• Poor Correspondence between Local and Global Structure:
• In some cases, local descent does not define a path to a solution at all. In other
cases, local moves can be too greedy and lead us along a path that moves
downhill but away from any solution, as in Fig. 8.4.
• Regardless of which of these problems are most significant, all of them might be
avoided if there exists a region of space connected reasonably directly to a
solution by a path that local descent can follow, and if we are able to initialize
learning within that well-behaved region.

41
• Theoretical Limits of Optimization:
• Several theoretical results show that there are limits on the performance
of any optimization algorithm we might design for neural networks.
Typically these results have little bearing on the use of neural networks
in practice.
• Some theoretical results apply only to the case where the units of a
neural network output discrete values. However, most neural network
units output smoothly increasing values that make optimization via local
search feasible. Some theoretical results show that there exist problem
classes that are intractable, but it can be difficult to tell whether a
particular problem falls into that class.
• Other results show that finding a solution for a network of a given size is
intractable, but in practice we can find a solution easily by using a larger
network for which many more parameter settings correspond to an
acceptable solution.
• In the context of NN training, we usually do not care about finding the
exact minimum of a function, but only in reducing its value sufficiently to
obtain good generalization error. Theoretical analysis of whether an
optimization algorithm can accomplish this goal is extremely difficult. 42
• Plateaus, Saddle Points and Other Flat Regions:
• For high-dimensional non-convex functions, local minima (and maxima)
are in fact rare compared to another kind of point with zero gradient: a
saddle point.
• Some points around a saddle point have greater cost than the saddle
point, while others have a lower cost.
• We can think of a saddle point as being a local minimum along one cross-
section of the cost function and a maximum along another cross-section.
• Many classes of random functions exhibit the following behavior: in low
dimensional spaces, local minima are common. In higher dimensional
spaces, local minima are rare and saddle points are more common.
• In optimization and deep learning, a plateau is a flat region of the loss
surface where the gradient (slope) is nearly zero. On a plateau, the loss
does not decrease much even after many training steps. Gradients are
very small, so the optimizer makes little to no progress. This slows down
convergence but is not a minimum or maximum.
• Symmetries in neural networks (e.g., swapping neurons with identical
roles) create flat directions. These regions don’t harm the final solution
but slow training. 43