인공지능을 위한 선형대수 - CHAPTER 3.3 정규방정식

www.edwith.org/linearalgebra4ai/lecture/24131/

[LECTURE] 정규방정식 : edwith

Another Derivation of Normal Equation

Normal Equation을 유도하는 방법으로 미분(Derivation)을 이용할 수 있습니다.

\(||\mathbf{b}-A\mathbf{x}||\)를 최소화하는 \(\mathbf{x}\)는 \(||\mathbf{b}-A\mathbf{x}||^{2}\)를 최소화하는 \(\mathbf{x}\)와 같습니다.

 

잠깐 복습을 해보자면, \(||\mathbf{y}||\)는 \((\mathbf{y}^{T}\mathbf{y})^{2}\) 이고 \(||\mathbf{y}||^{2}\)는 \((\mathbf{y}^{T}\mathbf{y})\)입니다.

 

\(||\mathbf{b}-A\mathbf{x}||^{2}\)를 최소화하는 것은 \( (\mathbf{b}-A\mathbf{x})^{T}(\mathbf{b}-A\mathbf{x}) \)를 최소화하는 것과 동일합니다. \( (\mathbf{b}-A\mathbf{x})^{T}(\mathbf{b}-A\mathbf{x}) \)는 전개하면 \(\mathbf{b}^{T}\mathbf{b} - \mathbf{x}^{T}A^{T}\mathbf{b}-\mathbf{b}^{T}A\mathbf{x}+\mathbf{x}^{T}A^{T}A\mathbf{x}\)가 됩니다. 

 

그리고, 이를 \(\mathbf{x}\)에 대하여 미분해보겠습니다. 우선, \(\mathbf{b}^{T}\mathbf{b} - \mathbf{x}^{T}A^{T}\mathbf{b}-\mathbf{b}^{T}A\mathbf{x}+\mathbf{x}^{T}A^{T}A\mathbf{x}\)를 4개의 항으로 쪼개고 각각 미분해보겠습니다.

 

1. \(\mathbf{b}^{T}\mathbf{b}\)

항에 \(\mathbf{x}\)가 없으므로 0이 됩니다.

2. \(\mathbf{x}^{T}A^{T}\mathbf{b}\)

항에 \(\mathbf{x}\)가 존재합니다. 그런데 해당 항을 벡터 \(\mathbf{x}\)로 미분하려니 머리가 뜨거워지기 시작합니다.

 

해당 항을 미분하기 위하여 벡터를 포함하는 항을 해당 벡터로 미분하는 방법을 먼저 정리할 필요가 있습니다.

 

입력 값이 벡터 \(\mathbf{x}\)인 함수 \(f(\mathbf{x}) = \mathbf{a}^{T}\mathbf{x}\)가 있습니다. 여기서, \(\mathbf{a}^{T}\) 는 \(\begin{bmatrix} 3 && 2  \end{bmatrix} \) 이고, \(\mathbf{x}\) 는 \(\begin{bmatrix} x_{1} \\ x_{2}  \end{bmatrix} \) 라고 정의하겠습니다.

 

즉 \(f(\mathbf{x})= 3x_{1}+2x_{2}\) 입니다.

 

\(f(\mathbf{x})\)을 \(x_{1}\)에 대해 편미분하면 \(3\)이 나옵니다. 

\(f(\mathbf{x})\)을 \(x_{2}\)에 대해 편미분하면 \(2\)가 나옵니다. 

 

\(\frac{\partial f}{\partial x}=\begin{bmatrix} 3 \\ 2 \end{bmatrix} = \mathbf{a}\) 가 됩니다.

그리고, 다시 한 번 생각해보면 \(f(\mathbf{x}) = \mathbf{a}^{T}\mathbf{x} = \mathbf{x}^{T}\mathbf{a}\)입니다.

 

앞으로 인생을 살면서 \(f(\mathbf{x}) = \mathbf{a}^{T}\mathbf{x} = \mathbf{x}^{T}\mathbf{a}\) 를 \(\mathbf{x}\)로 미분한 결과는 \(\mathbf{a}\)라고 생각하면 됩니다. 이를 본 글에서는 인생 벡터 미분 법칙이라고 부르겠습니다.

 

다시 돌아와서 \(\mathbf{x}^{T}A^{T}\mathbf{b}\)를 \(\mathbf{x}\)로 미분해보겠습니다. 보이시나요? \(\mathbf{x}^{T}A^{T}\mathbf{b}\)를 보다보면 \(A^{T}\mathbf{b}\)가 수상스럽게 보입니다. 그렇습니다. \(f(\mathbf{x}) =\mathbf{x}^{T}A^{T}\mathbf{b}\) 라고 했을때, 이를 \(\mathbf{x}\)로 미분한 결과는 인생 벡터 미분 법칙에 따라 \(A^{T}\mathbf{b}\)입니다.

 

3. \(\mathbf{b}^{T}A\mathbf{x}\)

항에 \(\mathbf{x}\)가 존재합니다. 그런데 해당 항을 벡터 \(\mathbf{x}\)로 미분하려니 인생 벡터 미분 법칙을 적용할 생각에 머리가 차가워지기 시작합니다.

 

