核方法

核技巧

非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。如图 111 所示，“●”表示正样本，“×”表示负样本，显然无法用直线（线性模型）将正负样本正确分开，但是可以用一条椭圆曲线（非线性模型）将它们分开。

一般来说，对给定的一个训练数据集 D={(x1,y1),(x2,y2),…,(xn,yn)}D=\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}D={(x1​,y1​),(x2​,y2​),…,(xn​,yn​)}，其中，样本 xix_ixi​ 属于输入空间，xi∈X=Rdx_i\in\mathcal{X}=\mathbb R^dxi​∈X=Rd，对应的标签有两类 yi∈Y={−1,+1}y_i\in \mathcal{Y}=\{-1,+1\}yi​∈Y={−1,+1}，i=1,2,…,ni=1,2,\dots,ni=1,2,…,n。如果能用 Rd\mathbb R^dRd 中的一个超曲面将正负样本正确分开，则称这个问题为非线性可分问题。

图 1    非线性分类问题与核技巧示例

非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。对图 111 所示的例子，通过变换，将左图中椭圆变换成右图中的直线，将非线性分类问题变换为线性分类问题。

设原空间为 X⊂R2\mathcal X\subset \mathbb R^2X⊂R2，x=(x(1),x(2))T∈Xx=(x^{(1)},x^{(2)})^T\in \mathcal Xx=(x(1),x(2))T∈X，新空间为 Z⊂R2\mathcal Z\subset\mathbb R^2Z⊂R2，z=(z(1),z(2))T∈Zz=(z^{(1)},z^{(2)})^T\in \mathcal Zz=(z(1),z(2))T∈Z，定义从原空间到新空间的变换（映射）：
z=ϕ(x)=(ϕ1(x(1)),ϕ2(x(2)))T=((x(1))2,(x(2))2)Tz = \phi(x) = \big(\phi_1(x^{(1)}),\phi_2(x^{(2)})\big)^T = \big((x^{(1)})^2,(x^{(2)})^2\big)^T z=ϕ(x)=(ϕ1​(x(1)),ϕ2​(x(2)))T=((x(1))2,(x(2))2)T
经过变换 z=ϕ(x)z=\phi(x)z=ϕ(x)，原空间 X⊂R2\mathcal X\subset \mathbb R^2X⊂R2 变换为新空间 Z⊂R2\mathcal Z\subset\mathbb R^2Z⊂R2，原空间中的点相应地变换为新空间中的点，原空间中的椭圆
w1(x(1))2+w2(x(2))2+b=0w_1(x^{(1)})^2+w_2(x^{(2)})^2+b=0 w1​(x(1))2+w2​(x(2))2+b=0
变换成为新空间中的直线
w1z(1)+w2z(2)+b=0w_1z^{(1)}+w_2z^{(2)}+b=0 w1​z(1)+w2​z(2)+b=0
在变换后的新空间里，直线 w1z(1)+w2z(2)+b=0w_1z^{(1)}+w_2z^{(2)}+b=0w1​z(1)+w2​z(2)+b=0 可以将变换后的正负样本正确分开。这样，原空间的非线性可分问题就变成了新空间的线性可分问题。

上面的例子说明，用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。

核函数

设 X\mathcal XX 是输入空间（欧氏空间 Rd\mathbb R^dRd 的子集或离散集合），又设 H\mathcal HH 为特征空间（希尔伯特空间，Hilbert space），如果存在一个从 X\mathcal XX 到 H\mathcal HH 的映射
ϕ(x):X→H\phi(x):\mathcal X\to \mathcal H ϕ(x):X→H
使得对所有 x,z∈Xx,z\in \mathcal Xx,z∈X，函数 K(x,z)K(x,z)K(x,z) 满足条件
K(x,z)=ϕ(x)Tϕ(z)(1)K(x, z) = \phi(x)^T\phi(z) \tag{1} K(x,z)=ϕ(x)Tϕ(z)(1)
则称 K(x,z)K(x,z)K(x,z) 为核函数，ϕ(x)\phi(x)ϕ(x) 为映射函数，式中 ϕ(x)Tϕ(z)\phi(x)^T \phi(z)ϕ(x)Tϕ(z) 为 ϕ(x)\phi(x)ϕ(x) 和 ϕ(z)\phi(z)ϕ(z) 的内积。

注意，ϕ\phiϕ 是输入空间 Rd\mathbb R^dRd 到特征空间 H\mathcal HH 的映射，特征空间 H\mathcal HH 一般是高维的，甚至是无穷维的。对于给定的核 K(x,z)K(x,z)K(x,z)，特征空间 H\mathcal HH 和映射函数 ϕ\phiϕ 的取法不唯一，可以取不同的特征空间，即便是在同一特征空间里也可以取不同的映射。举一个简单的例子来说明核函数和映射函数的关系。

例：假设输入空间是 R2\mathbb R^2R2，核函数是 K(x,z)=(xTz)2K(x,z)=(x^Tz)^2K(x,z)=(xTz)2，我们可以找到许多满足条件的特征空间 H\mathcal HH 和映射 ϕ(x):R2→H\phi(x):\mathbb R^2\to \mathcal Hϕ(x):R2→H。

取特征空间 H=R3\mathcal H=\mathbb R^3H=R3，记 x=(x(1),x(2))Tx=(x^{(1)},x^{(2)})^Tx=(x(1),x(2))T，z=(z(1),z(2))Tz=(z^{(1)},z^{(2)})^Tz=(z(1),z(2))T，由于
(xTz)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^Tz)^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 (xTz)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)=\big( (x^{(1)})^2,\sqrt{2}x^{(1)}x^{(2)},(x^{(2)})^2 \big)^T ϕ(x)=((x(1))2,2​x(1)x(2),(x(2))2)T
容易验证 ϕ(x)Tϕ(z)=(xTz)2=K(x,z)\phi(x)^T\phi(z)=(x^Tz)^2=K(x,z)ϕ(x)Tϕ(z)=(xTz)2=K(x,z)。

