流形正則化：一個從已標記和未標記樣本學習的幾何框架（JMLR2006）

04-05

原題目：Manifold Regularization: A Geometric Framework for Learning from

Labeled and Unlabeled Examples

提示：原文獻有些長（現在（2018.1.16）引用次數已經近2800次了，說明這篇論文還是具有一定的意義的），為便於閱讀，這裡先寫一下文章的第二節和第四節內容，因為第二節提出了半監督學習的基本框架，並且給出了同時利用標記和未標記數據的目標函數，關於理論證明的部分暫且略掉（以後有可能的話再更新），第四節則舉了RLS和SVM的兩個應用來加深理解。還有，這篇文獻是前面介紹的paper里用到的LapSVM所參考的文獻。

由於只介紹了文章的一部分，所以先這裡寫個摘要來介紹一下文章的主旨。

摘要：文章基於一種新形式的正則化提出了一個系列的學習演算法，這種演算法利用了邊緣分布的幾何性質。我們關注這樣一個半監督框架：在一個通用目的學習中同時利用了標記和未標記數據。一些直推圖學習演算法和標準方法包括SVM和RLS（regularized least squares）可以是其中的特殊情況。我們使用再生核希爾伯特空間的性質來證明新的表示理論可以為演算法提供理論基礎。（和純粹基於圖的方法相比）我們可以將樣本向外擴展到新實例上，可以處理直推式和真正的半監督環境這兩種情況。實驗表明我們的半監督演算法可以有效利用未標記數據。最後給出了無監督和全監督在我們的通用框架中的討論。

2半監督學習框架（The Semi-Supervised Learning Framework）

先回顧一下從樣本學習的標準框架。在空間 $X imesmathbb R$ 上有一個概率分布 $P$ ，通過分布 $P$ 生成的樣本來學習函數，已標記數據對 $(x,y)$ 通過 $P$ 產生。未標記樣本 $xin X$ 簡單的從 $P$ 的邊緣分布 $mathcal P_X$ 採樣。

我們可能會希望利用邊緣分布 $mathcal P_X$ 的知識來更好的函數學習（例如在分類或回歸任務中）。當然，如果在 $mathcal P_X$ 和條件分布 $mathcal P(y|x)$ 間沒有可識別的關係的話， $mathcal P_X$ 的知識很可能不會起太多作用。

因此，我們作一個關於邊緣分布和條件分布的假設。假設如果兩個點 $x_1,x_2in X$ 在 $mathcal P_X$ 的內蘊幾何上是接近的，那麼條件分布 $mathcal P(y|x_1)$ 和 $mathcal P(y|x_2)$ 也是相似的。換句話說：條件概率分布 $mathcal P(y|x)$ 沿著 $mathcal P_X$ 內蘊幾何的測地線變化平滑（varies smoothly）。

我們根據這些幾何直覺來拓展建立函數學習的框架。很多演算法比如SVM，嶺回歸（Ridge regression），樣條函數（splines），徑向基函數（Radial Basis Functions）可以看成正則化演算法的廣泛解釋，只不過這些演算法是選擇了一個合適的再生核希爾伯特空間（RKHS），有著不同的經驗代價函數和計算複雜度。

對於一個Mercer核 $K:X imes X ightarrowmathbb R$ 存在一個相應的希爾伯特空間： $X ightarrowmathbb R$ ,範數為 $| |_K$ 。給定已標記數據集 $(x_i,y_i),i=1,...,l$ ，標準的框架通過最小化式（1）來評估一個未知函數：

$f^*=mbox{argmin}_{fin mathcal H_K}frac{1}{l}sum_{i=1}^lV(x_i,y_i,f)+gamma|f|_K^2,（1）$

其中 $V$ 是某種損失函數，比如對於RLS是平方損失 $(y_i-f(x_i))^2$ ，對於SVM的hinge loss函數 $mbox{max}[0,1-y_if(x_i)]$ 。懲罰 RKHS範數對可能解施加了平滑條件。

傳統的表示理論認為在 $mathcal H_K$ 中存在這個最小化問題的解，並可以寫成如下形式：

