支持向量机

全面理解SVM

感知机

感知机是一个二分类的线性分类模型，其输入为样本的特征向量，输出为样本的类别（+1 或 -1）。对于某特征向量x，有广义线性模型
$f(x)=sign(w\cdot x+b)$
在感知机中，符号函数为阶跃函数
$sign(x)=\left\{ \begin{aligned} +1,\ & x\ge 0 \\ -1,\ & x <0 \end{aligned} \right.$
它的几何解释是，f(x) 是一个超平面，其中权值w是超平面的法向量，偏置b是超平面的截距。超平面把特征空间划分为两部分，位于超平面两端的特征向量分别被划分为正负两类。

所以感知机模型是要求数据集线性可分的。

训练感知机模型，首先需要一个衡量预测值与真实值的损失函数。感知机的损失函数定义的是误分类点到超平面的距离，训练的目的是最小化损失函数，即最小化这个距离。

样本点（特征向量）与超平面的距离可定义为
$\frac{|w\cdot x_i+b|}{||w||}$
对于误分类的样本点，其预测值与真实值显然是异号的，即
$-y_i(w\cdot x_i+b)>0$
所以，假设有M个误分类点，它们到超平面距离的总和为
$-\frac{1}{||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b)$
$\frac{1}{||w||}$ 是一个常数，可以省略。最终得到感知机的损失函数
$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$
显然，这个损失函数的最小值是0，也就是没有误分类点。感知机学习就是在假设空间中选取合适的w和b，使损失函数最小化。

优化方法是随机梯度下降法。将损失函数分别对w和b求梯度
$\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i\\\nabla_bL(w,b)=-\sum_{x_i\in M}y_i$
选取一个误分类点，对w和b执行更新
$w\gets w+\eta y_ix_i\\b\gets b+\eta y_i$
循环进行，直到损失函数收敛或训练达到设定的轮次。可以证明，在线性可分数据集里，感知机是可以经过有限次迭代而最终收敛的。

硬间隔支持向量机

感知机模型简单易懂，但它的训练是一种启发式方法。要将两组数据样本线性分开，其实存在很多解，而从感知机的损失函数就可以看出来，它的优化仅仅是能将两组样本分开，使误分类点为0，而不管分开的方法是不是最优解。

比如在上面的情形中，明显第二种分开方法是更好的，因为它更加健壮，对未见样本的泛化能力更强。硬间隔支持向量机的目的，就是在线性可分数据集中，找到这样一个最好的超平面。

和感知机算法一样，我们定义一个广义线性模型。
$f(x)=sign(wx+b)$
在数据集中，各点离超平面的远近，可以表明该点分类预测的确信程度。离超平面越远，可以说这个点更“确切”地分类到对应的一类。假如超平面确定， $|w\cdot x+b|$ 可以相对地表示点x和超平面之间的远近，而其与标签是否同号，则可表示分类是否正确。由此可以定义函数间隔
$\hat{\gamma_i}=y_i(w\cdot x_i+b)$
这其实在感知机里已经出现了，但之前并没有点明。

一组数据集的函数间隔，可以用这组样本里离超平面最近的样本点的函数间隔来表示，这个样本点称为支持向量，即
$\hat{\gamma}=\min_{i=1,..,N}\hat{\gamma _i}$
在决定分离超平面时，只有支持向量起作用，其他样本点并不起作用。

如果成比例地缩放w和b，超平面并没有改变，但是函数间隔却会发生变化。因此需要给函数间隔加上约束，使其变为几何间隔。其中 $||w||$ 是w的 L2 范数。
$\gamma_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})$
和函数间隔一样，数据集T的几何间隔为
$\gamma=\min_{i=1,..,N}\gamma _i$
几何间隔可以视作实例点到超平面的带符号距离。支持向量机的基本思想就是求解能够正确划分数据集并且几何间隔最大的分离超平面。对于线性可分的数据集而言，这个最大间隔分离超平面是唯一的，这里的几何间隔最大化称为硬间隔最大化。

