Training a Neural Network

Lecture 20 contd: Neural Network Training using Backpropagation, Convolutional And Recurrent Neural Networks

Instructor: Prof. Ganesh Ramakrishnan

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Feed-forward Neural Nets

x_n x₂ x₁ 1

z₁ =g(∑)

z₂ =g(∑) w_n1

w₂₁ w₁₁ w₀₁

w_n2 w₂₂ w₁₂ w₀₂

f₁ =g(.)

f₂ =g(.) inputs

October 10, 2016 2 / 19

Training a Neural Network

STEP 0: Pick a network architecture

Number of input units: Dimension of features ϕ (

x⁽ⁱ⁾) . Number of output units: Number of classes.

Reasonable default: 1 hidden layer, or if >1 hidden layer, have same number of hidden units in every layer.

Number of hidden units in each layer a constant factor (3 or 4) of dimension ofx.

We will use

▶ the smooth sigmoidal functiong(s) =_1+e¹₋s: We have now learnt how to train a single node sigmoidal (LR) neural network

▶ instead of the non-smooth step functiong(s) = 1ifs∈[θ,∞)andg(s) = 0otherwise.

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

High Level Overview of Backpropagation Algorithm for Training NN

1 Randomly initialize weightsw^l_ij for l= 1, . . . ,L,i= 1, . . . ,s_l,j= 1, . . . ,s_l+1.

2 Implementforward propagation to getf_w(x) for anyx∈ D.

3 Execute backpropagation

1 by computing partial derivatives ^∂

∂w^(l)_ij E(w)forl= 1, . . . ,L,i= 1, . . . ,sl,j= 1, . . . ,sl+1.

2 and using gradient descent to try to minimize (non-convex)E(w)as a function of parametersw.

w^l_ij=w^l_ij−η ∂

∂w^(l)_ij E(w)

4 Verify that the cost functionE(w) has indeed reduced, else resort to some random perturbation of weights w.

October 10, 2016 4 / 19

The Backpropagation Algorithm

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Setting Notation for Backpropagation

σ^l_s⁻_l−¹₁ σ_i^l−1 σ₂^l−1 σ₁^l−1

σ_j^l=σ (

sum^l_j)

σ^l_sl =σ

(sum^l_sl) w^l_sl

−1j

w^l_ij w^l_2j w^l_1j

w^l_sl−1sl w^l_isl w^l_2sl w^l_1sl

σ^L₁

σ^L_K (l−1)^th layer

October 10, 2016 6 / 19

Gradient Computation

The Neural Network objective to be minimized:

E(w) =−1 m



∑^m

i=1

∑K k=1

y⁽ⁱ⁾_k log (

σ^L_k( x⁽ⁱ⁾))

+( 1−y⁽ⁱ⁾_k )

log (

1−σ^L_k( x⁽ⁱ⁾))



+ λ 2m

∑L l=1

s∑l−1 i=1

s_l

∑

j=1

(w^l_ij)2

(1)

sum^l_j =

s_l−1

∑

k=1

w^l_kjσ_k^l−1 andσ^l_i = ¹

1+e^−sumli

∂E

∂w^l_ij = _∂σ^∂El j

∂σ_j^l

∂sum^l_j

∂sum^l_j

∂w^l_ij +_2m^λ w^l_ij

∂σ^l_j

∂sum^l_j = (

1 1+e^−sumli

) (

1− ¹

1+e^−sumli

)

=σ_j^l(1−σ_j^l)

∂sum^l_j

∂w^l_ij = _∂w^∂_l

ij





sl−1

∑

k=1

w^l_kjσ_k^l−1



=σ_i^l−1

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Gradient Computation

The Neural Network objective to be minimized:

E(w) =−1 m



∑^m

i=1

∑K k=1

y⁽ⁱ⁾_k log (

σ^L_k( x⁽ⁱ⁾))

+( 1−y⁽ⁱ⁾_k )

log (

1−σ^L_k( x⁽ⁱ⁾))



+ λ 2m

∑L l=1

s∑l−1 i=1

s_l

∑

j=1

(w^l_ij)2

(1)

sum^l_j=

s_l−1

∑

k=1

w^l_kjσ_k^l−1 andσ^l_i = ¹

1+e^−sumli

∂E

∂w^l_ij = _∂σ^∂El j

∂σ_j^l

∂sum^l_j

∂sum^l_j

∂w^l_ij +_2m^λ w^l_ij

∂σ^l_j

∂sum^l_j = (

1 1+e^−sumli

) (

1− ¹

1+e^−sumli

)

=σ^l_j(1−σ_j^l)

∂sum^l_j

∂w^l_ij = _∂w^∂l ij





sl−1

∑

k=1

w^l_kjσ_k^l−1



=σ_i^l−1

October 10, 2016 7 / 19

For a single example(x,y):

−



∑^K

k=1

y_klog( σ^L_k(x))

+ (1−y_k)log(

1−σ^L_k(x))



+ λ 2m

∑L l=1

s∑l−1 i=1

sl

∑

j=1

(w^l_ij)2

(2)

∂E

∂σ^l_j =

sl+1

∑

p=1

∂E

∂sum^l+1_p

∂sum^l+1_p

∂σ^l_j =

sl+1

∑

p=1

∂E

∂σp^l+1

∂σ_p^l+1

∂sum^l+1_p w^l+1_jp since ^∂suml+1p

