介紹

如下圖所示，這是一個二分類問題，紅色藍色分別表示兩個類，顯然這個決策邊界是非線性的

圖1

模式分類的常見的方法就是使用高斯核 k(x,z)=e^{-frac{||x-z||^2}{sigma^2}} .核 k 定義了一個在二維平面上的再生核希爾伯特空間，用 mathcal H 表示。

假設給定比較少的已標記數據對 (x_i,y_i) ,數量為 l 對每個 x_iinmathbb R^2 有 y_iin {-1,+1} 。那麼為了學得一個好的分類器，可能需要求解以下維問題：

f=mathrm{argmin}_{hin mathcal H}frac{1}{l}sum_{i=1}^{l}V(h,x_i,y_i)+gamma|h|_{mathcal H}^2

公式的含義顯而易見，不細說。根據表示理論解的形式可以寫為：

f(x)=sum_{i=1}^lalpha_ik(x,x_i)

V 是平方損失時相當於RLS，是hinge loss時相當於SVM。

如圖1b所示考慮當只有兩個已標記數據點的時候，學到的函數是兩個高斯的線性組合，如圖2所示兩個中心即是這兩個數據點。

圖2

因為高斯核是各向同性的，因此它是兩個對稱球狀。最節決策平面是一條線，如圖2c所示。

很明顯高斯的對稱球狀不是合適的核函數選擇，因為決策平面和實際的類數據分布不一致。我們提出這樣一個問題：

能否定義一個核函數 ilde k ：這個核函數能夠適應數據的幾何分布？

這樣的核函數必須滿足兩個性質：

  • 這是有個有效的Mercer kernel ilde k : X imes X ightarrowmathbb R ,因此定義了一個新的RKHS ilde{ mathcal H}
  • 它能反映我們關於數據集合分布的直覺。

我們的希望是獲得這樣一個問題：

g=mathrm{argmin}_{hin ilde {mathcal H}}frac{1}{2}sum_{i=1}^{2}V(h,x_i,y_i)+|h|_{ ilde {mathcal H}}^2

它的解 g(x)=sum_{i=1}^{2}alpha_i ilde k(x,x_i) 應該符合我們的要求。

注意這裡的 g(x) 仍然是兩個核函數的線性組合，中心是兩個數據點。這個解必須產生一個直觀上符合圖1a的決策面來分開兩個圓。Mercer Kernel的先天形式顯然不符合。

這裡為了滿足要求，我們需要把原始空間做變換獲得一個新的RKHS ilde{mathcal H} 。根據流行正則化的思想，可利用未標記數據來估計數據的潛在的邊緣分布的幾何形狀。新的 ilde k 可以通過未標記數據顯示的計算。在新的RKHS中只有已標記數據，可以對半監督推斷使用全監督核方法。

Warping an RKHS using Poing Cloud Norms（「彎曲」RKHS）

先來討論一下RKHS的基本性質。設 X 表示一個歐式空間或流行的一個緊域（compact domain）。

如果點的計算函數有界，也就是對任何 xin X,fin mathcal H ,存在一個 C 使得

|f(x)|le C|f|_{mathcal H} ，那麼一個完備的希爾伯特空間 mathcal H ( X ightarrow mathbb R ,內積為 <cdot,cdot>_{mathcal H} )是再生核希爾伯特空間。

可以使用Risesz表示定理為點的計算函數來構建一個對稱的半正定核 k(x,z):

f(x)=<f,k(x,cdot)>_{mathcal H}

k(x,z)=<k(x,cdot),k(z,cdot)>_{mathcal H}

我們將會闡釋一個非常普適的過程：「彎曲」範數 ||_{mathcal H} 給出一個新的RKHS ilde {mathcal H} ,其核我們表示為 k(x,z) .

設 mathcal V 是一個有半正定內積（二次形式）的線性空間，設 S：mathcal H ightarrowmathcal V 是一個有界線性運算元。我們定義 ilde {mathcal H} 是來自 mathcal H 的函數的空間，然而內積修改為：

<f,g>_{ ilde {mathcal H}}=<f,g>_{mathcal H}+<Sf,Sg>_{mathcal V}

命題2.1： ilde {mathcal H} 是一個再生核希爾伯特空間。

證明：顯然 ilde {mathcal H} 是完備的，因為改進範數（modified norm）中的柯西列也是原始範數（original norm）中的柯西列，所以收斂到 mathcal H 中的某個元。同樣的原因顯然點的計算有界 |f(x)|le C|f|_{mathcal H} 暗含： |f(x)|le C|f|_{ ilde{mathcal H}} .

我們感興趣的是當 S 和 mathcal V 依賴於數據的時候。注意到命題2.1非常普適，對許多S和 mathcal V 的選擇都成立，這通常並不容易把核 k 和 ilde k 聯繫起來。但如後面所說，對一個類從『point-cloud norms』的角度這種聯繫可以顯示錶示。

給定數據點 x_1,...,x_n ,設 S:mathcal H ightarrowmathbb R^n 為計算映射： S(f)=(f(x_1),...,f(x_n)) .令 old f=(f(x_1),...,f(x_n)) . mathbb R^n 上的（半）範數通過一個對稱半正定矩陣 M 給定：

|Sf|_{mathcal V}^2=old f^tMold f

