支持向量机

0.引言

本文主要参考了李航的《统计学习方法》。是本人学习支持向量机的学习笔记。
首先对支持向量机做简单介绍，然后分别介绍以下三个模型：
（1）线性可分支持向量机：又称为硬间隔支持向量机，通过硬间隔最大化来学习一个线性分类器。适合数据线性可分情况；
（2）线性支持向量机：又称为软间隔支持向量机，通过软间隔最大化来学习一个线性分类器。适合数据近似线性可分情况；
（3）非线性支持向量机：通过核技巧和软间隔最大化来学一个非线性分类器。适合数据非线性可分情况
本文将对三个模型的介绍，从原始问题导出对偶问题。得到对偶问题以后，通过SMO算法对模型参数进行求解。最后，如果有机会再介绍以下支持向量机模型参数是如何利用SMO算法学习和训练的。

1.线性可分支持向量机

1.1基本模型

两堆数据怎么样才是线性可分就不再赘述，否则请出门左拐百度“线性可分”。支持向量机学习的目的是找到一个将两类数据分离的超平面，这个超平面可以描述为：
$w\cdot x+b=0$
但实际上，我们通过给定的线性可分数据集能够拟合出来的模型为：
$w^*\cdot x+b^*=0$
其中带了星号的 $w^*$ 和 $b^*$ 是超平面模型的参数，表示是从数据集中学习得到的经验值或者说是估计值。与理论上的模型差别就在于这两个参数。如果数据足够多，那么经验值与理论值就近似相等了。

1.2函数间隔和几何间隔

为什么要引入间隔呢？为什么还有除了函数间隔之外还有个几何间隔？

间隔——追求分类的正确度和确信度

什么是间隔，间隔就是样本点与分离超平面之间的距离。支持向量机学习的目标就是将间隔最大化。
支持向量机在学习过程中最终目的是找到一个能将数据分离的超平面。但将数据分离完成后还不够完美，还需要使得这个分离超平面具有足够的正确性和确信度。
假设我们得到了一个超平面 $w\cdot x+b=0$ ，如果有一个点 $x_p$ ，则我们可以采用 $y(w\cdot x_p+b)$ 来表示分类的正确性和确信度。 $y$ 的正负取值描述正确性； $|w\cdot x_p+b|$ 的取值描述确信度。

函数间隔

