🗄️ SVD: Singular Value Decomposition

특이값 분해는 고유값 분해를 일반적인 상황으로 확장시킨 개념으로 LSA(Latent Semantic Anaylsis), Collaborative Filtering과 같은 머신러닝 기법에 사용되기 때문에 자연어처리, 추천시스템에 관심이 있다면 반드시 이해하고 넘어가야 하는 중요한 방법론이다. 혁펜하임님의 선형대수학 강의와 공돌이의 수학정리님의 강의 및 포스트 그리고 딥러닝을 위한 선형대수학 교재을 참고하고 개인적인 해석을 더해 정리했다.

🌟 Concept of SVD

\[A = UΣV^T\]

크기가 mxn인 임의의 행렬 $A$를 위 수식의 우변처럼 여러 다른 행렬로 분해하는 방법을 말한다. 행렬 분해 기법이라는 점에서 고유값 분해와 궤를 같이하지만 좀 더 실용적인 형태로 변화했다. 고유값 분해는 행렬 $A$가 정사각행렬 일 때만 적용할 수 있다는 한계를 가지고 있다. 실생활에서 다루는 행렬 모형의 테이블 데이터는 99.9999999%의 확률로 직사각행렬이다. 필자는 살면서 한 번도 정사각행렬 형태의 테이블 데이터를 본적이 없다. 즉 실생활의 데이터에 고유값 분해를 적용하기 위해 직사각행렬 형태로 확장한 것이 바로 특이값 분해다.

선형변환 $A$ 가 다음과 같다고 가정하고 구체적인 예시와 함께 우변의 항들에 대해 자세히 살펴보자.

\[A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{pmatrix}\]

먼저 행렬 $U$는 크기가 mxm인 정사각행렬이다.

\[U = \begin{pmatrix}-0.2298 & 0.8835 & 0.4082 \\-0.5247 & 0.2408 & -0.8165 \\-0.8196 & -0.4019 & 0.4082\end{pmatrix}\]

고유값 분해에서 고유벡터를 쌓아 만든 행렬 $V$와 비슷한 역할을 하면서 특이값 행렬의 왼족에 있다는 의미에서 Left Singular Vector라고도 부른다. 행렬의 개별 열차원의 벡터는 고유한 특이벡터가 된다. 따라서 개별 고유벡터는 서로에게 독립이며 직교한다. 따라서 전체 행렬 $U$는 Orthogonal Matrix가 된다.

한편, $Σ$는 개별 특이벡터에 해당되는 특이값들을 저장한 행렬로 크기는 mxn이다.

\[\Sigma = \begin{pmatrix} \sigma_1 & 0 \\ 0 & \sigma_2 \\ 0 & 0 \end{pmatrix}\]

현재 제시된 예시 행렬의 크기가 m>n이기 때문에 $Σ$의 모양 역시 행 방향으로 더 길게 놓인 직사각행렬이 된다. 반대의 상황이라면 열방향으로 길게 누적된 직사각행렬이 될 것이다. 또한 $Σ$은 직사각행렬이지만 대각행렬이라서, 주대각성분 원소를 제외한 나머지 원소는 모두 반드시 0이 된다.

마지막으로 행렬 $V^T$는 크기가 nxn인 정사각행렬이다.

\[V^T = \begin{pmatrix}-0.6196 & -0.7849 \\-0.7849 & 0.6196\end{pmatrix}\]

행렬 $U$때와 같은 논리와 더불어 특이값 행렬의 오른족에 배치되어 있기 때문에 Right singular Vector 라고 부른다. 마찬가지로 개별 고유벡터는 서로에게 독립이며 직교한다. 따라서 전체 행렬 $V^T$역시 Orthogonal Matrix가 된다.

그렇다면 특이값 분해는 어떻게 고유값 분해의 제약조건을 탈피했는지 살펴보자. 바로 크기가 mxn인 행렬 $A$와 그것의 전치 행렬 $A^T$ 사이의 곱은 항상 대칭 행렬이 되고, 대칭행렬은 대각화-가능 행렬이라는 점을 이용한다.

