文章目录

支持向量怎么找这个“超平面”简化对偶问题求解SMO软间隔简化版SMO代码其他核函数SVM回归

支持向量

​ 整篇文章大量参考小白学习机器学习，在这里先感谢作者。

​ 支持向量机里最难理解的部分之一就是搞清楚什么是支持向量。我尽量用比较通俗易懂的方式来讲讲我自己的理解。

​ 总的来说，支持向量机就是要通过找支持向量来找划分超平面。

​ 以二维平面的样本来做例子，高维数据样本请自行想象和推理。并且SVM最常用和适用的场景是做二分类，如果是多分类的话需要做一些其他的处理(可以用之前的那种方式，参考之前的博客)，处理回归问题(连续值)的话后面也有涉及。

假设所有的样本X=x1,x2...xn,xi=(xi1,xi2)X = {x_1, x_2...x_n}, x_i = (x_{i1},x_{i2})X=x1​,x2​...xn​,xi​=(xi1​,xi2​)，每个样本两个属性。y∈(+1,−1)y\in(+1, -1)y∈(+1,−1)。

假设上述的样本集在二维坐标系里面的分布如下所示：

​ 从图中可以看出，这些样本是线性可分的，可以用一条直线分开，而且是无限多条直线，这些直线可以用

wx+b=0wx + b = 0 wx+b=0

这样一个方程来表达，由www和bbb来确定这条直线的斜率和相对原点的偏移量。

​ 那么推广到多维空间的话，这个方程就变成了：

wTx+b=0w^Tx+b=0 wTx+b=0

其中的wTw^TwT就是表示向量。从距离上看，到这个超平面距离等于1的点，也就是恰好等于yyy的点就是样本点中的支持向量，其他样本点的结果都会大于1。

​ 我们需要这条分界线(超平面)最好是离两边的样本，也就是每类样本距离都远一点，这样的话，泛化误差会好一些。不会出现一点抖动就分类错误。所以，这个分界线是最好在中间位置，如下图所示：

​ 也就是找到最中间的那个分界线。假设存在了这条分界线，所有样本点到这条分界线的距离可以用下面这个公式来计算(至于为什么，自己去看线性代数和解析几何啥的)：

ri=∣wiTxi+b∣∣∣w∣∣r_i = \frac{|w_i^Tx_i+b|}{||w||} ri​=∣∣w∣∣∣wiT​xi​+b∣​

​ 其中∣∣w∣∣||w||∣∣w∣∣表示向量www的范数，一般就是w12+w22+...+wn2\sqrt{w_1^2+w_2^2+...+w_n^2}w12​+w22​+...+wn2​​。

​ 然后，所有样本点中到这条分界线最近的那些样本，也就是我们这篇文章的重点：支持向量。

​ 支持向量用公式表示的话就是：

γ=min⁡i=1,2...mri\gamma = \min_{i=1,2...m}r^i γ=i=1,2...mmin​ri

​ 很明显，对于每一条分界线或者超平面，同一个样本集DDD都会得到不同支持向量γ\gammaγ。支持向量机模型的目的就是找到最合适的分界线或者超平面，这个超平面的特征就是使得支持向量到这个分界面的距离最大，也就是上文说到的，这个分界面到两个类别都比较远(公式1)。

max⁡w,bγs.t.yi(wxi+b∣∣w∣∣)≥γ\max_{w,b}\gamma\\s.t. y_i(\frac{wx_i+b}{||w||}) \geq\gamma w,bmax​γs.t.yi​(∣∣w∣∣wxi​+b​)≥γ

​ 优化项max⁡w,bγ\max_{w,b}\gammamaxw,b​γ比较好理解，也就是找到一个www和bbb来确定一个分界面，使得支持向量们到分界面的距离γ\gammaγ最大。其中的约束条件就是说所有的点到平面的距离都应该大于等于这个距离γ\gammaγ。

​ 有些地方的这个约束条件是写的：

s.t.(wxi+b∣∣w∣∣)≥γs.t.(\frac{wx_i+b}{||w||}) \geq \gamma s.t.(∣∣w∣∣wxi​+b​)≥γ

