主成分分析 Principal Component Analysis (PCA) 推導、證明 (using Lagrange multiplier)

序言:當我們需要將 n 個 m 維 data 投影到 k 維中時 (n>k ,即為降維投影)
PCA 可以幫我們找到 k 個互相垂直且長度為 1 的向量
使得投影到那些向量後的 data 有最大的變異數 (可以保留最多原本的 data 特性)
而此降維的投影動作可以幫助我們做特徵擷取 (feature extracting)


1. 當投影到一維的時候


將 n 個 m 維 data 投影到某一向量中,使 n 個 data 間的變異數最大
另變異數為 J,data 為 $X=[x_1, x_2, ..., x_n]$ (shape of X = (m,n))
$$ J = {1 \over n} \sum^n_{i=1} (t^T x_i - t^T \bar{X}) (t^T x_i - t^T \bar{X})^T$$

t is an unknown project vector (we can set $\Vert t \Vert$ to be 1 so that $t^T x_i$ can be projected vector of $x_i$); 
$t^T x_i$ means one projected datum, and $t^T \bar{X}$ means the projected sample mean.

整理上式
$$ J = {1 \over n} \sum^n_{i=1} t^T (x_i- \bar{X}) ( x_i - \bar{X})^T t$$
$$ = t^T {1 \over n} \sum^n_{i=1} (x_i - \bar{X}) ( x_i - \bar{X})^T t$$

${1 \over n} \sum^n_{i=1} (x_i - \bar{X}) ( x_i - \bar{X})^T$ 可以計算得知,可設為 S,上式等於$ t^T S t$

Use Lagrange function: (可參考文章 Lagrange Multiplier)
$$ L = t^T S t - \lambda (t^T t - 1)$$
求極值:${\partial L \over \partial t}=0 $ 
$$2St - 2 \lambda t = 0, St=\lambda t$$
故 t 的必要條件:須為 S 之eigen-vector

而變異數$t^T S t$在上述條件下可寫為 $t^T \lambda t = \lambda$,即為 S 之 eigenvalue
(S 的 eigenvalue 皆為非負實數:可參考文章 Singular Value Decomposition 中的 6.)
又知 S 之 eigenvalue $\lambda_1' \geq \lambda_2' \geq \dots$ 符合 $S u_i = \lambda_i' u_i$

故選 $\lambda_1'$ 作為 J 的最大值,而$u_1$作為投影用向量 


2. 當投影到 k 維的時候


將 n 個 m 維 data 投影到某 k 個互相垂直且長度為 1 的向量中,使 n 個 data 間的變異數最大
假設:其中 k-1 個投影用向量會是 $u_1, u_2, ..., u_{k-1}$
則現在只是要找 $t_k$ 使投影到該向量上的 data 變異數為最大

Use Lagrange function:
$$L = {t_k}^T S t_k - \sum^{k-1}_{j=1} \lambda_j ({u_j}^T t_k - 0) - \lambda_k (t_k^T t_k - 1)$$
求極值:${\partial L \over \partial t_k}=0 $ 
$$ S t_k - \sum^{k-1}_{j=1} \lambda_j {u_j}  - \lambda_k t_k = 0$$

然後我們證明 $\lambda_j=0$ for j = 1, ..., k-1
for i = 1, ..., k-1 ,上式等號兩邊同乘 ${u_i}^T$
$$ {u_i}^T S t_k - \sum^{k-1}_{j=1} \lambda_j {u_i}^T{u_j} - \lambda_k {u_i}^T t_k = 0$$
apply Eigen Decomposition to S: $S=UDU^T$ (可參考文章 Eigen Decomposition)
$$ {u_i}^T UDU^T t_k -  \lambda_i  = 0 $$
$$ [0,0, ..., 1_{index=i}, 0,0,...0]D\begin{bmatrix} 0 \\[0.5em] \vdots\\[0.5em] 0_{index=k-1>i}\\[0.5em]X\\[0.5em] \vdots \\[0.5em] X \end{bmatrix} =0=\lambda_i$$

$\lambda_j=0$ for j = 1, ..., k-1 =>
$$ S t_k -  \lambda_k t_k = 0$$
又知 $t_k$ 需垂直於$u_1, u_2, ..., u_{k-1}$ => $t_k \neq \lambda_1', \lambda_2,' ..., \lambda_{k-1}'$

故選$u_k$作為投影用向量 


3. 為什麼 2. 中的假設成立?


在我參考其他地方的推導時,他們都直接把這裡當已知。不過個人覺得,這個假設的正確性不太直覺。
↑以三維投影到二維為例:data 投影在 "以假設求出的兩個向量"後,變異數分別是 4, 2,如何保證三維空間中不會有兩個互相垂直的向量,data 投影在其中的變異數總和會比前者還高?

所以想要嘗試證明一下此假設,不過花超久時間的。思考了一個晚上後,結果還發現另一個不用 Lagrange multiplier 就能推導 PCA 的方法,順便證明該假設成立。(下集待續)

... 那是不是用 Lagrange multiplier 去證會有 bug 阿?
  

沒有留言:

張貼留言