선형대수 6-5*. PCA

• goodfellow의 딥러닝 저서를 보고 정리한 내용으로 작성중입니다

Principal Componens Analysis

• Condition
  - suppose we have a collection of m points $\{ \boldsymbol{x} ^{(1)},\boldsymbol{x} ^{(2)},\cdots,\boldsymbol{x} ^{(m)} \}$ in $\mathbb{R}^n$
  - suppose we would like to apply lossy compression to these points
  - Lossy compression means strong the points in a way that requires less memory but may lose some precision
  - we would like to lose as little precision as possible

• Statement
  - we can make encoding function $f$ such that for each point $\boldsymbol{x} ^{(i)} \in \mathbb{R} ^{n}$ corresponds code vector $\boldsymbol{c} ^{i} \in \mathbb{R} ^{l}$ , where $l<n$
  - $f(\boldsymbol{x}) =\boldsymbol{c}$
  - we can make decoding function $g$ such that $\boldsymbol{x} \sim g(f(\boldsymbol{x}))$
  - For simple, choose suppose $\boldsymbol{D} \in \mathbb{R} ^{n \times l}$
  - let columns of $\boldsymbol{D}$ to be orthogonal to each other
  - we can control the scale of $\boldsymbol{D}$. in this case, we constrain all of the columns of $\boldsymbol{D}$ to have unit norm
  - Let $g(\boldsymbol{c})=\boldsymbol{D}\boldsymbol{c}$
  - we can find optical point $\boldsymbol{c} ^{*}$ by calculating the minimized distance between $\boldsymbol{c} ^{*}=argmin \,\,{\boldsymbol{c}}\,\, \| \boldsymbol{x}- g(\boldsymbol{c}) \|$
  - we can switch to the squared $L^2$ norm instead of $L^2$ norm itself, because both are minimized by same value of $\boldsymbol{c}$
  - $\boldsymbol{c} ^{*}=argmin \,\,{\boldsymbol{c}} \| \boldsymbol{x} - g(\boldsymbol{c}) \|_2^2$
  - $(\boldsymbol{x}-g(\boldsymbol{c}))^T(\boldsymbol{x}-g(\boldsymbol{c}))$
  - $=\boldsymbol{x} ^{T} \boldsymbol{x} - \boldsymbol{x} ^{T}g( \boldsymbol{c})- g(\boldsymbol{c}) ^{T} \boldsymbol{x}+g(\boldsymbol{c}) ^{T}g(\boldsymbol{c})$
  - $=\boldsymbol{x} ^{T} \boldsymbol{x}- 2 \boldsymbol{x} ^{T}g(\boldsymbol{c}) + g(\boldsymbol{c}) ^{T} g( \boldsymbol{c})$ (because $\boldsymbol{x} ^{T} g(\boldsymbol{c})$ is scalar)
  - we can ignore first term since this term does not depend on $\boldsymbol{c}$
  - $\boldsymbol{c} ^{*}=argmin \,\,\{\boldsymbol{c}\}\,\, -2\boldsymbol{x} ^{T}g(\boldsymbol{c})+g(\boldsymbol{c}) ^{T}g(\boldsymbol{c})$
  - $=argmin \,\,\{\boldsymbol{c}\}\,\, -2\boldsymbol{x} ^{T}\boldsymbol{D}\boldsymbol{c}+\boldsymbol{c} ^{T}\boldsymbol{D} ^{T}\boldsymbol{D}\boldsymbol{c}$
  - $=argmin \,\,\{\boldsymbol{c}\}\,\, -2\boldsymbol{x} ^{T}\boldsymbol{D}\boldsymbol{c}+\boldsymbol{c} ^{T}\boldsymbol{I} _{l} \boldsymbol{c}$
  - (by orthogonality and unit norm constraints of $\boldsymbol{D}$)
  - $= argmin \,\,\{\boldsymbol{c}\}\,\, -2\boldsymbol{x} ^{T}\boldsymbol{D}\boldsymbol{c}+\boldsymbol{c} ^{T}\boldsymbol{c}$
  - $\nabla{}_{\boldsymbol{c}}(-2\boldsymbol{x} ^{T} \boldsymbol{D} \boldsymbol{c}+\boldsymbol{c} ^{T} \boldsymbol{c})=0$
  - $-2\boldsymbol{D} ^{T}\boldsymbol{x}+2\boldsymbol{c}=0$
  - $\boldsymbol{c}=\boldsymbol{D} ^{T}\boldsymbol{x}$

  	- conclusion
  		- $f(\boldsymbol{x})=\boldsymbol{D} ^{T}\boldsymbol{x}$

