謝宗翰的隨筆

以下我們介紹機器學習/統計學習理論 中把 高維度資料 降維 的一種常用工具，稱作 主成分分析 (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$ 投影到 sub

Claim: 令 $A \in \mathbb{R}^{m \times n}$，且 $\lambda >0$ 則以下等式成立 \[ (A^TA+\lambda I)^{-1}A^T = A^T(AA^T+\lambda I)^{-1} \] Proof: 觀察 $A^TAA^T+\lambda A^T$ 可對其從左方或者右方提出 $A^T$，亦即 \[\begin{align*} A^T(AA^T+\lambda I) = (A^TA+\lambda I)A^T \end{align*}\]由於 $(AA^T +\lambda I)$ 為可逆，$(AA^T+\lambda I)^{-1}$存在，故對上式兩邊從右方同乘此項可得 \[ A^T = (A^TA+\lambda I)A^T(AA^T+\lambda I)^{-1} \]又注意到 $(A^TA+\lambda I)$ 為可逆，$(A^TA+\lambda I)^{-1}$存在，對上式從左方同乘此項可得 \[ (A^TA+\lambda I)^{-1}A^T = A^T(AA^T+\lambda I)^{-1} \]至此證明完畢。$\square$ Comments: 上述結果多出現於一類稱作 Tikhonov Regularization (或者有拘束的最小二乘方問題)問題之中：亦即令 $A \in \mathbb{R}^{m \times n}$ 且 ${\bf x},{\bf y}\in \mathbb{R}^{n}$，$\lambda >0$考慮 \[ \min_{\bf x}\|A{\bf x} - {\bf y}\|_2^2 + \lambda \|{\bf x}\|_2^2 \]則不難證明上述最佳化問題之解為 \[ {\bf x}= (A^TA+\lambda I)^{-1}A^T {\bf y}  = A^T(AA^T+\lambda I)^{-1}{\bf y} \]上述第二等式成立因為 前述 claim。故我們在實際計算反矩陣時，可以決定到底要用 哪一個 inverse來加速計算速度，比如 $A \in \mathbb{R}^{5000\times 100}$ 那麼 $(A^TA+\lambda I)^{-1}$ 要求對 $10