仍取 H=R3\mathcal H=\mathbb R^3H=R3 以及
ϕ(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}} \big( (x^{(1)})^2 - (x^{(2)})^2,2x^{(1)}x^{(2)},(x^{(1)})^2+(x^{(2)})^2 \big)^T ϕ(x)=2​1​((x(1))2−(x(2))2,2x(1)x(2),(x(1))2+(x(2))2)T
同样有 ϕ(x)Tϕ(z)=(xTz)2=K(x,z)\phi(x)^T\phi(z) = (x^Tz)^2 = K(x,z)ϕ(x)Tϕ(z)=(xTz)2=K(x,z)。

还可以取 H=R4\mathcal H =\mathbb R^4H=R4 和
ϕ(x)=((x(1))2,x(1)x(2),x(1)x(2),(x(2))2)T\phi(x) = \big( (x^{(1)})^2, x^{(1)}x^{(2)}, x^{(1)}x^{(2)} ,(x^{(2)})^2 \big)^T ϕ(x)=((x(1))2,x(1)x(2),x(1)x(2),(x(2))2)T
通过上面的例子注意到，假设特征空间 H=Rm\mathcal H=\mathbb R^mH=Rm，那么映射函数 ϕ(x)\phi(x)ϕ(x) 其实可以更完整地表示为
ϕ(x)=(ϕ1(x),ϕ2(x),…,ϕm(x))T\phi(x) = \big( \phi_1(x), \phi_2(x),\dots, \phi_m(x) \big) ^T ϕ(x)=(ϕ1​(x),ϕ2​(x),…,ϕm​(x))T
其中 ϕi(x)\phi_i(x)ϕi​(x) 为基函数。对应的核函数表示为
K(x,z)=ϕ(x)Tϕ(z)=∑i=1mϕi(x)ϕi(z)K(x, z) = \phi(x)^T\phi(z) = \sum_{i=1}^m\phi_i(x)\phi_i(z) K(x,z)=ϕ(x)Tϕ(z)=i=1∑m​ϕi​(x)ϕi​(z)
图 222 所示为从对应的基函数集合构建核函数的例⼦。在每⼀列中，下面三幅图给出了由上式定义的核函数 K(x,z)K(x,z)K(x,z)，它是关于 xxx 的函数，zzz 的值在图中用红叉表示。上面三幅图给出了对应的基函数分别是多项式基函数 （左列）、⾼斯基函数（中列）、logistic sigmoid基函数（右列）。

图 2    从对应的基函数集合构建核函数的示例

上面对于核函数的定义指明了其用途，即不仅可以实现从输入空间到特征空间的非线性映射，而且可以简化映射函数的内积运算，这为在支持向量机等算法中使用核函数提供了可能。实际上，在学习与预测中，我们只定义核函数 K(x,z)K(x,z)K(x,z) 而不显式地定义映射函数 ϕ\phiϕ，这是因为，通过每个样本的 ϕ\phiϕ 值来计算 K(x,z)K(x,z)K(x,z) 会使得计算变得非常复杂。可见，核函数的定义仅说明了在出现内积时可以使用核函数，但是并未介绍如何检验一个函数是否为核函数，如何构造一个复杂的核函数。

正定核

已知映射函数 ϕ\phiϕ，可以通过 ϕ(x)\phi(x)ϕ(x) 和 ϕ(z)\phi(z)ϕ(z) 的内积求得核函数 K(x,z)K(x , z)K(x,z)。不用构造映射 ϕ(x)\phi(x)ϕ(x) 能否直接判断一个给定的函数 K(x,z)K(x,z)K(x,z) 是不是核函数？或者说，函数 K(x,z)K(x,z)K(x,z) 满足什么条件才能成为核函数？

通常所说的核函数就是正定核函数（positive definite kernel function) 。设 K:X×X→RK:\mathcal X\times \mathcal X\to \mathbb RK:X×X→R 是对称函数，则 K(x,z)K(x,z)K(x,z) 为正定核函数的充要条件是，对于任意 mmm，取任意 xi∈Xx_i\in \mathcal Xxi​∈X，i=1,2,…,mi=1,2,\dots, mi=1,2,…,m，K(x,z)K(x,z)K(x,z) 对应的 Gram\rm GramGram 矩阵：
K=[K(xi,xj)]m×mK = [K(x_i,x_j)]_{m\times m} K=[K(xi​,xj​)]m×m​
是半正定的。

简而言之，一个函数具有对称性，并且对应的 Gram\rm GramGram 矩阵为半正定矩阵，那么可以认为其为正定核函数。下面证明充分必要性。

必要性证明

已知 K(x,z)K(x,z)K(x,z) 为核函数，即式 (1)(1)(1)，证明 K(x,z)K(x,z)K(x,z) 具有对称性，并且对应的 Gram\rm GramGram 矩阵 KKK 为半正定矩阵。

由于内积运算具有对称性，显然式 (1)(1)(1) 也具有对称性。

我们利用矩阵半正定的充要条件“∀α∈Rm\forall \alpha\in \mathbb R^m∀α∈Rm，αTKα≥0\alpha^TK\alpha\ge 0αTKα≥0”。令 Kij=K(xi,xj)K_{ij}=K(x_i,x_j)Kij​=K(xi​,xj​)，则