于是得到如下的约束最优化问题：
$\begin{align*} & \max_{w, b}\quad \gamma \\ & s.t.\quad y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})\geqslant \gamma \\ \end{align*}$
相当于
$\begin{align*} & \max_{w, b}\quad \frac{\hat{\gamma}}{||w||} \\ & s.t.\quad y_i(w\cdot x_i+b)\geqslant \hat{\gamma} \\ \end{align*}$
函数间隔的取值并不影响最优化问题的解，也就是说这是一个等价的最优化问题，于是我们可以将整个模型缩放到函数间隔为1的程度。另外注意到最大化 $\frac{1}{||w||}$ 等价于最小化 $\frac{1}{2}||w||^2$ ，于是得到最终的最优化问题
$\begin{align*} & \min_{w, b}\quad \frac{1}{2}||w||^2 \\ & s.t.\quad 1-y_i(w\cdot x_i+b)\leqslant 0 \\ \end{align*}$
这是一个凸二次规划问题。对于这种有约束最优化问题，可以构建拉格朗日函数
$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$
其中α为拉格朗日乘子向量。

假设有定义在 Rⁿ 上的连续可微函数，存在有约束最优化问题
$\begin{align*} & \min_{x\in R^n}\quad f(x) \\ & s.t.\quad c_i(x)\leqslant 0,\ h_j(x)=0 \\ \end{align*}$
其中 $f(x)$ 和 $c_i(x)$ 都是定义在实数集上连续可微的凸函数， $h_j(x)$ 是定义在实数集上的仿射函数。则可构造广义拉格朗日函数
$L(x,\alpha, \beta)=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)$
其中 α_i 和 β_j 为拉格朗日乘子，α_i ≥0。

将原始最优化问题记为P，则有
$\begin{equation} \begin{split} \theta_P(x)&=\max_{\alpha,\beta:\alpha_i\geqslant0}L(x,\alpha,\beta)\\ &=\max_{\alpha,\beta:\alpha_i\geqslant0}[f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)] \end{split} \end{equation}$
假设有某个x违反约束条件（即在拉格朗日函数的可行解区域外），使得 $c_i(x)>0$ 或 $h_j(x)\ne 0$ ，则上式的最大化会使结果趋向于正无穷。因为某个 $c_i(x)>0$ ，函数最大化这可令其权重 $\alpha_i\to+\infty$ ，而 $h_j(x)\ne 0$ 则可令 $\beta_ih_j(x)\to+\infty$ ，而将其他项的α、β取为0。

