Deep Learning -5

Deep Learning
What is Srihari

Regularization?
• Central problem of ML is to design algorithms
that will perform well not just on training data
but on new inputs as well
• Regularization is:
– “any modification made to a learning algorithm to
reduce generalization error but not training error”
• Reduce test error even at expense of higher training error
Deep Learning Srihari

Philosophical view
• Regularization is a recurrent issue in ML
• Hinton borrowed the concept in his
neural networked view:
– used a shocking term "unlearning" to refer to it.
• To achieve a greater effectiveness, one must
not learn the idiosyncrasies of the
data(noise, outliers, or overly specific
patterns)
• One must remain a little ignorant in order to
discover the true behavior of the data
 Some Goals of
Deep Learning Srihari

Regularization
• Many forms of regularization available
– Major efforts are to develop better regularization
• Put extra constraints on objective function
– They are equivalent to a soft constraint on
parameter values
• Result in improved performance on test set
• Result in improved performance on test set
• A hard constraint would strictly limit parameters, like:
“∥w∥≤1”.
• A soft constraint (as done by regularization) penalizes
large weights but still allows them if necessary,
balancing between fitting the data and keeping the
model simple. 4
• Some goals of regularization
1. Encode prior knowledge(knowing that the value of the weights should
be smaller)
2. Express preference for simpler model(Occam’s Razor — the simplest
explanation is often the best.)
3. Needed to make underdetermined problem determined (features
greater than samples, but the number of features can be
controlled by this)
Deep Learning Srihari

Regularization using a
simpler model
Deep Learning Srihari

Regularizing Estimators

• In Deep Learning, regularization means

regularizing estimators
• Involves increased bias for reduced variance
– Good regularizes reduces variance significantly
while not overly increasing bias
Deep Learning Srihari

Model Types and Regularization

• Three types of model families
1. Excludes the true data generating process
• Implies underfitting and inducing high bias
2. Matches the true data generating process
3. Overfits
• Includes true data generating process but also
many other processes
• Goal of regularization is to take
model from third regime to second
Deep Learning Srihari

Importance of Regularization
• Overly complex family does not necessarily
include target function, true data
generating process, or even an
approximation
• Most deep learning applications are where true
data generating process is outside family
– Complex domains of images, audio sequences and
text true generation process may involve entire
universe
• Fitting square hole (data generating process) to round
hole (model family)
Deep Learning Srihari

What is the Best Model?

• Best fitting model obtained not by finding the

right number of parameters
• Instead, best fitting model is a large model that
has been regularized appropriately
• We review several strategies for how to create
such a large, deep regularized model
Deep Learning Srihari

Regularization Strategies
1. Parameter Norm Penalties
– (L2- and L1- regularization)
2. Norm Penalties as Constrained Optimization
3. Regularization and Under-
constrained Problems
4. Data Set Augmentation
5. Noise Robustness
 More Regularization
Deep Learning Srihari

Strategies
6. Semi-supervised learning
7. Multi-task learning
8. Early Stopping
9. Parameter tying and parameter sharing
10. Sparse representations
11. Bagging and other ensemble methods
12. Dropout
13. Adversarial training
14. Tangent methods
Deep Learning Srihari

Topics in Parameter Norm Penalties

1. Overview (limiting model capacity)

2. L2 parameter regularization
3. L1 regularization

3
Deep Learning Srihari

Limiting Model Capacity

• Regularization has been used for decades
prior to advent of deep learning
• Linear- and logistic-regression allow simple,
straightforward and effective regularization
strategies
– Adding a parameter norm penalty Ω(θ) to the
objective function J :
J!(;X,y ) = J(  ; X,y ) + ()
• where αε[0,θ) is a hyperparameter that weight the relative
contribution of the norm penalty term Ω
– Setting α to 0 results in no regularization. Larger values
correspond to more regularization 4
Deep Learning Srihari

Norm
Penalty
• When our training algorithm minimizes the
regularized objective function
J!(;X,y ) = J(  ; X,y ) + ()
– it will decrease both the original objective J on the
training data and some measure of the size of the
parameters θ
• Different choices of the parameter norm Ω can
result in different solutions preferred
– We discuss effects of various norms
5
 Deep Learning
No penalty for biases Srihari

