图解机器学习 | 支持向量机模型详解

本文涉及的产品
模型在线服务 PAI-EAS,A10/V100等 500元 1个月
交互式建模 PAI-DSW,每月250计算时 3个月
模型训练 PAI-DLC,100CU*H 3个月
简介: SVM是机器学习领域非常知名的模型。本文讲解SVM的最大间隔分类器、模型原理、核函数与核技巧等重要知识点,并附上线性核函数、多项式核函数和高斯核函数的Python代码实践。

ShowMeAI研究中心

作者:韩信子@ShowMeAI
教程地址http://www.showmeai.tech/tutorials/34
本文地址http://www.showmeai.tech/article-detail/196
声明:版权所有,转载请联系平台与作者并注明出处
收藏 ShowMeAI 查看更多


引言

本篇我们要讲解的模型是大名鼎鼎的支持向量机 SVM,这是曾经在机器学习界有着近乎「垄断」地位的模型,影响力持续了好多年。直至今日,即使深度学习神经网络的影响力逐渐增强,但 SVM 在中小型数据集上依旧有着可以和神经网络抗衡的极好效果和模型鲁棒性。

支持向量机模型; 支持向量机学习方法; 12-1

支持向量机学习方法,针对不同的情况,有由简至繁的不同模型:

  • 线性可分支持向量机(linear support vector machine in linearly separable case):训练数据线性可分的情况下,通过硬间隔最大化(hard margin maximization),学习一个线性的分类器,即线性可分支持向量机(亦称作硬间隔支持向量机)。
  • 线性支持向量机(linear support vector machine):训练数据近似线性可分的情况下,通过软间隔最大化(soft margin maximization),学习一个线性的分类器,称作线性支持向量机(又叫软间隔支持向量机)。
  • 非线性支持向量机(non-linear support vector machine):训练数据线性不可分的情况下,通过使用核技巧(kernel trick)及软间隔最大化,学习非线性分类器,称作非线性支持向量机。

支持向量机模型; 核函数与核技巧; 12-2

支持向量机可以借助核技巧完成复杂场景下的非线性分类,当输入空间为欧式空间或离散集合、特征空间为希尔贝特空间时,核函数(kernel function)表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。

通过使用核函数可以学习非线性支持向量机,等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。

1.最大间隔分类器

1)分类问题与线性模型

分类问题是监督学习的一个核心问题。在监督学习中,当输出变量取有限个离散值时,预测问题便成为分类问题。

支持向量机模型; 最大间隔分类器; 分类问题与线性模型; 12-3

实际生活中,有很多问题的本质都是分类,如识别某种模式:文本分类、分词、词性标注、图像内容识别和目标检测等。

支持向量机模型; 最大间隔分类器; 分类问题与线性模型; 12-4

分类问题的数学理解是空间划分(或者寻找不同类别的决策边界),如图所示是一个简单的线性分类器(这部分更详细的讲解参考ShowMeAI文章 图解机器学习 | 机器学习基础知识图解机器学习 | 逻辑回归算法详解)。

2)最大间隔分类器

不同的模型在解决分类问题时,会有不同的处理方式,直观上看,我们会使用不同的决策边界对样本进行划分。

如图中「冰墩墩」与「雪容融」两类样本点,我们对其进行分类,可以完成该分类任务的决策边界有无数个。而我们这里介绍到的 SVM 模型,要求更高一些,它不仅仅希望把两类样本点区分开,还希望找到鲁棒性最高、稳定性最好的决策边界(对应图中的黑色直线)。

支持向量机模型; 最大间隔分类器; 决策边界; 12-5

这个决策边界与两侧「最近」的数据点有着「最大」的距离,这意味着决策边界具有最强的容错性,不容易受到噪声数据的干扰。直观的理解就是,如果决策边界抖动,最不容易「撞上」样本点或者进而导致误判。

2.支持向量机详解

1)线性可分 SVM 与硬间隔最大化

我们要找到把下图中红蓝两色的图标点分开的最优分界线。令红色的图标点 equation?tex=%3D%2B1 ,蓝色的图标的点 equation?tex=%3D-1 ,直线 equation?tex=f%28x%29%20%3D%20%5Cboldsymbol%7Bw%7D%5Ccdot%20%5Cboldsymbol%7Bx%7D%20%2B%20b ,这里 equation?tex=w%E3%80%81x 是向量,其实公式等价于 equation?tex=f%28x%29%20%3D%20w_1x_1%20%2B%20w_2x_2%20%2B%E2%80%A6%2B%20w_nx_n%20%2B%20b

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-6

  • 当向量 equation?tex=x 为二维向量时, equation?tex=f%28x%29 表示二维空间中的一条直线。
  • 当向量 equation?tex=x 为三维向量时, equation?tex=f%28x%29 表示三维空间中的一个平面。
  • 当向量 equation?tex=xequation?tex=n 维向量( equation?tex=fn%3E3 )时, equation?tex=f%28x%29 表示 equation?tex=n 维空间中的 equation?tex=n-1 维超平面。

