SVD의 기본 이론과 이해 및 활용

SVD (Singular Value Decomposition)

정의: 임의의 $m * n$ 차원 행렬 A에 대하여 다음과 같이 행렬 분해를 할 수 있다는 행렬 분해 방법 중 하나이다.

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

$A: m \times n$ rectangular matrix

$U: m \times n$ orthogonal matrix

$\Sigma : m \times n$ diagonal matrix

$V^T: m \times n$ orthogonal matrix

 

Pre-knowledge

Orthogonal matrix

- ortho~: 두 벡터가 직교한다.

- orthogonal vectors: 두 벡터의 내적 값은 0인 벡터들

- $UU^T = U^T U = 1$

$\therefore$ $U^T = U^{-1}$

 

Diagonal matrix

- 대각 성분을 제외한 모든 원소 값이 0인 행렬

ex) $ 2 \times 2 $ diagonal matrix

 

$$
    \begin{pmatrix}
    1 & x & x^2 \\
    1 & y & y^2 \\
    1 & z & z^2 \\
    \end{pmatrix}
$$

 

ex) $ 2 * 2 $ diagonal matrix (m > n)

$$
    \begin{pmatrix}
    \sigma_{1} & 0 & \cdots & 0 \\
    0 &  \sigma_{2} & \cdots &0\\
   &&\ddots \\
    0 &  0 & \cdots &\sigma_{n}\\
    0 &  0 & \cdots &0\\
    0 &  0 & \cdots &0\\
    \end{pmatrix}
$$

 

ex) $ 2 \times 2 $ diagonal matrix (m < n)

$$
    \begin{pmatrix}
    \sigma_{1} & 0 & \cdots & 0& \cdots &0 \\
    0 &  \sigma_{2} & \cdots &0 & \cdots & 0\\
   &&\ddots \\
    0 &  0 & \cdots &\sigma_{m} & \cdots & 0\\
    \end{pmatrix}
$$

 

Definition

2차원 벡터 공간에서의 예를 생각해보자.

$A$가 $2 \times 2$인 경우, 두 벡터 $\overrightarrow{x}, \overrightarrow{y}$에 대한 선형 변환 결과 $A\overrightarrow{x}, A\overrightarrow{y}$가 직교하게 되는 경우는 한번만 있는 것이 아니라 여러번 존재하게 된다.

선형 변환 후 각 벡터의 길이가 조금씩 커지거나 작아지는데, 이를 scailing factor라고 할 수 있고, 이를 일반적으로는 singular value라고 부른다.

singular value의 크기가 큰 것부터 $\sigma_{1}, \sigma_{2}, \cdots$ 등으로 부른다.

 

직교하는 벡터 $\overrightarrow{x}, \overrightarrow{y}$는 열벡터의 모음으로 생각할 수 있고, 이는 $V$에 해당한다.

$$V =  \begin{pmatrix}
\mid & \mid \\
\overrightarrow{x} & \overrightarrow{y} \\
\mid & \mid
\end{pmatrix}$$

 

$A\overrightarrow{x}, A\overrightarrow{y}$에 대하여 각각의 크기를 1로 정규화한 벡터를 $\overrightarrow{u_{1}}, \overrightarrow{u_{2}}$라 하면

$$U =  \begin{pmatrix}
\mid & \mid \\
\overrightarrow{u_{1}} & \overrightarrow{u_{2}} \\
\mid & \mid
\end{pmatrix}$$

 

그리고 여기서 singular value는 $\Sigma$로 묶어서 생각할 수 있다.

$$\Sigma = \begin{pmatrix}
\sigma_{1} & 0 \\
0 & \sigma_{2}
\end{pmatrix}$$

 

선형 관점에서는

$AV = U\Sigma$ 에서 $V^{-1} = V^T$이므로

$AV = U\Sigma$

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

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

 

$A = U\Sigma V^T$

$$= \begin{pmatrix}
\mid & \mid & & \mid\\
\overrightarrow{u_{1}} & \overrightarrow{u_{2}} & \cdots & \overrightarrow{u_{m}}\\
\mid & \mid & & \mid
\end{pmatrix}

\begin{pmatrix}
\sigma_{1} & & & & 0 \\
 & \sigma_{2}& & & 0\\
 & & \ddots & & 0\\
 & & & \sigma_{m} & 0\\
\end{pmatrix}

