[機器學習] 主成分分析 (1)

以下我們介紹機器學習/統計學習理論 中把 高維度資料 降維 的一種常用工具，稱作 主成分分析 (Principal Component Analysis)。假設我們有 $n$ 組 $m$ 維度 (去除平均) 資料點集，下圖 顯示 $n=100$ 組 $m=2$ 維 資料點集

注意到上述資料集已經先預先處理使其資料集 中心 在 $(0,0)$。任意(有限維度)資料集皆可預先做此處理將其資料點的平均值 預先 移除。此為主成分分析的首要步驟。


主成分分析(Principal Component Analysis)：
我們的目標為 找到一個向量 ${\bf x} \neq {\bf 0}$ 使得 由此向量所 線性張成(span) 的子空間，記作 $X:=span\{{\bf x}\}$ ，能 最佳適配我們得資料集 (此 subspace $X$ 又稱作 "best line ") 使得\[
\min_{\bf x} \sum_{i=1}^n d_i^2
\]其中 $d_i$ 為第 $i$ 個 資料點 到此  best line (subspace) $X$ 的距離。

Comments: (1) 此處最佳 "best line" 意指我們要找 ${\bf x}$ 使得 資料點到此 best line 的距離平方最小，此想法可參閱下方示意圖，其中 ${\bf a}_i$ 為代表 第 $i$ 個資料點的向量，$proj_X{\bf a}_i$ 代表 ${\bf a}_i$ 投影到 我們的 subspace $X$ 的投影向量。

(2) 當然，距離平方最小並不是唯一的選擇，讀者可以考慮使用 $\sum_i |d_i|$ 當作 最佳化的目標函數或者其他種類的目標函數，但為求簡單起見，且符合經典 主成分分析的內容，在此我們僅考慮 距離平方誤差 作為我們的 目標函數。

(3) 由下圖，讀者不難發現對任意資料向量 ${\bf a}_i$ 而言，此向量 與 subspace $X$ 的 距離平方 $d_i^2$ 可表為
\[
d_i^2  = \| {\bf a}_i - proj_X {\bf a}_i \|_2^2
\]其中 $proj_X {\bf a}_i$ 表示 ${\bf a}_i$ 投影到 subspace $X$ 的向量 。

Claim: 令資料矩陣 \[ A:= \begin{bmatrix} -{\bf a}_1^T- \\ -{\bf a}_2^T- \\ \vdots\\ -{\bf a}_n^T- \end{bmatrix} \in \mathbb{R}^{n \times m} \]則存在 ${\bf x}={\bf v}_1$  為 1st right-singular vector of $A$ 使得
\[
\min_{{\bf x}} \sum_{i=1}^n d_i^2 = \sigma_2^2+\cdots + \sigma_n^2
\]其中 $\sigma_1$ 為 $A$ 的 1st singular value 。

Proof: 對任意資料向量 ${\bf a}_i \in \mathbb{R}^m$ 而言，${\bf a}_i$ 與 待定向量 ${\bf x} \in X$ 的 距離平方 $d_i^2$ 可表為
\[
\begin{align*} d_i^2 & = \| {\bf a}_i - proj_{\bf x} {\bf a}_i \|_2^2 \\
&= \bigg\|{\bf a}_i - \frac{ {\bf a}_i^T {\bf x}}{ {\bf x}^T {\bf x}  }{\bf x} \bigg\|_2^2\\
 & = \bigg\|{\bf a}_i - \frac{ {\bf x}^T {\bf a}_i}{{\bf x}^T {\bf x}}{\bf x} \bigg\|_2^2\\ & = \bigg\|{\bf a}_i - \frac{ {\bf x} ({\bf x}^T {\bf a}_i)}{{\bf x}^T {\bf x} }\bigg\|_2^2\\
 & = \bigg\|\bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x}} \bigg) {\bf a}_i \bigg\|_2^2\\
 & = \bigg(\bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg) {\bf a}_i \bigg)^T \bigg(\bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg) {\bf a}_i \bigg)\\
 & = {\bf a}_i ^T \bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x}} \bigg)^T \bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg) {\bf a}_i \\
 & = {\bf a}_i ^T \underbrace{\bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg)^2}_{= I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x}} }{\bf a}_i \\
 & = {\bf a}_i ^T \bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg){\bf a}_i \\
 & = {\bf a}_i ^T {\bf a}_i - {\bf a}_i ^T \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x}}{\bf a}_i \\ \end{align*}