αTKα=(α1α2…αm)(K11K12…K1mK21K22…K2m⋮⋮⋮Km1Km2…Kmm)(α1α2⋮αm)=∑i=1m∑j=1mαiKijαj=∑i=1m∑j=1mαiαjKij=∑i=1m∑j=1mαiαjϕ(xi)Tϕ(xj)=∑i=1mαiϕ(xi)T∑j=1mαjϕ(xj)=(∑i=1mαiϕ(xi))T(∑j=1mαjϕ(xj))=∣∣∑i=1mαiϕ(xi)∣∣2≥0\begin{aligned} \alpha^TK\alpha &= (\begin{matrix}\alpha_1&\alpha_2& \dots & \alpha_m\end{matrix})\left( \begin{matrix} K_{11} & K_{12} & \dots & K_{1m}\\ K_{21} & K_{22} &\dots & K_{2m} \\ \vdots & \vdots & & \vdots \\ K_{m1} & K_{m2} & \dots & K_{mm} \end{matrix}\right)\left( \begin{matrix} \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_m \end{matrix} \right) \\ &=\sum_{i=1}^m\sum_{j=1}^m\alpha_i K_{ij} \alpha_j \\ &=\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j K_{ij} \\ &=\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j \phi(x_i)^T\phi(x_j) \\ &=\sum_{i=1}^m\alpha_i \phi(x_i)^T \sum_{j=1}^m \alpha_j \phi(x_j) \\ &=\Big(\sum_{i=1}^m\alpha_i \phi(x_i)\Big)^T \Big(\sum_{j=1}^m \alpha_j \phi(x_j)\Big) \\ &=\left|\left|\sum_{i=1}^m\alpha_i \phi(x_i)\right|\right|^2 \\ &\ge 0 \end{aligned} αTKα​=(α1​​α2​​…​αm​​)⎝⎜⎜⎜⎛​K11​K21​⋮Km1​​K12​K22​⋮Km2​​………​K1m​K2m​⋮Kmm​​⎠⎟⎟⎟⎞​⎝⎜⎜⎜⎛​α1​α2​⋮αm​​⎠⎟⎟⎟⎞​=i=1∑m​j=1∑m​αi​Kij​αj​=i=1∑m​j=1∑m​αi​αj​Kij​=i=1∑m​j=1∑m​αi​αj​ϕ(xi​)Tϕ(xj​)=i=1∑m​αi​ϕ(xi​)Tj=1∑m​αj​ϕ(xj​)=(i=1∑m​αi​ϕ(xi​))T(j=1∑m​αj​ϕ(xj​))=∣∣∣∣∣​∣∣∣∣∣​i=1∑m​αi​ϕ(xi​)∣∣∣∣∣​∣∣∣∣∣​2≥0​

其中 ∑i=1mαiϕ(xi)\sum\limits_{i=1}^m\alpha_i \phi(x_i)i=1∑m​αi​ϕ(xi​) 为向量的线性组合。可见，Gram\rm GramGram 矩阵 KKK 为半正定矩阵，必要性证毕。

充分性证明

已知函数 K(x,z)K(x,z)K(x,z) 对应的 Gram\rm GramGram 矩阵 KKK 为半正定矩阵，证明 K(x,z)K(x,z)K(x,z) 为核函数。

根据半正定矩阵性质，可以对 KKK 进行特征值分解
K=vΛvTK = v\Lambda v^T K=vΛvT
其中，Λ=diag(λ1,λ2,…,λm)\Lambda = {\rm diag(\lambda_1,\lambda_2,\dots,\lambda_m)}Λ=diag(λ1​,λ2​,…,λm​) 为特征值矩阵，v=(v1v2…vm)v=\left(\begin{matrix}v_1&v_2&\dots & v_m\end{matrix}\right)v=(v1​​v2​​…​vm​​)，viv_ivi​ 为特征值 λi\lambda_iλi​ 对应的特征向量，特征向量 viv_ivi​ 可以详细表示为 vi=(vi1vi2…vim)Tv_i=\left(\begin{matrix}v_{i1}&v_{i2}&\dots & v_{im}\end{matrix}\right)^Tvi​=(vi1​​vi2​​…​vim​​)T，vijv_{ij}vij​ 表示特征向量 viv_ivi​ 的第 jjj 个分量。可见，vvv 是个 mmm 阶单位方阵，Λ\LambdaΛ 为半正定对角阵。

将 K=vΛvTK = v\Lambda v^TK=vΛvT 展开

