SVD와 PCA, 그리고 잠재의미분석(LSA)
06 Apr 2017 | SVD, PCA, LSA
이번 포스팅에서는 차원축소(dimension reduction) 기법으로 널리 쓰이고 있는 특이값분해(Singular Value Decomposion)와 주성분분석(Principal Component Analysis)에 대해 알아보도록 하겠습니다. 마지막으로는 이러한 기법이 잠재의미분석(Latent Sematic Analysis)와 어떻게 연결되는지 이야기해보도록 하겠습니다. 이번 글은 고려대 강필성 교수님, 한양대 이상화 교수님 강의와 quora, 또 다크프로그래머의 블로그를 참고했음을 미리 밝힙니다. 그럼 시작하겠습니다.
주성분 분석
PCA는 데이터의 분산(variance)을 최대한 보존하면서 서로 직교하는 새 기저(축)를 찾아, 고차원 공간의 표본들을 선형 연관성이 없는 저차원 공간으로 변환하는 기법입니다. 이를 그림으로 나타내면 아래와 같습니다. 3차원 공간에 있는 데이터들이 서로 수직인 두 개의 주성분(PC1, PC2)을 새로운 기저로, 선형변환된 것을 확인할 수 있습니다. PCA 관련 자세한 내용은 이곳을 참고하시기 바랍니다.
원 데이터의 분산을 최대화하는 새로운 기저를 찾는 목표를 달성하려면 우선 데이터 행렬 $A$의 공분산 행렬부터 구해야 합니다. 데이터가 각 변수별로 평균이 0으로 맞춰져 있을 때(centering 작업 이미 수행되어 있다고 가정) 공분산 행렬은 아래와 같이 구합니다.
\[cov(A)=\frac { 1 }{ n-1 } A{ A }^{ T }\propto A{ A }^{ T }\]
PCA의 새로운 축을 찾기 위해서는 위 공분산행렬을 아래처럼 고유분해(Eigen decomposition)를 수행해주어야 합니다. 아래 식에서 $Λ$는 대각성분이 공분산행렬의 고유값이고 나머지 요소는 0인 행렬, $U$는 열벡터가 공분산행렬 $AA^T$의 고유벡터로 이뤄진 행렬입니다.
\[A{ A }^{ T }=U\Lambda { U }^{T }\]
여기에서 $Λ$의 대각성분은 데이터 행렬 $A$의 각 변수에 해당하는 분산을 의미합니다. 원 데이터의 분산을 최대화하는 새로운 기저를 찾는 것이 PCA 목표인 만큼 가장 큰 고유값 몇 개를 고르고, 그에 해당하는 고유벡터를 새로운 기저로 하여 원데이터를 사영(선형변환)해주면 PCA 작업이 완료되게 됩니다.
예컨대 변수가 100개(100차원)인 데이터에 PCA를 적용한 후 가장 큰 고유값 두 개에 해당하는 고유벡터로 원 데이터를 사영시키면 원데이터의 분산을 최대한 보존하면서도 그 차원수를 100차원에서 2차원으로 줄일 수 있게 됩니다.
특이값 분해
특이값분해는 m x n 크기의 데이터 행렬 $A$를 아래와 같이 분해하는 걸 말합니다.
\[A=U\Sigma { V }^{ T }\\\]
행렬 $U$와 $V$에 속한 열벡터는 특이벡터(singular vector)로 불리고요, 모든 특이벡터는 서로 직교하는 성질을 지닙니다.
\[U=\begin{bmatrix} \overrightarrow { { u }_{ 1 } } & \overrightarrow { { u }_{ 2 } } & ... & \overrightarrow { { u }_{ m } } \end{bmatrix}\\ V=\begin{bmatrix} \overrightarrow { { v }_{ 1 } } & \overrightarrow { v_{ 2 } } & ... & \overrightarrow { { v }_{ n } } \end{bmatrix}\\ \overrightarrow { { u }_{ k } } =\begin{bmatrix} { u }_{ k1 } \\ { u }_{ k2 } \\ ... \\ { u }_{ km } \end{bmatrix}\quad \overrightarrow { { v }_{ k } } =\begin{bmatrix} { v }_{ k1 } \\ v_{ k2 } \\ ... \\ { v }_{ kn } \end{bmatrix}\\ { \overrightarrow { { u }_{ k } } }^{ T }\overrightarrow { { u }_{ k } } =1,\quad { U }^{ T }U=I\\ { \overrightarrow { { v }_{ k } } }^{ T }\overrightarrow { { v }_{ k } } =1,\quad { V }^{ T }V=I\]
행렬 $Σ$의 특이값은 모두 0보다 크거나 같으며 내림차순으로 정렬돼 있습니다. 행렬 $Σ$의 $k$번째 대각원소에 해당하는 특이값 $Σ_k$는 행렬 $A{A}^{T}$의 $k$번째 고유값에 제곱근을 취한 값과 같습니다.
\[{ \Sigma }_{ k }=\sqrt { { \lambda }_{ k } } \]
그러면 특이값 분해를 주성분 분석과 비교해보기 위해 행렬 $A$를 제곱해 보겠습니다. 이후 식을 정리하면 아래와 같습니다.
\[\begin{align*}
A{ A }^{ T }&=U\Sigma { V }^{ T }{ (U\Sigma { V }^{ T }) }^{ T }\\ &=U\Sigma { V }^{ T }V\Sigma { U }^{ T }\\ &=U{ \Sigma }^{ 2 }{ U }^{ T }\\ &=U\Lambda { U }^{ T }
\end{align*}\]
여기서 대각성분이 행렬 $A$의 특이값이고 나머지 성분이 0인 행렬 $Σ$에 주의할 필요가 있습니다. $Σ$는 대각행렬(diagonal matrix)인데요, 대각행렬의 거듭제곱은 대각원소들만 거듭제곱을 해준 결과와 같습니다.
따라서 $Σ$의 제곱은 각 대각원소, 즉 행렬 $A$의 특이값들을 제곱해준 값과 똑같습니다. 그런데 행렬 $A$의 특이값은 $A{A}^T$의 고유값에 제곱근을 취한 값과 동일하므로, $Σ$을 제곱한 행렬은 행렬 $AA^T$의 고유값으로 이뤄진 행렬 $Λ$가 됩니다. 이는 정확히 주성분 분석의 결과와 같습니다.
특이값 분해의 여러 변형들
thin SVD
thin SVD는 $Σ$ 행렬의 아랫부분(비대각 파트, 모두 0)과 $U$에서 여기에 해당하는 부분을 모두 제거합니다. 이렇게 $U$와 $Σ$를 줄여도 $U_sΣ_sV^T$로 $A$를 원복할 수 있습니다.
compact SVD
compact SVD는 $Σ$ 행렬에서 비대각파트뿐 아니라 대각원소(특이값)가 0인 부분도 모두 제거한 형태입니다. 여기에 대응하는 $U$와 $V$의 요소 또한 제거합니다. 다시 말해 특이값이 양수인 부분만 골라낸다는 뜻입니다. 이렇게 $U$와 $Σ$, $V$를 줄여도 $U_rΣ_rV_r^T$로 $A$를 원복할 수 있습니다.
truncated SVD
truncated SVD는 $Σ$ 행렬의 대각원소(특이값) 가운데 상위 $t$개만 골라낸 형태입니다. 이렇게 하면 행렬 $A$를 원복할 수 없게 되지만, 데이터 정보를 상당히 압축했음에도 행렬 $A$를 근사할 수 있게 됩니다. 이후 설명드릴 잠재의미분석은 바로 이 방법을 사용합니다.
SVD 예시
\[A=U\Sigma { V }^{ T } \\ \\ \begin{bmatrix} 2 & 3 \\ 1 & 4 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}=\begin{bmatrix} 0.82 & -0.58 & 0 & 0 \\ 0.58 & 0.82 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 5.47 & 0 & 0 & 0 \\ 0 & 0.37 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}\begin{bmatrix} 0.40 & 0.91 \\ -0.91 & 0.40 \end{bmatrix}\]
truncated SVD 예시
\[\begin{align*}
{ A }^{ ' }&={ U }_{ 1 }{ \Sigma }_{ 1 }{ V }_{ 1 }^{ T }\\ \\ \begin{bmatrix} 1.79 & 4.08 \\ 1.27 & 2.89 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}&=\begin{bmatrix} 0.82 \\ 0.58 \\ 0 \\ 0 \end{bmatrix}\begin{bmatrix} 5.47 \end{bmatrix}\begin{bmatrix} 0.40 & 0.91 \end{bmatrix}
\end{align*}\]
잠재의미분석 개요
예컨대 다음과 같은 문서들이 있다고 하면, 우리는 이를 토대로 단어-문서행렬 $A$를 만들 수 있습니다.
doc1 : 나,는,학교,에,가,ㄴ,다
doc2 : 학교,에,가,는,영희
doc3 : 나,는,영희,는,좋,다
-
doc1
doc2
doc3
나
1
0
0
는
1
1
2
학교
1
1
0
에
1
1
0
가
1
1
0
ㄴ
1
0
0
다
1
0
1
영희
0
1
1
좋
0
0
1
잠재의미분석이란 위와 같은 단어-문서행렬(Word-Document Matrix), 단어-문맥행렬(window based co-occurrence matrix) 등 입력 데이터에 특이값 분해를 수행해 데이터의 차원수를 줄여 계산 효율성을 키우는 한편 행간에 숨어있는(latent) 의미를 이끌어내기 위한 방법론입니다. 대략적인 개념은 아래 그림과 같습니다.
잠재의미분석을 수행하는 절차는 이렇습니다. $n$개의 문서를 $m$개의 단어로 표현된 입력데이터 행렬 $A$가 주어졌다고 칩시다. $A$의 0보다 큰 고유값의 개수를 $r$이라고 할 때, $r$보다 작은 $k$를 연구자가 임의로 설정하고 $Σ_k$를 만듭니다. 이후 $U$와 $V$ 행렬에서 여기에 대응하는 부분만 남겨 $U_k$와 $V_k$를 만들어줍니다. 이렇게 되면 $A$와 비슷한 $A_k$ 행렬을 구축할 수 있습니다.
\[{ A }_{ k }={ U }_{ k }{ \Sigma }_{ k }{ V }_{ k }^{ T }\]
위 식 양변에 $U_k$의 전치행렬을 곱해준 것을 $X_1$, $V_k$를 곱해준 것을 $X_2$라고 둡니다. 그러면 $X_1$의 경우 $n$개의 문서는 원래 단어수 $m$보다 훨씬 작은 $k$개 변수로 표현된 결과가 됩니다. $X_2$는 $m$개의 단어가 원래 문서 수 $n$보다 작은 $k$개 변수로 표현한 결과입니다. 이는 주성분 분석에서의 차원축소 효과와 비슷한 것으로 이해하면 좋을 것 같습니다.
\[{ { U }_{ k }^{ T }A }_{ k }={ { U }_{ k }^{ T }U }_{ k }{ \Sigma }_{ k }{ V }_{ k }^{ T }=I{ \Sigma }_{ k }{ V }_{ k }^{ T }={ \Sigma }_{ k }{ V }_{ k }^{ T }={ X }_{ 1 }\\ { A }_{ k }{ V }_{ k }={ U }_{ k }{ \Sigma }_{ k }{ V }_{ k }^{ T }{ V }_{ k }={ U }_{ k }{ \Sigma }_{ k }^{ T }I={ U }_{ k }{ V }_{ k }^{ T }={ X }_{ 2 }\]
잠재의미분석 예시
자, 그럼 위에서 예로 든 단어-문서행렬 $A$를 가지고 잠재의미분석을 수행해 보겠습니다. $A$에 SVD를 수행하면 아래와 같이 쓸 수 있습니다. 숫자들이 엄청 많은데요, ‘아 이렇게 분해될 수 있구나’ 정도로 보고 슥 넘어가시면 될 것 같습니다.
\[A=U\Sigma { V }^{ T }\\ \\ \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}=\begin{bmatrix} -0.17 & 0.27 & -0.40 \\ -0.63 & -0.41 & -0.03 \\ -0.32 & 0.37 & 0.21 \\ -0.32 & 0.37 & 0.21 \\ -0.32 & 0.37 & 0.21 \\ -0.17 & 0.27 & -0.40 \\ -0.33 & -0.12 & -0.52 \\ -0.30 & -0.29 & 0.49 \\ -0.15 & -0.39 & -0.13 \end{bmatrix}\begin{bmatrix} 3.61 & 0 & 0 \\ 0 & 2.04 & 0 \\ 0 & 0 & 1.34 \end{bmatrix}\begin{bmatrix} -0.63 & -0.53 & -0.57 \\ 0.56 & 0.20 & -0.80 \\ -0.54 & 0.83 & -0.17 \end{bmatrix}\]
그럼 $Σ$ 행렬의 특이값 가운데 상위 2개(3.61과 2.04)만 남기고 나머지를 제거하는 방식으로 truncated SVD를 수행해 보겠습니다. 아래와 같습니다.
\[{ A }^{ ' }={ U }_{ 2 }{ \Sigma }_{ 2 }{ V }_{ 2 }^{ T }\\ \begin{bmatrix} 0.71 & 0.44 & -0.09 \\ 0.97 & 1.04 & 1.99 \\ 1.15 & 0.76 & 0.04 \\ 1.15 & 0.76 & 0.04 \\ 1.15 & 0.76 & 0.04 \\ 0.71 & 0.45 & -0.09 \\ 0.62 & 0.58 & 0.88 \\ 0.36 & 0.45 & 1.11 \\ -0.09 & 0.14 & 0.97 \end{bmatrix}=\begin{bmatrix} -0.17 & 0.27 \\ -0.63 & -0.41 \\ -0.32 & 0.37 \\ -0.32 & 0.37 \\ -0.32 & 0.37 \\ -0.17 & 0.27 \\ -0.33 & -0.12 \\ -0.30 & -0.29 \\ -0.15 & -0.39 \end{bmatrix}\begin{bmatrix} 3.61 & 0 \\ 0 & 2.04 \end{bmatrix}\begin{bmatrix} -0.63 & -0.53 & -0.57 \\ 0.56 & 0.20 & -0.80 \end{bmatrix}\]
솔직히 이렇게 봐서는 $A’$가 원데이터 행렬 $A$에 제대로 근사한 것인지 아리송합니다. $A’$의 각 요소값을 반올림해서 원 행렬 $A$와 비교해보겠습니다. 6행과 7행의 요소값이 조금 다를 뿐 거의 유사한 것을 확인할 수 있습니다.
\[round({ A }^{ ' })=\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix},\quad A=\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}\]
그럼 $A’=U_2Σ_2V^T_2$ 양변의 맨 앞에 $U_2$의 전치행렬을 각각 곱해줄까요? 그 결과를 $X_1$이라고 두면 아래와 같습니다.
\[X_{1}=\begin{bmatrix} -2.28 & -1.90 & -2.07 \\ 1.14 & 0.42 & -1.64 \end{bmatrix}\]
원데이터인 $A$와 SVD 결과인 $X_1$의 열(column)은 문서(문장)를 의미합니다. 단어-문맥행렬 $A$에서 각 문서들은 9개 단어(변수)들로 표현됐으나 $X_1$에서는 단 두 개의 변수들만으로도 표현이 가능해졌습니다. 이렇게 만든 $X_1$에 다양한 데이터마이닝 기법을 적용해 여러 가지 문제를 풀게 되는 것입니다.
자, 이제는 반대로 $A’=U_2Σ_2V^T_2$ 양변의 맨 뒤에 $V_2$를 각각 곱해볼까요? 그 결과를 $X_2$라고 두면 다음과 같습니다.
\[{ X }_{ 2 }=\begin{bmatrix} -0.63 & 0.56 \\ -2.30 & -0.84 \\ -1.16 & 0.76 \\ -1.16 & 0.76 \\ -1.16 & 0.76 \\ -0.63 & 0.56 \\ -1.20 & -0.24 \\ -1.10 & -0.60 \\ -0.57 & -0.80 \end{bmatrix}\]
원데이터인 $A$와 SVD 결과인 $X_2$의 행(row)은 단어를 의미합니다. 단어-문맥행렬 $A$에서 각 단어들은 3개 문서(변수)들로 표현됐으나 $X_2$에서는 단 두 개의 변수들만으로도 표현이 가능해졌습니다. 이렇게 만든 $X_2$에 마찬가지로 다양한 데이터마이닝 기법을 적용해 여러 가지 문제를 풀게 됩니다.
잠재의미분석의 효과
이제까지 든 예시에서는 차원축소의 효과가 도드라져 보이진 않지만 데이터가 클 경우 그 효과가 드라마틱하다고 합니다. 실제로 네이버, 카카오 등 현업에서도 이러한 방법론을 많이 쓰고 있는 것으로 알려져 있습니다. 잠재의미분석은 이외에도 많은 장점이 있다고 합니다. Deerwester et ak.(1990)과 Landauer and Dumais(1997)은 이 기법을 적용하면 단어와 문맥 간의 내재적인 의미(latent/hidden meaning)을 효과적으로 보존할 수 있게 돼 결과적으로 문서 간 유사도 측정 등 모델의 성능 향상에 도움을 줄 수 있다고 합니다. Rapp(2003)은 입력 데이터의 노이즈 제거, Vozalis and Margaritis(2003)은 입력데이터의 sparsity를 줄이게 돼 그 효과가 좋다고 합니다. 잠재의미분석은 입력데이터의 크기가 m x n이고 문서당 평균 단어수가 $c$일 경우 계산복잡도가 $O(mnc)$이어서 그다지 무거운 알고리즘은 아닙니다. 하지만 새로운 문서나 단어가 추가되면 아예 처음부터 작업을 새로 시작해야 합니다. 이 때문에 최근에는 Word2Vec 등 뉴럴네트워크 기반의 representation 방법론도 각광을 받고 있습니다.
이번 포스팅에서는 차원축소(dimension reduction) 기법으로 널리 쓰이고 있는 특이값분해(Singular Value Decomposion)와 주성분분석(Principal Component Analysis)에 대해 알아보도록 하겠습니다. 마지막으로는 이러한 기법이 잠재의미분석(Latent Sematic Analysis)와 어떻게 연결되는지 이야기해보도록 하겠습니다. 이번 글은 고려대 강필성 교수님, 한양대 이상화 교수님 강의와 quora, 또 다크프로그래머의 블로그를 참고했음을 미리 밝힙니다. 그럼 시작하겠습니다.
주성분 분석
PCA는 데이터의 분산(variance)을 최대한 보존하면서 서로 직교하는 새 기저(축)를 찾아, 고차원 공간의 표본들을 선형 연관성이 없는 저차원 공간으로 변환하는 기법입니다. 이를 그림으로 나타내면 아래와 같습니다. 3차원 공간에 있는 데이터들이 서로 수직인 두 개의 주성분(PC1, PC2)을 새로운 기저로, 선형변환된 것을 확인할 수 있습니다. PCA 관련 자세한 내용은 이곳을 참고하시기 바랍니다.
원 데이터의 분산을 최대화하는 새로운 기저를 찾는 목표를 달성하려면 우선 데이터 행렬 $A$의 공분산 행렬부터 구해야 합니다. 데이터가 각 변수별로 평균이 0으로 맞춰져 있을 때(centering 작업 이미 수행되어 있다고 가정) 공분산 행렬은 아래와 같이 구합니다.
\[cov(A)=\frac { 1 }{ n-1 } A{ A }^{ T }\propto A{ A }^{ T }\]PCA의 새로운 축을 찾기 위해서는 위 공분산행렬을 아래처럼 고유분해(Eigen decomposition)를 수행해주어야 합니다. 아래 식에서 $Λ$는 대각성분이 공분산행렬의 고유값이고 나머지 요소는 0인 행렬, $U$는 열벡터가 공분산행렬 $AA^T$의 고유벡터로 이뤄진 행렬입니다.
\[A{ A }^{ T }=U\Lambda { U }^{T }\]여기에서 $Λ$의 대각성분은 데이터 행렬 $A$의 각 변수에 해당하는 분산을 의미합니다. 원 데이터의 분산을 최대화하는 새로운 기저를 찾는 것이 PCA 목표인 만큼 가장 큰 고유값 몇 개를 고르고, 그에 해당하는 고유벡터를 새로운 기저로 하여 원데이터를 사영(선형변환)해주면 PCA 작업이 완료되게 됩니다.
예컨대 변수가 100개(100차원)인 데이터에 PCA를 적용한 후 가장 큰 고유값 두 개에 해당하는 고유벡터로 원 데이터를 사영시키면 원데이터의 분산을 최대한 보존하면서도 그 차원수를 100차원에서 2차원으로 줄일 수 있게 됩니다.
특이값 분해
특이값분해는 m x n 크기의 데이터 행렬 $A$를 아래와 같이 분해하는 걸 말합니다.
\[A=U\Sigma { V }^{ T }\\\]
행렬 $U$와 $V$에 속한 열벡터는 특이벡터(singular vector)로 불리고요, 모든 특이벡터는 서로 직교하는 성질을 지닙니다.
\[U=\begin{bmatrix} \overrightarrow { { u }_{ 1 } } & \overrightarrow { { u }_{ 2 } } & ... & \overrightarrow { { u }_{ m } } \end{bmatrix}\\ V=\begin{bmatrix} \overrightarrow { { v }_{ 1 } } & \overrightarrow { v_{ 2 } } & ... & \overrightarrow { { v }_{ n } } \end{bmatrix}\\ \overrightarrow { { u }_{ k } } =\begin{bmatrix} { u }_{ k1 } \\ { u }_{ k2 } \\ ... \\ { u }_{ km } \end{bmatrix}\quad \overrightarrow { { v }_{ k } } =\begin{bmatrix} { v }_{ k1 } \\ v_{ k2 } \\ ... \\ { v }_{ kn } \end{bmatrix}\\ { \overrightarrow { { u }_{ k } } }^{ T }\overrightarrow { { u }_{ k } } =1,\quad { U }^{ T }U=I\\ { \overrightarrow { { v }_{ k } } }^{ T }\overrightarrow { { v }_{ k } } =1,\quad { V }^{ T }V=I\]행렬 $Σ$의 특이값은 모두 0보다 크거나 같으며 내림차순으로 정렬돼 있습니다. 행렬 $Σ$의 $k$번째 대각원소에 해당하는 특이값 $Σ_k$는 행렬 $A{A}^{T}$의 $k$번째 고유값에 제곱근을 취한 값과 같습니다.
\[{ \Sigma }_{ k }=\sqrt { { \lambda }_{ k } } \]그러면 특이값 분해를 주성분 분석과 비교해보기 위해 행렬 $A$를 제곱해 보겠습니다. 이후 식을 정리하면 아래와 같습니다.
\[\begin{align*} A{ A }^{ T }&=U\Sigma { V }^{ T }{ (U\Sigma { V }^{ T }) }^{ T }\\ &=U\Sigma { V }^{ T }V\Sigma { U }^{ T }\\ &=U{ \Sigma }^{ 2 }{ U }^{ T }\\ &=U\Lambda { U }^{ T } \end{align*}\]여기서 대각성분이 행렬 $A$의 특이값이고 나머지 성분이 0인 행렬 $Σ$에 주의할 필요가 있습니다. $Σ$는 대각행렬(diagonal matrix)인데요, 대각행렬의 거듭제곱은 대각원소들만 거듭제곱을 해준 결과와 같습니다.
따라서 $Σ$의 제곱은 각 대각원소, 즉 행렬 $A$의 특이값들을 제곱해준 값과 똑같습니다. 그런데 행렬 $A$의 특이값은 $A{A}^T$의 고유값에 제곱근을 취한 값과 동일하므로, $Σ$을 제곱한 행렬은 행렬 $AA^T$의 고유값으로 이뤄진 행렬 $Λ$가 됩니다. 이는 정확히 주성분 분석의 결과와 같습니다.
특이값 분해의 여러 변형들
thin SVD
thin SVD는 $Σ$ 행렬의 아랫부분(비대각 파트, 모두 0)과 $U$에서 여기에 해당하는 부분을 모두 제거합니다. 이렇게 $U$와 $Σ$를 줄여도 $U_sΣ_sV^T$로 $A$를 원복할 수 있습니다.
compact SVD
compact SVD는 $Σ$ 행렬에서 비대각파트뿐 아니라 대각원소(특이값)가 0인 부분도 모두 제거한 형태입니다. 여기에 대응하는 $U$와 $V$의 요소 또한 제거합니다. 다시 말해 특이값이 양수인 부분만 골라낸다는 뜻입니다. 이렇게 $U$와 $Σ$, $V$를 줄여도 $U_rΣ_rV_r^T$로 $A$를 원복할 수 있습니다.
truncated SVD
truncated SVD는 $Σ$ 행렬의 대각원소(특이값) 가운데 상위 $t$개만 골라낸 형태입니다. 이렇게 하면 행렬 $A$를 원복할 수 없게 되지만, 데이터 정보를 상당히 압축했음에도 행렬 $A$를 근사할 수 있게 됩니다. 이후 설명드릴 잠재의미분석은 바로 이 방법을 사용합니다.
SVD 예시
\[A=U\Sigma { V }^{ T } \\ \\ \begin{bmatrix} 2 & 3 \\ 1 & 4 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}=\begin{bmatrix} 0.82 & -0.58 & 0 & 0 \\ 0.58 & 0.82 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 5.47 & 0 & 0 & 0 \\ 0 & 0.37 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}\begin{bmatrix} 0.40 & 0.91 \\ -0.91 & 0.40 \end{bmatrix}\]truncated SVD 예시
\[\begin{align*} { A }^{ ' }&={ U }_{ 1 }{ \Sigma }_{ 1 }{ V }_{ 1 }^{ T }\\ \\ \begin{bmatrix} 1.79 & 4.08 \\ 1.27 & 2.89 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}&=\begin{bmatrix} 0.82 \\ 0.58 \\ 0 \\ 0 \end{bmatrix}\begin{bmatrix} 5.47 \end{bmatrix}\begin{bmatrix} 0.40 & 0.91 \end{bmatrix} \end{align*}\]잠재의미분석 개요
예컨대 다음과 같은 문서들이 있다고 하면, 우리는 이를 토대로 단어-문서행렬 $A$를 만들 수 있습니다.
doc1 : 나,는,학교,에,가,ㄴ,다
doc2 : 학교,에,가,는,영희
doc3 : 나,는,영희,는,좋,다
| - | doc1 | doc2 | doc3 |
|---|---|---|---|
| 나 | 1 | 0 | 0 |
| 는 | 1 | 1 | 2 |
| 학교 | 1 | 1 | 0 |
| 에 | 1 | 1 | 0 |
| 가 | 1 | 1 | 0 |
| ㄴ | 1 | 0 | 0 |
| 다 | 1 | 0 | 1 |
| 영희 | 0 | 1 | 1 |
| 좋 | 0 | 0 | 1 |
잠재의미분석이란 위와 같은 단어-문서행렬(Word-Document Matrix), 단어-문맥행렬(window based co-occurrence matrix) 등 입력 데이터에 특이값 분해를 수행해 데이터의 차원수를 줄여 계산 효율성을 키우는 한편 행간에 숨어있는(latent) 의미를 이끌어내기 위한 방법론입니다. 대략적인 개념은 아래 그림과 같습니다.
잠재의미분석을 수행하는 절차는 이렇습니다. $n$개의 문서를 $m$개의 단어로 표현된 입력데이터 행렬 $A$가 주어졌다고 칩시다. $A$의 0보다 큰 고유값의 개수를 $r$이라고 할 때, $r$보다 작은 $k$를 연구자가 임의로 설정하고 $Σ_k$를 만듭니다. 이후 $U$와 $V$ 행렬에서 여기에 대응하는 부분만 남겨 $U_k$와 $V_k$를 만들어줍니다. 이렇게 되면 $A$와 비슷한 $A_k$ 행렬을 구축할 수 있습니다.
\[{ A }_{ k }={ U }_{ k }{ \Sigma }_{ k }{ V }_{ k }^{ T }\]위 식 양변에 $U_k$의 전치행렬을 곱해준 것을 $X_1$, $V_k$를 곱해준 것을 $X_2$라고 둡니다. 그러면 $X_1$의 경우 $n$개의 문서는 원래 단어수 $m$보다 훨씬 작은 $k$개 변수로 표현된 결과가 됩니다. $X_2$는 $m$개의 단어가 원래 문서 수 $n$보다 작은 $k$개 변수로 표현한 결과입니다. 이는 주성분 분석에서의 차원축소 효과와 비슷한 것으로 이해하면 좋을 것 같습니다.
\[{ { U }_{ k }^{ T }A }_{ k }={ { U }_{ k }^{ T }U }_{ k }{ \Sigma }_{ k }{ V }_{ k }^{ T }=I{ \Sigma }_{ k }{ V }_{ k }^{ T }={ \Sigma }_{ k }{ V }_{ k }^{ T }={ X }_{ 1 }\\ { A }_{ k }{ V }_{ k }={ U }_{ k }{ \Sigma }_{ k }{ V }_{ k }^{ T }{ V }_{ k }={ U }_{ k }{ \Sigma }_{ k }^{ T }I={ U }_{ k }{ V }_{ k }^{ T }={ X }_{ 2 }\]잠재의미분석 예시
자, 그럼 위에서 예로 든 단어-문서행렬 $A$를 가지고 잠재의미분석을 수행해 보겠습니다. $A$에 SVD를 수행하면 아래와 같이 쓸 수 있습니다. 숫자들이 엄청 많은데요, ‘아 이렇게 분해될 수 있구나’ 정도로 보고 슥 넘어가시면 될 것 같습니다.
\[A=U\Sigma { V }^{ T }\\ \\ \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}=\begin{bmatrix} -0.17 & 0.27 & -0.40 \\ -0.63 & -0.41 & -0.03 \\ -0.32 & 0.37 & 0.21 \\ -0.32 & 0.37 & 0.21 \\ -0.32 & 0.37 & 0.21 \\ -0.17 & 0.27 & -0.40 \\ -0.33 & -0.12 & -0.52 \\ -0.30 & -0.29 & 0.49 \\ -0.15 & -0.39 & -0.13 \end{bmatrix}\begin{bmatrix} 3.61 & 0 & 0 \\ 0 & 2.04 & 0 \\ 0 & 0 & 1.34 \end{bmatrix}\begin{bmatrix} -0.63 & -0.53 & -0.57 \\ 0.56 & 0.20 & -0.80 \\ -0.54 & 0.83 & -0.17 \end{bmatrix}\]그럼 $Σ$ 행렬의 특이값 가운데 상위 2개(3.61과 2.04)만 남기고 나머지를 제거하는 방식으로 truncated SVD를 수행해 보겠습니다. 아래와 같습니다.
\[{ A }^{ ' }={ U }_{ 2 }{ \Sigma }_{ 2 }{ V }_{ 2 }^{ T }\\ \begin{bmatrix} 0.71 & 0.44 & -0.09 \\ 0.97 & 1.04 & 1.99 \\ 1.15 & 0.76 & 0.04 \\ 1.15 & 0.76 & 0.04 \\ 1.15 & 0.76 & 0.04 \\ 0.71 & 0.45 & -0.09 \\ 0.62 & 0.58 & 0.88 \\ 0.36 & 0.45 & 1.11 \\ -0.09 & 0.14 & 0.97 \end{bmatrix}=\begin{bmatrix} -0.17 & 0.27 \\ -0.63 & -0.41 \\ -0.32 & 0.37 \\ -0.32 & 0.37 \\ -0.32 & 0.37 \\ -0.17 & 0.27 \\ -0.33 & -0.12 \\ -0.30 & -0.29 \\ -0.15 & -0.39 \end{bmatrix}\begin{bmatrix} 3.61 & 0 \\ 0 & 2.04 \end{bmatrix}\begin{bmatrix} -0.63 & -0.53 & -0.57 \\ 0.56 & 0.20 & -0.80 \end{bmatrix}\]솔직히 이렇게 봐서는 $A’$가 원데이터 행렬 $A$에 제대로 근사한 것인지 아리송합니다. $A’$의 각 요소값을 반올림해서 원 행렬 $A$와 비교해보겠습니다. 6행과 7행의 요소값이 조금 다를 뿐 거의 유사한 것을 확인할 수 있습니다.
\[round({ A }^{ ' })=\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix},\quad A=\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}\]그럼 $A’=U_2Σ_2V^T_2$ 양변의 맨 앞에 $U_2$의 전치행렬을 각각 곱해줄까요? 그 결과를 $X_1$이라고 두면 아래와 같습니다.
\[X_{1}=\begin{bmatrix} -2.28 & -1.90 & -2.07 \\ 1.14 & 0.42 & -1.64 \end{bmatrix}\]원데이터인 $A$와 SVD 결과인 $X_1$의 열(column)은 문서(문장)를 의미합니다. 단어-문맥행렬 $A$에서 각 문서들은 9개 단어(변수)들로 표현됐으나 $X_1$에서는 단 두 개의 변수들만으로도 표현이 가능해졌습니다. 이렇게 만든 $X_1$에 다양한 데이터마이닝 기법을 적용해 여러 가지 문제를 풀게 되는 것입니다.
자, 이제는 반대로 $A’=U_2Σ_2V^T_2$ 양변의 맨 뒤에 $V_2$를 각각 곱해볼까요? 그 결과를 $X_2$라고 두면 다음과 같습니다.
\[{ X }_{ 2 }=\begin{bmatrix} -0.63 & 0.56 \\ -2.30 & -0.84 \\ -1.16 & 0.76 \\ -1.16 & 0.76 \\ -1.16 & 0.76 \\ -0.63 & 0.56 \\ -1.20 & -0.24 \\ -1.10 & -0.60 \\ -0.57 & -0.80 \end{bmatrix}\]원데이터인 $A$와 SVD 결과인 $X_2$의 행(row)은 단어를 의미합니다. 단어-문맥행렬 $A$에서 각 단어들은 3개 문서(변수)들로 표현됐으나 $X_2$에서는 단 두 개의 변수들만으로도 표현이 가능해졌습니다. 이렇게 만든 $X_2$에 마찬가지로 다양한 데이터마이닝 기법을 적용해 여러 가지 문제를 풀게 됩니다.
잠재의미분석의 효과
이제까지 든 예시에서는 차원축소의 효과가 도드라져 보이진 않지만 데이터가 클 경우 그 효과가 드라마틱하다고 합니다. 실제로 네이버, 카카오 등 현업에서도 이러한 방법론을 많이 쓰고 있는 것으로 알려져 있습니다. 잠재의미분석은 이외에도 많은 장점이 있다고 합니다. Deerwester et ak.(1990)과 Landauer and Dumais(1997)은 이 기법을 적용하면 단어와 문맥 간의 내재적인 의미(latent/hidden meaning)을 효과적으로 보존할 수 있게 돼 결과적으로 문서 간 유사도 측정 등 모델의 성능 향상에 도움을 줄 수 있다고 합니다. Rapp(2003)은 입력 데이터의 노이즈 제거, Vozalis and Margaritis(2003)은 입력데이터의 sparsity를 줄이게 돼 그 효과가 좋다고 합니다. 잠재의미분석은 입력데이터의 크기가 m x n이고 문서당 평균 단어수가 $c$일 경우 계산복잡도가 $O(mnc)$이어서 그다지 무거운 알고리즘은 아닙니다. 하지만 새로운 문서나 단어가 추가되면 아예 처음부터 작업을 새로 시작해야 합니다. 이 때문에 최근에는 Word2Vec 등 뉴럴네트워크 기반의 representation 방법론도 각광을 받고 있습니다.
Comments