최소자승법 이해와 다양한 활용예 (Least Square Method)

한글로 최소자승법 또는 최소제곱법, 영어로는 LSM(Least Square Method) 또는 LMS(Least Mean Square) 방법.

최소자승법 하면 흔히 어떤 점들의 분포를 직선이나 곡선으로 근사하는 것만을 생각하기 쉽습니다. 하지만, 최소자승법은 일반적인 수학적 도구(tool)로서 수치해석, 회귀분석 뿐만 아니라 영상처리 분야에서도 다양하게 활용될 수 있습니다.

이 글에서는 최소자승법이 어떻게 실제 다양한 문제에 활용될 수 있는지, 그리고 계산은 어떻게 하면 되는지 몇몇 구체적 예를 통해 하나씩 살펴보도록 하겠습니다. 그래서 궁극적으로는 이 글을 읽는 분들이 자신의 문제에 최소자승법을 보다 잘 활용할 수 있기를 바래 봅니다. 최소자승법을 잘만 활용할 수 있어도 연구개발에 있어 강력한 무기(?) 하나를 갖게 되는 셈입니다 ^^

1. 최소자승법의 이해

2. 최소자승법의 계산

3. 최소자승법의 활용

4. 최소자승법의 한계

최소자승법을 활용할 수 있으려면 먼저 최소자승법이 어떤 것인지 알고 있어야 할 것입니다.

1. 최소자승법의 이해

조금 딱딱한 표현이긴 하지만 최소자승법(Least Square Method)은 '어떤 모델의 파라미터를 구하는 한 방법으로서, 데이터와의 residual²의 합을 최소화하도록 모델의 파라미터를 구하는 방법'을 지칭한다.

모델, 파라미터, 데이터, residual(레지듀얼), ...

이런 단어 하나 하나들이 그대로 이해되면서 머리속으로 하나의 그림이 그려진다면 굳이 최소자승법의 이해 파트는 읽을 필요가 없을 것이다 ^^.

어쨌든, 이렇게 말하면 얼른 감이 안오기 때문에, 이들 단어가, 그리고 최소자승법이 어떤 의미인지 예를 통해 설명해 보자.

보통 블로그를 운영하면서 가장 신경쓰이는 것 중의 하나가 일일 방문객 수이며, 방문객 수를 늘이기 위해 참으로 눈물겨운 노력들을 한다. 그래서 방문객 수의 추세를 알아보기 위해 아래 그림과 같이 날짜별 블로그 방문객 수를 그래프로 그려 보았다고 하자.

x축은 블로그를 개설한 후 경과 일수고 y축은 일자별 방문객 수이다. 그래프에서 각각의 점들이 관측된 데이터 (x, y)이다.

내 블로그 방문객 수는 어떤 분포를 따르는 것일까? 위 데이터의 분포를 보면 일단 생각나는게 직선일 것이다. 하지만 아직 블로그를 개설한지 얼마 안 되었기 때문에 사실은 실제 분포가 포물선일 수도 있다 (그러기를 희망해 본다 ^^). 이와 같이 데이터 분포를 보고 이걸 직선으로 해석할지 아니면 포물선으로 해석할지 선택하는 것이 바로 모델을 선택하는 것이다 (모델이 미리 알려지지 않은 경우에는 자신이 직접 모델을 선택해야 하는데, 모델을 선택하는 것은 데이터 해석에 있어서 가장 어려우면서도 중요한 일 중 하나이다).

설마 포물선일리는 없을 테니 일단은 모델(model)을 직선으로 잡자. 일단 모델이 결정되면 모델의 파라미터가 정해지는데, 직선의 경우에는 기울기와 y절편이 모델의 파라미터가 된다. 즉, 모델을 f(x) = ax + b로 잡으면 a, b가 파라미터가 된다. 이 시점에서 최소자승법의 의미를 다시 한번 되돌아보자.

