机器学习算法——支持向量机SVM5(核函数)

在前面的文章里(支持向量机1-4)假设的训练样本是线性可分的,即存在一个划分超平面能将训练样本正确分类。然而在现实任务中,原始样本空间内也许并不存在一个能正确划分两类样本的超平面。

对于这样的问题,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分。

一个定理:如果原始空间是有限维,即属性数有限,那么一定存在一个高维度特征空间使样本可分。

\phi (x)表示将x映射后的特征向量,于是,在特征空间中划分超平面所对应的模型可表示为:

f(x)=w^T \phi(x) + b

其中w和b是模型参数,有:

min \frac{1}{2} ||w||^2 \\ \\ s.t. y_i(w^T \phi (x) + b) \geqslant 1,i=1,2,...,m

其对偶问题是:

\underset{\alpha}{max} \sum_{i=1}^{m} \alpha_i - \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j) \\ \\ s.t. \sum_{i=1}^{m} \alpha_i y_i =0\\ \\ \alpha_i \geqslant 0, i=1,2,...,m

求解上述式子涉及到计算\phi(x_i)^T \phi(x_j),这是样本x_ix_j映射到特征空间之后的内积。由于特征空间维数可能很高,甚至可能是无穷维,因此直接计算\phi(x_i)^T \phi(x_j)是很困难的。于是,可以设想这样一个函数:

\kappa (x_i,x_j) =(\phi(x_i), \phi(x_j))=\phi(x_i)^T \phi(x_j)

即样本x_ix_j在特征空间的内积等于它们在原始样本空间中通过函数\kappa(\cdot, \cdot )计算的结果。这样就不用直接去计算高维甚至无穷维特征空间中的内积,就可以将对偶问题重写为:

机器学习算法——支持向量机SVM5(核函数)_第1张图片

求解后,会得到

f(x)=w^T \phi(x) +b =\sum_{i=1}^{m} \alpha_iy_i \phi_(x_i)^T \phi_{x} +b= \sum_{i=1}^{m} \alpha_iy_i \kappa(x_i,x_j) + b

这里的\kappa(\cdot, \cdot )就是“核函数”(kernel function)。上述式子可以看出,模型最优解可以通过训练样本的核函数展开,这一展开式也称为“支持向量展式”。

那什么样的函数能做核函数呢?有下面的定理:

定理1 令\chi 为输入空间,\kappa(\cdot , \cdot)是定义在\chi × \chi 上的对称函数,则\kappa是核函数当且仅当对于任意数据D= \{x_1, x_2,...,x_m \},则“核矩阵” K总是半正定的:

K= \begin{bmatrix} \kappa(x_1,x_2) & ... & \kappa(x_1,x_j) &... & \kappa(x_1,x_m)\\ \vdots & \ddots & \vdots & \ddots & \vdots\\ \kappa(x_i,x_1)& ...& \kappa(x_i,x_j) & ... & \kappa(x_i,x_m)\\ \vdots & \ddots & \vdots & \ddots & \vdots\\ \kappa(x_m,x_1)& ...& \kappa(x_m,x_j) & ... & \kappa(x_m,x_m)\\ \end{bmatrix}

 ====================================================================

补充知识点:什么是半正定?

设A为实对称矩阵,若对于每个非零实向量X,都是X^TAX\geq 0,则称A为半正定矩阵。

=======================================================================

 从定理1得出,只要一个对称函数所对应的核矩阵是半正定,它就能作为核函数使用。事实上,对于一个半正定核矩阵,总能找到一个与之对应的映射\phi.

换言之,任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”(RKHS)的特征空间。我们常用的核函数有以下几种:

表1 常用核函数
名称 表达式 参数
线性核 \kappa(x_i,x_j)=x_i^Tx_j --
多项式核 \kappa(x_i,x_j) = (x_i^Tx_j)^d d\geqslant 1为多项式的次数
高斯核 \kappa(x_i,x_j)=exp(-\frac{||x_i-x_j||^2}{2\sigma ^2}) \sigma > 0为高斯核的带宽
拉普拉斯核 \kappa(x_i,x_j) = exp(-\frac{||x_i-x_j||}{\sigma}) \sigma > 0
Sigmoid核 \kappa(x_i,x_j) = tanh(\beta x_i^Tx_j+\theta ) tanh为双曲正切函数,\beta > 0, \theta < 0

此外,还可以通过函数组合得到,例如:

\kappa_1\kappa_2为核函数,则对于任意正数\gamma_1\gamma _2,其线性组合\gamma_1 \kappa_1+\gamma_2 \kappa_2也是核函数。

\kappa_1\kappa_2为核函数,则核函数的直积 \kappa_1 \bigotimes \kappa_2(x,z) =\kappa_1(x,z)\kappa_2(x,z)也是核函数。

\kappa_1为核函数,则对于任意函数g(x),\kappa(x,z)=g(x) \kappa_1(x,z) g(z)也是核函数。

你可能感兴趣的