核方法

0x01 为什么需要核函数

问题1:

SVM显然是线性分类器,但数据如果根本就线性不可分怎么办?

解决方案1:

数据在原始空间(称为输入空间)线性不可分,但是映射到高维空间(称为特征空间)后很可能就线性可分了。

问题2:

映射到高维空间同时带来一个问题:在高维空间上求解一个带约束的优化问题显然比在低维空间上计算量要大得多,这就是所谓的“维数灾难”。

解决方案2:

于是就引入了“核函数”,核函数的价值在于它虽然也是讲特征进行从低维到高维的转换,但核函数绝就绝在它事先在低维上进行计算,而将实质上的分类效果表现在了高维上,也就是说避免了直接在高维空间中的复杂计算

例如图中的两类数据,分别分布为两个圆圈的形状,不论是任何高级的分类器,只要它是线性的,就没法处理,SVM 也不行。因为这样的数据本身就是线性不可分的。

0x02 什么是核函数

引入:

从上图我们可以看出一个理想的分界应该是一个“圆圈”而不是一条线(超平面)。如果用 X1 和 X2 来表示这个二维平面的两个坐标的话,我们知道一条二次曲线(圆圈是二次曲线的一种特殊情况)的方程可以写作这样的形式:

a1X1+a2X12+a3X2+a4X22+a5X1X2+a6=0a_1X_1+a_2X_1^2+a_3X_2+a_4X_2^2+a_5X_1X_2+a_6=0

注意上面的形式,如果我们构造另外一个五维的空间:

核方法的主要思想是基于这样一个假设:“在低维空间中不能线性分割的点集,通过转化为高维空间中的点集时,很有可能变为线性可分的”

i=15aiZi+a6=0\sum_{i=1}^5 a_iZ_i +a_6=0

核函数的定义:

X\mathcal{X}是输入空间(欧式空间RnR^n的子集或离散集合),又设H\mathcal{H}为特征空间(希尔伯特空间),如果存在一个从X\mathcal{X}H\mathcal{H}的映射:

ϕ(x):XH\phi(x):\mathcal{X} \rightarrow \mathcal{H}

使得对所有的x,zXx,z \in \mathcal{X},函数K(x,z)K(x,z)满足条件:

K(x,z)=ϕ(x)ϕ(z)K(x,z) = \phi(x)\cdot\phi(z)

则称K(x,z)K(x,z)为核函数,ϕ(x)\phi(x)为映射函数,式中$ \phi(x)\cdot\phi(z)$为二者内积。

核技巧一种利用核函数直接计算K(x,z)K(x,z),以避开分别计算ϕ(x)\phi(x)ϕ(z)\phi(z) ,从而加速核方法计算的技巧。

映射函数ϕ\phi的取法并不是唯一的:

假设输入空间是R2R^2,核函数是K(x,z)=(xz)2K(x,z)=(x\cdot z)^2,试找出相关的特征空间H\mathcal{H}和映射ϕ(x):R2H\phi(x):R^2 \rightarrow \mathcal{H}

解:

取特征空间H=R3\mathcal{H}=R^3,记x=(x(1),x(2))T,z=(z(1),z(2))Tx=(x^{(1)},x^{(2)})^T,z=(z^{(1)},z^{(2)})^T.由于

(xz)2=(x(1)z(1)+x(2)z(2))2=(x(1)z(1))2+2x(1)z(1)x(2)z(2)+(x(2)z(2))2(x\cdot z)^2 = (x^{(1)}z^{(1)}+x^{(2)}z^{(2)})^2 = (x^{(1)}z^{(1)})^2+2x^{(1)}z^{(1)}x^{(2)}z^{(2)}+(x^{(2)}z^{(2)})^2

所以可以取映射函数ϕ(x)=((x(1))2,2x(1)x(2),(x(2))2)T\phi(x)=((x^{(1)})^2,\sqrt{2}x^{(1)}x^{(2)},(x^{(2)})^2)^T.

也可以取ϕ(x)=12((x(1))2(x(2))2,2x(1)x(2),(x(1))2+(x(2))2)T\phi(x)=\frac{1}{\sqrt{2}}((x^{(1)})^2-(x^{(2)})^2,2x^{(1)}x^{(2)},(x^{(1)})^2+(x^{(2)})^2)^T.

但取H=R4\mathcal{H}=R^4时,可以取ϕ(x)=((x(1))2,x(1)x(2),x(1)x(2),(x(2))2)T\phi(x)=((x^{(1)})^2,x^{(1)}x^{(2)},x^{(1)}x^{(2)},(x^{(2)})^2)^T

0x03 正定核

预备知识:

假设K(x,z)K(x,z)是定义在X×X\mathcal{X}×\mathcal{X}上的对称函数,对任意的xiX,i=1,2,3,...,m,K(x,z)x_i\in \mathcal{X},i=1,2,3,...,m,K(x,z)关于x1,x2,...,xmx_1,x_2,...,x_m的Gram矩阵是半正定的。则依据函数K(x,z)K(x,z)可以构成一个希尔伯特空间。其步骤如下:

  • 首先定义映射ϕ\phi并构成向量空间S\mathcal{S}.
  • S\mathcal{S}定义内积构成内积空间.
  • S\mathcal{S}完备化成希尔伯特空间.

