资料参考来源：

清华大学出版社 周志华 《机器学习》 第六章

清华大学出版社 李航 《统计学习方法》 第二章 感知机，第七章 支持向量机

第八讲：核方法、序列最小优化算法

cs229 lecture 3 support vector machine

引子

线性支持向量机在解决线性分类问题的时候有相当大的作用，但在面对非线性分类问题时，就没有那么简单了。

我们知道，线性分类问题实际上就是需要我们在下图中找到一条合适的能将不同颜色的点分开的超平面：

但非线性分类问题的图像往往会各种各样，例如下图：

显然，直接在图上找超平面将正负类分开是不现实的，这个时候，我们就可以利用核技巧(kernel trick)配合非线性支持向量机来解决这个问题。

核技巧

我们先来讨论一下核技巧。

一般来说，给定一个训练集$T=\{(x_1,y_1),...,(x_N,y_N)\}$，其中$x_i$属于输入空间，$x_i∈X=R^n$，对应的标记有两类$y_i∈Y=\{-1,+1\},i=1,2,...,N$，如果有一个在$R^n$中的超曲面将正负例分开，那么我们就称这个问题为非线性可分问题。

为了解决非线性问题，我们常用的方式是对其进行非线性变换，然后将非线性问题转换成线性问题求解，因为我们线性问题对于我们来说要比非线性问题好求解的多。像下图这个例子,就是通过变换将左图中的椭圆变换成右图中的直线，从而达到将非线性问题转换成线性问题的目的：

现在我们来讨论一下该如何进行变换：

设原空间为$X\subset R^2,x=(x^{(1)},x^{(2)})^T∈X$，新空间为$Z\subset R^2,z=(z^{(1)},z^{(2)})^T∈Z$，我们定义从原空间到新空间的变换（映射）为：

经过变换$z=Φ(x)$，原空间$X\subset R^2$变换为新空间$z\subset R^2$，原空间中的点也相应地变换为新空间中的点，原空间中的椭圆：

也变换成新空间中的直线：

显然，在新空间中直线可以将正负实例点分开。原空间的非线性问题也就转变成了新空间的线性问题。

上面的例子说明，要用线性分类方法求解非线性分类方法，有两个步骤：

1. 将原空间的数据通过一个变换映射到新空间
2. 在新空间里用线性分类学习方法从训练数据中学习分类模型

核技巧就是这样的一个方法。

核技巧在支持向量机中使用的基本想法就是通过一个非线性变换将输入空间（欧式空间$R^n$或离散集合）对应于一个特征空间（希尔伯特空间$H$），使得在输入空间中的超曲面模型能够对应于特征空间中的超平面模型（即支持向量机）。

核函数

定义

设$X$是输入空间（欧式空间$R^n$或离散集合），$H$为特征空间（希尔伯特空间$H$），如果存在一个从X到H的映射

（希尔伯特空间我们可以简单的理解为定义了内积的线性空间。详细内容参考希尔伯特空间（维基百科） 内积空间（维基百科），）

使得对所有的$x,z∈X$，函数$K(x,z)$满足条件：

我们就称$K(x,z)$为核函数，$Φ(x)$为映射函数，式中$Φ(x)·Φ(z)$是$Φ(x)$和$Φ(z)$的内积。（假设有函数$f(x),g(x)$与区间$[a,b]$，且两个函数在该区间上可积且平方可积，那么$\int^b_a f(x)g(x)dx$就是函数的内积，通常记作$< f(x),g(x) >$，不过这个我们在这里并用不到，因为此处的映射后面会用向量表示）

于核技巧而言，我们通常在学习与预测中只定义核函数$K(x,z)$而不显式定义映射函数Φ，因为一般来说直接计算$K(x,z)$会比较容易，而通过$Φ(x)$和$Φ(z)$来计算$K(x,z)$就不那么容易了。

需要注意的是，Φ是输入空间$R^n$到特征空间$H$的映射，$H$一般是高维甚至无穷维的。 我们还可以看到，对给定的核$K(x,z)$,特征空间$H$和映射函数$Φ$的取法并不是唯一的。不仅可以取不同的特征空间，甚至即便是在同一空间也可以取不同的映射。

下面我们举一个简单的例子来说明核函数和映射函数的关系

核函数和映射函数的关系

例子

假设输入空间是$R^2$，核函数是$K(x,z)=(x·z)^2$，我们来试着找出与其对应的特征空间$H$和映射$Φ(x):R^2\rightarrow H$：