​ 我的理解是yiy_iyi​反正是只能取值1或者-1，而在上图里面，yi=1y_i=1yi​=1的时候，wxi+b≥γwx_i+b \geq \gammawxi​+b≥γ，也就是说分界线wx+b=0wx+b=0wx+b=0把整个空间划分成了两个部分，一个是大于0，一个是小于0。所以yi(wxi+b)y_i(wx_i+b)yi​(wxi​+b)总是可以保证符号为正，而yiy_iyi​就可以忽略了。

怎么找这个“超平面”

​ 实际上不应该叫做怎么找支持向量，应该是来确定这个超平面的两个参数www和bbb。

​ 这里还是要简单描述一下后面的推导过程，因为SVM的整个过程就是数学推导的过程。

简化

​ 把公式一拿出来研究一下：

​ 首先，那个约束条件来简化一下：

不等式两边除以γ\gammaγ，变成yi(wxi+b∣∣w∣∣γ)≥1y_i(\frac{wx_i+b}{||w||\gamma}) \geq 1yi​(∣∣w∣∣γwxi​+b​)≥1。展开一下，变成yi(wxi∣∣w∣∣γ+b∣∣w∣∣γ)≥1y_i(\frac{wx_i}{||w||\gamma} + \frac{b}{||w||\gamma}) \geq 1yi​(∣∣w∣∣γwxi​​+∣∣w∣∣γb​)≥1。上面的∣∣w∣∣||w||∣∣w∣∣和γ\gammaγ都是标量，可以把值吸入到向量www和bbb中，这就和x本身代表了一个变量，x和x/2是一个意思一样。这样就把公式变成了yi(wxi+b)≥1y_i(wx_i+b)\geq1yi​(wxi​+b)≥1

​ 然后，再把那个优化项拿出来简化一下：

​ 1. max⁡w,bγ\max_{w,b}\gammamaxw,b​γ展开一下变成max⁡w,b∣wiTxi+b∣∣∣w∣∣\max_{w,b}\frac{|w_i^Tx_i+b|}{||w||}maxw,b​∣∣w∣∣∣wiT​xi​+b∣​

最大化γ\gammaγ的话，就可以最大化1∣∣w∣∣\frac{1}{||w||}∣∣w∣∣1​，或者说最小化∣∣w2∣∣||w^2||∣∣w2∣∣

3. 加上一个1/2，也就是最小化12∣∣w2∣∣\frac{1}{2}||w^2||21​∣∣w2∣∣，这是因为后面要求导，直接把指数的2弄下来乘以1/2，就不需要写了。

​ 最后，这个公式一就变成了(公式2)：

min⁡w,b12∣∣w2∣∣s.t.yi(wiTxi+b)≥1\min_{w,b}\frac{1}{2}||w^2|| \\ s.t. y_i(w_i^Tx_i+b)\ge 1 w,bmin​21​∣∣w2∣∣s.t.yi​(wiT​xi​+b)≥1

对偶问题求解

​ SVM里求解这个二次规划问题是使用朗格朗日算子来进行计算，本人对拉格朗日算子是学过，考过，然后就直接过了。所以我差不多能理解个大概，知道是在干什么，怎么干成的，为什么能干成，那就不知道了。

用上一个朗格朗日算子αi\alpha_iαi​的向量，就可以把优化问题转换成一个等价的问题：将优化项和约束项放在一个式子里去求解。上面的公式2增加朗格朗日算子之后变成(公式3)：

L(w,b,α)=12∣∣w2∣∣−∑i=1Nαi(yi(wxi+b)−1)L(w,b,\alpha) = \frac{1}{2}||w^2|| - \sum_{i=1}^N{\alpha_i(yi(wx_i+b) - 1)} L(w,b,α)=21​∣∣w2∣∣−i=1∑N​αi​(yi(wxi​+b)−1)

​ 也就是说把求解公式2中的极值问题改成了求解这个公式3–拉格朗日函数的极值。

