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

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

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

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

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

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

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

<그림 1>

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

주어진 점들의 좌표가 (x1,y1), ..., (xn,yn)이고 이 점들을 직선 y = ax + b로 근사할 때, 흔히 오차(residual)를 ri = yi - (axi + b)로 잡고 ∑ri²이 최소화되도록 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 = (A^TA)^-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∑V^T라 할때 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)

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

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

이 경우 가우스-뉴턴법에 따른 최소자승 해는 모델 파라미터에 대한 초기 추정값 p₀=(a₀, b₀)에서 시작하여 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)

이 경우 가우스-뉴턴법에 따른 최소자승 해는 모델 파라미터에 대한 초기 추정값 p₀=(a₀, b₀, c₀)에서 시작하여 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 다크 프로그래머