Main Procedure

hypothesis

a function that maps input to output

Univariate linear regression

$h_\theta(x) = \theta_0 + \theta_1x$hθ​(x)=θ0​+θ1​x

Cost function

Idea

Choose $\theta$θ so that $h_\theta(x)$hθ​(x) is close to y for our training examples (x,y).
To fit the function to training data => To minimized the cost function
To minimize the square difference between the hypothesis and the actual value

Cost function for Univariate linear regression

Gradient Descent

An algorithm for minimizing the cost function.

Intuition: contour plot for $J(\theta)$J(θ)

To minimize as quickly as possible

Outline

1. Start with some $\theta_0$θ0​, $\theta_1$θ1​ (Random Initialize)
2. Keep changing $\theta_0$θ0​, $\theta_1$θ1​ to reduce $J(\theta_0, \theta_1)$J(θ0​,θ1​) until end up at minimum (Although sensitive of local mini, usually get global mini)

Algorithm: To minimize as quickly as possible

Repeat util convergence{

}
NOTE: All the parameter $\theta_i$θi​ should be update simultaneously.

$\alpha$α: learning rate

Need to choose carefully.

• Too small: gradient descent can be slow
• Too large: it can be overshoot the minimum. It may be fail to converge, or even diverge

Gradient descent can converge to a local minimum, even with learning rate a fixed
As we approach a local minimum, gradient descent will automatically take smaller steps(because the partial derivative will become smaller). So there is no need to decrease $\alpha$α overtime.

Gradient Descent for Univariate Linear Regression

Problem: susceptible to local optima
It’s okay because the cost function for linear regression is a convex function

Batch Gradient Descent

Each step uses all the training examples.