我们最初的问题是求最小值。再来看一下这个公式3，这个函数应该在可行解区域内与原目标函数完全一致，而在可行解区域外的数值非常大，甚至是无穷大，那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化问题等价。那么怎么令这个函数达到这个目标呢？从可行解区域入手，也就是约束条件入手。

先再准备一个函数：θ(w)=max⁡αi≥0L(w,b,α)\theta(w) = \max_{\alpha_i\ge0}{L(w,b,\alpha)}θ(w)=maxαi​≥0​L(w,b,α)假设样本不满足约束条件，也就是yi(xiT+b)<1y_i(x_i^T+b)<1yi​(xiT​+b)<1，此时，假设将αi\alpha_iαi​设置为无穷大，那么函数L(w,b,α)L(w,b,\alpha)L(w,b,α)的后面的部分就是负无穷大，yi(wxi+b)−1<0y_i(wx_i+b) - 1 < 0yi​(wxi​+b)−1<0，一个负数乘以无穷大就是负无穷大，再弄个 - 号就是无穷大了。那么此时函数θ(w)\theta(w)θ(w)也就是无穷大了。假设样本满足了约束条件，也就是yi(xiT+b)≥1y_i(x_i^T+b)\ge1yi​(xiT​+b)≥1，此时，θ(w)\theta(w)θ(w)就等于12∣∣w∣∣2\frac{1}{2}||w||^221​∣∣w∣∣2，因为什么呢，在这种情况下，α≥0\alpha \ge0α≥0，yi(xiT+b)−1≥0y_i(x_i^T+b) - 1\ge0yi​(xiT​+b)−1≥0，那么后面无论如何都是一个大于等于0的数，而θ(w)\theta(w)θ(w)的定义就是maxLmaxLmaxL，那么最大是啥呢，就是后面那一截等于0的情况下，LLL能取得最大值，所以θ(w)=12∣∣w∣∣2\theta(w) = \frac{1}{2}||w||^2θ(w)=21​∣∣w∣∣2

所以说，从上面的公式3，经过第二步的变换(不知道什么样的脑袋才能想出这个来)，新的目标函数就变成了：