• Statement2
  - $r(\boldsymbol{x})=g(f(\boldsymbol{x}))=\boldsymbol{D}\boldsymbol{D} ^{T}\boldsymbol{x}$
  - We will find the $\boldsymbol{D}$ minimizing the $L ^{2}$ distance between inputs and reconstructions
  - $\boldsymbol{D} ^{*}=argmin \,\,\{\boldsymbol{D}\}\,\, \sqrt{\displaystyle\sum_{i,j}^{}{(x _{j} ^{(i)}-r(\boldsymbol{x} ^{(i)})_{j}) ^{2}}}$ (subject to $\boldsymbol{D} ^{T} \boldsymbol{D}= \boldsymbol{I} _{l}$)
  - To derive the algorithm for finding $\boldsymbol{D} ^{*}$, we will start by considering the case where $l=1$
  - In this single case $\boldsymbol{D}$ is just a single vector $\boldsymbol{d}$
  - $\boldsymbol{d} ^{*}= argmin \,\,\{\boldsymbol{d}\}\,\, \displaystyle\sum_{i}^{}{\| \boldsymbol{x} ^{(i)}-\boldsymbol{d}\boldsymbol{d} ^{T}\boldsymbol{x} ^{(i)} \|^2 }$ subject to $\| \boldsymbol{d}_{2} \|=1$
  - exploiting the fact that a scalr is its own transpose
  - $\boldsymbol{d} ^{*}=argmin \,\,\{\boldsymbol{d}\}\,\, \displaystyle\sum_{i}^{}{\| \boldsymbol{x} ^{(i)} - \boldsymbol{d} ^{T}\boldsymbol{x}^{(i)} \boldsymbol{d} \|}^2$ subject to $\| \boldsymbol{d}_{2} \|=1$
  - let $\boldsymbol{X} \in \mathbb{R} ^{m \times n}$ be matrix defined by stacking all of the vectors describing the points such that $\boldsymbol{X}_{i,:}=\boldsymbol{x}^{(i)^T}$
  - we can now rewrite the problem as
  - $\boldsymbol{d} ^*=argmin \,\,\{\boldsymbol{d}\}\,\, \| \boldsymbol{X}-\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^T \| ^{2}_{F}$
  - 여기서 Frobenius norm은 $\| \boldsymbol{X} \| ^{2}_{F}=Tr(\boldsymbol{X}\boldsymbol{X} ^{T})=\sqrt{\displaystyle\sum_{i}^{}{\displaystyle\sum_{j}^{}{|x _{ij}| ^{2}}}}$이다
  - $argmin \,\,\{\boldsymbol{d}\}\,\, \| \boldsymbol{X}-\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^T \| ^{2}_{F}$
  - $=argmin \,\,\{\boldsymbol{d}\}\,\, Tr((\boldsymbol{X}-\boldsymbol{Xd}\boldsymbol{d}^T)^T(\boldsymbol{X}-\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^T))$
  - $=argmin \,\,\{\boldsymbol{d}\}\,\, Tr(\boldsymbol{X}^{T}\boldsymbol{X}-\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^T-\boldsymbol{d}\boldsymbol{d}^{T}\boldsymbol{X}^{T}\boldsymbol{X}+\boldsymbol{d}\boldsymbol{d}^{T}\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{T})$
  - $=argmin \,\,\{\boldsymbol{d}\}\,\, -Tr(\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{T})-Tr(\boldsymbol{d}\boldsymbol{d}^{T}\boldsymbol{X}^{T}\boldsymbol{X})+Tr(\boldsymbol{dd}^{T}\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{T})$
  - (term not involving $\boldsymbol{d}$ ignored since do not affect the arg min)
  - use property of 'Trace of matrix'
  - $=argmin \,\,\{\boldsymbol{d}\}\,\, -2Tr(\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{T}+Tr(\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{T}\boldsymbol{d}\boldsymbol{d}^{T}))$
  - subject to $\boldsymbol{d}^{T} \boldsymbol{d}=1$
  - =-$argmin \,\,\{\boldsymbol{d}\}\,\, Tr(\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{T})$
  - subject to $\boldsymbol{d}^{T} \boldsymbol{d}=1$
  - =$argmax\{\boldsymbol{d}\}\,\,Tr(\boldsymbol{d}^{T}\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{d})$
  - subject to $\boldsymbol{d}^{T} \boldsymbol{d}=1$
  - optimal $d$ is given by eigenvector of $\boldsymbol{X}^{T}\boldsymbol{X}$ corresponding to the largest eigenvalue
  - In the general case, the matrix $\boldsymbol{D}$ is given by $l$ eigenvectors corresponding to the largest eigenvalues This may be shown using proof by induction