K=vΛvT=(v1v2…vm)(λ1λ2⋱λm)(v1Tv2T⋮vmT)=(v11v21…vm1v12v22…vm2⋮⋮⋮v1mv2m…vmm)(λ1λ2⋱λm)(v11v12…v1mv21v22…v2m⋮⋮⋮vm1vm2…vmm)=(λ1v11λ2v21…λmvm1λ1v12λ2v22…λmvm2⋮⋮⋮λ1v1mλ2v2m…λmvmm)(v11v12…v1mv21v22…v2m⋮⋮⋮vm1vm2…vmm)=(∑i=1mλivi1vi1∑i=1mλivi1vi2…∑i=1mλivi1vim∑i=1mλivi2vi1∑i=1mλivi2vi2…∑i=1mλivi2vim⋮⋮⋮∑i=1mλivimvi1∑i=1mλivimvi2…∑i=1mλivimvim)\begin{aligned} K &= v\Lambda v^T \\ & = (\begin{matrix}v_{1}&v_2& \dots & v_m\end{matrix})\left(\begin{matrix}\lambda_1& & & \\ &\lambda_2& & \\ && \ddots &\\&&&\lambda_m\\\end{matrix}\right)\left(\begin{matrix}v_1^T\\v_2^T\\ \vdots \\ v_m^T\end{matrix}\right)\\ &= \left(\begin{matrix}v_{11}&v_{21}& \dots & v_{m1} \\ v_{12}&v_{22}& \dots & v_{m2} \\ \vdots & \vdots & & \vdots \\ v_{1m}&v_{2m}& \dots & v_{mm} \end{matrix}\right) \left(\begin{matrix}\lambda_1& & & \\ &\lambda_2& & \\ && \ddots &\\&&&\lambda_m\\\end{matrix}\right) \left(\begin{matrix}v_{11}&v_{12}& \dots & v_{1m} \\ v_{21}&v_{22}& \dots & v_{2m} \\ \vdots & \vdots & & \vdots \\ v_{m1}&v_{m2}& \dots & v_{mm} \end{matrix}\right) \\ &=\left(\begin{matrix}\lambda_1v_{11}&\lambda_2v_{21}& \dots & \lambda_mv_{m1} \\ \lambda_1v_{12}& \lambda_2v_{22}& \dots &\lambda_m v_{m2} \\ \vdots & \vdots & & \vdots \\\lambda_1 v_{1m}& \lambda_2v_{2m}& \dots & \lambda_m v_{mm} \end{matrix}\right) \left(\begin{matrix}v_{11}&v_{12}& \dots & v_{1m} \\ v_{21}&v_{22}& \dots & v_{2m} \\ \vdots & \vdots & & \vdots \\ v_{m1}&v_{m2}& \dots & v_{mm} \end{matrix}\right) \\ &= \left(\begin{matrix}\sum\limits_{i=1}^m\lambda_iv_{i1}v_{i1} & \sum\limits_{i=1}^m \lambda_iv_{i1}v_{i2} & \dots & \sum\limits_{i=1}^m\lambda_iv_{i1}v_{im} \\ \sum\limits_{i=1}^m\lambda_iv_{i2}v_{i1} & \sum\limits_{i=1}^m \lambda_iv_{i2}v_{i2} & \dots & \sum\limits_{i=1}^m\lambda_iv_{i2}v_{im} \\ \vdots & \vdots & & \vdots \\\sum\limits_{i=1}^m\lambda_iv_{im}v_{i1} & \sum\limits_{i=1}^m \lambda_iv_{im}v_{i2} & \dots & \sum\limits_{i=1}^m\lambda_iv_{im}v_{im} \\ \end{matrix}\right)\\ \end{aligned} K​=vΛvT=(v1​​v2​​…​vm​​)⎝⎜⎜⎛​λ1​​λ2​​⋱​λm​​⎠⎟⎟⎞​⎝⎜⎜⎜⎛​v1T​v2T​⋮vmT​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​v11​v12​⋮v1m​​v21​v22​⋮v2m​​………​vm1​vm2​⋮vmm​​⎠⎟⎟⎟⎞​⎝⎜⎜⎛​λ1​​λ2​​⋱​λm​​⎠⎟⎟⎞​⎝⎜⎜⎜⎛​v11​v21​⋮vm1​​v12​v22​⋮vm2​​………​v1m​v2m​⋮vmm​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​λ1​v11​λ1​v12​⋮λ1​v1m​​λ2​v21​λ2​v22​⋮λ2​v2m​​………​λm​vm1​λm​vm2​⋮λm​vmm​​⎠⎟⎟⎟⎞​⎝⎜⎜⎜⎛​v11​v21​⋮vm1​​v12​v22​⋮vm2​​………​v1m​v2m​⋮vmm​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎛​i=1∑m​λi​vi1​vi1​i=1∑m​λi​vi2​vi1​⋮i=1∑m​λi​vim​vi1​​i=1∑m​λi​vi1​vi2​i=1∑m​λi​vi2​vi2​⋮i=1∑m​λi​vim​vi2​​………​i=1∑m​λi​vi1​vim​i=1∑m​λi​vi2​vim​⋮i=1∑m​λi​vim​vim​​⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞​​

因此

Kij=K(xi,xj)=∑k=1mλkvkivkj=∑k=1mλkvkiλkvkj=∑k=1m(λkvki)(λkvkj)=(λ1v1iλ2v2i…λmvmi)(λ1v1jλ2v2j⋮λmvmj)\begin{aligned} K_{ij} = K(x_i,x_j) &= \sum_{k=1}^m\lambda_k v_{ki}v_{kj} \\ &= \sum_{k=1}^m \sqrt{\lambda_k} v_{ki} \sqrt{\lambda_k}v_{kj} \\ &=\sum_{k=1}^m \left( \sqrt{\lambda_k} v_{ki} \right) \left( \sqrt{\lambda_k}v_{kj} \right)\\ &= (\begin{matrix} \sqrt{\lambda_1} v_{1i} & \sqrt{\lambda_2} v_{2i}& \dots & \sqrt{\lambda_m}v_{mi}\end{matrix}) \left(\begin{matrix} \sqrt{\lambda_1} v_{1j} \\ \sqrt{\lambda_2} v_{2j}\\ \vdots \\ \sqrt{\lambda_m}v_{mj}\end{matrix} \right)\\ \end{aligned} Kij​=K(xi​,xj​)​=k=1∑m​λk​vki​vkj​=k=1∑m​λk​​vki​λk​​vkj​=k=1∑m​(λk​​vki​)(λk​​vkj​)=(λ1​​v1i​​λ2​​v2i​​…​λm​​vmi​​)⎝⎜⎜⎜⎛​λ1​​v1j​λ2​​v2j​⋮λm​​vmj​​⎠⎟⎟⎟⎞​​

