Introduction

Next

Let’s use gradient descent to solve Linear Regression by using Linear Least Squares (LLS) in its cost function 𝐽(𝜃)

given sample/training data:

• (𝑦⁽¹⁾, 𝑥₁⁽¹⁾, …, 𝑥_𝑘⁽¹⁾) # sample 1
• (𝑦⁽²⁾, 𝑥₁⁽²⁾, …, 𝑥_𝑘⁽²⁾) # sample 2
• …
• (𝑦^(𝑛), 𝑥₁^(𝑛), …, 𝑥_𝑘^(𝑛)) # sample 𝑛

given inputs {𝑥₁, …, 𝑥_𝑘} and trained model parameters {𝜃₀, …, 𝜃_𝑘}, the predicted value 𝑦̂ is defined as (i.e. hypothesis):

• 𝐄{𝑌|𝑋₁=𝑥₁, …, 𝑋_𝑘=𝑥_𝑘} = ℎ(𝑥₁, …, 𝑥_𝑘) = 𝑦̂ = 𝜃₀+ 𝜃₁𝑓₁(𝑥₁, …, 𝑥_𝑘) + … + 𝜃_𝑘𝑓_𝑘(𝑥₁, …, 𝑥_𝑘)

Cost Function

the cost function of a single sample 𝑖:

• (1/2)[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)]²

the cost function of all samples:

• 𝐽(𝜃₀, …, 𝜃_𝑘) = (1/2𝑛)𝛴_{1≤𝑖≤𝑛}[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)]²

Goal

minimize 𝐽(𝜃₀, …, 𝜃_𝑘) with respect to the regression coefficients {𝜃₀, …, 𝜃_𝑘} using gradient descent

Gradient Descent

repeat until convergence:

• 𝜃₀← 𝜃₀- 𝛼·(1/𝑚)𝛴_{1≤𝑖≤𝑛}[[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)] · 𝑓₁(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖))]
• …
• 𝜃_𝑘← 𝜃_𝑘- 𝛼·(1/𝑚)𝛴_{1≤𝑖≤𝑛}[[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)] · 𝑓_𝑘(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖))]

derivation:

Click here to expand...

generic gradient descent algorithm:

repeat until convergence:

• • 𝜃₀← 𝜃₀- 𝛼·(𝛿/𝛿𝜃₀)𝐽(𝜃₀, …, 𝜃_𝑘)
  • …
  • 𝜃_𝑘← 𝜃_𝑘- 𝛼·(𝛿/𝛿𝜃_𝑘)𝐽(𝜃₀, …, 𝜃_𝑘)

taking the partial derivative of 𝐽(𝜃₀, …, 𝜃_𝑘) wrt to 𝜃_𝑖:

• (𝛿/𝛿𝜃_𝑖)𝐽(𝜃₀, …, 𝜃_𝑘) = (𝛿/𝛿𝜃_𝑖)(1/2𝑚)𝛴_{1≤𝑖≤𝑛}[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)]²
• (𝛿/𝛿𝜃_𝑖)𝐽(𝜃₀, …, 𝜃_𝑘) = (1/𝑚)𝛴_{1≤𝑖≤𝑛}[[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)] · (𝛿/𝛿𝜃_𝑖)ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖))]

modified gradient descent algorithm:

repeat until convergence:

• • 𝜃₀← 𝜃₀- 𝛼·(1/𝑚)𝛴_{1≤𝑖≤𝑛}[[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)] · (𝛿/𝛿𝜃₀)ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖))]
  • …
  • 𝜃_𝑘← 𝜃_𝑘- 𝛼·(1/𝑚)𝛴_{1≤𝑖≤𝑛}[[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)] · (𝛿/𝛿𝜃_𝑘)ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖))]

partial derivative of ℎ(𝑥₁, …, 𝑥_𝑘) wrt to 𝜃_𝑗:

• (𝛿/𝛿𝜃_𝑗)ℎ(𝑥₁, …, 𝑥_𝑘) = (𝛿/𝛿𝜃_𝑗) [𝜃₀+ 𝜃₁𝑓₁(𝑥₁, …, 𝑥_𝑘) + … + 𝜃_𝑘𝑓_𝑘(𝑥₁, …, 𝑥_𝑘)]
• (𝛿/𝛿𝜃_𝑗)ℎ(𝑥₁, …, 𝑥_𝑘) = 𝑓_𝑗(𝑥₁, …, 𝑥_𝑘)

FINAL modified gradient descent algorithm:

repeat until convergence:

• • 𝜃₀← 𝜃₀- 𝛼·(1/𝑚)𝛴_{1≤𝑖≤𝑛}[[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)] · 𝑓₁(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖))]
  • …
  • 𝜃_𝑘← 𝜃_𝑘- 𝛼·(1/𝑚)𝛴_{1≤𝑖≤𝑛}[[ℎ(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖)) - 𝑦^(𝑖)] · 𝑓_𝑘(𝑥₁^(𝑖), …, 𝑥_𝑘^(𝑖))]

Gradient Descent Variants

see Ascent Algorithms