07: Regularization

The problem of overfitting

• So far we've seen a few algorithms - work well for many applications, but can suffer from the problem of overfitting
• What is overfitting?
• What is regularization and how does it help

Overfitting with linear regression

• Using our house pricing example again
  • Fit a linear function to the data - not a great model
    • This is underfitting - also known as high bias
    • Bias is a historic/technical one - if we're fitting a straight line to the data we have a strong preconception that there should be a linear fit
      • In this case, this is not correct, but a straight line can't help being straight!
  • Fit a quadratic function
    • Works well
  • Fit a 4th order polynomial
    • Now curve fits through all five examples
      • Seems to do a good job fitting the training set
      • But, despite fitting the data we've provided very well, this is actually not such a good model
    • This is overfitting - also known as high variance
  • Algorithm has high variance
    • High variance - if fitting high order polynomial then the hypothesis can basically fit any data
    • Space of hypothesis is too large

• To recap, if we have too many features then the learned hypothesis may give a cost function of exactly zero
  • But this tries too hard to fit the training set
  • Fails to provide a general solution - unable to generalize (apply to new examples)

Overfitting with logistic regression

• Same thing can happen to logistic regression
  • Sigmoidal function is an underfit
  • But a high order polynomial gives an overfitting (high variance hypothesis)

Addressing overfitting

• Later we'll look at identifying when overfitting and underfitting is occurring
• Earlier we just plotted a higher order function - saw that it looks "too curvy"
  • Plotting hypothesis is one way to decide, but doesn't always work
  • Often have lots of features - here it's not just a case of selecting a degree polynomial, but also harder to plot the data and visualize to decide what features to keep and which to drop
  • If you have lots of features and little data - overfitting can be a problem
• How do we deal with this?
  • 1) Reduce number of features
    • Manually select which features to keep
    • Model selection algorithms are discussed later (good for reducing number of features)
    • But, in reducing the number of features we lose some information
      • Ideally select those features which minimize data loss, but even so, some info is lost
  • 2) Regularization
    • Keep all features, but reduce magnitude of parameters θ
    • Works well when we have a lot of features, each of which contributes a bit to predicting y

Cost function optimization for regularization

• Penalize and make some of the θ parameters really small
  • e.g. here θ₃ and θ₄

• The addition in blue is a modification of our cost function to help penalize θ₃ and θ₄
  • So here we end up with θ₃ and θ₄ being close to zero (because the constants are massive)
  • So we're basically left with a quadratic function

• In this example, we penalized two of the parameter values
  • More generally, regularization is as follows
• Regularization
  • Small values for parameters corresponds to a simpler hypothesis (you effectively get rid of some of the terms)
  • A simpler hypothesis is less prone to overfitting
• Another example
  • Have 100 features x₁, x₂, ..., x₁₀₀
  • Unlike the polynomial example, we don't know what are the high order terms
    • How do we pick the ones to shrink?
  • With regularization, take cost function and modify it to shrink all the parameters
    • Add a term at the end
      • This regularization term shrinks every parameter
      • By convention you don't penalize θ₀ - minimization is from θ₁ onwards

• In practice, if you include θ₀ it has little impact
• λ is the regularization parameter
  • Chapter 05 derives this penalty as MAP estimation with a Gaussian prior - "prefer small parameters", stated probabilistically
  • Controls a trade off between our two goals
    • 1) Want to fit the training set well
    • 2) Want to keep parameters small
• With our example, using the regularized objective (i.e. the cost function with the regularization term) you get a much smoother curve which fits the data and gives a much better hypothesis
  • If λ is very large we end up penalizing ALL the parameters (θ₁, θ₂ etc.) so all the parameters end up being close to zero
    • If this happens, it's like we got rid of all the terms in the hypothesis
      • The result here is then underfitting
    • So this hypothesis is too biased because of the absence of any parameters (effectively)
• So, λ should be chosen carefully - not too big...
  • We look at some automatic ways to select λ later in the course

Regularized linear regression

• Previously, we looked at two algorithms for linear regression
  • Gradient descent
  • Normal equation
• Our linear regression with regularization is shown below

import numpy as np

def J(theta, X, y, lam):
    m = len(y)
    err = ((X @ theta - y) ** 2).sum()
    penalty = lam * (theta[1:] ** 2).sum()   # theta[1:] - theta0 is not penalised
    return (err + penalty) / (2 * m)

• Previously, gradient descent would repeatedly update the parameters θ_j, where j = 0,1,2...n simultaneously
  • Shown below

• We've got the θ₀ update here shown explicitly
  • This is because for regularization we don't penalize θ₀ so treat it slightly differently
• How do we regularize these two rules?
  • Take the term and add λ/m * θ_j
    • Sum for every θ (i.e. j = 1 to n)
  • This gives regularization for gradient descent
• We can show using calculus that the equation given below is the partial derivative of the regularized J(θ)

• The update for θ_j
  • θ_j gets updated to
    • θ_j - α * [a big term which also depends on θ_j]
• So if you group the θ_j terms together

• The term
  $$(1-\alpha \frac{\lambda }{m})$$ Slightly less than 1, so each update shrinks θ_j a little before the usual gradient step.

  alpha, lam, m = 0.05, 10, 10
  1 - alpha * lam / m   # 0.95  : theta_j is multiplied by this every step
  
  alpha, lam, m = 0.01, 1, 10
  1 - alpha * lam / m   # 0.999 : closer to 1 for gentler regularization

  The shrink factor for two settings — every update scales θ_j by a number just under 1 before the usual gradient step.

  • Is going to be a number less than 1 usually
  • Usually learning rate is small and m is large
    • So this typically evaluates to (1 - a small number)
    • So the term is often around 0.99 to 0.95
• This in effect means θ_j gets multiplied by 0.99
  • Means the squared norm of θ_j gets a little smaller
  • The second term is exactly the same as the original gradient descent

Regularization with the normal equation

• Normal equation is the other linear regression model
  • Minimize the J(θ) using the normal equation
  • To use regularization we add a term (+ λ [n+1 x n+1]) to the equation
    • [n+1 x n+1] is the identity matrix with the top-left entry set to 0 — so θ₀ escapes the penalty, as everywhere else in this chapter

X = np.array([[1, 2, 2],   # x2 is an exact copy of x1,
              [1, 3, 3],   # so X.T @ X is singular
              [1, 4, 4],
              [1, 5, 5]], dtype=float)
y = np.array([2, 3, 4, 5], dtype=float)

np.linalg.det(X.T @ X)   # 0.0 - not invertible

L = np.eye(3)
L[0, 0] = 0              # the modified identity from the equation above
theta = np.linalg.solve(X.T @ X + 1.0 * L, X.T @ y)
X @ theta                # [2.14, 3.05, 3.95, 4.86]  - a sensible fit anyway

Regularization for logistic regression

• We saw earlier that logistic regression can be prone to overfitting with lots of features
• Logistic regression cost function is as follows;

• To modify it we have to add an extra term
  $$+\frac{\lambda }{2m}\sum _{j=1}^n{\theta }_j^2$$
• This has the effect of penalizing the parameters θ₁, θ₂ up to θ_n
  • Means, like with linear regression, we can get what appears to be a better fitting lower order hypothesis
• How do we implement this?
  • Original logistic regression with gradient descent function was as follows
    $${\theta }_j≔{\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m\left(h_{\theta }\right(x^{\left(i\right)})-y^{\left(i\right)})x_j^{\left(i\right)}$$ j = 0, 1, 2, 3, …, n
• Again, to modify the algorithm we simply need to modify the update rule for θ₁, onwards
  • Looks cosmetically the same as linear regression, except obviously the hypothesis is very different
    $${\theta }_j≔{\theta }_j(1-\alpha \frac{\lambda }{m})-\alpha \frac{1}{m}\sum _{i=1}^m\left(h_{\theta }\right(x^{\left(i\right)})-y^{\left(i\right)})x_j^{\left(i\right)}$$ Cosmetically the same as regularised linear regression — but h_θ(x) is the sigmoid here, so it is a different algorithm.

Advanced optimization of regularized linear regression

• As before, define a cost_function which takes a θ parameter and gives jVal and gradient back

def cost_function(theta):

    jVal = [code to compute $J\left(\theta \right)$];

    gradient[0] = [code to compute $\frac{\partial }{\partial {\theta }_0}J\left(\theta \right)$];

    gradient[1] = [code to compute $\frac{\partial }{\partial {\theta }_1}J\left(\theta \right)$];

    gradient[2] = [code to compute $\frac{\partial }{\partial {\theta }_2}J\left(\theta \right)$];
    $⋮$
    gradient[n] = [code to compute $\frac{\partial }{\partial {\theta }_n}J\left(\theta \right)$];

• use scipy.optimize.minimize
  • Pass it the cost_function object
  • Minimizes in an optimized manner using the cost function
• jVal
  • Need code to compute J(θ)
    • Need to include regularization term
• Gradient
  • Needs to be the partial derivative of J(θ) with respect to θ_i
  • Adding the appropriate term here is also necessary

def cost_function(theta):

    jVal = [code to compute $J\left(\theta \right)$];
      $J\left(\theta \right)=-\frac{1}{m}\left[\sum _{i=1}^m{y}^{\left(i\right)}\log h_{\theta }\right(x^{\left(i\right)})+(1-y^{\left(i\right)}\left)\log \right(1-h_{\theta }\left(x^{\left(i\right)}\right)\left)\right]+\frac{\lambda }{2m}\sum _{j=1}^n{\theta }_j^2$

    gradient[0] = [code to compute $\frac{\partial }{\partial {\theta }_0}J\left(\theta \right)$];
      $\frac{1}{m}\sum _{i=1}^m\left(h_{\theta }\right(x^{\left(i\right)})-y^{\left(i\right)})x_0^{\left(i\right)}$

    gradient[1] = [code to compute $\frac{\partial }{\partial {\theta }_1}J\left(\theta \right)$];
      $\frac{1}{m}\sum _{i=1}^m\left(h_{\theta }\right(x^{\left(i\right)})-y^{\left(i\right)})x_1^{\left(i\right)}+\frac{\lambda }{m}{\theta }_1$

    gradient[2] = [code to compute $\frac{\partial }{\partial {\theta }_2}J\left(\theta \right)$];
      $\frac{1}{m}\sum _{i=1}^m\left(h_{\theta }\right(x^{\left(i\right)})-y^{\left(i\right)})x_2^{\left(i\right)}+\frac{\lambda }{m}{\theta }_2$
    $⋮$
    gradient[n] = [code to compute $\frac{\partial }{\partial {\theta }_n}J\left(\theta \right)$];

• Ensure summation doesn't extend to the lambda term!
  • It doesn't, but, you know, don't be daft!