[NLP] Dimensionality Reduction

고려대학교 산업경영공학부 DSBA 강필성 교수님의 '[Korea University] Unstructured Data Analysis(Text Analytics)'

 

Dimensionality Reduction

텍스트 데이터가 BoW(Bag-of-Words)로 표현되었을 때, 실제로는 일부 단어만이 text mining task와 연관되어있다.

•  High dimensionality : 단어의 수가 문서의 수보다 많다. → 기존의 통계적 방법론을 사용하기에 한계가 있다.
• Sparseness : TDM의 대부분의 원소가 0으로 이루어져 있다. → 저장(메모리)과 연산의 비효율성을 초래한다.

→ 연산의 효율성을 높이고 텍스트 마이닝의 성능을 높이기 위해서는 차원 축소(Dimensionality Reduction)가 필수적이다.

 



차원 축소에는 크게 두가지 방식이 있다.

• Feature Selection : 주어진 feature 중 유의미다고 판단되는 일부 feature만을 이용한다.
• Feature Extraction : 주어진 feature를 이용하여 데이터셋을 잘 표현하는 feature를 만든다.
  • 주성분 분석(Principal Component analysis, PCA) : 각 feature 간의 분산이 최대가 되도록 하는 방법.
  • 다차원 척도법(Multi-Dimensional scaling, MDS) : 각 feature 간의 거리 정보를 최대한 보전하는 방법.
  • 잠재 의미 분석(Latent Semantic Indexing, LSI) : DTM의 잠재된 의미를 이끌어내는 방법.

Feature Selection

Feature Selection의 대표적인 방법으로는 Information Gain이 있다. 특정 단어 $w$가 두 범주($Pos, Neg$)를 구분하는 데 있어 큰 정보량을 갖는다면 Infomation Gain은 큰 값을 갖는다.

• 특정 단어 $w$가 등장하지 않았을 때의 Entropy : $Entropy(absent\ w) = \Sigma_{\{C \in Pos, Neg\}} -P(C) \times \log ((P(C))$
• 특정 단어 $w$가 등장했을 때의 Entropy : $ Entropy(given\ w) = P(w)[\Sigma_{\{C \in Pos, Neg\}} -P(C|w) \times \log (P(C|w))] + P(\bar{w})[\Sigma_{\{C \in Pos, Neg\}} -P(C| \bar{w}) \times \log (P(C| \bar{w}))]$
• Information Gain : $IG(w) = Entropty(absent\ w) - Entropy(given\ w)$

Feature Extraction

1) Latent Semantic Analysis

LSA(Latent Semantic Analysis, 잠재의미분석)에 대해 이야기하기 앞서 특이값 분해(Singular Value Decomposition, SVD)를 이해할 필요가 있다. SVD란 $A$가 $m \times n$ 행렬(Text Mining에서의 TDM)일 때, 다음과 같이 3개의 행렬의 곱으로 분해하는 것을 의미한다.

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

• $U$ : $m \times m$ 직교행렬($AA^{T} = U(\Sigma \Sigma^{T})U^{T}$)
• $V$ : $n \times n$ 직교행렬 ($A^{T}A = V(\Sigma^{T} \Sigma)V^{T})$
• $\Sigma$ : $m \times n$ 직사각 대각행렬 

이때 SVD로 나온 대각 행렬의 대각 원소의 값을 행렬 $A$의 특이값(singular value)라고 한다. 대각 행렬 $\Sigma$의 대각 원소들, 즉 특이값들은 $ \Sigma_{11} \geq \Sigma_{22} \geq \Sigma_{33} \geq ... $와 같이 내림차순으로 정렬되어 있다. 또한, 양의 특이값의 수는 $A$의 계수(Rank)를 나타낸다고 할 수 있다.

SVD는 다양한 방식으로 축소할 수 있다. 그 중 Truncated SVD는 특이값 중에서 값이 큰 순서대로 T개를 선택하는 방식으로 이루어진다. LSA는 TDM에 Truncated SVD를 사용하여 차원을 축소시키고, 데이터의 구조적인 특징은 보전하는 것을 목적으로 한다.

Truncated SVD를 통해 TDM($m \times n$, $m$ : 단어의 수, $n$ : 문서의 수)를 $k \times n$ 행렬로 축소시킬 수 있다. $k$로 단어의 수를 줄이는 방법 이외에도 $$A_{k}V_{k} = U_{k}\Sigma_{k}(V_k^{T}V_{k}) = U_{k}\Sigma_{k}I = U_{k}\Sigma_{k}$$와 같이 $m \times k$ 행렬로 문서의 수를 줄이는 방법도 있다.

2) t-SNE

t-SNE(t-distributed stochastic neighbor embedding)는 하나의 데이터가 주어졌을 때 다른 데이터가 해당 데이터의 이웃일 확률을 계산하는 방식으로 이루어진다.

이때 $q_{j|i}$가 $p_{j|i}$를 잘 표현하고 있는지 측정하기 위한 지표로서 KL(Kullback-Leibler) divergence를 사용한다.

KL divergence는 두 분포가 완전히 일치할 경우에 0이 된다. 즉 저차원 공간 상에서 계산된 확률 분포가 고차원 공간 상에서 $j$번째 데이터가 $i$번째 데이터의 이웃일 확률에 대한 분포와 일치할 경우에는 고차원 공간 상에서 나타난 특징이 저차원 공간 상에 잘 보전되어있음을 의미한다.