대수적 에러와 기하학적 에러(Algebraic & Geometric Error)

기계학습 2014.09.06 11:47

다크입니다. 요즘은 너무 팍팍한 글들만 쓰고 있는 건 아닌지 걱정입니다.. 좀더 재밌게 쓰면 좋을텐데 주제가 주제인지라 ㅠㅠ 그래도 이론적으로는 꼭 필요한 내용들이라 생각됩니다.


이번 글은 대수적 에러(algebraic error)와 기하학적 에러(geometric error)에 대한 내용입니다 (데이터를 근사하거나 함수 최적화에서는 꽤 중요한 용어인데, 다음이나 네이버 등 국내 검색사이트에서는 거의 검색이 되질 않네요..).


원래는 앞서 [기계학습] - 함수최적화 기법 정리 (Levenberg–Marquardt 방법 등) 글에 포함되어야 할 내용이지만 글이 너무 길어지고 또 흐름이 끊길 수 있어서 따로 글로 씁니다.


대수적 에러, 기하학적 에러에 대한 내용은 영상에서 차선 등의 직선을 찾을 때, 벽면이나 물체 표면의 밝기 변화를 평면이나 곡면으로 근사할 때, 3D 비전에서 bundle adjustment를 수행할 때 등 어떤 주어진 데이터를 모델로 근사시키는 모든 문제에 관련됩니다. 이 글에서는 가장 간단한 예인 직선 근사 문제를 통해 관련 개념과 구체적인 계산 방법 등을 살펴봅니다.



1. 대수적 에러와 기하학적 에러의 의미


아래 그림과 같이 2차원 평면 위에 점들이 있고 이 점들을 직선으로 근사하는 문제가 있습니다.


<그림 1>


주어진 데이터가 있고, 이 데이터들을 어떤 모델로 근사시키고자 할 때, 최소자승법에서는 데이터와 모델과의 오차 제곱의 합이 최소가 되도록 모델 파라미터를 구합니다. 그런데, 이 오차를 어떻게 정의하느냐에 따라서 문제 풀이 방법 및 그 결과가 크게 달라질 수 있습니다.


주어진 점들의 좌표가 (x1,y1), ..., (xn,yn)이고 이 점들을 직선 y = ax + b로 근사할 때, 흔히 오차(residual)를 ri = yi - (axi + b)로 잡고 ∑ri2이 최소화되도록 a, b를 정합니다. 그리고 이 경우의 최소자승문제는 선형(linear) 문제가 되어서 pseudo inverse를 이용하면 손쉽게 해를 구할 수 있습니다 (자세한 내용은 [기계학습] - 함수최적화 기법 정리 (Levenberg–Marquardt 방법 등) 글 참조).


그런데 이렇게 잡은 오차 ri = yi - (axi + b)는 기하학적으로 어떤 의미를 가질까요? 바로 아래 그림에서 점과 직선과의 y축 거리가 됩니다 (또는 모델을 x = ay + b로 잡고 오차를 ri = xi - (ayi + b)로 잡아서 최소화시키면 데이터 점과 직선과의 x축 방향으로의 거리를 최소화시키는 직선을 구하게 됩니다).


<그림 2>


즉, 원래는 직선과의 수직거리를 최소화시키는 모델을 찾아야 하는데 엉뚱하게도 y축 거리를 최소화시키는 모델을 찾고 있는 셈입니다. 만일, 원래대로 데이터들과의 수직거리가 최소화되는 직선을 찾고자 한다면 ri를 다음과 같이 정의해야 합니다.


 --- (1)


이 때, ri = yi - (axi + b)와 같이 대수적으로 정의되는 에러를 대수적 에러(algebraic error)라 하고 직선과의 수직거리처럼 기하학적인 해석에 의해 정의되는 에러를 기하학적 에러(geometric error)라 합니다.


적고 보니 마치 '산을 산이라 하고 물을 물이라 한다'가 되버렸네요.. ^^; 지금은 애매하지만 끝까지 읽다보면 좀더 뜻이 명확해 지리라 생각합니다.


[양함수 표현과 음함수 표현]

