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

Intro

SVD는 1800 후반에 수학적으로 발견되었으며 (by. Eugenio Beltrami) 강체의 회전 운동 분석뿐만 아니라 행렬 처리가 들어가는 대부분의 분야, 특히 컴퓨터의 발전으로 SVD개념이 통계나 데이터 사이언스 분야 (ex. text mining, recommend system) 및 영상처리 (image processing), 분류 문제 (classification problems) 등 다양한 분야에서 필수적인 개념으로 사용되고 있습니다. 

Eugenio Beltrami

 

Definition of Singular Value Decomposition

Singular Value Decomposition은 행렬 분해 (Matrix Factorization) 방식 중에 하나로서 해당 방법은 행과 열이 다른 (m x n) 행렬 A에 대해서 직교 행렬 (orthogonal matrix)과 대각 행렬 (diagonal matrix)로 분해하는 방법입니다.   

1. U Matrix: SVD 결과를 통해서 얻어진 U는 AA^T 행렬로부터 얻어진 orthonormal eigenvector로 이뤄진 matrix입니다. U의 열 벡터 들을 A의 left singular vector라 부릅니다.

2. V Matrix: V행렬은 (A^T)A 행렬로부터 얻어진 orthonormal eigenvector로 이뤄진 matrix이며 V의 행렬의 열 벡터들을 A의 right singular vector라고 부릅니다.

3. Σ Matrix: Σ 행렬은 AA^T와 (A^T)A 행렬에서 나오는 고윳값 (eigenvalue)들의 square root를 대각 원소로 하는 행렬입니다. 그림에는 r x r 크기로 정방 행렬일 수도 있고 또는 직사각 행렬이 될 수도 있습니다. 

 

Why & Characteristic of Singular Value Decomposition 

SVD의 특징이자 장점은 정방행렬 뿐만아니라 행과 열의 길이가 다른 행렬에 대해서 적용이 가능하다는 점입니다. 고윳값 분해 (Eigenvalue Decomposition)는 정방 행렬에 대해서만 가능합니다. 

고유값 분해 (Eigenvalue Decomposition)

또한 고유값 분해를 통해서 얻어진 P는 항상 orthogonal하지 않습니다. 하지만 SVD는 나아가 차원의 길이가 다른 행렬에서도 적용이 가능합니다 (more useful).

또한 SVD를 이용하는 중요한 의미는 차원을 줄이는 기능에 있습니다 (dimension reduction). 데이터를 노멀 라이즈 (normalize)할 뿐만 아니라 여분의 데이터 (redundant data)를 제거하는 기능을 가지고 있는데요. 

우선 SVD의 일반화된 결과를 먼저 보겠습니다.  

Generalization of SVD result

선형 결합으로 이뤄지며 각각의 벡터 곱은 (e.g. u1 * v1) 행렬을 만들게 됩니다. 그러나 u와 v 벡터는 단위 벡터이기 때문에 성분의 값은 -1~1 사이의 값을 가지게 되므로 singular value가 결국 행렬의 크기를 나타내게 됩니다. 

이와 같이 SVD는 A라는 하나의 행렬을 eigenvalue에 따른 여러개의 선형 결합으로 표현하는 데에 있어 매우 중요한 의미를 가집니다. 즉 선형 결합이 가능하다는 것은 몇 개의 특이값을 가지고 A라는 행렬을 부분 복원이 가능하다는 것이며, A의 정보량에 대해서 필요 없는 것은 제거하고 몇 개의 특이값이 큰 값들을 이용하여 A가 가진 유용한 정보를 유지할 수 있다는 점입니다. 

때문에 정보들의 합에서 필요한 정보들을 추출해서 필요한 정보들만 보여줄수있으며 그 방법에는 아래와 같이 여러 타입이 존재합니다.

*s = singular value 개수, r = singular value 중 0이 아닌 원소 개수

1) full SVD

위에서 설명된 내용들은 모두 full SVD이며 A행렬이 SVD를 진행하였을때 얻는 그대로의 과정을 의미합니다. 

2) Thin SVD

Thin SVD는 Σ 행렬에서 대각 원소가 아닌 0으로 구성된 부분이 제거되었으며 이에 따라서 U에서 제거된 부분과 대응되는 열 벡터들이 제거된 U_s 로 이뤄지는 SVD를 의미합니다. 

3) Compact SVD

Compact SVD는 대각선에 위치하지 않은 원소들을 제거할 뿐만 아니라 0인 singular value까지 제거된 SVD를 의미합니다. 

4) Truncated SVD

Truncated SVD는 Σ 행렬의 대각원소 가운데 상위 t개만 골라낸 형태입니다. 해당 방법은 행렬 A를 원복 하지 못하게 되지만 데이터를 상당히 압축해도 행렬 A에 근사할 수 있는 장점이 있습니다. 

*1)을 제외한 2), 3), 4)는 reduced SVD라고 불리며 각 행렬마다 0 성분들을 제거하기 때문에 메모리를 절약하고 원본의 형태를 유지하는 정보 압축에 의의가 존재합니다. 

 

 

Applications of SVD

1) Image compression

이미지 처리에서 예를 하나 보겠습니다.  

C라는 행렬의 SVD 결과에서 일부분만 이용하여 C'이라는 부분행렬 (빨간색) 또는 부분 정보를 이용할 때 이미지 처리에서 어떠한 결과가 나오는지 보겠습니다. 아래는 파인만 (과학자) 사진입니다. 

