Sherman-Morrison formula와 RLS

선형 대수도 거의 다 끝났다. 크하하 이거 정리하면 앞으로 Matrix Inversion Lemma 하나 남았다.

이번에 정리할 내용은 1949년 셔먼과 모리슨이라는 수학자들이 발표한 공식으로 Recursive Least Squares라는 것을 해결하는데 도움이 된다.

 

Sherman-Morrison Formula

Sherman-Morrison Formula란 invertible한(역행렬이 존재하는) 행렬 $A$와 $\textbf{u}, \textbf{v} \in \R^n$인 두 열 벡터가 있을때 $A+\textbf{uv}^T$의 역행렬을 구하는 공식이며 아래와 같다.

$$
(A + \textbf{uv}^T)^{-1} = A^{-1} - \frac{A^{-1}\textbf{uv}^TA^{-1}}{1 + \textbf{v}^TA^{-1}\textbf{u}}
$$

이러한 공식들은 항상 분모가 0이 아니라는 보장을 해준다. 즉, $1 + \textbf{v}^TA^{-1}\textbf{u} \neq 0$이라는 것이며 이는 $A+\textbf{uv}^T$가 역행렬이 존재하다는 것을 의미한다.

 

응용 Recursive Least Squares

결국 응용은 또 최소 제곱법이다. ㅋㅋㅋ 근데 이걸 Recursive하게 해야 할 경우 Sherman Morrison Formula를 쓰면 계산을 더 적게 하여 최소 제곱법을 재귀적으로 할 수 있다. 그렇다면 최소 제곱법을 재귀적으로 사용해야하는 경우가 어떤게 있을까?

 

바로 선형 회귀를 통해 특정 데이터 셋에 대해서 회귀를 할 때이다.

데이터의 feature의 역할을 하는 행렬 $A$, 이 행렬에 적절한 coefficient $x$, 마지막으로 우리가 예측해야할 레이블 $b$가 존재할 때 우리는 선형 회귀를 통해 $Ax \approx b$에 적합한 $x$를 구한다.

 

이때 하나의 데이터가 더 추가된다면 다시 선형 회귀를 수행해주어야 하는데 이전 계산 정보가 너무 아깝다. 이때 사용할 수 있는 공식이 바로 Sherman Morrison Formula다.

 

먼저 지금까지 많이 해본 것처럼 $x =(A^TA)^{-1}A^Tb$이다.

이때 $A$의 밑에 한 줄이 추가되는 것으로 $\begin{bmatrix}
A\
a^T
\end{bmatrix}$가 된다. 이를 $x =(A^TA)^{-1}A^Tb$에 대입하면 다음과 같다.

$$
\begin{align}
x_a &= (\begin{bmatrix}
A^T & a\end{bmatrix}
\begin{bmatrix}
A \\
a^T
\end{bmatrix}
)^{-1}
\begin{bmatrix}
A^T & a
\end{bmatrix}b \\
&= (A^TA + aa^T)^{-1}(A^Tb + ab)
\end{align}
$$

여기서 $(A^TA + aa^T)^{-1}$에 sherman Morrison formula를 사용해주면 쉽게 구할 수 있다.

$$
(A^TA + aa^T)^{-1} = (A^TA)^{-1} - \frac{(A^TA)^{-1}aa^T(A^TA)^{-1}}{1 + a^T(A^TA)^{-1}a} = P_a
$$

위 식을 $P_a$라 칭하고 이를 이전 식에 대입하면 다음과 같다.

$$
\begin{align}
x_a &= (A^TA + aa^T)^{-1}(A^Tb + ab) \\
&= ((A^TA)^{-1} - \frac{(A^TA)^{-1}aa^T(A^TA)^{-1}}{1 + a^T(A^TA)^{-1}a})(A^Tb + ab) \\
&= (A^TA)^{-1}A^Tb - \frac{(A^TA)^{-1}aa^T(A^TA)^{-1}}{1 + a^T(A^TA)^{-1}a}(A^Tb) + P_aab
\end{align}
$$

이때 맨 앞의 $(A^TA)^{-1}A^Tb = x$.

두번째 항인 $\frac{(A^TA)^{-1}aa^T(A^TA)^{-1}}{1 + a^T(A^TA)^{-1}a}(A^Tb)
= \frac{(A^TA)^{-1}a}{1 + a^T(A^TA)^{-1}a}a^T(A^TA)^{-1}(A^Tb)
= \frac{(A^TA)^{-1}a}{1 + a^T(A^TA)^{-1}a}a^Tx$이다. 이때 $a^Tx$의 계수인 $\frac{(A^TA)^{-1}a}{1 + a^T(A^TA)^{-1}a} = P_aa$이다. (아래 수식 참고.)

$$
\begin{align}
P_a a &= (A^TA)^{-1}a - \frac{(A^TA)^{-1}aa^T(A^TA)^{-1}a}{1 + a^T(A^TA)^{-1}a} \\
&= \frac{(A^TA)^{-1}a + (A^TA)^{-1}aa^t(A^TA)^{-1}a -(A^TA)^{-1}aa^T(A^TA)^{-1}a}{1 + a^T(A^TA)^{-1}a} \\
&= \frac{(A^TA)^{-1}a}{1 + a^T(A^TA)^{-1}a}
\end{align}
$$

즉, 다시 써보면 아래와 같다.

$$
x_a = x-P_aaa^Tx + P_aab = x + P_aa(b - a^Tx)
$$

즉, 기존 $x$에 대해 우린 이미 계산했으면, 여기에 $x = (A^TA)^{-1}A^Tb$$x$$(A^TA)^{-1}$과 새로운 데이터 $a,b_{new}$를 이용해 행렬의 곱셈과 덧셈을 이용해 새로운 $x_a$를 구할 수 있다.

 

이 방식을 이용하지 못하면 행렬의 역행렬을 구하기 위해서는 가우스-조던 소거법을 사용하면 $O(n^3)$이 걸리게 되지만, 위 방식을 사용하면 데이터가 1개 추가될 때 다시 계산하지 않아도 되고 필요한 연산은 곱셈과 덧셈 뿐이기에 $O(n^2)$의 시간복잡도를 가진다.

 

하지만 1개의 데이터만 추가될 때만 가능하다는 점이 치명적이다. 이렇게 여러 개의 데이터가 추가될 때는 Sherman–Morrison-Woodbury formula라는 확장 버전이 존재한다. 이는 다음 장에 알아보도록 하자.

 

Reference

• 혁펜하임 유튜브
• 셔먼-모리슨-우드버리 공식(Sherman–Morrison-Woodbury formula)