y = f(x), y = f(x1,x2,...,xn) 등과 같이 독립변수가 종속변수들에 대한 명시적 식으로 표현된 함수를 양함수(explicit function)이라 하고 f(x,y) = 0,  f(x1,x2,...,xn) = 0 등과 같이 독립변수와 종속변수가 구분되지 않고 하나의 관계식 형태로 주어진 함수를 음함수(implicit function)라 합니다.


위 직선근사 문제의 경우에는 다음과 같이 양함수, 음함수 2가지 형태로 직선 모델을 잡을 수 있습니다.

  • 양함수 직선 모델: y = ax + b
  • 음함수 직선 모델: ax + by + c = 0

알다시피 y = ax + b는 기울기가 90도인 직선은 표현하지 못하는 문제점이 있기 때문에 일반적으로는 ax + by + c = 0 모델을 사용하는 것이 좋습니다 (y = ax + b를 음함수 형태로 변형시켜 보면 y - ax - b = 0이 되는데, y 앞의 계수가 0이 아니라는 제약을 가지기 때문에 표현하지 못하는 직선이 존재하게 됩니다).


만일 직선근사 문제에서 음함수 모델 f(x,y) = ax + by + c = 0을 사용할 경우에는 대수적 에러(algebraic error)와 기하학적 에러(geometric error)를 다음과 같이 잡을 수 있습니다.


 --- (2)


 --- (3)


여기서 식 (2)로 주어지는 대수적 에러의 의미를 생각해 보면 다음과 같습니다. 직선 ax + by + c = 0에 점 (xi, yi)를 대입해서 그 결과가 axi + byi + c = 0이 되면 (xi, yi)는 직선 위의 점이고 axi + byi + c ≠ 0 이면 직선과 떨어진 점입니다. 즉, ri = axi + byi + c 는 직선의 방정식에 (xi, yi)를 대입하여 0이 아닌 정도를 에러로 생각한 것입니다. 따라서 식 (2)에 의해 주어지는 에러가 기하학적으로 어떤 의미가 있는지는 불명확합니다. 그저 모델로 주어지는 함수 조건을 만족하지 못하는 정도로 밖에는 해석이 안됩니다. 반면에 식 (3)은 점 (xi, yi)과 직선 ax + by + c = 0과의 수직거리이므로 기하학적 의미가 명확합니다.


이상의 내용을 정리해 보면 다음과 같습니다.

  • 대수적 에러(algebraic error)는 데이터를 모델의 함수식(관계식)에 대입했을 때 발생하는 오차를 에러로 잡은 것으로서 양함수 모델의 경우에는 ri = yi - f(xi,...), 음함수 모델일 경우에는 ri = f(xi,yi,...)가 대수적 에러이다.
  • 기하학적 에러(geometric error)는 데이터와 모델 함수 사이의 기하학적 거리(수직/최단 거리)를 에러로 잡은 것으로서 그 구체적인 계산은 모델마다 함수마다 달라질 수 있다.


따라서 쉽게 생각해 봐도 대수적 에러(algebraic error)보다는 기하학적 에러(geometric error)를 최소화시키는 것이 훨씬 좋음을 알 수 있습니다. 하지만, 기하학적 에러는 계산이 복잡하고 해를 찾기가 어렵다는 문제점이 있습니다. 따라서 보통의 경우에는 계산의 편리성 측면에서 대수적 에러를 사용하고 정밀한 해가 요구되는 문제에는 기하학적 에러를 사용하는게 일반적입니다.


참고로, 기하학적 에러는 대부분 점과 함수와의 수직거리로 주어지는데 n차원 공간에서 점 (a1,...,an)과 초평면(hyper plane) c1x1 + c2x2 + ... cnxn + cn+1 = 0과의 수직거리는 일반적으로 다음과 같이 구해집니다 (n≥2).


 --- (4)



2. 직선 근사 예제


간단한 적용 예로, 5개의 점 (1, 2.8), (2, 2.6), (3, 3.4), (4, 4.4), (5, 4.8)을 근사하는 직선을 대수적 에러와 기하학적 에러를 이용하여 구해보고 그 결과를 살펴보도록 하겠습니다.


