[CS246] Dimensionality Reduction (1) - Introduction

Demensionality Reduction

Reducing Matrix Reduction

대부분의 데이터는 행렬로 표현할 수 있다. 

예를 들어, $m \times n$ 행렬은 $m$개의 점들과 $n$개의 feature로 생각할 수 있다.

 

선형대수를 이용하면, 행렬을 3개의 행렬의 곱으로 나타낼 수 있다. 이때 새로 생기는 3개의 행렬은 더 작은 차원 $r$을 공유한다. 

예를 들어, SVD를 이용하면 $m \times n$ 행렬은 각각 $m\ times r,\ r \times r,\ r times n$ 이렇게 3개의 행렬을 얻게 되고 가운데 행렬은 대각행렬이기 때문에 $r \times r$은 사실상 $r \times 1$ 이다.

Example of SVD: $(m+n+1)r \ll mn$ (Stanford CS246)

Latent Factors

Example of Latent Factors (Stanford CS246)

원래 데이터의 차원을 $D$, 그리고 축소된(혹은 잠재공간) 차원을 $d$라 하자.

왼쪽 그림은 2차원 공간에 데이터가 저장되어있지만, 직선의 형태를 하고 있다. 사실상 latent dimension은 $d=1$이다. 빨간색 직선이 latent space가 된다.

 

오른쪽 그림은 $D=3$인 공간에 데이터가 저장되어있다. 그러나 자세히 살펴보면 3차원 공간에 랜덤하게 흩어진 것이 아니라, 어떤 평면 위의 점들로 생각할 수 있다. 이 경우 $d=2$인 것이다.

 

※ 경우에 따라 latent factor는 manifold가 될 수 있다.

 

Rank is "Dimensionality"

(선형대수에서) rank는 어떤 행렬의 선형독립인 행(또는 열)의 개수이다. basis의 개수와도 같다. (참고로 rank(row)=rank(column)이다. 증명 생략)

 

예를 들어 3차원 행렬 $M$이 다음과 같다고 하자. 

\[ M = \begin{bmatrix} 1 & 2 & 1 \\ -2 & -3 & -1 \\ 3 & 5 & 0 \end{bmatrix} \]

그러나 $\text{rank}(M)=2$ 이다. 

row의 관점에서 보면 $r_1 - r_2 - r_3 = \mathbf{0}$이고, column 관점에서 보면 $5c_1 - 3c_2 + c_3 = \mathbf{0}$ 이다.

 

각 행을 하나의 점이라 하자. 즉 $A(1, 2, 1),\ B(-2, -3, 1),\ C(3, 5, 0)$ 이라 생각하자.

Example Matrix (Stanford CS246)

새로운 기저 new basis를 다음과 같이 $[1, 2, 1],\ [-2, -3, 1]$이라 하면 위 세점은 새로운 좌표 $[1, 0],\ [0, 1],\ [1, -1]$로 나타낼 수 있다. 즉 원래 행렬 $M$이 2차원으로 축소시킨 것이다.

 

Why Reduce Dimensions?

• hidden correlation을 찾을 수 있다.
• 중복되거나 noisy한 feature를 제거할 수 있다.
• 해석(interpretation)와 시각화에 용이하다.
• 데이터 저장과 조작(manipulation)에 용이하다.