$f^*(x)=sum_{i=1}^lalpha_iK(x_i,x)$ 。

因此這個問題轉化成了在係數 $alpha_i$ 的有限維空間中最優化的問題，這是SVM，RLS和其他回歸分類任務的演算法基礎。

我們首先考慮已知邊緣分布的情形。

2.1邊緣分布 $mathcal P_X$ 已知

我們的目的是通過引入額外的關於邊緣分布 $mathcal P_X$ 的幾何結構信息來拓展這個框架。我們想要確保解關於環繞空間（ambient space:這裡根據Wikipedia的介紹對環繞空間作個小解釋：在數學尤其是幾何和拓撲學中，ambient space是環繞一個數學對象的空間，比如一條線可以進行孤立的研究，也可以把它當成二維空間中的一個對象，這時環繞空間是一個平面，也可以把它作為三維空間中的一個對象，這時環繞空間是三維的）和邊緣分布 $mathcal P_X$ 都是平滑的，為此我們引入另一個正則化項：

$f^*=mbox{argmin}_{finmathcal H_K}frac{1}{l}sum_{i=1}^{l}V(x_i,y_i,f)+gamma_A|f|_K^2+gamma_I|f|_I^2，（2）$

其中 $|f|_I^2$ 一個可以反映 $mathcal P_X$ 內蘊結構的懲罰項。直觀上 $|f|_I^2$ 是相應概率分布的一個平滑懲罰項。例如，如果概率分布是一個低維流形， $|f|_I^2$ 可沿著這個流形來懲罰 $f$ 。 $gamma_A$ 控制著在環繞空間中的函數複雜度，而 $gamma_I$ 控制著在 $mathcal P_X$ 內蘊幾何上的函數複雜度。如下面的定理所示，可以獲得解 $f^*$ 的顯式函數形式。

Theorem 1：假定懲罰項 $|f|_I$ 關於RKHS範數 $|f|_K$ 充分光滑。那麼在式（2）中優化問題的解 $f^*$ 存在，並且符合以下表示：

$f^*(x)=sum_{i=1}^{l}alpha_iK(x_i,x)+int_{mathcal M}alpha(z)K(x,z)dmathcal P_X(z)，（3）$

，其中 $mathcal M=mbox{supp}{mathcal P_X}$ 是邊緣分布 $mathcal P_X$ 的支撐（the support of the marginal $mathcal P_X$ ）。

上面的表示定理允許我們根據已標記數據，（環繞）核 $K$ 和邊緣分布 $mathcal P_X$ 來直接寫出解 $f^*$ 。如果 $mathcal P_X$ 未知，解可以通過 $mathcal P_X$ 的經驗估計寫出。取決於這個估計的固有性質，得到的解也是不同方式的近似。

2.2邊緣分布 $mathcal P_X$ 未知

在絕大多數情況下 $mathcal P_X$ 是未知的。所以我們必須試圖獲得 $mathcal P_X$ 的經驗估計和 $| |_I$ 。需要說明為了獲得這個經驗估計，未標記數據數量是充足的。

一種特定的情況是當 $mathcal P_X$ 的支撐是一個緊緻子流形 $mathcal Msubsetmathbb R^n$ 。在這種情況下， $|f|_I$ 一個自然選擇是 $int_{xinmathcal M}| abla_{mathcal M}f|^2dmathcal P_X(x)$ ，其中 $abla_{mathcal M}$ 是 $f$ 沿著流形 $mathcal M$ 的梯度，這個積分是關於邊緣分布的。

這個優化問題變成了：

$f^*=mbox{argmin}_{fin mathcal H_K}frac{1}{l}sum_{i=1}^lV(x_i,y_i,f)+gamma_A|f|_K^2+gamma_Iint_{xinmathcal M}| abla_{mathcal M}f|^2dmathcal P_X(x)$ .

$int_{xinmathcal M}| abla_{mathcal M}f|^2dmathcal P_X(x)$ 可以基於已標記和未標記數據使用拉普拉斯矩陣（graph Laplacian）近似。關於這些問題的進一步討論超出了本文範圍，可以表明的是在一定條件下選擇鄰接圖的指數權重拉普拉斯矩陣在流形上可以收斂到Laplace-Beltrami運算元 $Delta_{mathcal M}$ （或者它的加權形式）。詳細情況可參考Belkin (2003);Lafon (2004); Belkin and Niyogi (2005); Coifman et al. (2005); Hein et al. (2005)。

