[LG Aimers] Module 2.3(Mathematics for ML) : PCA (주성분분석)

1. Problem Setting

 

• 차원축소
  • Data의 dimension이 커질수록 분석하기가 힘듦
  • High-dimesional data를 어떻게 하면 Low-dimensional vector로 차원을 줄일 수 없는가
  • PCA (Principal Component Analysis) 가 가장 전통적이고 대표적인 방법

 

 

• PCA Algorithm
  • $\chi$ : Total Data Set (D차원 data vector N개로 구성됨)
  • $X_{i} = (x_{1,i}, x_{2,i}, ..... , x_{d,i})$
  • $X_{i}$ : 하나의 Data Point(vector)
  • $D$ : dimension of the vector ($ D \times 1 vector $)

 

• Centering : 각 Data Point 마다 Expectation을 빼는 것으로 처리 

 

• Standardization : 각 dimension ($d = 1,2,...,D$)마다 data point들을 standard deviation으로 나눠주기
  • linear transformation 
  • $\frac {(X - \mu_{x})} {\sigma} \sim Expectation = 0, Variance = 1$

 

• Eigenvalue, Eigenvector
  • Data Covariance Matrix를 구하기 
  • M(target 축소하고 싶은 dimension의 개수, $ M << D$)개의 가장 큰 eigenvalue 를 구하기
  • 이에 해당하는 eigenvector를 구하기

 

• Projection
  
  • 이루어진 공간으로 data point들을 projection(정사영) 시켜서 data point들을 이동시킴
  • 더 큰 Eigenvalue에 해당하는 Eigenvector의 방향을 기준으로 정사영시킨다

 

• Undo standardization & Centering
  • original data point를 이동시키게 됨

 

 

 

PCA를 거친 후에 Target dimesion M = 1로 한 data는 선분 위의 1차원 data가 됨

 

• Data Covarianve Matrix
  • $ S = \frac {1} {N} X X^{T} $ : Always positive definite (PD)
  • N : data의 개수
  • D : data의 dimension
  • $\chi$ : data matrix
  • $X_{1}, X_{2}, ... , X_{N}$ : data vectors(data point) - D dimension

 

 

 

• Original Data $X_{n}$(D차원)에 특정 행렬 $B$를 곱해서(PCA의 모든 과정이 선형변환) $Z_{n}$(M차원)으로 차원을 축소함

 

 

 

 

• PCA의 역할 : 선형적인 decoding, encoding을 하는 과정
  
  • original D-dimension data $x$에 어떤 행렬 $B$를 곱해서 차원을 축소 (M-dimension)  
  • standardization & centering undo  : $B^{T} = B^{-1}$을 곱해서 처리
    • B는 orthogonal matrix : $BB^{T} = I$
    • $B$ : Decoding
    • $B^{T}$ : Encoding

 

 

2. Maximum Variance Perspective

 

 

 

• PCA를 이용하여 차원축소
  • dimensionality reduction algorithm that maximizes the variance of low-dimensional data representation
  • data의 subspace를 찾아서 그 subspace에 projection 시켰을 때 data의 variance를 maximize하는 low-dimensional space를 찾는 것

 

 

 

 

 

 

• $X_{n}$ : original data point (D-Dimensional vector)
• $B$ : 어떤 data point를 low-dimensional space로 mapping하는 행렬
• $Z_{n}$ : mapping된 vector (M-Dimensional vector)
• $M << D$

 

 

 

 

어떤 B를 골라야 B space로 projection할 때 Z의 variance가 가장 커질 것인가?

 

S(data covariance matrix)의 largest eigenvalue에 해당하는 Eigenvector가 solution이 된다

 

 

수학적 귀납법에 의해 증명 가능

 

• Caution : 두 벡터의 내적을 표시할 때 $a^{T}b$로 표시하는 것이 맞다.
  • Transpose가 앞에 들어가 있어야 한다

Variance를 maximize하는 b를 구하기 w/ b의 크기에 대한 조건

lambda, b가 각각 eigenvalue, eigenvector가 된다, 결국 maximum variance는 maximum eigenvalue가 만드는 eigenvector에 의해 생긴다

Lagrange function 이용

apply KKT condition

 

 

 

3. Eigenvector Computation and Low-Rank Approximations

 

 

• Data covariance matrix S를 구한 후에 eigendecomposition을 통해 eigenvalue, eigenvector를 구하기

 

• original matrix X에 singular matrix decomposition을 적용 
  • Data covariance matrix S를 구성하는  꼴로 분해 : eigenvector, eigenvalue들을 구하기

 

 

 

 

 

• 어떤 Matrix가 주어져있을 때, L2-norm 관점에서 X와 가장 근사한 matrix A 를 찾고 싶음
  • rank A = M : low rank(M)으로 근사하는 최적의 $\tilde {X}_{M}$을 찾기

 

4. PCA in High Dimensions

 

 

• Data dimension >> number of Data
• $ X : D \times N$ matrix
• $XX^{T} : D \times D$ matrix
• $X^{T}X : N \times N$ matrix