当有一个新的点 equation?tex=x 需要预测属于哪个分类的时候,我们用 equation?tex=sgn%28f%28x%29%29 就可以预测了。 equation?tex=sgn 表示符号函数:

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-7

  • equation?tex=f%28x%29%3E0 的时候, equation?tex=sgn%28f%28x%29%29%20%3D%20%2B1
  • equation?tex=f%28x%29%20%3C%200 的时候 equation?tex=sgn%28f%28x%29%29%20%3D%20%E2%80%931

回到重点,我们怎样才能取得一个最优的划分直线 equation?tex=f%28x%29 呢?下图的直线表示几条可能的 equation?tex=f%28x%29

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-8

我们希望这条直线满足「最大间隔」原则,也就是如下图的形态。图中位于红色和蓝色线上的图标就是所谓的支持向量(support vector)。

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-9

决策边界就是 equation?tex=f%28x%29 ,红色和蓝色的线是支持向量(support vector)所在的面,红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙M(Margin Width)。

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-10

这里直接给出间隔 equation?tex=M 的计算公式: equation?tex=M%3D%5Cfrac%7B2%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%20%7D

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-11

SVM 要求解能够正确划分训练数据集并且「几何间隔」最大的分离超平面。

如下图所示, equation?tex=%5Cboldsymbol%7Bw%7D%20%5Ccdot%20%5Cboldsymbol%7Bx%7D%2Bb%3D0 即为分离超平面。对于线性可分的数据集来说,这样的超平面有无穷多个(即感知机),但是几何间隔最大的分离超平面却是唯一的。

我们先做一些定义,假设给定一个特征空间上的训练数据集: equation?tex=T%3D%7B%28x_1%2C%20y_1%29%2C%28x_2%2C%20y_2%29%2C%20%5Cldots%2C%28x_N%2C%20y_N%29%7D 。且训练数据集是线性可分的,其中:

  • equation?tex=x_i%20%5Cin%20%5Cmathbb%7BR%7D%5E%7Bn%7Dequation?tex=y_%7Bi%7D%20%5Cin%20%5Cleft%20%5C%7B%2B1%2C-1%20%5Cright%20%5C%7Dequation?tex=i%3D1%2C2%2C%20%5Cldots%20N%2Cx_%7Bi%7D 为第 equation?tex=i 个特征向量。
  • equation?tex=y_%7Bi%7D 为类标记,当它等于 equation?tex=%2B1 时为正例;为 equation?tex=-1 时为负例。

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-12

(1)几何间隔

对于给定的数据集 equation?tex=T 和超平面 equation?tex=wx%2Bb%3D0

  • 定义超平面关于样本点 equation?tex=%28x_%7Bi%7D%2C%20y_%7Bi%7D%29 的几何间隔为: equation?tex=%5Cgamma_%7Bi%7D%20%3D%20y_i%28%5Cfrac%7Bw%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%20%7D%20%5Ccdot%20x_i%20%2B%20%5Cfrac%7Bb%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%20%7D%29
  • 超平面关于所有样本点的几何间隔的最小值为: equation?tex=%5Cgamma%20%3D%20%5Cmin%20_%7Bi%3D1%2C2%20%5Cldots%2C%20N%7D%20%5Cgamma_%7Bi%7D ,实际上这个距离就是我们所谓的「支持向量到超平面的距离」。

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-13


根据以上定义, SVM 模型的「求解最大分割超平面问题」可以表示为以下约束最优化问题

equation?tex=%5Cbegin%7Baligned%7D%20%20%26%20%5Cmax%20_%7Bw%2Cb%7D%20%5Cgamma%20%5C%5C%20%26%20s.t.%20%5Cquad%20y_%7Bi%7D%28%5Cfrac%7Bw%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%7D%20%5Ccdot%20x_i%2B%5Cfrac%7Bb%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%7D%29%20%5Cgeq%20%5Cgamma%2C%20i%3D1%2C2%2C%20%5Cldots%2C%20N%5C%5C%20%5Cend%7Baligned%7D

  • 上面公式中 s.t 是 subject to 的缩写,也就是限制条件的意思。


将约束条件两边同时除以 equation?tex=%5Cgamma 得到

equation?tex=y_%7Bi%7D%28%5Cfrac%7Bw%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%20%5Cgamma%7D%20%5Ccdot%20x_i%2B%5Cfrac%7Bb%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%5Cgamma%7D%29%20%5Cgeq%201


