Principal Component Analysis (PCA)

Motivation

1. Clustering
   • 복잡한 real-valued data point를 하나의 categorical variable로 요약하는 것
2. Dimensionality reduction
   • 고차원 data를 단순화하는 방법
     • 고차원 data로 학습을 진행하면 overfitting 되기 쉽다.
   • Real valued vector를 낮은 차원의 data로 요약, 단순화하는 것

Data points의 차원이 $d$ 일 때

• $d$ 보다 작은 $r$ 차원으로 바꾼다.
• 차원을 낮출 때 정보의 손실을 최소화 해야 한다.

Data Compression

Parameter $\theta$의 복잡도를 낮추는 정규화와 달리 데이터에 초점을 두고 $x$의 차원을 줄인다.

• 이때 Data의 분포가 넓은 방향으로 축소해야 한다.
• 정보 손실이 적은 쪽으로 축소해야 한다.
• 따라서 분산이 큰 축을 찾아야 한다. $\rightarrow$ PCA
• 이때 $d$ 차원의 Data를 가장 잘 설명하는 축 상위 $r$개를 찾기만 하면 된다.

Principal Component Analysis problem formulation

• Reduce from 2-dim to 1-dim: Projection error를 최소화하는 projection 할 방향 벡터 $u^{(1)} \in \mathbb{R}^n$을 찾는다.
  • 방향 벡터: 낮은 차원의 축
• Reduct from d-dim to r-dim: Proejction error를 최소화하는 projection 할 방향 벡터 $u^{(1)}, u^{(2)}, \cdots, u^{(r)}$를 찾는다.

PCA의 Goal

1. Points의 mean vector $\mu$와 공분산 행렬 $\sum$을 계산한다.
2. $\sum$의 고유벡터와 고유값을 계산한다.
3. 최상위 $r$ 개의 고유벡터를 선택한다.
4. Points를 subspace로 투영한다.

Covariance

• Variance and Covariance: 중심으로부터 points가 퍼진(spread) 정도
• Variance: 1 차원에서 평균값으로부터 편차
• Covariance: 2 차원에서 points 분포의 경향성
  • Covariance는 두 차원에서의 관계를 나타낸다.
  • 1 차원에서 Covariance는 variance와 같다.
  • 2 차원에서 points의 분포를 variance로 계산한다면 서로 정반대의 분포이더라도 동일한 값이 나오는 문제가 있다.
    
  • 고차원 데이터가 있을 때 차원 간의 관계를 찾기 위해 공분산을 사용한다.
  • $j$ 차원과 $k$ 차원의 Covariance $q_{jk}$
    $q_{jk}=\frac{1}{N}\sum_{i=1}^{N}(X_{ij}-E(X_j))(X_{ik}-E(X_k))$
  • 다차원 확장
    
  • Covariance matrix
    • $x=[x_1, \cdots, x_n]^T$: sample data, $n$차원 column 벡터
    • $C=E[(x-m_x)(x-m_x)^T]$: $n \times n$ 행렬
    • $<C>_{ij}=E[(x_i-m_{xi})(x_j-m_{xj}^T)]$: $i$번째 성분과 $j$번째 성분의 공분산
  • $C$는 대칭 행렬이다.
    $C=\begin{bmatrix} C_{11} & \cdots & C_{1n} \\ \vdots & \ddots & \vdots \\ C_{n1} & \cdots & C_{nn} \end{bmatrix}$
    • 대각 원소는 분산이다.

고유값과 고유벡터

• Eigenvector: 정방 행렬 $M$을 곱하여 선형변환 했을 때 길이만 변하는 벡터 $\bar{v}$

  • 고유벡터는 크기만 달라지며 방향의 변화는 없다.
  • $Mv=\lambda v$를 만족하는 0이 아닌 벡터여야 한다.
  • 행렬 $M$의 $\lambda$에 대한 고유벡터

• Eigenvalue: 정방 행렬 $M$을 곱했을 때 벡터 $\bar{v}$의 길이 변화 $\lambda$

  • 행렬 $M$의 고유값
  • 고유값으로 분산을 계산하여 PCA 계산에 활용한다.
  • 가장 큰 고유값은 분산이 가장 크다.

• 고유값과 고유벡터는 없을 수도 있고 행렬의 차원($n$)에 따라 $n$개까지 있을 수도 있다.