∂σ^l_j =w^l+1_jp

∂E

∂σ^L_j =−_σ^yL^j

j −₁¹₋⁻_σ^yL^j j

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Backpropagation in Action

σ^l_s⁻_l−¹₁ σ_i^l−1 σ₂^l−1 σ₁^l−1

∂E

∂σl j

= sl+1∑ p=1

∂E

∂σ^l+1_p

∂σ^l+1_p

∂sum^l+1_p w^l+1_jp

∂E

∂σl sl

= sl+1∑ p=1

∂E

∂σ^l+1p

∂σ^l+1_p

∂sum^l+1_sl+1w^l+1_sl+1p

w^l_sl

−1j

w^l_ij w^l_2j w^l_1j

w^l_sl

−1sl

w^l_is

l

w^l_2sl w^l_1sl

σ^L₁

σ^L_K (l−1)^th layer

October 10, 2016 9 / 19

Backpropagation in Action

. σ_i^l−1

. .

∂E

∂σ^l_j

.

∂E

∂w^l_ij = _∂σ^∂El j

∂σ_j^l

∂sum^l_j

∂sum^l_j

∂w^l_ij

. .

. . . .

σ^L₁

σ^L_K (l−1)^th layer

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Recall and Substitute

sum^l_j=

s_l−1

∑

k=1

w^l_kjσ_k^l−1 andσ^l_i = ¹

1+e^−sumli

∂E

∂w^l_ij = _∂σ^∂El j

∂σ_j^l

∂sum^l_j

∂sum^l_j

∂w^l_ij +_2m^λ w^l_ij

∂σ^l_j

∂sum^l_j =σ_j^l(1−σ^l_j)

∂sum^l_j

∂w^l_ij =σ_i^l−1

∂E

∂σ^l_j =

s_l+1

∑

p=1

∂E

∂σ_j^l+1

∂σ_j^l+1

∂sum^l+1_p w^l+1_jp

∂E

∂σ^L_j =−_σ^yL^j

j −₁¹₋⁻_σ^yL^j j

October 10, 2016 11 / 19

Backpropagation in Action

. σ_i^l−1

. .

∂E

∂σ_j^l,σ_j^l

.

∂E

∂w^l_ij = _∂σ^∂El

jσ_j^l(1−σ^l_j)σ^l_i⁻¹+_2m^λ w^l_ij .

.

. . . .

σ^L₁

σ^L_K (l−1)^th layer

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Backpropagation in Action

. σ_i^l−1

. .

∂E

∂σ^l_j

∂E

∂σ^l_sl

.

w^l_ij =w^l_ij−η_∂w^∂El ij

. .

. . . .

σ^L₁

σ^L_K (l−1)^th layer

October 10, 2016 13 / 19

The Backpropagation Algorithm for Training NN

1 Randomly initialize weightsw^l_ij for l= 1, . . . ,L,i= 1, . . . ,s_l,j= 1, . . . ,s_l+1.

2 Implementforward propagation to getf_w(x) for everyx∈ D.

3 Execute backpropagationon any misclassifiedx∈ D by performing gradient descent to minimize (non-convex)E(w)as a function of parameters w.

4 ∂E

∂σ^L_j =−_σ^yL^j

j −₁¹₋⁻_σ^yL^j j

for j= 1 tos_L.

5 For l=L−1 down to 2:

1 ∂E

∂σ^l_j =

sl+1

∑

p=1

∂E

∂σ^l+1_j σ_j^l+1(1−σ_j^l+1)w^l+1_jp

2 ∂E

∂w^l_ij =_∂σ^∂El j

σ_j^l(1−σ_j^l)σ^l_i⁻¹+_2m^λ w^l_ij

3 w^l_ij=w^l_ij−η_∂w^∂El ij

6 Keep picking misclassified examples until the cost function E(w) shows significant

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Challenges with Neural Network Training

October 10, 2016 15 / 19

What Changed with Neural Networks?

Origin: Computational Model of Threshold Logic from Warren McCulloch and Walter Pitts (1943)

Big Leap: For ImageNet Challenge, AlexNet acheived 85 % accuracy(NIPS 2012). Prev best was 75 % (CVPR 2011).

Present best is 96.5 % MSRA (arXiv 2015). Comparable to human level accuracy.

Challenges involved were varied background, same object with different colors(e.g. cats), varied sizes and postures of same objects, varied illuminated conditions.

Tasks like OCR, Speech recognition are now possible without segmenting the word image/signal into character images/signals.

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

LeNet(1989 and 1998) v/s AlexNet(2012)

October 10, 2016 17 / 19

Reasons for Big Leap

Why LeeNet was not as successful as AlexNet, though the algorithm was same?

Right algorithm at wrong time.

Modern features.

Advancement in Machine learning.

Realistic data collection in huge amount due to: regular competitions, evaluation metrics or challenging problem statements.

Advances in Computational Resources: GPUs, industrial scale clusters.

Evolution of tasks: Classification of 10 objects to 100 objects to “structure of classes”.

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Convolutional Neural Network

Variation of multi layer feedforward neural network designed to use minimal preprocessing with wide application in image recognition and natural language processing

Traditional multilayer perceptron(MLP) models do not take into account spatial structure of data and suffer from curse of dimensionality

Convolution Neural network has smaller number of parameters due tolocal connections andweight sharing

October 10, 2016 19 / 19