\begin{pmatrix}
- & \overrightarrow{v_{1}}^T & - \\
- & \overrightarrow{v_{2}}^T & -  \\
- & \vdots & -  \\
- & \overrightarrow{v_{m}}^T &  - \\
\end{pmatrix}$$
$$= \sigma_{1}\overrightarrow{u_{1}}\overrightarrow{v_{1}}^T + \sigma_{2}\overrightarrow{u_{2}}\overrightarrow{v_{2}}^T + \cdots + \sigma_{m}\overrightarrow{u_{m}}\overrightarrow{v_{m}}^T $$

 

 $\overrightarrow{u_{1}} \overrightarrow{v_{1}}$ 등의 벡터들은 $m \times n$ 행렬이고, 정규화 된 벡터이기 때문에 -1 ~ 1의 값을 갖는다.

여기서 행렬의 크기는 $\sigma_{1}$에 의해 정해진다.

$\therefore$ SVD를 이용해 임의의 행렬 $A$를 정보량에 따라 여러 layer로 쪼갤 수 있다.

 

이를 활용하여 기존 $U, V^T, \Sigma$ 로 분해된 $A$ 행렬을 특이값 $P$ 개만을 이용해  $A'$ 라는 행렬로 부분 복원이 가능하다.

 

Calculation

$A = U \cdot \Sigma \cdot V^T$ 에서 $A = \begin{pmatrix}
3 & 1 & 1 \\
-1 & 3 & 1
\end{pmatrix}$ 라고 가정해보고 계산해보자.

 

1) $U$ 구하기

a. $AA^T$

 

$$\begin{pmatrix}
3 & 1 & 1 \\
-1 & 3 & 1
\end{pmatrix}

\begin{pmatrix}
3 & -1 \\
1 & 3\\
1 & 1
\end{pmatrix}
= \begin{pmatrix}
9+1+1 & -3+3+1  \\
-3+3+1 & 1+9+1
\end{pmatrix}
=
\begin{pmatrix}
11 & 1  \\
1 & 11
\end{pmatrix}$$

b. $AA^T$의 eigen values, eigen vectors

($Be = \lambda I e\rightarrow (B- \lambda I)\cdot e =0$인 $\lambda , e$)

 

$$\begin{pmatrix}
11- \lambda & 1 \\
1 & 11- \lambda
\end{pmatrix}
\rightarrow  \ (11-\lambda)^2-1=0 
\rightarrow (11-\lambda)^2=1$$
$$\therefore \lambda = 10, 12$$

가)  $$\lambda=10 \rightarrow 
\begin{pmatrix}
1 & 1 \\
1 & 1
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
= 0$$

 

$$\therefore x+y=0 \rightarrow
\begin{pmatrix}
1 \\
-1
\end{pmatrix}$$

 

나)  $$\lambda=10 \rightarrow 
\begin{pmatrix}
-1 & 1 \\
1 & -1
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
= 0$$

$$\therefore -x+y=0 \rightarrow
\begin{pmatrix}
1 \\
1
\end{pmatrix}$$

 

c. eigen vector regulation

$$u_{1} = \begin{pmatrix}
\frac{1}{\sqrt{2}}\\
-\frac{1}{\sqrt{2}}

\end{pmatrix}$$

$$where \, \, \lambda = 10$$



$$u_{2} = \begin{pmatrix}
\frac{1}{\sqrt{2}}\\
\frac{1}{\sqrt{2}}
\end{pmatrix}$$
$$where \, \, \lambda = 12$$

 

d. 최종 $U \rightarrow$ 1. 정규환 된 $AA^T$의 고유 벡터 

                          2. 고유값 순서대로 배치

 

$$\therefore \, U =\begin{pmatrix}
\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{2}}\\
\frac{1}{\sqrt{2}} &-\frac{1}{\sqrt{2}}\\
\end{pmatrix}$$

 

2) $V$ 구하기

b. $AA^T$의 eigen values, eigen vectors

$$
\begin{pmatrix}
3 & -1 \\
1 & 3\\
1 & 1
\end{pmatrix}
\begin{pmatrix}
3 & 1 & 1 \\
-1 & 3 & 1
\end{pmatrix}

=
\begin{pmatrix}
10 & 0 & 2  \\
0 & 10 & 4 \\
2 & 4 & 2
\end{pmatrix}$$

$$\begin{pmatrix}
10 - \lambda & 0 & 2  \\
0 & 10- \lambda & 4 \\
2 & 4 & 2- \lambda
\end{pmatrix}
\rightarrow \, (10- \lambda)(\lambda^2 -12\lambda+4-4) = (10-\lambda)(\lambda^2-12\lambda) =(10-\lambda) \cdot \lambda(\lambda-12)$$

