Semi-supervised Learning (半監督式學習)

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

所謂的半監督式學習，就是我們有部分的資料是沒有label的，這也接近我們實務上操作的資料
通常遇到的情況，是沒有label的資料遠大於有label的資料。(我們從不缺data，缺的是有label的data，就像可以拍很多照片，但他們是沒有標籤的)

Semi-supervised Learning 可以分成兩種情況:

• Transductive Learning: unlabeled data is the testing data 
  使用testing data 的 feature，但是不使用testing data的label
• Inductive Learning: unlabeled data is not the testing data
  就是完全不考慮testing data

要選擇使用哪一種方法，取決於是否已經有testing set

Semi-supervised Learning 的使用unable data往往伴隨著假設，而假設的合理與否，決定了結果的好壞程度

---

Outline

1. Semi-supervised Learning for Generative Model
2. Low-density Separation Assumption
3. Smoothness Assumption
4. Better Representation

---

Semi-supervised Learning for Generative Model

在監督學習中，我們討論過機率生成模型了，所以可以算出class 1 & class 2 的分佈分別為何，再根據貝氏公式得到新的x 的類別。不過在半監督學習中，unlabeled data會影響最終的決定，劃分兩個class的decision boundary也會隨之變化，(會影響posterior probability，也會影響decision boundary)

因此，在計算上就會有些調整(x^u為unlabeled data)

• 先初始化一組參數: θ = {P(C1),P(C2),u¹,u², ∑}
• Step 1: 利用初始model計算每一筆unlabeled data x^u 屬於 class 1 的機率Pθ(C1|x^u)
• Step 2: update model 
  因為考慮unlabeled data，分子還要加上所有unlabeled data屬於class 1 機率和

• 平均數則要增加機率對於x^u求和在歸一化的結果即可

• 剩下的參數同理，接下來就有一組新的參數θ’，於是就回到step 1 →step 2→step1
• 理論上這個方法是可以收斂的，並且一開始的θ會影響收斂的結果，類似於gradient descent
• 上述的step1 就是EM algorithm裡的E ，step2 為M

以上的推導基於的基本思想是，把未標記的數據看成是可以劃分的，一部分屬於C1，一部分屬於C2
也就是C1的先驗概率乘上C1這個class產生的概率+C2的先驗機率乘上C2這個類別產生的機率
實際上我們在利用極大似然函數更新參數的時候，就利用了該分段的結果：

---

Low-density separation Assumption

接下來介紹一種新的方法，它基於的假設是Low-density separation
通俗來講，就是這個世界是非黑即白的，在兩個class的交界處data的密度(density)是很低的，它們之間會有一道明顯的鴻溝，此時unlabeled data(下圖綠色的點)就是幫助你在原本正確的基礎上挑一條更好的boundary

Self Training

low-density separation最具代表性也最簡單的方法是self training

• 先從labeled data去訓練一個model f*，訓練方式沒有限制
• 然後用f*該去對unlabeled data打上label， ，也叫作pseudo label
• 從unlabeled data中拿出一些data加到labeled data裡，至於data的選取需要你自己設計算法來挑選
• 回頭再去訓練，循環即可

注：該方法對Regression是不適用的

實際上，該方法與之前提到的generative model還是挺像的，區別在於：

• Self Training使用的是hard label：假設一筆data強制屬於某個class
• Generative Model使用的是soft label：假設一筆data可以按照概率劃分，不同部分屬於不同class

可以看到，在neural network裡使用soft label是沒有用的，因為把原始的model裡的某個點丟回去重新訓練，得到的依舊是同一組參數，實際上low density separation就是通過強制分類來提升分類效果的方法

Entropy-based Regularization

該方法是low-density separation的進階版，你可能會覺得hard label這種直接強制性打標籤的方式有些太武斷了，而entropy-based regularization則做了相應的改進： y^u=f*_θ*(x^u)，其中y^u是一個概率分布(distribution)

