# 李宏毅_ML_Lecture_13
###### tags: `Hung-yi Lee` `NTU` `Machine Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
## ML Lecture 13: Unsupervised Learning - Linear Methods
[課程連結](https://www.youtube.com/watch?v=iwh5o_M4BNU&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49&index=22)
### Unsupervised Learning

Hung-yi Lee將非監督式學習分成兩類：
1. Clustering&Dimension Reduction
1. 化繁為簡
2. 將相關性的資料抽象化
2. Generation
1. 無中生有
2. 給定一個數值，經過function之後產生資料

### Clustering

直觀來看Cluster，就是將相聚一起的資料設置Group，它們就屬於同一個標記。至於需要多少Cluster就非常需要經驗來設置，常見作法如下：
1. K-means
1. 初始化K個中心點
2. 從資料集中隨機標記
3. 反覆計算更新
1. 決定現在的資料屬於K個Cluster中的那一個
2. 更新Cluster
1. 將屬第i個Cluster的資料取出平均，得到新的中心點
2. Hierarchical Agglomerative Clustering(HAC)
1. Build a tree
2. 兩兩計算相似度，取出最相似的一組，平均生成新的資料向量，直到最後生成root
3. 設置threshold
1. 依所設置threshold產生不同的Cluster

兩者的差異在於K-means要定義K個Cluster，而HAC是依threshold產生不同的Cluster狀態。
### Distributed Representation

單純考量Cluster的時候，所有的資料都必需有一個所屬的Cluster，但單純的一個歸於一個Cluster是比較粗糙的作法，較佳作法是利用向量來表示，每一個維度都代表一個Cluster來表示，這種作法稱為『Distributed representation』，這種作法也可以讓一個高維度的資料降為低維度，這稱為『Dimension Reduction』。
### Dimension Reduction

假設現在的資料在3D空間內的呈現如上圖左所示，但是將資料拋開的時候可以發現，其實利用2D的空間就可以描述這個資料集。
### Dimension Reduction

以MNIST為例，它是一個28x28的矩陣，但有時候我們並不需要這麼大的維度空間來描述資料，以『3』為例，它其實只需要一個維度就可以描述，只要記錄它的角度就可以知道它長什麼樣子。
### Dimension Reduction

實作Dimension Reduction的方式如下：
1. 找一個function，輸入為『x』，輸出為『z』，其中『z』的維度相較於『x』小很多。
2. 特徵選擇
* 但多數情況下你無法單純取一個特徵來表示
3. PCA(主成份分析)
* $z=Wx$
* 可參閱Bitshop, Chapter12
### PCA

現在要將資料縮減至1D空間，並假設$||w^1||_2=1$。

$x$為高維空間中的一個點，$w^1$為高維空間中的一個向量，$z^1$為$x$在$w^1$上的投影，其值為$x, w^1$的內積。

$w^1$的選擇在於將$x$投影為$z^1$的時候，其分佈愈大愈好，因為我們希望保留資料之間的奇異度，因此兩個向量線來看(紅、暗黃)，紅線所投影的分佈較大(Large Variance)。

$Var(z_1)=\sum_{z_1}(z_1-\bar{z_1})^2$
* $\bar{z_1}$: 所有$z_1$的平均
### PCA

如果實務上希望將維度調整為非1D的，作法也是相同，差別在於$w^1 \cdot w^2=0$，這代表兩個向量是垂直的，如果沒有加入這個項目，那兩個向量所找的結果就是相同。
### PCA

此部份不瞭解沒關係，目前較多實作都透過套件直接處理，有個概念即可，主要說明公式推導的過程。

公式的條件是$||w^1||_2=(w^1)^Tw^1=1$

$S=Cov(x)$:Covariance matrix(共變異數矩陣)，對稱(Symmetric)，半正定(positive semidefinite)

$w^1$:$S$的eigenvectory(特徵向量)，對應最大的eigenvalue(特徵值)$\lambda_1$
### PCA - decorrelation

$z=Wx$，其中$z$的Convariance Matrix是屬於Diagonal Matrix(對角矩陣)。

上圖左為原始資料分佈，在執行PCA之後會讓不同維度間的Convariance為0，意思即為計算$z$這維度的Convariance的時候會發現它為Diagonal。

### PCA - Another Poing of View

以手寫數字MNIST(28x28)為例，假設手寫數字是由眾多元件(Basic Component)所組成($u^1, u^2....$)，每一個元件皆為(28x28)向量，將所有的向量加總之後就會得到代表的數字。

* $x \approx c_1u^1+c_2u^2...+c_Ku^K+\bar{x}$
* $x$: 代表某一張照片的pixel
* $\bar{x}$: 所有image的平均

上圖『7』為例，它由$u^1,u^3,u^5$所組成，因此所對應的值為1，其餘為0，因此可以以$c_1,c_2...c_K$來表示一張照片。

在元件遠比Pixel小的情況下，我們就可以利用元件的權重來表示一張照片。
### PCA - Another Poing of View

$x - \bar{x} \approx c_1u^1+c_2u^2...+c_Ku^K=\hat{x}$

目前為止我們並不知道如何去找出K個Vectory來滿足上述條件，因此我們需要找出K個Vectory讓$\hat{x}$與$x - \bar{x}$愈接近愈好，而在稍早所提到PCA:$z=Wx$就剛好可以滿足該數學式。

它們中間的無法以元件來描述的誤差即稱為『Reconstruction error』

從另外的角度來說明，有一個資料集$x$，從內一次取出一筆資料，標記為$x^1...$，每一筆資料皆為一個向量，合併起來為一個矩陣，其Column維度為資料集的數目(上圖左)，而$u,c$皆為矩陣，兩者相乘我們希望最小化與左邊等式的差距_{(最小化Reconstruction errordru)}。

在線性代數裡面，矩陣$X(m\times n)$可以利用SVD來拆解為$U(m\times k),\Sigma(k \times k),V(k\times n)$，其中$k$為Compoent的數目。

拆解之後的$U$即為$u^1,u^2...u^k$的矩陣，而$\Sigma \times v$即資料集的矩陣$c$。

$U$是一組Orthonormal vectors_{(正交常態向量)}，它是$XX^T$的eigenvectory(特徵向量)，它有K個Orthonormal vectors對應K個擁有最大eigenvalue的eigenvectory。

$XX^T$是一個Covariance matrix(共變異數矩陣)，PCA所找出來的W就是Covariance matrix的eigenvectory，而利用SVD解出來的U的每一個Column都是Covariance matrix的eigenvectory，因此U這個解即為PCA所得出來的解。

現在得到一個結論，由PCA所得到的W即是Component U，這經由SVD可以得到，而$c_k$存在資料集內各自資料身上，只需要將$(x-\bar{x})\cdot w^k$，這種性質來自於Orthonormal vectors。

假設K=2，以神經網路來說明，$x-\bar{x}$是一個3維的向量，$(x-\bar{x})\cdot w^1$得到了$c_1$，再將$c_1$乘上$w^1$得到$\hat{x}$，相同的方式計算$c_2$，將最後結果加上得到最後的輸出$\hat{x}$，優化的目標就是讓結果接近$x-\bar{x}$

從上面的結果可以發現到，PCA可以用一層隱藏層的神經網路來表示，並且該隱藏層為線性層，沒有啟動函數，目標是輸入資料之後經過神經網路計算輸出的結果愈接近輸入愈好，這種作法即稱為『Autoencoder』。

需要注意到，利用這種模式所得的結果與直接使用PCA所解的結果是不會相同的，利用PCA所得解是Orthonormal vectors，它是垂直的，它利用神經網路所得的解我們無沒有辦法保證它會是垂直的，而且神經網路所得reconstruction error不會比直接PCA所得還要來的小。

但是使用神經網路的好處就是它可以『deep』，『Deep Autoencoder』

簡報碪誤：不是$c^k$，應該統一為$c_k$
### Weakness of PCA

PCA屬非監督式學習，如果嚐試將資料投影到1D的話，它會嚐試尋找讓資料Variance最大的那條線(紅線)。

缺點就是，如果資料本身是兩個類別，投影到1D的時候會造成兩個不同類別的資料合併在一起，這時候可能需要考慮使用LDA_{屬監督式學習}。

另一個缺點在於PCA是線性函數，對於非線性的資料分佈來說是無法完美的投影，如上圖右為例，一個S型分佈式資料是無法靠PCA來做降維投影，執行之後會如上圖右下般混雜。
### PCA - Pokemon

800隻寶可夢，其特徵數有6個，針對PCA應該設置幾個component需視情況而定，如果想要可視化，那就要降為2D，其它情況常見作法如下。

利用每一個componetns的eigenvalue$\lambda$來計算每個eigenvalued的ratio，此例6個特徵，因此6個$\lambda$的ratio如上。

很明顯的後面兩個$\lambda$佔比已經太小，因此不考慮。
### PCA - Pokemon

執行PCA之後得到四組componetns，各為6維向量，每一隻寶可夢都是這四組componetns計算之後加總而得，判讀如下：
1. PCA1: 每一個維度皆為正值，這代表寶可夢的強度
2. PCA2: Def為正而Speed為負，這代表高防會有低速，兩者成反比
3. PCA3: 特別防禦為正，血量與攻擊為負，這代表用血量與攻擊來換特別防禦
4. PCA4: 用攻防來換取高血量，兩者成反比
### PCA - MNIST

將PCA應用於MNIST手寫辨識，取30個component，所得結果可上圖，部份文字如血輪眼一般不可辨識。(Eigen-digit)
### PCA - Face

應用於人臉，如上圖(Eigen-face)
### What happends to PCA?

PCA內，Linear Conversation內的Weigth可以是任何實數，有正數也有負數，這導致PCA所找到的component不見得是內容物的某一個基礎架構，因此在觀察MNIST的時候才會有血輪眼般的文字產生。

如果希望可以將MNIST有筆劃取的產出的話，那可以利用另一個NMF_{(Non-negative matrix factorization)(非負數矩陣分解)}處理，不同於PCA那SVD分解之後有正負值，NMF會強迫所取得的component的weight皆為正數，皆為正數的好處在於image必須由component來疊加。
### NMF on MNIST

利用NMF所得的component如上圖，可以清楚看到照片所呈現皆為筆劃，清楚可見。
### NMF on Face

應用於人臉的話也不同於PCA，比較多出現的是臉部的特徵
### Matrix Factorization_{(矩陣分解)}

Matrix Factorization主要說明著行為跟行為之間可能有某一種的關聯，以上圖公仔收藏為例，有涼宮春公仔的人就比較有可能會有御坂美琴公仔，而有小野寺的人就比較有可能有小唯的公仔。

這說明著收藏的人跟收收藏的公仔之間有某種相似性來造成這個結果
### Matrix Factorization

如果人與公仔的屬性分為天然呆與傲嬌，各為空間中的一個向量，他們之間一定會接近，在做內積的時候值會很大，但是我們很難直接觀察到收藏人與被收藏公仔背後的屬性。

因此我們手上有的就單純就是收藏人手上有的公仔數目，我們要靠著這個推論出每一個人跟動漫人物背後的屬性向量_{(呆、傲嬌)}

將收藏人手上有的公仔資料設定為Matrix X，它的Row為Otaku的數目M，Column為動漫角色數目N，X內的每一個元素都是來自於兩者之間的向量內積($r^A\cdot r^1 \approx 5...$)，因此我們可以這麼拆解：
1. $r^A,r^B...$為一個Column，維度為MxK
* 簡報誤值為NxK
2. $r^1,r^2...$為一個Row，維度為KxN
3. 兩者相乘得到MxN的Matrix X

K為Laten Factor，這代表我們並不能精確的設置，此例將人單純設置兩種屬性向量是不足的，必須經過一再的測試才能確認。

我們的目標就是最小化誤差_{(兩個屬性向量內積所得與實際購買量的誤差)}，這部份可以利用SVD來求解。
### Matrix Factorization

部份情況下我們所得到的資料可能有缺失，像上表所示就不少資料是未知的，其中一種作法就是利用梯度下降優化的時候不處理未知的資料。

假設Laten Factor=2_(K=2)，因此每個人都會對應到一個2維屬性向量_{如上圖左下表}，每一個角色也會有相對應的2維屬性向量_{如上圖右下表}，紅框所標可以看的出來A、B兩個阿宅對應春日與炮姐相對應屬性都是高的，另外CDE三個阿宅與姐寺、小唯相同。

針對未知的部份利用內積計算就可以得到他們可能會購買該公仔的數量，可以看到C對姐寺的公仔似乎是有機會的，因此就可以推他入火坑。

這種作法就是推薦系統，只要將公仔換成電影，將數量換成分數就可以做電影推薦系統
### More about Matrix Factorization

雖然兩者內積就可以得到預估量，但這可能還少考慮了偏差單元，更精確的寫法應該還要再加入$b_A,b_1...$，換個角色可以想成$b_A$就像是一個阿宅有多少買公仔，$b_1$是這個公仔有多吸引人買，這跟屬性是無關的。

因此成本函數就可以調整如下：
$L=\sum_{(i,j)}(r^i\cdot r^j+b_i+b_j-n_{ij})^2$

最終再利用梯度下降來優化即可，如果有需要也可以加上正規化。
### Matrix Factorization for Topic analysis

將公仔換成文件，將阿宅換成字詞，如此即變為主題分析(Topic analysis)，內容數字為該詞彙在文件內出現次數。

相關論文可參閱簡報上提供論文。
### More Related Approaches Not Introduced