基於圖的半監督學習
chapter 2是標籤傳播演算法,然後通過高斯隨機場和調和函數來再次闡釋標籤傳播。標籤傳播的解釋有很多角度,比如隨機行走(random walk)、電壓電流網路(Electric Networks)、也可以是圖的最小割的soft version。其中作者的Combining Active Learning and Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions論文獲得了ICML10年經典論文獎。
Chapter 2:標籤傳播 Label Propagation
我們把問題看成在圖上標籤傳播的形式,根據節點的相近性一個節點的標籤傳播到它的鄰居節點。在這個過程中我們固定已標記數據的標籤。因此已標記數據就像源頭一樣流出通過未標記數據的標籤。
2.1 問題設定
設已標記數據為
直觀上我們希望相近的數據點有相同的標籤。我們創造一個圖,圖中節點代表數據點(包括已標記和未標記)。節點
2.2 演算法流程
我們通過邊來傳播標籤,更大的邊允許標籤更容易通過。定義一個
其中
- 傳播:Propagate
- 固定已標記數據:Clamp the labeled data
- 重複步驟1直到
收斂。
在第一步中所有節點將它們的標籤傳向它們的鄰居。第二步非常關鍵:我們想從已標記數據那裡獲得固定持久的標籤源,因此不是讓初始的標籤逐漸減弱消失,而是用
2.3 收斂性
這種演算法最後會收斂到一個簡單的解。令
演算法中可以表示為:
其中:
從而:
因此
顯然有:
需要注意當
2.4示例
我們在兩個數據集上展現標籤傳播的性質。圖2.1(a)中數據有三個類,每個是橫窄帶狀分佈。數據點為均勻的從帶中採樣而得。開始有三個標記點和178個未標記點。在1NN(1-nearest-neighbor)演算法中,忽略了未標記數據因此得到了2.1(b)結果。標籤傳播演算法得到的結果為2.1(c),標籤沿著橫向帶狀傳播。
圖2.2是三維螺旋結構的數據集,有兩個類。圖中有2個已標記數據點和184個未標記數據點。同樣1NN的結果不如標籤傳播。
Chapter 3 高斯隨機場和調和函數(Gaussian Random Fields and Harmonic Functions)
在這一章我們將基於概率框架的標籤傳播形式化。不失一般性,假定二分類
4.1 高斯隨機場(Gaussian Random Fields)
我們的方法是在圖上定義一個連續隨機場。首先定義一個實值函數:
顯然
我們感興趣的是推斷問題
分佈
4.2拉普拉斯運算元(The Graph Laplacian)
現在我們介紹一個重要的量:combinatorial Laplacian
利用拉普拉斯運算元可將能量函數簡寫,可以證明:
高斯隨機場可以寫為:
4.3調和函數(Harmonic Functions)
不難看出最小化能量函數
調和性質意味著在每個未標記數據點
由於調和函數最大原理( 如果調和函數不是一個常數,那麼它的最大最小值只能在邊界上),故
為了計算調和解,我們把矩陣
由
最後一項和等式(2.11)一樣,其中
調和函數最小化能量是(4.2)的眾數,因為(4.2)定義了一個單峯各向同性的高斯分佈,眾數也是均值。
Chapter 5 Active Learning
5.1 結合半監督學習和主動學習(Combing Semi-Supervised and Active Learning)
高斯隨機場和調和函數框架允許將半監督啊學習和主動學習結合起來。每次從未標記數據中貪婪選擇點查詢,按照最小化調和能量最小函數的風險為準則。這個風險是貝葉斯分類器泛化誤差的估計,可以通過矩陣的方法計算。基於調和函數
直觀上,在圖上一次random walk為1的概率是
如果查詢一個未標記結點
因為我們不知道
這裡我們使用的選擇防範是最小化期望估計風險的貪婪選擇:
在這個過程中,我們在把
如果我們固定結點
主動學習演算法流程如下圖:
推薦閱讀: