接下來總結經典的無監督學習模型主成分分析(Principal component analysis, 簡稱PCA)。Ian分別在第二章和第五章從不同角度討論了PCA演算法，分別是在第二章線性代數中本徵分解和奇異值分解SVD之後和第五章無監督學習模型中，這裡總結在一起。

問題定義

機器學習有一類常見問題是有損壓縮（lossy compression),即我們對於原數據進行一些壓縮以減少存儲空間，這個過程中不可避免地會損失一些原有的信息，我們希望盡量減小精度的損失。

我們將這一問題用數學表示：假設我們有m個 R^n 空間中點 left{ x^{(1)},...,x^{(m)} ight} 的集合，對於每一個 x^{(i)}in R^n ，我們希望找到對應的壓縮後的矢量 c^{(i)}in R^l ，其中 l<m ，我們有編碼函數 f(x)=c ，還有可以利用壓縮後的信息重構原信息的解碼函數，並希望重構的信息與原信息盡量相同，即 xapprox g(f(x)) 。假設我們用矩陣乘法來解碼，則 g(c)=Dc ，其中 Din R^{n imes l} 是解碼矩陣。

為了使問題簡化，PCA演算法限制D的列是正交歸一的。

有損壓縮問題可表述為使得重構的點與原信息點的距離最小的優化問題，用公式表述為 c^* = argmin_c ||x-g(c)||^2 = argmin_c (x-g(c))^T(x-g(c))

優化問題

將 g(c)=Dc 代入最小化公式並化簡得 c^* = argmin_c -2x^TDc+c^Tc

令其梯度為零，則可得到 c=D^Tx

所以編碼函數為 f(x)=D^Tx

而PCA的重構操作則是 r(x)=g(f(x)) = DD^Tx

為了使重構結果與原輸入距離最小，D的優化問題可用公式表示為 D^* = argmin_D sqrt{sum_{i,j}{(x_j^{(i)}-r(x^{(i)})_j)^2}}

其正交歸一的限制條件為 D^TD = I_l

我們先來考慮 l=1 的情況，矩陣D就是一個向量d，優化問題轉化為

d^* = argmin_d sum_i ||x^{(i)}-(x^{(i)})^Tdd^T||^2 ，其中 ||d||_2=1

我們將所有的輸入用一個 Xin R^{m imes n} 的矩陣表示，則可用矩陣的Frobenius norm來表示d的優化問題

d^* = argmin_d sum_i ||X-Xdd^T||_F^2 ，其中 d^Td=1

利用矩陣的Frobenius norm與跡的關係 ||A||_F = sqrt{Tr(AA^T)} ，代入並簡化式子有

d^* = argmin_d -2Tr(X^TXdd^T) + Tr(X^TXdd^Tdd^T)

並且由於 d^Td=1 ，可以進一步簡化為

d^* = argmin_d -Tr(X^TXdd^T) = argmax_dTr(d^TX^TXd)

通過上式可以看出，這個極值問題可以用 X^TX 的本徵分解來解決，即 X^TX 的最大的本徵值對應的本徵矢量為d的最優解，這是對 l=1 的情況，用本徵分解得到的first principle component。推廣到 l>1 的情況，則D的最優解為 X^TX 的 最大的l 個本徵值對應的本徵矢量組成的矩陣。

從表徵空間角度理解PCA

除了將PCA看做是一種壓縮數據的方法，我們還可以將其看做是一種學習數據表徵方式的無監督學習演算法。我們可以將PCA看做是從高維空間到低維空間的映射，並且在低維空間中的元素間是線性無關的。

對於原數據的矩陣 Xin R^{m imes n} ，為方便討論，我們可以假設 E[x]=0 ，因為我們總是可以預處理我們的數據並減掉一個線性項使期為零。則無偏的協方差可表示為

Var[x] = frac{1}{m-1}X^TX

而PCA就是要找到一個通過線性變換的方式 z=W^Tx ，使得 Var[z] 是對角的，從而使在新的表徵空間的元素間是無關的。

前面我們利用 X^TX 的本徵分解來解決PCA問題，即 X^TX = WLambda W^T 。這裡，我們也可以用另一種方法，即對X的奇異值分解（關於本徵分解和奇異值分解的區別，可回顧線性代數——深度學習花書第二章）來表示PCA問題。

令 X=USigma W^T ，其中 U,W 為正交矩陣， Sigma 為對焦矩陣，則 X^TX=(USigma W^T)^TUSigma W^T=WSigma ^2 W^T

Var[x]=frac{1}{m-1}WSigma ^2 W^T

而 Var(z)=frac{1}{m-1}Z^TZ = frac{1}{m-1}W^TX^TXW = frac{1}{m-1}W^TWSigma ^2 W^TW=frac{1}{m-1}Sigma ^2

可以看出經過PCA轉換後，協方差只有對角上才有值，所以z的元素間是線性無關的，相當於對原空間做了一個旋轉（通過矩陣W)，使得方差大的方向落在新空間的各個主軸上，如下圖所示，在原空間中，方差最大的方向並不是在軸線上，經過PCA的線性轉換後，在新空間 z=W^Tx 中方差最大的方向沿著 z_1 軸方向，而次大的沿著 z_2 軸方向。

至此，花書第五章機器學習基礎基本總結完畢，後面還有關於隨機梯度下降(Stochastic Gradient Descent)的討論，準備在第八章深度神經網路的優化方法中再總結。


推薦閱讀：
相关文章