首先我们取特征空间$H=R^3$，记$x=(x^{(1)},x^{(2)})^T$，$z=(z^{(1)},z^{(2)})^T$，由于

所以我们可以取映射

易得$Φ(x)·Φ(z)=(xz)^2=K(x,z)$

• 若是取$H=R^3$以及映射

我们也可以得到一个核函数$Φ(x)·Φ(z)=(xz)^2=K(x,z)$

• 另外，还可以取$H=R^4$与映射

核技巧在支持向量机中的应用

回顾上一章我们所讲的线性支持向量机中的对偶问题：

我们可以发现，目标函数只涉及输入实例与实例之间的内积（事实上决策函数、分离超平面也是一样）。我们可以用核函数$K(x_i,x_j)=Φ(x_i)·Φ(x_j)$来代替目标函数中的内积$x_i·x_j$，从而将目标函数转变成

同样，我们还可以用核函数代替分类决策函数中的内积：

这个简单的替换等价于通过映射函数Φ将原来的输入空间变换到一个新的特征空间，将输入空间中的内积$x_i·x_j$变换为特征空间中的内积$Φ(x_i)·Φ(x_j)$，在新的特征空间里从训练样本中学习线性支持向量机。 当映射函数是非线性函数时，学习到的含有核函数的支持向量机就是非线性分类模型。

换句话说，给定核函数$K(x,z)$，我们就可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。模型的学习是在特征空间中隐式的进行的，不需要显式地定义特征空间和映射函数。这样的技巧我们就称之为核技巧，即利用线性分类学习方法与核函数解决非线性问题的技术。

在实际应用中，核函数的选取往往依赖领域知识直接选择，而它的有效性则需要通过实验验证。

正定核

我们知道，若已知映射函数Φ，我们可以通过求映射函数的内积得到核函数$K(x,z)$。那么，在不构造映射$Φ(x)$的情况下我们能否直接判断一个给定的函数$K(x,z)$是不是核函数呢？或者，函数$K(x,z)$应该满足什么条件才算是核函数？

我们通常所说的核函数就是正定核函数(positive definite kernel function)。

在讨论正定核之前，我们需要先接受一些预备知识：

先是回顾一下我们曾学习过的线性代数的一部分内容：

线性空间（或称向量空间）：该空间内的任意向量与该空间内的向量之和，以及该空间内的任意向量与任意标量的积的结果所得到的向量都在该空间内，则该空间为向量空间，这个性质又被称之为线性运算的封闭性，前者称为加法封闭，后者称为乘法封闭 例如：R²就是一个向量空间，它表示一个二维平面

假设$K(x,z)$是定义在$X*X$上的对称函数（简单一点说，设$f(x,y)$为对称函数，则$f(x,y)=f(y,x)$），并对任意的$x_1,...,x_m∈X$，$K(x,z)$关于$x_1,...,x_m$的Gram矩阵是半正定的。

（Gram矩阵简单的说就是由一族向量内积运算(在上面的叙述中就是K)构成其中各个元素的对称矩阵，它的元素$G_{ij}=(x_i,x_j)，(x_i,x_j)$表示$x_i与x_j$作内积运算）

这样，我们就可以根据函数$K(x,z)$构成一个希尔伯特空间（Hilbert space），其步骤是：

• 首先定义映射Φ并构成向量空间S；
• 然后在S上定义内积构成内积空间
• 最后将S完备化构成希尔伯特空间

下面我们详细讲解这3个步骤

1.定义映射，构成空间向量S

我们首先定义映射

根据这个映射，对任意的$x_i∈X，α_i∈R,i=1,...,m$ ，定义线性组合

我们定义集合S的元素这个线性组合组成，因此我们可以得到集合S对加法和乘法的运算封闭，从而得到S构成一个向量空间。

2.在S上定义内积，使其成为内积空间

我们在S上定义运算*：对任意$f,g∈S$

定义运算*

要证明*是空间S的内积，我们就需要证明下面四条式子：

（这四条其实就是判定一个运算是否是内积的条件）

其中1到3条的证明并不困难（根据步骤1和步骤2中的式子以及$K(x,z)$的对称性），我们直接看到第四条中式子(7.77)的证明：

由$f(·)=\sum^m_{i=1}α_iK(·,x_i)$与式子$f*g=\sum^m_{i=1}\sum^l_{j=1}α_iβ_jK(x_i,z_j)$可以得到：

由Gram矩阵的半正定性我们知道上式右端非负，从而得到$f·f≥0$。（利用半正定矩阵$x^TAx≥0$的性质）

