Unsupervised Learning: PCA

非監督式學習: 主成分分析(Principal components analysis，PCA)

上篇提到PCA是降維的一種方法，他的input x和output z之間是linear transform，即z=Wx，PCA要做的，就是根據x把W給找出來(z未知)

今日的課程來自於: https://youtu.be/CXgbekl66jc 

---

PCA for 1-D

為了簡化問題，這裡我們假設z是1維的vector，也就是把x投影到一維空間，此時w是一個row vector : z_1=w¹．x ，其中w¹表示w的第一個row vector，假設w¹的長度為1，即||w¹||_2=1，此時z_1就是x在w¹方向上的投影

基本上，就是將二維的x，投影到一維的z，並且符合z_1=w¹．x
那我們要找甚麼樣的w¹呢?

• 我們希望找到一個projection的方向，他可以讓projection後的variance越大越好
• 我們不希望projection使這些data point 通通擠在一起，導致點和點之間的資訊消失
• 其中，variance的計算公式: Var(z_1)=1/N Σ(z_1-mean(z_1))²，||w¹||_2 = 1

---

PCA for n-D

當然不只投影到一維空間，還可以投影到更高維的空間

同樣也滿足，z=Wx。只不過 z = z1、z2、….. ，而W也是，並且W 是一個正交矩陣(orthogonal matrix)

找到的w¹必須讓var(z_1)最大，而w²在不等於w¹的情況下，同樣要使var(z_2)最大

---

Lagrange multiplier

基本上可以使用現有的函數計算，這邊介紹Lagrange multiplier求解PCA的結論

• w¹ 是S=Cov(x)這個matrix的特徵向量，對應最大的特徵值λ_1
• 在算w²時，多了w¹一個條件，就是w¹與w²必須正交，也就是w²也是S=Cov(x)這個matrix的特徵向量，對應最大第二特徵值λ_2

---

PCA-decorrelation

z=W．x
神奇之處在於cov(z)=D，即z的covariance是一個diagonal matrix
PCA可以讓不同dimension之間的covariance變為0，即不同new feature之間是沒有correlation的，這樣做的好處是，減少feature之間的關係從而減少model所需的參數量
如果你把原來的input data通過PCA之後再給其他model使用，那這些model就可以使用簡單的形式，而無需考慮不同dimension之間類似這些交叉項，此時model得到簡化，參數量大大降低，相同的data量可以得到更好的訓練結果，從而可以避免overfitting的發生

---

Reconstruction Component

假設我們現在考慮是手寫數字識別，這些數字是由一些類似於筆畫的basic component 組成，就是把每個筆畫寫成vector，記成u_1\u_2 … ，以MNIST為例，不同的筆畫都是一個28*28的vector，把某些vector加起來，就組成一個28*28的digit

可以寫成 x≈c_1 * u¹ + c_2 * u²+c_3 * u³+ ….. +x̄

x代表某張digit image的pixel，他等於k個component 的加權和加上所有image的平均值(x̄)

以上圖為例，7就是 x=u¹+u³+u⁵ ，我們可以用[c_1,c_2,c_3,c_4,c_5]^T 來表示一張digit image，如果component的數目k 遠比pixel的數目小，那這個描述是有效的

實際上我們不知道 u¹ ~ u^k 的具體值，因此我們要找到這樣 k個vector，使得 x-x̄ 與 x ^( x 的預估值) 越接近越好

而且用未知component來描述的這部分內容，叫做Reconstruction error ，即|| (x-x̄) – x^ || ，接下來我們去找 k個 vector 去minimize這個error:

回顧 PCA ，z=W．x ，實際上我們通過PCA最終解得到的{w¹,w²,…. w^k }就使reconstruction error 最小化的{u¹,u²,… u^k }

---

NN for PCA

現在我們已經知道，PCA找出的{w¹,w²,…. w^k }就是k個component{u¹,u²,… u^k }，並且{w¹,w²,…. w^k }這k個vector是標準正交化的(orthonormal)，因此:

