支持向量机（SVM）原理小结（2）非线性支持向量机

1. 非线性支持向量机1.1 图示举例1.2 核技巧1.3 核技巧在支持向量机中的应用1.4 常用核函数1.5 学习算法1.6 联想：多项式回归（线性回归推广） 2. 代码示例：使用非线性kernel SVM解决非线性问题完整代码地址参考

SVM系列文章：

支持向量机（SVM）原理小结（1）线性支持向量机

支持向量机（SVM）原理小结（2）非线性支持向量机

支持向量机（SVM）原理小结（3）支持向量回归SVR

本博客中使用到的完整代码请移步至: 我的github：/qingyujean/Magic-NLPer，求赞求星求鼓励~~~

1. 非线性支持向量机

什么是非线性分类问题：通过利用非线性模型才能很好地进行分类的问题。

数据集非线性可分：是指能使用一个超曲面，将正负例正确分开。

思考：非线性问题不好求解，使用非线性变换，将非线性问题转化为线性问题，通过求解变换后的线性问题的方法，求解原来的非线性问题。

（1）首先使用一个变换，将原空间的数据映射到新空间；（2）然后在新空间里用线性分类学习方法，从训练数据中学习分类模型

核技巧就属于这样的方法。

解决非线性问题的基本思路：将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。

幸运的是，如果原始空间是有限维的，即属性数有限，那么一定存在一个高维特征空间使样本可分。

1.1 图示举例

例如在下图中的两类数据，分别分布为两个圆圈的形状，显然这2类数据是线性不可分的。但是我们可以将一个二维的数据通过下面的映射函数转换到三维空间，在这个三维空间里数据是可分的：

ϕ ( x 1 , x 2 ) = ( z 1 , z 2 , z 3 ) = ( x 1 , x 2 , x 1 2 + x 2 2 ) \phi(x_1,x_2)=(z_1,z_2,z_3)=(x_1,x_2,x_1^2+x_2^2) ϕ(x1​,x2​)=(z1​,z2​,z3​)=(x1​,x2​,x12​+x22​)

上图来源于：/?p=685

通过 ϕ \phi ϕ变换，可以通过一个线性超平面将样本分为2类，当将这个线性超平面再投射到原先的二维特征空间时，它变成了一个非线性决策边界。

1.2 核技巧

核技巧应用到支持向量机，基本想法就是：通过一个非线性变换，将输入空间（欧式空间）对应于一个特征空间（希尔伯特空间），使得在输入空间的超曲面模型，对于特征空间的超平面模型（SVM）。这样，分类学习就能在特征空间中求解线性支持SVM来完成。

设原空间为 X \mathcal{X} X为输入空间， H \mathcal{H} H为特征空间，如果存在映射： ϕ ( x ) : X → H \phi(x):\mathcal{X} \rightarrow \mathcal{H} ϕ(x):X→H，对所有的 x , z ∈ X x,z \in \mathcal{X} x,z∈X，函数 K ( x , z ) K(x,z) K(x,z)满足：

K ( x , z ) = ϕ ( x ) ⋅ ϕ ( z ) K(x,z)=\phi(x)\cdot\phi(z) K(x,z)=ϕ(x)⋅ϕ(z)

则称 K ( x , z ) K(x,z) K(x,z)为核函数，其中 ϕ ( x ) \phi(x) ϕ(x)为映射函数， ⋅ \cdot ⋅为内积。

核函数的直观理解：

实例x i x_i xi​与x j x_j xj​在特征空间的内积，等于它们在原始样本空间中通过K ( x i , x j ) K(x_i,x_j) K(xi​,xj​)计算的结果。有了这样的函数，就不必直接去求高维甚至无穷维特征空间的内积ϕ ( x ) ⋅ ϕ ( z ) \phi(x)\cdot\phi(z) ϕ(x)⋅ϕ(z)。

注意：

特征空间一般是高维甚至是无穷维的，直接计算ϕ ( x ) ⋅ ϕ ( z ) \phi(x)\cdot\phi(z) ϕ(x)⋅ϕ(z)通常是困难的。

对于给定的核函数，特征空间的取法（例如维度）不唯一，映射函数ϕ ( x ) \phi(x) ϕ(x)的取法也不唯一。

通常直接计算K ( x , z ) K(x,z) K(x,z)更容易，而无需显示的定义ϕ ( x ) \phi(x) ϕ(x)的具体形式。

1.3 核技巧在支持向量机中的应用

在线性支持向量机（无论是硬间隔还是软间隔）的对偶问题中，其目标函数（包括分类决策函数/分离超平面）都只依赖于输入实例之间的内积，例如：

对偶问题的目标函数（ min ⁡ α L ( α ) \min\limits_{\alpha}L(\alpha) αmin​L(α)）：

