Least Squares Fitting

전체 글

(1)

Least Squares Fitting

Wanho Choi

(wanochoi.com)

(2)

Goals

키 - 체중 상관관계

강수량 - 생산량 상관관계

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

(3)

What We Want

Prediction

(4)
(5)
(6)
(7)
(8)

Problem Description

x

y

Given data that have some noise

(9)

Problem Description

x

y

y = ax + b

What is the best fitting line?

(10)

Problem Description

x

y

x

i

y

i

P(x

i

, y

i

)

y = ax + b

ax

i

+ b

y

i

− ax

i

− b

(11)
(12)

Mathematical Formulation

y

i

= ax

i

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

(13)

Mathematical Formulation

y

i

= ax

i

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

Model:

Total Error:

E = 1 N Ni=1 yi− axi− b

(14)

Mathematical Formulation

y

i

= ax

i

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

Model:

Total Error:

E = 1 N Ni=1 yi− axi− b E = N i=1 yi − axi− b : const. N

(15)

Mathematical Formulation

y

i

= ax

i

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

Model:

Total Error:

E = 1 N Ni=1 yi− axi− b E = N i=1 yi − axi− b : const. N E = Ni=1 (yi − axi− b)2

(16)

Mathematical Formulation

y

i

= ax

i

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

Model:

Total Error:

E = 1 N Ni=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

(17)

Mathematical Formulation

y

i

= ax

i

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

Model:

Total Error:

E = 1 N Ni=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 Ni=1 (yi − axi− b) ⋅ (−xi) = 0 ∂E ∂b = 2 Ni=1 (yi − axi− b) ⋅ (−1) = 0

(18)

Mathematical Formulation

∂E ∂a = 2 Ni=1 (yi − axi− b) ⋅ (−xi) = 0 ∂E ∂b = 2 Ni=1 (yi − axi− b) ⋅ (−1) = 0 (− Ni=1 xiyi)+ a( Ni=1 x2 i )+ b( Ni=1 xi) = 0 (− Ni=1 yi )+ a( Ni=1 xi )+ bN = 0 a(N i=1 x2 i )+ b( Ni=1 xi) = ( Ni=1 xiyi) a ( Ni=1 xi )+ bN = ( Ni=1 yi ) ∑Ni=1x2 iNi=1xiNi=1xi N

[

a

b]

= ∑ N i=1xiyiNi=1yi

(19)

Mathematical Formulation

∂E ∂a = 2 Ni=1 (yi − axi− b) ⋅ (−xi) = 0 ∂E ∂b = 2 Ni=1 (yi − axi− b) ⋅ (−1) = 0 (− Ni=1 xiyi)+ a( Ni=1 x2 i )+ b( Ni=1 xi) = 0 (− Ni=1 yi )+ a( Ni=1 xi )+ bN = 0 a(N i=1 x2 i )+ b( Ni=1 xi) = ( Ni=1 xiyi) a ( Ni=1 xi )+ bN = ( Ni=1 yi ) ∑Ni=1x2 iNi=1xiNi=1xi N

[

a

b]

= ∑ N i=1xiyiNi=1yi

Ax

= b

(20)

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.

(21)

수치

Updating...

참조

  1. wanochoi.com)
관련 주제 :