Least Squres

Posted 2011.10.26 23:16

 매우 직관적인 방법이다. 주어진 데이터 x[n]을 우리가 임의로 선정한 s[n]에 맞추는 것이다. 
 Θ를 파라미터라고 할 때 s[n] = HΘ이다. 이 때 H는 알고 있다고 한다. 
 
 J(Θ) = SUM(x[n]-s[n])^2 을 최소화하는 Θ를 구한다. 
 Θ_hat = inv(H'WH)H'x 이다. 이를 푸는 것을 normal equation을 푼다고 한다. 

출처: http://poucotm.egloos.com/5872003
Part 1의 내용에 이어서 ...
 
Vector 간 거리를 구하는 것이   ( x1 - x2 )^2 + ( y1 - y2 )^2 임을 상기하면 유사하다는 것을 알  수 있을 것이다.
이제 보다 확장할 것이다. Part 1의 마지막 그림에서 Vector a 의 line은 Column Space로 확장되고 해당 column 들을 갖고 있는 Matrix A 로 다뤄진다. 여기서 Column Space란 Matrix의 각 Column 들의 Linear Combination 에 의해 만들어진 공간을 의미한다. 또한 Linear Combination이란 각 Vector들에 Scalar 값을 곱하고 더해서 조합시키는 것이다. 다음 식을 보자.

 
c1, c2 는 임의의 Scalar 값이다. 여기서 Matrix A 는 3 x 2 행렬이다.
 
이제 Part 1 에서의 그림처럼 표현해보자.

(와 역시 뽀대가 다르다. *.* Visio 로 그렸다.)
 
Column Space인 Matrix A 의 column 들에 의해 만들어진 공간은 2 차원이다. 여기서 LSS(Least Squares Solution)은 Vector b 와 column space 간 거리가 가장 짧은 포인트를 만드는 해 x~ 이다. Part 1 에서와 달리 여기서 x~ 은 2 차원 Vector 값(특정 c1, c2 포인트)이다. 또한 다음 식처럼 쓸 수 있는데, Column Spcae에 수직한다는 얘기는 Column Space 안의 모든 Vector와 수직이 된다는 얘기이다.
... (5)
여기서 0 은 Scalar 값 0 이아니라 0 Vector 이다.
 
아참 주의할 것은 두 개의 column 1, 2 는 서로 linearly independent 해야하는데, 이 선형적 독립이란, 하나의 Vector에 어떤 Scalar 값을 곱하여 다른 Vector와 같게 만들지 못한다는 얘기다. 만약에 만들수 있다면 dependent 한 것이고 위의 경우 처럼 Column Space를 2차원 평면으로 만들 수가 없다. 또한 Matrix A 는 임의의 m x n Matrix 여도 된다. 3 x 2 는 예시를 위함이다. 그리고 Ax~ 은 Vector b를 column space에 Projection(사영)한 Vector 라 불린다.
 
이제 식(5)를 정리한 LSS(Least Squares Solution)의 일반형을 적는다. (번역하지 않고 책을 그대로 옮긴다.)
 
The least squares solution to an inconsistent system Ax = b of m equations in n unknowns satisfies
 
 
If the column space of A are linearly independent, then ATA is invertible and
 
 
The projection of b onto the column space is therefore
 
 
M^(-1) 은 Inverse Matrix 이다. 즉,
그리고 I 는 Identity Matrix 로 MI = IM = M 이다.
 
주의할 것은 Matrix A 의 Column 들이 Linearly Independent 해야한다는 것이다. 만약에 m x n 에서 m < n 이라면 Column 들은 선형적 독립이 되지 않는다. 때문에 ATA 의 Invert 는 존재하지 않는다. (Appendix에서 추가 언급)
 
처음에 언급한 것이있다. 턱 선 추출. MATLAB 과 함께 살펴보자. MATLAB은 기본적으로 행렬로 모든 계산을 다룬다. -0-
 
우선 당신의 얼굴을 디카로 찍고 턱부분만 보자.


(이쁘다 *.*)
검은 점들은 턱 선을 따라서 찍은 점들이고 LSS를 구하기 위한 Sample 들이된다.
 
우리는 ax^2 + bx + c = y 의 식에서 그림의 턱을 근사화할 a, b, c 값을 정하는 게 목표다. 사실 c 값은 위아래 높이를 지정해주는 상수이고 턱의 모양, 굴곡 등의 특징은 a, b 값에 의해 결정된다. 우리는 Sample 들에서 다음을 얻을 수 있다.
 
Sample Point 1 (28, 49) => a ( 28 ^2 ) + b (28) + c = 49
Sample Point 2 (46, 82) => a ( 46 ^2 ) + b (46) + c = 82
Sample Point 3 (62, 110) => a ( 62 ^2 ) + b (62) + c = 110
...
 
여기서 Ax = b 는 다음과 같이 된다.
이걸 위에서 구한 LSS의 일반형에 대입만 시키면 된다. -0-
 
다음은 위에서 LSS를 구하기 위하여 Coding한 MATLAB Code 이다.
 
% Least Squares Solution (2nd order)
%                        coded by chani(=sunlet, poucotm) @ 2002.11
 
function [a, b, c ] = SecondOrderLSS(column, b)
 
b = b';
A = [column.^2; column; ones(1, length(column))]';
INV_ATA = inv(A' * A);
X_ = INV_ATA * A' * b;
 
a = X_(1,1);
b = X_(2,1);
c = X_(3,1);
 
우와 간단하다. -0- 음 여기서 MATLAB Code 를 설명하기는 ... 알아서 Study ... (__);;;
 
결과만 함 보자 :-) 컴퓨터 좌표계는 위쪽이 0 이니 끙.. Code에서 - 를 붙였다.
 
다음은 Test를 위한 Code 와 Plotting 한 그림이다.
 
function test
 
samples = [
28 -49
46 -82
62 -110
90 -134
130 -144
174 -128
203 -99
226 -73
241 -36
];
 
[a b c ] = SecondOrderLSS(samples(:,1)', samples(:,2)');
x = 0:250;
plot(samples(:,1), samples(:,2), 'b'); hold on;
y = a * x.^2 + b * x + c;
plot(x, y, 'r'); hold off;
grid;
 


그림에서 파란선은 Sample 들을 이어놓은 것이고 빨간선은 Approximation에 의한 그래프이다.
 
구한 a, b, c 값은 다음과 같다.
 
a = 0.0089
b = -2.3382
c = 6.1358
 
 재미있었길 ... 
 
 
 
Appendix
 
 
  ==> if A has linearly independent columns, then ATA is square, symmetric and invertible
 
 

'Enginius > Machine Learning' 카테고리의 다른 글

Interpolation  (0) 2011.11.01
Gmail Priority Inbox 알고리즘에서 배우는 실전 기계학습  (0) 2011.11.01
Least Squres  (2) 2011.10.26
퍼셉트론 패턴인식 데모  (0) 2011.10.25
Introduction to Pattern Recognition  (0) 2011.10.25
Expectation of X^n; X~N(u,sigma^2)  (0) 2011.10.24
« PREV : 1 : ··· : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : ··· : 142 : NEXT »