B a c k p r o p a g a t i o n
Loss function and activation
Dr. Haithem Hermessi
•
•
Sr. Compu te r Vision Engine e r @ SCYLLA
AI research Scientist @ LIMTIC - University of Tunis El Manar
Parameterized Model
Parameterized model
Example: linear regression
Example: Nearest neighbor:
Cost
Function
Implicit
scalar output
Output
y
C(y,y)
Parameterized
Deterministic
Function
implicit parameter input
G(x,w)
Computing function G may involve
complicated algorithms
x
y
Input
Desired
output
Block diagram notations for computation graphs
Variables (tensor, scalar, continuous, discrete...)
Observed: input, desired output…
Computed variable: outputs of deterministic functions
x
y
x
G(x,w)
y
Deterministic function
Multiple inputs and outputs (tensors, scalars,….)
Implicit parameter variable (here: w)
y
C(y,y)
y
Scalar-valued function (implicit output)
Single scalar output (implicit)
used mostly for cost functions
Loss function, average loss
Simple per-sample loss function
A set of samples
Average loss over the set
average
y
y
C(y,y)
C(y,y)
C(y,y)
C(y,y)
y
y
G(x,w)
G(x,w)
G(x,w)
G(x,w)
x[0]
Advertisement
x[1]
y[0]
y[1]
x[2]
x[3]
y[2]
y[3]
Gradient Descent
Full (batch) gradient
Stochastic Gradient (SGD)
Pick a p in 0...P-1, then update w:
SGD exploits the redundancy in the samples
It goes faster than full gradient in most cases
In practice, we use mini-batches for parallelization.
-g
g
Traditional Neural Net
Stacked linear and non-linear functional blocks
Weighted sums, matrix-vector product
Point-wise non-linearities (e.g. ReLu, tanh, ….)
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
Traditional Neural Net
Stacked linear and non-linear functional blocks
w
w[i,j]
w
s[j]
z[j]
w
w
w
w
s[i]
z[i]
Backprop through a non-linear function
Chain rule:
g(h(s))’ = g’(h(s)).h’(s)
dc/ds = dc/dz * dz/ds
dc/ds = dc/dz * h’(s)
Perturbations:
Perturbing s by ds will perturb z
by: dz=ds*h’(s)
h(s)
z
This will perturb c by
dc = dz dc/dz = dsh’(s)*dc/dz
Advertisement
s
Hence: dc/ds = dc/dz*h’(s)
c
cost
1
cost
network
hT(s)
dc/dz
*
dc/ds
derivative
network
x
y
dc/dx dc/dy
Backprop through a weighted sum
Perturbations:
Perturbing z by dz will perturb
s[0],s[1],s[2] by ds[0]=w[0]*dz,
ds[1]=w[1]dz, ds[2]=w[2]dz
This will perturb c by
dc = ds[0]*dc/ds[0]+
s[0] s[1] s[2]
c
cost
1
cost
dc/ds[1]
dc/ds[0] dc/ds[2]
ds[1]*dc/ds[1]+
ds[2]*dc/ds[2]
w[0] w[1] w[2]
network
w[0] w[1] w[2]
Hence: dc/dz = dc/ds[0]*w[0]+
z
dc/dz
derivative
réseau
network
dérivé
e
dc/ds[1]*w[1]+
dc/ds[2]*w[2]+
x
y
dc/dx dc/dy
Block Diagram of a Traditional Neural Net
linear blocks
Non-linear blocks
PyTorch definition
Object-oriented version
Uses predefined nn.Linear class,
(which includes a bias vector)
Uses torch.relu function
State variables are temporary
Y. LeCun
Backprop through a functional module
Using chain rule for vector functions
Jacobian matrix
Partial derivative of i-th output w.r.t. j-th input
c
c(zg,y)
1
dc/dzg
dc/dy
Advertisement
zg
dc/zg
wg
g(zf,wg)
dc/wg
*dg/dwg
*dg/dzf
zf
dc/dzf
wf
f(x,wf)
dc/wf
*df/dwf
*df/dx
x
y
dc/dx dc/dy
Backprop through a multi-stage graph
Using chain rule for vector functions
Two Jacobian matrices for the module:
One with respect to z[k]
One with respect to w[k]
c
1
c(z[K],y)
z[K]
dc/dz[K] dc/dy
w[k+1]
f(z[k+1],w[k+1])
z[k
+1]
dc/dw[k+1]
dc/z[k
*df/dw[k+1]
*df/dz[k+1]
+1]
w[k]
fk(z[k],w[k])
dc/w[k]
*dfk/dw[k]
*dfk/dz[k]
z[k]
dc/dz
[k]
f(z[k-1],w[k-1])
w[k-1]
*df/dw[k-1]
dc/dw[k-1]
*df/dz[k-1]
x
y
dc/dx dc/dy
Backprop = propagation through a transformed graph
Derivative of composed functions
1
*
y
C(y,y)
dC/dy
y
dC(y,y)
dy
G(x,w)
*
dC/dw
dG(x,w)
dw
Advertisement
x
y
x
y
Gradient, Jacobian, ….
Dimensions:
Row vector = row vector . matrix
1
*
y
C(y,y)
dC/dy
y
dC(y,y)
dy
G(x,w)
*
dC/dw
dG(x,w)
dw
Gradient = gradient . Jacobian
x
y
x
y
Basic Modules
Linear
ReLU
Y = W.X ;
dC/dX = WT. dC/dY ; dC/dW = dC/dY . XT
y = ReLU(x)
;
if ( x < 0 ) dC/dx = 0 e l s e dC/dx = dC/dy
Duplicate
Y1 = X, Y2 = X ; dC/dX = dC/dY1 + dC/dY2
Add
M a x
Y = X1 + X2
;
dC/dX1 = dC/dY ;
dC/dX2 = dC/dY
y = m a x ( x 1 , x 2 ) ; if ( x 1 > x 2 ) dC/dx1 = dC/dy e l s e d C / d x 1 = 0
L o g S o f t M a x
Yi = Xi – log[∑j exp(Xj)] ; … . . ? ? ?
Backprop in Practice ….Tips
Use ReLU non-linearities (tanh and logistic are falling out of favor)
Use cross-entropy loss for classification
Use Stochastic Gradient Descent on minibatches
Shuffle the training samples
Normalize the input variables (zero mean, unit variance)
Schedule to decrease the learning rate
Use a bit of L1 or L2 regularization on the weights (or a combination)
But it's best to turn it on after a couple of epochs
Use “dropout” for regularization
Hinton et al 2012 http://arxiv.org/abs/1207.0580
Lots more in [LeCun et al. “Efficient Backprop” 1998]
Lots, lots more in “Neural Networks, Tricks of the Trade” (2012 edition)
edited by G. Montavon, G. B. Orr, and K-R Müller (Springer)
Any directed acyclic graph is OK for backprop
As long as there is a partial order on the
modules
Reference:
•
Yann LeCun’s Deep Learning Course at CDS: DS-GA 1008
FAIR: “Giving people the power to share and
connect requires constant innovation…”