因此，給定已標記樣本 ${(x_i,y_i)}_{i=1}^l$ 和未標記數據 ${x_j}_{j=l+1}^{j=l+u}$ ，我們考慮如下優化問題：

$egin{split}f^*&=mbox{argmin}_{finmathcal H_K}frac{1}{l}sum_{i=1}^l+gamma_A|f|_K^2+frac{gamma_I}{(u+l)^2}sum_{i,j=1}^{l+u}(f(x_i)-f(x_j))^2W_{ij}\&=mbox{armmin}_{finmathcal H_K}frac{1}{l}sum_{i=1}^l+gamma_A|f|_K^2+frac{gamma_I}{(u+l)^2}old f^TLold f，（4）end{split}$

$W_{ij}$ 是數據鄰接圖的邊的權重， $old f=[f(x_1,...,f(x_{l+u}))]^T$ ，拉普拉斯矩陣 $L=D-W$ 。這裡對角矩陣為 $D_{ii}=sum_{j=1}^{l+u}W_{ij}$ ,歸一化係數 $frac{1}{(u+l)^2}$ 是拉普拉斯運算元經驗估計的自然比例因子。如果是一個稀疏圖的話可用通過 $sum_{i,j=1}^{l+u}W_{ij}$ 來代替。

下面的表示定理是我們演算法的關鍵。

Theorem 2：依照已標記和未標記數據優化問題（4）的最小值遵從下面的展開式：

$f^*(x)=sum_{i=1}^{l+u}alpha_iK(x_i,x)（5）$

Remark 1：存在 $| |_I$ 的幾個自然選擇。幾個例子如下：

迭代拉普拉斯運算元 $(Delta_{mathcal M})^k$ 。不同的運算元 $(Delta_{mathcal M})^k$ 及其線性組合提供了一個自然的光滑懲罰項。回顧一下Laplace-Beltrami（拉普拉斯-貝特拉米）運算元 $Delta_{mathcal M}$ 可以定義為散度的梯度向量場 $Delta_{mathcal M}f=div( abla_{mathcal M}f)$ ，如下面的等式 $mu$ ： $int_{xin mathcal M}f(x)Delta_{mathcal M}f(x)dmu=int_{xin mathcal M}| abla_{mathcal M}f(x)|^2dmu$ ,其中 $mu$ 是黎曼流形上的標準測度（均勻分布）。如果 $mu$ 取為非均勻那麼相應的就是加權的Laplace-Beltrami運算元（例如Grigoryan,2006）
熱半群 $e^{-tDelta_{mathcal M}}$ 是對應流形中擴散過程（布朗運動）的一系列光滑運算元。可以去 $|f|_I^2=int_{mathcal M}fe^{tDelta_{mathcal M}}(f)dmathcal P_X$ 。需要指出的是當 $t$ 的值很小時相應格林函數（ $mathcal M$ 的熱核）（Green function:the heat kernel of $mathcal M$ ）在測地坐標上非常接近一個高斯函數，在環繞空間中可以通過一個sharp Gaussian（此處應該理解為方差很小的高斯函數）近似。
海森矩陣的平方範數（Squared norm of the Hessian）(Donoho and Grimes,2003)。海森矩陣 $old H(f)$ ( $f$ 的二階導矩陣)通常依賴於坐標系，但 $old H$ 的Frobenius範數在任何測地坐標系中都是一樣的，因此其在黎曼流形 $mathcal M$ 上的定義是不變的。使用 $old H$ 的F範數作為正則項體現了除了薄板樣條函數(thin-plate splines)的一個有趣推廣。我們也寫作 $Delta_{mathcal M}=tr(old H(f))$ 。

Remark 2：為什麼不直接使用內蘊正則項（intrinsic regularizer）？聯合使用環繞和內蘊正則項（ambient and intrinsic regualrizers）有以下兩個重要原因：

