Least Squares Fitting

Least Squares Fitting

Wanho Choi

(wanochoi.com)

Goals

키 - 체중 상관관계

강수량 - 생산량 상관관계

흡연기간 - 폐암발생률 상관관계

What We Want

Prediction

Problem Description

x

y

Given data that have some noise

Problem Description

x

y

y = ax + b

What is the best fitting line?

Problem Description

x

y

x

_i

y

_i

P(x

i

, y

i

)

y = ax + b

ax

_i

+ b

y

_i

− ax

_i

− b

Mathematical Formulation

y

_i

= ax

_i

+ b (i = 1,2,3,⋯, N)

Mathematical Formulation

y

_i

= ax

_i

+ b (i = 1,2,3,⋯, N)

Model:

Total Error:

_{E = 1} N N ∑ i=1 yi− axi− b

Mathematical Formulation

y

_i

= ax

_i

+ b (i = 1,2,3,⋯, N)

Model:

Total Error:

_{E = 1} N N ∑ i=1 yi− axi− b E = _∑N i=1 yi − axi− b : const. N

Mathematical Formulation

y

_i

= ax

_i

+ b (i = 1,2,3,⋯, N)

Model:

Total Error:

_{E = 1} N N ∑ i=1 yi− axi− b E = _∑N i=1 yi − axi− b : const. N E = N ∑ i=1 (yi − axi− b)2

Mathematical Formulation

y

_i

= ax

_i

+ b (i = 1,2,3,⋯, N)

Model:

Total Error:

_{E = 1} N N ∑ i=1 yi− axi− b E = _∑N i=1 yi − axi− b : const. N argmin a,b E

What we want:

We have to find & that make

a b

∂E

.

∂a

= ∂E

∂b

= 0

E = _∑N

i=1 (yi

Mathematical Formulation

y

_i

= ax

_i

+ b (i = 1,2,3,⋯, N)

Model:

Total Error:

_{E = 1} N N ∑ i=1 yi− axi− b E = _∑N i=1 yi − axi− b : const. N argmin a,b E

What we want:

We have to find & that make

a b

∂E

.

∂a

= ∂E

∂b

= 0

E = _∑N i=1 (yi − axi− b)2 ∂E ∂a = 2 N ∑ i=1 (yi − ax_{i− b) ⋅ (−xi}) = 0 ∂E ∂b = 2 N ∑ i=1 (yi − axi− b) ⋅ (−1) = 0

Mathematical Formulation

∂E ∂a = 2 N ∑ i=1 (yi − ax_{i− b) ⋅ (−xi}) = 0 ∂E ∂b = 2 N ∑ i=1 (yi − axi− b) ⋅ (−1) = 0 (− N ∑ i=1 xiyi₎+ a₍ N ∑ i=1 x2 i ₎+ b₍ N ∑ i=1 xi₎ = 0 (− N ∑ i=1 y_i )+ a( N ∑ i=1 x_i )+ bN = 0 a_(∑N i=1 x2 i ₎+ b₍ N ∑ i=1 xi₎ = ₍ N ∑ i=1 xiyi₎ a ( N ∑ i=1 x_i )+ bN = ( N ∑ i=1 y_i ) ∑N_i=1x2 i ∑N_i=1xi ∑N_i=1x_i N

[

a

b]

= ∑ N i=1xiyi ∑N_i=1y_i

Mathematical Formulation

∂E ∂a = 2 N ∑ i=1 (yi − ax_{i− b) ⋅ (−xi}) = 0 ∂E ∂b = 2 N ∑ i=1 (yi − axi− b) ⋅ (−1) = 0 (− N ∑ i=1 xiyi₎+ a₍ N ∑ i=1 x2 i ₎+ b₍ N ∑ i=1 xi₎ = 0 (− N ∑ i=1 y_i )+ a( N ∑ i=1 x_i )+ bN = 0 a_(∑N i=1 x2 i ₎+ b₍ N ∑ i=1 xi₎ = ₍ N ∑ i=1 xiyi₎ a ( N ∑ i=1 x_i )+ bN = ( N ∑ i=1 y_i ) ∑N_i=1x2 i ∑N_i=1xi ∑N_i=1x_i N

[

a

b]

= ∑ N i=1xiyi ∑N_i=1y_i

Ax

= b

How to solve Ax=b

•

Invert A

‣

Very expensive

•

Direct methods

‣

Gaussian elimination

‣

LU-factorization

‣

QR-factorizaiton

‣

Cholesky-factorization

‣

etc.

•

Iterative methods

‣

Jacobi method

‣

Gauss-Seidel

‣

Successive Over Relaxation (SOR)

‣

Steepest descent, (preconditioned) conjugate gradient

‣

etc.