*My notes from the Machine Learning Course provided by Andrew Ng on Coursera*

# Linear Regression with Multiple Variables

## Linear Regression for a single feature

`h_θ(x)=θ_0+θ_1 x`

## Linear Regression for multiple variables

`h_θ(x)=θ_0x_0+θ_1x_1+θ_2x_2+...+θ_nx_n`

where `x_0=1`

**Parameters**: `θ=\{θ_0,θ_1,θ_2,...,θ_n\} \in \R^{n+1}`

**Features**: `x=\{x_0,x_1,x_2,...,x_n\} \in \R^{n+1}`

### Notation:

`n`

– number of features`x^{(i)}`

– input (features) of`i^{th}`

training example`x_j^{(i)}`

– values of feature`j`

in`i^{th}`

training example

### Example:

Predict house price:

Size (`feet^2` ) |
No. of bedrooms | No. of floors | Age of house (years) | Price($1000) |
---|---|---|---|---|

`\textcolor{#c91862}{x_1}` |
`\textcolor{#c91862}{x_2}` |
`\textcolor{#c91862}{x_3}` |
`\textcolor{#c91862}{x_4}` |
`\textcolor{#c91862}{h_θ(x)=y}` |

2104 | 5 | 1 | 45 | 460 |

1416 | 3 | 2 | 40 | 232 |

1534 | 3 | 2 | 30 | 315 |

852 | 2 | 1 | 36 | 178 |

`n=4`

`x^{(i)}`

:

`x^{(2)}=\begin{bmatrix} 1416 \\ 3 \\ 2 \\ 40 \end{bmatrix}`

`x^{(4)}=\begin{bmatrix} 852 \\ 2 \\ 1 \\ 36 \end{bmatrix}`

*Vector is \R^n \Rightarrow \R^4*

`x_j^{(i)}`

:

`x_1^{(2)}=1416; x_2^{(2)}=3; x_3^{(2)}=2; x_4^{(2)}=40;`

`x_1^{(4)}=852; x_2^{(4)}=2; x_3^{(4)}=1; x_4^{(4)}=36;`

so hypothesis function will use like below:

`h_θ(x)=θ_0+2140 θ_1 + 5 θ_2 + θ_3 + 45 θ_4 = 460`

`h_θ(x)=θ_0+1416 θ_1 + 3 θ_2 + 2 θ_3 + 40 θ_4 = 232`

`h_θ(x)=θ_0+1534 θ_1 + 3 θ_2 + 2 θ_3 + 30 θ_4 = 315`

`h_θ(x)=θ_0+852 θ_1 + 2 θ_2 + θ_3 + 36 θ_4 = 178`

# Cost Function

`J(θ)=\frac{1}{2m} \displaystyle\sum_{i=1}^m (h_θ (x^{(i)})-y^{(i)})^2`

where

`(h_θ (x^{(i)})-y^{(i)})^2`

– Square Error of data `i`

`h_θ (x^{(i)})`

– Predicted value

`y^{(i)}`

– True value

The function is called *Mean Error Square (MSE)*

# Gradient Descent

Repeat {

`θ_j := θ_j - \alpha \frac{∂}{∂θ_j} J(θ)`

}

*(simultanously uptae for every j=0,...,n)*

## Pseudocode for gradient descent

1) `n=1`

(only one variable)

repeat until convergence {

`θ_0 := θ_0 - \alpha \frac{1}{m} \displaystyle\sum_{i=1}^m (h_θ (x^{(i)} )-y^{(i)})`

`θ_1 := θ_1 - \alpha \frac{1}{m} \displaystyle\sum_{i=1}^m (h_θ (x^{(i)} )-y^{(i)})x^{(i)}`

} simonously update `θ_0, θ_1`

2) `n\geqslant1`

repeat until convergence {

`θ_j := θ_j - \alpha \frac{1}{m} \displaystyle\sum_{i=1}^m (h_θ (x^{(i)} )-y^{(i)})x_j^{(i)}`

} simonously update `θ_j`

for `j = 0,...,n`

### Example for more than two features

`θ_0 := θ_0 - \alpha \frac{1}{m} \displaystyle\sum_{i=1}^m (h_θ (x^{(i)} )-y^{(i)})x_0^{(i)}`

and because`x_0^{(i)}=1`

this pseudocode for`θ_0`

parameter can be written:

`θ_0 := θ_0 - \alpha \frac{1}{m} \displaystyle\sum_{i=1}^m (h_θ (x^{(i)} )-y^{(i)})`

