介绍

如下图所示，这是一个二分类问题，红色蓝色分别表示两个类，显然这个决策边界是非线性的

图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

推荐阅读：

相关文章