我們很難直接獲得 $mathcal M$ 或真正的潛在邊緣分布，只有從其中採樣而得的數據點。所以相應的正則化項就只是針對採樣而得的流形是不適定（ill-posed）的。通過引入環繞項這個問題就變成適定（well-posed）的.
存在很多這樣的情況：關於環繞空間的正則化會得到更好的解，例如，當流形假設不成立（或者成立的程度較低）。在實際應用中折中這兩種正則項可能會非常重要。

Remark 3: 簡單起見我們使用拉普拉斯矩陣，規範化拉普拉斯矩陣 $ilde L=D^{-1/2}LD^{-1/2}$ 在我們所有的公式中可以和 $L$ 互換。用 $ilde L$ 來代替 $L$ 提供網路一定的理論保證（von Luxburg et al., 2004），而且在許多實際任務中表現一樣好甚至更好。 $ilde L$ 和加權Laplace-Beltrami運算元的關係在（Lafon 2004）中有討論。

Remark 4：一個限制在 $mathcal M$ 上的全局核 $K$ (表示為 $K_{mathcal M}$ )也是一個在 $mathcal M$ （其相關的RKHS $mathcal H_{mathcal M}$ : $mathcal M ightarrowmathbb R$ ）上的核。建議 $|f|_I$ 的一個選擇為 $|f|_I=|f_{mathcal M}|_{K_{mathcal M}}$ ( $f_{mathcal M}$ 表示 $f$ 限制於 $mathcal M$ )。結果表明對於相應優化問題的解 $f^*$ 有 $|f^*|_I=|f^*|_K$ ，即儘管有一個不同的參數 $gamma$ 和標準的正則項的解仍相同（「這個現象第3節討論」，但此處不再寫，有機會更第3節）。所以沒有兩種不同的光滑測度的話不可能有樣本外擴展。另一方面一個不同的限制在 $mathcal M$ 上的環繞核可以達到內蘊正則化項相同的作用。例如一個sharp高斯核可以看成在 $mathcal M$ 上熱核的一種近似。因此一個（sharper）核可能用在未標記數據中來估計 $mathcal M$ 上的熱核，一個wider核來做inference。

4 Algorithms

我們現在討論兩個標準正則化演算法（RLS和SVM）並給出它們的擴展版（LapRLS，LapSVM）。這可以通過選擇不同代價函數 $V$ 和正則化參數 $gamma_A,gamma_I$ 求解優化問題式（4）來獲得。設定一下符號含義：假定有 $l$ 個已標記數據 ${(x_i,y_i)}_{i=1}^l$ 和 $u$ 個未標記數據 ${(x_i,y_i)}_{j=l+1}^{j=l+u}$ 。用 $K$ 表示核函數或者Gram矩陣。

4.1 Regularized Least Squares

RLS演算法是一個全監督方法，需要求解下式： $mbox{min}_{finmathcal H_K}frac{1}{l}sum_{i=1}^{l}(y_i-f(x_i))^2+gamma|f|_K^2$ ,在傳統表示理論中解的形式如下：

$f^*(x)=sum_{i=1}^lalpha_i^*K(x,x_i)$

對上述問題換個形式的寫法，我么得到如下 $l$ -dimension變數 $alpha=[alpha_1...alpha_l]^T$ :

$alpha^*=mbox{argmin}frac{1}{l}(Y-Kalpha)^T(Y-Kalpha)+gammaalpha^TKalpha$ ，

其中 $K$ 是 $l imes l$ 的Gram矩陣 $K_{ij}=K(x_i,x_j)$ , $Y$ 是標記向量 $Y=[y_1...y_l]^T$ 。

上面的目標函數的導數在最優解處為0：

$frac{1}{l}(Y-Kalpha^*)T(-K)+gamma Kalpha^*=0$

得出最優解為： $alpha^*=(K+gamma lI)^{-1}Y$ 。

4.2Laplacian Regularized Least Squares (LapRLS)

LapRLS求解式（4）中的優化問題，其中損失函數為平方損失函數：