$$\therefore \, \lambda = 12, 10, 0$$

 

$1. \,\, \lambda=12$

$$\begin{pmatrix}
-2 & 0 & 2 \\
0 & -2 & 4 \\
2 & 4 & -10 
\end{pmatrix}
\begin{pmatrix}
x\\
y \\
z 
\end{pmatrix}$$



$$x = z \\
y=2z \\
x+2y-5z=0 \\
\therefore \ (1,2,1)$$



$2. \,\, \lambda=10$
$$\therefore \ (2,-1,0)$$
$3. \,\, \lambda=0$
$$\therefore \ (1,2,-5)$$

 

b. eigen vector regulatation

$$v_{1}=(1,2,1) \rightarrow (\frac{1}{\sqrt{6}},\frac{2}{\sqrt{6}},\frac{1}{\sqrt{1}}) \\
v_{2}=(2,-1,0) \rightarrow (\frac{2}{\sqrt{5}},-\frac{1}{\sqrt{5}},0)\\
v_{3}=(1,2,-5) \rightarrow (\frac{1}{\sqrt{30}},\frac{2}{\sqrt{30}},-\frac{5}{\sqrt{30}})$$

 

c. $V^T$ 구하기

$$V = \begin{pmatrix}
\frac{1}{\sqrt{6}}&\frac{2}{\sqrt{5}} & \frac{1}{\sqrt{30}} \\
\frac{2}{\sqrt{6}}&-\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{30}}\\
\frac{1}{\sqrt{6}}& 0 &-\frac{5}{\sqrt{30}}
\end{pmatrix}
\rightarrow \, V^T = \begin{pmatrix}
\frac{1}{\sqrt{6}}&\frac{2}{\sqrt{6}} & \frac{1}{\sqrt{6}} \\
\frac{2}{\sqrt{5}}&-\frac{1}{\sqrt{5}} & 0\\
\frac{1}{\sqrt{30}}& \frac{2}{\sqrt{30}} &-\frac{5}{\sqrt{30}}
\end{pmatrix}$$

 

$AA^T$로 $V$를 구하는 이유

(1) $AA^T$는 Symmentric matrix이다.

(2) Symmentric matrix는 모두 eigen value로 분해가 가능하고, othogonal matrix로도 분해가 가능하다.

 

$$A = U\Sigma V^T \\
AA^T =  U\Sigma V^T \cdot  U^T\Sigma^T  V
\\
= U\Sigma \Sigma^T U^T \, \, (\therefore U^T = U^{-1})
\\
=U\Sigma \Sigma^T U^{-1}
\\
U(\Sigma \Sigma^T) U^{-1}$$

여기서 $U$는 $AA^T$의 eigen vector로 구성이 되어 있다.

 

3) $\Sigma$ 구하기

$AA^T, A^TA$의 eigen value의 root를 취한 값을 diagonal element로 설정한다.

$$\begin{pmatrix}
\sqrt{12}&0&0\\
0&\sqrt{10}&0
\end{pmatrix}$$

 

Sklearn 활용

import numpy as np
import matplotlib.pyplot as plt

from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer
from sklearn import decomposition
from scipy import linalg

np.set_printoptions(suppress=True)

categories = ['alt.atheism', 'talk.religion.misc', 'comp.graphics', 'sci.space']
remove = ('headers', 'footers', 'quotes')
newsgroups_train = fetch_20newsgroups(subset='train', categories=categories, remove=remove)
newsgroups_test = fetch_20newsgroups(subset='test', categories=categories, remove=remove)

sklearn의 fetch_20newgroups는 20개의 topic으로 이루어진 18,000개의  80~90년도 newsgroup dataset 이다.

원래 20개의 topic을 우리는 categories라는 변수를 통해 4개의 분류 대상 topic을 지정한 후 train, test data를 나누어준다.

print(newsgroups_train.filenames.shape, newsgroups_train.target.shape)
# (2034,) (2034,)

train 데이터와 target이 각각 2034개 씩 매핑되어있는 모습을 볼 수 있다.

