文章目录
- 一、原始目标
* - （一）超平面方程
- （二）严格线性可分问题
- 二、目标解析
- 三、兼容软间隔
- 四、兼容非线性分割
- 五、拉格朗日乘数法
- 六、核函数
- 七、SMO算法
* - （一）无约束最小化
- （二）根据约束条件做修剪
- 八、应用示例
* - （一）SVM函数代码
- （二）绘图代码
- （三）线性分割效果
- （四）非线性分割效果
通俗来讲，所谓支持向量机是一种分类器，对于做出标记的两组向量，给出一个最优分割超曲面把这两组向量分割到两边，使得两组向量中离此超平面最近的向量（即所谓支持向量）到此超平面的距离都尽可能远。
一、原始目标
（一）超平面方程
所谓向量，可以简单理解成在直角坐标系中由原点出发，指向某一坐标点的一个剪头，因此它只有两个特征，大小和方向，如下图（以二维空间为例）中x \boldsymbol x x。所谓n n n维超平面（hyperplane）是指在n n n维内积空间中，所有在同一个法向量（如下图中w \boldsymbol w w）上投影长度相同的向量组成的集合，如下图中超平面。
设法向量w = [ w 1 w 2 ⋯ w n ] T \boldsymbol w = [\begin{matrix} w_1 & w_2 & \cdots & w_n\end{matrix}]^T w =[w 1 w 2 ⋯w n ]T，其模长为：
∥ w ∥ = w 1 2 + w 2 2 + ⋯ + w n 2 \| \boldsymbol w \| = \sqrt{w^2_1+w^2_2+\cdots +w^2_n}∥w ∥=w 1 2 +w 2 2 +⋯+w n 2 在上图中记为长度a a a。超平面上的所有向量在法向量方向上的投影长度都相同，记为l l l，即原点到此超平面的距离，所以由内积定义可知，超平面上的任一向量x = [ x 1 x 2 ⋯ x n ] T \boldsymbol x = [\begin{matrix} x_1 & x_2 & \cdots & x_n\end{matrix}]^T x =[x 1 x 2 ⋯x n ]T与此法向量w \boldsymbol w w的内积绝对值就是其在法向量方向投影与法向量模长的乘积，即
∣ w T x ∣ = ∣ w 1 x 1 + w 2 x 2 + ⋯ + w n x n ∣ = a l |\boldsymbol w^T \boldsymbol x | = |w_1x_1+w_2x_2+ \cdots + w_nx_n|=al ∣w T x ∣=∣w 1 x 1 +w 2 x 2 +⋯+w n x n ∣=a l由于一旦法向量和超平面固定，a a a和l l l就都是固定值，所以可将上式中a l al a l改写成− b -b −b，并赋予b > 0 b>0 b >0的含义是向量x \boldsymbol x x投影方向与超平面在法向量反方向，于是就得到了超平面方程：
w T x + b = 0 \boldsymbol w^T \boldsymbol x + b = 0 w T x +b =0并称其中b b b为超平面的 截距。
对于超平面外一向量y = [ y 1 y 2 ⋯ y n ] T \boldsymbol y = [\begin{matrix} y_1 & y_2 & \cdots & y_n\end{matrix}]^T y =[y 1 y 2 ⋯y n ]T，同理可知该向量与超平面法向量的内积绝对值为：
∣ w T y ∣ = ∣ w 1 y 1 + w 2 y 2 + ⋯ + w n y n ∣ = a d |\boldsymbol w^T \boldsymbol y| = |w_1y_1+w_2y_2+ \cdots + w_ny_n|=ad ∣w T y ∣=∣w 1 y 1 +w 2 y 2 +⋯+w n y n ∣=a d而在上图中可直观看出向量y \boldsymbol y y到此超平面的距离是h h h，且有如下关系：
h = d − l = a d − a l a = ∣ w T y + b ∣ ∥ w ∥ h=d-l={ad-al \over a}={|\boldsymbol w^T \boldsymbol y+b| \over \| \boldsymbol w \|}h =d −l =a a d −a l =∥w ∥∣w T y +b ∣由此可见，超平面外一向量到超平面的几何距离就等于将该向量代入超平面方程取绝对值后，再除以超平面法向量的模长。
; （二）严格线性可分问题
设n n n维向量空间中有m m m个向量x 1 ∼ x m \boldsymbol x_1 \sim \boldsymbol x_m x 1 ∼x m ，每个向量x i \boldsymbol x_i x i 都对应一个标签y i y_i y i ，其中一部分向量的标签值是1，另一部分向量的标签值是-1，从而区分出两组向量。我们所要做的是在n n n维向量空间中构造一个超平面 ，使得在超平面两侧找到的支持向量（即距离超平面几何距离最短的向量）x s \boldsymbol x_s x s 到此超平面的距离尽可能远，由前述超平面方程可知这个距离为：
d s = ∣ w T x s + b ∣ ∥ w ∥ d_s = {|\boldsymbol w^T \boldsymbol x_s + b| \over \| \boldsymbol w \|}d s =∥w ∥∣w T x s +b ∣同时要满足同标记的向量只能在此超平面的同一边，即
{ w T x i + b > 0 y i = 1 w T x i + b < 0 y i = − 1 \begin{cases} \boldsymbol w^T \boldsymbol x_i + b > 0 & y_i=1 \ \boldsymbol w^T \boldsymbol x_i + b < 0 & y_i=-1 \end{cases}{w T x i +b >0 w T x i +b <0 y i =1 y i =−1 满足上述条件的超平面称为 决策面。
二、目标解析
对于上述约束条件，当y i = 1 y_i=1 y i =1时有w T x i + b > 0 \boldsymbol w^T \boldsymbol x_i + b > 0 w T x i +b >0，等价于必然存在α > 0 \alpha>0 α>0使得w T x i + b > α \boldsymbol w^T \boldsymbol x_i + b > \alpha w T x i +b >α；同理，必然存在− α -\alpha −α使得当y i = − 1 y_i=-1 y i =−1时，w T x i + b < − α \boldsymbol w^T \boldsymbol x_i + b < -\alpha w T x i +b <−α；而由超平面方程可知，w \boldsymbol w w和b b b同比例变化后，方程所描述的仍是同一个超平面，所以上述条件等价于不等式两边同除α \alpha α的结果，即
{ w T x i + b > 1 y i = 1 w T x i + b < − 1 y i = − 1 \begin{cases} \boldsymbol w^T \boldsymbol x_i + b > 1 & y_i=1 \ \boldsymbol w^T \boldsymbol x_i + b < -1 & y_i=-1 \end{cases}{w T x i +b >1 w T x i +b <−1 y i =1 y i =−1 由于所追求的决策面到其两侧支持向量（x s + \boldsymbol x_{s+}x s +和x s − \boldsymbol x_{s-}x s −）的距离相同，可以令上述α \alpha α就等于支持向量代入决策面表达式后的结果，即
{ w T x s + + b = α y s + = 1 w T x s − + b = − α y s − = − 1 \begin{cases} \boldsymbol w^T \boldsymbol x_{s+} + b = \alpha & y_{s+}=1 \ \boldsymbol w^T \boldsymbol x_{s-} + b = -\alpha & y_{s-}=-1 \end{cases}{w T x s ++b =αw T x s −+b =−αy s +=1 y s −=−1 上述条件同样等价于等式两边同除α \alpha α的结果，即
{ w T x s + + b = 1 y s + = 1 w T x s − + b = − 1 y s − = − 1 \begin{cases} \boldsymbol w^T \boldsymbol x_{s+} + b = 1 & y_{s+}=1 \ \boldsymbol w^T \boldsymbol x_{s-} + b = -1 & y_{s-}=-1 \end{cases}{w T x s ++b =1 w T x s −+b =−1 y s +=1 y s −=−1 上述各式等号与不等号两侧再同乘标签值，最终约束条件可简化为:
{ y i ( w T x i + b ) > 1 i ≠ s + 或 s − y i ( w T x i + b ) = 1 i = s + 或 s − \begin{cases} y_i(\boldsymbol w^T \boldsymbol x_i + b) > 1 & i \not= s+ 或 s-\ y_i(\boldsymbol w^T \boldsymbol x_i + b) = 1 & i = s+ 或 s- \end{cases}{y i (w T x i +b )>1 y i (w T x i +b )=1 i =s +或s −i =s +或s −因此，要最大化的目标函数可化为：
d s = ∣ w T x s + b ∣ ∥ w ∥ = 1 ∥ w ∥ d_s = {|\boldsymbol w^T \boldsymbol x_s + b| \over \| \boldsymbol w \|} = {1 \over \| \boldsymbol w \|}d s =∥w ∥∣w T x s +b ∣=∥w ∥1 综上所述，原始目标可以具体描述为如下求条件最值问题：
{ max w 1 ∥ w ∥ s . t . y i ( w T x i + b ) ≥ 1 i = 1 , 2 , ⋯ , m \begin{cases} \max \limits_{\boldsymbol w} {1 \over \| \boldsymbol w \|} \ s.t. \quad y_i(\boldsymbol w^T \boldsymbol x_i + b) \geq 1\ \quad \quad \,\,\, i = 1,2, \cdots,m \end{cases}⎩⎪⎨⎪⎧w max ∥w ∥1 s .t .y i (w T x i +b )≥1 i =1 ,2 ,⋯,m 其中s . t . s.t.s .t .是satisfy to的缩写，即同时满足于的意思。
三、兼容软间隔
在实际问题中，总有可能偶尔出现异常数据，比如个别正标向量跑到了负标向量堆里去了，如果严格分类会造成一部分向量与决策面很近，甚至根本无法分界。如下图所示：
为了容忍个别异常数据，提升模型鲁棒性，实现下图分类效果：
需要对原条件最值问题做调整如下：
{ max w { 1 ∥ w ∥ − C ∑ i = 1 m ξ i } s . t . y i ( w T x i + b ) ≥ 1 − ξ i ξ i ≥ 0 i = 1 , 2 , ⋯ , m \begin{cases} \max \limits_{\boldsymbol w} {{1 \over \| \boldsymbol w \|}-C \sum \limits_{i=1}^m \xi_i} \ s.t. \quad y_i(\boldsymbol w^T \boldsymbol x_i + b) \geq 1-\xi_i\ \quad \quad \,\,\, \xi_i \geq 0 \ \quad \quad \,\,\, i = 1,2, \cdots,m \end{cases}⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧w max {∥w ∥1 −C i =1 ∑m ξi }s .t .y i (w T x i +b )≥1 −ξi ξi ≥0 i =1 ,2 ,⋯,m 其中新增了两个大于0的变量：
- 松弛变量ξ i \xi_i ξi 。当ξ i = 0 \xi_i=0 ξi =0时，说明第i i i个向量要严格遵守分类要求；当0 < ξ i < 1 0 < \xi_i时，说明允许第i i i个向量离决策面的距离比支持向量还近；当ξ i ≥ 1 \xi_i \geq 1 ξi ≥1时，表示允许第i i i个向量可以处在决策面上甚至在决策面另一边。
- 惩罚系数C C C。如果松弛变量的取值不被约束，则相当于此优化问题不再有约束条件了，这样显然不行，因此需要使每个松弛变量都付出代价，即对优化问题产生负面影响，这个影响度就是惩罚系数，该系数越大则越不能容忍例外向量，越小则约能容忍。故而该系数是超参数，即需要人为设定，而非模型训练出来。
; 四、兼容非线性分割
当出现类似下图的分类问题时，无论如何容忍异常向量，也无法做到在平面上用一条直线分割两类向量。
对于上图中的向量分布，实际上需要一条环线才能有效分割两类向量。以平面上二次曲线为例，其方程形式为：
w 0 + w 1 x 1 + w 2 x 2 + w 3 x 1 2 + w 4 x 2 2 + w 5 x 1 x 2 = 0 w_0+w_1x_1+w_2x_2+w_3x^2_1+w_4x^2_2+w_5x_1x_2=0 w 0 +w 1 x 1 +w 2 x 2 +w 3 x 1 2 +w 4 x 2 2 +w 5 x 1 x 2 =0就相当于将原二维向量映射到五维空间后的线性方程，即
w T ϕ ( x ) + b = 0 \boldsymbol w^T \phi(\boldsymbol x)+b=0 w T ϕ(x )+b =0其中
ϕ ( x ) = [ x 1 x 2 x 1 2 x 2 2 x 1 x 2 ] , w = [ w 1 w 2 w 3 w 4 w 5 ] , b = w 0 \phi (\boldsymbol x) = \left [ \begin{matrix} x_1 \ x_2 \ x^2_1 \ x^2_2 \ x_1x_2 \end{matrix} \right], \quad \boldsymbol w = \left [ \begin{matrix} w_1 \ w_2 \ w_3 \ w_4 \ w_5 \end{matrix} \right], \quad b=w_0 ϕ(x )=⎣⎢⎢⎢⎢⎡x 1 x 2 x 1 2 x 2 2 x 1 x 2 ⎦⎥⎥⎥⎥⎤,w =⎣⎢⎢⎢⎢⎡w 1 w 2 w 3 w 4 w 5 ⎦⎥⎥⎥⎥⎤,b =w 0 由此可见，在低维空间无法线性分割的两组向量可以映射到高维空间实现线性分割。为兼容非线性分割问题，需要再次对上述条件最值问题做调整，得到最终目标如下：
{ max w { 1 ∥ w ∥ − C ∑ i = 1 m ξ i } s . t . y i [ w T ϕ ( x i ) + b ] ≥ 1 − ξ i ξ i ≥ 0 i = 1 , 2 , ⋯ , m \begin{cases} \max \limits_{\boldsymbol w} {{1 \over \| \boldsymbol w \|}-C \sum \limits_{i=1}^m \xi_i} \ s.t. \quad y_i[\boldsymbol w^T \phi (\boldsymbol x_i) + b] \geq 1-\xi_i\ \quad \quad \,\,\, \xi_i \geq 0 \ \quad \quad \,\,\, i = 1,2, \cdots,m \end{cases}⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧w max {∥w ∥1 −C i =1 ∑m ξi }s .t .y i [w T ϕ(x i )+b ]≥1 −ξi ξi ≥0 i =1 ,2 ,⋯,m 至此，终于将既兼容软间隔，又兼容非线性分割的SVM模型描述成了条件最值问题。后面就是如何求解此条件最值问题了。
五、拉格朗日乘数法
为便于构造拉格朗日函数后计算梯度，可将原条件最值问题等价为：
{ min w { ∥ w ∥ 2 2 + C ∑ i = 1 m ξ i } s . t . 1 − ξ i − y i [ w T ϕ ( x i ) + b ] ≤ 0 ξ i ≥ 0 i = 1 , 2 , ⋯ , m \begin{cases} \min \limits_{\boldsymbol w} {{ \| \boldsymbol w \|^2 \over 2}+C \sum \limits_{i=1}^m \xi_i} \ s.t. \quad 1-\xi_i – y_i[\boldsymbol w^T \phi (\boldsymbol x_i) + b] \leq 0 \ \quad \quad \,\,\, \xi_i \geq 0 \ \quad \quad \,\,\, i = 1,2, \cdots,m \end{cases}⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧w min {2 ∥w ∥2 +C i =1 ∑m ξi }s .t .1 −ξi −y i [w T ϕ(x i )+b ]≤0 ξi ≥0 i =1 ,2 ,⋯,m 拉格朗日函数的作用是可以把所有约束条件囊括进一个多元函数，通过求该多元函数的最值来得到想要的条件最值。具体原理证明不在此文中详述，我们只需知道所谓拉格朗日函数就是将所有以小于零作为条件的各条件函数分别乘上一个系数，再加上要求最小值的目标函数后组成的多项式。针对上述条件最值问题，可构造拉格朗日函数如下：
L ( w , ξ , b , a , μ ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ξ i + ∑ i = 1 m a i { 1 − ξ i − y i [ w T ϕ ( x i ) + b ] } − ∑ i = 1 m μ i ξ i L(\boldsymbol w, \boldsymbol \xi, b, \boldsymbol a, \boldsymbol \mu) = {1 \over 2}\| \boldsymbol w \|^2 + C \sum \limits_{i=1}^m \xi_i + \sum \limits_{i=1}^m a_i{ 1-\xi_i-y_i[\boldsymbol w^T\phi(\boldsymbol x_i)+b] } – \sum \limits_{i=1}^m \mu_i \xi_i L (w ,ξ,b ,a ,μ)=2 1 ∥w ∥2 +C i =1 ∑m ξi +i =1 ∑m a i {1 −ξi −y i [w T ϕ(x i )+b ]}−i =1 ∑m μi ξi 由于优化的目标是求条件最小值，而约束条件又是一系列不等式，如果直接对上述L L L函数取梯度为零点，则相当于在约束边界上找最小值，但我们想要的效果是最小值只要在约束区域内就行，不一定只能在边界上。也就是说通过L L L函数中( w , ξ , b ) (\boldsymbol w, \boldsymbol \xi, b)(w ,ξ,b )变量（即除去约束条件前的系数变量）求得的最小值位置可能落在约束区域内也可能落在外面，对于这两种情况，我们想要的效果是：
- 如果恰好就落在哪几个约束区域内，则这几个约束条件就可以无视了，即其前面的条件系数就可以为0；
- 如果落在哪几个约束区域外，则这几个约束条件就要起作用，把取值点限定在只能在该条件边界上。
要实现上述目的，我们只需要先在限定条件系数（即a \boldsymbol a a和μ \boldsymbol \mu μ）大于0的同时由这些条件系数求L L L函数最大值后，再通过非条件系数变量( w , ξ , b ) (\boldsymbol w, \boldsymbol \xi, b)(w ,ξ,b )求L L L函数最小值即可。因为约束条件都是约束小于0的，所以
- 一旦某个约束条件被满足了，则该条件项就变成负数了，此时要想让L L L函数值尽可能大，则该条件项前的条件系数就只能变成0，这样第一个想要的效果就满足了；
- 一旦某个约束条件没被满足，则该条件项就变成正数了，此时要想让L L L函数值尽可能大，则该条件项前的条件系数就会尽可能大，甚至到正无穷。而后续还会对L L L函数取最小值，这样就使得这些项前系数取到正无穷的条件项只能取0，即把取值点限定在该条件边界上，从而也满足了第二个想要的效果。
因此，最终的目标可描述为：
min w , ξ , b max a ≥ 0 , μ ≥ 0 L ( w , ξ , b , a , μ ) \min \limits_{\boldsymbol w, \boldsymbol \xi, b} \max \limits_{\boldsymbol a \geq 0, \boldsymbol \mu \geq 0} L(\boldsymbol w, \boldsymbol \xi, b, \boldsymbol a, \boldsymbol \mu)w ,ξ,b min a ≥0 ,μ≥0 max L (w ,ξ,b ,a ,μ)由于取最大结果中的最小值和取最小结果中的最大值效果相同（即拉格朗日对偶性），因此上述问题又等价于:
max a ≥ 0 , μ ≥ 0 min w , ξ , b L ( w , ξ , b , a , μ ) \max \limits_{\boldsymbol a \geq 0, \boldsymbol \mu \geq 0} \min \limits_{\boldsymbol w, \boldsymbol \xi, b} L(\boldsymbol w, \boldsymbol \xi, b, \boldsymbol a, \boldsymbol \mu)a ≥0 ,μ≥0 max w ,ξ,b min L (w ,ξ,b ,a ,μ)第一步先取最小值，通过使L L L函数分别对各自变量的偏导为零可得，即
∇ w , ξ , b L = { ∂ L ∂ w = w − ∑ i = 1 m a i y i ϕ ( x i ) = 0 ∂ L ∂ b = − ∑ i = 1 m a i y i = 0 ∂ L ∂ ξ i = C − a i − μ i = 0 \nabla_{\boldsymbol w, \boldsymbol \xi, b}L= \begin{cases} {\partial L \over \partial \boldsymbol w} = \boldsymbol w – \sum \limits_{i=1}^m a_iy_i \phi (\boldsymbol x_i) = 0 \ {\partial L \over \partial b} = – \sum \limits_{i=1}^m a_iy_i = 0 \ {\partial L \over \partial \xi_i} = C – a_i – \mu_i = 0 \end{cases}∇w ,ξ,b L =⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧∂w ∂L =w −i =1 ∑m a i y i ϕ(x i )=0 ∂b ∂L =−i =1 ∑m a i y i =0 ∂ξi ∂L =C −a i −μi =0 将上述结论代入第一步优化目标得
min w , ξ , b L ( w , ξ , b , a , μ ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ξ i + ∑ i = 1 m a i { 1 − ξ i − y i [ w T ϕ ( x i ) + b ] } − ∑ i = 1 m μ i ξ i = 1 2 w T w + C ∑ i = 1 m ξ i + ∑ i = 1 m a i − ∑ i = 1 m a i ξ i − w T w − b ∑ i = 1 m a i y i − C ∑ i = 1 m ξ i + ∑ i = 1 m a i ξ i = ∑ i = 1 m a i − 1 2 w T w = ∑ i = 1 m a i − 1 2 ∑ i = 1 m ∑ j = 1 m a i a j y i y j ϕ ( x i ) T ϕ ( x j ) \begin{aligned} \min \limits_{\boldsymbol w, \boldsymbol \xi, b} L(\boldsymbol w, \boldsymbol \xi, b, \boldsymbol a, \boldsymbol \mu) &= {1 \over 2}\| \boldsymbol w \|^2 + C \sum \limits_{i=1}^m \xi_i + \sum \limits_{i=1}^m a_i{ 1-\xi_i-y_i[\boldsymbol w^T\phi(\boldsymbol x_i)+b] } – \sum \limits_{i=1}^m \mu_i \xi_i \ &= {1 \over 2} \boldsymbol w^T \boldsymbol w + C \sum \limits_{i=1}^m \xi_i + \sum \limits_{i=1}^m a_i – \sum \limits_{i=1}^m a_i \xi_i – \boldsymbol w^T \boldsymbol w – b \sum \limits_{i=1}^m a_i y_i – C\sum \limits_{i=1}^m \xi_i +\sum \limits_{i=1}^m a_i \xi_i \ &= \sum \limits_{i=1}^m a_i – {1 \over 2}\boldsymbol w^T \boldsymbol w \ &= \sum \limits_{i=1}^m a_i – {1 \over 2}\sum \limits_{i=1}^m \sum \limits_{j=1}^m a_i a_j y_i y_j \phi(\boldsymbol x_i)^T \phi(\boldsymbol x_j) \end{aligned}w ,ξ,b min L (w ,ξ,b ,a ,μ)=2 1 ∥w ∥2 +C i =1 ∑m ξi +i =1 ∑m a i {1 −ξi −y i [w T ϕ(x i )+b ]}−i =1 ∑m μi ξi =2 1 w T w +C i =1 ∑m ξi +i =1 ∑m a i −i =1 ∑m a i ξi −w T w −b i =1 ∑m a i y i −C i =1 ∑m ξi +i =1 ∑m a i ξi =i =1 ∑m a i −2 1 w T w =i =1 ∑m a i −2 1 i =1 ∑m j =1 ∑m a i a j y i y j ϕ(x i )T ϕ(x j )第二步就是进一步求解max a ≥ 0 , μ ≥ 0 min w , ξ , b L ( w , ξ , b , a , μ ) \max \limits_{\boldsymbol a \geq 0, \boldsymbol \mu \geq 0} \min \limits_{\boldsymbol w, \boldsymbol \xi, b} L(\boldsymbol w, \boldsymbol \xi, b, \boldsymbol a, \boldsymbol \mu)a ≥0 ,μ≥0 max w ,ξ,b min L (w ,ξ,b ,a ,μ)，结合上述条件，原条件最值问题可化为如下优化问题：
{ min a { 1 2 ∑ i = 1 m ∑ j = 1 m a i a j y i y j ϕ ( x i ) T ϕ ( x j ) − ∑ i = 1 m a i } s . t . ∑ i = 1 m a i y i = 0 a i , μ i ≥ 0 C − a i − μ i = 0 i = 1 , 2 , ⋯ , m \begin{cases} \min \limits_{\boldsymbol a} {{1 \over 2}\sum \limits_{i=1}^m \sum \limits_{j=1}^m a_i a_j y_i y_j \phi(\boldsymbol x_i)^T \phi(\boldsymbol x_j) – \sum \limits_{i=1}^m a_i} \ s.t. \quad \sum \limits_{i=1}^m a_iy_i = 0 \ \quad \quad \,\,\, a_i,\mu_i \geq 0 \ \quad \quad \,\,\, C – a_i – \mu_i = 0 \ \quad \quad \,\,\, i = 1,2, \cdots,m \end{cases}⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧a min {2 1 i =1 ∑m j =1 ∑m a i a j y i y j ϕ(x i )T ϕ(x j )−i =1 ∑m a i }s .t .i =1 ∑m a i y i =0 a i ,μi ≥0 C −a i −μi =0 i =1 ,2 ,⋯,m 由于
{ μ i ≥ 0 μ i = C − a i ⇒ a i ≤ C \begin{cases} \mu_i \geq 0 \ \mu_i = C – a_i \end{cases} \Rightarrow a_i \leq C {μi ≥0 μi =C −a i ⇒a i ≤C从而得到最终条件最值问题：
{ min a { 1 2 ∑ i = 1 m ∑ j = 1 m a i a j y i y j ϕ ( x i ) T ϕ ( x j ) − ∑ i = 1 m a i } s . t . ∑ i = 1 m a i y i = 0 0 ≤ a i ≤ C i = 1 , 2 , ⋯ , m \begin{cases} \min \limits_{\boldsymbol a} {{1 \over 2}\sum \limits_{i=1}^m \sum \limits_{j=1}^m a_i a_j y_i y_j \phi(\boldsymbol x_i)^T \phi(\boldsymbol x_j) – \sum \limits_{i=1}^m a_i} \ s.t. \quad \sum \limits_{i=1}^m a_iy_i = 0 \ \quad \quad \,\,\, 0 \leq a_i \leq C \ \quad \quad \,\,\, i = 1,2, \cdots,m \end{cases}⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧a min {2 1 i =1 ∑m j =1 ∑m a i a j y i y j ϕ(x i )T ϕ(x j )−i =1 ∑m a i }s .t .i =1 ∑m a i y i =0 0 ≤a i ≤C i =1 ,2 ,⋯,m 上述问题涉及映射到高维空间的向量内积，即ϕ ( x i ) T ϕ ( x j ) \phi(\boldsymbol x_i)^T \phi(\boldsymbol x_j)ϕ(x i )T ϕ(x j )的计算问题，需要引入核函数。
六、核函数
在第四章的例子中，对二维向量做二次曲线分割就需要映射到五维空间，如果三维甚至更高维度向量做高次超曲面分割，所要升的维度将很高，从而造成极大的计算量。因此需找到一种方法，使得两个低维向量无需向高维空间做映射，只需在原维度空间做简单运算，所得结果就等于其映射到高维空间后的内积。这种方法就是核函数，将同是低维度的两个向量代入核函数，所得结果就是其映射到高维空间后的内积，即
ϕ ( x i ) T ϕ ( x j ) = κ ( x i , x j ) \phi(\boldsymbol x_i)^T \phi(\boldsymbol x_j) = \kappa(\boldsymbol x_i, \boldsymbol x_j)ϕ(x i )T ϕ(x j )=κ(x i ,x j )常用的核函数有以下几种：
1、线性核。就表示原空间内积，适用于线性可分问题。
κ ( x i , x j ) = x i T x j \kappa(\boldsymbol x_i, \boldsymbol x_j) = \boldsymbol x_i^T \boldsymbol x_j κ(x i ,x j )=x i T x j 2、高斯核。适用于没有先验经验的非线性分类。其中σ \sigma σ越小，使得映射的维度越高。
κ ( x i , x j ) = exp ( − ∥ x i − x j ∥ 2 2 σ 2 ) \kappa(\boldsymbol x_i, \boldsymbol x_j) = \exp \left( -{\|\boldsymbol x_i – \boldsymbol x_j \|^2 \over 2\sigma^2} \right )κ(x i ,x j )=exp (−2 σ2 ∥x i −x j ∥2 )3、多项式核。适用于没有先验经验的分类。其中d d d越越小，使得映射的维度越高。
κ ( x i , x j ) = ( a x i T x j + c ) d \kappa(\boldsymbol x_i, \boldsymbol x_j) =( a \boldsymbol x^T_i \boldsymbol x_j +c)^d κ(x i ,x j )=(a x i T x j +c )d4、Sigmoid核。此时SVM实现的就是一种多层感知器神经网络。
κ ( x i , x j ) = tanh ( a x i T x j + c ) \kappa(\boldsymbol x_i, \boldsymbol x_j) =\tanh( a \boldsymbol x^T_i \boldsymbol x_j +c)κ(x i ,x j )=tanh (a x i T x j +c )
大多数非线性分割使用高斯核都能很好处理。
七、SMO算法
通过核函数解决了高维向量内积计算问题后，就剩下如何求解出满足约束条件的一组最优条件系数a \boldsymbol a a这最后一个问题了。由于条件系数a i a_i a i 的个数与待分割向量一样多，难以直接计算梯度最低点，故而采用SMO算法，即序列最小优化（Sequential Minimal Optimization）算法。其思路是每次选择两个待优化条件系数而固定其他系数，由约束条件又可以化去一个系数，从而化成一个一元二次函数的求最值问题。对于已满足约束条件的最优解，再使用SMO算法做迭代优化时，是不会改变其结果的，所以当通过两两优化的方式把所有条件系数遍历几遍，各系数已不再有可优化空间后，即得到了最优结果。
（一）无约束最小化
首先选定a 1 a_1 a 1 和a 2 a_2 a 2 做优化，其他系数由于都先被视为常量，所以可以都先无视；并用核函数代替映射到高维空间的向量内积，则前述条件最值问题可化为：
{ min a { 1 2 a 1 2 κ ( x 1 , x 1 ) + 1 2 a 2 2 κ ( x 2 , x 2 ) + y 1 y 2 a 1 a 2 κ ( x 1 , x 2 ) + y 1 a 1 ∑ i = 3 m y i a i κ ( x i , x 1 ) + y 2 a 2 ∑ i = 3 m y i a i κ ( x i , x 2 ) − ( a 1 + a 2 ) } s . t . a 1 y 1 + a 2 y 2 = − ∑ i = 3 m a i y i = ς 0 ≤ a i ≤ C i = 1 , 2 , ⋯ , m \begin{cases} \min \limits_{\boldsymbol a} {{1 \over 2}a_1^2 \kappa(\boldsymbol x_1, \boldsymbol x_1) + {1 \over 2}a_2^2 \kappa(\boldsymbol x_2, \boldsymbol x_2) + y_1y_2a_1a_2\kappa(\boldsymbol x_1, \boldsymbol x_2) + y_1a_1\sum \limits_{i=3}^m y_i a_i \kappa(\boldsymbol x_i, \boldsymbol x_1) + y_2a_2\sum \limits_{i=3}^m y_i a_i \kappa(\boldsymbol x_i, \boldsymbol x_2) – (a_1+a_2) } \ s.t. \quad a_1y_1 + a_2y_2 = – \sum \limits_{i=3}^m a_i y_i = \varsigma\ \quad \quad \,\,\, 0 \leq a_i \leq C \ \quad \quad \,\,\, i = 1,2, \cdots,m \end{cases}⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧a min {2 1 a 1 2 κ(x 1 ,x 1 )+2 1 a 2 2 κ(x 2 ,x 2 )+y 1 y 2 a 1 a 2 κ(x 1 ,x 2 )+y 1 a 1 i =3 ∑m y i a i κ(x i ,x 1 )+y 2 a 2 i =3 ∑m y i a i κ(x i ,x 2 )−(a 1 +a 2 )}s .t .a 1 y 1 +a 2 y 2 =−i =3 ∑m a i y i =ς0 ≤a i ≤C i =1 ,2 ,⋯,m 其中ς \varsigma ς为常数；κ ( x i , x j ) \kappa(\boldsymbol x_i, \boldsymbol x_j)κ(x i ,x j )可简记为κ i j \kappa_{ij}κi j 。由此，上述要最小化的目标函数可记为：
J = 1 2 a 1 2 κ 11 + 1 2 a 2 2 κ 22 + y 1 y 2 a 1 a 2 κ 12 + y 1 a 1 ∑ i = 3 m y i a i κ i 1 + y 2 a 2 ∑ i = 3 m y i a i κ i 2 − ( a 1 + a 2 ) J={1 \over 2}a_1^2 \kappa_{11} + {1 \over 2}a_2^2 \kappa_{22} + y_1y_2a_1a_2 \kappa_{12} + y_1a_1\sum \limits_{i=3}^m y_i a_i \kappa_{i1} + y_2a_2\sum \limits_{i=3}^m y_i a_i \kappa_{i2} – (a_1+a_2)J =2 1 a 1 2 κ1 1 +2 1 a 2 2 κ2 2 +y 1 y 2 a 1 a 2 κ1 2 +y 1 a 1 i =3 ∑m y i a i κi 1 +y 2 a 2 i =3 ∑m y i a i κi 2 −(a 1 +a 2 )由于a 1 y 1 + a 2 y 2 = ς a_1y_1 + a_2y_2 = \varsigma a 1 y 1 +a 2 y 2 =ς，且y i y_i y i 只可能取± 1 \pm 1 ±1，可得a 1 = y 1 ( ς − a 2 y 2 ) a_1=y_1(\varsigma – a_2y_2)a 1 =y 1 (ς−a 2 y 2 )，代入上式对a 2 a_2 a 2 求偏导为：
∂ J ∂ a 2 = ( κ 11 + κ 22 − 2 κ 12 ) a 2 + ( y 2 κ 12 − y 2 κ 11 ) ς − y 2 ∑ i = 3 m y i a i κ i 1 + y 2 ∑ i = 3 m y i a i κ i 2 + y 1 y 2 − 1 {\partial J \over \partial a_2}= (\kappa_{11} + \kappa_{22} – 2 \kappa_{12} ) a_2+ (y_2 \kappa_{12} – y_2 \kappa_{11})\varsigma – y_2\sum \limits_{i=3}^m y_i a_i \kappa_{i1} + y_2\sum \limits_{i=3}^m y_i a_i \kappa_{i2} + y_1y_2 – 1 ∂a 2 ∂J =(κ1 1 +κ2 2 −2 κ1 2 )a 2 +(y 2 κ1 2 −y 2 κ1 1 )ς−y 2 i =3 ∑m y i a i κi 1 +y 2 i =3 ∑m y i a i κi 2 +y 1 y 2 −1令上式等于0，同时将待优化更新的a 2 a_2 a 2 记为a 2 ′ a_2’a 2 ′，区别于其他仍未更新的旧值a i a_i a i ，有：
( κ 11 + κ 22 − 2 κ 12 ) a 2 ′ = ( y 2 κ 11 − y 2 κ 12 ) ς + y 2 ∑ i = 3 m y i a i κ i 1 − y 2 ∑ i = 3 m y i a i κ i 2 − y 1 y 2 + 1 (\kappa_{11} + \kappa_{22} – 2 \kappa_{12} ) a_2′ = (y_2 \kappa_{11} – y_2 \kappa_{12})\varsigma +y_2\sum \limits_{i=3}^m y_i a_i \kappa_{i1} -y_2\sum \limits_{i=3}^m y_i a_i \kappa_{i2} -y_1y_2 + 1 (κ1 1 +κ2 2 −2 κ1 2 )a 2 ′=(y 2 κ1 1 −y 2 κ1 2 )ς+y 2 i =3 ∑m y i a i κi 1 −y 2 i =3 ∑m y i a i κi 2 −y 1 y 2 +1由于
∑ i = 1 m y i a i κ i j = a 1 y 1 κ 1 j + a 2 y 2 κ 2 j + ∑ i = 3 m y i a i κ i j \sum \limits_{i=1}^m y_i a_i \kappa_{ij} =a_1y_1\kappa_{1j} +a_2y_2\kappa_{2j}+\sum \limits_{i=3}^m y_i a_i \kappa_{ij}i =1 ∑m y i a i κi j =a 1 y 1 κ1 j +a 2 y 2 κ2 j +i =3 ∑m y i a i κi j 代入上式可得：
( κ 11 + κ 22 − 2 κ 12 ) a 2 ′ = ( y 2 κ 11 − y 2 κ 12 ) ς + y 2 ( ∑ i = 1 m y i a i κ i 1 − a 1 y 1 κ 11 − a 2 y 2 κ 21 ) − y 2 ( ∑ i = 1 m y i a i κ i 2 − a 1 y 1 κ 12 − a 2 y 2 κ 22 ) − y 1 y 2 + 1 = ( y 2 κ 11 − y 2 κ 12 ) ς + y 2 ∑ i = 1 m y i a i κ i 1 − y 1 y 2 a 1 κ 11 − a 2 κ 21 − y 2 ∑ i = 1 m y i a i κ i 2 + y 1 y 2 a 1 κ 12 + a 2 κ 22 − y 1 y 2 + 1 \begin{aligned} (\kappa_{11} + \kappa_{22} – 2 \kappa_{12} ) a_2′ &= (y_2 \kappa_{11} – y_2 \kappa_{12})\varsigma +y_2(\sum \limits_{i=1}^m y_i a_i \kappa_{i1} -a_1y_1\kappa_{11} – a_2y_2\kappa_{21}) -y_2(\sum \limits_{i=1}^m y_i a_i \kappa_{i2} -a_1y_1\kappa_{12} – a_2y_2\kappa_{22}) -y_1y_2 + 1 \ &=(y_2 \kappa_{11} – y_2 \kappa_{12})\varsigma +y_2\sum \limits_{i=1}^m y_i a_i \kappa_{i1} – y_1y_2a_1\kappa_{11} – a_2\kappa_{21} -y_2\sum \limits_{i=1}^m y_i a_i \kappa_{i2} +y_1y_2a_1\kappa_{12} + a_2\kappa_{22} -y_1y_2 + 1 \end{aligned}(κ1 1 +κ2 2 −2 κ1 2 )a 2 ′=(y 2 κ1 1 −y 2 κ1 2 )ς+y 2 (i =1 ∑m y i a i κi 1 −a 1 y 1 κ1 1 −a 2 y 2 κ2 1 )−y 2 (i =1 ∑m y i a i κi 2 −a 1 y 1 κ1 2 −a 2 y 2 κ2 2 )−y 1 y 2 +1 =(y 2 κ1 1 −y 2 κ1 2 )ς+y 2 i =1 ∑m y i a i κi 1 −y 1 y 2 a 1 κ1 1 −a 2 κ2 1 −y 2 i =1 ∑m y i a i κi 2 +y 1 y 2 a 1 κ1 2 +a 2 κ2 2 −y 1 y 2 +1 为简化表达式，记
E j = ∑ i = 1 m y i a i κ i j − y j E_j = \sum \limits_{i=1}^m y_i a_i \kappa_{ij} – y_j E j =i =1 ∑m y i a i κi j −y j 即
E = [ E 1 E 2 ⋮ E m ] = [ ∑ i = 1 m y i a i κ i 1 − y 1 ∑ i = 1 m y i a i κ i 2 − y 2 ⋮ ∑ i = 1 m y i a i κ i m − y m ] = [ κ 11 κ 12 ⋯ κ 1 m κ 21 κ 22 ⋯ κ 2 m ⋮ ⋮ ⋱ ⋮ κ m 1 κ m 2 ⋯ κ m m ] [ y 1 a 1 y 2 a 2 ⋮ y m a m ] − [ y 1 y 2 ⋮ y m ] \boldsymbol E = \left [ \begin{matrix} E_1\ E_2 \ \vdots \ E_m \end{matrix} \right] = \left [ \begin{matrix} \sum \limits_{i=1}^m y_i a_i \kappa_{i1} – y_1 \ \sum \limits_{i=1}^m y_i a_i \kappa_{i2} – y_2 \ \vdots \ \sum \limits_{i=1}^m y_i a_i \kappa_{im} – y_m \end{matrix} \right] = \left [ \begin{matrix} \kappa_{11} & \kappa_{12} & \cdots & \kappa_{1m} \ \kappa_{21} & \kappa_{22} & \cdots & \kappa_{2m} \ \vdots & \vdots & \ddots & \vdots \ \kappa_{m1} & \kappa_{m2} & \cdots & \kappa_{mm} \ \end{matrix} \right] \left [ \begin{matrix} y_1 a_1 \ y_2 a_2 \ \vdots \ y_m a_m \end{matrix} \right] – \left [ \begin{matrix} y_1\ y_2 \ \vdots \ y_m \end{matrix} \right]E =⎣⎢⎢⎢⎡E 1 E 2 ⋮E m ⎦⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡i =1 ∑m y i a i κi 1 −y 1 i =1 ∑m y i a i κi 2 −y 2 ⋮i =1 ∑m y i a i κi m −y m ⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎡κ1 1 κ2 1 ⋮κm 1 κ1 2 κ2 2 ⋮κm 2 ⋯⋯⋱⋯κ1 m κ2 m ⋮κm m ⎦⎥⎥⎥⎤⎣⎢⎢⎢⎡y 1 a 1 y 2 a 2 ⋮y m a m ⎦⎥⎥⎥⎤−⎣⎢⎢⎢⎡y 1 y 2 ⋮y m ⎦⎥⎥⎥⎤则有：
y 2 ( E 1 − E 2 ） = y 2 ∑ i = 1 m y i a i κ i 1 − y 1 y 2 − y 2 ∑ i = 1 m y i a i κ i 2 + 1 y_2(E_1-E2） = y_2\sum \limits_{i=1}^m y_i a_i \kappa_{i1} – y_1y_2 – y_2\sum \limits_{i=1}^m y_i a_i \kappa_{i2} + 1 y 2 (E 1 −E 2 ）=y 2 i =1 ∑m y i a i κi 1 −y 1 y 2 −y 2 i =1 ∑m y i a i κi 2 +1代入前式可化简为：
( κ 11 + κ 22 − 2 κ 12 ) a 2 ′ = ( y 2 κ 11 − y 2 κ 12 ) ς − y 1 y 2 a 1 κ 11 − a 2 κ 21 + y 1 y 2 a 1 κ 12 + a 2 κ 22 + y 2 ( E 1 − E 2 ) (\kappa_{11} + \kappa_{22} – 2 \kappa_{12} ) a_2′ = (y_2 \kappa_{11} – y_2 \kappa_{12})\varsigma -y_1y_2a_1\kappa_{11} – a_2\kappa_{21} +y_1y_2a_1\kappa_{12} + a_2\kappa_{22} +y_2(E_1-E_2)(κ1 1 +κ2 2 −2 κ1 2 )a 2 ′=(y 2 κ1 1 −y 2 κ1 2 )ς−y 1 y 2 a 1 κ1 1 −a 2 κ2 1 +y 1 y 2 a 1 κ1 2 +a 2 κ2 2 +y 2 (E 1 −E 2 )再将a 1 = y 1 ( ς − a 2 y 2 ) a_1=y_1(\varsigma – a_2y_2)a 1 =y 1 (ς−a 2 y 2 )代入上式可得：
( κ 11 + κ 22 − 2 κ 12 ) a 2 ′ = y 2 κ 11 ς − y 2 κ 12 ς − y 2 ( ς − a 2 y 2 ) κ 11 − a 2 κ 21 + y 2 ( ς − a 2 y 2 ) κ 12 + a 2 κ 22 + y 2 ( E 1 − E 2 ) = a 2 κ 11 − a 2 κ 21 − a 2 κ 12 + a 2 κ 22 + y 2 ( E 1 − E 2 ) = ( κ 11 + κ 22 − 2 κ 12 ) a 2 + y 2 ( E 1 − E 2 ) \begin{aligned} (\kappa_{11} + \kappa_{22} – 2 \kappa_{12} ) a_2′ &= y_2 \kappa_{11} \varsigma – y_2 \kappa_{12}\varsigma -y_2(\varsigma – a_2y_2)\kappa_{11} – a_2\kappa_{21} +y_2(\varsigma – a_2y_2)\kappa_{12} + a_2\kappa_{22} +y_2(E_1-E_2) \ &=a_2 \kappa_{11} – a_2 \kappa_{21} – a_2 \kappa_{12} + a_2 \kappa_{22} + y_2(E_1-E_2) \ &=(\kappa_{11} + \kappa_{22} – 2 \kappa_{12})a_2 + y_2(E_1-E_2) \end{aligned}(κ1 1 +κ2 2 −2 κ1 2 )a 2 ′=y 2 κ1 1 ς−y 2 κ1 2 ς−y 2 (ς−a 2 y 2 )κ1 1 −a 2 κ2 1 +y 2 (ς−a 2 y 2 )κ1 2 +a 2 κ2 2 +y 2 (E 1 −E 2 )=a 2 κ1 1 −a 2 κ2 1 −a 2 κ1 2 +a 2 κ2 2 +y 2 (E 1 −E 2 )=(κ1 1 +κ2 2 −2 κ1 2 )a 2 +y 2 (E 1 −E 2 )因此：
a 2 ′ = a 2 + y 2 E 1 − E 2 κ 11 + κ 22 − 2 κ 12 a_2′ = a_2 + y_2{E_1-E_2 \over \kappa_{11} + \kappa_{22} – 2 \kappa_{12}}a 2 ′=a 2 +y 2 κ1 1 +κ2 2 −2 κ1 2 E 1 −E 2 上式右侧a 2 a_2 a 2 是未更新的旧值。此时得到的a 2 ′ a_2’a 2 ′还并没有考虑约束条件0 ≤ a i ≤ C 0 \leq a_i \leq C 0 ≤a i ≤C ，因此还有待修剪。为方便区分，最终修剪后的各条件系数记为a ^ i \hat a_i a ^i
（二）根据约束条件做修剪
结合约束条件0 ≤ a i ≤ C 0 \leq a_i \leq C 0 ≤a i ≤C及a 1 y 1 + a 2 y 2 = ς a_1y_1 + a_2y_2 = \varsigma a 1 y 1 +a 2 y 2 =ς，可确定( a ^ 1 , a ^ 2 ) (\hat a_1, \hat a_2)(a ^1 ,a ^2 )的坐标只能落在下图方框中：
由y 1 y_1 y 1 和y 2 y_2 y 2 的不同取值可分四种情况讨论：
- 当y 1 = y 2 = 1 y_1=y_2=1 y 1 =y 2 =1时，有a ^ 2 = − a ^ 1 + ς \hat a_2 = -\hat a_1+\varsigma a ^2 =−a ^1 +ς。此时ς ≥ 0 \varsigma \geq 0 ς≥0，如上面左图所示，区分ς \varsigma ς与C C C的位置关系做分类讨论如下：
（1）当0 ≤ ς ≤ C 0 \leq \varsigma \leq C 0 ≤ς≤C时，a ^ 1 ∈ [ 0 , ς ] \hat a_1 \in [0, \varsigma]a ^1 ∈[0 ,ς]，所以a ^ 2 ∈ [ 0 , ς = a 1 + a 2 ] \hat a_2 \in [0, \varsigma=a_1+a_2]a ^2 ∈[0 ,ς=a 1 +a 2 ]。
（2）当C ≤ ς ≤ 2 C C \leq \varsigma \leq 2C C ≤ς≤2 C时，a ^ 1 ∈ [ ς − C , C ] \hat a_1 \in [\varsigma-C, C]a ^1 ∈[ς−C ,C ]，所以a ^ 2 ∈ [ ς − C = a 1 + a 2 − C , C ] \hat a_2 \in [\varsigma-C=a_1+a_2-C, C]a ^2 ∈[ς−C =a 1 +a 2 −C ,C ]。 - 当y 1 = y 2 = − 1 y_1=y_2=-1 y 1 =y 2 =−1时，有a ^ 2 = − a ^ 1 − ς \hat a_2 = -\hat a_1-\varsigma a ^2 =−a ^1 −ς。此时ς ≤ 0 \varsigma \leq 0 ς≤0，将此处取负值的ς \varsigma ς换成上述取正值的ς \varsigma ς，可得与上述相同的结果。
- 当y 1 = 1 y_1=1 y 1 =1，y 2 = − 1 y_2=-1 y 2 =−1时，有a ^ 2 = a ^ 1 − ς \hat a_2 = \hat a_1-\varsigma a ^2 =a ^1 −ς。此时− C ≤ ς ≤ C -C \leq \varsigma \leq C −C ≤ς≤C，如上面右图所示，区分ς \varsigma ς与0 0 0的位置关系做分类讨论如下：
（1）当− C ≤ ς ≤ 0 -C \leq \varsigma \leq 0 −C ≤ς≤0时，a ^ 1 ∈ [ 0 , C + ς ] \hat a_1 \in [0, C+\varsigma]a ^1 ∈[0 ,C +ς]，所以a ^ 2 ∈ [ − ς = a 2 − a 1 , C ] \hat a_2 \in [-\varsigma=a_2-a_1, C]a ^2 ∈[−ς=a 2 −a 1 ,C ]。
（2）当0 ≤ ς ≤ C 0 \leq \varsigma \leq C 0 ≤ς≤C时，a ^ 1 ∈ [ ς , C ] \hat a_1 \in [\varsigma, C]a ^1 ∈[ς,C ]，所以a ^ 2 ∈ [ 0 , C − ς = C + a 2 − a 1 ] \hat a_2 \in [0, C-\varsigma=C+a_2-a_1]a ^2 ∈[0 ,C −ς=C +a 2 −a 1 ]。 - 当y 1 = − 1 y_1=-1 y 1 =−1，y 2 = 1 y_2=1 y 2 =1时，有a ^ 2 = a ^ 1 + ς \hat a_2 = \hat a_1 + \varsigma a ^2 =a ^1 +ς。同理可将此处ς \varsigma ς换成− ς -\varsigma −ς，可得与上述相同的结果。
综上可得a ^ 2 \hat a_2 a ^2 的取值上下界为：
{ i f ( y 1 = y 2 ) L = max { 0 , a 1 + a 2 − C } H = min { a 1 + a 2 , C } i f ( y 1 ≠ y 2 ) L = max { a 2 − a 1 , 0 } H = min { C , C + a 2 − a 1 } \begin{cases} if(y_1 = y_2) \quad L=\max{ 0, a_1+a_2-C} & H=\min{ a_1+a_2,C} \ if(y_1 \not = y_2) \quad L=\max{ a_2-a_1,0} & H=\min{C, C+a_2-a_1} \end{cases}{i f (y 1 =y 2 )L =max {0 ,a 1 +a 2 −C }i f (y 1 =y 2 )L =max {a 2 −a 1 ,0 }H =min {a 1 +a 2 ,C }H =min {C ,C +a 2 −a 1 }注意，上述a 1 a_1 a 1 和a 2 a_2 a 2 都是指本轮更新前的原值。至此可得：
a ^ 2 = { H a 2 ′ > H a 2 ′ L ≤ a 2 ′ ≤ H L a 2 ′ < H a ^ 1 = y 1 ( ς − a ^ 2 y 2 ) = y 1 [ ( y 1 a 1 + y 2 a 2 ) − a ^ 2 y 2 ] = a 1 + y 1 y 2 ( a 2 − a ^ 2 ) \begin{aligned} \hat a_2 &= \begin{cases} H & a_2′ > H \ a_2′ & L \leq a_2′ \leq H \ L & a_2′ < H \ \end{cases} \ \hat a_1 &= y_1(\varsigma-\hat a_2 y_2)=y_1[(y_1a_1+y_2a_2)-\hat a_2y_2]=a_1+y_1y_2(a_2-\hat a_2) \end{aligned}a ^2 a ^1 =⎩⎪⎨⎪⎧H a 2 ′L a 2 ′>H L ≤a 2 ′≤H a 2 ′<H =y 1 (ς−a ^2 y 2 )=y 1 [(y 1 a 1 +y 2 a 2 )−a ^2 y 2 ]=a 1 +y 1 y 2 (a 2 −a ^2 )以此类推，将所有条件系数a i a_i a i 遍历更新几遍后即得到最终优化后的一组条件系数a ^ i \hat a_i a ^i 。
由第五章可知，在拉格朗日函数中，对于不等式约束条件项，要么该约束条件表达式取0，要么该条件项前的条件系数取0（即所谓KKT条件），即若a ^ s ≠ 0 \hat a_s \not= 0 a ^s =0，则y s ( ∑ i = 1 m a i y i κ i s + b ) ≥ 1 − ξ s y_s(\sum \limits_{i=1}^m a_iy_i \kappa_{is} + b) \geq 1-\xi_s y s (i =1 ∑m a i y i κi s +b )≥1 −ξs ，也就是说该x s \boldsymbol x_s x s 向量要么是支持向量，即ξ s = 0 \xi_s=0 ξs =0；要么就是被容忍的异常向量，即ξ s > 0 \xi_s>0 ξs >0。对于支持向量，有
b = y s − ∑ i = 1 m a i y i κ i s = − E s b = y_s – \sum \limits_{i=1}^m a_iy_i \kappa_{is} = -E_s b =y s −i =1 ∑m a i y i κi s =−E s 所以我们只需找到支持向量就可求得决策面截距。同时上式也说明凡支持向量，其对应的偏移量E E E都是相等的，所以我们只需要找到所有条件系数不为零的特殊向量，再从这些特殊向量所对应的偏移量中找到出现次数最多的值，就是支持向量的偏移量，再取负数就得到了决策面的截距b ^ \hat b b ^。最终得到决策面方程为：
∑ i = 1 m a ^ i y i κ ( x i , x ) + b ^ = 0 \sum \limits_{i=1}^m \hat a_iy_i \kappa(\boldsymbol x_i, \boldsymbol x) + \hat b = 0 i =1 ∑m a ^i y i κ(x i ,x )+b ^=0
; 八、应用示例
（一）SVM函数代码
import numpy as np
import numpy.matlib as matlib
import numpy.random as random
from collections import Counter
def gaussKernel(X, Y, sigma=3):
'''
Parameters
----------
X : np.matrix
一个n行m列矩阵，代表m个n维向量。
Y : np.matrix
一个n行m列矩阵，代表另外m个n维向量。
sigma : float
调控参数。越小映射的空间维度约高。默认为3。
Returns
-------
K : np.matrix
一个m行1列矩阵，其中k_i = exp[-(||X_i-Y_i||^2)/(2*sigma^2)]。
Examples
--------
X = np.matrix('1, 2, 3; 4, 5, 6').T
Y = np.matrix('1, 3, 5; 2, 4, 6').T
K = gaussKernel(X, Y, 3)
'''
K = np.exp(-(np.square(X - Y).T * matlib.ones((np.shape(X)[0], 1))) / (2*sigma**2))
return K
def svnSimple(dataMatrix, labelVector, C, maxIter, kernel=None, sigma=3):
'''
Parameters
----------
dataMatrix : np.matrix
一个n行m列矩阵，代表m个n维向量，作为待分类向量。
labelVector : np.matrix
一个由+1和-1组成的1行m列矩矩阵，作为dataMatrix各列向量的标签。
C : float
惩罚系数。一个大于等于0的数值，越接近0则对异常向量的容忍度越高。
maxIter : int
最大遍历次数。对所有条件系数做一次迭代更新为一次遍历。
kernel : function
核函数。用于在低维空间计算映射到高维空间的向量内积。
sigma : float
核函数的调控参数。越小映射的空间维度约高。默认为3。
Returns
-------
A : np.matrix
一个1行m列矩阵，代表最优条件系数向量。
b : float
一个1行1列矩阵，代表决策平面的截距。
Examples
--------
X = np.matrix('1, 1; 4, 3; 3, 3').T
Y = np.matrix('-1, 1, 1')
A, b = svnSimple(X, Y, 100, 10)
'''
n, m = np.shape(dataMatrix)
A = matlib.zeros((1, m))
if callable(kernel):
K = matlib.zeros((m, m))
for i in range(m):
K[:,i] = kernel(dataMatrix[:,i] * matlib.ones((1,m)), dataMatrix, sigma)
else:
K = dataMatrix.T * dataMatrix
iterNum = 0
effTraversalNum = 0
while (iterNum < maxIter):
alphaPairsChanged = 0
for i in range(m):
E = (K*np.multiply(A, labelVector).T ).T- labelVector
j = i
while (j == i):
j = int(random.uniform(0, m))
a2 = A[0,j] + labelVector[0,j]*(E[0,i]-E[0,j])/(K[i,i]+K[j,j]-2*K[i,j])
if labelVector[0,i] == labelVector[0,j]:
l = max(0, A[0,i]+A[0,j]-C)
h = min(C, A[0,i]+A[0,j])
else:
l = max(0, A[0,j]-A[0,i])
h = min(C, C+A[0,j]-A[0,i])
if a2 > h:
a2 = h
elif a2 < l:
a2 = l
if (abs(A[0,j] - a2) < 0.00001): continue
a1 = A[0,i] + labelVector[0,i]*labelVector[0,j]*(A[0,j]-a2)
A[0,i] = a1
A[0,j] = a2
alphaPairsChanged += 1
if alphaPairsChanged != 0: effTraversalNum += 1
iterNum += 1
print("共完成有效遍历%d次。" %effTraversalNum)
spVecIndex = []
for k in range(m):
if abs(A[0,k]) > 0.01:
spVecIndex.append(k)
spE = E[:, spVecIndex].tolist()[0]
roundSpE = []
for n in spE: roundSpE.append(round(n, 4))
listRoundSpE = list(Counter(roundSpE).items())
listRoundSpE.sort(key=lambda x:x[1],reverse=True)
b = -listRoundSpE[0][0]
return A, b
（二）绘图代码
import numpy as np
import numpy.matlib as matlib
import matplotlib.pyplot as plt
def showDataSet(dataMatrix, labelVector, A=None, b=None, kernel=None, sigma=None):
'''
Parameters
----------
dataMatrix : np.matrix
一个2行m列矩阵，代表m个2维向量，作为待分类向量。默认第一行是横坐标，第二行是纵坐标。
labelVector : np.matrix
一个由+1和-1组成的1行m列矩矩阵，作为dataMatrix各列向量的标签。
A : np.matrix
一个1行m列矩阵，代表各待分向量对应的条件系数，非零系数对应支持向量。默认为空，
即不画分界线。
b : float
一个1行1列矩阵，代表决策平面的截距。默认为空，即不绘制分界线。
kernel : function
核函数。用于在低维空间计算映射到高维空间的向量内积。为空则默认为原向量空间内积。
sigma : float
核函数的调控参数。越小映射的空间维度约高。
Returns
-------
null
Notes
-----
只能绘制二维向量散点图。
Examples
--------
X = np.matrix('1, 1; 4, 3; 3, 3').T
Y = np.matrix('-1, 1, 1')
A = np.matrix('0.25, 0, 0.25')
b = np.matrix('-2')
showDataSet(X, Y, A, b)
'''
n, m = np.shape(dataMatrix)
if not n == 2:
raise Exception("only 2-dimension vectors can be darwn")
plusColumNum = []
minusColumNum = []
for i in range(m):
if labelVector[0,i] > 0:
plusColumNum.append(i)
else:
minusColumNum.append(i)
plusData = dataMatrix[:, plusColumNum]
minusData = dataMatrix[:, minusColumNum]
plt.figure()
plt.axis('scaled')
x_min = min(min(dataMatrix[0].tolist()[0])-1, 0)
x_max = max(max(dataMatrix[0].tolist()[0])+1, 0)
y_min = min(min(dataMatrix[1].tolist()[0])-1, 0)
y_max = max(max(dataMatrix[1].tolist()[0])+1, 0)
plt.xlim([x_min, x_max])
plt.ylim([y_min, y_max])
plt.scatter(plusData[0].tolist()[0], plusData[1].tolist()[0])
plt.scatter(minusData[0].tolist()[0], minusData[1].tolist()[0])
ax = plt.gca()
ax.spines['right'].set_color('none')
ax.spines['top'].set_color('none')
ax.spines['bottom'].set_position(('data',0))
ax.spines['left'].set_position(('data',0))
if b is not None:
x = np.linspace(x_min, x_max, 100)
y = np.linspace(y_min, y_max, 100)
meshX,meshY = np.meshgrid(x,y)
vecX = matlib.zeros((2, 1))
Z = matlib.zeros((100, 100))
for i, item_x in enumerate(x):
for j, item_y in enumerate(y):
vecX[0] = item_x
vecX[1] = item_y
matX = vecX * matlib.ones((1, m))
if callable(kernel):
Z[j,i] = kernel(dataMatrix, matX, sigma).T * np.multiply(labelVector, A).T +b
else:
Z[j,i] = (dataMatrix.T * vecX).T * np.multiply(labelVector, A).T +b
plt.contour(meshX, meshY, np.array(Z), [0], colors='r')
if A is not None and np.shape(A)[1] == m:
svOder = []
for i in range(m):
if abs(A[0,i]) > 0.01:
svOder.append(i)
svSet = dataMatrix[:, svOder]
plt.scatter(svSet[0].tolist()[0], svSet[1].tolist()[0], s=150,
c='none', alpha=0.7, linewidth=1.5, edgecolor='red')
（三）线性分割效果
import numpy as np
import numpy.matlib as matlib
import numpy.random as random
import svnSimple
import showDataSet
plusX = np.matrix(random.standard_normal((20, 2))).T + np.matrix('1; 1')
plusY = matlib.ones((1,np.shape(plusX)[1]))
minusX = np.matrix(random.standard_normal((25, 2))).T + np.matrix('5; 5')
minusY = matlib.ones((1,np.shape(minusX)[1]))*-1
X1 = np.c_[plusX, minusX]
Y1 = np.c_[plusY, minusY]
A, b = svnSimple(X1, Y1, 50, 50)
showDataSet(X1, Y1, A, b)
效果图如下：
（四）非线性分割效果
import numpy as np
import numpy.matlib as matlib
import numpy.random as random
import svnSimple
import showDataSet
plusX = np.matrix(random.standard_normal((40, 2))).T
plusY = matlib.ones((1,np.shape(plusX)[1]))
minusXright = np.matrix(random.standard_normal((10, 2))).T + np.matrix('7; 0')
minusXleft = np.matrix(random.standard_normal((10, 2))).T + np.matrix('-7; 0')
minusXup = np.matrix(random.standard_normal((10, 2))).T + np.matrix('0; 7')
minusXdown = np.matrix(random.standard_normal((10, 2))).T + np.matrix('0; -7')
minusXru = np.matrix(random.standard_normal((10, 2))).T + np.matrix('5; 5')
minusXrd = np.matrix(random.standard_normal((10, 2))).T + np.matrix('5; -5')
minusXlu = np.matrix(random.standard_normal((10, 2))).T + np.matrix('-5; 5')
minusXld = np.matrix(random.standard_normal((10, 2))).T + np.matrix('-5; -5')
minusX = np.c_[minusXright, minusXleft, minusXup, minusXdown, minusXru,
minusXrd, minusXlu, minusXld]
minusY = matlib.ones((1,np.shape(minusX)[1]))*-1
X2 = np.c_[plusX, minusX]
Y2 = np.c_[plusY, minusY]
A, b = svnSimple(X2, Y2, 300, 100, gaussKernel, 3)
showDataSet(X2, Y2, A, b, gaussKernel, 3)
效果图如下：
Original: https://blog.csdn.net/weixin_44657251/article/details/123882018
Author: XY_0209
Title: 详解支持向量机（Support Vector Machines, SVM）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/667487/
转载文章受原作者版权保护。转载请注明原作者出处！