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

2020-06-26  本文已影响0人  又双叒叕苟了一天

非线性支持向量机

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

线性不可分

于是通过从输入空间到特征空间的映射z=\phi(x),其中x\in\mathcal Xz\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 Xi=1,2,\cdots,mK(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)}

计算字符串st的相似程度。具体略。

非线性支持向量机

从非线性分类训练集,通过核函数与软间隔最大化,或凸二次规划,学习得到的分类决策函数
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^ny_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^*)的求解,一个快速有效的方法就是序列最小最优化算法
)。

上一篇 下一篇

猜你喜欢

热点阅读