`θ_1 := θ_1 - \alpha \frac{1}{m} \displaystyle\sum_{i=1}^m (h_θ (x^{(i)} )-y^{(i)})x_1^{(i)}`

`θ_2 := θ_2 - \alpha \frac{1}{m} \displaystyle\sum_{i=1}^m (h_θ (x^{(i)} )-y^{(i)})x_2^{(i)}`

# Gradient Descent in Practice

Idea: Make sure features are on a similar scale, so gradient descent coverages fast

Example:

`x_1 =`

size (`0-2000 feet^2`

)

`x_2 =`

number of bedrooms (`1-5`

)

Problem:

The `x_1`

have a larger range of values than `x_2`

, so `J(θ)`

can write very skewed elliptical shape and gradient descent on this cost function may end up with a long time of execution.

## Feature Scaling

**Feature scaling** involves dividing the input values by the range (i.e. the maximum values minus the minimum value) of the input variable, resulting in a new range of just 1

`x_1 = \frac{size(feet^2)}{2000}`

`x_2 = \frac{no. of bedrooms}{5}`

new tange for this example:

`0 \leqslant x_1 \leqslant 1`

`0 \leqslant x_2 \leqslant 1`

The scale for the features should be approximately a `\textcolor{#c91862}{-1 \leqslant x_i \leqslant 1}`

range

## Mean Normalization

Replace `x_i`

with `x_1 - \mu_1`

to make features have approximetley zero mean (don’t do for `x_0=1`

)

Example:

`x_1 = \frac{size-1000}{2000}`

(where `average = 1000`

and `max=2000`

)

`x_2 = \frac{no. of bedrooms - 2}{5}`

(where `average = 2`

and `max = 5`

)

The new range is:

`-0.5 \leqslant x_1 \leqslant 0.5`

`-0.5 \leqslant x_2 \leqslant 0.5`

`x_i = \frac{x_i-\mu_i}{s_i}`

where `\mu_i =`

average of `x`

in training set and `s_i =`

range `(max - min)`

or standard derivation

# Learning Rate `\alpha`

## "Debugging" – how to make sure gradient descent is working correctly.

Plot min value of cost function after some number of iterations.

It’s difficult to tell how many iterations cost function need to coverage.

The function works correctly because `J(\theta)`

decrease after each iterration:

In below example, the function is flattened and (less or more) the function is coverage as a cost function

If `J(\theta)`

increasing, probably it should use smaller `\alpha`

### Automatic coverage test

Example: Declare coverage if `J(\theta)`

decreases by less then the small value * (10^{-3})* in one iteration.

### Summary

- for sufficiently small
`\alpha`

,`J(\theta)`

should decrease on each iteration - if
`\alpha`

is too small: slow coverage - if
`\alpha`

is too large:`J(\theta)`

may not decrease on every iteration; may not coverage - find best
`\alpha`

for speed + convergence by ploting different`\alpha`

values, e.g.`0.01, 0.03, 0.1, 0.3...`

# Features and Polynomial Regression

Understanding features can allow us to create a better model e.g. by combining them:

`x_1 = width`

`x_2 = depth`

`h_\theta(x)=\theta_0 + \theta_1 x_1 + \theta_2 x_2`

`\rightarrow`

combine to area

`area = width * depth`

`x = x_1 * x_2`

so

`h_\theta(x) = \theta_0 + \theta_1 x`

(using only one feature)

## Polynomial regression

Hypothesis function doesn’t need to be a straight line.

It can be polynomial by choosing features

The hypothesis function can change into quadratic, cubic or square root function (or any other form)

e.g.

hypothesis function: `h_\theta(x) = \theta_0 + \theta_1 x_1`

- create an additional feature based on
`x_1`

`h_\theta(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_1^2`

(quadratic function)

or

`h_\theta(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_1^2 + \theta_3 x_1^3`

(cubic function)

### The feature scaling is very important!

e.g. if `x_1`

has range `1-1000`

than range of `x_1^2`

becomes `1-100 000`

and `x_1^3`

becomes `1 - 100 000 000`

# Normal Equation

**Normal equation** – Method to solve `\theta`

analytically `\rightarrow`

finding the optimal value in just one go

Intuition: If `1D (\theta \in \R)`

Cost function: `J(\theta) = a\theta^2 + b\theta+c`

(quadratic function)

Solve for `minJ(\theta) \rArr (\theta_0, \theta_1, ..., \theta_n)`

- take the derivetives with respect to the
`\theta's`

and set them to 0 `\theta \in \R^{n+1}`

`J(\theta_0,\theta_1,...,\theta_m) = \frac{1}{2m}\displaystyle\sum_{i=1}^m (h_\theta (x^{(i)})-y^{(i)})^2`

