[ML] PCA 主成份分析

Posted on by
Post Views: 3,970

在上一篇的文章中，檸檬爸首先介紹如何使用 Python 與 Numpy 函式庫將想要分析的圖片載入多維的空間中，接下來就是需要開始分析這些圖片，假設一開始並不知道這些圖片的標籤的時候，我們沒有辦法執行分類的訓練。本篇想要介紹一下 Principle Component Analysis, PCA 主成份分析這一個方法背後的數學理論與物理意義，參考的是台大資工系林軒田教授的講義，在林教授的講解過程中，PCA 其實是 Auto-Encoder 中的一個線性特例，如果從 Auto-Encoder 的角度來看 PCA 的話可以更加了解 PCA 主成份分析的物理意義！

一般情況的 Auto-Encoder
可以描述成以下的數學式，輸入是維度為 d 的 \textbf{x} 向量，中間的神經元數量為 \tilde{d}，輸出為 h_i(\textbf{x}) 維度也是 d。

(1)   \begin{equation*} h_i(\textbf{x}) = \sum^{\tilde{d}}_{j=0}w^{(2)}_{ji}\tanh\left(\sum^{d}_{i=0}w^{(1)}_{ij}x_i\right) \end{equation*}

線性的 Auto-Encoder
線性的情況則可以描述成以下的數學式，輸入是維度為 d 的 \textbf{x} 向量，中間的神經元數量為 \tilde{d}，輸出為 h_i(\textbf{x}) 維度也是 d。

(2)   \begin{equation*} h_i(\textbf{x}) = \sum^{\tilde{d}}_{j=0}w^{(2)}_{ji}\left(\sum^{d}_{i=0}w^{(1)}_{ij}x_i\right) \end{equation*}

假設 w^{(2)}_{ji}=w^{(1)}_{ij}=w_{ij} 且用 W=[w_{ij}] 維度為 d\times\tilde{d} 的矩陣表示，另外為了合理性也假設 \tilde{d} < d，所以

(3)   \begin{equation*} \textbf{h}(\textbf{x}) = WW^T\textbf{x} \end{equation*}

物理意義
首先我們利用 eigen-decompose 的技術將 WW^T 用另外的方式表示，其中 V 是 d\times d 的正交矩陣也就是說 VV^T = V^TV = I_d，另外 \Gamma 是對角線矩陣，而且總共有 \leq\tilde{d} 個值不是零，主要是因為 W \in R^{d\times\tilde{d}} 的關係

(4)   \begin{equation*} WW^T = V\Gamma V^T \end{equation*}

所以線性 Auto-Encoder 的物理意義就是：

  1. 先利用一個 orthonormal 的基礎向量集合 V 將 x 向量轉置到另外一個向量空間 (Vector Space)
  2. 將一部分維度放大縮小，另外一部分維度設成 0
  3. 再利用同一組基礎向量集合將處理過後的向量轉回原本的向量空間
如果 \Gamma = I 矩陣的話，其實我們將一組向量轉置到另外一個向量空間維持個正交維度的長度不變再轉置回來理論上就會得到自己

(5)   \begin{equation*} WW^T\textbf{x}_n = VIV^T\textbf{x}_n = \textbf{x}_n \end{equation*}

Problem Formulation 問題表述
有了以上對 Auto-Encoder 的描述，我們可以架構我們的問題為：找出一個最佳化的矩陣 W (也就是一組 V, \Gamma) 使得 Auto-Encoder h(\textbf{x}) 的結果與原始資料的差距 E_{\text{in}}(\textbf{h}) 最小。

(6)   \begin{equation*} E_{\text{in}}(\textbf{h}) = E_{\text{in}}(W) = \frac{1}{N}\sum^{N}_{n=1}\|\textbf{x}_n-WW^T\textbf{x}_n\|^2 \end{equation*}

求解 W

以下我們 go through 一遍講義中的線性代數證明，也就是求解以下的最佳化問題：

