從優化的角度看PCA降維的原理

04-30

參考周志華老師的西瓜書，對PCA的求解構成進行細節的推導，希望能有所幫助。

主成分分析簡稱PCA，是一種在儘可能減少信息損失的情況下找到某種方式降低數據的維度的方法。對於正交屬性空間中的樣本點，如何用一個超平面對所有樣本進行恰當的表達？這裡這個超平面應該有兩個性質：

I.最近重構性：重構後的樣本映射回原空間，與原樣本的距離都足夠的近；
II.最大可分性：樣本在這個超平面上的投影儘可能分開。

本文主要基於這個兩個性質，從PCA的公式推導的角度，來看優化在其中的作用。

一、最近重構性

設在n維空間中有m個樣本點矩陣X： $left{ x_1,x_2,x_3,...,x_m ight}^T$

現在對這些點進行壓縮，使其投影到k維空間中，其中k<n，使其損失的信息最小。設矩陣 $W=left{ w_1,w_2,w_3,...,w_k ight}$ ，是一個大小為n*k維的正交陣，也是投影矩陣，其中是標準的正交基向量，即滿足：

$||w_i||_2=1,w_i^Tw_j=0 (i eq j)$

由矩陣的乘法可知，將X經過W投影到k維空間的點的坐標為 $Z=XW$

所以，利用該坐標系重構數據，即把數據集合Z從k維空間重新映射回n維空間，得到新的坐標點 $Z=XWW^T$

這裡假設新得到的數據與原始的數據點之間的距離最小，即PCA可轉化為求解約束最優化問題：

$min_{W}{||X-X^*||_F}^2=min_{W}{||X-XWW^T||_F}^2$
$s.t. W^TW=I$ 1.1

根據F範數與矩陣跡的關係:

$||A||_F=sqrt{tr(AA^T)}$ 1.2

利用1.2對1.1進行簡化:

$min_{W}{||X-X^*||_F}^2=min_{W}tr((X-XWW^T)(X-XWW^T)^T)=min_{W}tr(XX^T)-min_{W}tr(XWW^TX^T)$ 1.3

由於 $XX^T$ 是已知項，不會影響到最優化的結果；有負號轉為最大值，所以1.4等式簡化為：

$min_{W}{||X-X^*||_F}^2=max_{W}tr(XWW^TX^T)$ 1.4

同時利用矩陣跡的循環不變性，1.4式變換為：

$max_{W}tr(XWW^TX^T)=max_{W}tr(W^TX^TXW)$ 1.5

最終PCA的最優化問題就簡化為：

$max_{W}tr(W^TX^TXW)$ $s.t. W^TW=I$ 1.6

利用拉個朗日乘子法來求解1.6的最優化問題，引入乘子 $lambda$ ，1.6式轉化為求解拉格朗日函數的極值：

$L(W,lambda )=tr(W^TX^TXW)+lambda*(I-W^TW)$ 1.7

對1.7式求W的偏導數，在導數為0處取極值：

$frac{partial L(W,lambda)}{partial W}=frac{partial tr(W^TX^TXW)+lambda*(I-W^TW)}{partial W}=0$ $Longleftrightarrow frac{partial tr(W^TX^TXW)}{partial W}=lambda W$
$Longleftrightarrow X^TXW=lambda W$ 1.8

從1.8式根據特徵向量的定義可知，W是由協方差矩陣 $X^TX in R^{m*m}$ 的特徵矩陣，特徵值越大，數據在其對應額特徵向量的方向上所包含的信息越豐富。

因此， $W=left{ w_1,w_2,w_3,...,w_k ight}$ $Win R^{n*k}$ ，就是取 $X^TX$ 的特徵矩陣中對應特徵值前k大的特徵向量，其中 $w_i$ 就是第i大的特徵向量。

二、最大可分性

從最大可分性出發，能得到PCA的另一種解釋。樣本點 $x_i$ 在新空間中超平面上的投影是 $x_iW$ ，若所有樣本點的投影能儘可能分開，則應該使投影后樣本點的方差最大化：

使所有的樣本的投影儘可能的分開，則敘最大話投影點的方差

投影后樣本點的方差是 $sum_iW^T{x_i}^tx_iW$ ，優化目標可以轉化為矩陣的跡：

$max_{W}tr(W^TX^TXW)$

$s.t. W^TW=I$

後面的求解構成與第一種的最近重構性一致。

PCA的演算法步驟：
輸入：n維空間的樣本集合其中；映射到k維空間
1、歸一化，將X中樣本變換為標準正態分布 $Nsim(0,1)$ ：
1.1 $x_i=x_i-frac{1}{m}sum_{i=1}^mx_i$
1.2 $x_i=frac{x_i}{sqrt{frac{1}{m}sum_{i=1}^m(x_i-0)^2}}$
2、計算協方差矩陣 $X^TX in R^{m*m}$
3、對協方差矩陣 $X^TX$ 進行特徵分解
$X^TX=V*Sigma *V^{-1}$
4、求取最大的k個特徵值以及對應的特徵向量，依次記錄為 $w_1,w_2,w_3,...,w_k$

輸出，其中 $W=left{ w_1,w_2,w_3,...,w_k ight}$