前文链接

核函数(A)

正定核充要条件

定理（正定核的充要条件）：设$K:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$是对称函数，则$K(x, z)$为正定核的充要条件是对任意$x_i\in\mathcal{X}, i=1, 2, \dots, m, K(x, z)$对应的Gram矩阵
$K=[K(x_i, x_j)]_{m\times m}$
是半正定矩阵.
证明：
必要性 由于$K(x,z)$是$\mathcal{X}\times\mathcal{X}$上的正定核，所以存在$\mathcal{X}$到希尔伯特空间$\mathcal{H}$的映射$\phi$，使得
$K(x, z)=\phi(x)\cdot\phi(z)$
所以，对于任意$x_1, x_2, \dots, x_m$构造$K(x, z)$关于$x_1, x_2, \dots, x_m$的Gram矩阵
$[K_{ij}]_{m\times m}=[K(x_i, x_j)]_{m\times m}$
对任意的$c_1, c_2, \dots, c_m\in\mathbb{R}$，有
$\begin{aligned} \sum_{i, j=1}^mc_ic_jK(x_i, x_j)&=\sum_{i, j=1}^mc_ic_j(\phi(x_i)\cdot \phi(x_j))\\ &=\bigg( \sum_ic_i\phi(x_i)\bigg)\cdot\bigg(\sum_jc_j\phi(x_j)\bigg)\\ &=\bigg\lVert\sum_i c_i\phi(x_i)\bigg\rVert^2\geq 0 \end{aligned}$
可以得到$K(x, z)$关于$x_1, x_2, \dots, x_m$的Gram矩阵为半正定的.
充分性 已知对称函数$K(x, z)$，对任意$x_1, x_2, \dots, x_m\in\mathcal{X}$，$K(x, z)$关于$x_1, x_2, \dots, x_m$的Gram的矩阵是半正定的，构造从$\mathcal{X}$到希尔伯特空间$\mathcal{H}$的映射
$\phi:x\to K(\cdot, x)$
根据核再生性，可以得到
$\left\{ \begin{aligned} &K(\cdot, x)\cdot f=f(x)\\ &K(\cdot, x)K(\cdot, y)=K(x, z) \end{aligned} \right.$
即
$K(x, z)=\phi(x)\cdot\phi(y)$
表示$K(x, z)$是$\mathcal{X}\times\mathcal{X}$上的核函数.
定义（正定核等价定义）：设$\mathcal{X}\subset\mathbb{R}^n$，$K(x, z)$是定义在$\mathcal{X}\times\mathcal{X}$上的对称函数，如果对任意$x_i\in\mathcal{X}, i=1, 2, \dots, m$，$K(x, z)$对应的Gram矩阵
$K=[K(x_i, x_j)]_{m\times m}$
是半正定矩阵，则称$K(x, z)$是正定核.
但是正定核比较难以验证，一般用已有的核函数，如由Mercer定理得到Mercer核.

常用核函数

多项式核函数（polynomial kernel function）

$K(x, z)=(x\cdot z+1)^p$
对应的支持向量机是一个$p$次多项式分类器，此时决策函数为
$f(x)=sgn(\sum_{i=1}^{N_s}\alpha_i^*y_i(x_i\cdot x+1)^p+b^*)$

高斯核函数（Gaussian kernel function）

$K(x, z)=\exp(-\frac{\lVert x-z\rVert^2}{2\sigma^2})$
对应的支持向量机为高斯径向基函数（radial basis function）分类器. 分类决策函数为
$f(x)=sgn(\sum_{i=1}^{N_s}\alpha_i^*y_i\exp(-\frac{\lVert x-x_i\rVert^2}{2\sigma^2})+b^*)$

字符串核函数

核函数不仅可以定义在欧式空间上，还可以定义在离散数据集合上. 建立字符串集合$\mathcal{S}$到特征空间$\mathcal{H}_n=R^{\sum^n}$的映射$\phi_n(s)$，$R^{\sum^n}$表示定义在$\sum^n$上的实数空间，其每一维对应一个字符串$u\in\sum^n$，映射$\phi_n(s)$将字符串$s$对应于空间$R^{\sum^n}$的一个向量，其在$u$维上的取值为
$[\phi_n(s)]_u=\sum_{i:s(i)=u}\lambda^{l(i)}$
两个字符串$s$和$t$上的字符串核函数是基于映射$\phi_n$的特征空间中的内积
$\begin{aligned} k_n(s, t)&=\sum_{u\in\sum^n}[\phi_n(s)]_u[\phi_n(t)]_u \\ &=\sum_{u\in\sum^n}\sum_{(i,j):s(i)=t(j)=u}\lambda^{l(i)}\lambda^{l(j)} \end{aligned}$
字符串核函数给出了字符串$s$和$t$中长度等于$n$的所有子串组成的特征向量的余弦相似度(cosine similarity). 可以使用动态规划快速计算.

参考资料

统计学习方法 清华大学出版社 李航
理解字符串核函数