一、硬间隔SVM

1. 模型定义

假设有以下数据：

$\left \{(x_{i},y_{i})\right \}_{i=1}^{N},x_{i}\in \mathbb{R}^{p},y_{i}\in \{+1,-1\}${(xi​,yi​)}i=1N​,xi​∈Rp,yi​∈{+1,−1}

SVM的主要思想是在特征空间中寻找一个最大间隔的超平面$w^{T}x+b$wTx+b实现数据的二分类，SVM属于判别模型。这里的间隔指的是样本点到分离超平面的距离的最小值，用函数$margin(w,b)$margin(w,b)来表达。下图中在$w\cdot x+b=1$w⋅x+b=1和$w\cdot x+b=-1$w⋅x+b=−1线上的样本点就叫支持向量：

超平面实现将数据的正例和负例分隔开，因此有：

$\left.\begin{matrix} y_{i}=+1,w^{T}x_{i}+b>0\\ y_{i}=-1,w^{T}x_{i}+b<0 \end{matrix}\right\}y_{i}(w^{T}x_{i}+b)>0,for\; \forall i=1,2,\cdots ,N$yi​=+1,wTxi​+b>0yi​=−1,wTxi​+b<0​}yi​(wTxi​+b)>0,for∀i=1,2,⋯,N

另外最大间隔通过以下方式来表达：

$①\; 首先要明确样本点到超平面的距离公式：\\ distance(w,b,x_{i})=\frac{\left | w^{T}x+b\right |}{\left \| w\right \|}\\ (可以参考初中知识点：点到直线距离d=\frac{\left | Ax+By+C\right |}{\sqrt{A^{2}+B^{2}}})\\ ②\; 因此间隔可以表达为：\\ margin(w,b)=\underset{x_{i}}{min}\; distance(w,b,x_{i})=\underset{x_{i}}{min}\frac{\left | w^{T}x_{i}+b\right |}{\left \| w\right \|},i=1,2,\cdots ,N\\ ③\; 最大间隔可以表达为：\\ \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{\left | w^{T}x_{i}+b\right |}{\left \| w\right \|}=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N$①首先要明确样本点到超平面的距离公式：distance(w,b,xi​)=∥w∥∣∣​wTx+b∣∣​​(可以参考初中知识点：点到直线距离d=A2+B2​∣Ax+By+C∣​)②因此间隔可以表达为：margin(w,b)=xi​min​distance(w,b,xi​)=xi​min​∥w∥∣∣​wTxi​+b∣∣​​,i=1,2,⋯,N③最大间隔可以表达为：w,bmax​margin(w,b)=w,bmax​xi​min​∥w∥∣∣​wTxi​+b∣∣​​=w,bmax​xi​min​∥w∥yi​(wTxi​+b)​,i=1,2,⋯,N

然后求解支持向量机就可以转化为以下带约束的优化问题：