L ( α ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i L(\alpha)=\frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum\limits_{i=1}^{N} \alpha_{i} L(α)=21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​

分离超平面可以写为

∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ = 0 \sum_{i=1}^{N}\alpha_i^*y_i(x\cdot x_i)+b^*=0 i=1∑N​αi∗​yi​(x⋅xi​)+b∗=0

分类决策函数可以写成

f ( x ) = sign ( ∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ ) f(x)=\text{sign}\left(\sum_{i=1}^{N}\alpha_i^*y_i(x\cdot x_i)+b^*\right) f(x)=sign(i=1∑N​αi∗​yi​(x⋅xi​)+b∗)

将上面的内积x i ⋅ x j x_i\cdot x_j xi​⋅xj​用核函数K ( x i , x j ) = ϕ ( x i ) ϕ ( x j ) K(x_i,x_j)=\phi(x_i)\phi(x_j) K(xi​,xj​)=ϕ(xi​)ϕ(xj​)代替，就可以得到如下对偶问题的目标函数以及相应的分离超平面和分类决策函数：

对偶问题的目标函数（ min ⁡ α W ( α ) \min\limits_{\alpha}W(\alpha) αmin​W(α)）：

W ( α ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ϕ ( x i ) ⋅ ϕ ( x j ) − ∑ i = 1 N α i = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i \begin{array}{ll}W(\alpha) &= \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\phi(x_{i}) \cdot \phi(x_{j})-\sum\limits_{i=1}^{N} \alpha_{i} \\& =\frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}K(x_i,x_j)-\sum\limits_{i=1}^{N} \alpha_{i} \end{array} W(α)​=21​i=1∑N​j=1∑N​αi​αj​yi​yj​ϕ(xi​)⋅ϕ(xj​)−i=1∑N​αi​=21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​,xj​)−i=1∑N​αi​​

分离超平面可以写为

∑ i = 1 N α i ∗ y i K ( x i , x ) + b ∗ = 0 \sum_{i=1}^{N}\alpha_i^*y_iK(x_i,x)+b^*=0 i=1∑N​αi∗​yi​K(xi​,x)+b∗=0

分类决策函数可以写成

f ( x ) = sign ( ∑ i = 1 N α i ∗ y i ϕ ( x i ) ⋅ ϕ ( x ) + b ∗ ) = sign ( ∑ i = 1 N α i ∗ y i K ( x i , x ) + b ∗ ) \begin{array}{ll}f(x) & =\text{sign}\left(\sum\limits_{i=1}^{N}\alpha_i^*y_i\phi(x_i)\cdot \phi(x)+b^*\right) \\& =\text{sign}\left(\sum\limits_{i=1}^{N}\alpha_i^*y_iK(x_i,x)+b^*\right)\end{array} f(x)​=sign(i=1∑N​αi∗​yi​ϕ(xi​)⋅ϕ(x)+b∗)=sign(i=1∑N​αi∗​yi​K(xi​,x)+b∗)​

这相当于原输入空间经过映射 ϕ \phi ϕ，变换到一个新的特征空间，原输入空间的内积运算 x i ⋅ x j x_i\cdot x_j xi​⋅xj​转化为了新特征空间的内积运算 ϕ ( x i ) ⋅ ϕ ( x j ) \phi(x_i)\cdot \phi(x_j) ϕ(xi​)⋅ϕ(xj​)（即 K ( x i , x j ) K(x_i,x_j) K(xi​,xj​)），在新的特征空间中从训练样本中学习线性支持向量机。当映射函数为非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。

在核函数给定的条件下，利用解线性分类问题的方法来求解非线性分类问题支持向量机，即为非线性支持向量机。学习是隐式的在特征空间进行的，不需要显示的定义特征空间和映射函数。这样的技巧称为核技巧，它是巧妙的利用线性分类学习方法与核函数解决非线性问题的技术。

在实际应用中，往往依赖领域知识直接选择核函数，核函数的有效性需要通过实验验证。

通常所说的核函数就是正定核函数。

1.4 常用核函数

线性核 K ( x , z ) = x ⋅ z K(x,z)=x \cdot z K(x,z)=x⋅z多项式核函数 K ( x , z ) = ( x ⋅ z + 1 ) p K(x,z)=(x\cdot z+1)^p K(x,z)=(x⋅z+1)p高斯核函数 K ( x , z ) = exp ⁡ ( − ∥ x − z ∥ 2 2 σ 2 ) K(x,z)=\exp \left(-\frac{\left\|x-z\right\|^{2}}{2 \sigma^{2}}\right) K(x,z)=exp(−2σ2∥x−z∥2​)拉普拉斯核 K ( x , z ) = exp ⁡ ( − ∥ x − z ∥ σ ) K(x,z)=\exp \left(-\frac{\left\|x-z\right\|}{\sigma}\right) K(x,z)=exp(−σ∥x−z∥​)sigmoid核 K ( x , z ) = tanh ⁡ ( β x ⋅ z + θ ) K(x,z)=\tanh (\beta\; x\cdot z+\theta) K(x,z)=tanh(βx⋅z+θ)字符串核函数

