의심으로 가득 찬 마음은 승리로의 여정에 집중할 수 없다.
- 아서 골드 -
이번 포스팅에서 다룰 내용은 행렬 분해 (Matrix factorization)입니다. Matrix Factorization은 데이터를 분석하고 모델링하는데 널리 사용되는 방법 중 하나입니다. 이 방법은 매우 큰 데이터 집합에서 숨겨진 패턴을 추출하고, 예측 모델을 생성하고, 더 나은 결과를 도출할 수 있는 방법을 제공합니다.
이 방법은 행렬을 작은 크기의 더 간단한 행렬로 분해하여 데이터의 복잡성을 줄이는 방법입니다. 이렇게하면 복잡한 문제를 해결하는 데 더 간단한 알고리즘을 사용할 수 있으며, 더 나은 성능을 얻을 수 있습니다.
이번 포스팅은 이전 개념을 숙지하고 공부하시는 것을 권장드립니다.
[문과도 이해하는 선형대수 for 딥러닝] 3. 행렬곱, 역행렬, 가우스-조던 소거법 (Multiplication and Inve
늘 명심하라. 성공하겠다는 너 자신의 결심이 다른 어떤 것보다 중요하다는 것을. - 아브라함 링컨 - 곱셈(multiplication)과 역행렬(inverse matrix)은 선형 대수학에서 가장 기본이 되는 연산 중 하나입
box-world.tistory.com
1. 역행렬에 대한 리뷰 (Review of inverse matrix)
여기 곱하면 $P$가 나오는 두 행렬 $A$와 $B$가 있습니다.
$$A \times B = P$$
각 행렬에 대한 역행렬이 존재한다고 가정할 때, 행렬 $AB$에 대한 역행렬은 무엇일까요? 물론 $A^{-1}$과 $B^{-1}$가 곱해진 형태겠지만 중요한건 곱하는 순서도 함께 역으로 바뀌며 $B^{-1}A^{-1}$이라는 것입니다.
이것은 마치 우리가 집에 돌아오면 1) 신발을 벗고 2) 양말을 벗는데, 다시 집밖으로 나갈땐 2) 양말을 신고 1) 신발을 신는 것과 같은 맥락입니다^^.
마찬가지로 $A \times A^{-1}=I$를 전치 (transpose) 시킨다면 마찬가지로 앞 뒤 순서가 바뀌어 다음과 같이 나타납니다.
$$(A^{-1})^TA^T=I$$
당연하겠지만, 단위 행렬은 전치를 해도 여전히 단위 행렬입니다! 어쨌든 여기서 우리가 얻을 수 있는 것은 $(A^{-1})^T$와 $A^T$를 곱했을 때 $I$가 나왔기 때문에 이 둘은 역행렬 관계라는 겁니다.
2. $A =LU$
이제 우리는 본격적으로 행렬 분해 (Matrix factorization)에 대해 살펴보려합니다. 우선 그전에 소거 행렬 (Elimination matrix)에 대해 간단히 짚고 가겠습니다.
$$\begin{bmatrix}-&-\\-&-\end{bmatrix}\begin{bmatrix}2&1\\8&7\end{bmatrix}=\begin{bmatrix}2&1\\0&3\end{bmatrix}$$
위 식에 대하여, 좌변의 행렬에 어떤 Elimination matrix를 곱하여 우변처럼 Upper triangle matrix의 형태로 나타내고 싶다면 Elimination matrix는 어떤 형태가 되어야할까요?
좌변 행렬의 첫번째 row는 그대로 유지되고 두번째 row의 경우 $\begin{bmatrix}0&3\end{bmatrix}$이 되어야 하므로 [첫번째 row의 (-4)배 +두번째 row의 (1)배]를 해야하므로 Elimination matrix는 $\begin{bmatrix}1&0\\-4&1\end{bmatrix}$가 되고 지금부터 이를 2번째 row의 첫번째 component를 0으로 만드는 행렬이라는 의미로 $E_{21}$이라고 정의합니다.
아래 식은 $E_{21}A=U$의 형태이고,
$$\begin{bmatrix}1&0\\-4&1\end{bmatrix}\begin{bmatrix}2&1\\8&7\end{bmatrix}=\begin{bmatrix}2&1\\0&3\end{bmatrix}$$
또 하나의 아래 식은 $A=LU$ 형태의 식입니다.
$$\begin{bmatrix}2&1\\8&7\end{bmatrix}=\begin{bmatrix}-&-\\-&-\end{bmatrix}\begin{bmatrix}2&1\\0&3\end{bmatrix}$$
그렇다면 $L$은 직관적으로 $E_{21}$의 역행렬이라는 것을 알 수 있습니다! 그렇다면 이는 어떻게 구할까요? 그냥 $E_{21}$에서 -4를 4로 바꿔주면 됩니다! 왜냐하면 $E_{21}$이 4배를 빼는 거였는데, 역행렬은 이를 되돌리는 것이기 때문입니다. 그렇기에 부호만 바꾸면 되는 것입니다.
$$\begin{bmatrix}2&1\\8&7\end{bmatrix}=\begin{bmatrix}1&0\\4&1\end{bmatrix}\begin{bmatrix}2&1\\0&3\end{bmatrix}$$
위 식에서 $U$의 pivot을 빼내면 다음과 같이 표현할 수 있습니다. pivot을 빼내면 $U$의 첫번째 row는 2로, 2번째 row는 3으로 나눠주는 것입니다.
$$\begin{bmatrix}2&1\\8&7\end{bmatrix}=\begin{bmatrix}1&0\\4&1\end{bmatrix}\begin{bmatrix}2&0\\0&3\end{bmatrix}\begin{bmatrix}1&1\over2\\0&1\end{bmatrix}$$
이제 $2 \times 2$의 경우를 봤으니 $3 \times 3$의 경우도 살펴보겠습니다. 그렇다면 $3 \times 3$ 행렬 $A$가 다음과 같을때
$$A=\begin{bmatrix}(1,1)&(1,2)&(1,3)\\(2,1)&(2,2)&(2,3)\\(3,1)&(3,2)&(3,3)\end{bmatrix}$$
행렬 $A$를 Upper triangle matrix $U$의 형태로 바꿔주는 Elimination matrix들의 조합은 다음과 같이 표현할 수 있습니다.
$$E_{32}E_{31}E_{21}=U$$
각각은 행렬 $A$의 $(3,2),(3,1),(2,1)$ 자리를 0으로 만들어줍니다. 이것을 $A=LU$형태로 만들어주면, 다음과 같습니다.
$$A=E^{-1}_{21}E^{-1}_{31}E^{-1}_{32}U$$
그렇다면 자꾸 $E_{32}E_{31}E_{21}$을 그대로 처리하지 않고, $E^{-1}_{21}E^{-1}_{31}E^{-1}_{32}$의 형태로 바꾸어 처리하려는 것일까요? 다음은 $E_{32}E_{21}=E$의 경우를 임의로 살펴보겠습니다.
$$\begin{bmatrix}1&0&0\\0&1&0\\0&-5&1\end{bmatrix}\begin{bmatrix}1&0&0\\-2&1&0\\0&0&1\end{bmatrix}=\begin{bmatrix}1&0&0\\-2&1&0\\10&-5&1\end{bmatrix}$$
그리고 다음은 $E^{-1}_{32}E^{-1}_{21}=L$의 경우입니다.
$$\begin{bmatrix}1&0&0\\2&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&0\\0&1&0\\0&5&1\end{bmatrix}=\begin{bmatrix}1&0&0\\2&1&0\\0&5&1\end{bmatrix}$$
보다시피 일반 행렬의 곱셈과 달리, 역행렬의 곱셈의 경우 배수 2나 5와 같은 배수 부분이 결과로 도출되는 행렬 $L$에 그대로 위치하기 때문에 연산과정이 훨씬 단순해집니다!
결과적으로 만약 행 변환 (row change)가 없다면, 행렬 $A$를 Elimination하면 자연스럽게 $A$는 $LU$를 만들어내게 됩니다.
3. 소거에 대한 연산량 (Complexity of Elimination)
$n \times n$ 차원 행렬에 대해 Elimination을 위해 필요한 연산은 얼마나 클까요? $n=100$을 예로 들겠습니다. 처음에는 1st row는 두고 2nd row부터 $99 \times 100$의 성분에 대한 연산이 필요하니 $100^2$의 연산이 필요합니다. 이런식으로 반복되면 최종적으로는
$$n^2+(n-1)^2+\dots+2^2+1^2$$
가 됩니다. 즉 정석적으로라면, $n$개의 항복이 $n^2$이 되지만, $n$개의 항목이 점점 숫자가 작아지므로 대략 $1 \over 3 n^3$정도가 됩니다!
긴 글 읽어주셔서 감사합니다! 오늘도 행복한 하루 보내세요 :)