由於我們不知道unlabeled data 的label到底是什麼，但如果通過entropy-based regularization得到的分佈集中在某個class上的話，那這個model就是好的，而如果分佈是比較分散的，那這個model就是不好的，如下圖所示：

接下來的問題是，如何用數值的方法來evaluate distribution的集中(好壞)與否，要用到的方法叫entropy，一個distribution的entropy可以告訴你它的集中程度：

對上圖中的第1、2種情況，算出的E(y^u)=0，而第3種情況，算出的E(y^u)=ln(5)，可見entropy越大，distribution就越分散，entropy越小，distribution就越集中
因此我們的目標是在labeled data上分類要正確，在unlabeled data上，output的entropy要越小越好，此時就要修改loss function

• 對labeled data來說，它的output要跟正確的label越接近越好，用cross entropy表示如下：

• 對unlabeled data來說，要使得該distribution(也就是output)的entropy越小越好：

• 兩項綜合起來，可以用weight來加權，以決定哪個部分更為重要一些

可以發現該式長得很像regularization，這也就是entropy regularization的名稱由來

semi-supervised SVM

SVM要做的是，給你兩個class的data，去找一個boundary：

• 要有最大的margin，讓這兩個class分的越開越好
• 要有最小的分類錯誤

對unlabeled data窮舉所有可能的label，下圖中列舉了三種可能的情況；然後對每一種可能的結果都去算SVM，再找出可以讓margin最大，同時又minimize error的那種情況，下圖中是用黑色方框標註的情況

當然這麼做會存在一個問題，對於n筆unlabeled data，意味著即使在二元分類裡也有種可能的情況，數據量大的時候，幾乎難以窮舉完畢，上面給出的paper提出了一種approximate的方法，基本精神是：一開始你先得到一些label，然後每次改一筆unlabeled data的label，看看可不可以讓你的objective function變大，如果變大就去改變該label。

---

Smoothness Assumption

concepts

smoothness assumption的基本精神就是將兩個點可以在樣本高密度集中分布的區域有一條可連結的路徑，即connected by a high density path

精準的定義是:

• x的分布是不均勻的(有些地方集中，有些又分散)
• 如果x¹ 和 x² 在一個high density region 上很接近的話，那麼 ŷ¹ 和 ŷ² 就是相同的

假設下圖是data的分布，x¹, x², x³ 是其中的三筆data，如果單純的看x的相似度，顯然x²和 x³ 的距離比較近一些，但對於smoothness assumption 來說，x¹ 和 x² 是處於同一個區域的，他們之間有一條相連的路徑

digits detection

以手寫數字識別為例，對於最右側的2和3以及最左側的2，顯然最右側的2和3在pixel上相似度更高一些；但如果把所有連續變化的2都放進來，就會產生一種“不直接相連的相似”，根據Smoothness Assumption的理論，由於2之間有連續過渡的形態，因此第一個2和最後一個2是比較像的，而最右側2
和3之間由於沒有過渡的data，因此它們是比較不像的

人臉的過渡數據也同理

file classification

Smoothness Assumption在文件分類上是非常有用的

假設對天文學(astronomy)和旅行(travel)的文章進行分類，它們各自有專屬的詞彙，此時如果 unlabeled data與label data的詞彙是相同或重合(overlap)的，那麼就很容易分類；但在真實的情況下，unlabeled data和labeled data之間可能沒有任何重複的words，因為世界上的詞彙太多了，
sparse的分佈很難會使overlap發生

但如果unlabeled data足夠多，就會以一種相似傳遞的形式，建立起文檔之間相似的橋樑

Graph-based Approach

之前講的是比較直覺的做法，接下來引入Graph Structure來表達connected by a high density path這件事

我們把所有的data points都建成一個graph，有時候建立vertex之間的關係是比較容易的，比如網頁之間的鏈接關係、論文之間的引用關係；但有時候需要你自己去尋找vertex之間的關係