최소자승법(Least Square Method)은 모델의 파라미터를 구하기 위한 대표적인 방법 중 하나로서 모델과 데이터와의 residual²의 합 또는 평균을 최소화하도록 파라미터를 결정하는 방법이다.

Residual은 어떤 데이터가 추정된 모델로부터 얼마나 떨어진 값인가를 나타내는 용어이다 (residual을 한국어로 어떻게 표현해야 할지는 잘 모르겠다. 추정오차? 근사오차? → 통계학에서는 '잔차'라고 부른다고 한다). 어쨌든, 관측된 데이터 (x1, y1), ..., (xn, yn)를 보고 어찌 어찌 계산을 해서 구한(추정한) 모델이 f(x) = a1x + b1라고 해 보자. 그런데, 위 그래프 예처럼 원래 관측된 데이터 분포가 완벽한 직선이 아니라면 어떻게 직선(모델)을 구하더라도 몇몇 데이터들은 오차를 갖게 된다. 이 오차를 residual이라고 부른다. 즉, 데이터 (xi, yi)의 residual은 ri = yi - f(xi)가 된다. 여기서 yi는 관측된 값이고 f(xi)는 추정된 모델에 따른 값이다.

결국, 최소자승법을 사용한다는 말은 residual²의 합, 즉 다음 수식을 최소화하도록 f(x)의 파라미터를 결정한다는 말이 된다.

(1)

f(x)가 직선 ax + b인 경우에는,

(2)

를 최소화하도록 a, b를 결정하는게 최소자승법이다. 위 그래프 예에서 보자면 (오른쪽 그림), 데이터들의 분포를 파란색 직선으로 해석할 수도 있고 빨간색 직선으로 해석할 수도 있겠지만 데이터들과의 residual² 합을 최소로하는 직선은 빨간색 직선일 것이다.

2. 최소자승법의 계산

최소자승법(Least Square Method)은 어떤 기준을 가지고 모델의 파라미터를 구하는가를 말해줄 뿐 실제로 이걸 어떻게 계산하는가는 별개의 문제이다. 실제 계산을 못한다면 활용하기 힘든 만큼 최소자승법을 어떻게 계산하느냐도 매우 중요하다. 최소자승법을 계산하는 방법은 크게 해석학적(analytic) 방법과 대수적(algebraic) 방법이 있는데 대수적 방법이 훨씬 직관적이면서도 효과적이다 (설명의 편의상 분류이며 일반적인 용어는 아님을 밝힌다)

A. 대수적 방법

먼저, 대수적 방법은 위의 모델 추정 문제를 행렬식 형태로 표현한 후에 선형대수학을 적용하는 방법이다. 위에서 예로 든 직선 f(x) = ax +b 추정 문제는 결국 다음 식들을 만족하는 a, b를 찾는 것이다.

(3)

이를 행렬식으로 표현하면 다음과 같다.

(4)

(5)

이 때, A의 역행렬은 존재하지 않지만 pseudo inverse라는 걸 이용하면 X를 다음과 같이 계산할 수 있다 (이걸 자신이 직접 계산해야 한다고 걱정할 필요는 없다. 행렬의 pseudo inverse 계산은 Matlab이나 OpenCV 등 다양한 툴들을 이용하면 된다).

(6)

그런데 여기서 이렇게 구한 X가 정말 residual² 합을 최소로 하는 모델 파라미터일까? 하는 의문이 들 수도 있겠다. 약간의 수학적 설명이 필요한 부분인데 여기서는 간단하게만 설명하도록 하겠다 (수학적 지식이 있는 분만 참고하기 바란다). 위의 residual 제곱합 식인 식 (1)을 행렬로 표현하면 ∥B - AX∥²이 된다 (여기서 ∥∥은 벡터의 L2 - norm이다). 즉, ∥B - AX∥²를 최소로 하는 X를 찾는 문제가 되는데, 이걸 X로 편미분한 후에 0으로 놓으면 -2A^T(B - AX) = 0이 된다. 따라서, ∥B - AX∥²를 최소로 하는, 즉 residual² 합을 최소로 하는 X는 X = (A^TA)^-1A^TB가 된다.