1.定义映射,构成向量空间S\mathcal{S}.

定义映射:

ϕxK(,x)\phi:x \rightarrow K(\cdot,x)

根据这一映射,对任意xiX,αiRx_i \in \mathcal{X},\alpha_i \in R,定义线性组合:

f()=i=1mαiK(,xi)(1)f(\cdot)=\sum_{i=1}^m\alpha_iK(\cdot,x_i) \tag{1}

已知线性组合的各个元素均来自集合S\mathcal{S}。由于集合S\mathcal{S}对加法和乘法运算是封闭的,所以S\mathcal{S}构成一个向量空间。

2.在S\mathcal{S}定义内积构成内积空间.

S\mathcal{S}上定义一个运算*,对任意的f,gSf,g\in \mathcal{S},

g()=j=1lβjK(,zj)(2)g(\cdot)=\sum_{j=1}^l\beta_jK(\cdot,z_j) \tag{2}

定义运算*:

fg=i=1mj=1lαiβjK(xi.zj)(3)f*g = \sum_{i=1}^m\sum_{j=1}^l\alpha_i\beta_jK(x_i.z_j) \tag{3}

证明运算*是空间S\mathcal{S}的内积。需要证:

a.(cf)g=c(fg),cRb.(f+g)h=fh+gh,hSc.fg=gfd.ff0,ff=0f=0\begin{array}{l} a.&(cf)*g=c(f*g),c\in R\\ b.&(f+g)*h=f*h+g*h,h\in \mathcal{S}\\ c.&f*g=g*f\\ d.&f*f\geq0,f*f=0 ⇔ f=0 \end{array}

其中a.b.c易证。现在主要证明d.

现证明ff0f*f\geq0:

由式(3)可得:

ff=i,j=1mαiαjK(xi.xj)f*f=\sum_{i,j=1}^m\alpha_i\alpha_jK(x_i.x_j)

由Gram矩阵的半正定性知该式右端非负,即ff0f*f\geq0.

再证明ff=0f=0f*f=0 ⇔ f=0:

充分性显然成立。下面工作主要是证明必要性,即ff=0f=0f*f=0 ⇒ f=0.

首先证明不等式:

fg2(ff)(gg)(4)|f*g|^2\leq(f*f)(g*g) \tag{4}

f,gS,λRf,g\in \mathcal{S},\lambda \in R,则f+λgSf+\lambda g\in\mathcal{S},于是:

(f+λg)(f+λg)0ff+2λ(fg)+λ2(gg)0(f+\lambda g)(f+\lambda g)\geq0\\ f*f+2\lambda(f*g)+\lambda^2(g*g)\geq0

将其看作λ\lambda的二次函数,根据根的判别式可知:

(fg)2(ff)(gg)0(f*g)^2-(f*f)(g*g)\leq0

则式(4)得证。

g=K(,x)g=K(\cdot,x),则由式(3)可得:K(,x)f=i=1mαiK(x,xi)=f(x)K(\cdot,x)*f=\sum_{i=1}^m\alpha_iK(x,x_i)=f(x).所以有:

f(x)2=K(,x)f2(5)|f(x)|^2=|K(\cdot,x)*f|^2 \tag{5}

结合式(4)可知:

K(,x)f2(K(,x)K(,x))(ff)=K(x,x)(ff)|K(\cdot,x)*f|^2\leq(K(\cdot,x)*K(\cdot,x))(f*f)=K(x,x)(f*f)

f(x)2K(x,x)(ff)|f(x)|^2\leq K(x,x)(f*f)

此式表明,ff=0f*f=0时,对任意的xXx\in \mathcal{X},都有f(x)=0|f(x)|=0.

至此证明了*是向量空间X\mathcal{X}的内积,可以用\cdot代替*:

fg=i=1mj=1lαiβjK(xi.zj)(6)f\cdot g = \sum_{i=1}^m\sum_{j=1}^l\alpha_i\beta_jK(x_i.z_j) \tag{6}

3.将S\mathcal{S}完备化成希尔伯特空间.

由式(6)定义的内积就可以得到范数:

f=ff||f||=\sqrt{f\cdot f}

因此,S\mathcal{S}是一个赋范向量空间。根据泛函分析理论,对于不完备的赋范向量空间S\mathcal{S},一定可以使之完备化,得到完备的赋范向量空间H\mathcal{H}。一个内积空间,当作为赋范向量空间是完备的时候,就是希尔伯特空间。

扩展:

完备性

完备性就是说任意柯西列的极限仍然在这个空间中。

柯西列就是空间中元素构成的一个序列,并且这个序列在无穷远处两个元素之间的距离趋于零。准确的说,如果空间中有一个序列{xn}\{x_n\} ,当 n,mn,m\rightarrow \infty 的时候,d(xn,xm)0d(x_n,x_m)\rightarrow 0,则 {xn}\{x_n\}就是一个柯西列,也就是说完备性保证了取序列极限不会跑到空间外面去。

