K. Baker의 특이값 분해(singular value decomposition) 튜토리얼에서 선형대수 기초적인 부분을 제외한 Gram-Schmidt 과정, Full SVD 예제, Reduced SVD 예제를 최대한 한글로 옮겨적었습니다.
원문은 링크에서 받아보실 수 있습니다. 원문에서 행렬의 기본적인 개념과 표기, 벡터의 연산 방법들을 설명하고, 행렬의 종류에 대해서 상세히 설명하므로 선형대수 수업을 안들어보신 분은 찾아보시기 바랍니다. 고등학교 때 행렬 연산 방법 배운걸 기억하시면 예제만 읽어보셔도 쉽게 이해될 거에요.
참고. 이 글에 LaTex 문법이 적용되어 있는데, 모바일에서는 수식이 제대로 안보여서 컴퓨터 화면으로 보시길 추천합니다.
Gram-Schmidt 과정
- 요약
이 과정은 벡터의 집합을 orthonormal 벡터의 집합으로 변환해주는 것이다.
기본적으로 첫 열의 벡터를 normalizing하고, 이를 다른 벡터에 곱해서 빼주는 방식을 쓴다.
Gram-Schmidt 과정의 일반식은 아래와 같다. 만약 orthonormal한 벡터의 집합 $$\vec{u}_1, ..., \vec{u}_{k-1}$$이 있다면, $$\vec{w}_k$$는 다음과 같이 구할 수 있다.
$$\vec{w}_k = \vec{v}_k - \Sigma_{i=1}^{k-1} \vec{u}_i \cdot \vec{v}_k * \vec{u}_i$$
이를 정규화하면 orthonormal 벡터 $$\vec{u}_k$$를 구할 수 있다.
- 예제
아래와 같이 행렬 A가 있다고 하자.
$$A=\begin{bmatrix}1 & 2 & 1 \\0 & 2 & 0 \\2 & 3 & 1 \\1 & 1 & 0 \end{bmatrix} $$
첫 열의 벡터 $$\vec{v}_1=[1,0,2,1]$$을 정규화한다.
$$\vec{w}_2 = \vec{v}_2 - \vec{u}_1 \cdot \vec{v}_2 * \vec{u}_1$$
$$ = [2,2,3,1] - [{1\over \sqrt{6}}, 0, {2\over \sqrt{6}}, {1\over \sqrt{6}}] \cdot [2,2,3,1] * [{1\over \sqrt{6}}, 0, {2\over \sqrt{6}}, {1\over \sqrt{6}}] $$
$$ = [2,2,3,1] - ({9\over \sqrt{6}}) * [{1\over \sqrt{6}}, 0, {2\over \sqrt{6}}, {1\over \sqrt{6}}]$$
$$=[2,2,3,1] - [{3\over 2},0,3,{3\over 2}]$$
$$=[{1\over 2},2,0,{-1\over 2}]$$
$$\vec{w}_2$$를 정규화한다.
$$\vec{u}_2 = [{\sqrt{2}\over 6}, {2\sqrt{2}\over 3},0, {-\sqrt{2}\over 6}]$$
다음으로 셋째 열의 벡터에 관해 다음과 같은 연산을 수행한다.
$$\vec{w}_3 = \vec{v_3}-\vec{u}_1 \cdot \vec{v}_3 * \vec{u}_1 - \vec{u}_2 \cdot \vec{v}_3 * \vec{u}_2 = [{4\over 9}, {-2\over 9}, 0, {-4\over 9}] $$
이를 정규화하면,
$$ \vec{u}_3 = [{2\over 3}, {-1 \over 3}, 0, {-2 \over 3}] $$
최종적인 orthonormal 열 벡터들은
$$\begin{bmatrix} {\sqrt{6}\over 6} &{\sqrt{2}\over 6} & {2\over 3} \\ 0 & {2\sqrt{2} \over 3} & {-1\over 3} \\ {\sqrt{6}\over 3}& 0 &0 \\ {\sqrt{6}\over 6} & {-\sqrt{2}\over 6} & {-2\over 3} \end{bmatrix} $$
Full SVD 예제
SVD는 행렬 A를 orthogonal 행렬 U, digonal 행렬 S, 전치 orthogonal 행렬 V로 나누는 것을 의미한다.
즉, $$A=USV^T$$ 가 되고, 이 때, $$ U^TU=I, V^TV=I $$가 된다.
U의 열들은 $$AA^T$$에 orthonormal 고유벡터이고, V의 열들은 $$A^TA$$에 orthonormal 고유벡터이다. 그리고 S는 U, V의 고유값을 거듭제곱한 것을 내림 차순으로 나타낸 digonal 행렬이다.
행렬 A가 다음과 같다고 하자.
$$ A=\begin{bmatrix}3 & 1& 1\\ -1& 3& 1\end{bmatrix} $$
(1) U 구하기
$$AA^T$$로 $$U$$를 구하므로,
$$A^T=\begin{bmatrix}3 & -1 \\1 & 3 \\1 & 1\end{bmatrix}$$
따라서,
$$AA^T=\begin{bmatrix}3 & 1 & 1 \\-1 & 3 & 1\end{bmatrix}\begin{bmatrix}3 & -1 \\1 & 3 \\1 & 1\end{bmatrix}=\begin{bmatrix}11 & 1 \\1 & 11\end{bmatrix}$$
다음으로 $$AA^T$$의 고유벡터를 구한다. 고유벡터를 구하는 등식은 $$A\vec{v}=\lambda\vec{v}$$이므로 위 행렬을 대입해서
$$\begin{bmatrix}11 & 1 \\1 & 11\end{bmatrix}\begin{bmatrix}x_1 \\x_2 \end{bmatrix}=\lambda\begin{bmatrix}x_1 \\x_2 \end{bmatrix}$$
위 행렬 연산을 방정식으로 나타내면,
$$11x_1+x_2=\lambda x_1$$
$$x_1+11x_2=\lambda x_2$$
좌변으로 정리하면,
$$(11-\lambda)x_1+x_2=0$$
$$x_1+(11-\lambda)x_2=0$$
$$\lambda$$를 풀기 위해서 계수 행렬식이 0이어야 한다.
즉, $$(11-\lambda)(11-\lambda)-1\cdot 1=0$$
$$(\lambda-10)(\lambda-12)=0$$
$$\lambda=10, \lambda=12$$이므로 하나 씩, 윗 방정식에 다시 대입한다.
$$\lambda=10$$ 일 때,
$$(11-10)x_1+x_2=0$$
$$x_1=-x_2$$
$$x_1, x_2$$가 무한히 많으므로 계산을 편하게 하기 위해 $$x_1=1, x_2=-1$$으로 한다.
이로써 고유벡터 $$[1,-1]$$ 을 하나 구했고,
$$\lambda=12$$ 의 경우 고유벡터는 $$[1,1]$$이다.
$$\lambda$$의 내림차순 순서대로 고유벡터가 각각의 열을 차지한다. 따라서,
$$\begin{bmatrix}1 & 1 \\1 & -1 \end{bmatrix}$$
위 행렬을 orthonormal한 행렬로 변환하면 $$U$$가 된다.
이를 구하기 위해 Gram-Schmidt의 orthonormalization 과정을 쓴다.
먼저 $$\vec{u_1}={\vec{v_1}\over |\vec{v_1}|}={[1,1]\over \sqrt{1^2+1^2}}={[1,1]\over \sqrt{2}}=[{1\over \sqrt{2}} , {1\over \sqrt{2}}]$$
다음으로 아래 연산을 한다.
$$\vec{w_2}=\vec{v_2}-\vec{u_1}\cdot \vec{v_2}*\vec{u_1}$$
$$=[1,-1]-[{1\over \sqrt{2}}, {1\over \sqrt{2}}]\cdot[1,-1]*[{1\over\sqrt{2}},{1\over \sqrt{2}}]$$
$$=[1,-1]-0*[{1\over\sqrt{2}}, {1\over\sqrt{2}}]=[1,-1]-[0,0]=[1,-1]$$
이를 정규화하여
$$\vec{u_2}={vec{w_2}\over |\vec{w_2}|}=[{1\over \sqrt{2}}, {-1\over \sqrt{2}}]$$
앞서 구한 orthonormal한 벡터를 각 행에 대입해 U가 된다.
$$U=\begin{bmatrix}{1\over\sqrt{2}} & { 1\over \sqrt{2}}\\{1\over \sqrt{2}}&{-1\over\sqrt{2}}\end{bmatrix}$$
(2) V 구하기
$$V$$를 구하기 위해서 $$A^TA$$로부터,
$$A^TA=\begin{bmatrix}3 & -1 \\1 & 3\\1&1 \end{bmatrix}\begin{bmatrix}3 & 1&1 \\-1 & 3&1 \end{bmatrix}=\begin{bmatrix}10&0 & 2 \\0 & 10&4\\2&4&2 \end{bmatrix}$$
$$A^TA$$의 고유값을 구한다.
$$\begin{bmatrix}10&0 & 2 \\0 & 10&4\\2&4&2 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\lambda\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}$$
위를 아래 방정식으로 표현할 수 있다.
$$10x_1+2x_3=\lambda x_1$$
$$10x_2+4x_3=\lambda x_2$$
$$2x_1+4x_2+2x_3=\lambda x_2$$
좌변으로 정리하면,
$$(10-\lambda)x_1+2x_3=0$$
$$(10-\lambda)x_2+4x_3=0$$
$$2x_1+4x_2+(2-\lambda)x_3=0$$
방정식의 계수 행렬을 만들면
$$\begin{vmatrix}(10-\lambda)&0&2\\0&(10-\lambda)&4\\2&4&(2-\lambda)\end{vmatrix}=0$$
위 매트릭스의 determinant가 0이어야하므로
$$(10-\lambda)\begin{vmatrix}(10-\lambda)&4\\4&(2-\lambda)\end{vmatrix}+2\begin{vmatrix}0&(10-\lambda)\\2&4\end{vmatrix}$$
$$=(10-\lambda)[(10-\lambda)(2-\lambda)-16]+2[0-(20-2\lambda)]$$
$$=\lambda(\lambda-10)(\lambda-12)=0$$
따라서 고유값은 $$\lambda=0, \lambda=10, \lambda=12$$이 된다.
고유값이 큰 순서대로, $$\lambda=12$$ 부터 $$x_1=1, x_2=2, x_3=1$$ 이고,
$$\lambda=10$$ 은 $$x_1=2, x_2=-1, x_3=0$$이고,
$$\lambda=0$$ 일 때, $$x_1=1, x_2=2, x_3=-5$$ 가 된다.
이를 열 왼쪽 부터 차례로 대입하여 만든 행렬은 아래와 같다.
$$\begin{bmatrix}1&2&1\\2&-1&2\\1&0&-5\end{bmatrix}$$
여기에 Gram-Schmidt의 orthonormalization 과정을 거치면 V를 구할 수 있다.
$$V=\begin{bmatrix}{1\over\sqrt{6}}&{2\over\sqrt{5}}&{1\over\sqrt{30}}\\{2\over\sqrt{6}}&{-1\over\sqrt{5}}&{2\over\sqrt{30}}\\{1\over\sqrt{6}}&0&{-5\over\sqrt{30}}\end{bmatrix}$$
V를 전치시켜서
$$V^T=\begin{bmatrix}{1\over\sqrt{6}}& {2\over\sqrt{6}}&{1\over\sqrt{6}}\\{2\over\sqrt{5}}&{-1\over\sqrt{5}}&0\\{1\over\sqrt{30}}&{2\over\sqrt{30}}&{-5\over\sqrt{30}}\end{bmatrix}$$
(3) S 구하기
U,V의 0이 아닌 고유값들은 항상 같은데 이 고유값을 내림 차순으로 행렬 S의 원소 $$s_{11}, s_{22}, ..., s_{mm}$$에 대입하고, 나머지 원소들은 0이다.
위에서 full SVD를 다루었으므로, S에 0인 열을 추가해서 inner product연산이 가능하도록 각각의 행렬의 행과 열의 크기를 맞춘다.
$$S=\begin{bmatrix}\sqrt{12}&0&0\\0&\sqrt{10}&0\end{bmatrix}$$
$$A_{mm}=U_{mm}S_{mn}V^T_{nn}$$
$$=\begin{bmatrix}{1\over\sqrt{2}}&{1\over\sqrt{2}}\\{1\over \sqrt{2}}&{-1\over\sqrt{2}}\end{bmatrix}\begin{bmatrix}\sqrt{12}&0&0\\0&\sqrt{10}&0\end{bmatrix}\begin{bmatrix}{1\over\sqrt{6}}&{2\over\sqrt{6}}&{1\over\sqrt{6}}\\{2\over\sqrt{5}}&{-1\over\sqrt{5}}&0\\{1\over\sqrt{30}}&{2\over\sqrt{30}}&{-5\over\sqrt{30}}\end{bmatrix}$$
$$=\begin{bmatrix}{\sqrt{12}\over\sqrt{2}}&{\sqrt{10}\over\sqrt{2}}&0\\{\sqrt{12}\over\sqrt{2}}&{-\sqrt{10}\over\sqrt{2}}&0\end{bmatrix}\begin{bmatrix}{1\over\sqrt{6}}&{2\over\sqrt{6}}&{1\over\sqrt{6}}\\{2\over\sqrt{5}}&{-1\over\sqrt{5}}&0\\{1\over\sqrt{30}}&{2\over\sqrt{30}}&{-5\over\sqrt{30}}\end{bmatrix}$$
$$=\begin{bmatrix}3&1&1\\-1&3&1\end{bmatrix}$$
Reduced SVD 예제
원래 데이터가 문자와 문서의 inner product로 된 행렬이라고 할 때, SVD로 분해 가능하다.
아래와 같은 데이터가 주어졌을 때,
$$A=\begin{bmatrix}2&0&8&6&0\\1&6&0&1&7\\5&0&7&4&0\\7&0&8&5&0\\0 &10 &0 &0 &7\end{bmatrix}$$
$$U=\begin{bmatrix}-0.54&0.07&0.82&-0.11&0.12\\-0.10&-0.59&-0.11&-0.79&-0.06\\-0.53&0.06&-0.21&0.12&-0.81\\-0.65&0.07&-0.51&0.06&0.56\\-0.06&-0.80&0.09&0.59&0.04\end{bmatrix}$$
$$V^T=\begin{bmatrix}-0.46&0.02&-0.87&-0.00&0.17\\-0.07&-0.76&0.06&0.06&0.23\\-0.74&0.10&0.28&0.22&-0.56\\-0.48&0.03&0.40&-0.33&0.70\\-0.07&-0.64&-0.04&-0.69&-0.32\end{bmatrix}$$
S는 U,V 중 하나의 고유값을 내림 차순으로 대입하면 되는데, reduced SVD를 구하기 위해 큰 값 부터 세 개의 고유값만 쓴다.
$$S=\begin{bmatrix}17.92&0&0\\0&15.17&0\\0&0&3.56\end{bmatrix}$$
U의 행은 문자를 나타내고, US의 행을 비교하여 문자의 유사도를 계산 가능하다.
V(전치 행렬 V가 아님)의 행은 문서를 나타내고, VS의 행을 비교하여 문서간의 유사도 비교가 가능하다.
위 튜토리얼에 추가하여 SVD가 데이터마이닝에 쓰이는 예시를 알려드리면, 지금은 사라진 Neflix Prize에서 우승 팀인 Koren, Robert, Volinsky (2009)의 "Matrix Factorization Techniques for Recommender Systems"에서 사용되었습니다. 데이터마이닝에서는 matrix factorization이라는 이름으로 유명한 방법입니다.
학술적인 내용은 아니지만 이에 관한 이야기를 읽어보시려면 아래 블로그를 방문해보세요. 100만 달러 규모의 대회에서 우승하기 위한 사람들의 뒷 이야기가 담겨 있습니다.
http://www.shalomeir.com/2014/11/netflix-prize-1/
http://www.shalomeir.com/2014/11/netflix-prize-2/
http://www.shalomeir.com/2014/12/netflix-prize-3/
추가로, 데이터마이닝에서 SVD를 쓰는 상세한 예제는 Jannach의 책 Recommender Systems: An Introduction, Cambridge University Press, 2010 에서 챕터 2의 2.4.1의 Matrix factorization/latent factor models에서 확인해볼 수 있습니다.
'노트정리 > 선형대수학 linear algebra' 카테고리의 다른 글
| 특이값 분해 따라하기. Singular value decomposition tutorial. (0) | 2015.10.09 |
|---|