因为 equation?tex=%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7Cequation?tex=%5Cgamma 都是标量,所以为了表达式简洁,令: equation?tex=w%3D%5Cfrac%7Bw%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%20%5Cgamma%7Dequation?tex=b%3D%5Cfrac%7Bb%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%20%5Cgamma%7D 得到

equation?tex=y_i%28w%20%5Ccdot%20x_i%2Bb%29%20%5Cgeq%201%2C%20i%3D1%2C2%2C%20%5Cldots%2C%20N


又因为最大化 equation?tex=%5Cgamma ,等价于最大化 equation?tex=%5Cfrac%7B1%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%7D ,也就等价于最小化 equation?tex=%5Cfrac%7B1%7D%7B2%7D%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%5E%7B2%7D ,最终 SVM 模型的求解最大分割超平面问题又可以表示为以下约束最优化问题

equation?tex=%5Cbegin%7Baligned%7D%20%20%26%20%5Cmin%20_%7Bw%2C%20b%7D%20%5Cfrac%7B1%7D%7B2%7D%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%5E%7B2%7D%5C%5C%20%26%20s.t.%20%5Cquad%20y_%7Bi%7D%28w%20%5Ccdot%20x_i%2Bb%29%20%5Cgeq%201%2C%20i%3D1%2C2%2C%20%5Cldots%2C%20N%20%5Cend%7Baligned%7D

(2)对偶算法

求解线性可分支持向量机的最优化问题,我们很多时候会将它转化为对偶问题(dual problem)来求解,也就是应用「拉格朗日对偶性」,通过求解「对偶问题(dual problem)」得到「原始问题(primal problem)」的最优解,即线性可分支持向量机的对偶算法(dual algorithm)。

这样做有一些优点:

  • 对偶问题往往更容易求解。
  • 引入自然核函数,进而可以推广到非线性分类问题。


我们首先构建拉格朗日函数(Lagrange function)。为此,对每一个不等式约束引进拉格朗日乘子(Lagrange multiplier) equation?tex=%5Calpha_i%5Cgeq%200%2Ci%3D1%2C2%2C%E2%80%A6%2CN ,定义拉格朗日函数:

equation?tex=%5Cbegin%7Baligned%7D%20%20L%28w%2C%20b%2C%20%5Calpha%29%3D%26%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2B%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%281-y_i%28w%5ET%20x_i%20%2B%20b%29%29%20%5C%5C%20%20%3D%26%20%5Cfrac%7B1%7D%7B2%7Dw%5ETw-%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%28w%5ET%20x_i%20%2B%20b%29%20%2B%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20%5Cend%7Baligned%7D

根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题: equation?tex=%5Cmax_%7B%5Calpha%7D%5Cmin_%7Bw%2Cb%7DL%28w%2C%20b%2C%20%5Calpha%29 。所以,为了得到对偶问题的解,需要先求 equation?tex=L%28w%2C%20b%2C%20%5Calpha%29equation?tex=w%E3%80%81b 的极小值,再求对 equation?tex=%5Calpha 的极大值。


equation?tex=L%28w%2C%20b%2C%20%5Calpha%29equation?tex=w%E3%80%81b 的极小值

将拉格朗日函数 equation?tex=L%28w%2C%20b%2C%20%5Calpha%29 分别对 equation?tex=w%E3%80%81b 求偏导,并令其值为 equation?tex=0

equation?tex=%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20w%7D%20%3D%20w%20%E2%80%93%20%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%20x_i%20%3D0%20%5CRightarrow%20w%20%3D%20%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%20x_i

equation?tex=%5Cfrac%7B%5Cpartial%20L%7D%7Bb%7D%3D-%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_iy_i%3D0%20%5CRightarrow%20%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_iy_i%3D0


将上式代入拉格朗日函数,即得:

equation?tex=%5Cbegin%7Baligned%7D%20%20%5Cmin_%7Bw%2Cb%7D%20L%28w%2C%20b%2C%5Calpha%29%3D%26%5Cfrac%7B1%7D%7B2%7D%20%28%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%20x_i%29%5ET%20%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%20x_i-%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%28%28%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%20x_i%29%5ET%20x_i%20%2B%20b%29%20%2B%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20%5C%5C%20%20%3D%26%5Cfrac%7B1%7D%7B2%7D%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Csum_%7Bj%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%5Calpha_j%20y_jx_i%5ETx_j-%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Csum_%7Bj%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%5Calpha_j%20y_jx_j%5ETx_i%2B%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20%5C%5C%20%20%3D%26%20-%5Cfrac%7B1%7D%7B2%7D%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Csum_%7Bj%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%5Calpha_j%20y_jx_i%5ETx_j%2B%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20%20%5Cend%7Baligned%7D

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-14


equation?tex=%5Cmin_%7Bw%2Cb%7DL%28w%2C%20b%2C%5Calpha%29equation?tex=%5Calpha 的极大值,即对偶问题

