Unsupervised Learning: Linear Dimension Reduction
===
###### tags: `李宏毅`

## 教材
* [PCA(Principle Component Analysis): pdf](https://drive.google.com/file/d/1pbUw336LVEKy4LimTY17cshwlMkwq6O5/view?usp=sharing)
* [youtube](https://www.youtube.com/watch?v=iwh5o_M4BNU&ab_channel=Hung-yiLee)

## Unsupervised Learning
可以分為 Cluster & Dimension Reduction 與 Generation 兩大類。舉例來說，前者是把樹的圖片當輸入，輸出簡單的樹；後者則是輸入簡單的資訊，要輸出不同的樹的圖片。


## Cluster
### K-means
K-means 的意思是要把一個大 Cluster X 分成 K 個小 Clusters。作法就是初始化暪個 Cluster 的 Center，然後分群的作法就是算個個 Data 離哪個 Center 最近就是屬於哪個 Cluster。

更新 Center 的方法也很簡單，就是所有資料點的輸出取平均，圖中最下面的例子是 Linear Clustering。


### Hierarchical Agglomerative CLustering(HAC)
另一種方法是每次都把向量距離最近的兩個資料點合成一個 Cluster，所以合成到最後就會剩下一個 Cluster，也就是 Root，最後選一個 Threshold，挑選要分成幾個 Cluster。

這個方法的好處在於它不像 K-means 要明確知道要幾個 Cluster，而是可以根據條件判斷選出 Cluster 的數量。


## Dimension Reduction
有時輸入的維度很大，但是其實訓練需要的維度沒這麼大時，可以做 Dimension Reduction，取出較少卻仍然有效的資訊。

其中最直觀的方法是 Feature Selection，把不需要的 Feature 挑掉，剩下的就是需要的 Feature。不過這個方法可能不適用在很多地方，因為會有 Feature 之間可能互相影響，但是卻還是能取出更低維度的情況。

另一種方法是 Principle Component Analysis(PCA)，就是把 Feature 們乘以一個矩陣 W，其中 W 的輸入維度大，輸出維度小。


## Principle Component Analysis(PCA)
### 數學推導
PCA 的目的是要找出一個 W，讓資料點投影後仍然可以保有資訊量。

下圖以二維的方式表示，根據資料點的分布，W 應該會是往右上的方向。寫成算式就是最大化輸出 z 的標準差。


如果要取多維的 W，那就分別取一維的 $w^1,w^2,...$，其中 w 之間互相垂直，也就是內積為 0。


找 w 的推導如下，最後是要最大化 $(w^1)^TCov(x)w^1=(w^1)^TSw^1$，不過有些限制，也就是 $||w^1||_2=(w^1)^Tw^1=1$。


結論是 $w^1$ 會是 Covariance Matrix S 的最大的 Eigenvalue $λ_1$ 的 Eigenvector。


$w^2$ 則是 Covariance Matrix S 的最大的 Eigenvalue $λ_2$ 的 Eigenvector。


z 的 Covariance Cov(z) 會是 Diagonal Matrix，推導如下。


### 概念解釋
舉例來說，辨識數字只需要知道其中幾個元素就可以了，而每個元素都當作一個向量，它們可以組成輸出 x。即 $x≈c_1u^1+c_2u^2+...+c_Ku^K+\bar{x}$。


因此目標就會是要最小化 Error $min\sum||(x-\bar{x})-(\sum_{k=1}^Kc_ku^k)||_2$。


把目標式轉成形式 $X≈U\sum_{}V$，其中 U 就跟數學推導的一樣會是 Cov(X) 的前 K 大的 EigenValues 的 Eigenvectors。得到的結果則是 $\sum_{}V$。


### PCA + Neural Network
已知 $\hat{x}=\sum_{k=1}^Kc_kw^k$，然後要最小化 $c^k=(x-\bar{x})w^k$。所以就可以用 Gradient Descent 的方式訓練參數，Error 就是 $x-\bar{x}$。不過在 Linear 的情況下用數學算還是最好，但是用 Neural Network 的方式不只可以用在多維，還可以 Deep，這就是 Autoencoder。


### Weakness of PCA
因為是 Unsipervised， PCA 做出來的結果只考慮讓 Variance 最大的那個 Dimension，不會去考慮資料點的類別，導致下圖藍橘兩個 Class 被 Merge 在一起，結果分別不出來。除非使用 LDA。

另外這是 Linear 的，所以在下圖右邊無法把那 S 型拉直，PCA 只能把它打扁。除非使用 Non-linear Dimension Reduction。


## Matrix Factorization
舉例來說，宅宅和動畫角色之間是有 Common Factors 的。

例如天然呆的宅宅喜歡天然呆的角色。

不過沒有辦法知道這些 Common Factors 是什麼。

所以假設 Common Factor 是二維的，那就可以用 PCA 去降維所有特徵變成二維。


不過有些特徵可能是不知道的，所以那些先略過。使用有的特徵，最小化 Loss。


最後用取得的參數預測未知的特徵。這常被用在推薦系統，e.g. Netflix。