\(f(\mathbf{x}) =\mathbf{b}^{T}A\mathbf{x}\) 라고 했을때, \(f(\mathbf{x}) =\mathbf{b}^{T}A\mathbf{x} = \mathbf{x}^{T}(\mathbf{b}^{T}A)^{T} = \mathbf{x}^{T}A^{T}\mathbf{b}\)가 됩니다.

 

이를 \(\mathbf{x}\)로 미분한 결과는 인생 벡터 미분 법칙에 따라 \(A^{T}\mathbf{b}\)입니다.

 

4. \(\mathbf{x}^{T}A^{T}A\mathbf{x}\)

 

\(\mathbf{x}^{T}A^{T}A\mathbf{x}\)를 미분하는 건 예상치 못한 시나리오입니다.

고등학교때 배운 미분 공식을 생각해봅시다.

 

\(y = f \cdot g \) 일때, \(y^{'} = f^{'}g + fg^{'}\)입니다. 이 공식을 통해 간단한 식 \(x^{2}\), \(x^{3}\)을 미분해보겠습니다.

 

\(x^{2}\) 를 \( f \cdot g \) = \(x \cdot x \) 로 보겠습니다.

이를 위 공식을 이용하여 미분하면 \(1 \cdot x + x \cdot 1 = 2x \)가 됨을 확인할 수 있습니다.

 

\(x^{3}\) 을 \( f \cdot g \) = \(x^{2} \cdot x \) 로 보겠습니다.

이를 위 공식을 이용하여 미분하면 \(2x \cdot x + x^{2} \cdot 1 \)가 됨을 확인할 수 있습니다.

 

이제 위 공식을 응용하여 \(\mathbf{x}^{T}A^{T}A\mathbf{x}\)를 \(\mathbf{x}\)로 미분해봅시다.

사실 위 공식과 100% 대응되어 미분이 되지는 않습니다. 이점에 유의해야 합니다.

 

먼저, \(\mathbf{x}^{T}A^{T}A\mathbf{x}\)를 \(\mathbf{x}^{T}\) 와 \(A^{T}A\mathbf{x}\)의 곱이라고 나누어 생각하고\(A^{T}A\mathbf{x}\) 항에는 \(x\)가 있지만 이를 무시하고 \(\mathbf{a}\)라는 벡터라고 생각해보겠습니다. 이때, \(\mathbf{x}^{T}A^{T}A\mathbf{x} = \mathbf{x}^{T}\mathbf{a}\)를 \(\mathbf{x}\) 로 미분하면 인생 벡터 미분 법칙에 의하여 \(\mathbf{a} = A^{T}A\mathbf{x}\)가 나오게 됩니다. 이를 \(f^{'}\)라고 하겠습니다.

 

이번에는 위와 반대로 \(\mathbf{x}^{T}A^{T}A\mathbf{x}\)를 \(\mathbf{x}^{T}A^{T}A\) 와 \(\mathbf{x}\)의 곱이라고 나누어 생각하고 \(\mathbf{x}^{T}A^{T}A\) 항에는 \(\mathbf{x}\)가 있지만 이를 무시하고 \(\mathbf{a}^{T}\)라는 벡터라고 생각해보겠습니다. 이때, \(\mathbf{x}^{T}A^{T}A\mathbf{x} = \mathbf{a}^{T}\mathbf{x} = \mathbf{x}^{T}\mathbf{a}\)를 \(\mathbf{x}\) 로 미분하면 인생 벡터 미분 법칙에 의하여 \(\mathbf{a} = A^{T}A\mathbf{x}\)가 나오게 됩니다. 이를 \(g^{'}\)라고 하겠습니다.

 

\(\mathbf{x}^{T}A^{T}A\mathbf{x}\)를 \(\mathbf{x}\)로 미분한 결과는 \(f^{'} + g^{'}\)로 \(2A^{T}A\mathbf{x}\)와 같습니다. 

 

4가지 항에 대해 모두 미분해보았습니다. 이제 이를 부호에 맞게 다시 정리하면, \(\mathbf{b}^{T}\mathbf{b} - \mathbf{x}^{T}A^{T}\mathbf{b}-\mathbf{b}^{T}A\mathbf{x}+\mathbf{x}^{T}A^{T}A\mathbf{x}\)의 미분 결과는 \(-A^{T}\mathbf{b} - A^{T}\mathbf{b} + 2A^{T}A\mathbf{x} = 2(-A^{T}\mathbf{b} + A^{T}A\mathbf{x}) \) 가 됩니다.

 

 \( (\mathbf{b}-A\mathbf{x})^{T}(\mathbf{b}-A\mathbf{x}) \)를 최소화하는 \(\mathbf{x}\)는  \(2(-A^{T}\mathbf{b} + A^{T}A\mathbf{x}) = 0\)일때의 \(\mathbf{x}\) 와 동일합니다. (극소값일 때 최소값)

 

여기서, 양변을 2로 나누면, \(-A^{T}\mathbf{b} + A^{T}A\mathbf{x} = 0\) 는 \(A^{T}A\mathbf{x} = A^{T}\mathbf{b}\)가 됩니다.

 

미분을 통해 Normal Equation, \(A^{T}A\mathbf{x} = A^{T}\mathbf{b}\)를 유도해보았습니다.

 

행렬 및 벡터의 미분에 관한 공식을 공부하고 싶다면 Matrix Cookbook 책을 읽을 것을 권장드립니다.