我们用变量 $\hat{\gamma_i}$ 来表示第i个样本与超平面之间的函数间隔描述式：
$\hat{\gamma_i}=y_i(w \cdot x_i+b)$
在定义和寻找超平面的时候就是在训练集 $T{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ 中寻找最小的函数间隔，即:
$\hat{\gamma}=\min_{i=1,...,N} \hat{\gamma}_i$

几何间隔——对函数间隔加以约束

先不废话，直接给出几何间隔的描述式，然后再解释要引入几何间隔。免得看一堆字看的懵逼。
$\gamma_i=y_i(\frac{w}{||w||} \cdot x_i+\frac{b}{||w||})$
可以看到函数间隔和集合间隔相比，参数 $w$ 和 $b$ 的分母上多了个 $||w||$ ，为什么要这样做呢？因为我们需要对参数 $w$ 和 $b$ 进行约束。如果不进行约束，求出来的超平面 $w\cdot x+b=0$ 与不加约束是相同的（毕竟 $w$ 和 $b$ 前面的系数可以约掉），但 $w$ 和 $b$ 的实际可能会大个好几倍，会导致超平面的确信度 $|w\cdot x+b|$ 变得十分不可靠。因此，我们对函数间隔加以约束，引入几何间隔的概念。
在定义和寻找超平面的时候就是在训练集 $T{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ 中寻找最小的几何间隔，即:
$\gamma_i=\min_{i=1,...,N}\gamma_i$
函数间隔和几何间隔的关系：
$\gamma=\frac{\hat{\gamma}}{||w||}$

1.3线性可分支持向量机的描述——间隔最大化

支持向量机学习的目的是找到一个几何间隔最大的、能正确划分数据集 $T{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ 的分离超平面。有目标，有约束，那么就可以表示为一个有约束的最优化问题,用几何间隔描述：
$\begin{aligned} \max_{w,b} \ \ &\hat{\gamma} \\ s.t.\ \ & y_i(\frac{w}{||w||} \cdot x_i+\frac{b}{||w||}) \leqslant \gamma,\ \ i=1,2,...,N\\ \end{aligned}$
用函数间隔描述：
$\begin{aligned} \max_{w,b}\ \ & \frac{\hat{\gamma}}{||w||}\\ s.t.\ \ & y_i(w\cdot x+b) \geqslant \hat{\gamma}, \ \ i=1,2,...,N\\ \end{aligned}$
为了方便转换为最优化问题，我们将约束项 $||w||$ 保留的同时，对 $\frac{1}{||w||}$ 积分得到 $\frac{1}{2}||w||^2$ ，使得最大化 $\frac{1}{||w||}$ 问题等价转换为最小化 $\frac{1}{2}||w||^2$ ；令 $\hat{\gamma}=1$ ; 利用两个数学技巧得到最终的最优化问题：
线性可分支持向量机最优化问题
$\begin{aligned} \min_{w,b}\ & \ \frac{1}{2}||w||^2\\ s.t. \ & \ \ y_i(w\cdot x+b) -1 \geqslant 0,\ \ i=1,2,...,N\\ \end{aligned}$
我们求出最优解 $w^*,b^*$ 后，可以得到分离超平面：
$w^*\cdot x+b^*=0$
对新样本进行决策分类函数为：
$f(x)=sign(w^*\cdot x+b^*)$
决策分类函数的意思就是将新样本的特征值 $x$ 带入式子 $w^*\cdot x+b^*$ 中，根据得出正负取值来进行分类。
其中， $sign$ 函数：
$sign(x)= \begin{cases} 0,& x<0\\ 1,& x>0\\ \end{cases}$

1.4 从线性可分支持向量机的原始问题导出对偶问题

原始问题：线性可分支持向量机最优化问题
$\begin{aligned} & \min_{w,b}\ \ \frac{1}{2}||w||^2\\ & s.t. \ \ \ y_i(w\cdot x+b) -1 \geqslant 0,\ \ i=1,2,...,N\\ \end{aligned}$
为了导出它的对偶问题，我们构造一个拉格朗日函数：
$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^{N}\alpha_i$
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题
$\max_{\alpha}\min_{w,b}L(w,b,\alpha)$
先求极小化问题，再求极大化问题。
(1)求极小化问题 $\min_{w,b}L(w,b,\alpha)$ ：
将 $L(w,b,\alpha)$ 对 $w$ 和 $b$ 求偏导并令其等于0
$\begin{aligned} & \frac{\partial{L(w,b,\alpha)}}{\partial{{w}}}=w-\sum_{i=1}^{N}y_i\alpha_ix_i=0 \ \Rightarrow \ w=\sum_{i=1}^{N}y_i\alpha_ix_i\\ & \frac{\partial{L(w,b,\alpha)}}{\partial{{b}}}= -\sum_{i=1}^{N}y_i\alpha_i =0 \ \Rightarrow \ \sum_{i=1}^{N}y_i\alpha_i =0\\ \end{aligned}$
将上面两个式子得出的结果代回到 $L(w,b,\alpha)$ ：
$\begin{aligned} L(w,b,\alpha) &=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j-\sum_{i=1}^{N}\alpha_iy_i\big[\sum_{j=1}^{N}y_j\alpha_jx_j\cdot x_i+b\big]+\sum_{i=1}^{N}\alpha_i\\ & =-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ \end{aligned}$
于是就求得：
$\min_{w,b}L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j+\sum_{i=1}^{N}\alpha_i$
(2)求极大化问题 $\max_{\alpha}\min_{w,b}L(w,b,\alpha)$ ：
我们把上一步的结果带入第二步中，再加上约束条件可以得到：
$\begin{aligned} \max_{\alpha}\min_{w,b}\ L(w,b,\alpha) & =\max_{\alpha}\ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ &s.t.\ \sum_{i=1}^{N}\alpha_iy_i=0\\ &\alpha_i \geqslant 0,\ \ \ i=1,...,N \end{aligned}$
再把负号去掉，使得最大化问题等价转化为最小化问题
$\begin{aligned} \min_{\alpha}\ \ \ &\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ s.t.\ \ \ &\sum_{i=1}^{N}\alpha_iy_i=0\\ &\alpha_i \geqslant 0,\ \ \ i=1,...,N \end{aligned}$
这样就得到了对偶问题的最优化问题，然后采用如SMO这种参数估计方法来对参数进行求解。
原始问题的解
假设我们求出了对偶最优化问题的解 $\alpha^*=(\alpha^*_1,...,\alpha^*_l)^T$ ，则存在一个下标j使得 $\alpha^*_j \geqslant 0$ ，我们就可以根据关系推导出原始最优化问题的解 $w^*,b^*$ (这是一个定理，证明请参考李航的《统计学习方法》):
$\begin{aligned} \sum_{i=1}^{N}y_i\alpha_i =0 &\Rightarrow w^*=\sum_{i=1}^{N}\alpha_i^*y_ix_i\\ y_i(w\cdot x+b) -1 \leqslant 0& \Rightarrow b^*=y_i-\sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x_j) \end{aligned}$

2.线性支持向量机

2.1基本模型

正如本文开篇所说的，线性支持向量机用来解决近似线性可分的数据分类问题。我们在线性可分支持向量机的基础对数据集 $T{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ 中的每一个样本都引入一个松弛变量 $\xi_i$ ，并对目标函数引入一个惩罚项，改变原来的目标函数和约束条件，使得线性支持向量机的原始问题为：
$\begin{aligned} \min_{w,b,\xi}\ \ &\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i\\ s.t.\ \ &y_i(w\cdot x_i+b) \geqslant 1-\xi_i,\ \ i=1,2,...,N\\ &\xi_i \geqslant 0,\ \ i=1,2,...,N\\ \end{aligned}$

2.2从线性支持向量机的原始问题导出对偶问题

根据原始问题构造拉格朗日函数：
$L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_i\big[y_i(w\cdot x+b)-1+\xi_i\big]-\sum_{i=1}^{N}\mu_i\xi_i$
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题
$\max_{\alpha}\min_{w,b,\xi}\ \ L(w,b,\xi,\alpha,\mu)$
(1)求极小化问题 $\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)$
将 $L(w,b,\alpha)$ 对 $w,b,\xi$ 求偏导并令其等于0:
$\begin{aligned} \frac{\partial L}{\partial w} &=w-\sum_{i=1}^{N}\alpha_iy_ix_i=0\ \Rightarrow w=\sum_{i=1}^{N}\alpha_iy_ix_i\\ \frac{\partial L}{\partial b}&=-\sum_{i=1}^{N}\ \alpha_iy_i=0 \ \Rightarrow \sum_{i=1}^{N}\ \alpha_i y_i=0\\ \frac{\partial L}{\partial \xi}&=C-\alpha_i-\mu_i=0,\ \Rightarrow C-\alpha_i-\mu_i=0 \end{aligned}$
将上面的结果代回拉格朗日函数得到：
$\begin{aligned} \min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)&=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_i\big[y_i(\sum_{j=1}^{N}\alpha_jy_jx_j+b)-1+\xi_i\big]-\sum_{i=1}^{N}\mu_i\xi_i\\ &=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\xi_i(C-\alpha_i-\xi_i)+\sum_{i=1}^{N}\alpha_i\\ &=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ \end{aligned}$
(2)求极大化问题 $\max_{\alpha}\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)$
通过上一步我们求解得到了极小化问题的表达式，接下来我们求解极大化问题：
$\begin{aligned} \max_{\alpha} & \ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ s.t.&\ \ \sum_{i=1}^{N}\alpha_iy_i=0\\ &\ \ C-\alpha_i-\mu_i=0\\ &\ \ \alpha_i \geqslant 0\\ &\ \ \mu_i \geqslant 0,\ \ i=1,2,...,N \end{aligned}$
实际上，通过约束条件中的非零关系，可以进一步将约束条件简化为 $0\leqslant \alpha \leqslant C$ .我们可以得到最终的线性支持向量机的对偶最优化问题：
$\begin{aligned} \max_{\alpha} & \ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ s.t.&\ \ \sum_{i=1}^{N}\alpha_iy_i=0\\ &\ \ 0\leqslant \alpha \leqslant C,\ \ i=1,2,...,N\\ \end{aligned}$
原始问题的解
原始问题的解与前面的线性可分支持向量机一样，假设我们求出了对偶最优化问题的解 $\alpha^*=(\alpha^*_1,...,\alpha^*_l)^T$ ，则存在一个下标j使得 $0\leqslant \alpha^* \leqslant C$ ，我们就可以根据关系推导出原始最优化问题的解 $w^*,b^*$ (这也是一个定理，证明请参考李航的《统计学习方法》):
$\begin{aligned} \sum_{i=1}^{N}y_i\alpha_i =0 &\Rightarrow w^*=\sum_{i=1}^{N}\alpha_i^*y_ix_i\\ y_i(w\cdot x+b) -1+\xi_i\leqslant 0& \Rightarrow b^*=y_i-\sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x_j) \end{aligned}$
对新样本进行决策分类函数的对偶形式为：
$f(x)=sign(\sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x)+b^*)$
决策分类函数的意思就是将新样本的特征值 $x$ 带入式子 $w^*\cdot x+b^*$ 中，根据得出正负取值来进行分类。
其中， $sign$ 函数：
$sign(x)= \begin{cases} 0,& x<0\\ 1,& x>0\\ \end{cases}$