equation?tex=%5Cbegin%7Baligned%7D%20%20%26%20%5Cmax_%7B%5Calpha%7D%20-%5Cfrac%7B1%7D%7B2%7D%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Csum_%7Bj%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%5Calpha_j%20y_jx_i%5ETx_j%2B%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20%5C%5C%20%26%20s.t.%20%5Cquad%20%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_iy_i%3D0%20%5C%5C%20%26%20%5Cquad%20%5Cquad%20%5Calpha_i%20%5Cgeq%200%2Ci%3D1%2C%202%E2%80%A6N%20%20%5Cend%7Baligned%7D

将式中的目标函数由求极大转换成求极小,就得到下面与之等价的对偶最优化问题:

equation?tex=%5Cbegin%7Baligned%7D%20%20%26%20%5Cmin_%7B%5Calpha%7D%20%5Cfrac%7B1%7D%7B2%7D%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Csum_%7Bj%3D1%7D%5E%7BN%7D%5Calpha_i%20y_i%5Calpha_j%20y_jx_i%5ETx_j-%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%20%5C%5C%20%20%26%20s.t.%20%5Cquad%20%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_iy_i%3D0%20%5C%5C%20%20%26%20%5Cquad%20%5Cquad%20%5Calpha_i%20%5Cgeq%200%2Ci%3D1%2C%202%E2%80%A6N%20%20%5Cend%7Baligned%7D

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-15


对线性可分训练数据集,假设对偶最优化问题对 equation?tex=%5Calpha 的解为 equation?tex=%5Calpha%5E%2A%3D%28%5Calpha_1%5E%2A%2C%5Calpha_2%5E%2A%2C%E2%80%A6%2C%5Calpha_N%5E%2A%29%5E%20T ,可以由 equation?tex=%5Calpha%5E%2A 求得原始最优化问题的解 equation?tex=w%5E%2A%E3%80%81b%5E%2A

有下面的定理:设 equation?tex=%5Calpha%5E%2A%3D%28%5Calpha_1%5E%2A%2C%5Calpha_2%5E%2A%2C%E2%80%A6%2C%5Calpha_N%5E%2A%29%5ET 是对偶最优化问题的解,则存在下标 equation?tex=j ,使得 equation?tex=%5Calpha_j%5E%2A%3E0 ,并可按下式求得原始最优化问题的解 equation?tex=w%5E%2A%2Cb%5E%2A

equation?tex=w%5E*%3D%5Csum_%7Bi%3D1%7D%5E*%7BN%7D%20%5Calpha_i%5E*y_ix_i

equation?tex=b%5E*%3Dy_j-%5Csum_%7Bi%3D1%7D%5E*%7BN%7D%20%5Calpha_i%5E*y_i(x_i%5E*Tx_j)


证明:根据定理,KKT条件成立,即得:

equation?tex=%5Cbegin%7Baligned%7D%20%20%20%26%20%5Cfrac%7B%5Cpartial%20L%28w%5E%2A%2Cb%5E%2A%2C%5Calpha%20%5E%2A%29%7D%7B%5Cpartial%20w%7D%20%3D%20w%5E%2A-%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%5E%2A%20y_i%20x_i%3D0%20%5C%5C%20%20%26%20%5Cfrac%7B%5Cpartial%20L%28w%5E%2A%2Cb%5E%2A%2C%5Calpha%20%5E%2A%29%7D%7B%5Cpartial%20b%7D%20%3D%20-%5Csum_%7Bi%3D1%7D%5E%7BN%7D%5Calpha_i%5E%2Ay_i%3D0%20%5C%5C%20%20%26%20%5Cfrac%7B%5Cpartial%20L%28w%5E%2A%2Cb%5E%2A%2C%5Calpha%20%5E%2A%29%7D%7B%5Cpartial%20%5Calpha%7D%20%3D%200%20%5C%5C%20%20%26%20%5Calpha_i%281-y_i%28w%5ETx_i%2Bb%29%29%20%3D0%20%5C%5C%20%20%26%20%5Calpha_i%20%5Cgeq%200%20%2C%20%5C%5C%20%20%26%20i%3D1%2C2%2C%E2%80%A6%2CN%20%5C%5C%20%20%26%201-y_i%28w%5ETx_i%2Bb%29%20%5Cleq%200%20%2C%20i%3D1%2C2%2C%E2%80%A6%2CN%20%20%5Cend%7Baligned%7D

由此得 equation?tex=w%5E%2A%3D%5Csum_%7Bi%3D1%7D%5E%7BN%7D%20%5Calpha_i%5E%2Ay_ix_i

