# 李宏毅_ML_Lecture_12
###### tags: `Hung-yi Lee` `NTU` `Machine Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
## ML Lecture 12: Semi-supervised
[課程連結](https://www.youtube.com/watch?v=fX_guE7JNnY&index=21&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49)
### Introduction

在監督式學習(Supervised learning)中，會有一個很大的訓練資料集，裡面資料的輸入與輸出，以影像辨識為例，輸入就是照片，輸出就是它的類別。

半監督式學習(Semi-supervised learning)，意指在資料集中有另外一組沒有label的資料($x^U$)_{(U指資料集數量)}，它只有輸入沒有輸出。普遍來說，未標記的資料量會大於標記的資料量。

Semi-supervised learning主要有兩種：
1. Transductive learning:
* 未標記的資料即為你的測試資料集
3. Inductive learning:

Semi-supervised learning的應用主要在於收集資料很簡單，但標記的資料太少了，我們希望可以自動標記資料。
### Why Semi-supervised learning helps?

假設目前要建置一個貓狗分類的模型，但手上有很多未標記(label)的資料。

如果給定各一張貓狗的照片並只考慮該二照片來繪出決策邊界，那可能就是中間一條直線切割，但如果將未標記資料也考慮進來的話_(灰色點)，在未標記的資料也提供訊息的情況下，就會影響到決策邊界，這通常會伴隨著一些假設，因此，Semi-supervised是否有用就取決於你的假設。
### Outline

這個課程你會學到幾件事：
1. 如何使用Semi-supervised來建立模型
2. 兩個常見假設
* Low-density Separation
* Smoothness
3. 更好的表示方式
### Supervised Generative Model

監督式學習的模型建立在有標記的資料，估測各類別的最大似然概率，並假設它們都符合高斯分佈，以此計算後續進入的資料是屬於那一個類別，繪製出決策邊界。
### Semi-supervised Generative Model

在Semi-supervised中，未標記的資料(淡綠色資料點)會影響決定，加入未標記的資料之後，如果依然使用$\mu^1,\mu^2,\Sigma$那很顯然的是不合理的。
### Semi-supervised Generative Model

Generative流程如下：
0. 初始化參數：$P(C_1),P(C_2),\mu^2,\mu^2,\Sigma$
* 亂數產生或利用已有標記的資料估測出初始值
1. 計算未標記資料的posterior probability(後驗機率)
* $P_\theta(C_1|x^u)$
* 依據初始化的參數計算
2. 更新模型
* $P(C_1)=\dfrac{N_1+\sum_{x^u}P(C_1|x^u)}{N}$
* 不考慮未標記資料的話就很單純的$\dfrac{N_1}{N}$
* $\sum_{x^u}P(C_1|x^u)$
* 所有未標記資料它屬於$C_1$的機率總合
* $\mu^1=\dfrac{1}{N_1}\sum_{x^r\in C_1}x^r+\dfrac{1}{\sum_{x^u}P(C_1|x^u)\sum_{x^u}P(C_1|x^u)x^u}$
3. 回到第一步
* 理論上可以成功收斂，但受初始值影響收斂結果。
### Why?

在單純擁有已標記資料時，我們要做的是『最大化似然概率』，但考慮未標記資料的時候，它是兩種類別都有可能，因此以加總方式來處理。

$P_\theta(X^u)=P_\theta(x^u|C_1)P(C_1)+P_\theta(x^u|C_2)P(C_2)$

註：考慮標未記資料的數學式錯誤，正確應為$logL(\theta)=\sum_{x^r}logP_\theta(x^r, \hat{y}^r)+\sum_{x^u}logP_\theta(x^u)$
### Low-density Separation

在不考量未標記資料情況下，可能兩個決策邊界都是完美的，但考量未標記資料情況之後，左邊的決策邊界更符合Low-density。
### Self-training

直觀來看，你的手上會有標記、未標記資料：
1. 先以已標記資料訓練模型$f^*$
2. 將未標記資料丟入該模型分類
3. 從未標記資料取出資料加入已標記資料集中
* 隨機挑選
* 可以針對各別資料給予權重
4. 利用加入的未標記資料重新訓練模型$f^*$

這個作法應用在Regression上的話並沒有效果。
### Self-training

Self-training與Generative的作法雷同，差異在於Self-training的一定要強制標記每筆資料的label(Hard label)，而Generative是根據Posterior Probability來分類(Soft label)。

實作神經網路的時候所採用的，一定是Hard label的方式，這是一種Low-density Separation的概念，它並不是絕對，但是非黑即白的概念下，你有70%像，它就是Class 1。

採用Soft label的作法在神經網路上是無法有作用的，那只是把參數的值再輸出一次。

簡報錯誤：Soft的30%屬Class 2
### Entropy-based Regularization

使用Neural Network的時候，我們會希望輸出的結果是很集中的，如上圖所示。假設有五個類別，資料在某一個類別的結果是非常高機率，那就是一個很好的結果，將結果數值化就是利用Entropy。

$E(y^u)=-\sum^5_{m=1}y^u_mln(y^u_m)$
:::info
對每一個類別的機率乘上log那一個類別的機率
:::

針對上圖最上面兩種狀況計算，所得的Entropy為0，但最下面的每一個機率平均為$\frac{1}{5}$，因此所得的Entropy較大，這代表散佈較大，我們希望它愈小愈好，所以成本函數需要調整。

$L=\sum_{x^r}C(y^r,\hat{y}^r)+\lambda\sum_{x^u}E(y^u)$
:::info
* $L=\sum_{x^r}C(y^r,\hat{y}^r)$，針對已標記資料的計算
* $\lambda\sum_{x^u}E(y^u)$，針對每一筆未標記資料的輸出分佈Entropy
:::
### Outlook: Semi-supervised SVM

SVM主要在資料之間取得一個決策邊界，並且可以讓資料之間分的愈開愈好，在加入未標記資料之後，Semi-supervised SVM會窮舉所有可能的label，並對所有可能的結果都計算，從中取得**margin**最大並且**least error**。
### Smoothness Assumption

它的精神就是當$x$是類似的，那$\hat{y}$就是一樣的，因此稱為近朱者赤，近墨者黑。更進一步說明，$x$的分佈並不平均，而是集中、分散在各地，如果$x^1,x^2$在一個高密度區域(high density region)非常接近的時候，那$\hat{y^1},\hat{y^2}$就會相同。

上圖右為例，如果以第一個假設來看，那$x^2,x^3$應該是相似的，但以更精確的假設來看，$x^1,x^2$是處於一個高密度區域連接處，在Smoothness Assumption的定義精神上，$x^1,x^2$是比較有可能是相同的label。
### Smoothness Assumption

以上圖為例，左二數字為2，右一為3，如果單純以pixel來看也許右2、右3是比較類似的，但將資料展開觀察的話可以發現，也許在左2之間存在著很多2的的不同筆跡，在Smoothness Assumption的假設上，它們的中間是存在著一個高度密區域連接，因為左二會是相近的。
### Smoothness Assumption

在類似的文章分類上，如果未標記類別的文章跟已標記類別的文章有出現重覆的關鍵字，那可能就可以以此分類未標記類別的文章，但實務上未標記的文章與已標記的文章之間沒有出現重覆關鍵字機會很高，因為描述用語太多了。

如果可以收集到更多的資料，如上圖二，那就可以類似的文字來做推估，以此分類。
### Cluster and then Label

上圖顯示純以Cluster來標記資料。
### Graph-based Approach

上圖顯示以Graph來顯示資料之間的high density path
### Graph-based Approach - Graph Construction

建置Graph流程如下：
1. 定義兩者之間的相似度
* 影像如以Pixel做相似度處理效能較不好，如果以AUTOENCODER的話效能較佳。
2. 建立Graph
* K Nearest Neighbor(KNN)
* 定義K個相似點
* e-Neighborhood
* 定義e(相似度)
* **Gaussian Radial Basis Function(rbf)**
* $s(x^i, x^j)=exp(-\gamma||x^i-x^j||^2)$
* 效能較佳

建議以rbf的原因在於幾點如下：
1. 取exp，因此下降速度較快
2. 只有在$x^i, x^j$非常靠近的時候，相似度才會大，只要距離稍遠，相似度就會下降很快。

因此點與點之間，以右下圖橘綠點為例，雖然橘綠點之間是相近的，但它們在rbf計算之下，點跟點之間的距離除非非常的小，否則是不會相連。

簡報錯誤：$d(x^i, x^j)$應為$s(x^i, x^j)$
### Graph-base Approach

Graph-base的基本精神在於，未標記資料與已標記資料相連接的時候，它屬於已標記資料的類別機率是上升的，因此每一筆資料都會影響著鄰居，但不僅僅如此，這種影響就跟傳染病一樣，即使不是直接相鄰的連接，也會因為中間的連接而影響著其它遠親，如右二下圖示範例。

但要注意到的一點是，這種作法必需要確保資料夠大，否則中間如果有斷層的話會無法確實的連結，如右二上圖範例。

### Graph-base Approach

我們需要定義label的smoothness(平滑度)，以上圖範例，左右兩個比較，直觀來看左邊較為smoothness，但我們需要量化它，常見作法如下：
* $S=\dfrac{1}{2}\sum _{i,j}w_{i,j}(y^i,y^j)^2$
* 計算兩兩相連的權重乘上距離平方
* 加總所有的資料，不論有無標記

這方式來計算上圖範例，左邊所得S=0.5，右邊所得S=3，愈小代表愈smoothness也愈好。
### Graph-base Approach

* $S=\dfrac{1}{2}\sum _{i,j}w_{i,j}(y^i,y^j)^2=y^TLy$
* $L=D-W$
* (R+U)x(R+U) matrix
* 此為Graph Laplacian
* $W$為兩兩相連的權重Matrix
* $D$為該資料的相連權重加總
* $y$為已標記與未標記資料串連起來的向量
* (R+U)-dim

瞭解之後我們就可以調整神經網路的成本函數如下：
* $L=\sum_{x^r}C(y^r,\hat{y^r})+\lambda S$

直觀來看，這就跟加入正規化一樣，在$L$的同時也同時優化$S$，而這計算不一定是在輸出的地方，也可以是其它層上的Embedding。