B. 해석학적 방법

 최소자승법(Least Square Method)을 계산하는 다른 한 방법으로 해석학적(analytic) 방법이 있다. 해석학적 방법은 식 (1)을 각각의 모델 파라미터들로 편미분한 후에 그 결과를 0으로 놓고 연립 방정식을 푸는 것이다. f(x) = ax + b인 직선의 경우 식 (2)을 a, b로 각각 편미분하고 그 결과를 0으로 놓으면 다음과 같은 식이 된다.

(7)

이걸 a, b에 대한 연립방정식으로 놓고 풀면 복잡하긴 하지만 어쨌든 a, b가 구해진다.

그런데, 풀리기야 하지만 이러한 해석학적 방법은 계산이 복잡하고 또 계산하다가 실수할 확률이 매우 높다. 어느 세월에 이걸 다 계산한단 말인가.. 단순한 직선 근사 문제야 어찌 어찌 계산한다고 해도 복잡한 고차 함수나 다변수 함수의 경우에는 일찌감치 포기하고 첫번째 대수적 방법으로 푸는 것이 훨씬 정신건강에 좋을 것이다.

하지만, 굳이 해석학적 방법을 여기에 같이 소개한 이유는 문제에 따라서는 대수적 방법으로 잘 해결되지 않을 수도 있기 때문이다. 대수적 방법을 적용하기 위해서는 f(x)가 파라미터들에 대한 1차 선형함수로 표현될 수 있어야 한다 ( f(x) = ax + b는 a, b를 변수로 보면 a, b에 대한 1차식이다). 파라미터에 대한 선형화가 잘 안되는 경우에는 해석학적 방법을 사용하거나 해석학적 방법과 대수적 방법을 병행하는 것도 고려해 볼 수 있을 것이다.

C. 비선형 최소자승법 (non-linear least square)

주어진 least square 문제가 파라미터들에 대한 선형식이 아닌 경우에는 위와 같은 방법으로는 문제를 해결하기 힘들고 비선형 least square 문제로 풀어야 한다. 비선형 least square 문제는 가우스-뉴턴 방법을 이용하여 풀 수 있는데, 이에 대한 설명 및 예제는 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method)을 참조하기 바란다.

3. 최소자승법의 활용

어떤 문제가 주어졌을 때 최소자승법(Least Square Method)을 활용하기 위해서는 먼저 그 문제를 식 (4)와 같은 행렬식 형태로 표현할 수 있어야 한다. 식 (4)와 같이 표현할 수 있다면 그 문제는 쉽게 풀 수 있을 것이요, 그렇지 않은 경우에는 다른 방법을 찾거나 아니면 무슨 수를 쓰든지 식 (4) 형태로 만들어야 한다. 아래의 몇 가지 예들을 통해서 어떤 식으로 최소자승법이 실제 문제에 활용될 수 있는지 하나씩 살펴보도록 하자.

A. 포물선 근사

일단은 연습문제로서, 위 블로그 방문객 수 그래프를 포물선으로 근사한다고 해 보자. 즉,  관측된 데이터 (x1, y1), ..., (xn, yn)를 포물선 f(x) = ax² + bx + c로 근사할 경우에는 다음과 같이 행렬식을 세울 수 있다.

(8)

포물선 이상의 3차, 4차, ... n차 함수로 근사할 경우에도 마찬가지이다. 이와 같이 식을 세운 후 matlab 등의 툴로 pseudo inverse 계산을 해 주면 바로 답을 얻을 수 있다.

참고로, 위 행렬식을 최소자승법으로 풀어서 (풀이 방법은 '2. 최소자승법의 계산' 파트를 읽어보기 바란다) 구한 해를 X' = [a' b' c']^T라 할 때, AX'은 추정된 모델에 따른 값, B - AX'은 이 모델에 대한 residual을 나타낸다.