print("\n".join(newsgroups_train.data[:3]))
# Hi,
#
# I've noticed that if you only save a model (with all your mapping planes
# positioned carefully) to a .3DS file that when you reload it after restarting
# 3DS, they are given a default position and orientation.  But if you save
# to a .PRJ file their positions/orientation are preserved.  Does anyone
# know why this information is not stored in the .3DS file?  Nothing is
# explicitly said in the manual about saving texture rules in the .PRJ file.
# I'd like to be able to read the texture rule information, does anyone have
# the format for the .PRJ file?
#
# 
# Rych
# 
# 
# Seems to be, barring evidence to the contrary, that Koresh was simply
# another deranged fanatic who thought it neccessary to take a whole bunch of
# folks with him, children and all, to satisfy his delusional mania. Jim
# Jones, circa 1993.
# 
# 
# Nope - fruitcakes like Koresh have been demonstrating such evil corruption
# for centuries.
# 
#  >In article <1993Apr19.020359.26996@sq.sq.com>, msb@sq.sq.com (Mark Brader) 
# 
# MB>                                                             So the
# MB> 1970 figure seems unlikely to actually be anything but a perijove.
# 
# JG>Sorry, _perijoves_...I'm not used to talking this language.
# 
# Couldn't we just say periapsis or apoapsis?

train 데이터의 0, 1, 2번째 데이터 샘플이다.

print(np.array(newsgroups_train.target_names)[newsgroups_train.target[:3]])
# ['comp.graphics' 'talk.religion.misc' 'sci.space']

앞 3개의 데이터에 대한 target 값이다. 실제로는 index로 구성되어 있으며, 매핑 된 결과를 출력하였다.

num_topics, num_top_words = 6, 8

vectorizer = CountVectorizer(stop_words='english')
vectors = vectorizer.fit_transform(newsgroups_train.data).todense()
print(vectors.shape)
# (2034, 26576)

CountVectorizer를 통해 각 문서의 단어를 벡터화하여 빈도수를 vectorizer 변수에 할당한다. 그리고 나서 해당 변수를 fit_transform을 통해 정규화를 진행해 준다.

최종적으로 vectors는 2034개의 문서가 row, 26576개의 단어가 column으로 이루어진 배열이 된다.

vocab = np.array(vectorizer.get_feature_names())
print(vocab.shape)
# (26576,)

vocab이라는 변수에는 각 단어의 빈도수만 저장해둔다.

print(vocab[7000:7020])
# ['cosmonauts' 'cosmos' 'cosponsored' 'cost' 'costa' 'costar' 'costing'
#  'costly' 'costruction' 'costs' 'cosy' 'cote' 'couched' 'couldn' 'council'
#  'councils' 'counsel' 'counselees' 'counselor' 'count']

U, s, Vh = linalg.svd(vectors, full_matrices=False)
# print(U.shape, s.shape, Vh.shape)
# (2034, 2034) (2034,) (2034, 26576)
plt.plot(s)
plt.show()
plt.plot(s[:10])
plt.show()

svd 메서드를 통해 vectors 배열을 추출한 후 sigma 배열을 plt를 사용해 그래프를 그린다.

 

sigma 배열 특성상 앞쪽으로 갈 수록 빈도가 높은 단어인 모습을 볼 수 있다.

앞서 설명했던바와 같이 sigma 배열은 벡터의 크기를 결정한다.

num_top_words = 8


def show_topics(a):
    top_words = lambda t: [vocab[i] for i in np.argsort(t)[:-num_top_words - 1: -1]]
    topic_words = ([top_words(t) for t in a])
    return [' '.join(t) for t in topic_words]

result = show_topics(Vh[:10])
print(result)

['critus ditto propagandist surname galacticentric kindergarten surreal imaginative',
 'jpeg gif file color quality image jfif format',
 'graphics edu pub mail 128 3d ray ftp',
 'jesus god matthew people atheists atheism does graphics',
 'image data processing analysis software available tools display',
 'god atheists atheism religious believe religion argument true',
 'space nasa lunar mars probe moon missions probes',
 'image probe surface lunar mars probes moon orbit',
 'argument fallacy conclusion example true ad argumentum premises',
 'space larson image theory universe physical nasa material']

show_topics 함수를 통해 빈도수가 가장 높은 단어를 8개씩 묶어 문장을 만들어 준다.

이를 통해 topic을 예측할 수 있다.

 

Reference

https://github.com/fastai/numerical-linear-algebra/blob/master/README.md

GitHub - fastai/numerical-linear-algebra: Free online textbook of Jupyter notebooks for fast.ai Computational Linear Algebra cou

https://angeloyeo.github.io/2019/08/01/SVD.html

특이값 분해(SVD) - 공돌이의 수학정리노트

가짜연구소 선형대수 스터디 'FlyToLA' 김소연님 발표 자료