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 阿？
沒有留言:
張貼留言