3.非线性支持向量机

非线性支持向量机中用一个核函数来替代输入实例向量之间的内积，从而实现了把线性不可分的低维数据映射成线性可分的高维数据，然后再用超平面对高维空间内的数据进行分类。

图来自https://blog.csdn.net/jiangjieqazwsx/article/details/51418681

我们回忆线性支持向量机的对偶最优化问题和分类决策函数：
最优化问题：

\begin{aligned} \max_{\alpha} & \ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ s.t.&\ \ \sum_{i=1}^{N}\alpha_iy_i=0\\ &\ \ 0\leqslant \alpha \leqslant C,\ \ i=1,2,...,N\\ \end{aligned}

分类决策函数：

f(x)=sign(\sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x)+b^*)

其实，可以看到上面的最优化问题和分类决策函数中只涉及到了输入实例# $x_ix_j$ 的内积，因此我们可以通过核函数代替输入实例之间的内积。从而达到用核函数把数据映射到高维空间的目的。
我们用核函数 $K(x_i,x_j)$ 来代替实例之间的内积 $x_ix_j$ 后可以写出非线性支持向量机的对偶最优化问题和分类决策函数：
最优化问题：
$\begin{aligned} \max_{\alpha} & \ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)+\sum_{i=1}^{N}\alpha_i\\ s.t.&\ \ \sum_{i=1}^{N}\alpha_iy_i=0\\ &\ \ 0\leqslant \alpha \leqslant C,\ \ i=1,2,...,N\\ \end{aligned}$
分类决策函数：
$f(x)=sign(\sum_{i=1}^{N}\alpha_i^*y_iK(x,x_i)+b^*)$
当核函数 $K(x,x_i)$ 是正定核函数时，最优化问题是凸二次规划问题，解存在。