B. 영상의 밝기 보정

예를 들어, 문자인식에서 배경과 문자를 분리하기 위해 이미지를 이진화한다고 했을 때, 아래 그림과 같이 배경의 밝기 변화가 심한 경우에는 어떤 threshold 값을 사용해도 글씨와 배경이 잘 분리되지 않을 수 있다.

이럴 때, 배경의 밝기 변화를 근사하여 이를 제거한 후에 이진화를 수행하면 아래 그림과 같이 글씨와 배경을 깨끗하게 분리해 낼 수 있다.

그러기 위해서는 먼저 배경의 밝기 변화를 곡면으로 근사할 수 있어야 한다. 이를 위해 영상의 픽셀값들을  관측값으로 생각하고 모델을 z = f(x, y)로 세운다. 여기서 (x, y)는 픽셀 좌표이고, z는 (x, y)에서의 입력 영상의 픽셀값(intensity), f는 우리가 픽셀값들을 근사하기 위한 어떤 함수 모델이다.

먼저, 영상 배경 밝기를 1차 평면 f(x, y) = ax + by + c로 근사할 경우에는 행렬식을 다음과 같이 세울 수 있다.

(9)

만일, 좀더 복잡한 배경 변화까지 커버하기 위해 2차 곡면  f(x,y) = ax² + by² + cxy + dx + ey + f을 사용할 경우에는 행렬식을 다음과 같이 세운다.

(10)

3차 이상의 곡면으로 근사할 경우에도 이와 유사하게 행렬식을 세울 수 있다.

C. 원(circle) 및 타원(ellipse) 근사

2차원 평면상의 점 데이터 (x1, y1), ..., (xn, yn) 들을 원이나 타원으로 근사하는 문제는 직접적인 최소자승법 적용이 힘든 문제로서 이것에 대한 논문들도 많이 나왔을 만큼 쉽지 않은 문제이다.

먼저, 원으로 근사하는 경우를 보면 원의 방정식 (x-a)² + (y-b)² = r²를 전개하면 x² + y² - 2ax - 2by + a² + b² - r² = 0 이 된다. 그런데, 보다시피 모델 파라미터인 a, b, r에 대한 1차 선형식이 아니기 때문에 최소자승법을 곧이 곧대로 적용하기는 힘들다. 이걸 푸는 한 방법은 c = a² + b² - r²라 잡고 x² + y²을 우변으로 넘긴 후에 행렬식을 다음과 같이 세우는 것이다.

(11)

단, r은 위 행렬식을 풀어서 a, b, c를 구한 후에 r = sqrt(a² + b² - c)로 구한다.

타원의 경우에는 x² + ay² + bxy + cx + dy + e = 0 라 식을 세운 후 x²을 우변으로 넘겨서 다음과 같이 행렬식을 만들 수 있다 (회전된 타원까지 고려하여 bxy 항이 들어감).

(12)

그런데, 이렇게 원과 타원을 구하는 것은 residual에 대한 기하학적 해석이 명확하지 않은 약간은 편법적인 방법이며 보다 정확한 근사를 위해서는 비선형(non-linear) 최소자승법으로 해결해야 한다. 비선형 least square 문제는 가우스-뉴턴(Gauss-Newton) 방법으로 풀 수 있는데, 이에 대한 설명 및 예제는 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method)에 있는 원(circle) 근사 예제를 참조하기 바란다.

D. 모션 추정하기

영상처리 분야에서는 optical flow라고 아래 그림과 같이 물체 상에 점들이 연속된 영상 프레임에서 어디로 이동하는지를 추적함으로써 물체의 모션을 추정하는 기술이 있다. 참고로 이 예는 조금 전문적인 내용이기 때문에 이해하기 힘들 수도 있겠다. 하지만 통상적인 방법으로 최소자승법을 적용하기 힘든 경우에는 아래에 사용된 기법이 도움이 될 수도 있으니 참고하기 바란다.