$mbox{min}_{finmathcal H_K}frac{1}{l}sum_{i=1}^{l}(y_i-f(x_i))^2+gamma_A|f|_K^2+frac{gamma_I}{(u+l)^2}old f^TLold f$

如前邊的表示定理所說，解可以寫成在已標記和未標記數據上核函數的擴展形式：

$f^*(x)=sum_{i=1}^{l+u}alpha_i^*K(x,x_i)$

依然對上式換種形式的寫法，我們得到一個 $l+u$ 維變數 $alpha=[alpha_1...alpha_{l+u}]^T$ 凸可微目標函數:

$alpha^*=mbox{argmin}_{alphainmathbb R^{l+u}}frac{1}{l}(Y-JKalpha)^T(Y-JKalpha)+gamma_Aalpha^TKalpha+frac{gamma_I}{(u+l)^2}alpha^TKLKalpha$ ，

$K$ 是在已標記和未標記數據點上的 $(l+u) imes(l+u)$ Gram矩陣。 $Y$ 是一個 $(l+u)$ 維標記向量： $Y=[y_1,...,y_l,0,...,0]$ ， $J$ 是一個 $(l+u) imes(l+u)$ 對角矩陣， $J=mbox{diag}(1,...,1,0,..,0)$ 。

令上述目標函數在最優值處的導數為0：

$frac{1}{l}(Y-JKalpha)^T(-JK)+(gamma_AK+frac{gamma_Il}{(u+l)^2}KLK)alpha=0$

從而最優解為：

$alpha^*=(JK+gamma_AlI+frac{gamma_Il}{(u+l)^2}LK)^{-1}Y，（8）$ 。

可以看出在式（8）中當 $gamma_I=0$ 時，未標記數據的係數為0，已標記數據的係數和標準RLS中一樣。

4.3 Support Vector Machine Classification

這裡我們說一下SVM解決二分類問題。對於SVM需要解決如下問題：

$mbox{min}_{finmathcal H_K}frac{1}{l}sum_{i=1}^{l}(1-y_if(x_i))_++gamma|f|_K^2$ ，其中hinge loss定義為：

$（1-yf(x))_+=mbox{max}(0,1-yf(x))$ ， $y_iin{-1,+1}$ 。

同樣解可以寫為：

$f^*(x)=sum_{i=1}^lalpha_i^*K(x,x_i)，（9）$

根據SVM的理論，上述問題可以等價的寫為如下形式：

$mbox{min}_{finmathcal H_K,xi_iinmathbb R}frac{1}{l}sum_{i=1}^lxi_i+gamma|f|_K^2\ s.t.y_if(x_i)geq1-xi_i,i=1,...,l\ xi_ige0,i=1,...,l.$

使用拉格朗日乘數法，由於強對偶性質，上述問題有一個簡單的二次規劃形式：

$eta^*=mbox{max}_{etainmathbb R^l}sum_{i=1}^{l}eta_i-frac{1}{2}eta^TQeta\s.t.sum_{i=1}^{l}y_ieta_i=0\0leeta_ilefrac{1}{l},i=1,...,l.$

拉格朗日乘數為 $eta=[eta_1,...,eta_l]^Tinmathbb R^l$ ,其中存在等式約束的原因是式（9）中經常添加一個的偏移項。使用如下符號來表示：

$Y=mbox{diag}(y_1,y_2,...,y_l),\Q=YBig(frac{K}{2gamma}Big)Y,\alpha^*=frac{Yeta^*}{2gamma}.$

這裡 $K$ 依然是關於已標記數據點的Gram矩陣。讀者可能會發現係數有些不一樣，可以對比參考李航《統計學習方法》page109—111，其實沒問題。

4.4Laplacian Support Vector Machines

通過引入內蘊光滑懲罰項，SVM問題擴展如下式：

$mbox{min}_{finmathcal H_K}frac{1}{l}sum_{i=1}^{l}(1-y_if(x_i))_++gamma_A|f|_K^2+frac{gamma_I}{(u+l)^2}old fLold f.$

根據前面的表述定理，問題的解可以寫為如下形式：

$f^*(x)=sum_{i=1}^{l+u}alpha^*K(x,x_i).$