问题：什么样的函数才可以作为核函数呢？他需要满足什么条件？

为了搞清楚这个问题，首先要想想提出核函数的动机什么？提出核函数的目的是为了把低维数据映射成高维数据啊，然后好用一个分类超平面对这些数据分类。但是映射完成后的高维空间是什么样的我们并不清楚，好像目前只能保证哪些函数可以作为核函数使用，而不能为每种输入数据分布巧妙地设计出一个个核函数。而实际应用中也是在尝试使用各种各样的核函数，如高斯核函数、多项式核函数、线性核函数、sigmoid核函数、拉普拉斯核函数、字符串核函数等。
既然不能对每次的输入数据设计出合适的核函数，我们总能讨论一下什么样的函数才有资格成为核函数，因此我们退而求其次，有空去了解一下为什么核函数 $K(x_i,x_j)$ 必须要是正定核函数？虽然在实际应用中我们直接就采用几种常见的核函数进行尝试。

参考：https://blog.csdn.net/jiangjieqazwsx/article/details/51418681

最后编辑于：2018.08.26 21:06:07

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,293评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,604评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,958评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,729评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,719评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,630评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,000评论 3赞 397
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,665评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,909评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,646评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,726评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,400评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,986评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,959评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,197评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,996评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,481评论 2赞 342

支持向量机

支持向量机

0.引言

1.线性可分支持向量机

1.1基本模型

1.2函数间隔和几何间隔

间隔——追求分类的正确度和确信度

函数间隔

几何间隔——对函数间隔加以约束

1.3线性可分支持向量机的描述——间隔最大化

1.4 从线性可分支持向量机的原始问题导出对偶问题

2.线性支持向量机

2.1基本模型

2.2从线性支持向量机的原始问题导出对偶问题

3.非线性支持向量机

问题：什么样的函数才可以作为核函数呢？他需要满足什么条件？

推荐阅读更多精彩内容