`\frac{\partial}{\partial \theta_j} J(\theta) = ... = 0`

(for every `j`

)

Example: `m = 4`

(House price prediction)

Size (`feet^2` ) |
No. of bedrooms | No. of floors | Age of house (years) | Price($1000) |
---|---|---|---|---|

`\textcolor{green}{x_1}` |
`\textcolor{green}{x_2}` |
`\textcolor{green}{x_3}` |
`\textcolor{green}{x_4}` |
`\textcolor{green}{y}` |

2104 | 5 | 1 | 45 | 460 |

1416 | 3 | 2 | 40 | 232 |

1534 | 3 | 2 | 30 | 315 |

852 | 2 | 1 | 36 | 178 |

`\Darr`

Add extra column that corresponds to extra feature `x`

that always takes value of `1`

Size (`feet^2` ) |
No. of bedrooms | No. of floors | Age of house (years) | Price($1000) | |
---|---|---|---|---|---|

`\textcolor{#c91862}{x_0}` |
`\textcolor{green}{x_1}` |
`\textcolor{green}{x_2}` |
`\textcolor{green}{x_3}` |
`\textcolor{green}{x_4}` |
`\textcolor{green}{y}` |

`\textcolor{#c91862}{1}` |
2104 | 5 | 1 | 45 | 460 |

`\textcolor{#c91862}{1}` |
1416 | 3 | 2 | 40 | 232 |

`\textcolor{#c91862}{1}` |
1534 | 3 | 2 | 30 | 315 |

`\textcolor{#c91862}{1}` |
852 | 2 | 1 | 36 | 178 |

so:

note

a+b+c

`\underbrace{X}_{\text{features}} = \underbrace{\begin{bmatrix} 1 & 2104 & 5 & 1 & 45 \\ 1 & 1416 & 3 & 2 & 40 \\ 1 & 1534 & 3 & 2 & 30 \\ 1 & 852 & 2 & 1 & 36 \end{bmatrix}}_{\textcolor{#c91862}{\text{m x (n + 1)}}}`

`y = \underbrace{\begin{bmatrix} 460 \\ 232 \\ 315 \\ 178 \end{bmatrix}}_{\textcolor{#c91862}{\text{m - dimensional vector}}}`

Than:

`\theta = (X^TX)^{-1}X^Ty`

*(normal equation)*

In general case:

`m`

examples`(x^{(1)}, y^{(1)}), ... , (x^{(m)}, y^{(m)})`

`x^{(i)} = \underbrace{\begin{bmatrix} x_0^{(i)} \\ x_1^{(i)} \\ x_2^{(i)} \\ \vdots \\ x_n^{(i)} \end{bmatrix}}_{\textcolor{#c91862}{\text{vector of all features values in the example}}} \in \R^{n+1}`

Design matrix:

`X = \underbrace{\begin{bmatrix} --- & (x^{(1)})^T & --- \\ --- & (x^{(2)})^T & --- \\ \vdots \\ --- & (x^{(m)})^T & --- \\ \end{bmatrix}}_{\textcolor{#c91862}{\text{m x (n + 1)}}}`

E.g.

If `x^{(i)} = \begin{bmatrix} 1 \\ x_1^{(i)} \end{bmatrix}`

`X = \begin{bmatrix} 1 & x^{(1)} \\ 1 & x_2^{(1)} \\ \vdots \\ 1 & x_m^{(1)} \end{bmatrix}`

`\vec{y} = \begin{bmatrix} y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(m)} \end{bmatrix}`

`\theta = (X^TX)^{-1}X^Ty`

where:

`(X^TX)^{-1}`

– is inverse of matrix `X^TX`

*No need to do a feature scaling*

# Gradient Descent vs Normal Equation

for `m`

training examples and `n`

features

Gradient Descent | Normal Equation |
---|---|

Need to choose `\alpha` |
No need to choose `\alpha` |

Needs many iterations | Don’t need to iterate |

`\mathcal{O}(kn^2)` |
Need to compute `(X^TX)^{-1} \Rightarrow \mathcal{O}(n^3)` |

Works well even when `n` is large |
Slow if `n` is very large |

# What if `X^TX`

is non-invertible?

Non-invertible `X^TX`

:

- singular
- degenerate

If `X^TX`

is non-invertible – there are usually two common causes for this:

1) Redundant features (linear dependent)

E.g. `x_1 = \text{size in } feet^2`

`x_2 = \text{size in } m^2`

2) Too many features (e.g. `m \leqslant n`

)

delete features or use some regularization