iT邦幫忙

2021 iThome 鐵人賽

DAY 25
0
AI & Data

30天搞懂機器學習是否搞錯了什麼系列 第 25

【Day 25】半監督式學習(Semi-supervised Learning)(下)

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

Smoothness Assumption

  • 近朱者赤,近墨者黑。

它的假設是,https://chart.googleapis.com/chart?cht=tx&chl=x 的分佈是不平均的,在某些地方很集中,某些地方很分散,如果今天 https://chart.googleapis.com/chart?cht=tx&chl=x%5E1%2C%20x%5E2 他們在一個high density的region很接近的話,那它們的label https://chart.googleapis.com/chart?cht=tx&chl=%5Chat%20y%5E1%2C%20%5Chat%20y%5E2才會是相同的,也就是說它們可以用high density的path做connection。

舉例來說,下圖是我們data的分佈,假設我們有三筆data https://chart.googleapis.com/chart?cht=tx&chl=x%5E1%2C%20x%5E2%2C%20x%5E3,而Smoothness Assumption的假設是相似要透過一個high density的region,也就是說,https://chart.googleapis.com/chart?cht=tx&chl=x%5E1%2C%20x%5E2 相連的地方是通過一個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之間的相似度,設定 https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%203,就代表每一個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。

而我們可以把 https://chart.googleapis.com/chart?cht=tx&chl=y 串成一個vector,裡面包含labeled data也包含unlabeled data,然後我們就可以把原本的式子寫成 https://chart.googleapis.com/chart?cht=tx&chl=%5Cbf%20y%5ET%20Ly,這個 https://chart.googleapis.com/chart?cht=tx&chl=L 我們稱之為Graph Laplacian,它可以寫成兩個matrix相減,其中 https://chart.googleapis.com/chart?cht=tx&chl=W 代表每一個data point兩兩之間的weight的connection的關係,而 https://chart.googleapis.com/chart?cht=tx&chl=D 是把 https://chart.googleapis.com/chart?cht=tx&chl=W 的每一個row合起來。

現在我們知道可以用 https://chart.googleapis.com/chart?cht=tx&chl=%5Cbf%20y%5ET%20Ly 來評估我們的label有多smooth,當你要把graph的information考慮到neural network的訓練的時候,你就只要在原本的Loss加一項smoothness的值乘上一個可調的參數 https://chart.googleapis.com/chart?cht=tx&chl=%5Clambda,而這一項就像是一個Regularization term。當然算smoothness不一定是要在output的地方,如果今天是一個deep neural network,你可以在network的任何地方算smoothness。


參考資料

李宏毅老師 - ML Lecture 12


上一篇
【Day 24】半監督式學習(Semi-supervised Learning)(上)
下一篇
【Day 26】遷移學習(Transfer Learning)(上)
系列文
30天搞懂機器學習是否搞錯了什麼30

尚未有邦友留言

立即登入留言