其中至少有一个 equation?tex=%5Calpha_j%5E%2A%3E0 (用反正法,假设 equation?tex=%5Calpha_j%5E%2A%3D0 ,由式可知 equation?tex=w%5E%2A%3D0 ,而 equation?tex=w%5E%2A%3D0 不是原始最优化问题的解,产生矛盾),由此对 equation?tex=j 有: equation?tex=y_j%28w%5E%2A%5Ccdot%20x_j%2Bb%5E%2A%29%20%E2%80%93%201%20%3D%200

将式代入并注意到 equation?tex=y_j%5E2%3D1 ,即得: equation?tex=b%5E%2A%20%3D%20y_j%20%E2%80%93%20w%5E%2A%7B%7Dx_j%20%3D%20y_j%20%E2%80%93%20%5Csum_%7Bi%3D1%7D%5E%7BN%7D%20%5Calpha_i%5E%2Ay_i%28x_ix_j%29


由此定理可知,分离超平面可以写成

equation?tex=%5Csum_%7Bi%3D1%7D%5E%7BN%7D%20%5Calpha_i%5E%2Ay_i%28x%5Ccdot%20x_i%29%20%2B%20b%5E%2A%20%3D%200


分类决策函数可以写成

equation?tex=f%28x%29%20%3D%20sign%28%5Csum_%7Bi%3D1%7D%5E%7BN%7D%20%5Calpha_i%5E%2Ay_i%28x%5Ccdot%20x_i%29%20%2B%20b%5E%2A%29

支持向量机模型; 线性可分SVM与硬间隔最大化; 12-16

也就是说,这里的决策函数只依赖于输入 equation?tex=x 和训练样本输入的内积。上式亦称作线性可分 SVM 的对偶形式。

综上所述,对于给定得线性可分训练数据集,可以首先求对偶问题的解 equation?tex=%5Calpha%5E%2A ;再利用公式求得原始问题的解 equation?tex=w%5E%2A%2Cb%5E%2A ;从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法,是线性可分支持向量机学习的基本算法。

2)线性 SVM 与软间隔最大化

我们前面提到的是线性可分的情况,但实际应用中完全线性可分的情况太少见了。如下图就是一个典型的线性不可分的分类图(我们没有办法找到一条直线,把空间划分为 equation?tex=2 个区域,一个区域只有黑点,一个区域只有白点)。

要对其进行切分,有2种方案:


方案1:用曲线去将其完全分开,即非线性的决策边界,这会和之后谈到的核函数关联

支持向量机模型; 线性SVM与软间隔最大化; 12-17


方案2:还是使用直线,不过不追求完全可分,会适当包容一些分错的情况,在这个过程中我们会在模型中加入惩罚函数,尽量让分错的点不要太多太离谱。对分错点的惩罚函数就是这个点到其正确位置的距离,如下图所示:

支持向量机模型; 线性SVM与软间隔最大化; 12-18

图上黄色、蓝色的直线分别为支持向量所在的边界,黑色的线为决策函数,那些绿色的线表示分错的点到其相应的决策面的距离,这样我们可以在原函数上面加上一个惩罚函数,并且带上其限制条件为:

equation?tex=%5Cbegin%7Baligned%7D%20%20%26%20%5Cmin%20%5Cfrac%7B1%7D%7B2%7D%7Cw%7C%5E%7B2%7D%2BC%20%5Csum_%7Bi%3D1%7D%5E%7BR%7D%20%5Cvarepsilon_%7Bi%7D%2C%20%5C%5C%20%26%20s.t.%2C%20y_%7Bi%7D%5Cleft%28w%5E%7BT%7D%20x_%7Bi%7D%2Bb%5Cright%29%20%5Cgeq%201-%5Cvarepsilon_%7Bi%7D%2C%20%5Cvarepsilon_%7Bi%7D%20%5Cgeq%200%20%5Cend%7Baligned%7D

上述公式为在线性可分问题的基础上加上的惩罚函数部分,当 equation?tex=x_i 在正确一边的时候, equation?tex=%5Cvarepsilon%20%3D%200equation?tex=R 为全部的点的数目, equation?tex=C 是一个由用户去指定的系数,表示对分错的点加入多少的惩罚:

  • 当C很大的时候,分错的点就会更少,但是过拟合的情况可能会比较严重。
  • 当C很小的时候,分错的点可能会很多,不过可能由此得到的模型也会不太正确。

实际我们也会调整和选择合适的 equation?tex=C 值。

经过这个变换之后,我们可以同样求解一个拉格朗日对偶问题,得到原问题的对偶问题的表达式:

