DD2380 Artificial Intelligence

Machine Learning 1: Deep Neural Networks

Alexandre Proutiere
September 6, 2017
KTH (The Royal Institute of Technology)
Outline of today’s lecture

0. Introduction: Supervised vs. Unsupervised learning

1. Supervised Learning
A. Regression and Classification
B. Neural Networks (Deep Learning)

2. Reinforcement Learning

1
Outline of today’s lecture

0. Introduction: Supervised vs. Unsupervised learning

1. Supervised Learning
A. Regression and Classification
B. Neural Networks (Deep Learning)

2. Reinforcement Learning

2
”Machine Learning explores the study and construction of algorithms
that can learn from and make predictions on data” (Wikipedia)

3
Learning

Supervised (or Predictive) learning (or learning from examples)

Learn a mapping from inputs x to outputs y, given a labeled set

of input-ouput pairs (the training set)
Dn = {(Xi , Yi ), i = 1, . . . , n}

We learn the classification function f = 1 if versicolor, f = −1 if virginica

4
Learning

Unsupervised (or Descriptive) learning

Find interesting patterns in the data Dn = {Xi , i = 1, . . . , n}

We learn there are 2 distinct types of iris and how to distinguish them!

5
Examples

Supervised learning:
• digit, flower, picture, ... recognition
• music classification
• predict prices
• predict the outcome of chemical reactions
• source separation: identify the instruments present in a recording
• ...

Unsupervised learning:
• classification (without training set): spam filter, news (google news),
...
• identify structures and causes in the data: e.g. J. Snow – cholera
deaths vs pollution
• image segmentation
• ...
6
Outline of today’s lecture

0. Introduction: Supervised vs. Unsupervised learning

1. Supervised Learning
A. Regression and Classification
B. Neural Networks (Deep Learning)

2. Reinforcement Learning

7
Supervised learning: regression vs. classification

• Training set: Dn = {(Xi , Yi ), i = 1, . . . , n}