$\left\{\begin{matrix} \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N\\ s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N \end{matrix}\right.${w,bmax​margin(w,b)=w,bmax​xi​min​∥w∥yi​(wTxi​+b)​,i=1,2,⋯,Ns.t.yi​(wTxi​+b)>0,i=1,2,⋯,N​

上述优化问题还可以进一步转化：

$由约束y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N可以得出\\ \exists \gamma >0使得\underset{x_{i}}{min}\; y_{i}(w^{T}x_{i}+b)=\gamma \\ 由于确定同一个超平面的w,b可以任意放缩，所以这里的\gamma 可以约束等于1。\\ 则\underset{w,b}{max}\; margin(w,b)\\ =\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|}\\ =\underset{w,b}{max}\frac{1}{\left \| w\right \|}\underset{=\gamma =1}{\underbrace{\underset{x_{i}}{min}\; y_{i}(w^{T}x_{i}+b)}}\\ =\underset{w,b}{max}\frac{1}{\left \| w\right \|}\\ =\underset{w,b}{min}\frac{1}{2}w^{T}w\\ i=1,2,\cdots ,N$由约束yi​(wTxi​+b)>0,i=1,2,⋯,N可以得出∃γ>0使得xi​min​yi​(wTxi​+b)=γ由于确定同一个超平面的w,b可以任意放缩，所以这里的γ可以约束等于1。则w,bmax​margin(w,b)=w,bmax​xi​min​∥w∥yi​(wTxi​+b)​=w,bmax​∥w∥1​=γ=1xi​min​yi​(wTxi​+b)​​=w,bmax​∥w∥1​=w,bmin​21​wTwi=1,2,⋯,N

由此上述优化问题转化为：

$\left\{\begin{matrix} \underset{w,b}{min}\frac{1}{2}w^{T}w\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.${w,bmin​21​wTws.t.yi​(wTxi​+b)≥1,i=1,2,⋯,N​

这是一个带N个约束的凸优化问题。

2. 优化问题的转化

上述优化问题可以使用拉格朗日乘子法来求解，构建拉格朗日函数：

$L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ \lambda =\begin{pmatrix} \lambda _{1} & \lambda _{2} & \cdots & \lambda _{N} \end{pmatrix}^{T}$L(w,b,λ)=21​wTw+i=1∑N​λi​(1−yi​(wTxi​+b))λ=(λ1​​λ2​​⋯​λN​​)T

然后上述优化问题就可以转换为以下优化问题：

$\left\{\begin{matrix} \underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.${w,bmin​λmax​L(w,b,λ)=21​wTw+∑i=1N​λi​(1−yi​(wTxi​+b))s.t.λi​≥0,i=1,2,⋯,N​

我们可以简单地看一下为什么可以这么转化：

$当1-y_{i}(w^{T}x_{i}+b)>0时，由于\lambda _{i}\geq 0，所以\underset{\lambda }{max}L(w,b,\lambda )=\infty \\ 当1-y_{i}(w^{T}x_{i}+b)\leq 0时，由于\lambda _{i}\geq 0，所以\underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w\\ 因此\underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\underset{w,b}{min}\left \{\frac{1}{2}w^{T}w,\infty \right \}=\frac{1}{2}w^{T}w$当1−yi​(wTxi​+b)>0时，由于λi​≥0，所以λmax​L(w,b,λ)=∞当1−yi​(wTxi​+b)≤0时，由于λi​≥0，所以λmax​L(w,b,λ)=21​wTw因此w,bmin​λmax​L(w,b,λ)=w,bmin​{21​wTw,∞}=21​wTw

然后使用以下结论继续对该优化问题进行转化：

$min\; max\; L的对偶问题为max\; min\; L,有以下结论：\\ min\; max\; L\geq max\; min\; L\\ 可以简单地认为对于L先取最大，再从最大里面取最小就一定大于等于先取最小，再从最小里面取最大\\ 类似于“凤尾”\geq “鸡头”\\ 如果min\; max\; L是凸优化问题，所以min\; max\; L=max\; min\; L，为强对偶关系$minmaxL的对偶问题为maxminL,有以下结论：minmaxL≥maxminL可以简单地认为对于L先取最大，再从最大里面取最小就一定大于等于先取最小，再从最小里面取最大类似于“凤尾”≥“鸡头”如果minmaxL是凸优化问题，所以minmaxL=maxminL，为强对偶关系

因此该优化问题可以继续转化：

$\left\{\begin{matrix} \underset{\lambda }{max}\; \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.${λmax​w,bmin​L(w,b,λ)=21​wTw+∑i=1N​λi​(1−yi​(wTxi​+b))s.t.λi​≥0,i=1,2,⋯,N​

总结一下，该优化问题经历了以下转化过程：

$①\; 带约束优化问题\left\{\begin{matrix} \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N\\ s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N \end{matrix}\right.\\ ②\; 带约束优化问题\left\{\begin{matrix} \underset{w,b}{min}\;\frac{1}{2}w^{T}w\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.\\ ③\; 无约束优化问题\left\{\begin{matrix} \underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.\\ ④\; 无约束优化问题\left\{\begin{matrix} \underset{\lambda }{max}\; \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.$①带约束优化问题{w,bmax​margin(w,b)=w,bmax​xi​min​∥w∥yi​(wTxi​+b)​,i=1,2,⋯,Ns.t.yi​(wTxi​+b)>0,i=1,2,⋯,N​②带约束优化问题{w,bmin​21​wTws.t.yi​(wTxi​+b)≥1,i=1,2,⋯,N​③无约束优化问题{w,bmin​λmax​L(w,b,λ)=21​wTw+∑i=1N​λi​(1−yi​(wTxi​+b))s.t.λi​≥0,i=1,2,⋯,N​④无约束优化问题{λmax​w,bmin​L(w,b,λ)=21​wTw+∑i=1N​λi​(1−yi​(wTxi​+b))s.t.λi​≥0,i=1,2,⋯,N​

3. 模型求解

• 对$b$b求导

$\frac{\partial L}{\partial b}=\frac{\partial \sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}(w^{T}x_{i}+b)}{\partial b}=\frac{\partial -\sum_{i=1}^{N}\lambda _{i}y_{i}b}{\partial b}=-\sum_{i=1}^{N}\lambda _{i}y_{i}=0\\ 因此得出\sum_{i=1}^{N}\lambda _{i}y_{i}=0$∂b∂L​=∂b∂∑i=1N​λi​−∑i=1N​λi​yi​(wTxi​+b)​=∂b∂−∑i=1N​λi​yi​b​=−i=1∑N​λi​yi​=0因此得出i=1∑N​λi​yi​=0

• 求解$w$w

$将上一步的结果代入L(w,b,\lambda )\\ L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}w^{T}x_{i}-\underset{=0}{\underbrace{\sum_{i=1}^{N}\lambda _{i}y_{i}b}}\\ =\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}w^{T}x_{i}\\ \frac{\partial L}{\partial w}=w-\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}=0\\ 得出w^{*}=\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}$将上一步的结果代入L(w,b,λ)L(w,b,λ)=21​wTw+i=1∑N​λi​−i=1∑N​λi​yi​wTxi​−=0i=1∑N​λi​yi​b​​=21​wTw+i=1∑N​λi​−i=1∑N​λi​yi​wTxi​∂w∂L​=w−i=1∑N​λi​yi​xi​=0得出w∗=i=1∑N​λi​yi​xi​

这里我们可以看出$w^{*}$w∗是数据的线性组合。

• 得出$\underset{w,b}{min}\;L(w,b,\lambda )$w,bmin​L(w,b,λ)

$接着将上一步的结果代入L(w,b,\lambda )\\ \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}(\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i})^{T}(\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}(\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})^{T}x_{i}\\ =\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}{\color{Red}{x_{j}^{T}x_{i}}}+\sum_{i=1}^{N}\lambda _{i}\\ =\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}{\color{Red}{x_{i}^{T}x_{j}}}+\sum_{i=1}^{N}\lambda _{i}\\ =-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i}$接着将上一步的结果代入L(w,b,λ)w,bmin​L(w,b,λ)=21​(i=1∑N​λi​yi​xi​)T(j=1∑N​λj​yj​xj​)+i=1∑N​λi​−i=1∑N​λi​yi​(j=1∑N​λj​yj​xj​)Txi​=21​i=1∑N​j=1∑N​λi​λj​yi​yj​xiT​xj​−i=1∑N​j=1∑N​λi​λj​yi​yj​xjT​xi​+i=1∑N​λi​=21​i=1∑N​j=1∑N​λi​λj​yi​yj​xiT​xj​−i=1∑N​j=1∑N​λi​λj​yi​yj​xiT​xj​+i=1∑N​λi​=−21​i=1∑N​j=1∑N​λi​λj​yi​yj​xiT​xj​+i=1∑N​λi​

因此该优化问题就相当于：

$\left\{\begin{matrix} \underset{\lambda }{max}\; -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N\\ s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N\\ \sum_{i=1}^{N}\lambda _{i}y_{i}=0 \end{matrix}\right.$⎩⎪⎨⎪⎧​λmax​−21​∑i=1N​∑j=1N​λi​λj​yi​yj​xiT​xj​+∑i=1N​λi​,i=1,2,⋯,Ns.t.yi​(wTxi​+b)>0,i=1,2,⋯,N∑i=1N​λi​yi​=0​

也就相当于：

$\left\{\begin{matrix} \underset{\lambda }{min}\; \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N\\ s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N\\ \sum_{i=1}^{N}\lambda _{i}y_{i}=0 \end{matrix}\right.$⎩⎪⎨⎪⎧​λmin​21​∑i=1N​∑j=1N​λi​λj​yi​yj​xiT​xj​−∑i=1N​λi​,i=1,2,⋯,Ns.t.yi​(wTxi​+b)>0,i=1,2,⋯,N∑i=1N​λi​yi​=0​

• KKT条件

首先定义该优化问题的KKT条件：

$\left\{\begin{matrix} \frac{\partial L}{\partial w}=0,\frac{\partial L}{\partial b}=0\\ \lambda _{i}(1-y_{i}(w^{T}x_{i}+b))=0\\ \lambda _{i}\geq 0\\ 1-y_{i}(w^{T}x_{i}+b)\leq 0 \end{matrix}\right.$⎩⎪⎪⎨⎪⎪⎧​∂w∂L​=0,∂b∂L​=0λi​(1−yi​(wTxi​+b))=0λi​≥01−yi​(wTxi​+b)≤0​

该优化问题满足上述KKT条件，这是由于以下定理：

$原问题、对偶问题具有强对偶关系\Leftrightarrow 满足KKT条件$原问题、对偶问题具有强对偶关系⇔满足KKT条件

KKT条件中$\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))=0$λi​(1−yi​(wTxi​+b))=0也叫松弛互补条件，即$\lambda _{i}$λi​和$1-y_{i}(w^{T}x_{i}+b)$1−yi​(wTxi​+b)总有一个为0。也就是说只有支持向量对应的$\lambda _{i}$λi​才可能有值（$\lambda _{i}\neq 0$λi​​=0），而其他不在$w\cdot x+b=1$w⋅x+b=1和$w\cdot x+b=-1$w⋅x+b=−1上的样本点对应的$\lambda _{i}$λi​一定为$0$0，该性质可以用来求出$b^{*}$b∗。

我们已经根据$\frac{\partial L}{\partial w}=0$∂w∂L​=0求出了$w^{*}$w∗，接下来要求出$b^{*}$b∗，我们可以通过求解$\underset{\lambda }{min}; \frac{1}{2}\sum_{i=1}^{{N}\sum_{j=1}}{N}\lambda {i}\lambda {j}y{i}y{j}x_{i}^{{T}x_{j}-\sum_{i=1}}{N}\lambda _{i},i=1,2,\cdots ,N\ $来得出各个$来得出各个\lambda _{i}$，而这个过程也是支持向量机算法计算量最大的地方，这里我们就不展示过程了。

找出求解得到的不等于$0$0的$\lambda _{i}$λi​，也就是支持向量对应的$\lambda _{i}$λi​，假设其中一个支持向量为$(x_{k},y_{k})$(xk​,yk​)，则有$1-y_{k}(w^{T}x_{k}+b)=0$1−yk​(wTxk​+b)=0，最终可以解得：

$b^{*}=y_{k}-w^{T}x_{k}=y_{k}-\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}^{T}x^{k}$b∗=yk​−wTxk​=yk​−i=1∑N​λi​yi​xiT​xk

二、软间隔SVM

我们的训练数据通常不是理想的线性可分，有时甚至是线性不可分的数据。对于存在噪声的一些数据，我们应该允许一点分类错误，因此我们需要对目标函数进行一些调整：

$\underset{w,b}{min}\; \frac{1}{2}w^{T}w+loss$w,bmin​21​wTw+loss

1. 使用误分类点的个数作为loss

$loss=\sum_{i=1}^{N}I\left \{y_{i}(w^{T}x_{i}+b)<1\right \}$loss=i=1∑N​I{yi​(wTxi​+b)<1}

显然使用的指示函数是不连续的，不利于求解，所以不使用这种loss函数。

2. 使用距离作为loss

$\left.\begin{matrix} 如果y_{i}(w^{T}x_{i}+b)\geq 1,loss=0\\ 如果y_{i}(w^{T}x_{i}+b)< 1,loss=1-y_{i}(w^{T}x_{i}+b) \end{matrix}\right\}loss=max\left \{0,1-y_{i}(w^{T}x_{i}+b)\right \}$如果yi​(wTxi​+b)≥1,loss=0如果yi​(wTxi​+b)<1,loss=1−yi​(wTxi​+b)​}loss=max{0,1−yi​(wTxi​+b)}

该函数为合页损失函数（hinge loss），令$z=y_{i}(w^{T}x_{i}+b)$z=yi​(wTxi​+b)，则$loss$loss对$z$z的图像如下：

3. 软间隔SVM的优化问题

$\left\{\begin{matrix} \underset{w,b}{min}\; \frac{1}{2}w^{T}w+C\sum_{i=1}^{N}max\left \{0,1-y_{i}(w^{T}x_{i}+b)\right \}\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.${w,bmin​21​wTw+C∑i=1N​max{0,1−yi​(wTxi​+b)}s.t.yi​(wTxi​+b)≥1,i=1,2,⋯,N​

引入$\xi _{i}=1-y_{i}(w^{T}x_{i}+b),\xi _{i}\geq 0,i=1,2,\cdots ,N$ξi​=1−yi​(wTxi​+b),ξi​≥0,i=1,2,⋯,N，则该优化问题转化为：

$$\left{\begin{matrix}
\underset{w,b}{min}; \frac{1}{2}w^{{T}w+C\sum_{i=1}}{N}\xi {i}\
s.t.; y{i}(w^{T}x_{i}+b)\geq 1-\xi _{i},i=1,2,\cdots ,N
\end{matrix}\right.\$$

上面的式子中，常数$C$C可以看作允许的错误⽔平，同时上式为了进⼀步消除$max$max符号，对数据集中的每⼀个观测，我们可以认为其⼤部分满⾜约束，但是其中部分违反约束，因此这部分约束变成$y_{i}(w^{T}x_{i}+b)\geq 1-\xi _{i}$yi​(wTxi​+b)≥1−ξi​。

软间隔SVM也是使用拉格朗日乘子法进行求解。

公众号同步更新

---

---