我们再证式子（4）中的（7.78），充分性显然（这里指$f*f=0\leftarrow f=0$，即由右式推出左式，注意充分性针对命题，充分条件描述条件，两者是有区别的，详情参考充分性和必要性）

为了证明必要性，我们首先需要证明不等式：

为了证明这个不等式，我们设$f,g∈S,λ∈R$，则$f+λg∈S$（因为线性封闭），于是我们有：

如果们将λ看作一个变量，那么式子左端就可以看成是一个二次三项式（一元二次方程？），并且这个方程的值非负，并且我们知道它的判别式（Δ）小于等于0，即

（或许是 $(f*g)^2-4(f*f)(g*g)≤0$ ？不过对最终结果没有影响）

由此我们证明了上面给出的不等式。现在我们来证明若$f*f=0,则f=0$：

前面我们曾定义线性组合：

那么按照运算*的定义式$f*g=\sum^m_{i=1}\sum^l_{j=1}α_iβ_jK(x_i,z_j)$，对任意的$x∈X$，我们有：

于是，

又由我们已证明的不等式和$f*f≥0$可以得到

结合上面两个式子，我们可以得到

至此，我们就证明了当$f*f=0$时，对任意的x都有$\mid f(x)\mid =0$

于是我们便完成了*为向量空间S的内积的证明。赋予了内积定义的空间便是向量空间。

*既然是内积运算，那么我们就可以用符号“$·$”来代替原来的符号了，因此我们有，若

则

3.将内积空间S完备化为希尔伯特空间

内积空间准确的来说只能算准希尔伯特空间，为了让S能够成为完全的希尔伯特空间，我们还要将其完备化。

首先，由式子$f·g=\sum^m_{i=1}\sum^l_{j=1}α_iβ_jK(x_i,z_j)$定义的内积我们可以得到范数：

由此，我们得到S是一个赋范向量空间（如同加入了内积定义的向量空间就成为内积空间，赋予了向量“长度”概念的向量空间就是赋范向量空间，。根据泛函分析理论，对于不完备的赋范向量空间S，一定可以使之完备化，因而完备化后的S便是完备的赋范向量空间，而一个内积空间，如果作为一个赋范向量空间是完备的时候，就是一个希尔伯特空间了。

（一般来说，在一个内积空间中如果给定的内积$< x,y >$可以按照如上方式（$\mid\mid x\mid\mid=\sqrt{ < x,y > }$）导出一个范数（范数其实也可以算是“长度”，根据范数的定义，范数必须具有非负性、齐次性、三角不等性三条性质），并且空间对于这个范数是完备的，那么这个空间就可以称为是一个希尔伯特空间。另外，完备性指的就是任何一个柯西序列都收敛到此空间中的某个元素，即它们与某个元素的范数差的极限为0）

（还是再简单备注一下柯西序列，假设$\{x_1,...,x_n\}$ (n或许应该趋向于正无穷) 为某欧式空间中的点组成的序列，如果对于任意的$ε > 0$，存在自然数N,当$m,n > N$时，$\mid x_m-x_n\mid < ε$,则称序列$\{x_1,...,x_n\}$为一个柯西序列，通俗地说，就是这个序列它的元素随着序数的增加而愈发靠近）

回到正题，这个由S生成的希尔伯特空间 H 称为再生希尔伯特核空间（reproducing kernel Hilbert space,RKHS）。这是因为其核K具有再生性，即满足条件：

和

我们就称其为再生核。

4.正定核的充要条件

定理（正定核的充要条件）

假设$K:X*X\rightarrow R$是对称函数，则$K(x,z)$是正定核函数的充要条件是对任意$x_i∈X,i=1,...,m$，$K(x,z)$对应的Gram矩阵：

是半正定矩阵。

证明

首先证明必要性（若K是正定核函数则Gram矩阵必须半正定）：

由于$K(x,z)$是$X*X$上的正定核，所以，存在从X到希尔伯特空间H的映射Φ，使得

因此，对任意$x_1,...,x_m$，构造$K(x,z)$关于这一族向量的Gram矩阵

而对任意$c_1,...,c_m∈R$（这里c显然是标量），有

表明$K(x,z)$关于$x_1,...,x_m$的Gram矩阵是半正定的。

接着我们证明充分性：

已知对称函数$K(x,z)$对任意$x_1,...,x_m∈X$，$K$关于该族向量的Gram矩阵是半正定的。

根据前面的结果，对给定的$K(x,z)$我们可以构造从X到某个希尔伯特空间H的映射：

由核K的再生性我们有：

与

再由映射的式子我们得到

