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 演算法流程

我們通過邊來傳播標籤，更大的邊允許標籤更容易通過。定義一個 概率轉移矩陣 :

其中 是從節點 到 的概率。定義一個 標籤矩陣 ，第 行是 的一個指示向量。我們計算節點的"軟"標籤 。 是一個 的矩陣，行可以理解為標籤之間的概率分佈。 的初始化不重要，整個標籤傳播演算法過程如下：

1. 傳播：Propagate
2. 固定已標記數據：Clamp the labeled data
3. 重複步驟1直到 收斂。

在第一步中所有節點將它們的標籤傳向它們的鄰居。第二步非常關鍵：我們想從已標記數據那裡獲得固定持久的標籤源，因此不是讓初始的標籤逐漸減弱消失，而是用 固定它們。有了這個從已標記節點的不變「動力（push）」，類邊界就會繼續推進通過高密度區域並在低密度間隔處停止。如果用這種結構用來做分類任務，那麼這個演算法可以利用未標記數據來學習。

2.3 收斂性

這種演算法最後會收斂到一個簡單的解。令 。由於將 固定為了 ，我們只對 感興趣。我們把P切分為已標記和未標記的子矩陣來表示：

演算法中可以表示為：

即：

其中： 是 的初始值， 。因為 是行規範化的， 是 的子矩陣，因此有：

從而：

因此 收斂到0意味著 。因此初始值 不重要。

顯然有： 是一個固定不動的點。因此我麼的迭代演算法的解是這個不動點，無需迭代的傳播就能直接求得標籤傳播問題的解。

需要注意當 可逆的時候解是有效的。這個條件滿足的話，直觀上圖中的每個連接組件都至少有一個已標記點。

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）

我們的方法是在圖上定義一個連續隨機場。首先定義一個實值函數： 。 可以是負的也可以大於1。直觀上我們認為相似的未標記點具有相似的標籤，從這點考慮可以選擇二次能量函數：

顯然 可以通過常數函數最小化。但對於已經觀測到的點我們設 。通過高斯隨機場我們假設函數 的概率分佈為

是「溫度顛倒」參數，

是配分函數，作用是為了歸一化。

我們感興趣的是推斷問題 或者均值 。

分佈 非常像離散狀態的標準馬爾科夫隨機場。實際上區別就是具有實值關係。但這個關係可以大大簡化推斷問題。因為二次能量函數， 都是多維高斯分佈。這就是為什麼把 稱為高斯隨機場。邊緣分佈 是單變數高斯分佈，具有閉式解。

4.2拉普拉斯運算元（The Graph Laplacian）

現在我們介紹一個重要的量：combinatorial Laplacian 。設 是度矩陣定義請參考這裡其中 是節點 的度。拉普拉斯運算元定義為：

利用拉普拉斯運算元可將能量函數簡寫，可以證明：

高斯隨機場可以寫為：

在一個多維高斯分佈中扮演精度矩陣的角色。如果 是對稱非負的話，就總是半正定的。

4.3調和函數（Harmonic Functions）

不難看出最小化能量函數 是harmonic，也就是說在未標記數據點 上滿足 ，在已標記數據點上等於 。我們用 來代表這個調和函數。

調和性質意味著在每個未標記數據點 的值 是它在圖中的鄰居的平均值：

由於調和函數最大原理（ 如果調和函數不是一個常數，那麼它的最大最小值只能在邊界上），故 是獨一無二的並且滿足 ,注意對 有 .

為了計算調和解，我們把矩陣 分解為四塊：

由 和約束 可得調和解：

最後一項和等式（2.11）一樣，其中 是圖上的傳播矩陣。chapter2裡面的標籤傳播演算法實際上計算的是調和函數。

調和函數最小化能量是（4.2）的眾數，因為（4.2）定義了一個單峯各向同性的高斯分佈，眾數也是均值。

---

Chapter 5 Active Learning

5.1 結合半監督學習和主動學習（Combing Semi-Supervised and Active Learning）

高斯隨機場和調和函數框架允許將半監督啊學習和主動學習結合起來。每次從未標記數據中貪婪選擇點查詢，按照最小化調和能量最小函數的風險為準則。這個風險是貝葉斯分類器泛化誤差的估計，可以通過矩陣的方法計算。基於調和函數 我們定義貝葉斯分類器的真實風險 為：

是貝葉斯決策規則，閾值為0.5，大於0.5為1否則為1. 是未知的真實標籤在結點 的分佈，因此 是可計算的。假設我們可以用高斯隨機場的均值來估計未知分佈 :

直觀上，在圖上一次random walk為1的概率是 ,我們的假設是我們可以近似這個分佈，使用在每個結點使用一個有偏硬幣，正面朝上的概率為 。有了這個假設可以計算估計風險：

如果查詢一個未標記結點 ，就會得到一個結果 。把這個點加入訓練集中重新訓練，高斯隨機場和均值函數也會改變。設新的調和函數為 。估計風險也會變為：

因為我們不知道 的真實標記，我們再一次假設 。查詢過結點 之後的期望估計風險為：

這裡我們使用的選擇防範是最小化期望估計風險的貪婪選擇：

在這個過程中，我們在把 加入到當前已標記訓練集中後需要計算調和函數 。這是一個重複訓練問題並且通常需要密集計算。但對於高斯隨機場和調和函數存在一個有效的方法。已知調和函數的解為：

如果我們固定結點 的值 解會是什麼？這和給定值 計算所有未標記數據條件分佈相同。在高斯場中，未標記數據的條件是多維高斯分佈 。一旦固定 ，條件均值為（參考原論文的附錄A）：

是未標記數據的Laplacian逆矩陣的第k列， 是其第k個對角元素。當計算調和函數 的時候這兩項已經計算過了。

主動學習演算法流程如下圖：

推薦閱讀：

相關文章