Solving the problem of overfitting / underfitting

This is my personal notes taken for the course Machine learning by Standford. Feel free to check the assignments.
Also, if you want to read my other notes, feel free to check them at my blog.

I) Introduction

Consider the problem of predicting

$y$ from

$x\in \mathbb{R}$.

1. The leftmost picture shows the result of
   $h(x)={\theta }_0+{\theta }_1{x}_1$. You can notice that the line doesn't fit well the plotted data. This is called
   underfitting or high bias.
2. The middle pictures show the result of
   $h(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2^2$. It seems to be a very good curve.
3. The rightmost picture shows the result of
   $h(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2^2+{\theta }_3{x}_3^3+{\theta }_4{x}_4^4$. It might seem that the more features we add, the better the curve will be. You can notice here that the curve passes through the plotted data perfectly. However, there is a danger. Adding to much features can lead to a curve that fits perfectly the plotted data but will give poor prediction. This is called overfitting or high variance.

Think of it like this. There are 3 students doing the same MCQ. The first student is the one that didn't revise enough (leftmost). The second student is the one that understand his course and can adapt to every type of MCQ (middle one). The last student is the one that learned by hearth all the annals of previous MCQ (rightmost). He may do well for this particular MCQ but will fail if we change the question. "Overfitting" and "underfitting" apply to both linear and logistic regression.

To get out of underfitting, you have to add more features (polynomials).

To get out of overfitting, there are 2 mains options:

1. Reduce the number of features:

   • Manually select which features to keep.
   • Use a model selection algorithm.

2. Regularization:

   • Keep all the features, but reduce the magnitude of parameters
     $\theta$.
   • Regularization works well when we have a lot of slightly useful features.

Modifying the cost function

Suppose we want to make our following hypothesis function

$h(x)$ more
quadratic:

$$h(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2^2+{\theta }_3{x}_3^3+{\theta }_4{x}_4^4$$

We'll want to eliminate the influence of

${\theta }_3{x}^3$ and

${\theta }_4{x}^4$. Without actually getting rid of these features or changing the form of our hypothesis, we can instead modify our cost function:

$$mi{n}_{\theta }\frac{1}{2m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)}{)}^2+\underset{\text{regularization term}}{\underbrace{1000\ast {\theta }_3^2+1000\ast {\theta }_4^2}}$$

Why are we adding up

$1000\ast {\theta }_3^2$ and

$1000\ast {\theta }_4^2$ to the initial

$J(\mathrm{\Theta })$? Well, remember that our goal is to minimize

$J(\mathrm{\Theta })$. That means finding best value of

$\theta$s so that

$J(\mathrm{\Theta })$ is near as much as possible to 0.

Thus adding extra values will require

$J(\mathrm{\Theta })$ to find smallest values of

$\theta$s

In our case, the two extra term inflate the cost of

${\theta }_3$ and

${\theta }_4$. Now, in order for the cost function to get close to zero, we will have to reduce the values of

${\theta }_3$ and

${\theta }_4$ to near zero. This will in turn greatly reduce the values of

${\theta }_3{x}^3$ and

${\theta }_4{x}^4$ in our hypothesis function.

Multiply

$1000$ by

${\theta }_3^2$ and

${\theta }_4^2$ enable us to know when

${\theta }_3$ and

${\theta }_4$ are near 0 since the regularization term will disappear. If we didn't multiply by

${\theta }_3^2$ and

${\theta }_4^2$, it means that the regularization term will always be there, forcing

${\theta }_1$ and

${\theta }_2$ to have values they should normally not take.

If you are wondering why we are regularizing with

${\theta }_3^2$ and

${\theta }_4^2$ instead of

${\theta }_3$ and

${\theta }_4$, here is the answer:

Suppose

${\theta }_3=+1000000$ and

${\theta }_4=-1000001$.

• $sum(\theta )=+1000000-1000001=-1$ which is small.
• $sum({\theta }^2)=([phone]\mathrm{}{}^{\mathrm{}}+(-1000001{)}^2$ will be very big.

Thus, as you have noticed, using

$sum(\theta )$ comes down to not regularizing at all.

A general formula will be:

$$\boxed{{\displaystyle mi{n}_{\theta }\frac{1}{2m}[\sum _{i=1}^m(h(x^{(i)})-y^{(i)}{)}^2+\underset{\text{regularization term}}{\underbrace{\lambda \sum _{j=1}^m{\theta }_j^2]}}}}$$

Notice that we are not regularizing

${\theta }_0$ (summation start at index 1).

The

$\lambda$ is the regularization parameter: the bigger

$\lambda$ is, the smaller the concerning

$\theta$s will be.

However, if

$\lambda$ is too large (

$\lambda ={10}^{10}$), all the

$\theta$s will be too small (near 0) and we will be left with

$h(x)={\theta }_0$ (underfitting problem).

II) Regularized Linear Regression

In order to build a regularized linear regression, we have to tweak the gradient descent algorithm. The original one looked like this :

$$\begin{array}{rl}& \text{repeat until convergence:}\{\\ & {\theta }_0:={\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})\cdot x_0^{(i)}\\ & \cdots \\ & {\theta }_j:={\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})\cdot x_j^{(i)}& \\ \}\end{array}$$

Nothing new, right? The derivative at this point has already been computed and we plugged it into the formula. In order to upgrade this into a regularized algorithm, we have to figure out the derivative for the new regularized cost function seen above. This is how it looks after computing the derivative.