equation?tex=%5Cbegin%7Baligned%7D%20%20%26%20%5Cmax%20_%7B%5Calpha%7D%20%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Calpha_%7Bi%7D-%5Cfrac%7B1%7D%7B2%7D%20%5Csum_%7Bi%2C%20j%3D1%7D%5E%7Bn%7D%20%5Calpha_%7Bi%7D%20%5Calpha_%7Bj%7D%20y_%7Bi%7D%20y_%7Bj%7D%20x_%7Bi%7D%5E%7BT%7D%20x_%7Bj%7D%20%5C%5C%20%20%26%20%5Ctext%20%7B%20s.t.%20%7D%2C%20C%20%5Cgeq%20%5Calpha_%7Bi%7D%20%5Cgeq%200%2C%20i%3D1%2C%20%5Ccdots%2C%20n%20%2C%20%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Calpha_%7Bi%7D%20y_%7Bi%7D%3D0%20%5Cend%7Baligned%7D

支持向量机模型; 线性SVM与软间隔最大化; 12-19

在线性不可分情况下得到的对偶问题,不同的地方就是 equation?tex=%5Calpha 的范围从 equation?tex=%5B0%2C%20%2B%20%5Cinfty) ,变为了 equation?tex=%5B0%2C%20C%5D ,增加的惩罚 equation?tex=%5Cvarepsilon 没有为对偶问题增加太多复杂度。

3)非线性 SVM 与核函数

如果我们要处理的分类问题更加复杂,甚至不能像上面一样近似线性可分呢,这种情况下找到的超平面分错的程度太高不太可接受。

对于这样的问题,一种解决方案是将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分,然后再运用 SVM 求解,如下图所示:

支持向量机模型; 非线性SVM与核函数; 12-20

比如下图中的典型线性不可分的情况:

支持向量机模型; 非线性SVM与核函数; 12-21

当我们使用映射函数 equation?tex=z_%7B1%7D%3Dx_%7B1%7D%5E%7B2%7D%2C%20z_%7B2%7D%3Dx_%7B2%7D%5E%7B2%7D%2C%20z_%7B3%7D%3Dx_%7B2%7D 把这两个类似于椭圆形的点映射到三维空间 equation?tex=%28z_1%2Cz_2%2Cz_3%29 后,对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。

支持向量机模型; 非线性SVM与核函数; 12-22

我们回忆一下之前得到的对偶问题表达式:

equation?tex=%5Cbegin%7Baligned%7D%20%20%26%20%5Cmax%20_%7B%5Calpha%7D%20%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Calpha_%7Bi%7D-%5Cfrac%7B1%7D%7B2%7D%20%5Csum_%7Bi%2C%20j%3D1%7D%5E%7Bn%7D%20%5Calpha_%7Bi%7D%20%5Calpha_%7Bj%7D%20y_%7Bi%7D%20y_%7Bj%7D%20x_%7Bi%7D%5E%7BT%7D%20x_%7Bj%7D%20%5C%5C%20%26%20s.t.%20%2C%20C%20%5Cgeq%20%5Calpha_%7Bi%7D%20%5Cgeq%200%2C%20i%3D1%2C%20%5Ccdots%2C%20n%2C%20%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Calpha_%7Bi%7D%20y_%7Bi%7D%3D0%20%5C%5C%20%5Cend%7Baligned%7D

做一点小小的改造,令: equation?tex=x_%7Bi%7D%5E%7BT%7D%20x_%7Bj%7D%3D%5Ckappa%5Cleft%28x_%7Bi%7D%2C%20x_%7Bj%7D%5Cright%29 。这个式子所做的事情就是将线性的空间映射到高维的空间, equation?tex=%5Ckappa%5Cleft%28x_%7Bi%7D%2C%20x_%7Bj%7D%5Cright%29 有很多种,下面是比较典型的两种:

equation?tex=%5Ckappa%5Cleft%28x_%7Bi%7D%2C%20x_%7Bj%7D%5Cright%29%3D%5Cleft%28x_%7Bi%7D%20%5Ccdot%20x_%7Bj%7D%2B1%5Cright%29%5E%7Bd%7Dequation?tex=%5Ckappa%5Cleft%28x_%7Bi%7D%2C%20x_%7Bj%7D%5Cright%29%3D%20%5Cexp%20%5Cleft%28-%5Cfrac%7B%5Cleft%28x_%7Bi%7D-x_%7Bj%7D%5Cright%29%5E%7B2%7D%7D%7B2%5Csigma%5E%7B2%7D%7D%5Cright%29

支持向量机模型; 非线性SVM与核函数; 12-23

上述两个核函数分别为多项式核和高斯核,高斯核甚至是将原始空间映射为无穷维空间,另外核函数有一些比较好的性质,比如说不会比线性条件下增加多少额外的计算量,等等,此处我们不深入。对于一个问题,不同的核函数可能会带来不同的结果,我们需要做一些尝试来支撑选择(关于这个部分,大家可以看最下方的 python 实现部分)。

3. SVM 总结

1)模型总结

支持向量机(Support vector machines, SVM)是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,他的学习策略就是间隔最大化,同时该方法可以形式化为一个求解图二次规划。

支持向量机模型; SVM模型总结; 12-24