• Example: $M = \begin{bmatrix} 4 & 2 \\ 3 & 5 \end{bmatrix}$

  • $Mv = \lambda v$

  • $(M-\lambda I)v = 0$

  • $(M-\lambda I)v$의 역행렬이 존재한다면 $v = (M-\lambda I)^{-1}0$, $v=0$으로 모순이다.

  • Eigenvector $v$는 0이 될 수 없으므로 $(M-\lambda I) = 0$이고 역행렬이 존재하지 않아야 한다.

  • $\det(M-\lambda I)=0$

    $Mv = \begin{bmatrix} 4 & 2 \\ 3 & 5 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \lambda v$	$4x_1+2x_2=\lambda x_1$ $3x_1+5x_2=\lambda x_2$
    $(M-\lambda I)v = 0$	$(4-\lambda)x_1+2x_2=0$ $3x_1+(5-\lambda)x_2=0$
    $\det(M-\lambda I)=0$
    $\begin{vmatrix}4-\lambda & 2 \\ 3 & 5-\lambda\end{vmatrix}=0$	$(\lambda-7)(\lambda-2)=0$

  1. $\lambda=2$
     $\begin{bmatrix} -3 & 2 \\ 3 & -2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$
     • $\lambda$는 고유한 값이지만 고유값에 대응하는 고유벡터는 여러 개일 수 있다.
     • $x_1=\frac{2}{3}x_2$로, 방향은 정해져 있지만 크기는 달라질 수 있다.
  2. $\lambda=7$
     $\begin{bmatrix} -2 & 2 \\ 3 & -3 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$
     • $x_1=-x_2$

Principal Component Analysis

데이터가 넓게 퍼진 분산값이 높은 축을 찾아 그 방향으로 projection하는 것
공분산 행렬 $C$를 구하고, 고유값이 큰 것에 해당하는 고유벡터로 projection한다.

• Input: $\mathbf{x} \in \mathbb{R}^{\mathcal{D}}:\mathcal{D}={x_1,\dots,x_N}$
  • 차원이 축소된 $\mathbf{ux}^T = \mathbf{z} = z_1, \dots, z_K$의 분산이 최대여야 한다.
  • 즉, $Var(\mathbf{ux}^T) = \mathbf{u}^TVar(\mathbf{x})\mathbf{u} = \mathbf{u}^TC\mathbf{u}$를 최대로 하는 $\mathbf{u}$를 찾아야 한다.
    • projection 된 $z_i$의 분산
      $\frac{1}{n}\sum_{i}(x_i\cdot \mathbf{u})^2$
      $=\frac{1}{n}(\mathbf{x}\mathbf{u})^T(\mathbf{x}\mathbf{u})$
      $=\frac{1}{n}\mathbf{u}^T\mathbf{x}^T\mathbf{x}\mathbf{u}$
      $=\mathbf{u}^TC\mathbf{u}$
  • 위 식을 만족하는 $\mathbf{u}$는 많을 수 있으므로 $|\mathbf{u}|=1$ 제약 조건을 걸어 라그랑지안 문제(조건부 최적화)로 해결한다.
• Basis vector: $\mathbf{U}=[\mathbf{u}_1, \dots, \mathbf{u}_k]$
  • 벡터 공간을 형성하는데 사용되는 기초적인 벡터
  • Symmetirc matrix의 고유벡터는 직교하므로 $\mathbf{u}_j^T\mathbf{u}_j=0$이 성립한다.
• New Data representation: $z_j=\mathbf{u}_j\cdot\mathbf{x}$
  • $h(\mathbf{x})=[z_1,\dots,z_K]^T$
  • $h(\mathbf{x})=\mathbf{U}^T\mathbf{x}$

PCA 과정

1. 데이터 $\mathbf{x}$의 공분산 행렬 $C$를 구한다.
2. $C\mathbf{u}=\lambda \mathbf{u}$
   • 공분산 행렬의 $\lambda$에 대한 고유벡터 $\mathbf{u}$를 찾는다.
   • $\mathbf{u}$는 데이터를 나타낼 새로운 축으로 $\mathbf{x}$가 $N$차원이라면 $\mathbf{u}$도 $N$ 차원이다.
3. $\lambda$가 큰 순서대로 $\mathbf{u}$를 정렬한다.
   • $\lambda$는 해당 축 $\mathbf{u}_i$이 데이터를 얼마나 잘 나타내는지 의미한다.