θ(w)={12∣∣w∣∣2x满足约束+∞x不满足约束\theta(w)=\begin{cases}\frac{1}{2}||w||^2 x满足约束 \\ +\infin x不满足约束 \end{cases} θ(w)={21​∣∣w∣∣2x满足约束+∞x不满足约束​

在xxx满足要求的情况下，我们得到了一个更简单的函数形式θ(w)\theta(w)θ(w)，根据第二步，我们是要求解原函数的最小值，经过等价之后，相当于要求解min⁡wθ(w)\min_{w}\theta(w)minw​θ(w)，也就是满足函数θ(w)\theta(w)θ(w)的最小的www值。也就是

min⁡wθ(w)=min⁡wmax⁡αi≥0L(w,b,α)\min_w{\theta(w)} = \min_w{\max_{\alpha_i\geq0}{L(w,b,\alpha)}} wmin​θ(w)=wmin​αi​≥0max​L(w,b,α)

继续转换成更容易求解的方式：根据拉格朗日函数对偶性，将最小和最大的位置交换一下(至于为什么有对偶性，我是忘记了，不纠结这个东西)，优化的函数就变成对偶问题(公式4)：

max⁡αi≥0min⁡wL(w,b,α)\max_{\alpha_i\geq0}{\min_w{L(w,b,\alpha)}} αi​≥0max​wmin​L(w,b,α)

不过这里要满足这个对偶性，也就是这个max和min可以互换需要满足两个条件：

函数L(w,b,α)L(w,b,\alpha)L(w,b,α)是凸函数满足KKT条件(咱也不懂啥是KKT，既然大佬说满足就满足吧)

对于公式4，先看里面的一部分

min⁡wL(w,b,α)=min⁡w12∣∣w∣∣2−∑i=1Nαi(yi(wxi+b)−1)\min_w{L(w,b,\alpha)} = \min_w\frac{1}{2}||w||^2 - \sum_{i=1}^N{\alpha_i(yi(wx_i+b) - 1)} wmin​L(w,b,α)=wmin​21​∣∣w∣∣2−i=1∑N​αi​(yi(wxi​+b)−1)

先假设其中的α\alphaα为常量，将函数LLL对www和bbb求偏导，令偏导的结果等于0，这样求出来的就是令函数LLL取得最小值的www和bbb。得到结果是：

w=∑i=1Nαiyixi0=∑i=1Nαiyiw=\sum_{i=1}^N{\alpha_iy_ix_i} \\ 0=\sum_{i=1}^N{\alpha_iy_i} w=i=1∑N​αi​yi​xi​0=i=1∑N​αi​yi​

bbb直接没有了，因为求导的时候会得到∂L∂w=∑i=1Nαiyib=0\frac{\partial L}{\partial w} = \sum_{i=1}^N{\alpha_iyib = 0}∂w∂L​=∑i=1N​αi​yib=0，如果b不为0，那么就是0=∑i=1Nαiyi0=\sum_{i=1}^N{\alpha_iy_i}0=∑i=1N​αi​yi​

把上面那两个式子代入到公式4里面去求解α\alphaα，公式4经过一通变形转换就会变成：

∑i=1Nαi−12∑i,j=1NαiαjyiyjxiTxj\sum_{i=1}^N{\alpha_i} - \frac{1}{2}\sum_{i,j=1}^N{\alpha_i\alpha_jy_iy_jx_i^Tx_j} i=1∑N​αi​−21​i,j=1∑N​αi​αj​yi​yj​xiT​xj​

我理解里面αiαj\alpha_i\alpha_jαi​αj​和yiyjy_iy_jyi​yj​是指每个样本之间的内积。

然后，再在这个式子前面加上一个max，然后再加上两个约束条件就是各种转换之后的优化函数了(公式5)：

max⁡α∑i=1Nαi−12∑i,j=1NαiαjyiyjxiTxjs.t.α≥0∑i=1Nαiyi=0\max_{\alpha}{\sum_{i=1}^N{\alpha_i} - \frac{1}{2}\sum_{i,j=1}^N{\alpha_i\alpha_jy_iy_jx_i^Tx_j}} \\ s.t. \alpha \ge 0 \\ \sum_{i=1}^N{\alpha_iy_i} = 0 αmax​i=1∑N​αi​−21​i,j=1∑N​αi​αj​yi​yj​xiT​xj​s.t.α≥0i=1∑N​αi​yi​=0

然后，使用SMO方法来求解这个函数中的α\alphaα，进而再计算出www和bbb。

SMO

​ SMO全称为序列最小优化法：Sequential Minimal Optimizaion。是针对SVM算法的一种数据训练方法，通过不同的迭代计算去算出公式5中合适的一系列α\alphaα。中心思想就是在一系列的α\alphaα中，每次挑选出两个参数：αi\alpha_iαi​和αj\alpha_jαj​，根据约束条件和优化函数计算出这两个参数的调整值，或者是最新值。

​ 先看一下怎么个计算法：

假设算法初始的α\alphaα是随机值，注意初始化的随机值需要大于等于0(约束条件，N个样本对应N个α\alphaα值。

根据某种策略(后面提到一种启发式的方法，这里先当时随机)挑选出两个α\alphaα值，比如就是αi\alpha_iαi​和αj\alpha_jαj​。那么对应的样本就是(xi,yi)(x_i, y_i)(xi​,yi​)和(xj,yj)(x_j, y_j)(xj​,yj​)。

因为存在条件∑i=1Nαiyi=0\sum_{i=1}^N{\alpha_iy_i} = 0∑i=1N​αi​yi​=0，那么我们可以得知αiyi+αjyj=c\alpha_iy_i+\alpha_jy_j = cαi​yi​+αj​yj​=c(公式6), c就等于其他的α\alphaα和yyy的和：∑k,k≠i,jαkyk=−c\sum_{k,k\neq i,j}{\alpha_ky_k} = -c∑k,k​=i,j​αk​yk​=−c。

把公式6两边都乘以yiy_iyi​，就变成αiyiyi+αjyjyi=cyi\alpha_iy_iy_i+\alpha_jy_jy_i = cy_iαi​yi​yi​+αj​yj​yi​=cyi​，因为y∈(1,−1)y \in (1, -1)y∈(1,−1)，所以yiyiy_iy_iyi​yi​肯定等于1，再令s=yiyjs=y_iy_js=yi​yj​，γ=cyi\gamma = cy_iγ=cyi​，公式6可以变换成αi=γ−sαj\alpha_i = \gamma - s\alpha_jαi​=γ−sαj​(公式7)。

把公式7代入到上面的优化函数，也就是公式7中，会得到一个很长的公式，然后针对这个公式求偏导之后就会得到另外一个很长的公式(里面的α2new\alpha_2^{new}α2new​就是我么你这里的αi\alpha_iαi​，根据这两个样本训练得出的值)，令求完偏导后等于0就可以得到：

αjnew=yj(yj−yi+yiγ(xiTxi−xiTxj)+vi−vj)xiTxi+xjTxj−2xiTxj\alpha_j^{new}=\frac{y_j(y_j-y_i+y_i\gamma(x_i^Tx_i-x_i^Tx_j)+v_i-v_j)}{x_i^Tx_i+x_j^Tx_j-2x_i^Tx_j} αjnew​=xiT​xi​+xjT​xj​−2xiT​xj​yj​(yj​−yi​+yi​γ(xiT​xi​−xiT​xj​)+vi​−vj​)​

然后再令Ei=f(xi)−yi,其中f(xi)=xIT+bE_i = f(x_i) - y_i, 其中f(x_i) = x_I^T+bEi​=f(xi​)−yi​,其中f(xi​)=xIT​+b, 令η=xiTxi+xjTxj−2xiTxj\eta = x_i^Tx_i + x_j^Tx_j - 2xi^Tx_jη=xiT​xi​+xjT​xj​−2xiTxj​，就可以得到αi\alpha_iαi​的计算方式：ainew=aiold+yj(Ei−Ej)ηa_i^{new} = a_i^{old} + \frac{y_j(E_i-E_j)}{\eta}ainew​=aiold​+ηyj​(Ei​−Ej​)​。也就是说，每次迭代，都可以在原有的基础上进行更新。其中：

EEE就是误差，η\etaη就是学习率。

根据αjold=γ−sαiold\alpha_j^{old}=\gamma-s\alpha_i^{old}αjold​=γ−sαiold​和αjnew=γ−sαinew\alpha_j^{new}=\gamma-s\alpha_i^{new}αjnew​=γ−sαinew​，两个公式相减，可以得到αjnew=αiold+yiyj(αiold−αinew)\alpha_j^{new} = \alpha_i^{old} + y_iy_j(\alpha_i^{old}-\alpha_i^{new})αjnew​=αiold​+yi​yj​(αiold​−αinew​)

回到第二步，这里的某种策略，一般可以选择两个差异较大α\alphaα，因为两个差别较大的值调整，对目标函数的改变较大，更加容易收敛。

上面迭代结束的条件一般可以设置为，整体误差小于某个值，或者规定迭代多少次。

接下来就是计算bbb，前面求偏导之后，没有获得bbb与α\alphaα之间的关系。这里可以根据其中的一个KKT条件来求解bbb：αi(yif(xi)−1)=0\alpha_i(y_if(x_i)-1) = 0αi​(yi​f(xi​)−1)=0，我们有条件α≥0\alpha\ge0α≥0。假设α=0\alpha=0α=0，不管样本取啥值，都可以满足这个条件，但是，如果某个样本所对应的α=0\alpha = 0α=0，在公式5中就不会起到作用，也就是可以不用考虑这种样本。所以只考虑α≠0\alpha\neq0α​=0的情况，那么就是yi(wTxi+b)=1y_i(w^Tx_i+b) = 1yi​(wTxi​+b)=1（公式8）。这个里面的yiy_iyi​不是等于-1，就是等于1。所以wTxi+bw^Tx_i+bwTxi​+b也是等于1或者-1，符号与yiy_iyi​相同。这样的样本实际上就是在最大间隔上，也就是上面说到的支持向量。

假设讨论的样本中，i=1,j=2i=1, j=2i=1,j=2。把上面的公式8两边乘以y1y_1y1​，就会变成wx1+b=y1wx_1+b = y1wx1​+b=y1，而w=∑i=1Nαiyixiw=\sum_{i=1}^N{\alpha_iy_ix_i}w=∑i=1N​αi​yi​xi​，所以可以得到∑i=1Nαiyixix1+b=y1\sum_{i=1}^N{\alpha_iy_ix_i}x_1+b=y_1∑i=1N​αi​yi​xi​x1​+b=y1​。因为我们已经获得了α1\alpha_1α1​和α2\alpha_2α2​的两个新值，所以，需要将1和2从前面的求和中拆出来，再去更新参数bbb。也就是公式：

b1new=y1−∑i=3NαiyixiTx1−α1newy1x1Tx1−α2newy2x2Tx2b_1^{new}=y_1-\sum_{i=3}^N\alpha_iy_ix_i^Tx_1-\alpha_1^{new}y_1x_1^Tx_1-\alpha_2^{new}y_2x_2^Tx_2 b1new​=y1​−i=3∑N​αi​yi​xiT​x1​−α1new​y1​x1T​x1​−α2new​y2​x2T​x2​

根据上面的公式，前面的两项y1−∑i=3NαiyixiTx1y_1-\sum_{i=3}^N\alpha_iy_ix_i^Tx_1y1​−∑i=3N​αi​yi​xiT​x1​又可以变换为：−E1+α1oldy1x1Tx1+α2oldy2x2Tx2-E_1+\alpha_1^{old}y_1x_1^Tx_1+\alpha_2^{old}y_2x_2^Tx_2−E1​+α1old​y1​x1T​x1​+α2old​y2​x2T​x2​，然后，就可以得到

b1new=bold−E1−y1(α1new−α1old)x1Tx1−y2(α2new−α2old)x2Tx1b_1^{new} = b^{old}-E_1-y_1(\alpha_1^{new}-\alpha_1{old})x_1^Tx_1-y_2(\alpha_2^{new}-\alpha_2{old})x_2^Tx_1 b1new​=bold−E1​−y1​(α1new​−α1​old)x1T​x1​−y2​(α2new​−α2​old)x2T​x1​

同样，可得到：

b2new=bold−E2−y1(α1new−α1old)x1Tx2−y2(α2new−α2old)x2Tx2b_2^{new} = b^{old}-E_2-y_1(\alpha_1^{new}-\alpha_1{old})x_1^Tx_2-y_2(\alpha_2^{new}-\alpha_2{old})x_2^Tx_2 b2new​=bold−E2​−y1​(α1new​−α1​old)x1T​x2​−y2​(α2new​−α2​old)x2T​x2​

如果两个样本都是支持向量，那么b1new=b2newb_1^{new} = b_2^{new}b1new​=b2new​，随便取一个就行，如果不相等，取均值：(b1new+b2new)/2(b_1^{new}+b_2^{new})/2(b1new​+b2new​)/2

迭代求出bbb和α\alphaα后，就可以可以根据w=∑i=1Nαiyixiw=\sum_{i=1}^N{\alpha_iy_ix_i}w=∑i=1N​αi​yi​xi​计算得到最后一个参数www，最终确认模型。

软间隔

​ 看下下面这样的分布图：

​ 假设一个超平面可以将绝大部分的样本分开，只有少数几个样本没法分开。其实我们是接受这样的超平面划分的，但是上面提到的“硬间隔”就没法进行这样的划分，所以就有这“软间隔”这一说。

​ “软间隔”的话，也就是某些样本不满足条件yif(xi)≥1y_if(x_i)\ge1yi​f(xi​)≥1。当然，我们希望这样的样本越少越好。那么优化的目标函数就变成(公式10)：

min⁡w,b12∣∣w∣∣2+C∑i=1Nρ0/1(yi(wTxi+b)−1)\min_{w,b}{\frac{1}{2}||w||^2}+C\sum_{i=1}^N{\rho_{0/1}(y_i(w^Tx_i+b)-1)} w,bmin​21​∣∣w∣∣2+Ci=1∑N​ρ0/1​(yi​(wTxi​+b)−1)

​ 就是在原优化函数的后面加了一截，这一截里面的C表示一个大于0的常数，ρ\rhoρ为一个损失函数：

ρ={1,ifz<00,otherwise\rho = \begin{cases}1, if z<0 \\ 0, otherwise\end{cases} ρ={1,ifz<00,otherwise​

如果C为无穷大，那么就要求函数ρ\rhoρ的取值必须为0，因为如果ρ\rhoρ不为0，这个函数就没有解了，函数的后面一截就是无穷大，没法求最小值。如果ρ\rhoρ要为0，就必须保证自变量Z≥0Z \ge0Z≥0，也就是说yi(wTxi+b)≥1y_i(w^Tx_i+b)\ge1yi​(wTxi​+b)≥1，也就是样本点都满足条件，那么就是原目标函数。如果C为有限值，就允许某些样本点不满足条件，使得Z<0Z<0Z<0，这样我们的目标函数才有可能有解。我理解是如果不满足条件的样本越少，后面一截的值就越小，目标函数的解就越容易一点。

这里还引入了一个变量，叫做“松弛变量”：ξ,ξ=ρ0/1(yi(wTxi+b)−1)\xi, \xi=\rho_{0/1}(y_i(w^Tx_i+b)-1)ξ,ξ=ρ0/1​(yi​(wTxi​+b)−1)，至于为啥叫松弛变量，就不清楚了。

然后针对这个目标函数(公式10)同样的转换成对偶问题的函数，不过这里因为后面有另外一截，所以有两个拉格朗日乘子：α\alphaα和μ\muμ。在KKT条件中需要增加两条：μi≥0\mu_i\ge0μi​≥0, ξiμi=0\xi_i\mu_i=0ξi​μi​=0。同样，不知道为啥，知道这个结论就好。

然后，和硬间隔类似，对对偶问题的L(w,b,α,μ,ξ)L(w,b,\alpha,\mu,\xi)L(w,b,α,μ,ξ)中的ξ\xiξ求偏导等于0后可以得到一个条件：C=αi+μiC=\alpha_i+\mu_iC=αi​+μi​，也就是说这个常量C由两个朗格朗日乘子确定。

因为α≥0\alpha\ge0α≥0，μ≥0\mu\ge0μ≥0，所以在求解公式5的时候，需要增加一个条件：C≥αi≥0C\ge\alpha_i\ge0C≥αi​≥0。

由上面一堆公式可以推出(各位看官联合上面的一堆公式一起看)：若αi<C\alpha_i<Cαi​<C,则μi>0,(αi+μi=C)\mu_i>0, (\alpha_i+\mu_i=C)μi​>0,(αi​+μi​=C)，进而有ξ=0\xi=0ξ=0，所以此时有：yf(xi)=1yf(x_i)=1yf(xi​)=1，即该样本恰好在最大间隔边界上；若αi=C\alpha_i=Cαi​=C，则有μi=0\mu_i=0μi​=0,此时若ξi<=1\xi_i<=1ξi​<=1, 则该样本落在最大间隔内部；若ξi>1\xi_i>1ξi​>1则该样本被错误分类。由此可以看出，软间隔支持向量机的最终模型仅与支持向量有关。

根据这里的两个α\alphaα还有另外的约束，根据硬间隔内容中的第三步里面的公式6，可以分成两种情况，如果yi≠yjy_i\neq y_jyi​​=yj​，那么可以得到αiold−αjold=c\alpha_i^{old}-\alpha_j^{old}=cαiold​−αjold​=c，配合条件C≥αC\ge\alphaC≥α，可以得到图(抄的图，图中的ζ\zetaζ就是我公式中的ccc)：

从图中清楚的看出，α\alphaα的最小值L=max(0,−c),c<0L=max(0,-c), c<0L=max(0,−c),c<0；最大值为H=min(C−c,C)H=min(C-c,C)H=min(C−c,C)

当yi=yjy_i=y_jyi​=yj​时，可以得到αiold+αjold=c\alpha_i^{old}+\alpha_j^{old}=cαiold​+αjold​=c，可以得到图：

从图中得知，α\alphaα的最小值L=max(0,c−C)L=max(0,c-C)L=max(0,c−C)，最大值H=min(c,C)H=min(c,C)H=min(c,C)

在代码中，需要根据yi,yjy_i, y_jyi​,yj​的取值来判断最大最小值。如果计算得出的α\alphaα超过了最大最小值，就直接赋值为最大最小值。

其他步骤和硬间隔的步骤一致。

简化版SMO代码

​ 截取的是《机器学习实战》中的代码：

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):#转换为numpy的mat存储dataMatrix = np.mat(dataMatIn); labelMat = np.mat(classLabels).transpose()#初始化b参数，统计dataMatrix的维度b = 0; m,n = np.shape(dataMatrix)#初始化alpha参数，设为0alphas = np.mat(np.zeros((m,1)))#初始化迭代次数iter_num = 0#最多迭代matIter次while (iter_num < maxIter):alphaPairsChanged = 0for i in range(m):#步骤1：计算误差EifXi = float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + bEi = fXi - float(labelMat[i])#优化alpha，更设定一定的容错率。if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):#随机选择另一个与alpha_i成对优化的alpha_jj = selectJrand(i,m)#步骤1：计算误差EjfXj = float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + bEj = fXj - float(labelMat[j])#保存更新前的aplpha值，使用深拷贝alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy();#步骤2：计算上下界L和Hif (labelMat[i] != labelMat[j]):L = max(0, alphas[j] - alphas[i])H = min(C, C + alphas[j] - alphas[i])else:L = max(0, alphas[j] + alphas[i] - C)H = min(C, alphas[j] + alphas[i])if L==H: print("L==H"); continue#步骤3：计算etaeta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].Tif eta >= 0: print("eta>=0"); continue#步骤4：更新alpha_jalphas[j] -= labelMat[j]*(Ei - Ej)/eta#步骤5：修剪alpha_jalphas[j] = clipAlpha(alphas[j],H,L)if (abs(alphas[j] - alphaJold) < 0.00001): print("alpha_j变化太小"); continue#步骤6：更新alpha_ialphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])#步骤7：更新b_1和b_2b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].Tb2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T#步骤8：根据b_1和b_2更新bif (0 < alphas[i]) and (C > alphas[i]): b = b1elif (0 < alphas[j]) and (C > alphas[j]): b = b2else: b = (b1 + b2)/2.0#统计优化次数alphaPairsChanged += 1#打印统计信息print("第%d次迭代 样本:%d, alpha优化次数:%d" % (iter_num,i,alphaPairsChanged))#更新迭代次数if (alphaPairsChanged == 0): iter_num += 1else: iter_num = 0print("迭代次数: %d" % iter_num)return b,alphas

其他

核函数

​ 当样本集D=(xi,yi),i∈ND={(x_i,y_i), i\in N}D=(xi​,yi​),i∈N在ddd维空间中不是线性可分时，也就是一个超平面无法有效分开这些样本时，可以通过一个函数将样本集从ddd维升到d+1d+1d+1维，从而从高维上来进行划分。这个从ddd维到d+1d+1d+1维的过程就是通过核函数来实现。

​ 我理解核函数可以形成一个矩阵M，将数据集从一个n∗dn*dn∗d的矩阵乘以这个矩阵M后就可以变成一个新的矩阵n∗(d+1)n*(d+1)n∗(d+1)。

​ 这个矩阵的样子就是：

​ 核函数有以下几种常用的：

​ 核函数的应用就超出我的数学理解范围了，知道了就好。

SVM回归

​ 使用SVM解决回归问题，也就是连续值得问题，可以参考西瓜书，懒得写了，太累。