主成分分析 - 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?

Avatar
Te-Sheng Lin (林得勝)
Associate Professor

The focus of my research is concerned with the development of analytical and computational tools, and further to communicate with scientists from other disciplines to solve engineering problems in practice.

Related