graph的好壞，對結果起著至關重要的影響，而如何build graph卻是一件heuristic的事情，需要憑著經驗和直覺來做

• 首先定義兩個object 之間的相似度 s(x^i, x^j)
  如果是基於pixel的相似度，performance可能會不太好；建議使用autoencoder提取出來的feature來計算相似度，得到的performance會好一些
• 算完相似度後，就可以建graph了，方式有很多種：
  k nearest neighbor：假設k=3，則每個point與相似度最接近的3個點相連
  e-neighborhood：每個point與相似度超過某個特定threshold e的點相連
• 除此之外，還可以給Edge特定的weight，讓它與相似度s(x^i, x^j)成正比
  1. 建議用RBM function來確定相似度，這裡均為vector，計算它們的Euclidean Distance(歐幾里得距離)，加上參數後再去exponential
  2. 至於加exponential，經驗上來說通常是可以幫助提升performance的，在這裡只有當x^i, x^j非常接近的時候，singularity才會大；只要距離稍微遠一點，singularity就會下降得很快，變得很小
  3. 使用exponential的RBM function可以做到只有非常近的兩個點才能相連，稍微遠一點就無法相連的效果，避免了下圖中跨區域相連的情況

graph-based approach的基本精神是，在graph上已經有一些labeled data，那麼跟它們相連的point，屬於同一類的概率就會上升，每一筆data都會去影響它的鄰居，而graph帶來的最重要的好處是，這個影響是會隨著edges傳遞出去的，即使有些點並沒有真的跟labeled data相連，也可以被傳遞到相應的屬性

比如下圖中，如果graph建的足夠好，那麼兩個被分別label為藍色和紅色的點就可以傳遞完兩張完整的圖；從中我們也可以看出，如果想要讓這種方法生效，收集到的data一定要足夠多，否則可能傳遞到一半，graph就斷掉了，information的傳遞就失效了

介紹完瞭如何定性使用graph，接下來介紹一下如何定量使用graph

定量的使用方式是定義label的smoothness，下圖中，edge上的數字是weight， x^i 表達data， y^i 表示data的label，計算smoothness的方式為：

我們期望smooth的值越小越好

當然上面的式子還可以化簡，如果把labeled data和unlabeled data的y組成一個(R+U)-dim vector，即 y=[… y^i … y^j]^T

於是smooth可以改寫為：

其中L為(R+U)×(R+U) matrix，成為Graph Laplacian， 定義為L=D-W

• W：把data point兩兩之間weight的關係建成matrix，代表了x^i與x^j之間的weight值
• D：把W的每一個row上的值加起來放在該行對應的diagonal上即可，比如5=2+3,3=2+1,…

對S=y^TLy 來說，y是label，是neural network的output，取決於neural network的parameters，因此要在原來僅針對labeled data的loss function中加上這一項，得到：

λS實際上也是一個 regularization term
訓練目標：

• labeled data的cross entropy越小越好(neural network的output跟真正的label越接近越好)
• smooth S越小越好(neural network的output，不管是labeled還是unlabeled，都要符合Smoothness Assumption的假設)

具體訓練的時候，不一定只局限於neural network的output要smooth，可以對中間任意一個hidden layer加上smooth的限制

---

Better Representation

Better Representation的精神是，去蕪存菁，化繁為簡

我們觀察到的世界是比較複雜的，而在它的背後其實是有一些比較簡單的東西，在操控著這個複雜的世界，所以只要你能夠看透這個世界的假象，直指它的核心的話，就可以讓training變得比較容易

舉一個例子，在神鵰俠侶中，楊過要在三招之內剪掉樊一翁的鬍子，雖然鬍子的變化是比較複雜的，但頭的變化是有限的，楊過看透了這一件事情就可以把鬍子剪掉。在這個例子中，樊一翁的鬍子就是original representation，而他的頭就是你要找的better representation

算法具體思路和內容到unsupervised learning的時候再介紹