과학자 파인만 사진이 가진 정보량의 rank가 original일때, 이때 rank가 1, 10, 50일 때 를 비교한 사진입니다. singular value를 더 많이 사용할수록 원래 사진이 보여주려고 하는 대상이 누군지 더 근접해지는 것을 알 수가 있었습니다. 

2) Least Square (LS)

최소자승법 문제는 Ax=b를 만족하는 x를 찾는 문제이며, 실제 문제들은 정확하게 A라는 행렬이 역행렬을 가질 수 없는 경우가 많기에 이때 pseudo inverse를 이용하여 x에 근사할 수 있었습니다.

그러나 역행렬 계산은 정방행렬에 의해서 정의되지만 pseudo inverse는 직사각 행렬에 대해서도 계산이 가능합니다. 그리고 이 과정에서 SVD는 pseudo inverse를 계산하는 안정적인 방법 중 하나입니다.  

 

3) Principal Component Analysis (PCA) 

PCA는 데이터의 분산을 최대한 보존하면서 서로 직교하는 새 기저를 찾아서 고차원 공간의 표본들을 선형 연관성이 없는 저 차원 공간으로 변환하는 기법입니다. 즉 새로운 축으로 데이터를 해석하기 위해서 사용되며 최적의 feature를 선택한다고 하여서 Feature Dimension Reduction이라고도 부릅니다.

이때 새로운 축 (axis)를 찾기 위해서 고유값 분해를 수행 줘야 하며 이때 SVD가 사용됩니다. 

 

4) Latent Semantic Analysis (LSA) 

LSA는 잠재의미분석이라는 의미로 문장에서 잠재되어 있는 의미를 찾아내는 기법입니다. 이때 잠재되어 있는 의미를 찾기 위해서 SVD가 사용되며 대략적인 절차는 다음과 같습니다. X라는 행렬에서 행은 문서 (또는 문장)을 의미하며, 열은 단어를 의미하며, 이때 행렬의 값은 word가 각 document에 몇 번 있는지를 보여주고 있습니다. 

해당 행렬을 Truncated SVD를 통해서 Rank수에 따른 차원을 축소시킴으로써 문서 1과 문서 2가 얼마나 유사한지, 얼마나 연관이 있는지 등 분석을 하기 위한 밑바탕을 마련해줄 수 있습니다. 

 

Geometrical meaning of SVD (SVD의 기하학적 의미) 

SVD는 다음과 같은 의미를 지니고 있습니다. 

직교하는 벡터 집합인 직교 행렬은 선형 변환 중에서 회전 변환을 의미합니다 - U, V (아래와 같이 해당 행렬은 각 벡터는 직교하면서 크기는 1인 벡터로 구성되었으며 각도에 따라서 2차원 점을 회전시킬수 있습니다) 

Rotation matrix

또한 대각선에만 성분이 존재하는 대각 행렬은 크기 (Scale) 변환을 하는 기능을 가지고 있습니다 - ∑.

정리하면 A라는 행렬은 SVD를 통해서 아래와 같은 식이 나오게 되는데, 먼저 (V^T)를 통해서 회전 변환 (Rotate)이 수행되고, ∑가 곱해지면서 스케일 변환 (Stretch)이 되고, 마지막으로 U를 통해서 회전 변환 (Rotate)가 수행되게 됩니다.  

How? (with simple example)

예시를 통해서 SVD과정이 어떻게 진행되는지 보겠습니다. 행렬 A가 있을때 이를 SVD 한 결과를 계산하기 위해서 과정은 다음과 같습니다. 

1. U (Left singular vector) 구하기 

1-1. A(A^T)를 계산하고 해당 행렬의 eigenvalue를 이용한 singular value를 계산합니다. 

 이때 eigenvalue는 25와 9가 되므로 singular value는 root를 씌워준 결과로 아래와 같습니다.

 

1-2. 위에서 얻은 eigenvalue를 이용한 eigenvector를 계산하여 U 행렬을 완성합니다. 

이때 각각의 eigenvalue에 해당하는 eigenvector는 정규화 과정을 진행하여 벡터 크기가 1인 단위 벡터로 만들어야 합니다. 

벡터 정규화

1열은 λ = 25에 해당하는 eigenvector이며, 2열은 λ = 9에 해당하는 eigenvector입니다. 

2. V (Right singular vector) 구하기 

2-1. (A^T)A를 계산하고 해당 행렬의 eigenvalue를 이용한 singular value를 계산합니다. 

이때 eigenvalue는 25와 9 그리고 0이 되므로 singular value는 root를 씌워준 결과로 아래와 같습니다.

 

2-2. 위에서 얻은 eigenvalue를 이용한 eigenvector를 계산하여 V 행렬을 완성합니다. 

이때 각각의 eigenvalue에 해당하는 eigenvector는 정규화 과정을 진행하여 벡터 크기가 1인 단위 벡터로 만들어야 합니다.

1행은 λ = 25에 해당하는 eigenvector이며, 2행은 λ = 9에 해당하는 eigenvector입니다. 

 

3. Σ 행렬 구하기

3-1. Σ는 A(A^T)행렬과 (A^T)A 행렬의 고윳값들에 square root를 취하여 대각 행렬을 얻습니다. 

 

*계산 결과

 

Reference

[1] https://en.wikipedia.org/wiki/Singular_value_decomposition