令 ui=(λ1v1iλ2v2i…λmvmi)Tu_i = (\begin{matrix} \sqrt{\lambda_1} v_{1i} & \sqrt{\lambda_2} v_{2i}& \dots & \sqrt{\lambda_m}v_{mi}\end{matrix}) ^Tui​=(λ1​​v1i​​λ2​​v2i​​…​λm​​vmi​​)T，则

K(xi,xj)=uiTui\begin{aligned} K(x_i,x_j) = u_i^Tu_i \end{aligned} K(xi​,xj​)=uiT​ui​​

令 ϕ(xi)=ui\phi(x_i) = u_iϕ(xi​)=ui​，ϕ(xj)=uj\phi(x_j) = u_jϕ(xj​)=uj​，则

K(xi,xj)=ϕ(xi)Tϕ(xj)K(x_i,x_j) = \phi(x_i)^T\phi(x_j) K(xi​,xj​)=ϕ(xi​)Tϕ(xj​)

充分性证毕。

另外，观察充分性证明部分，ϕ(⋅)\phi(·)ϕ(⋅) 为 mmm 维向量，即与构成 Gram\rm GramGram 矩阵所选取向量 x∈Xx\in \mathcal Xx∈X 的个数有关。选取 mmm 个向量构成 m×mm\times mm×m 维 Gram\rm GramGram 矩阵，因为输入空间 X\mathcal XX 中的向量可以有无穷多个，所以当 mmm 趋于无穷时， Gram\rm GramGram 矩阵趋于无穷阶，由 ϕ(⋅)\phi(·)ϕ(⋅) 映射得到的特征空间也就是无穷维。

根据核函数的定义我们可以知道，核函数必然可以找到至少一个映射函数实现从输入空间映射到希尔伯特空间，根据核函数构造一个希尔伯特空间的具体步骤见附录。

构造新的核函数的一个强大⽅法是使⽤简单的核函数作为基本的模块来构造。可以使⽤下⾯的性质来完成这件事。假设 K1(x,z)K_1(x,z)K1​(x,z) 和 K2(x,z)K_2(x,z)K2​(x,z) 为合法核函数，那么下面的新核也是合法的

K(x,z)=cK1(x,z)(2~1)K(x,z)=f(x)K1(x,z)f(z)(2~2)K(x,z)=q(K1(x,z))(2~3)K(x,z)=exp⁡(K1(x,z))(2~4)K(x,z)=K1(x,z)+K2(x,z)(2~5)K(x,z)=K1(x,z)K2(x,z)(2~6)K(x,z)=K3(ϕ(x),ϕ(z))(2~7)K(x,z)=xTAz(2~8)K(x,z)=Ka(xa,za)+Kb(xb,zb)(2~9)K(x,z)=Ka(xa,za)Kb(xb,zb)(2~10)\begin{aligned} K(x,z) &= cK_1(x,z)& &&&&&{(2\text{\textasciitilde}1)} \\ K(x,z) &=f(x) K_1(x,z)f(z) &&&&&&{(2\text{\textasciitilde}2)} \\ K(x,z) &=q(K_1(x,z)) &&&&&&{(2\text{\textasciitilde}3)} \\ K(x,z) &= \exp(K_1(x,z)) &&&&&& {(2\text{\textasciitilde}4)} \\ K(x,z) &= K_1(x,z)+K_2(x,z) &&&&&& {(2\text{\textasciitilde}5)} \\ K(x,z) &= K_1(x,z)K_2(x,z) &&&&&&{(2\text{\textasciitilde}6)} \\ K(x,z) &= K_3(\phi(x), \phi(z)) &&&&&&{(2\text{\textasciitilde}7)} \\ K(x,z) &= x^TAz &&&&&&{(2\text{\textasciitilde}8)} \\ K(x,z) &= K_a(x_a,z_a) + K_b(x_b,z_b) &&&&&& {(2\text{\textasciitilde}9)} \\ K(x,z) &= K_a(x_a,z_a) K_b(x_b,z_b) &&&&&& {(2\text{\textasciitilde}10)} \\ \end{aligned} K(x,z)K(x,z)K(x,z)K(x,z)K(x,z)K(x,z)K(x,z)K(x,z)K(x,z)K(x,z)​=cK1​(x,z)=f(x)K1​(x,z)f(z)=q(K1​(x,z))=exp(K1​(x,z))=K1​(x,z)+K2​(x,z)=K1​(x,z)K2​(x,z)=K3​(ϕ(x),ϕ(z))=xTAz=Ka​(xa​,za​)+Kb​(xb​,zb​)=Ka​(xa​,za​)Kb​(xb​,zb​)​​​​​​(2~1)(2~2)(2~3)(2~4)(2~5)(2~6)(2~7)(2~8)(2~9)(2~10)​

其中，c>0c>0c>0 是一个常数，f(⋅)f(·)f(⋅) 是任意函数，q(⋅)q(·)q(⋅) 是一个系数非负的多项式，ϕ(x)\phi(x)ϕ(x) 是一个从 xxx 到 Rm\mathbb R^mRm 的映射函数，K3(⋅,⋅)K_3(·,·)K3​(⋅,⋅) 是 Rm\mathbb R ^mRm 中的一个合法核，AAA 是一个对称半正定矩阵，xax_axa​ 和 xbx_bxb​ 是变量（未必互斥），且 x=(xa,xb)x=(x_a,x_b)x=(xa​,xb​)。KaK_aKa​ 和 KbK_bKb​ 是各自空间的合法核函数。

