主成分分析 - 2

這裡我們補充一下主成分分析裡的證明部分.

假設我們有 $n$ 筆 $p$ 維的資料, 記成 $$ \{x_1, x_2, \cdots, x_n\} \in R^p. $$ 假設想要投影到 $k$ 維, $k\le p$, 數學上來說就是想要找到 $\mu$, $U$ 以及 $\beta_i$ 使得下式 $E$ 有最小值 $$ E = \sum_{i=1}^n \|x_i - (\mu + U\beta_i)\|^2, $$ 其中有兩個條件, $U^TU=I_k$, 以及 $\sum^n_{i=1} \beta_i=\vec{0}$.

要求極值就是要找微分等於零的解, 由於這式子是 convex, 所以保證找到唯一解而且是最小的.

所以以下做法就是對每個變數做偏微分, 並求出偏微分等於零的解. 這樣就把最佳解找出來了!

1. 首先看 $\mu$

對 $\mu$ 做偏微分並且利用 $\sum^n_{i=1} \beta_i=\vec{0}$ 我們可以得到 $$ \partial_{\mu} E = -2 \left(\sum_i x_i - n\mu\right)=0. $$ 因此, 最佳的 $\mu$ 是 $$ \mu = \frac{1}{n}\sum_{i=1}^n x_i. $$

2. 接著找 $\beta_i$

找到平均後我們將所有資料做平移使得中心為原點, 定 $y_i = x_i-\mu$, 我們有 $$ E = \sum_{i=1}^n \|y_i - U\beta_i\|^2. $$ 接著對 $\beta_i$ 微分得到 $$ \partial_{\beta_i} E = 2\left(\beta_i - U^Ty_i\right)=0. $$ 因此可以得到 $$ \beta_i = U^T y_i = \sum^k_{j=1}<u_j, y_i>, $$ 其中 $U=[u_1, \cdots, u_k]$.

3. 最後找 $U$

代入最佳的 $\beta_i$ 後我們又可將原本的 $E$ 改寫為 $$ E = \sum_{i=1}^n \|y_i - UU^Ty_i\|^2 = \|Y - UU^TY\|^2_F, $$ 其中 $Y=[y_1, \cdots, y_n]$, 而下標 $F$ 代表矩陣的 Frobenius norm.

我們先定 $P = UU^T$, 則有 $P^T=P$, $P^2=P$. 接著我們改寫 $E$ 為 $$ E = \|Y - PY\|^2_F = trace\left[(Y-PY)^T(Y-PY)\right] = trace\left(Y^TY-Y^TPY\right). $$ 由於 $Y$ 不會變, 因此求 $E$ 的最小值變成求 $trace\left(-Y^TPY\right)$ 的最小值, 也就是求 $trace\left(Y^TPY\right)$ 的最大值, 換回來得到是求 $trace\left(Y^TUU^TY\right)$ 的最大值.

接著我們用線性代數裡一個定理, $trace(AB)=trace(BA)$, 將原式轉換成求 $trace\left(U^TYY^TU\right)$ 的最大值, 最後得到 $$ \arg\min_U E = \arg\max_U trace\left(U^T\Sigma U\right), $$ 其中 $\Sigma=YY^T$ 也就是原資料的共變異數矩陣. 上式是個非常重要的式子, 它告訴我們以下兩件事是等價的:

1. 使得原始資料與投影後的資料之間的距離平方和最小
2. 使得資料有最大的變異性

最後, 線性代數告訴我們等號右邊這問題的解就是 $\Sigma$ 最大的 $k$ 個 eigenvalues 其相對應的 eigenvectors, 收集起來得到 $U=[u_1, \cdots, u_k]$.

以上使用的線性代數結果, 其證明可見 tr(AB)=tr(BA) proof, 以及 maximize v^T Av.

總結一下最佳解如下:

1. $\mu$ 是原始資料的平均 $$ \mu = \frac{1}{n}\sum^n_{i=1} x_i $$

2. 找到平均後我們將所有資料做平移使得中心為原點, 定 $y_i = x_i-\mu$, 求出這組新資料的共變異數矩陣 $\Sigma=YY^T$, 其中 $Y=[y_1, \cdots, y_n]$.

   對 $\Sigma$ 做譜分解(spectral decomposition), 找到其最大的 $k$ 個 eigenvalues 以及相對應的 eigenvectors, 將 eigenvectors 收集起來就得到 $U=[u_1, \cdots, u_k]$, 也就是 affine subspace 的 basis.

3. 將平移後的資料投影到子空間中得到 $\beta_i$, 也就是 $$ \beta_i = \sum^k_{j=1}<u_j, y_i>. $$

References:

1. NCTS mini-course on manifold learning
2. What is principal component analysis?