☞ 계산과정에 대한 이론적인 내용에 대해서는 [기계학습] - 함수최적화 기법 정리 (Levenberg–Marquardt 방법 등) 글을 참조하기 바랍니다.



(1) 양함수모델: y=ax+b, 대수적 에러


이 경우 최소자승(least squares) 문제를 행렬 형태로 표현하면 다음과 같다.


 --- (5)



이 때, pseudo inverse를 이용해서 해를 구해보면 p = pinv(A)y = (ATA)-1Ay = [0.58 1.86]T가 된다. 즉, 양함수(explicit function) 모델에 대수적 에러를 사용할 경우의 근사 직선은 다음과 같다.


 --- (6)


<그림 3>


[Matlab 코드]

x = [1:5]';

y = [2.8,2.6,3.4,4.4,4.8]';


A = [x ones(length(x),1)];

p = pinv(A)*y;

yp = p(1)*x + p(2);

plot(x,y,'r*', x,yp,'b-');



(2) 음함수모델: ax+by+c=0, 대수적 에러


음함수(implicit function) 직선모델을 사용할 경우 앞서와 마찬가지로 행렬 형태로 문제를 표현하면 다음과 같다.


 --- (7)



이 경우, 식 (7)을 만족하는 해는 A의 SVD(singular vector decomposition)을 A = U∑VT라 할때 V의 가장 오른쪽 열벡터이다(최소 특이값에 대응하는 V의 열벡터). 실제로 계산해 보면 그 해는 p = [-0.2316 0.4314, -0.8719]T가 된다. 즉, 음함수(implicit function) 모델에 대수적 에러를 사용할 경우의 근사 직선은 다음과 같다.


 --- (8)


이를 y에 대해 정리해 보면 다음과 같다.


 --- (9)


<그림 4>


[Matlab 코드]

x = [1:5]';

y = [2.8,2.6,3.4,4.4,4.8]';


A = [x y ones(length(x),1)];

[U,D,V] = svd(A);

p = V(:,end);

yp = (-p(1)*x - p(3))/p(2);

plot(x,y,'r*', x,yp,'b-');



(3) 양함수모델: y=ax+b, 기하학적 에러


양함수 직선모델과 기하학적 에러를 사용할 경우 에러 r은 다음과 같이 잡을 수 있다.


 --- (10)


원래의 직선거리 식은 분자에 절대값이 붙어야 하지만 우리가 풀고자 하는 문제가 ∑ri2을 최소화시키는 a, b를 구하는 것이므로 굳이 절대값을 붙일 필요가 없다.


이 때, ∑ri2를 최소화시키는 문제는 비선형(nonlinear) 최소자승문제가 되므로 gradient descent 방법, 가우스-뉴턴법, Levenberg-Marquardt 방법 등과 같은 iterative minimization 기법을 사용해야 한다. 여기서는 가우스-뉴턴(Gauss-Newton)법을 이용하여 해를 구해보기로 한다.


이 경우 가우스-뉴턴법에 따른 최소자승 해는 모델 파라미터에 대한 초기 추정값 p0=(a0, b0)에서 시작하여 p를 다음 수식에 의해 반복적으로 갱신함으로써 얻어진다


--- (11)


단,

--- (12)


이 때, 야코비언 Jr(p) 계산을 위해 ri를 모델 파라미터 a, b로 편미분해 보면 다음과 같다.


 --- (13)


파라미터에 대한 초기 추정값을 대수적 에러를 이용하여 구한 해인 p0 = (0.58, 1.86)로 잡고 가우스-뉴턴법을 10회 반복하여 해를 구해보면 다음과 같다 (기하학적 에러를 사용할 경우에는 보통 대수적 에러를 이용하여 구한 해를 초기 추정값으로 이용한다).


 --- (14)


<그림 5>


[Matlab 코드]

x=[1:5]';

y=[2.8,2.6,3.4,4.4,4.8]';


p = [0.58,1.86]';

