[선형대수학#13] Least Squares Solution

이번 포스팅에서는 $A\mathbf{x} = \mathbf{b}$가 정확한 해를 갖지 않을 때, 오차를 최고화하는 근사해를 구하는 최소제곱해를 정리한다.

 

Problem Definition

$A\mathbf{x} = \mathbf{b}$를 풀고 싶다. $A$가 정방행렬이고 nonsingular이면 $\mathbf{x} = A^{-1}\mathbf{b}$로 정확한 해를 구할 수 있다. 그런데 현실의 데이터에서는 이 조건이 거의 성립하지 않는다. 데이터 포인트 수($m$)가 변수 수($n$)보다 많으면 $A$는 $m \times n$ 행렬($m > n$)이 되어 정방행렬이 아니고, 모든 데이터를 정확히 만족하는 $\mathbf{x}$는 일반적으로 존재하지 않는다. 

 

이때 우리가 할 수 있는 최선은, $A\hat{\mathbf{x}}$가 $\mathbf{b}$에 최대한 가까워지도록 하는 $\hat{\mathbf{x}}$를 찾는 것이다. 즉, 오차 $\lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert$를 최소화하는 문제이다.

 

최소제곱해 유도

$\lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert$를 최소화하는 $\hat{\mathbf{x}}$를 구하자. 오차를 그대로 다루면 제곱근이 있어서 불편하므로, 오차의 제곱을 최소화하는 것을 목표로 한다. $\lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert$를 최소화하는 $\mathbf{x}$와 $\lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert^2$를 최소화하는 $\mathbf{x}$는 같으므로 문제없다. "최소제곱"이라는 이름이 여기서 온다. 

 

$$f(\mathbf{x}) = \lVert \mathbf{b} - A\mathbf{x} \rVert^2 = (\mathbf{b} - A\mathbf{x})^T (\mathbf{b} - A\mathbf{x})$$

 

전개하면

 

$$f(\mathbf{x}) = \mathbf{b}^T \mathbf{b} - 2\mathbf{b}^T A \mathbf{x} + \mathbf{x}^T A^T A \mathbf{x}$$

 

이다. $ f(\mathbf{x})$를 최소화하려면 $\mathbf{x}$로 미분해서 0으로 놓으면 된다.

 

$$\frac{\partial f}{\partial \mathbf{x}} = -2A^T \mathbf{b} + 2A^T A \mathbf{x} = \mathbf{0}$$

 

정리하면

 

$$A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$$

 

이 식을 정규방정식(normal equation)이라 한다. $A$가 $m \times n$행렬이고 $\text{rank}(A) = n$이면 $A^TA$는 $n \times n$ nonsingular 대칭 행렬이므로 역행렬이 존재한다. 따라서 

 

$$\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}$$

 

이다. 이전 포스팅에서 다뤘던 rank와 nonsingular의 동치 조건이 여기서 쓰인다. $\text{rank}(A) = n$이 보장되어야 $ (A^T A)^{-1}$이 존재하고, 그래야 최소제곱해가 유일하게 결정된다.

 

 

예시

 

$$A = \begin{pmatrix} 1 & 2 & 1 \\ 0 & 1 & 4 \\ 1 & 6 & -1 \\ -2 & 5 & 3 \end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} 1 \\ 0 \\ 2 \\ -1 \end{pmatrix}$$

 

$A$는 $4 \times 3$행렬이고 $\text{rank}(A) = 3$이다. 방정식 수(4)가 변수 수(3)보다 많으므로 정확한 해는 존재하지 않는다. 최소재곱해를 구하면 

 

$$(A^T A)^{-1} = \begin{pmatrix} 0.216 & -0.005 & 0.051 \\ -0.005 & 0.017 & -0.011 \\ 0.051 & -0.011 & 0.054 \end{pmatrix}$$

 

$$\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b} = \begin{pmatrix} 0.831 \\ 0.175 \\ -0.061 \end{pmatrix}$$

 

이 $\hat{\mathbf{x}}$는 $A\mathbf{x} = \mathbf{b}$를 정확히 만족하지는 않지만, $\lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert$를 가능한 모든 $\mathbf{x}$ 중에서 가장 작게 만드는 값이다.

 

---

 

최소제곱해가 가장 직접적으로 사용하는 곳은 선형회귀(linear regression)이다. 데이터 행렬 $A$, 타겟값$y$가 주어졌을 때 $\mathbf{y} = A\mathbf{w}$를 만족하는 가중치 $\mathbf{w}$를 찾는 문제에서, 데이터가 완벽한 선형 관계를 갖지 않으므로 정확한 해는 없다. 이때 최소제곱해 $\mathbf{w} = (A^TA)^{-1}A^T\mathbf{y}$가 오차를 최소화하는 최적의 가중치가 된다. 이 공식이 바로 OLS(Ordinary Least Squares, 최소제곱해를 선형회귀 맥락에서 부르는 용어)의 닫힌 형태(closed-form) 해이다. 로지스틱 회귀에선 $\hat{y} = \frac{1}{1 + e^{-(A\mathbf{w} + b)}}$처럼 비선형 변환이 추가되어 닫힌 형태의 해가 존재하지 않으므로, 경사 하강법 등의 반복적 최적화가 필요하다.