Deep Learning

LM Computer Science & Data Science

2nd semester - 6 CFU
Nicolò Navarin & Alessandro Sperduti

A.A. 2021/22: Deep Learning 1

 Learning with gradient (Chp 4)

A.A. 2021/22: Deep Learning 2

 Numerical concerns for implementations of
deep learning algorithms
• Algorithms are often specified in terms of real numbers;
real numbers cannot be implemented in a finite computer

• Does the algorithm still work when implemented with a

finite number of bits?

• Do small changes in the input to a function cause large

changes to an output? (poor conditioning amplifies
rounding errors)

• Rounding errors, noise, measurement errors can cause

large changes

• more details in Chapter 4

A.A. 2021/22: Deep Learning 3

 Gradient-based optimization
We want to maximize/minimize an objective function
‣ Minimizing Cost/error/loss function

Consider a function ! = #(%)

!"
‣ The derivative #′(%) or gives the slope of #(%) at point
!#
x, or equivalently
$
# % + , − #(%)
# % = lim
%→' ,

# % + , ≈ # % + ,#′(%)
‣ Derivative tells us how to change % to make a small
improvement in !
‣ Critical/stationary points: # $ % = 0 No Information!
‣ Can be local maxima, minima or saddle points
A.A. 2021/22: Deep Learning 4
 Univariate calculus
• In this course, we will assume some familiarity with
calculus!

• In Moodle you can find a cheat sheet!

‣ Also, a link to some resources, useful to refresh your
memories!

‣ [Link] (bottom of the

page: calculus resources)

• Let’s refresh some basic concepts together..

• Chapter 5 of “Mathematics for Machine Learning”

A.A. 2021/22: Deep Learning 5

 Calculus Cheat Sheet Calculus Cheat Sheet

Derivatives Chain Rule Variants

Definition and Notation The chain rule applied to some specific functions.
f x h f x d n n 1 d
If y f x then the derivative is defined to be f x lim . 1. f x n f x f x 5. cos f x f x sin f x
h 0 h dx dx
d f x d
2. e f x ef x 6. tan f x f x sec 2 f x
If y f x then all of the following are If y f x all of the following are equivalent dx dx
d f x d
equivalent notations for the derivative. notations for derivative evaluated at x a . 3. ln f x 7. sec f ( x) f ( x ) sec f ( x ) tan f ( x)
df dy d df dy dx f x dx
f x y f x Df x f a y x a Df a d f x
dx dx dx dx x a dx x a d 8. tan 1
f x
4. sin f x f x cos f x dx 2
dx 1 f x
Interpretation of the Derivative
If y f x then, 2. f a is the instantaneous rate of Higher Order Derivatives
The Second Derivative is denoted as The nth Derivative is denoted as
1. m f a is the slope of the tangent change of f x at x a.
2 d2 f n dn f
line to y f x at x a and the 3. If f x is the position of an object at f x f x and is defined as f x and is defined as
dx 2 dx n
equation of the tangent line at x a is time x then f a is the velocity of
f x f x , i.e. the derivative of the f n
x f n 1
x , i.e. the derivative of
given by y f a f a x a . the object at x a.
first derivative, f x . the (n-1)st derivative, f
n 1
x .
Basic Properties and Formulas
If f x and g x are differentiable functions (the derivative exists), c and n are any real numbers, Implicit Differentiation
2x 9 y 3 2
d Find y if e x y sin y 11x . Remember y y x here, so products/quotients of x and y
1. cf cf x 5. c 0
dx will use the product/quotient rule and derivatives of y will use the chain rule. The “trick” is to
2. f g f x g x d n differentiate as normal and every time you differentiate a y you tack on a y (from the chain rule).
6. x n x n 1 – Power Rule After differentiating solve for y .
dx
3. f g f g f g – Product Rule d
7. f g x f g x g x e2 x 9y
2 9y 3x 2 y 2 2 x3 y y cos y y 11
f f g f g dx
4. – Quotient Rule This is the Chain Rule 11 2e 2 x 9 y 3 x 2 y 2
g g 2 2e2 x 9y
9 y e2 x 9y
3x 2 y 2 2 x3 y y cos y y 11 y
2 x3 y 9e 2 x 9 y cos y
2 x 3 y 9e 2 x 9y
cos y y 11 2e2 x 9y
3x 2 y 2
Common Derivatives
d d d
x 1 csc x csc x cot x ax a x ln a Increasing/Decreasing – Concave Up/Concave Down
dx dx dx Critical Points
d d 2 d x x x c is a critical point of f x provided either Concave Up/Concave Down
sin x cos x cot x csc x e e
dx dx dx 1. If f x 0 for all x in an interval I then
1. f c 0 or 2. f c doesn’t exist.
d d 1 d 1
cos x sin x sin 1 x ln x , x 0 f x is concave up on the interval I.
dx dx 1 x2 dx x
d d 1 Increasing/Decreasing 2. If f x 0 for all x in an interval I then
tan x sec 2 x d 1 1 ln x , x 0
cos x 1. If f x 0 for all x in an interval I then
dx dx 1 x2 dx x f x is concave down on the interval I.
d d 1 f x is increasing on the interval I.
sec x sec x tan x d 1 log a x , x 0
dx tan 1 x dx x ln a 2. If f x 0 for all x in an interval I then Inflection Points
dx 1 x2
x c is a inflection point of f x if the
f x is decreasing on the interval I.
concavity changes at x c.
3. If f x 0 for all x in an interval I then
f x is constant on the interval I.