for k=1:10,

    r = (y-p(1)*x-p(2))/sqrt(1+p(1)^2);

    J = [(-x*sqrt(1+p(1)^2)-r*p(1))/sqrt(1+p(1)^2) -ones(length(x),1)/sqrt(1+p(1)^2)];

    p = p - pinv(J)*r;

end;

yp = p(1)*x + p(2);

plot(x,y,'r*',x,yp,'b-');



(4) 음함수모델: ax+by+c=0, 기하학적 에러


음함수 직선모델과 기하학적 에러를 사용할 경우 에러 r은 다음과 같이 잡을 수 있다(앞서와 마찬가지 이유로 절대값을 제거하고 생각한다).


 --- (15)


이 경우 가우스-뉴턴법에 따른 최소자승 해는 모델 파라미터에 대한 초기 추정값 p0=(a0, b0, c0)에서 시작하여 p를 다음 수식에 의해 반복적으로 갱신함으로써 얻어진다


--- (16)


단,

--- (17)


이 때, 야코비언 Jr(p) 계산을 위해 ri를 모델 파라미터 a, b, c로 편미분해 보면 다음과 같다.


 --- (18)


앞서와 마찬가지로 파라미터에 대한 초기 추정값을 대수적 에러를 이용하여 구한 해인 p0 = (-0.2316, 0.4314, -0.8719)로 잡고 가우스-뉴턴법을 10회 반복하여 해를 구해보면 다음과 같다.


 --- (19)


그리고 이를 y에 대해 정리해 보면 다음과 같다.


 --- (20)


<그림 6>


[Matlab 코드]

x=[1:5]';

y=[2.8,2.6,3.4,4.4,4.8]';


p = [-0.2316,0.4314,-0.8719]';

for k=1:10,

    s = sqrt(p(1)^2+p(2)^2);

    r = (p(1)*x+p(2)*y+p(3))/s;

    J = [(x*s-r*p(1))/s^2 (y*s-r*p(2))/s^2 ones(length(x),1)/s];

    p = p - pinv(J)*r;

end;

yp = (-p(1)*x - p(3))/p(2);

plot(x,y,'r*',x,yp,'b-');



(5) 결과 비교


이상의 결과를 종합적으로 비교해 보면 아래와 같다.


직선 모델

최소화할 에러

근사 결과

 y = ax + b

대수적에러(algebraic error)

y = 0.58x + 1.86

 ax + by + c = 0

대수적에러(algebraic error)

y = 0.5368x + 2.021

 y = ax + b

기하학적에러(geometric error)

y = 0.5976x + 1.8073

 ax + by + c = 0

기하학적에러(geometric error)

y = 0.5976x + 1.8073


<그림 7>


3. 맺음말


예로 든 직선 근사 문제에 비추어 보면 대수적 에러(algebraic error)를 사용할 경우에는 모델의 형태에 따라서 서로 다른 결과를 보였지만 기하학적 에러(geometric error)를 사용했을 때에는 양함수 모델, 음함수 모델에 관계없이 동일한 결과(최적해)를 나타냄을 볼 수 있습니다. 하지만 예에서 봤듯이 기하학적 에러를 최소화시키는 것은 훨씬 복잡한 계산을 필요로 합니다.


또한 기억해야 할 중요한 점 중의 하나는 기하학적 에러를 사용할 경우에는 iterative minimization 기법을 적용해야 하는데, 이 때의 파라미터 초기 추정값은 대수적 에러 방법의 해를 이용하면 좋다는 것입니다.


☞ 최대한 간단한 예를 들고자 하는 마음에 직선 근사 예를 사용했는데, 막상 계산도 간단치 않고 <그림 6>의 결과처럼 대수적 에러를 사용한 경우가 더 좋은지 기하학적 에러가 더 좋은지 판단하기도 쉽지 않습니다.. 차라리 원근사 예를 들었다면 기하학적 에러가 더 좋다는 점도 보일 수 있고 더 좋았을 것 같다는 생각도 듭니다.


