昨天提到了Generative Model以及Low-density Separation，今天就要繼續介紹其他半監督式學習的方式。

Smoothness Assumption

• 近朱者赤，近墨者黑。

它的假設是， 的分佈是不平均的，在某些地方很集中，某些地方很分散，如果今天 他們在一個high density的region很接近的話，那它們的label 才會是相同的，也就是說它們可以用high density的path做connection。

舉例來說，下圖是我們data的分佈，假設我們有三筆data ，而Smoothness Assumption的假設是相似要透過一個high density的region，也就是說， 相連的地方是通過一個high density path相連的。

假設只看下圖的這幾筆資料，單看它們的pixel相似度可能2跟3是比較像的。

但是如果今天看了所有的data，就會發現這兩個2中間有很多連續的變化、很多過渡的型態，也就是說它們中間有很多不直接相連的相似，所以根據Smoothness Assumption你就可以發現兩個2是屬於同一個class，而2跟3是屬於不同的class。

Cluster and then Label

Cluster and then Label是實作Smoothness Assumption最簡單的方法，下圖中橘色是class 1，綠色是class 2，藍色是unlabeled data，接下來就把這些data做clustering，可能就可以分成3個cluster，然後你會發現cluster 1的橘色class 1的label data最多，所以cluster 1裡面的data都算是class 1，而cluster 2, 3都算是class 2。

Graph-based Approach

另一個方法是引入Graph structure，用Graph structure來表達connected by high density path，也就是說，我們把所有的data point建成一個graph，而你要想辦法算出它們之間的singularity並把它們之間的edge建出來。有了這個graph之後，如果今天有兩個點，它們在這個graph上面是相連的，他們就是同一個class。

要如何建一個graph？有些時候這個graph的representation是很自然就可以得到的，舉例來說，你現在要做一個網頁的分類，然後你有紀錄網頁和網頁之間的hyperlink，那hyperlink就會告訴你這些網頁是怎麼連結的。或是論文的分類，論文和論文之間有引用的關係，這些引用也可以是另外一種graph的edge。但有時候你還是要自己想辦法建一個graph。

Graph-based Approach - Graph Construction

要如何建一個graph？首先你要先定義如何計算兩個object之間的相似度，舉例來說，影像base on pixel算相似度可能表現不太好，可能base on autoencoder抽出來的feature算相似度可能表現會比較好等等。

接著就可以建graph。

• K Nearest Neighbor
  • 假設有一堆data，我都可以算出data跟data之間的相似度，設定 ，就代表每一個point都跟它最接近、最相似的3個點相連。
• e-Neighborhood
  • 每一個點只有跟它相似度超過某一個threshold，跟它相似度大於e的點才不會被圈在一起。

而edge也不是只有相連跟不相連兩種選擇而已，也可以給edge權重，讓你的edge跟要被連接起來的兩個data point之間的相似度成正比，這邊建議用RBF function來定義相似度，式子如下圖所示，其中取exponential可以讓表現比較好，因為有取exponential讓整個function下降速度很快，所以只有當兩個點非常相近的時候，它的singularity才會大，只要距離稍微遠一點，singularity就會下降的很快，變得很小。

所以Graph-based的方法，它的精神是，假設我在這個graph上面有一些labeled data，那跟它們有相連的，它們是class 1的機率也會上升，所以每一筆data會影響它的鄰居，而它的鄰居還會繼續影響它的鄰居，也就是說它會通過graph的link傳遞過去。

剛剛都是定性的說怎麼使用這個graph，接下來我要說明的是怎麼定量的使用這個graph。它是在graph的structure上面定一個label的smoothness，也就是會定義這個label有多符合我們剛剛提到的Smoothness Assumption的假設。

如果我們看下圖的兩個例子，其中data point和data point之間的數字代表edge的weight，假設我們給每一個data不同的label，左邊的給{1,1,1,0}，右邊的給{0,1,1,0}，很明顯的會覺得左邊比較smooth，但是我們要用一個數字來定量的描述它有多smooth，所以我們就可以使用下圖的公式，計算出來的值越小，代表越smooth。

而我們可以把 串成一個vector，裡面包含labeled data也包含unlabeled data，然後我們就可以把原本的式子寫成 ，這個 我們稱之為Graph Laplacian，它可以寫成兩個matrix相減，其中 代表每一個data point兩兩之間的weight的connection的關係，而 是把 的每一個row合起來。

現在我們知道可以用 來評估我們的label有多smooth，當你要把graph的information考慮到neural network的訓練的時候，你就只要在原本的Loss加一項smoothness的值乘上一個可調的參數 ，而這一項就像是一個Regularization term。當然算smoothness不一定是要在output的地方，如果今天是一個deep neural network，你可以在network的任何地方算smoothness。

參考資料

李宏毅老師 - ML Lecture 12