Visit [Link] for a complete set of Calculus notes. © 2005 Paul Dawkins Visit [Link] for a complete set of Calculus notes. © 2005 Paul Dawkins
A.A. 2021/22: Deep Learning 6
 Optimization in 1 variable
• To minimize a function in 1 variable, we have to
move in the direction opposite to the derivative
CHAPTER 4. NUMERICAL COMPUTATION

2.0

1.5 Global minimum at x = 0.

Since f 0 (x) = 0, gradient
descent halts here.
1.0

0.5

0.0
For x < 0, we have f 0 (x) < 0, For x > 0, we have f 0 (x) > 0,
so we can decrease f by so we can decrease f by
0.5 moving rightward. moving leftward.

1.0
f (x) = 12 x2
1.5
f 0 (x) = x
2.0
2.0 1.5 1.0 0.5 0.0 0.5 1.0 1.5 2.0
x

Figure 4.1: An illustration of how the gradient descent algorithm uses the derivatives of a
function
A.A. 2021/22: can be used to follow the function downhill to a minimum.
Deep Learning 7
 Simple example: finding a minimum
• Let’s try to find the minimum with gradient descent of ! " = " (
• Compute the gradient (derivative) !$ " = 2" (check the cheat sheet)
• It is the slope of the tangent, i.e. points in the direction of the
greatest rate of increase of the function
Idea of gradient descent:
! "
1. Start with a random value for "
2. Update " doing a little step in the
opposite direction w.r.t. the
gradient (% parameter)
" = " − %!′(") !!"# "
1. Repeat 2 until convergence (i.e.
"
gradient very small)
AL: start from z=2, with 0=0.25 find the minimum of the
function
A.A. 2021/22: Deep Learning
 Simple example: Gradient descent
univariate function
• Let’s start (at random) with 1 ' = 2.

• (gradient) 4$ 2 = 2 5 2 = 4

• Let’s update 1 is the opposite direction w.r.t. the gradient. Let’s

also define our step size as 0 = 0.25

• 1) = 1 ' − 0.25 5 4 = 1

• We now have 4$ 1 = 2 5 1 = 2

• 1 ( = 1) − 0.25 5 2 = 0.5

• 4$ 0.5 = 2 5 0.5 = 1

• ….
A.A. 2021/22: Deep Learning
ER 4. NUMERICAL COMPUTATION
Critical points

Minimum Maximum Saddle point

4.2: Examples of each of the three types of critical points in 1-D. A critical
with
A.A. zero slope.
2021/22: Deep Learning Such a point can either be a local minimum, which is 10
low
ER 4. NUMERICAL COMPUTATION

Global vs local minima

This local minimum

performs nearly as well as
the global one,
so it is an acceptable
halting point.
f (x)

Ideally, we would like

to arrive at the global
minimum, but this
might not be possible.
This local minimum performs
poorly and should be avoided.

x
• Global minimum vs local minima
4.3: Optimization algorithms may fail to find a global minimum when there
e local minima or plateaus present. In the context of deep learning, we gene
such solutions even though they are not truly minimal, so long as they corresp
A.A. 2021/22: Deep Learning 11
ficantly low values of the cost function.
 Multiple inputs
• Partial derivatives measure how ! changes as only
the variable "! increases at point #
$
!(#)
$"!
• Gradient is the generalization of derivative with
respect to a vector of input variables
$ $
∇" ! # = [ ! # ,…, ! # ]
$"# $"$
‣ i.e. It is the vector of the partial derivatives
=
{∇* #(;)}+ = #(;)
=%+
Critical points: all elements of the gradient are 0
A.A. 2021/22: Deep Learning 12
 Multivariate calculus
• The rules of partial differentiation follow exactly the
same logic as univariate differentiation.

• When computing partial derivatives w.r.t. a variable,

consider other variables as constants

• Lecture notes

• Chapter 5 of “Mathematics for Machine Learning”

A.A. 2021/22: Deep Learning 13

 Gradient
• The gradient points directly uphill, while the
negative gradient points downhill

A.A. 2021/22: Deep Learning 14

 Gradient descent
Idea: We can decrease - moving in the direction of
negative gradient

• Iterative algorithm, proposes a new point

#% = # − /∇" !(#)
‣ , > 0 is the learning rate (small)

• The algorithm converges when the gradient is zero

(or very small)

• In some cases, we may be able to analytically solve

∇" ! # = 0. Not the case for neural networks
Hill Climbing follows a similar idea, but in discrete spaces.
A.A. 2021/22: Deep Learning 15
 Beyond gradient
• If input and output are both vectors, the Jacobian
matrix is the matrix of all the partial derivatives

!: ℝ$ → ℝ& , 5 ∈ ℝ&×$
$ $
∇" ! #
…
& ' & '
$%! !
$%" !
#
()(") ()(")
5= ,…, = …
(,! (,"
$ $
& ' # & ' #
$%! $%"

-#
• Second derivatives # ! or !’’(") measures the
-,
curvature of a function
A.A. 2021/22: Deep Learning 16
 Second derivatives
First-order approximation
! " + / ≈ ! " + /!′(")
• Provide information about the curvature of the function
CHAPTER 4. NUMERICAL COMPUTATION
• Consider quadratic functions, step size , ! " + $ > ! " + $!′(")
Negative curvature No curvature Positive curvature

! " + $ < ! " + $!′(")

f (x)

f (x)

f (x)
x x x
#’’ % < 0 #’’(%) = 0 #’’ % > 0
Figure 4.4: The second derivative determines the curvature of a function. Here we show
quadratic functions with various curvature.
! " + $ = The
! " dashed
+ $!′(")line indicates the value of the cost
function we would expect based on the gradient information alone as we make a gradient
step downhill. In the case of negative curvature, the cost function actually decreases faster
A.A. 2021/22: Deep Learning 17
than the gradient predicts. In the case of no curvature, the gradient predicts the decrease
 Hessian matrix
• The matrix of second derivatives (the Jacobian of
the gradient)
/
& &×&
$
!: ℝ → ℝ , ; ∈ ℝ , ;!. = !
$"! $".
$$ … $$
& ' & '
$%!$ $%! $%#

;= $$ $$
& ' & '
$%# %! $%#$

A.A. 2021/22: Deep Learning 18

 Condition number
• ratio of the largest eigenvalue
CHAPTER to the
4. NUMERICAL smallest
COMPUTATION

• asymptotic worst-case relative change in a function

• Condition number of the Hessian matrix tells us how
much the second derivatives differ from one to each
other
‣ Gradient descent is a first order method, so it ignores
information in the hessian!
• second-order optimization 20
algorithms (such as Newton’s
10
method) considers the Hessian
0
• Slow (need to compute Hessian) x2
so not widely used for deep 10

learning 20

30
30 20 10 0 10 20
A.A. 2021/22: Deep Learning x1 19
 Constrained optimization problem
• Krush-Kuhn-Tucker approach (generalized
Laplacian)
! .
• !(#), with constraints ∀! = # = 0, ∀. ℎ # ≤0
! .
@ #, A, B = ! " + C D! = # + C E. ℎ (#)
min ! .
max

• We can solve a constrained problem using

unconstrained optimization

A.A. 2021/22: Deep Learning 20

 Example: Linear Regression with GD
Let’s consider a Perceptron WITHOUT hard-threshold:

! #; G, H = G0 # + H

And let’s define a loss function

Mean squared error
(
1 +
4 D; E = G H − # ; + ; D; E
2A,-
(* ! ,0 ! )∈,-

Where A,- is the cardinality of the training set BC.

The error function measures the mean squared error of the
output with respect to the target value.

We would like to find values for D and E such that 4(D; E) is

MINIMIZED.
A.A. 2021/22: Deep Learning 25
 Example: Linear Regression with GD
• Let us compute the gradient w.r.t. G:
‣ For ease of notation, let us extend ; with an entry fixed
to 1 and let us incorporate b in D
# ;; D = D, ;
1 (3) + 4
J " = ' ( − (+ ,)
2&+,
- ! ,/ ! ∈12

• Notebook: gradient descent for linear regression

A.A. 2021/22: Deep Learning 26

 Matrix notation: Gradient of Linear
7 7
Regression ∇ ! - = [7" ! - , … , 7" !
" #
! - ]

• Let us compute the gradient w.r.t. G:

‣ For ease of notation, let us extend ; with an entry fixed
to 1 and let us incorporate b in D
1 (+) , (6) (
∇3 4(D) = ∇3 G H − (D ; )
2A,-
* ! ,0 ! ∈45

1 (+) , (6) (
= G ∇3 H − (D ; ) =
2A,-
* ! ,0 ! ∈45
) (+) , (6)
=- ∑ *(!) ,0 (!) ∈45 2 H − D ; ;(6) =
(7"#
1
=− G H (+) − D, ;(6) ;(6)
A,-
*(!) ,0 (!) ∈45

• Gradient descent update rule: G% = G − I(∇1 J(G))0

A.A. 2021/22: Deep Learning 27