- Input features: Xi ∈ Rd
- Output: Yi
(
R regression (price, position, etc)
Yi ∈ Y
finite classification (type, mode, etc)
• y is a non-deterministic and complicated function of x
i.e., y = f (x, z) where z is unknown (e.g. noise). Goal: learn f .
• Learning algorithm:

8
Empirical risk

• Learning algorithm: A : Dn 7→ fˆn , fˆn estimates the true function f

• Performance of predictions defined through a loss function `

- Example 1. Regression, Least Squares (LS): Y = R,
`(y, y 0 ) = 21 |y − y 0 |2
- Example 2. Classification in Y = {0, 1}: `(y, y 0 ) = 1y6=y0

• Empirical risk of estimate g:

n
1X
R̂n (g) := `(g(Xi ), Yi )
n i=1

(often referred to as in-sample error)

9
Examples of classification algorithms

• Local averaging:
k-nearest neighbors
Nadaraya-Watson (Gaussian kernel)

• Support Vector Machine:

Aim at finding an hyperplane
”optimally” separating data

• Minimizing the empirical risk within a predefined set F of functions,

called the ”model”. Example: Deep learning

10
Model selection

We look for fˆn , the estimate of the true function, in a particular set F of
functions (e.g. for regression, linear or polynomial functions)

The choice of F is guided considering:

Expressibility. How large the class of functions that F can represent is.

Efficiency. How many parameters are required to approximate a function.

Learnability. How rapidly the model can be trained (sample complexity).

11
Model selection - Choosing F

Avoid overfitting!

A few principles:

• Occam’s razor principle: choose the simplest of two models if they

explain the data equally well
• Hadamard’s well posed problems: unique solution, smooth in the
parameters

Regularization: minimize error(fˆn )+Ω(fˆn ) – Penalizes the model

complexity
12
Linear regression: Minimizing the empirical risk

• F = set of linear functions from Rd (Xi ∈ Rd ) to R (Yi ∈ R)

• Function fθ ∈ F parametrized by θ ∈ Rd+1 : (by convention x0 = 1)

fθ (x) = θ0 + θ1 x1 + . . . + θd xd = θ> x

• Least square model. Empirical risk of θ:

1
Pn 2
R̂n (θ) = 2n i=1 (fθ (Xi ) − Yi )

• Minimal risk achieved for θ? = (X> X)−1 X> y where

y = [Y1 . . . Yn ]> and X is a matrix whose i-th line is Xi>

13
Gradient Descents for Regression

Alternative methods to find θ? : sequential algorithms.

Batch gradient descent. Repeat:

n
X
∀k ∈ {0, 1, . . . , d}, θk := θk − α (Yi − fθ (Xi ))Xik
i=1

Stochastic gradient descent. Repeat:

1. Select a sample i uniformly at random

2. Perform a descent using (Xi , Yi ) only

∀k ∈ {0, 1, . . . , d}, θk := θk − α(Yi − fθ (Xi ))Xik

14
Linear regression: Regularization

• For d > n, X> X ∈ Rd×d is not invertible, so θ? is not uniquely

defined. Need to put additional constraints on the model to get a
well-posed problem
• Regularization: add a cost for the magnitude of θ
n
1 X
min (fθ (Xi ) − Yi )2 + λΩ(θ)
θ 2n i=1

Ridge: Ω(θ) = kθk22

LASSO: Ω(θ) = kθk1
`p : Ω(θ) = kθkp

p small (< 1): sparse solutions but hard optimization problems

p large (≥ 1): less sparse solutions but convex optimization problems
15
Linear regression: Regularization

• Regularization: add a cost for the magnitude of θ

n
1 X
min (fθ (Xi ) − Yi )2 + λΩ(θ)
θ 2n i=1

• λ > 0 controls the bias-variance trade-off

- High value of λ: the data has a low weight in the objective function
(low variance but high bias)
- Low value of λ: the data has a high weight in the objective function
(low bias but high variance)
• Solution for Ridge regression: θ? = (X> X + nλI)−1 X> y
Prediction: For all x ∈ Rd , fˆλ (x) = y> (X> X + nλI)−1 X> x

16
Outline of today’s lecture

0. Introduction: Supervised vs. Unsupervised learning

1. Supervised Learning
A. Regression and Classification
B. Neural Networks (Deep Learning)
(i) From perceptron to deep networks
(ii) Computing with and training neural nets
(iii) Why deep? Why does it work?

2. Reinforcement Learning

17
Neural networks

Loosely inspired by how the brain works1 . Construct a network of

simplified neurones, with the hope of approximating and learning any
possible function

1 Mc Culloch-Pitts, 1943
18
The perceptron

The first artificial neural network with one layer, and σ(x) = sgn(x)
(classification)
Input x ∈ Rd , output in {−1, 1}. Can represent separating hyperplanes.

19
Multilayer perceptrons

They can represent any function of Rd to {−1, 1}

... but the structure depends on the unknown target function f , and is
difficult to optimise

20
From perceptrons to neural networks

... and the number of layers can

rapidly grow with the complexity
of the function

A key idea to make neural networks practical: soft-thresholding ...

21
Soft-thresholding

Replace hard-thresholding function σ by smoother functions

Theorem (Cybenko 1989) Any continuous function f from

[0, 1]d to R can be approximated as a function of the form:
PN >
j=1 αj σ(wj x + bj ), where σ is any sigmoid function.

22
Soft-thresholding

Cybenko’s theorem tells us that f can be represented using a single

hidden layer network ...

A non-constructive proof: how many neurones do we need? Might

depend on f ...

23
Neural networks

A feedforward layered network (deep learning = enough layers)

24
Deep Learning and the ILSVR challenge

Deep learning outperformed any other techniques in all major machine

learning competitions (image classification, speech recognition and
natural language processing)
The ImageNet Large Scale Visual Recognition Challenge
(ILSVRC).

1. Training: 1.2 million images (227×227), labeled one out of 1000

categories
2. Test: 100.000 images (227×227)
3. Error measure: The teams have to predict 5 (out of 1000) classes
and an image is considered to be correct if at least one of the
predictions is the ground truth.

25
ILSVR challenge2

2 From Stanford CS231n lecture notes

26
Architectures

27
Architectures

28
Outline of today’s lecture

0. Introduction: Supervised vs. Unsupervised learning

1. Supervised Learning
A. Regression and Classification
B. Neural Networks (Deep Learning)
(i) From perceptron to deep networks
(ii) Computing with and training neural nets
(iii) Why deep? Why does it work?

2. Reinforcement Learning

29
Computing with neural networks

(0) (0) (0)

• Layer 0: inputs x = (x1 , . . . , xd ) and x0 = 1
• Layer 1, . . . , L − 1: hidden layer `, d(`) + 1 nodes, state of node i,
(`) (`)
xi with x0 = 1
(L)
• Layer L: output y = x1

(`) Pd(`−1) (`) (`−1)

Signal at k: sk = i=0 wik xi

(`) (`)
State at k: xk = σ(sk )

(L)
Output: the state of y = x1

30
Training neural networks

(`)
The output of the network is a function of w = (wij )i,j,` : y = fw (x)
We wish to optimise over w to find the most accurate estimation of the
target function

Training data: (X1 , Y1 ), . . . , (Xn , Yn ) ∈ Rd × {−1, 1}

Objective: find w minimising the empirical risk:

n
1 X
E(w) := R(fw ) = |fw (Xl ) − Yl |2
2n
l=1

31
Stochastic Gradient Descent

1
Pn 2
E(w) = 2n l=1 El (w) where El (w) := |fw (Xl ) − Yl |
In each iteration of the SGD algorithm, only one function El is
considered ...

Parameter. learning rate α > 0

1. Initialization. w := w0
2. Sample selection. Select l uniformly at random in
{1, . . . , n}
3. GD iteration. w := w − α∇El (w), go to 2.

Is there an efficient way of computing ∇El (w)?

32
Backpropagation

We fix l, and introduce e(w) = El (w).

Let us compute ∇e(w):

(`)
∂e ∂e ∂sj
(`)
= (`)
× (`)
∂wij ∂sj ∂wij
| {z } | {z }
(`) (`−1)
:=δj =xi

The sensitivity of the error w.r.t. the signal at node j can be computed
recursively ...

33
Backward recursion
(L) ∂e (L)
Output layer. δ1 := (L) and e(w) = (σ(s1 ) − Yl )2
∂s1

(L) (L) (L)

δ1 = 2(x1 − Yl )σ 0 (s1 )

From layer ` to layer ` − 1.

(`) (`)
d (`−1)
(`−1) ∂e X ∂e ∂sj ∂xi
δi := (`−1)
= (`)
× (`−1)
× (`−1)
∂si j=1 ∂sj ∂xi ∂s
| {z } | {z } | i{z }
(`) (`) (`−1)
:=δj =wij =σ 0 (si )