经验：对文本数据通常采用线性核，情况不明时可先尝试高斯核。

1.5 学习算法

1.6 联想：多项式回归（线性回归推广）

SVM通过引入核函数，用解线性分类问题的方法来求解非线性分类问题，这不禁让人想起了在线性回归（Linear Regression）原理小结中，提到的多项式回归，也是一种通过“换元”（或者说叫“特征变换”），将低维线性不可分的数据，在映射到了高维以后，就变成线性可分的了，从而使得能用线性回归方法去解决非线性（多项式）的回归问题。

以一个只有两个特征的p次方多项式回归的模型为例进行说明：

h θ ( x 1 , x 2 ) = θ 0 + θ 1 x 1 + θ 2 x 2 + θ 3 x 1 2 + θ 4 x 2 2 + θ 5 x 1 x 2 h_\theta(x_1, x_2) = \theta_0 + \theta_{1}x_1 + \theta_{2}x_{2} + \theta_{3}x_1^{2} + \theta_{4}x_2^{2} + \theta_{5}x_{1}x_2 hθ​(x1​,x2​)=θ0​+θ1​x1​+θ2​x2​+θ3​x12​+θ4​x22​+θ5​x1​x2​

然后令 x 0 = 1 , x 1 = x 1 , x 2 = x 2 , x 3 = x 1 2 , x 4 = x 2 2 , x 5 = x 1 x 2 x_0 = 1, x_1 = x_1, x_2 = x_2, x_3 =x_1^{2}, x_4 = x_2^{2}, x_5 = x_{1}x_2 x0​=1,x1​=x1​,x2​=x2​,x3​=x12​,x4​=x22​,x5​=x1​x2​ ,这样我们就得到了下式：

h θ ( x 1 , x 2 ) = θ 0 + θ 1 x 1 + θ 2 x 2 + θ 3 x 3 + θ 4 x 4 + θ 5 x 5 h_\theta(x_1, x_2) = \theta_0 + \theta_{1}x_1 + \theta_{2}x_{2} + \theta_{3}x_3 + \theta_{4}x_4 + \theta_{5}x_5 hθ​(x1​,x2​)=θ0​+θ1​x1​+θ2​x2​+θ3​x3​+θ4​x4​+θ5​x5​

此时，一个二元的多项式回归，转化为了一个五元的线性回归，然后便可以使用线性回归的方法来完成算法。对于每个二元样本特征 ( x 1 , x 2 ) (x_1,x_2) (x1​,x2​)，可转化为一个五元样本特征 ( 1 , x 1 , x 2 , x 1 2 , x 2 2 , x 1 x 2 ) (1, x_1, x_2, x_{1}^2, x_{2}^2, x_{1}x_2) (1,x1​,x2​,x12​,x22​,x1​x2​)，对于转化得到的五元样本特征，便可以使用线性回归算法来求解。

2. 代码示例：使用非线性kernel SVM解决非线性问题

准备数据集：创建一个简单的数据集，它具有XOR门的形式，其中100个样本将被分配给类标签1，100个样本将被分配给类标签-1。

# 创建一个简单的数据集，它具有XOR门的形式# 其中100个样本将被分配给类标签1，100个样本将被分配给类标签-1np.random.seed(1)X_xor = np.random.randn(200, 2)y_xor = np.logical_xor(X_xor[:, 0] > 0, X_xor[:, 1] > 0)y_xor = np.where(y_xor, 1, -1)plt.scatter(X_xor[y_xor == 1, 0], X_xor[y_xor == 1, 1], c='b', marker='x', label='1')plt.scatter(X_xor[y_xor == -1, 0], X_xor[y_xor == -1, 1], c='r', marker='s', label='-1')plt.xlim([-3, 3])plt.ylim([-3, 3])plt.legend(loc='best')plt.show()

使用 rbf 核 SVM 训练，并绘制分类决策边界：

svm = SVC(kernel='rbf', random_state=1, gamma=0.10, C=10.0)svm.fit(X_xor, y_xor)plot_decision_regions(X_xor, y_xor, classifier=svm)plt.legend(loc='upper left')plt.show()

完整代码地址

完整代码请移步至: 我的github：/qingyujean/Magic-NLPer，求赞求星求鼓励~~~

最后：如果本文中出现任何错误，请您一定要帮忙指正，感激~

参考

[1] 统计学习方法（第2版） 李航

[2] Python_Machine_Learning_2nd_Edition

[3] 西瓜书-机器学习  周志华

[4] 支持向量机原理(三)线性不可分支持向量机与核函数  刘建平