☞ 위 직선 근사 예제에서 각각의 경우에 대해 일일히 풀이 방법을 설명한 이유는 앞서 [기계학습] - 함수최적화 기법 정리 (Levenberg–Marquardt 방법 등)에서 설명했던 여러 함수 최적화 기법들의 실제 적용법을 보이기 위한 목적도 있습니다. 원래는 기하학적 에러를 Levenberg-Marquardt 방법을 적용하여 최소화시키는 예를 보였으면 더 좋았겠지만 설명의 편의상 가우스-뉴턴법을 적용하였습니다.


☞ 최근에 용어 문제를 지적해 주신 댓글이 잠깐 달린 적이 있는데, 동일한 개념이라도 분야마다 조금씩 용어가 다른 것 같습니다. 대수적 에러는 ordinary error, 기하학적 에러는 orthogonal error라고 불러도 좋을 것 같습니다.


by 다크 프로그래머


  • 이 또한 지나가리라 2014.09.14 13:03 신고 ADDR 수정/삭제 답글

    정리해서 이렇게 깔끔하게 편집하려면 시간이 많이 걸리셨을 텐데, 어렵게 습득한 귀한 지식을 나눠주시려는 열정에 감복합니다. 우연히 들렀다가 제목만 보고 무슨 내용인지 궁금해서 읽어 봤는데 일반적인 최소오차자승법(Ordinary Least Squares, OLS)과 Total Least Squares(TLS, 혹은 orthogonal LS라고도 합니다)를 비교한 내용인 것 같습니다. '대수적 오차/기하학적 오차'라는 용어를 사용하기도 하는군요. OLS는 y + error1 = a*x + b 형태(즉 x는 주어졌다고 가정하고 y만 확률변수로 가정)로 error1을 최소화하는 것이고 TLS는 y + error1 = a*(x + error2) + b 형태의 모델(x, y 모두 확률변수로 가정)이었던 것 같습니다. 둘 중 어느 모델이 더 나으냐는 추정하려는 데이터 특성에 달려 있을 것 같습니다. 독립변수의 데이터 획득시 불확실성이 존재할 가능성이 별로 없으면 오히려 OLS가 더 나을지 모르겠습니다. 위키피디아에 Total Least Squares 찾아보니 다차원의 경우에 대해 잘 설명되어 있네요. 기본적인 형태의 선형회귀법(OLS)은 데이터에 대한 가정이 너무 많아서 그 가정을 하나씩 깨뜨린 변형방법들이 많습니다. TLS도 그 중의 하나인데 OLS의 weak exogeneity 가정을 깨뜨린 것으로 이해할 수 있을 것 같습니다. TLS도 SVD사용해서 간단히 구현은 가능한데 역시 안정성 문제가 있을 것 같습니다. TLS는 잡음제거, 해상도 증가 등을 연구하다가 우연히 알게 되었습니다.

    그리고 제가 보기에는, 대수적 에러라고 하지만 결국 기하학적으로 설명가능하니 기하학적 에러라고 볼 수도 있고, 기하학적 에러라고 하지만 결국 대수적으로 표현되니 역시 대수적 에러가 아닌가 하는 생각이 들어서 개인적으로는 용어가 조금 마음에 차지 않는 것 같습니다. 그래도 설명해주신 내용에는 어느정도 수긍이 갑니다. 음함수의 대수적 에러도 (a, b, c)와 (x, y, 1)의 내적을 의미하는 것이니 (a, b, c)를 단위벡터로 가정하면 기하학적 설명도 가능은 할 것 같습니다. 결국 벡터 (xi, yi, 1)들에 가장(?) 직교하는 하나의 단위벡터를 찾는 것인데, 이 단위벡터를 법선벡터로 하는 평면과 우리가 구하려는 직선이 무슨 관계가 있을 듯합니다만, 직관적으로 와닿는 설명은 확실히 아니네요. --;

    사실 선형회귀만 제대로 공부하려고 해도 아마 몇 주는 걸릴 것 같습니다. 위키피디아의 Linear Regression 에도 정리가 잘 되어 있었던 걸로 기억합니다. 공부한지 오래되서 저도 가물가물하네요.

    제가 포스팅 내용을 잘못 이해하고 착각한 것일 수도 있으니, 그럴 경우에는 가르침 주세요. 이미 다 아시는 내용인데 주제넘게 나선 것은 아닐까하는 생각도 들었는데, 여기 방문하시는 다른 분들께도 혹시 도움이 될까해서 이렇게 글 남깁니다. 그럼...

    • BlogIcon 다크pgmr 2014.09.14 15:49 신고 수정/삭제

      여러가지 좋은 의견 감사합니다.
      용어는 분야마다 조금씩 다를 수 있지만 말씀하신 것처럼 개념상 기하학적 에러와 대수적 에러가 상반되는 용어가 아니니 ordinary error, orthogonal error로 구분하는 것도 좋을 것 같습니다.
      다만, 제가 대수적 에러/기하학적 에러라 구분한 이유는 이들이 3D vision 쪽에서 통용되는 용어이기도 하고 또한 에러라는게 기하학적 해석에 따라 얼마든지 다양하게 잡을 수 있음을 강조하기 위함이기도 합니다. 제가 이 글을 쓴 가장 큰 이유(목적)는 최소자승(LS) 문제에서 에러 제곱합을 최소화하는 모델 파라미터를 구할 때, 이 에러 자체도 다양한 형태로 정의될 수 있으며 이 에러를 어떻게 정의하느냐에 따라 문제 풀이법과 결과가 달라질 수 있음을 설명하기 위함입니다. 그리고 이와 같이 다양하게 정의된 에러 목적함수의 최적화에 앞서 '함수 최적화 기법' 글에서 소개한 가우스-뉴턴법, Levenberg-Marquardt 등과 같은 최적화 기법들이 사용될 수 있음을 말하고 싶었습니다.

    • 메모광 2014.09.19 13:55 신고 수정/삭제

      Linear regression의 툴인 OLS와 TLS를 말씀하셨는데,
      대수적 에러와 기하학적 에러는 "보다 일반적인 상황"도 표현 가능한 용어인 것 같습니다. 예를 들어, 원이나 conic의 추정 문제에도 대수적 에러, 기하학적 에러 개념을 사용할 수 있지만, OLS이나 TLS 관점에서 보기는 쉽지 않을 것 같네요.

  • 이 또한 지나가리라 2014.09.14 18:42 신고 ADDR 수정/삭제 답글

    아~ 그렇군요. 제가 큰 맥락을 놓쳤네요. 다양한 비용함수에 대해 최적화기법을 시연해보는 것이 목적이었군요. 잘 알겠습니다. 용어는 동료연구자들이 오해없이 잘 이해할 수 있으면 그걸로도 괜찮을 듯합니다. 분야마다 그런 용어 조금씩은 다 있으니까요. 아무튼 저도 자주는 못하지만, 가끔씩 들리도록 하겠습니다. 수고가 많으시네요.

  • 실패란 없다 2014.12.16 16:53 신고 ADDR 수정/삭제 답글

    와 감사합니다.

  • 위촉 2015.06.01 15:13 신고 ADDR 수정/삭제 답글

    쉽지 않은 내용을 이렇게 이해하기 쉽게 설명해주셔서 정말 감사합니다.

    항상 많이 배워가고 있습니다!

  • 하하 2018.05.14 13:47 신고 ADDR 수정/삭제 답글

    3.맺음말에서 "또한 기억해야 할 중요한 점 중의 하나는 기하학적 에러를 사용할 경우에는 iterative minimization 기법을 적용해야 하는데, 이 때의 파라미터 초기 추정값은 대수적 에러 방법의 해를 이용하면 좋다는 것입니다." 다음과 같은 내용에서 비선형 신호, sine 또는 cos 신호 같은 경우 대수적 에러 방법을 사용하여 해를 구할 수 없다고 이해하였습니다. 그러면, 기하학적 에러 사용의 경우 파라미터 초기 수정값은 어떻게 설정하는 것이 맞나요??

    • BlogIcon 다크pgmr 2018.05.14 15:19 신고 수정/삭제

      파라미터에 대한 특별한 사전 지식이 없을 경우에는 모두 0으로 놓고 시작해야 할것 같습니다만.. 하지만, 저도 이쪽 분야에 전문지식을 가지고 있는 것은 아니라서 다른 좋은 방법이 있는지는 모르겠네요.