\[A•A^T = UΣV^T•VΣ^TU^T = UΣΣ^TU^T \\ A^T•A = VΣ^TU^T•UΣV^T = VΣ^TΣV^T\]

새롭게 정의된 행렬 $A•A^T$은 크기가 mxm인 정사각•대칭행렬이 되고, 행렬 $A^T•A$은 크기가 nxn인 정사각•대칭행렬이 된다. 행렬 $U,V$ 모두 Orthogonal Matrix 라는 점을 이용하면 우리는 새롭게 정의된 두 행렬을 고유값분해 결과와 유사하게 나타낼 수 있다.

\[A•A^T = Q_m \Lambda_m Q^T_m \\ A^T•A = Q_n \Lambda_n Q^T_n\]

수식 우변에 놓인 $\Lambda_m, \Lambda_n$ 의 구체적인 예시는 다음과 같다.

\[\Lambda_m = \Sigma\Sigma^T = \begin{pmatrix} \sigma_1^2 & 0 & 0 \\ 0 & \sigma_2^2 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \\ \Lambda_n = \Sigma^T\Sigma = \begin{pmatrix} \sigma_1^2 & 0 \\ 0 & \sigma_2^2 \\ \end{pmatrix}\]

이제 두 행렬에 각각 양의 제곱근을 사용해 $\sigma_1, \sigma_2$(특이값)를 구하고 원래 수식($A = UΣV^T$)의 $Σ$에 대입한다. 이렇게 하면 선형변환 $A$에 대한 특이값 분해를 모두 끝마친 셈이다. 지금까지 살펴본 내용을 요약 정리하면 다음과 같다.

• 1) $AA^T, A^TA$ 계산
• 2) $AA^T, A^TA$의 고유값, 고유벡터 계산
• 3) $A^TA$로 Right Singular Vector $V$를, $AA^T$로 Left Singular Vector $U$를 도출
• 4) 고유값($\Sigma\Sigma^T$)의 제곱근에서 나온 값들을 $\Sigma$의 대각선에 배치합니다. 이 값들이 특이값에 해당

💡 Insight of SVD

\[A\vec x = \sigma_1u_1v_1^T\vec x + \sigma_2u_2v_2^T\vec x + ... +\sigma_n u_nv_n^T\vec x\]

고유값 분해의 활용과 사실상 다른게 없다. 역시 데이터 압축•복원 혹은 PCA 같은 차원 축소 기법에 사용된다. 고유값 분해와 다른게 있다면 선형변환 $A$가 반드시 정사각행렬일 필요가 없다는 것이다. 그리고 고유값 분해를 데이터 압축이나 차원 축소에 간편히 사용하려면, 선형변환 $A$가 대칭행렬이여야 한다는 조건도 붙고 상당히 사용하게 까다로웠는데 특이값 분해에서는 그런 번거로운 제약 조건이 모두 사라진다는 장점이 있다.

특히 특이값 분해는 분해되는 과정 자체보다 분해되는 행렬을 개별 특이벡터에 대한 특이값의 가중합 방식으로 조합하는 과정에서 그 빛을 발한다. 특이값에 $argmax$를 적용해 상위 p개의 특이벡터만 반영한 부분 행렬 $A$를 이용할 수도 있고, 필요에 따라서 다시 p개의 개수를 늘려 원본으로 복원하는 것도 가능해진다. 이러한 기능이 가장 빛을 발하는 분야가 이미지 해상도 압축•복원 분야다. 현재 내가 사용하려면 이미지의 해상도가 너무 높아서 용량이 커져 사용하기 어렵다면 SVD를 이용해 필수적인 특이벡터 몇개만 남겨놓는 방식으로 해상도 압축을 수행해 용량을 줄일 수 도 있다. 공돌이의 수학정리님의 포스트 하단부에 정말 직관적으로 잘 만들어진 사례가 있으니 꼭 한 번씩 보고 오시길 권장한다.