(7)   \begin{align*} \min_{V,\Gamma}E_{\text{in}}(W) &= \min_{V,\Gamma}\frac{1}{N}\sum^{N}_{n=1}\|\textbf{x}_n-WW^T\textbf{x}_n\|^2\\ &= \min_{V,\Gamma}\frac{1}{N}\sum^{N}_{n=1}\|VIV^T\textbf{x}_n-V\Gamma V^T\textbf{x}_n\|^2 \end{align*}

因為使用 orthonormal 的向量集合轉置到另外一個向量空間並不會影響長度，所以我們將問題簡化，

(8)   \begin{align*} \min_{V,\Gamma}E_{\text{in}}(W) &= \min_{V,\Gamma}\sum^{N}_{n=1}\|(I-\Gamma)V^T\textbf{x}_n\|^2 \end{align*}

又因為我們希望 (I-\Gamma) 越多零越好，所以最佳化的 \Gamma = \begin{bmatrix} I_{\tilde{d}} & 0\\ 0 & 0 \end{bmatrix}。

(9)   \begin{align*} \min_{V,\Gamma}E_{\text{in}}(W) &=\min_{V}\sum^{N}_{n=1}\left \| \begin{bmatrix} 0 & 0\\ 0 & I_{d-\tilde{d}} \end{bmatrix} V^T\textbf{x}_n\right \|^2 \\ &\equiv \max_{V}\sum^{N}_{n=1}\left \| \begin{bmatrix} I_{\tilde{d}} & 0\\ 0 & 0 \end{bmatrix} V^T\textbf{x}_n\right \|^2 \end{align*}

如果 \tilde{d} = 1，那麼最佳化的工作就是找到一個 \textbf{v} 向量在條件 \textbf{v}^T\textbf{v} = 1 的條件下可以最大化

(10)   \begin{equation*} \max_{\textbf{v}}\sum^{N}_{n=1}\textbf{v}^T\textbf{x}_n\textbf{x}^T_n\textbf{v} \end{equation*}

因為 \sum^{N}_{n=1}\textbf{x}_n\textbf{x}^T_n\textbf{v} = X^T X \textbf{v}= \lambda\textbf{v} 所以最佳化誤差在 \tilde{d}=1 的情況下就是尋找 X^TX 中最大的特徵值對應的特徵向量作為 \textbf{v}，一般化情況 \tilde{d} \leq d，W=\{w_j\}=\{v_j\}^{\tilde{d}}_{j=1} 就是由 X^TX 中最大的 \tilde{d} 個特徵向量組成。
PCA 與 Auto-Encoder 的差異

其實 PCA 與 Auto-Encoder 在處理的問題還是有一點差異的，Auto-Encoder 是在處理最大化長度的問題，而 PCA 則是在處理最大化變異數的問題，但是其實兩個問題的本質是一樣的。

(11)   \begin{align*} \text{Auto-Encoder} &\rightarrow \max_{V}\sum^{N}_{n=1}\left \| \begin{bmatrix} I_{\tilde{d}} & 0\\ 0 & 0 \end{bmatrix} V^T\textbf{x}_n\right \|^2 \\ \text{PCA} &\rightarrow \max_{V}\sum^{N}_{n=1}\left \| \begin{bmatrix} I_{\tilde{d}} & 0\\ 0 & 0 \end{bmatrix} V^T(\textbf{x}_n-\bar{\textbf{x}})\right \|^2 \\ \end{align*}

PCA 在 Clustering 的應用實例

在以下連結中，作者使用 scikit-Learn 中的 PCA 主成份分析工具分析 MNIST 的圖片：

在 MNIST 的資料中實作 PCA, K-Means, LDA, t-SNE 等演算法

原本資料維度為 28 * 28 = 784 維，本篇作者展示將資料降維成 40 維一樣可以保持資料之間的差異性保持住，這邊值得一提的作者執行 PCA 之前有用

from sklearn.preprocessing import StandardScaler
X_std = StandardScaler().fit_transform(X)

先將資料去平均值與正規化，其實就是式子 (11) 在做的事情，取最大變異的兩個維度，可以得到以下的結果，結果顯示利用 PCA 降成兩個維度在做機器學習的效果可能部會太好，這邊可能要考慮使用一些非線性的分類方法，例如 t-SNE 等等！