\]注意到 $${\bf a}_i^T{\bf x} {\bf x}^T {\bf a}_i = \underbrace{({\bf a}_i^T{\bf x})}_{\in \mathbb{R}} \underbrace{({\bf x}^T {\bf a}_i)}_{\in \mathbb{R}} ={\bf x}^T ({\bf a}_i {\bf a}_i^T) {\bf x} $$故 \[ d_i^2 = {\bf a}_i ^T {\bf a}_i - \frac{ {\bf x}^T ( {\bf a}_i {\bf a}_i^T) {\bf x} }{\|{\bf x}\|}
\] 回憶我們的目標是要找到向量 ${\bf x} \neq {\bf 0}$ 使得 \[
\min_{{\bf x}} \sum_{i=1}^n d_i^2
\]上式等價於
\[
\min_{\bf x} \sum_{i=1}^n \bigg( {\bf a}_i ^T {\bf a}_i - \frac{ {\bf x}^T ( {\bf a}_i {\bf a}_i^T) {\bf x} }{{\bf x}^T {\bf x}} \bigg) = n {\bf a}_i ^T {\bf a}_i + \min_{\bf x} \bigg( - \frac{ {\bf x}^T ( \sum_{i=1}^n {\bf a}_i {\bf a}_i^T) {\bf x} }{{\bf x}^T {\bf x}}\bigg) 
\] 注意到第一項與 ${\bf x}$ 無關，利用 $\min_x -f(x)$ 等價為 $\max_x f(x)$ 我們可將上述最佳化問題等價為 \[ \max_{\bf x}\frac{ {\bf x}^T ( \sum_{i=1}^n {\bf a}_i {\bf a}_i^T) {\bf x} }{{\bf x}^T {\bf x}} \] 由 FACT 1，我們可知
\[ A^T A = \sum_{i=1}^n {\bf a}_i {\bf a}_i^T
\] 故我們最終的最佳化問題為找到向量 ${\bf x}$ 使得
\[
\max_{\bf x} \frac{{\bf x}^T A^T A {\bf x}}{{\bf x}^T {\bf x}} = \max_{\bf x} \frac{\|A {\bf x}\|_2^2}{\|{\bf x}\|_2^2} = \|A\|_2^2 \;\;\;\; (*)
\] 由 下方 FACT 2 可知 \[ \|A \|_2^2 = \sigma_1^2 \] 且 ${\bf x} = {\bf v}_1$, the 1st right-singular vector。此結果非常容易觀察：當 ${\bf x} = {\bf v}_1$ 則 $A{\bf v}_1 = \sigma_1 {\bf u}_1$ 故
\[
\frac{\|A {\bf x}\|_2^2}{\|x\|_2^2} = \frac{\|A {\bf v}_1\|_2^2}{\|{\bf u}_1\|_2^2} = \frac{\sigma_1^2 \|{\bf u}_1\|}{\|{\bf u}_1\|_2^2} = \sigma_1^2
\]故 ${\bf x}={\bf v}_1$ 取到最大值 $\|A \|=\sigma_1^2$，換言之，
\[
\min_{\bf x} \sum_{i=1}^n d_i^2 = (\sigma_1^2+...+\sigma_n^2 )- \sigma_1^2 = \sigma_2^2+\cdots + \sigma_n^2
\] 至此證明完畢。 $\square$


Comments:
1. ${\bf v}_1$ 又稱 $A$ 的 第一主成分 (the first principal component of $A$)

FACT 1: $A:= \begin{bmatrix} -{\bf a}_1^T- \\ -{\bf a}_2^T- \\ \vdots\\ -{\bf a}_n^T- \end{bmatrix} \in \mathbb{R}^{n \times m}$ 則
\[
A^TA = \sum_{i=1}^{n} {\bf a}_i {\bf a}_i^T
\]

Remark: 上述等式有個非常類似的結果與 矩陣的 trace 有關，我們順道在此紀錄：如果 $A:=\begin{bmatrix}{\bf a}_1 & {\bf a}_2 & \cdots {\bf a}_n \end{bmatrix} \in \mathbb{R}^{m \times n}$ 則
\[
\sum_{i=1}^n {\bf a}_i^T {\bf a}_i = trace(A^TA)
\]

FACT 2:
(a) 任意 $m \times n$ 矩陣 $A$ 的 2-norm $\|A\|_2 = \sigma_1$
(b) 任意 $m \times n$ 矩陣 $A$ 的 Fronbenious norm $\|A\|_F := \sqrt{\sigma_1^2+\sigma_2^2+\cdots + \sigma_n^2}$