统计机器学习-非线性支持向量机

作者: 又双叒叕苟了一天 | 来源:发表于2020-06-26 21:54 被阅读0次

统计机器学习-非线性支持向量机
SVM
关于希尔伯特空间
支持向量机
支持向量机-QA
支持向量机
支持向量机
svm
第五章支持向量机（分类）
SVM实现

非线性支持向量机

假设给定一个特征空间上的训练数据集
$T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$
其中， $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y=\{+1,-1 \}$ ， $i=1,2,\cdots,N$ ， $x_i$ 为第 $i$ 个特征向量，也称为实例， $y_i$ 为 $x_i$ 的类标记，当 $y_i=+1$ 时，称 $x_i$ 为正例；当 $y_i=-1$ 时，称 $x_i$ 为负例， $(x_i,y_i)$ 称为样本点。再假设输入空间中数据不是线性可分的，例如下图

线性不可分

于是通过从输入空间到特征空间的映射 $z=\phi(x)$ ，其中 $x\in\mathcal X$ ， $z\in\mathcal H$ ，在特征空间 $\mathcal H$ 上，可以找到超平面
$w\cdot z+b=0$
将数据线性划分，如下图：

线性可分

核函数的定义

设 $\mathcal X$ 是输入空间（欧氏空间 $\textbf R^n$ 的子集或离散集合），又设 $\mathcal H$ 为特征空间（希尔伯特空间），如果存在一个从 $\mathcal X$ 到 $\mathcal H$ 的映射
$\phi(x):\mathcal X\rightarrow\mathcal H$
使得对所有 $z,x\in\mathcal X$ ，函数 $K(x,z)$ 满足条件
$K(x,z)=\phi(x)\cdot\phi(z)\tag1$
则称 $K(x,z)$ 为核函数， $\phi(x)$ 为映射函数，式中 $\phi(x)\cdot\phi(z)$ 为 $\phi(x)$ 和 $\phi(z)$ 的内积。

回顾线性支持向量机中超平面公式：
$\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0\tag2$
分类的结果与输入和样本在输入空间的内积相关。而在非线性支持向量机中，则与输入和样本在特征空间的内积相关，即核函数。可以通过和线性支持向量机类似推导得到非线性支持向量机的超平面公式：
$\sum_{i=1}^N\alpha_i^*y_iK(x_i,x)+b^*=0\tag3$
上式只需计算核函数的结果，而无需计算具体映射函数的结果。例如 $K(x,z)=(x\cdot z)^2$ 就是一个核函数，我们可以找到一个映射函数得到 $(x\cdot z)^2=\phi(x)\cdot\phi(z)$ 。证明过程略。

正定核

如前面所述，我们只需计算核函数 $K(x,z)$ 而无需知道具体的映射函数 $\phi(x)$ 。那么我们如何判断一个函数是否具备这样的的映射函数 $\phi(x)$ 满足核函数的要求呢？我们可以根据核函数的充要条件判断：

设 $K:\mathcal X\times\mathcal X\rightarrow\textbf R$ 是对称函数，则 $K(x,z)$ 为正定核函数的充要条件是对任意 $x_i\in\mathcal X$ ， $i=1,2,\cdots,m$ ， $K(x,z)$ 对应的 $\mathrm{Gram}$ 矩阵：
$K=[K(X_i,X_j)]_{m\times m}\tag4$
是半正定矩阵。所以核函数也叫正定核函数。证明略。

常用的核函数

多项式核函数

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

高斯核函数

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

字符串核函数

$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)}$

计算字符串 $s$ 和 $t$ 的相似程度。具体略。

非线性支持向量机

从非线性分类训练集，通过核函数与软间隔最大化，或凸二次规划，学习得到的分类决策函数
$f(x)=\mathrm{sign}\bigg(\sum_{i=1}^N\alpha_i^*y_iK(x_i,x)+b^*\bigg)\tag5$
称为非线性支持向量机， $K(x,z)$ 是正定核函数。

非线性支持向量机学习算法

输入：训练数据集 $T= \{(x_1,y_1),(x_2,y_2),\cdots(x_N,y_N)\}$ ，其中 $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y= \{-1,+1\}$ ， $i=1,2,\cdots,N$ ；

输出：分类决策函数。

（1）选取适当的核函数 $K(x,z)$ 和适当的参数 $C$ ，构造并求解最优化问题
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i\tag6$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0\tag7$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N\tag8$

求得最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 。

（2）选择 $\alpha^*$ 的一个正分量 $0\lt\alpha_j^*\lt C$ ，计算
$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_iK(x_i\cdot x_j)\tag9$
（3）构造决策函数
$f(x)=\mathrm{sign}\bigg(\sum_{i=1}^N\alpha_i^*y_iK(x_i,x)+b^*\bigg)$
对于 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 的求解，一个快速有效的方法就是序列最小最优化算法
)。