• Norm penalty Ω penalizes only weights at each layer and leaves

biases unregularized
– Biases require less data to fit than weights
– Each weight specifies how variables interact(A weight (like wij​) defines
the strength of connection between input feature xj​ and output
neuron i.)
• Fitting weights requires observing both variables in a variety of conditions
• Each bias controls only a single variable
– We do not induce too much variance by leaving biases
unregularized
• w indicates all weights affected by norm penalty
• θ denotes both w and biases 6
Deep Learning Srihari

Different or Same αs for layers?

• Sometimes it is desirable to use a separate
penalty with a different α for each layer
J!(;X,y ) = J(  ; X,y ) + ()
• Invariance under linear transformation T is one
case
– i.e., we want neural net to perform the same when
the inputs are transformed

• But this creates too many hyperparameters

• Search space reduced by using same hyperparameters 7
Deep Learning Srihari

Linear Transformation T
• Consider a simple linear transformation of the
input

Two-variables
x and y
Three variables x,y and z

8
 Weight decay and
Deep Learning Srihari

• invariance
Suppose we train two 2-layer networks
– First network: trained using original data: x={xi}, y={yk}
– Second network: input and/or target variables are
transformed by one of the linear transformations
x i → x!i = axi + b yk → y!k = cyk + d

• Consistency requires that we should obtain

equivalent networks that differ only by linear
transformation of the weights

For first layer: And/or or second layer:

1 wk j → cwkj
wji → w
a ji
and/or
Deep Learning Srihari

Simple weight decay fails invariance

• Simple weight decay E!(w) = E(w) + α2 w w T

• Treats all weights and biases on equal footing

• While resulting wji and wkj should be treated differently
• Consequently networks will have different weights and
violate invariance
• We therefore look for a regularizer invariant
under the linear transformations
α1 α
– Such a regularizer is ∑
2 w∈W1
w2 + 2 ∑ w2
2 w∈W2
• where W are weights of first layer and
1

• W are the set of weights in the second layer

2

– This regularizer remains unchanged under the weight

transformations provided the parameters are rescaled using
λ → a1/2λ and λ 2 → c −1/2 λ 2
1 1
Deep Learning Srihari

Weight decay used in

practice
• Because it can be expensive to search for the
correct value of multiple hyperparameters, it is
still reasonable to use same weight decay at all
layers to reduce search space

11
Deep Learning Srihari

L2 parameter Regularization
• Simplest and most common kind
• Called Weight decay
• Drives weights closer to the origin
– by adding a regularization term () =
1
||w ||22
to the objectve function 2

• In other communities also known as ridge

regression or Tikhonov regularization

12
 Gradient of Regularized
Deep Learning Srihari

Objective
• Objective function (with no bias parameter)

J!(w;X,y) = wTw + J(w;X,y)
2
• Corresponding parameter
gradient  J!(w;X,y) = w +  J(w;X,y)
w w

• To perform single gradient step, perform update:

( (
w  w -  w +  w J w;X , y ))
• Written another way, the update is
(
w  (1−  )w -   w J w;X , y )
– We have modified learning rule to shrink w by
constant factor 1-εα at each step 13
Deep Learning Srihari

To study effect on entire

training
• Make quadratic approximation to the
objective function in the neighborhood of
minimal unregularized cost w*=arg minw J(w)
• The approximation is given by
J(w*)+½(w-w*)TH(w-w*)
• Where H is the Hessian matrix of J wrt w
evaluated at w*

14
Deep Learning Srihari

Effect of L2 regularization on optimal w

 J ( w; X,y)
J!(w;X,y) = wTw + J(w; X,y)
2

J ( w; X,y)

wTw
wTw

Along w1, eigen value of Hessian of J is small. Along w2, J is very sensitive to
J does not increase much when moving movements away from w*.
horizontally away from w*. Because J does not The corresponding eigenvalue is
have a strong preference along this direction, large, indicating high curvature.
the regularizer has a strong effect on this axis. As a result, weight decay affects the
The regularizer pulls w1 close to 0. position of w2 relatively little 15
Deep Learning Srihari

L1 Regularization
• L2 weight decay is common weight decay
• Other ways to penalize model parameter size
• L1 regularization is defined as
( ) = w =  w i
1
i 1