这个式子表明K是$X*X$上的核函数。

由此我们就得到了正定核的充要条件，换句话说，我们也可以用这个条件来判断函数K是否是正定核。

通过Gram矩阵是否半正定来判断核是否正定核这一方法在构造核函数的时候相当有用，但在实际操作中，对于一个具体的函数$K(x,z)$来说，对任意有限输入集$\{x_1,...,x_m\}$检验K对应的Gram矩阵是否正定是相当困难的，因此，我们常常用已有的核函数来解决实际中遇到的问题。

常用核函数

多项式核函数

ploynomial kernel function

对应的支持向量机是一个p次多项式分类器，其分类决策函数为

高斯函数

Gaussian kernel function

对应高斯径向基函数分类器（radial basis function），分类决策函数：

字符串核函数

string kernel function

核函数不仅可以定义在欧式空间上，还可以定义在离散数据几何上。我们这里举得这个字符串核就是定义在字符串集合上的核函数。它的用处很广泛，包括文本分类、信息检索、生物信息学等等等等。

假设我们有一个有限字符表Σ，字符串s是从Σ中取出的有限个字符串的序列，包括空字符串。我们用$\mid s\mid$来表示字符串的长度，并将它的元素记为$s(1)s(2)...s(\mid s\mid)$。字符串s和t的连接就记作$st$。所有长度为n的字符串的集合记作$Σ^n$，所有字符串的集合记作$Σ^{*}=\bigcup^\infty_{n=0}Σ^n$。

考虑字符串s的子串u，给定一个指标序列$i=(i_1,...,i_{\mid u\mid}),1≤i_1 < i_2 < ... < i_{\mid u\mid}≤\mid s\mid$。然后我们将s的子串u定义为$u=s(i)=s(i_1)...s(i_{\mid u\mid})$并将其长度记为$l(i)=i_{\mid u\mid}-i_1+1$。如果序列i是连续的，那么就有$l(i)=\mid u\mid$；否则$l(i) > \mid u\mid$

我们再假设S是长度大于或等于 n字符串 的集合，s是S的元素。现在我们就可以建立字符串集合S到特征空间$H_n=R^{Σ^n}$的映射$Φ_n(s)$了。$R^{Σ^n}$表示的是定义在$Σ^n$上的实数空间，其每一维对应一个字符串$u∈Σ^n$，映射$Φ_n(s)$将字符串s对应于空间$R^{Σ^n}$的一个向量，其在u维上的取值为

在这个式子中$0 < λ ≤1$是一个衰减参数，$l(i)$表示字符串i的长度，求和在s中所有与u相同的子串上进行。

现在来举个例子，假设Σ为英文字符集，n为3，S为长度大于或等于3的字符串集合。考虑将字符集S映射到特征空间$H_3$。设$H_3$的一维对应于字符串asd。这时字符串“Nasdaq”和“lass dass”在这一维上的值便分别是$[Φ_3(Nasdaq)]_{asd}=λ^3$和$[Φ_3(lass~das)]_{asd}=2λ^5$。第两个式子表示，在第一个字符串里，asd是连续的子串；在第二个字符串里，asd是长度为5的不连续字串，共出现两次。

两个字符串s和t上的字符串核函数是基于映射$Φ_n$的特征空间中的内积：

字符串核函数$k_n(s,t)$给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度（cosine similarity）。直观上看，两个字符串相同的子串越多，它们就越相似，字符串核函数的值就越大。

字符串核函数可以由动态规划快速地计算。

（这部分涉及的内容我们将在以后进行讨论，目前只是简单的了解一下）

非线性支持向量分类机

到目前为止，我们知道，要用支持向量机解决非线性分类问题，我们只需要将线性支持向量机对偶形式中的内积换成核函数即可。

于是我们就有了非线性支持向量机的定义：

非线性支持向量机定义

从非线性分类训练集中，通过核函数与软间隔最大化或凸二次规划学习得到的分类决策函数：

称为非线性支持向量，$K(x,z)$是正定核函数。

非线性支持向量机的算法

输入：训练集T （$x_i∈R^n$,$y_i=\{+1,-1\},i=1,...,N$）

输出：分类决策函数

步骤：

1.选取适当的核函数和适当的参数C，构造并求解最优化问题

求得最优解$α^*=(α^*_1,α^*_2,...,α^*_N)^T$

2.选择$α^*$的一个正分量$0 < α^*_j < C$，计算

3.构造决策函数

当$K(x,z)$是正定核函数时，该最优化问题是凸二次规划问题，解是存在的。