這時候我們可以使用神經網路(NN)來表示整個過程，假設x是三維向量，要投影到k=2維的component上:

• x-x̄與w^k做inner product的過程類似於neural network，x-x̄在3維空間上的座標就相當於是neuron 的input ，而w¹,w²,w³就是weight，而c_1是neuron的output

• 得到c_1之後，再乘上w¹，得到 x^的一部分

• 對c_2進行同樣的操作，乘上w²，貢獻x^的剩餘部分，此時我們已經完整計算出x^三個分量的值

• 此時，PCA就被表示成了只含一層hidden layer的神經網絡，且這個hidden layer是線性的激活函數，訓練目標是讓這個NN的input x-x̄ 與output x^ 越接近越好，這件事就叫做Autoencoder
• 注意，通過PCA求解出的與直接對上述的神經網絡做梯度下降所解得的是會不一樣的，因為PCA解出的是相互垂直的(orgonormal)，而用NN的方式得到的解無法保證相互垂直，NN無法做到Reconstruction error比PCA小，因此：在linear 的情況下，直接用PCA找W遠比用神經網路的方式還快速。NN的好處是他不只一層，可以做deep autoencoder

---

Weakness of PCA

PCA有很明顯的弱點：

• 它是unsupervised的，如果我們要將下圖綠色的點投影到一維空間上，PCA給出的從左上到右下的劃分很有可能使原本屬於藍色和橙色的兩個class的點被merge在一起
  而LDA則是考慮了labeled data之後進行降維的一種方式，但屬於supervised
• 它是linear的，對於下圖中的彩色曲面，我們期望把它平鋪拉直進行降維，但這是一個non-linear的投影轉換，PCA無法做到這件事情，PCA只能做到把這個曲面打扁壓在平面上，類似下圖，而無法把它拉開

對類似曲面空間的降維投影，需要用到non-linear transformation

---

PCA for MNIST

再次回到手寫數字識別的問題上來，這個時候我們就可以熟練地把一張數字圖像用多個組件(維度)表示出來了：

這裡的w^i 就表示降維後的其中一個維度，同時也是一個組件，它是由原先28×28維進行加權求和的結果，因此w^i也是一張28×28的圖像，下圖列出了通過PCA得到的前30個組件的形狀：
注：PCA就是求的前30個最大的特徵值對應的特徵向量

---

PCA for Face

同理，通過PCA找出人臉的前30個組件(維度)，如下圖所示：
用這些臉的組件做線性組合就可以得到所有的臉

在對MNIST和Face的PCA結果展示的時候，你可能會注意到我們找到的組件好像並不算是組件，比如MNIST找到的幾乎是完整的數字雛形，而Face找到的也幾乎是完整的人臉雛形，但我們預期的組件不應該是類似於橫折撇捺，眼睛鼻子眉毛這些嗎？
如果你仔細思考了PCA的特性，就會發現得到這個結果是可能的注意到linear combination的weight 可以是正的也可以是負的，因此我們可以通過把組件進行相加或相減來獲得目標圖像，這會導致你找出來的component不是基礎的組件，但是通過這些組件的加加減減肯定可以獲得基礎的組件元素

---

NMF

Introduction

如果你要一開始就得到類似筆劃這樣的基礎組件，就要使用NMF(non-negative matrix factorization)，非負矩陣分解的方法
PCA可以看成對原始矩陣做SVD進行矩陣分解，但並不保證分解後矩陣的正負，實際上當進行圖像處理時，如果部分組件的matrix包含一些負值的話，如何處理負的像素值也會成為一個問題(可以做歸一化處理，但比較麻煩)
而NMF的基本精神是，強迫使所有組件和它的加權值都必須是正的，也就是說所有圖像都必須由組件

在MNIST數據集上，通過NMF找到的前30個組件如下圖所示，可以發現這些組件都是由基礎的筆劃構成，如果應用在臉部辨別的話也是