一个不完备的例子就是有理数的集合,例如这个集合可以用柯西列的极限去逼近2\sqrt2,而这个极限并不在有理数这个集合中,所以有理数几何是不完备的。


充要条件:

K:X×XRK:\mathcal{X}×\mathcal{X}\rightarrow R是对称函数,则K(x,z)K(x,z)为正定核函数的充要条件是对任意的xiX,i=1,2,3,...,m,K(x,z)x_i\in \mathcal{X},i=1,2,3,...,m,K(x,z)对应的GramGram矩阵:

K=[K(xi,xj)]m×mK=[K(x_i,x_j)]_{m×m}

是半正定矩阵。

  • 必要性:

    由于K(x,z)K(x,z)X×X\mathcal{X}×\mathcal{X}上的正定核,所以存在从XH\mathcal{X}\rightarrow \mathcal{H}的映射ϕ\phi,使得K(x,z)=ϕ(x)ϕ(z)K(x,z)=\phi(x)\cdot \phi(z).

    构造Gram矩阵:

    [Kij]m×m=[K(xi,xj)]m×m[K_{ij}]_{m×m}=[K(x_i,x_j)]_{m×m}

    对任意的c1,c2,...,cmRc_1,c_2,...,c_m \in R,有:

i,j=1mcicjK(xi,xj)=i,j=1mcicj(ϕ(x)ϕ(z))=(iciϕ(xi))(jcjϕ(xj))=iciϕ(xi)20 \begin{array}{l} \sum_{i,j=1}^mc_ic_jK(x_i,x_j)&=\sum_{i,j=1}^mc_ic_j(\phi(x)\cdot \phi(z))\\ &=\left( \sum_ic_i\phi(x_i)\right)\cdot\left( \sum_jc_j\phi(x_j)\right)\\ &=||\sum_ic_i\phi(x_i)||^2 \geq 0 \end{array}

因此K(x,z)K(x,z)的Gram是半正定的。

  • 充分性:

    假设K(x,z)K(x,z)是定义在X×X\mathcal{X}×\mathcal{X}上的对称函数,对任意的xiX,i=1,2,3,...,m,K(x,z)x_i\in \mathcal{X},i=1,2,3,...,m,K(x,z)关于x1,x2,...,xmx_1,x_2,...,x_m的Gram矩阵是半正定的。可以构造映射函数ϕ:xK(,x)\phi:x\rightarrow K(\cdot,x).

    K(,x)f=i=1mαiK(x,xi)=f(x)K(\cdot,x)*f=\sum_{i=1}^m\alpha_iK(x,x_i)=f(x)

    并且K(,x)K(,z)=K(x,z)K(\cdot,x)\cdot K(\cdot,z)=K(x,z)可知:K(x,z)=ϕ(x)ϕ(z)K(x,z)=\phi(x)\cdot\phi(z)

    表明K(x,z)K(x,z)是核函数。

0x04 常见核函数

  • 线性核函数

    K(x,z)=xzK(x,z) = x\cdot z

    线性核,主要用于线性可分的情况,我们可以看到特征空间到输入空间的维度是一样的,其参数少速度快,对于线性可分数据,其分类效果很理想,因此我们通常首先尝试用线性核函数来做分类,看看效果如何,如果不行再换别的。

  • 多项式核函数

    K(x,z)=(xz+1)pK(x,z) = (x\cdot z+1)^p

    多项式核函数可以实现将低维的输入空间映射到高纬的特征空间,但是多项式核函数的参数多,当多项式的阶数比较高的时候,核矩阵的元素值将趋于无穷大或者无穷小,计算复杂度会大到无法计算。

  • 高斯核函数

    K(x,z)=exp(xz22σ2)K(x,z) = exp(-\frac{||x-z||^2}{2\sigma^2})

    高斯径向基函数是一种局部性强的核函数,其可以将一个样本映射到一个更高维的空间内,该核函数是应用最广的一个,无论大样本还是小样本都有比较好的性能,而且其相对于多项式核函数参数要少,因此大多数情况下在不知道用什么核函数的时候,优先使用高斯核函数。

  • Sigmoid核函数

    K(x,z)=tanh(γxz+θ)K(x,z) = tanh(\gamma x\cdot z+\theta)

    采用sigmoid核函数,支持向量机实现的就是一种多层神经网络。

核函数的选取
可根据专家先验知识预先选定核函数,或者采用交叉验证,试用不同核函数。或者,采用混合核函数的方法,将不同的核函数结合起来。在吴恩达的课上,也曾经给出过一系列的选择核函数的方法:

  • 如果特征的数量大到和样本数量差不多,则选用LR或者线性核的SVM;
  • 如果特征的数量小,样本的数量正常,则选用SVM+高斯核函数;
  • 如果特征的数量小,而样本的数量很大,则需要手工添加一些特征从而变成第一种情况。

参考