SVM由简至繁可分为三类:线性可分支持向量机、硬间隔(hard-margin svm);线性支持向量机、软间隔(soft-margin svm);非线性支持向量机、Kernel SVM。

SVM中存在三宝:间隔、对偶、核技巧。

2)模型优缺点

(1)SVM模型优点

支持向量机模型; SVM模型优缺点; 12-25

  • SVM 是一个凸优化问题,求得的解一定是全局最优而不仅仅是局部最优。
  • 不仅适用于线性问题,还适用于非线性问题(借助核技巧)。
  • 模型鲁棒性好,决策边界只取决于支持向量而不是全部数据集。
  • 中小样本量数据集上效果优异。
  • 无需依赖整个数据。
  • 泛化能力比较强。

(2)SVM模型缺点

  • 二次规划问题求解将涉及n阶矩阵的计算(其中n为样本的个数),计算量随样本量上涨厉害,因此 SVM 不适用于超大数据集。
  • 原始 SVM 仅适用于二分类问题。(当然, SVM 的推广SVR也适用于回归问题;我们也可以通过one-vs-one,one-vs-rest等思路组合 SVM 来解决多分类问题)。
  • 对非线性问题没有通用解决方案,有时候很难找到一个合适的核函数。
  • 对于核函数的高维映射解释力不强,尤其是径向基函数。
  • SVM 对缺失数据敏感。

更多监督学习的算法模型总结可以查看ShowMeAI的文章AI知识技能速查 | 机器学习-监督学习

4.基于Python的 SVM 代码实践

1)算法包说明

我们这里直接借助于python机器学习工具包sklearn来演示 SVM 的应用,sklearn中对 SVM 的算法实现都包在 sklearn.svm 下面,具体见 sklearn 官方文档,其中 SVC 类是用来进行进行分类的任务,SVR 是用来进行数值回归任务的。

不同的核函数需要指定不同的参数

  • 针对线性函数,只需要指定参数 equation?tex=C ,它表示对不符合最大间距规则的样本的惩罚力度。
  • 针对多项式核函数,除了参数 equation?tex=C 外,还需要指定degree,它表示多项式的阶数。
  • 针对高斯核函数,除了参数 equation?tex=C 外,还需要指定gamma值,这个值对应的是高斯函数公式中 equation?tex=%5Cfrac%7B1%7D%7B2%5Csigma%20%5E2%7D 的值。

2)使用线性核函数

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm, datasets

iris = datasets.load_iris()
X = iris.data[:, :2]  #只取前两维特征,方便可视化
y = iris.target

svc = svm.SVC(kernel='linear', C=1).fit(X, y)

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
h = (x_max / x_min) / 100
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

plt.subplot(1, 1, 1)
Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)

plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')
plt.xlim(xx.min(), xx.max())
plt.title('SVC with linear kernel')
plt.show()
AI 代码解读

支持向量机模型; 基于Python的SVM代码实践; 12-26

3)使用多项式核函数

初始化 SVM 对象的代码替换为下面这行

svc = svm.SVC(kernel='poly', degree=3).fit(X, y)
AI 代码解读

支持向量机模型; 基于Python的SVM代码实践; 12-27

4)使用rbf核函数(高斯核函数)

初始化 SVM 对象的代码替换为下面这行

svc = svm.SVC(kernel='rbf', C=1).fit(X, y)
AI 代码解读

支持向量机模型; 基于Python的SVM代码实践; 12-28

gamma 值越大,SVM 就会倾向于越准确的划分每一个训练集里的数据,这会导致泛化误差较大和过拟合问题。

支持向量机模型; 基于Python的SVM代码实践; 12-29

equation?tex=C:错误项的惩罚参数 equation?tex=C 。它还控制平滑决策边界和正确分类训练点之间的权衡。

支持向量机模型; 基于Python的SVM代码实践; 12-30

参考链接

视频教程

可以点击 B站 查看视频的【双语字幕】版本

frameLabelStart--frameLabelEnd

https://www.bilibili.com/video/BV1TT4y127Nf?p=6

机器学习【算法】系列教程

机器学习【实战】系列教程

ShowMeAI 系列教程推荐

ShowMeAI用知识加速每一次技术成长