而当满足约束条件，即 $c_i(x)\leqslant0$ ， $h_j(x)=0$ 时，上式的第三项消失，第二项当 $c_i(x)=0$ 时取得最大值0，所以有
$\max_{\alpha,\beta:\alpha_i\geqslant0}L(x,\alpha,\beta)=f(x)+0+0=f(x)$
综上所述，有
$\theta_P(x)=\left\{ \begin{aligned} f(x),\ & x满足原始约束 \\ +\infty,\ & 否则 \end{aligned} \right.$
这种构造方法的本质是，先构造一个在可行解区域与原目标函数完全一致，且在可行解区域外的数值非常大，甚至无限大的新目标函数，来将有约束优化问题转化为无约束优化问题。

所以对于原始问题的最小化，可等价于
$\min_{x\in R^n}f(x)=\min_{x\in R^n}\max_{\alpha,\beta:\alpha_i\geqslant0}L(x,\alpha,\beta)$
接下来利用拉格朗日函数的另一个性质，即对偶性，可将上面的问题转化为
$\min_{x\in R^n}\max_{\alpha,\beta:\alpha_i\geqslant0}L(x,\alpha,\beta)=\max_{\alpha,\beta:\alpha_i\geqslant0}\min_{x\in R^n}L(x,\alpha,\beta)$
这一步也就是将原始问题转化为对偶问题，拉格朗日函数对偶性的详述在此省略。

分别记上式左边和右边的最优解为 $p^*$ 和 $d^*$ ，可以证明
$p^*\geqslant d^*$
意思就是，对偶问题的最优解是原始问题最优解的下界。当主问题为凸优化问题，且可行域中至少有一点使不等式约束严格成立时, 对偶问题等价于原问题，也就是上式等号成立（强对偶关系成立）。这个条件称为Slater条件。而在SVM里，这个条件是符合的。

于是，我们可以将原始问题写成拉格朗日函数形式，再将其转化为对偶问题。而且原始问题和对偶问题的最优解，由于满足Slater条件，所以是一致的。

首先写出原始问题的对偶问题
$\max_{\alpha}\min_{w,b}L(w,b,\alpha)$
要求解这个对偶问题，需要先对 L(w,b,α) 对w和b求极小，再对α求极大。

首先求解极小问题。由于是凸函数且有闭式解，可以直接用费马大定理解。分别求拉格朗日函数对w和b的偏导，并令其等于0。
$\nabla _wL(w,b,\alpha)=w-\sum_{i=1}^N\alpha _iy_ix_i=0\\ \nabla _bL(w,b,\alpha)=\sum_{i=1}^N\alpha _iy_i=0$
解得
$w=\sum_{i=1}^N\alpha _iy_ix_i\\ \sum_{i=1}^N\alpha _iy_i=0$
将其代入拉格朗日函数原公式，得到
$\begin{equation} \begin{split} L(w,b,\alpha)&=\frac{1}{2}\sum_{i=1}^N\sum _{j=1}^N\alpha _i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha _iy_i((\sum_{j=1}^N\alpha_jy_jx_j)\cdot x_i+ b)+\sum_{i=1}^N\alpha _i\\ &=-\frac{1}{2}\sum_{i=1}^N\sum _{j=1}^N\alpha _i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha _i \end{split} \end{equation}$
接着求解极大问题。根据上面的推导，这个极大问题就是对偶问题
$\begin{align*} & \max_{\alpha}\quad -\frac{1}{2}\sum_{i=1}^N\sum _{j=1}^N\alpha _i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha _i \\ & s.t.\quad \sum_{i=1}^N\alpha _iy_i=0\qquad \alpha_i\geqslant0 \\ \end{align*}$
等价于求解极小化问题
$\begin{align*} & \min_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum _{j=1}^N\alpha _i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha _i \\ & s.t.\quad \sum_{i=1}^N\alpha _iy_i=0\qquad \alpha_i\geqslant0 \\ \end{align*}$
求解这个问题需要用到SMO算法，由于它的推导非常繁琐，我们在下文再继续叙述。SMO算法通过迭代求解，求得α的最优解 $\alpha^*$ ，我们根据这个最优解，就能求得w和b的最优解 $w^*$ 和 $b^*$ 。

我们利用KKT条件继续推导。

KKT条件是强对偶关系成立的充要条件，包括（以下的符号沿用之前论述拉格朗日函数时所用的符号，其中 $x^*$ 、 $\alpha^*$ 、 $\beta^*$ 分别表示x、α、β的最优解）

$\nabla_xL(x^*,\alpha^*,\beta^*)=0$

$\alpha_i^*c_i(x^*)=0$

$h_j(x^*)=0$

还有上文提到的

$\alpha^*_i\geqslant 0$

$c_i(x^*)\leqslant 0$

利用KKT条件的第一条，可以求得w的最优解
$w^*=\sum_{i=1}^N\alpha _i^*y_ix_i$
KKT条件的第二条称为KKT的对偶互补条件。由它可知，当 $c_i(x^*)=0$ 时，α_i 可在其限制范围内自由选取，而当 $c_i(x^*)<0$ 时，α_i 只能取0。

这是什么意思呢？我们假设有一个样本点 $(x_k,y_k)$ ，使得 $c_i(k^*)=0$ ，即
$1-y_k(w\cdot x_k+b)=0$
可化为
$y_k(w\cdot x_k+b)=1$
两边同乘 $y_k$
$y_k^2(w\cdot x_k+b)=y_k$
由于y只取1或-1，所以 $y_k^2=1$ ，可将式子左边的 $y_k^2$ 舍去，于是可以如此求b的最优解
$\begin{equation} \begin{split} b^*&=y_k-w^*x_k\\ &=y_k-\sum_{i=1}^N\alpha _i^*y_ix_ix_k \end{split} \end{equation}$
所以我们分别得到了w和b的最优解
$w^*=\sum_{i=1}^N\alpha _i^*y_ix_i\\b^*=y_k-\sum_{i=1}^N\alpha _i^*y_ix_ix_k$
进一步来考察样本点 $(x_k,y_k)$ 。它使得 $c_i(k^*)=0$ ，那么根据上面的推导， $w\cdot x_k+b$ 的取值也只有+1和-1两种，且与y同号。

而在推导的一开始，我们就通过放缩，将函数间隔 $\hat{\gamma}$ 放缩到1的程度。

也就是说， $(x_k,y_k)$ 就是一开始我们提到的支持向量！上面的推导，也是从数学上证明了，超平面的确定（即确定 $w^*$ 和 $b^*$ ）只依赖于支持向量，也就是数据中对应于 $\alpha^*_i>0$ 的样本点，而其他样本点并不会产生影响。

于是得到了最终的分类决策函数
$f(x)=sign(\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*)$
符号函数和感知机一样，同样是阶跃函数。

软间隔支持向量机

硬间隔支持向量机是一个严格的线性模型，即用一个超平面将数据分隔为两部分。但数据一般情况下很少是严格线性可分的，难以找到一个超平面可以完美地隔开这些数据，即使在训练模型的时候隔开了，当训练集或实际数据落入特征空间后，也很难说会被正确隔开（过拟合）。而且，如果模型把一些噪声当成了支持向量，那也会得到错误的结果。

缓解这个问题的一个方法是允许模型在一些样本上出错，由此可引出软间隔支持向量机的概念。

我们允许部分样本不满足约束
$y_i(w\cdot x_i+b)< 1$
当然，在最大化间隔的同时，还是要让不满足约束的样本尽可能少。所以可以把优化目标写成
$\min_{w,b}\frac{1}{2}||w||+C\sum_{i=1}^m\mathcal{L}_{0/1}(y_i(w\cdot x_i+b))$
C是一个常数，C＞0。而 L_0/1 代表 0/1 损失函数，如果括号里的值小于1，则损失函数输出1（代表有一个样本出错了），否则输出0。

所以C值控制了间隔有多“软”，当C无穷大时，优化目标会迫使所有样本都满足约束，而C越小，则可以允许越多样本不满足约束。在SVM的实际使用中，C是一个相当重要的超参数。

而 0/1 损失函数由于不连续且非凸，所以在实际应用中经常用hinge损失函数（也被称为合页函数）代替，即
$\mathcal{L}_{hinge}(z)=\max(0,1-z)$
当样本正确分类时，hinge损失输出0；而当样本被错误分类时，hinge损失可以输出它和正确值之间的绝对值距离。

于是优化目标变成
$\min_{w,b}\frac{1}{2}||w||+C\sum_{i=1}^m\max\{0,\ 1-y_i(w\cdot x_i+b)\}$
引入松弛变量 $\xi_i=1-y_i(w\cdot x_i+b)$ 且令 ξ_i≥0，就能将上式改写为
$\min_{w,b}\quad\frac{1}{2}||w||+C\sum_{i=1}^m\xi_i\\s.t.\quad y_i(w\cdot x_i+b)\geqslant1-\xi_i，\xi_i\geqslant0$
这就是软间隔支持向量机。

从约束条件可以看出，松弛变量使得 $y_i(w\cdot x_i+b)$ 不一定非要为1，也就是不一定要处在支持向量之外，也算正确分类，如下图所示。

这也可以被看成是一种正则化技巧。我们可以把上面优化目标里的第一项称为结构风险，第二项称为经验风险，即正则化项，而C是用来调和这两者的正则化常数。

非线性支持向量机（核方法）

无论是硬间隔或者软间隔支持向量机，都属于线性支持向量机，只能应用于训练样本线性可分的模型。可在很多情况下，线性可分是可望不可即的，有如异或问题一样，根本找不到一个超平面可以将样本分隔开。

对于这种问题，一种解决方法是将样本从原始空间映射到一个更高维的特征空间，而样本在这个高维的特征空间里线性可分。

关于这一点，有两个定理

Cover Theorem：高维空间比低维空间更易线性可分。
如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本线性可分。

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

支持向量机

全面理解SVM

感知机

硬间隔支持向量机

软间隔支持向量机

非线性支持向量机（核方法）

推荐阅读更多精彩内容