通过考虑式 (1)(1)(1) 中的特征空间的恒等映射 ϕ(x)=x\phi(x)=xϕ(x)=x，可以得到核函数的一个最简单例子，此时 K(x,z)=xTzK(x,z) = x^TzK(x,z)=xTz，我们称之为线性核。 基于线性核，我们可以构造出一个经常使用的核函数
K(x,z)=exp⁡(−∣∣x−z∣∣22σ2)K(x,z) = \exp(-\frac{||x-z||^2}{2\sigma^2}) K(x,z)=exp(−2σ2∣∣x−z∣∣2​)
这个被称为高斯核，亦称径向基函数核。但是注意，在现在的讨论中，它不表示概率密度，因此归⼀化系数被省略了。所谓径向基函数，它仅依赖于参数之间的距离（通常是欧氏距离）的大小，即 K(x,z)=K(∣∣x−z∣∣)K(x,z) = K(||x-z||)K(x,z)=K(∣∣x−z∣∣)。虽然它的名字包括基函数，但是我们不能将其完全理解为基函数 ϕi\phi_iϕi​，可以认为是一种思想或者复合函数中的内函数。

之所以高斯核是个合法核，是因为高斯核函数本质上是通过 (2~1)∼(2~10)(2\text{\textasciitilde}1)\sim(2\text{\textasciitilde}10)(2~1)∼(2~10) 中的公式对线性核进行组合构造而来的，理由如下。将平方项展开
∣∣x−z∣∣2=xTx+zTz−2xTz||x-z||^2 = x^Tx+z^Tz -2x^Tz ∣∣x−z∣∣2=xTx+zTz−2xTz
从而
K(x,z)=exp⁡(−xTx2σ2)exp⁡(xTzσ2)exp⁡(−zTz2σ2)K(x,z) = \exp(-\frac{x^Tx}{2\sigma^2}) \exp(\frac{x^Tz}{\sigma^2}) \exp(-\frac{z^Tz}{2\sigma^2}) K(x,z)=exp(−2σ2xTx​)exp(σ2xTz​)exp(−2σ2zTz​)
然后使⽤公式 (2~2)(2\text{\textasciitilde}2)(2~2) 和公式 (2~4)(2\text{\textasciitilde}4)(2~4)，以及线性核的合法性，即可看到⾼斯核是⼀个合法的核。

下面列出了几种常用的核函数。

字符串核函数

核函数不仅可以定义在欧氏空间上，还可以定义在离散数据的集合上。比如，字符串核是定义在字符串集合上的核函数。字符串核函数在文本分类、信息检索、生物信息学等方面都有应用。

考虑一个有限字符表 Σ\SigmaΣ。字符串 sss 是从 Σ\SigmaΣ 中取出的有限个字符的序列，包括空字符串。字符串 sss 的长度用 ∣s∣\vert s \vert∣s∣ 表示，它的元素记作 s(1)s(2)…s(∣s∣)s(1)s(2)\dots s(|s|)s(1)s(2)…s(∣s∣)。两个字符串 sss 和 ttt 的连接记为 ststst。所有长度为 nnn 的字符串的集合记作 Σn\Sigma^nΣn，所有字符串的集合记作 Σ∗=⋃n=0∞Σn\Sigma^*=\bigcup\limits_{n=0}^∞\Sigma^nΣ∗=n=0⋃∞​Σn。

考虑字符串 sss 的子串 uuu。给定一个指标序列 i=(i1,i2,…,i∣u∣)i=(i_1,i_2,\dots,i_{|u|})i=(i1​,i2​,…,i∣u∣​)，1≤i1∣u∣l(i)>|u|l(i)>∣u∣。举个例子，假设 s=abcdefs= \rm abcdefs=abcdef，分别取两个子串 u=abcu=\rm abcu=abc 和 v=aefv=\rm aefv=aef，那么 uuu 对应的指标序列为 iu=(1,2,3)i_u = (1,2,3)iu​=(1,2,3)，vvv 对应的指标序列为 iv=(1,5,6)i_v = (1,5,6)iv​=(1,5,6)，uuu 对应的长度 l(iu)=3−1+1=3l(i_u) = 3-1+1=3l(iu​)=3−1+1=3，vvv 对应的长度 l(iv)=6−1+1=6l(i_v) = 6-1+1 = 6l(iv​)=6−1+1=6。

假设 S\mathcal SS 是长度大于或等于 nnn 的字符串的集合，sss 是 S\mathcal SS 的元素。现在建立字符串集合 S\mathcal SS 到特征空间 Hn=RΣn\mathcal H_n = \mathbb R^{\Sigma^n}Hn​=RΣn 的映射 ϕn(s)\phi_n(s)ϕn​(s)。RΣn\mathbb R^{\Sigma^n}RΣn 表示定义在 Σn\Sigma^nΣn 上的实数空间，其每一维对应一个字符串 u∈Σnu\in \Sigma^nu∈Σn，映射 ϕn(s)\phi_n(s)ϕn​(s) 将字符串 sss 对应于空间 RΣn\mathbb R^{\Sigma^n}RΣn 的一个向量，其在 uuu 维上的取值为
[ϕn(s)]u=∑i:s(i)=uλl(i)[\phi_n(s)]_u = \sum_{i:s(i) = u}\lambda^{l(i)} [ϕn​(s)]u​=i:s(i)=u∑​λl(i)
这里，0≤λ≤10\le \lambda \le 10≤λ≤1 是一个衰减参数，l(i)l(i)l(i) 表示字符串 iii 的长度，求和在 sss 中所有与 uuu 相同的子串上进行。