通常在上式中添加一個偏置項 $b$ 。同樣原始問題可以寫成如下形式：

$mbox{min}_{alphainmathbb R^{l+u},xiinmathbb R^l}frac{1}{l}sum_{i=1}^{l}xi_i+gamma_Aalpha^TKalpha+frac{gamma_I}{(u+l)^2}alpha^TKLKalpha\ mbox{subject to}:y_i(sum_{j=1}^{l+u}alpha_jK(x_i,x_j)+b)ge1-xi_i,i=1,...,l\xi_ige 0,i=1,..,l.$

引入 $eta_i,xi_i$ 作為拉格朗日乘數，則有：

$L(alpha,xi,b,eta,zeta)=frac{1}{l}sum_{i=1}^{l}xi_i+frac{1}{2}alpha^T(2gamma_AK+2frac{gamma_A}{(l+u)^2}KLK)alpha\-sum_{i=1}^{l}eta_i(y_i(sum_{j=1}^{l+u}alpha_jK(x_i,x_j)+b)-1+xi_i)-sum_{i=1}^{l}zeta_ixi_i.$

若要化成對偶形式需有：

$frac{partial L}{partial b}=0Rightarrowsum_{i=1}^{l}eta_iy_i=0,\ frac{partial L}{partialxi_i}Rightarrowfrac{1}{l}-eta_i-xi_i=0,\ Rightarrow0leeta_ilefrac{1}{l}(xi_i,zeta_ige0).$

利用以上式子可以將 $L(alpha,xi,b,eta,zeta)$ 化簡為：

$egin{split}L^R(alpha, eta)&=frac{1}{2}alpha^T(2gamma_AK+2frac{gamma_I}{(u+l)^2}KLK)alpha-sum_{i=1}^{l}eta_i(y_isum_{j=1}^{l+u}alpha_jK(x_i,x_j)-1),\&=frac{1}{2}alpha^T(2gamma_AK+2frac{gamma_I}{(u+l)^2}KLK)alpha-alpha^TKJ^TYeta+sum_{i=1}^leta_i,end{split}$

其中 $J=[I,0]$ 是 $l imes (l+u)$ 矩陣， $I$ 是 $l imes l$ 單位矩陣（對應前 $l$ 個已標記數據點）， $Y=mbox{diag}(y_1,y_2,...,y_l)$ 。

令上式對 $alpha$ 求導等於零有：

$frac{partial L^R}{partial alpha}=(2gamma_AK+2frac{gamma_I}{(u+l)^2}KLK)alpha-KJ^TYeta.$

可得：

$alpha=(2gamma_AI+2frac{gamma_I}{(u+l)^2}LK)^{-1}J^TYeta^*.（10）$

需要說明的是 $alpha$ 和 $eta$ 的關係不再像SVM演算法中那樣簡單。在SVM對偶問題中出現一個包含 $l$ 個對偶變數的線性系統，通過求解可得 $(l+u)$ 個擴展係數

將解代回拉格朗日公式有：

$eta^*=mbox{max}_{etainmathbb R^l}sum_{i=1}^leta_i-frac{1}{2}eta^TQeta（11）\ mbox{subject to：}sum_{i=1}^leta_iy_i=0\ 0leeta_ilefrac{1}{l}i=1,...,l（12）$

其中 $Q=YJK(2gamma_AI+2frac{gamma_I}{(u+l)^2}LK)^{-1}J^TY$ 。

Laplacian SVMs可以通過一個標準的SVM求解程序（由上面的矩陣構成的二次型）來實現。可以通過求解式（10）中的線性系統來獲得擴展係數的解。

需要說明的是當 $gamma_I=0$ ,SVM QP和式（11）（10）關於未標記數據的擴展係數為0。在這種情況下在已標記數據上的展開係數和Q矩陣和標準SVM一樣。

流形正則化：一個從已標記和未標記樣本學習的幾何框架（JMLR2006）

2半監督學習框架（The Semi-Supervised Learning Framework）

2.1邊緣分布 已知

2.2邊緣分布 未知

4 Algorithms

2.1邊緣分布 $mathcal P_X$ 已知

2.2邊緣分布 $mathcal P_X$ 未知