만일 시간 t에서의 영상위의 점들 (x1, y1), (x2, y2), ..., (xn, yn)이 그 다음 영상 프레임에서 (x1', y1'), (x2', y2'), ..., (xn', yn')로 이동했다고 했을 때, 이 점들의 이동을 설명하는 변환관계를 구하는 문제가 있다고 하자. 이 때, 이 변환을 평행이동, 회전이동, scale 변화로만 국한하도록 하자 (이러한 변환을 similarity transform이라고 부른다).

먼저 이러한 similarity 변환관계는 일반적으로 다음과 같이 표현된다.

(13)

즉, 주어진 매칭 쌍 (xi, yi) - (xi', yi'), i = 1, ..., n들로부터 위 similarity 변환의 파라미터인 a, b, c, d를 구하는 문제가 되겠다.

이 문제를 최소자승법으로 푸는 방법은 여러 가지가 있을 수 있겠지만 여기서는 OpenCV에서 사용하는 방법을 소개하도록 하겠다. 먼저, 식 (13)을 전개하면 다음과 같다.

 ------- (14)

------- (15)

위 식을 변형하여 (14)*x + (15)*y, (15)*x - (14)*y, (14), (15)를 각각 행으로 하는 행렬식을 만들면 다음과 같은 행렬식이 만들어진다.

(16)

그러면, 이제 원래의 점 매칭쌍 하나당 위 행렬식이 하나씩 나오게 되는데 이것들을 전부 다 더한다.

(17)

그러면 위와 같은 행렬식이 나오는데, 이제는 pseudo inverse를 구할 필요 없이 바로 역행렬을 취하면 원하는 a, b, c, d를 곧바로 구할 수 있게 된다. 왜 이렇게 해야 하느냐고는 묻지 말자. 다만 이렇게 하면 효과적으로 a, b, c, d가 구해지는 것은 확실하며 통상적인 방법으로 최소자승법을 적용하기 힘든 경우에는 위와 같은 기법도 있음을 알아두면 도움이 될 것이다.

4. 최소자승법의 한계

최소자승법(Least Square Method)을 잘 이용하려면 최소자승법의 한계도 잘 알고 있어야 할 것이다. 최소자승법은 데이터 중에 보통 outlier(정상적인 데이터 분포에서 동떨어진 데이터)라고 불리는 이상한 놈이 하나라도 끼어 있으면 적용하기 힘든 방법이다.  그 이유는 최소자승법은 전체 데이터의 residual2 합을 최소화하기 때문에 outlier의 residual도 같이 줄이려고 하다보면 전혀 엉뚱한(잘못된) 근사 결과를 낼 수 있기 때문이다. 따라서, outlier가 존재하는 경우에는 RANSAC, LMedS, M-estimator 등과 같은 robust한 파라미터 추정 방법을 사용해야 한다. Robust한 파라미터 추정 방법들 중 가장 널리 쓰이는 일반적인 방법은 RANSAC이지만 outlier의 비율이 많지 않은 경우에는 M-estimator를 사용하는 것도 좋다 (RANSAC이나 LMedS는 랜덤성이 있기 때문에 극단적인 경우 해를 못 찾을 수도 있다).

RANSAC 및 robust한 파라미터 추정 방법에 대해서는 RANSAC의 이해와 영상처리 활용 글을 참조하기 바랍니다.

☞ 이상으로 최소자승법(Least Square Method) 및 그 활용법에 대한 나름의 설명을 해 보았습니다. 최소자승법에 관한 글들이 인터넷에 많이 있지만 대부분 회귀분석 쪽이라서 최소자승법의 범용성 및 다른 활용법은 잘 드러나 있지 않은 것 같습니다. 여기 있는 예 외에도 응용에 따라 다양한 활용이 가능할 것으로 생각됩니다.

by 다크 프로그래머