例如，假设 Σ\SigmaΣ 为英文字符集，nnn 为 333，S\mathcal SS 为长度大于或等于 333 的字符串的集合。考虑将字符集 S\mathcal SS 映射到特征空间 H3H_3H3​。H3H_3H3​ 的一维对应于字符串 asd\rm asdasd。这时，字符串 “Nasdaq\rm NasdaqNasdaq”与“lassdas\rm lass\space daslass das”在这一维上的值分别是 [ϕ3(Nasdaq)]asd=λ3[\phi_3({\rm Nasdaq})]_{\rm asd}=\lambda^3[ϕ3​(Nasdaq)]asd​=λ3 和 [ϕ3(lass□das)]asd=2λ5[\phi_3({\rm lass □das})]_{asd}=2\lambda^5[ϕ3​(lass□das)]asd​=2λ5（□□□ 为空格）。在第一个字符串里，asd\rm asdasd 是连续的子串。在第二个字符串里，asd\rm asdasd 是长度为 555 的不连续子串，共出现 222 次。

两个字符串 sss 和 ttt 上的字符串核函数是基于映射 ϕn\phi_nϕn​ 的特征空间中的内积：
Kn(s,t)=∑u∈Σn[ϕn(s)]u[ϕn(t)]u=∑u∈Σn∑(i,j):s(i)=t(j)=uλl(i)λl(j)\begin{aligned} K_n(s,t) &= \sum_{u\in \Sigma^n} [\phi_n(s)]_u [\phi_n(t)]_u \\ &= \sum_{u\in \Sigma^n} \sum_{(i,j):s(i)=t(j)=u} \lambda^{l(i)} \lambda^{l(j)} \end{aligned} Kn​(s,t)​=u∈Σn∑​[ϕn​(s)]u​[ϕn​(t)]u​=u∈Σn∑​(i,j):s(i)=t(j)=u∑​λl(i)λl(j)​
字符串核函数 Kn(s,t)K_n(s,t)Kn​(s,t) 给出了字符串 sss 和 ttt 中长度等于 nnn 的所有子串组成的特征向量的余弦相似度（cosine similarity）。直观上，两个字符串相同的子串越多，它们就越相似，字符串核函数的值就越大。字符串核函数可以由动态规划快速计算。

附录

依据函数 K(x,z)K(x,z)K(x,z) 构造一个希尔伯特空间的步骤是：首先定义映射 ϕ\phiϕ 并构成向量空间 S\mathcal SS；然后在 S\mathcal SS 上定义内积构成内积空间；最后将 S\mathcal SS 完备化构成希尔伯特空间。

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

定义映射

ϕ:x→K(⋅,x)∀x∈X\phi:x\to K(·,x) \space\space\space\space \forall x\in \mathcal X\\ ϕ:x→K(⋅,x)    ∀x∈X

根据这一映射，对任意 xi∈Xx_i\in \mathcal Xxi​∈X，αi∈R\alpha_i\in \mathbb Rαi​∈R，i=1,2,…,mi=1,2,\dots,mi=1,2,…,m，定义线性组合
f(⋅)=∑i=1mαiK(⋅,xi)(3)f(·)=\sum_{i=1}^m\alpha_i K(·,x_i)\tag{3} f(⋅)=i=1∑m​αi​K(⋅,xi​)(3)
所有的线性组合构成的集合 S\mathcal SS ，由于 S\mathcal SS 满足线性空间要求的八个公理，所以是一个线性空间。其中，线性空间最重要的特征就是对加法和数乘运算封闭。

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

在 S\mathcal SS 上定义一个运算 ∗*∗：对任意 f,g∈Sf,g\in \mathcal Sf,g∈S，
f(⋅)=∑i=1mαiK(⋅,xi)(4)f(·) = \sum_{i=1}^m \alpha_i K(·,x_i) \tag{4} f(⋅)=i=1∑m​αi​K(⋅,xi​)(4)

g(⋅)=∑j=1lβjK(⋅,zj)(5)g(·) = \sum_{j=1}^l \beta_j K(·,z_j)\tag{5} g(⋅)=j=1∑l​βj​K(⋅,zj​)(5)

定义运算 ∗*∗
f∗g=∑i=1m∑j=1lαiβjK(xi,zj)(6)f*g = \sum_{i=1}^m\sum_{j=1}^l \alpha_i\beta_j K (x_i,z_j) \tag{6} f∗g=i=1∑m​j=1∑l​αi​βj​K(xi​,zj​)(6)
证明运算 ∗*∗ 是空间 S\mathcal SS 的内积。为此要证明其满足四条公理：

(1)(cf)∗g=c(f∗g),c∈R(7~1)(2)(f+g)∗h=f∗h+g∗h,h∈S(7~2)(3)f∗g=g∗f(7~3)(4)f∗f≥0,(7~4)f∗f=0⇔f=0(7~5)\begin{aligned} (1)\space\space\space\space&(cf)*g = c(f*g), & c\in \mathbb R &&&&&& {(7\text{\textasciitilde}1)} \\ (2)\space\space\space\space&(f+g)*h = f*h+g*h,& h\in \mathcal S &&&&&& {(7\text{\textasciitilde}2)} \\ (3)\space\space\space\space&f*g=g*f &&&&&&&{(7\text{\textasciitilde}3)} \\ (4)\space\space\space\space&f*f\ge 0, &&&&&&&{(7\text{\textasciitilde}4)} \\ \space\space\space\space& f*f = 0\Leftrightarrow f=0 &&&&&&& {(7\text{\textasciitilde}5)} \end{aligned} (1)    (2)    (3)    (4)        ​(cf)∗g=c(f∗g),(f+g)∗h=f∗h+g∗h,f∗g=g∗ff∗f≥0,f∗f=0⇔f=0​c∈Rh∈S​​​​​​(7~1)(7~2)(7~3)(7~4)(7~5)​