我們將會推導出 ilde k(x,z) 的精確形式. 對 ilde {mathcal H} 採用正交分解有：

ilde{mathcal H}=spanig{ ilde k(x_1,cdot),..., ilde k(x_n,cdot)ig}oplus ilde{mathcal H^{ot}}

其中 ilde{mathcal H^{ot}} 表示在所有數據點消失的函數。很明顯對任何 fin ilde{mathcal H^{ot}} , Sf=0 ,因此對空間中的任何函數 g 有 <f,g>_{ ilde{mathcal H}}=<f,g>_{mathcal H}

因此對任意 fin ilde{mathcal H}^{ot} 有：

egin{split}f(x)=&<f, ilde k(x,cdot)>_{ ilde{mathcal H}}( ilde{mathcal H}的再生核性質)\=&<f,k(x,cdot)>_{mathcal H}(mathcal H的再生核性質)\=&<f, k(x,cdot)>_{ ilde{mathcal H}}(因為fin ilde{mathcal H}^{ot}) end{split}

因此，對任何 fin ilde{mathcal H}^{ot} ，我們有 <f,k(x,cdot)- ilde k(x,cdot)>_{ ilde{mathcal H}}=0 或者 k(x,cdot)- ilde k(x,cdot)in ( ilde{mathcal H}^{ot})^{ot} 。換句話說，

k(x,cdot)- ilde{k}(x,cdot)in spanig{ ilde k(x_1,cdot),..., ilde k(x_n,cdot)ig}

另一方面，對任意 x_iin X 和 fin{ ilde{mathcal H}}^{ot} ，從 ilde{mathcal H} 上的內積定義我們看到

<k(x,cdot),f>_{ ilde{mathcal H}}=0 . 因此， k(x_i,cdot)in( ilde{mathcal H}^{ot})^{ot} .

所以有： span{k(x_i,cdot)}_{i=1}^nsubseteq span{( ilde k(x_i,cdot))}_{i=1}^n .

這兩個spans相同，我們得出:

ilde k(x,cdot)=k(x,cdot)+sum_jeta_j(x)k(x_j,cdot)

其中係數eta_j 取決於 x 。

為了確定 eta_j(x) ,我們我們考慮一個在 x 處計算 k(x_i,cdot) 的線性方程組：

egin{split}k_{x_i}(x)=&<k(x_i,cdot), ilde k(x,cdot)>_{ ilde {mathcal H}}\=&<k(x_i,cdot), k(x,cdot)+sum_jeta_j(x)k(x_j,cdot)>_{ ilde{mathcal H}}\=&<k(x_i,cdot), k(x,cdot)+sum_jeta_j(x)k(x_j,cdot)>_{mathcal H}+old {k_{ x_i}}^tMold g end{split}

其中 old{k_{x_i}}=(k(x_i,x_1)...k(x_i,x_n))^t ， old g 是向量，其組成為 old g_k=k(x,x_k)+sum_jeta_j(x)k(x_j,x_k)

這個公式為下面的方程組提供了係數 eta(x)=(eta_1(x)...eta(x))^T ：

(I+MK)eta(x)=Mold k_x

其中 K 是矩陣 K_{ij}=K(x_i,x_j) , old k_x 像前面一樣表示向量 (k(x_1,x)...k(x_n,x))^t .

最終我們獲得 ilde k 的顯示形式：

ilde k(x,z)=k(x,z)=old k_x^t(I+MK)^{-1}Mold k_z

可以看到矩陣 (I+MK)^{-1}M 是對稱的。當 M 可逆時它等於 (M^{-1}+K)^{-1} ，也明顯對稱。當 M 異常可以對其添加一個小的項然後使用連續性理論。

Choosing the Point Cloud Norm

現在問題的關鍵就是選擇 M 使得依賴數據的改進核 能和我們關於數據的直覺相一致。這些直覺可能由先驗知識提供，或者在半監督學習中由未標記數據的邊緣分布來描述。

這裡我們使用關於point cloud 的Laplacian【1,2】。這個選擇滿足一個關於邊緣分布幾何結構經驗估計的光滑性假設。

設 M=L^p ， p 是一個整數， L 是圖的拉普拉斯矩陣。定義為：

L=D-W ， W_{ij}=e^{-frac{|x_i-x_j|^2}{2sigma^2}} , D 是一個對角矩陣 D_{ii}=sum_iW_{ij} 。

圖的拉普拉斯矩陣體用了顧上的光滑性懲罰： old f^tLold f=sum_{i,j=1}^n(f(x_i),f(x_j))^2W_{ij} .

通常我們用最近鄰來構建這個矩陣。鄰居關係可以隨著我們對數據的理解不同而改變。細節參考【3,4】

參考文獻

  1. Belkin M., Niyogi P. & Sindhwani V. (2004) Manifold Regularization : A Geometric Framework for Learning for Examples. Technical Report TR-2004-06, Dept. of Computer Science, Univ. of Chicago（即前面的介紹）
  2. Sindhwani, V. (2004) Kernel Machines for Semisupervised Learning. Masters Thesis, University of Chicago
  3. Belkin M. (2003) Problems of Learning on Manifolds. Ph.D. Dissertation, Dept. of Mathematics, Univ. of Chicago
  4. Lafon S. (2004) Di usion maps and geometric harmonics. Ph.D. dissertation, Yale University

推薦閱讀：

相关文章