[선형대수학] 특이값 분해 (SVD, Singular Value Decomposition)

데이터 과학은 SVD에서 선형대수학과 연결된다.
- 딥러닝을 위한 선형대수학, 길버트 스트랭 저

이전 포스팅에서 고유값 분해에 대해 알아보았다. 하지만 우리가 대부분 다루게 될 행렬은 정사각행렬이 아닌 경우가 많을 것이다. 그렇다면 어떻게 해야할까?

특이값 분해(SVD, Singular Value Decomposition)

정사각 행렬을 대상으로 하는 고유값 분해를 mXn 행렬로 일반화한 것을 특이값 분해라고 한다. 

수식으로는

$$A = U\Sigma V^T$$

으로 표현한다.

특이값 분해는 행렬의 차원 축소를 위한 도구로 주로 사용하며, 최소제곱(least squares)에서 최적의 $\hat{a}$ 를 찾고, PCA에서 주성분인 $v_1$를 계산하는 것은 데이터 fitting의 대수적 문제이다.

행렬 M의 크기가 $m \times n$이라는 말은 n차원에서 m개의 점이 있다고 생각 가능하다. M에 대한 차원 축소란 m개의 점으로 표현할 수 있는 n보다 작은 차원의 부분공간을 찾는 문제라고 할 수 있는데 이때 데이터와 부분공간의 수직거리를 최소화한다. 이때 최소제곱을 사용해 구하게 된다.

특이값분해의 대표적인 식에서는 벡터 U와 V라는 집합이 필요한데 $m \times n$ 실수 행렬이 있을 때 n개의 우특이벡터 $v_1, ... , v_n$은 %R^n%에서 직교이다. m개의 좌특이벡터 $u_1, ... u_m$ 역시 %R^m%에서 직교이다. 위 벡터들은 이전 고유값 분해에서의 $Av =  \lambda x$의 관계를 만족하지 않는다. 특이벡터에서는 $Av =  \sigma x$의 관계를 만족해야한다.

$$Av_1 = \sigma_1u_1 \\ Av_r = \sigma_ru_r \\ Av_{r+1} = 0 \\ Av_{n} = 0 $$

먼저 r개의 v와 u를 나머지와 분리한다. r의 A의 랭크인데, 독립인 열(과 행)의 개수. r의 열(행)공간의 차원이다. 이를 내림차순으로 정리한다고 하면 

$$ \sigma_1  \geq  \sigma_2  \geq ... \geq \sigma_r > 0$$

이며 r개의 양수 특잇값을 가지게 된다. v의 마지막 n-r개는 A의 영공간이고 u의 마지막 m-r개는 $A^T$의 영공간이다.

위 식을 행렬 형태로 쓰면

$$AV = U\Sigma \\ A\begin{bmatrix}v_1 \cdots v_r \cdots v_n \end{bmatrix} =\begin{bmatrix}u_1 \cdots u_r \cdots u_m \end{bmatrix} \begin{bmatrix}\sigma_1 & & & 0\\ &  \ddots & & 0  \\ & & \sigma_r & 0\\ 0 & 0 & 0 & 0\end{bmatrix} $$

이 된다.

위 식에서 처음 r개의 열은 $Av_k = \sigma_ku_k$가 성립함을 알 수 있다. 앞의 r개의 u, v 쌍에 대해 v는 A의 행공간의 기저, u는 열공간의 기저다. 나머지 0은 A와 $A^T$의 영공간에서 왔다.

V의 열은 서로 직교이고 U의 열 또한 서로 직교이다. 따라서 둘은 직교행렬이고 $V^T = V^{-1}, U^T = U^{-1}$가 성립한다.

따라서 $AV =U\Sigma$의 양변에 $V^{-1} = V^T$를 곱할 수 있고 그렇게 되면 위에서 말한 일반적인 식이 나오게 된다.

$$A = U\Sigma V^T$$

from scipy.linalg import svd
import numpy as np
A = np.random.randn(4, 4)

print(np.round(A, 3))

U, s, VT = svd(A)
print(U.shape, s.shape, VT.shape)
print('U matrix: \n', np.round(U, 3))
print('Sigma matrix: \n', np.round(s, 3))
print('VT matrix: \n', np.round(VT, 3))

sigma_mat = np.diag(s)
A_ = np.dot(np.dot(U, sigma_mat), VT)
print(np.round(A_, 3))

원본 행렬로 복원됨을 확인할 수 있음

Reduced SVD

적정 비율의 차원(k)을 선택하여 연산량을 줄일 수 있다. 특이값들 중에서 0인 것들을 제외하고 SVD를 진행하는 것을 reduced SVD라고 한다. 위에 행렬에서 0을 제외하는 SVD를 의미한다.

Truncated SVD

특잇값 가운데 가장 큰(가장 중요한) t개만 남기고 해당 특잇값에 대응되는 특이행렬(singular vector) 로 행렬 A를 근사(approximate)한 것이다. 이를 사용하게 될 경우 원본 행렬을 정확하게 복원할 수는 없지만 근사할 수 있다. 추천 시스템의 랭킹, NLP의 잠재의미분석에서 주로 사용된다.

$\Sigma$의 대각원소 중에 상위 몇개만 추출해서 여기에 대응하는 U와 V의 원소도 함께 제거한다. 

import numpy as np
from scipy.sparse.linalg import svds
from scipy.linalg import svd

matrix = np.random.random((6, 6))
print('원본 행렬 : \n', matrix)

U, Sigma, Vt = svd(matrix, full_matrices=False)
print('\n분해 행렬 차원: ', U.shape, Sigma.shape, Vt.shape)
print('\nSigma Matrix:\n', Sigma)

num_components = 4
U_tr, Sigma_tr, Vt_tr = svds(matrix, k=num_components)

print('\nTruncated SVD 분해 행렬 차원: ', U_tr.shape, Sigma_tr.shape, Vt_tr.shape)
print('\nTruncated SVD Sigma Matrix:\n', Sigma_tr)
matrix_tr = np.dot(np.dot(U_tr, np.diag(Sigma_tr)), Vt_tr)

print('\nTruncated SVD 분해 후 복원 행렬: \n', matrix_tr)

SVD, Reduced SVD, Truncated SVD 비교

https://math.stackexchange.com/questions/2627005/are-reduced-svd-and-truncated-svd-the-same-thing

특이값 분해의 활용

1. PCA(주성분 분석), LDA(선형 판별 분석법)에서 고유값과 고유벡터를 구하기 위해 사용
2. Face recognition에서 얼굴 추출을 위해 PCA, 얼굴 분류를 위해 LDA를 사용
3. 이상치 탐지를 위해 PCA를 사용
4. 토픽 모델링 중 LSA에서 특이값 분해를 사용해 설명력이 낮은 정보를 삭제하고 설명력이 높은 정보를 남김
5. 추천 시스템에서 SVD를 통해 평점 도출 가능