相关实践学习
使用PAI-EAS一键部署ChatGLM及LangChain应用
本场景中主要介绍如何使用模型在线服务(PAI-EAS)部署ChatGLM的AI-Web应用以及启动WebUI进行模型推理,并通过LangChain集成自己的业务数据。
机器学习概览及常见算法
机器学习(Machine Learning, ML)是人工智能的核心,专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能,它是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域。 本课程将带你入门机器学习,掌握机器学习的概念和常用的算法。
目录
打赏
0
0
1
0
2387
分享
相关文章
特征时序化建模:基于特征缓慢变化维度历史追踪的机器学习模型性能优化方法
本文探讨了数据基础设施设计中常见的一个问题:数据仓库或数据湖仓中的表格缺乏构建高性能机器学习模型所需的历史记录,导致模型性能受限。为解决这一问题,文章介绍了缓慢变化维度(SCD)技术,特别是Type II类型的应用。通过SCD,可以有效追踪维度表的历史变更,确保模型训练数据包含完整的时序信息,从而提升预测准确性。文章还从数据工程师、数据科学家和产品经理的不同视角提供了实施建议,强调历史数据追踪对提升模型性能和业务洞察的重要性,并建议采用渐进式策略逐步引入SCD设计模式。
103 8
特征时序化建模:基于特征缓慢变化维度历史追踪的机器学习模型性能优化方法
PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型
DeepSeek 系列模型以其卓越性能在全球范围内备受瞩目,多次评测中表现优异,性能接近甚至超越国际顶尖闭源模型(如OpenAI的GPT-4、Claude-3.5-Sonnet等)。企业用户和开发者可使用 PAI 平台一键部署 DeepSeek 系列模型,实现 DeepSeek 系列模型与现有业务的高效融合。
云上一键部署 DeepSeek-V3 模型,阿里云 PAI-Model Gallery 最佳实践
本文介绍了如何在阿里云 PAI 平台上一键部署 DeepSeek-V3 模型,通过这一过程,用户能够轻松地利用 DeepSeek-V3 模型进行实时交互和 API 推理,从而加速 AI 应用的开发和部署。
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
276 13
机器学习算法的优化与改进:提升模型性能的策略与方法
FastAPI + ONNX 部署机器学习模型最佳实践
本文介绍了如何结合FastAPI和ONNX实现机器学习模型的高效部署。面对模型兼容性、性能瓶颈、服务稳定性和安全性等挑战,FastAPI与ONNX提供了高性能、易于开发维护、跨框架支持和活跃社区的优势。通过将模型转换为ONNX格式、构建FastAPI应用、进行性能优化及考虑安全性,可以简化部署流程,提升推理性能,确保服务的可靠性与安全性。最后,以手写数字识别模型为例,展示了完整的部署过程,帮助读者更好地理解和应用这些技术。
97 20
多元线性回归:机器学习中的经典模型探讨
多元线性回归是统计学和机器学习中广泛应用的回归分析方法,通过分析多个自变量与因变量之间的关系,帮助理解和预测数据行为。本文深入探讨其理论背景、数学原理、模型构建及实际应用,涵盖房价预测、销售预测和医疗研究等领域。文章还讨论了多重共线性、过拟合等挑战,并展望了未来发展方向,如模型压缩与高效推理、跨模态学习和自监督学习。通过理解这些内容,读者可以更好地运用多元线性回归解决实际问题。
|
1月前
如何看PAI产品下训练(train)模型任务的费用细节
PAI产品下训练(train)模型任务的费用细节
85 6
Qwen2.5-Coder 系列模型在 PAI-QuickStart 的训练、评测、压缩及部署实践
阿里云的人工智能平台 PAI,作为一站式、 AI Native 的大模型与 AIGC 工程平台,为开发者和企业客户提供了 Qwen2.5-Coder 系列模型的全链路最佳实践。本文以Qwen2.5-Coder-32B为例,详细介绍在 PAI-QuickStart 完成 Qwen2.5-Coder 的训练、评测和快速部署。
Qwen2.5-Coder 系列模型在 PAI-QuickStart 的训练、评测、压缩及部署实践
技术实践 | 使用 PAI+LLaMA Factory 微调 Qwen2-VL 模型快速搭建专业领域知识问答机器人
Qwen2-VL是一款具备高级图像和视频理解能力的多模态模型,支持多种语言,适用于多模态应用开发。通过PAI和LLaMA Factory框架,用户可以轻松微调Qwen2-VL模型,快速构建文旅领域的知识问答机器人。本教程详细介绍了从模型部署、微调到对话测试的全过程,帮助开发者高效实现定制化多模态应用。
优化注意力层提升 Transformer 模型效率:通过改进注意力机制降低机器学习成本
Transformer架构自2017年被Vaswani等人提出以来,凭借其核心的注意力机制,已成为AI领域的重大突破。该机制允许模型根据任务需求灵活聚焦于输入的不同部分,极大地增强了对复杂语言和结构的理解能力。起初主要应用于自然语言处理,Transformer迅速扩展至语音识别、计算机视觉等多领域,展现出强大的跨学科应用潜力。然而,随着模型规模的增长,注意力层的高计算复杂度成为发展瓶颈。为此,本文探讨了在PyTorch生态系统中优化注意力层的各种技术,
152 6
优化注意力层提升 Transformer 模型效率:通过改进注意力机制降低机器学习成本