其中，(1)∼(3)(1)\sim(3)(1)∼(3) 由式 (3)∼(5)(3)\sim(5)(3)∼(5) 及 K(x,z)K(x,z)K(x,z) 的对称性容易得到。现证 (4)(4)(4) 之式 (7~4)(7\text{\textasciitilde}4)(7~4)。由式 (3)(3)(3) 及式 (6)(6)(6) 可得：
f∗f=∑i,j=1mαiβjK(xi,xj)f*f = \sum_{i,j=1}^m\alpha_i\beta_j K(x_i,x_j) f∗f=i,j=1∑m​αi​βj​K(xi​,xj​)
由 Gram\rm GramGram 矩阵的半正定性知上式右端非负，即 f∗f≥0f*f\ge 0f∗f≥0。

再证 (4)(4)(4) 之式 (7~5)(7\text{\textasciitilde}5)(7~5)。其充分性，当 f(⋅)=0f(·)=0f(⋅)=0 时，可得
∑i=1mαiK(xi,xj)=0∀j=1,2,…,m\sum_{i=1}^m\alpha_i K(x_i,x_j)=0 \space\space\space\space \forall j=1,2,\dots, m\\ i=1∑m​αi​K(xi​,xj​)=0    ∀j=1,2,…,m
将 f∗ff*ff∗f 表示为
∑j=1mαj(∑i=1mαiK(xi,xj))=0\sum_{j=1}^m\alpha_j \Big(\sum_{i=1}^m \alpha_iK(x_i,x_j)\Big)=0 j=1∑m​αj​(i=1∑m​αi​K(xi​,xj​))=0
其中累加的每一项均为 000，于是 f∗f=0f*f=0f∗f=0。

必要性，首先我们注意到如下性质
K(⋅,x)∗f=∑i=1mαiK(x,xi)=f(x)∀x∈XK(·,x)*f = \sum_{i=1}^m\alpha_iK(x,x_i) = f(x) \space\space\space\space \forall x\in \mathcal X\\ K(⋅,x)∗f=i=1∑m​αi​K(x,xi​)=f(x)    ∀x∈X
运用柯西-施瓦茨不等式，有
f(x)2=(K(⋅,x)∗f)2≤(K(⋅,x)∗K(⋅,x))(f∗f)=0f(x)^2 =\big(K(·,x)*f \big)^2\le \big(K(·,x) * K(·,x) \big) \big( f*f \big) = 0 f(x)2=(K(⋅,x)∗f)2≤(K(⋅,x)∗K(⋅,x))(f∗f)=0
于是有 f(x)=0f(x)=0f(x)=0，再由 xxx 的任意性可知 f=0f=0f=0。

至此，证明了 ∗*∗ 为向量空间 S\mathcal SS 中的内积。赋予内积的向量空间为内积空间，因此 S\mathcal SS 是一个内积空间。

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

现将内积空间 S\mathcal SS 完备化。由式 (6)(6)(6) 定义的内积可以得到范数
∣∣f∣∣=f∗f||f|| = \sqrt{f*f} ∣∣f∣∣=f∗f​
要说明其为范数，需要验证满足三条公理：正定性、正齐次性和次可加性（三角不等式）。其中正定性和正齐次性显然，仅简单验证次可加性：
∣∣f+g∣∣2=(f+g)∗(f+g)=(f∗f)+2(f∗g)+(g∗g)=∣∣f∣∣2+2(f∗g)+∣∣g∣∣2≤∣∣f∣∣2+2∥f∥∥g∥+∣∣g∣∣2=(∣∣f∣∣+∣∣g∣∣)2\begin{aligned} ||f+g||^2 &= (f+g) * (f+g) \\ &=(f*f) + 2(f*g)+(g*g) \\ &= ||f||^2+2(f*g)+||g||^2 \\ &\le||f||^2+2\Vert f\Vert \Vert g\Vert+||g||^2 \\ &=(||f||+||g||)^2 \end{aligned} ∣∣f+g∣∣2​=(f+g)∗(f+g)=(f∗f)+2(f∗g)+(g∗g)=∣∣f∣∣2+2(f∗g)+∣∣g∣∣2≤∣∣f∣∣2+2∥f∥∥g∥+∣∣g∣∣2=(∣∣f∣∣+∣∣g∣∣)2​
其中也运用了柯西-施瓦茨不等式。因此，S\mathcal SS 是一个定义了范数的线性空间，即赋范向量空间。

根据泛函分析中的一个结论，对于不完备的赋范向量空间 S\mathcal SS，一定可以使之完备化，得到完备的赋范向量空间 H\mathcal HH。一个内积空间，当作为一个赋范向量空间是完备的时候，就是希尔伯特空间。这样，就得到了希尔伯特空间 H\mathcal HH。

这一希尔伯特空间 H\mathcal HH 称为再生核希尔伯特空间（reproducing kernel Hilbert space，RKHS）。这是由于核 KKK 具有再生性，即满足
K(⋅,x)∗f=f(x)K(·,x)*f = f(x) K(⋅,x)∗f=f(x)
取 f=K(⋅,z)f=K(·,z)f=K(⋅,z)，可得
K(⋅,x)∗K(⋅,z)=K(x,z)K(·,x)*K(·,z) = K(x,z) K(⋅,x)∗K(⋅,z)=K(x,z)
称为再生核。

至此，我们由满足半正定性的 Gram\rm GramGram 矩阵对应的对称函数 KKK 构造出了一个再生核希尔伯特空间。

REF

[1]《统计学习方法（第二版）》李航著

[2]《Pattern Recognition and Mechine Learning》

[3] 机器学习笔记之核方法(二)正定核函数的充要性证明 - CSDN博客

[4] 正定核 - 知乎