Summary.
(`)
d
∂El (`) (`−1) (`−1)
X (`) (`) (`−1)
(`)
= δ j xi , δi = δj wij σ 0 (si )
∂wij j=1

34
Backpropagation algorithm

Parameter. Learning rate α > 0

Input. (X1 , Y1 ), . . . , (Xn , Yn ) ∈ Rd × {−1, 1}
1. Initialization. w := w0
2. Sample selection. Select l uniformly at random in
{1, . . . , n}
3. Gradient of El .
(0)
• xi := Xli for all i = 1, . . . d
• Forward propagation: compute the state and signal at each
(`) (`)
node (xi , si )
(`)
• Backward propagation: propagate back Yl to compute δi
∂El
at each node and the partial derivative (`)
∂wij

4. GD iteration. w := w − α∇El (w), go to 2.

35
Example: tensorflow

[Link]

36
Outline of today’s lecture

0. Introduction: Supervised vs. Unsupervised learning

1. Supervised Learning
A. Regression and Classification
B. Neural Networks (Deep Learning)
(i) From perceptron to deep networks
(ii) Computing with and training neural nets
(iii) Why deep? Why does it work?

2. Reinforcement Learning

37
Deep learning and model selection

A given network represents a model. F encodes the architecture and

topolgy of the network.

F = {fw : w ∈ W ⊂ Rb }

