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