– which sums the absolute values of parameters

Image Source: [Link]

16
Deep Learning Srihari

Sparsity and Feature Selection

• The sparsity property induced by L1
regularization has been used extensively as a
feature selection mechanism
– Feature selection simplifies an ML problem by
choosing subset of available features
• LASSO (Least Absolute Shrinkage and
Selection Operator) integrates an L1 penalty with
a linear model and least squares cost function
– The L1 penalty causes a subset of the weights to
become zero, suggesting that those features can be
discarded
17
Deep Learning Srihari

Sparsity with Lasso constraint

• With q=1 and λ is sufficiently large, some of the coefficients wj
are driven to zero
• Leads to a sparse model
• – where corresponding basis functions play no role
• Origin of sparsity is illustrated here:
Quadratic solution where Minimization with Lasso Regularizer
w1* and w0* are nonzero A sparse solution with w1*=0

Contours of
Unregularized
Error function

Constraint
region

18
Using Quadratic Approximation of the
function

In simpler terms, it indicates that the function associated

with the Hessian is convex or has a minimum at a critical
point.
Deep Learning Srihari

Topics in Norm Penalty Optimization

1. Lagrangian formulation
2. KKT multiplier
3. Equivalence to norm penalty
4. Explicit constraints and Reprojection

3
Deep Learning Srihari

Constrained Optimization
• Consider the cost function regularized by a
norm penalty J ! (  ;X,y) = J (  ; X , y ) + ()
• Recall we can minimize a function subject to constraints
by constructing a generalized Lagrange function,
consisting of the original objective function plus a set of
penalties
• – Each penalty is a product between a coefficient called a
Karush-Kuhn-Tucker (KKT) multiplier and a function
representing whether constraint is satisfied

4
Deep Learning Srihari

Lagrange Formulation
• If we wanted to constrain Ω(θ) to be less than
some constant k, we could construct a
generalized Lagrange function
(
L(  ,  ;X,y) = J (  ; X , y ) +  () − k )
• The solution to the constrained problem is
given by  * = arg min max L ,
  , 0
( )
• Solving this problem requires modifying both θ
and α
– Many different procedures are possible 5
Deep Learning Srihari

Insight into effect of constraint

• We can fix α* and view the problem as just a
function of θ:
( )
 * = arg min L , * = arg minJ(  ;X,y) +  * ()
 

• This is exactly the same as the regularized

training problem of minimizing J ! (  ;X,y) = J(  ; X,y) + ()
• We can thus think of the parameter norm
penalty as imposing a constraint on the weights
6
Deep Learning Srihari

How α influences weights

• If Ω is L 2 norm
– weights are then constrained to lie in an L2 ball
• If Ω is the L 1 norm
– Weights are constrained to lie in a region of limited
L1 norm
• Usually we do not know size of constraint
region that we impose by using weight decay
with coefficient α* because the value of α* does
not directly tell us the value of k
– Larger α will result in smaller constraint region
7
– Smaller α will result in larger constraint region
Deep Learning Srihari

Reprojection
• Sometimes we may wish to use explicit
constraints rather than penalties
– We can modify SGD to take a step downhill on J(θ)
and then project θ back to the nearest point that
satisfies Ω(θ)<k
– This useful when we have an idea of what values of
k is appropriate and we do not want to spend time
searching for the value of α that corresponds to this
k
• Rationale for explicit constraints/Reprojection
1. Dead weights
8
2. Stability
Deep Learning Srihari

1. Eliminating dead weights

• A reason to use explicit constraints and
reprojection rather than enforcing constraints
with penalties:
– Penalties can cause nonconvex optimization
procedures to get stuck in local minima
corresponding to small θ
• This manifests as training with dead units
– Explicit constraints implemented by reprojection can
work much better because they do not encourage
weights to approach the origin
9
Deep Learning Srihari

2. Stability of Optimization
• Explicit constraints with reprojection can be
useful because these impose some stability
on the optimization procedure
• When using high learning rates, it is possible to
encounter a positive feedback learning loop in
which large weights induce large gradients,
which then induce a large update of the weights
– Can lead to numerical overflow
• Explicit constraints with reprojection prevent
this feedback loop from continuing to increase
magnitudes of weights without bound 10