Deep learning = find the weights or equivalently the function in F

minimising the empirical risk. Why should it be good?
Expressibility. How large the class of functions that F can represent is.

Efficiency. How many parameters are required to approximate a function.

Learnability. How rapidly the model can be trained (sample complexity).

38
Expressibility and Efficiency of Neural Nets3

• Neural nets can approximate any continuous function (Cybenko’s

theorem).
• Neural nets can compute polynomials efficiently.

Lemma Let σ be a sigmoid function with non-zero second derivative

at 0. Using 4 σ-neurones, we can approximation the multiplication.

Corollary The class of polynomials involving n multiplications can

be represented (with arbitrary precision) with a neural network of
size slightly larger than 4n.

3 Why does deep and cheap learning work so well? Lin-Tegmark, 2016
39
Why deep?

No flattening theorem:

Theorem To compute the product of n variables in a single-layer

network, we need 2n neurones.

Extensions: with two layers we need 2 × 2n/2 neurones.

40
Learnability

Critical question: The SGD algorithm will converge to a global

minimum of the risk, if we can guarantee that local minima have the
same risk as a global minimum. What does the loss surface look like?

The output of a neural network is a non-linear function of the weights,

and possibly has many bad local minima where the SGD gets trapped.
41
Notations

• Data: Xi ∈ Rdx , Yi ∈ Rdy , m data points

X: dx × m matrix whose columns are the Xi s
Y : dy × m matrix whose columns are the Yi ’s
• H hidden layers
• Layer k with dk neurons, input weight matrix Wk ∈ Rdk ×dk1
• p = min{d1 , . . . , dH }
• Output:

Ŷ (W, X) = qσH+1 (WH+1 σ(WH σ(WH1 . . . σ(W2 σ(W1 X) . . .)

Linear activation function: Ŷ (W, X) = WH+1 . . . W1 X.

42
1-hidden layer networks

• Linear regression: fitting a linear model to the data. Xi ∈ Rdx ,

Yi ∈ Rdy
Find the matrix L? ∈ Rdy ×dx minimizing
m
X
L(L) = kYi LXi k2
i=1

When XX > is invertible, L? = Y X > (XX > )−1 Convexity of L

• Now in a 1-hidden layer network, we are looking for L that can be
factorized as W2 W1 where W1 ∈ Rp×dx and W2 ∈ Rdy ×p .
In particular the rank of L is at most p. Non uniqueness:
W10 = CW1 and W20 = W2 C −1 work as well.

43
1-hidden layer networks

Introduce the dy × dy matrix Σ = Y X > (XX > )−1 XY > as the

covariance matrix of the best unconstrained linear approximation of Y

Theorem (Baldi-Hornik, 1989) Assume that Σ is full rank with

distinct eigenvalues. Up to C, the global minimizer is unique, and is
the projection on the subspace spanned by the p top eigenvectors of
Σ of the ordinary least square regression matrix.

44
H-hidden layer networks

Theorem (Kawaguchi, 2016) Assume that XX > and Y Y > are

full rank, and dx ≥ dy . Assume that Σ is full rank with distinct
eigenvalues. The loss function L(W1 , . . . , WH+1 ) satisfies:
(i) it is non-convex and non-concave.
(ii) Every local minimum is a global minimum.
(iii) Every critical point that is not a minimum is a saddle point.
(iv) If rank(WH , . . . , W2 ) = p, then the Hessian at any saddle point
has at least one strictly negative eigenvalue (we can escape
local saddle points).

45
Neural networks

Open questions:

• What is the role of the regularization term?

• What about sigmoid functions, and ReU?
• Interpretability of the role of the various layers?
• ...

46
A few references

• P. Baldi, K. Hornik. Neural Networks and PCA: Learning from

Examples without Local Minima. Neural Networks, 1989.
• I. Goodfellow, Y. Bengio, A. Courville. Deep Learning,
[Link]
• A. Choromanska et al.. The Loss Surface of Multilayer Networks.
ICML 2015.
• K. Kawaguchi. Deep Learning without Poor Local Minima. NIPS
2016

47