$$\frac{\partial }{\partial {\theta }_j}{J}_{reg}(\mathrm{\Theta })=\frac{1}{m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})\cdot x_j^{(i)}+\frac{\lambda }{m}{\theta }_j$$

Bonus:

Let's compute

$\frac{\partial }{\partial {\theta }_j}{J}_{reg}(\mathrm{\Theta })$.

$$J(\mathrm{\Theta })=\frac{1}{2m}[\sum _{i=1}^m(h(x^{(i)})-y^{(i)}{)}^2+\lambda \sum _{j=1}^m{\theta }_j^2]$$

Thus,

$$\begin{array}{rl}\frac{\partial }{\partial {\theta }_j}J& =\underset{\text{compute in "Linear Regression (one variable)"}}{\underbrace{\frac{\partial }{\partial {\theta }_j}(\frac{1}{2m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)}{)}^2)}}+\frac{\partial }{\partial {\theta }_j}(\frac{1}{2m}\lambda \sum _{j=1}^m{\theta }_j^2)\\ & =\frac{1}{m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})\cdot x_j^{(i)}+\frac{\lambda }{m}{\theta }_j\end{array}$$

Notice: That's why we squared

$\theta$ in the regularization term because we are going to differentiate it in the gradient descent algorithm. If we didn't square it, it will disappear while differentiating (showing that the

$\theta$s not raise to the square are too small when adding up).

And now we are ready to plug it into the gradient descent algorithm. Note how the first

${\theta }_0$ is left unprocessed, as we said earlier:

$$\begin{array}{rl}& \text{repeat until convergence:}\{\\ & {\theta }_0:={\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})\cdot x_0^{(i)}\\ & \cdots \\ & {\theta }_j:={\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})\cdot x_j^{(i)}+\frac{\lambda }{m}{\theta }_j& \\ \}\end{array}$$

We can do even better. Let's group all the terms together that depends on

${\theta }_j$ (and

${\theta }_0$ left untouched as always):

$$\begin{array}{rl}& \text{repeat until convergence:}\{\\ & {\theta }_0:={\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})\cdot x_0^{(i)}\\ & \cdots \\ & {\theta }_j:={\theta }_j(1-\alpha \frac{\lambda }{m})-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})\cdot x_j^{(i)}& \\ \}\end{array}$$

I have simply rearranged things around in each

${\theta }_j$ update, except for

${\theta }_0$. This alternate way of writing shows the regularization in action: as you may see, the term

$(1-\alpha \frac{\lambda }{m})$ multiplies

${\theta }_j$ and it's responsible for its shrinkage (because it will be always

$<$ 1). The rest of the equation is the same as before the whole regularization thing.

Normal equation:

Now let's approach regularization using the alternate method of the non-iterative normal equation.
To add in regularization, the equation is the same as our riginal, except that we add another term inside the parentheses:

$$\begin{array}{rl}& \theta ={(X^{T}X+\lambda \cdot L)}^{-1}{X}^{T}y\text{where}L=\left[\begin{array}{cccccc}0& & & & & \\ & 1& & & & \\ & & 1& & & \\ & & & \cdot & & \\ & & & & \cdot & \\ & & & & & 1& \end{array}\right]\end{array}$$

$L$ is a matrix with

$\theta$ at the top left and

$1$'s down the diagonal, with

$0$'s everywhere else. It should have dimension

$(n+1)\times (n+1)$. Intuitively, this is the identity matrix (though we are not including

$x_0$), multiplied with a single real number

$\lambda$.

Recall that if

$m\le n$ (

$m$ : number of training examples and

$n$ : number of features), then

$X^{T}X$ is non-invertible. However, when we add the term λ⋅L, then

$X^{T}X+\lambda \cdot L$ becomes invertible.

III) Regularized Logistic Regression

The gradient descent algorithm for logistic regression looks identical to the linear regression one. So the good news is that we can apply the very same regularization trick as we did above in order to shrink the

$\theta$s parameters.

The original, non-regularized cost function for logistic regression looks like:

$$J(\mathrm{\Theta })=-{\displaystyle \frac{1}{m}}[\sum _{i=1}^m{y}^{(i)}\log (h(x^{(i)}))+(1-y^{(i)})\log (1-h(x^{(i)}))]$$

As we did in the regularized linear regression, we have to add the regularization term that shrinks all the parameters. It is slightly different here:

$$J_{reg}(\mathrm{\Theta })=-{\displaystyle \frac{1}{m}}[\sum _{i=1}^m{y}^{(i)}\log (h(x^{(i)}))+(1-y^{(i)})\log (1-h(x^{(i)}))]+\frac{\lambda }{2m}\sum _{j=1}^n{\theta }_j^2$$

Thus, its derivative is:

$$\frac{\partial }{\partial {\theta }_j}{J}_{reg}(\theta )={\theta }_j-\alpha [{\displaystyle \frac{1}{m}}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda }{m}{\theta }_j]$$

We are now ready to plug it into the gradient descent algorithm for the logistic regression. As always the first item

${\theta }_0$ is left unprocessed:

$$\begin{array}{rl}& \text{repeat until convergence:}\{\\ & {\theta }_0:={\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})x_0^{(i)}\\ & \cdots \\ & {\theta }_j:={\theta }_j-\alpha [{\displaystyle \frac{1}{m}}\sum _{i=1}^m(h(x^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda }{m}{\theta }_j]& \\ \}\end{array}$$