机器学习经典算法之SVM深入解析

水深无声 2022-05-14 16:48 659阅读 0赞

# 前言 #

起初让我最头疼的是拉格朗日对偶和SMO，后来逐渐明白拉格朗日对偶的重要作用是将w的计算提前并消除w，使得优化函数变为拉格朗日乘子的单一参数优化问题。而SMO里面迭代公式的推导也着实让我花费了不少时间。

对比这么复杂的推导过程，SVM的思想确实那么简单。它不再像logistic回归一样企图去拟合样本点（中间加了一层sigmoid函数变换），而是就在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。

之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中，发现了w可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的处理，导致的结果就是将优化问题变得更加复杂，然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题，也被拉格朗日对偶和SMO算法化解，使SVM趋向于完美。

# 1. 支持向量机基本概念及原理 #

## 1.1 间隔与支持向量 ##

给定训练样本集  D = ( x ⃗ ( 1 ) , y ( 1 ) ) , ( x ⃗ ( 2 ) , y ( 2 ) ) , . . , ( x ⃗ ( m ) , y ( m ) ) , y i ∈ − 1 , + 1 ( 二 分 类 问 题 ) , x ⃗ ( i ) = ( x 1 ( i ) ; x 2 ( i ) ; . . . ; x d ( i ) ) D = \{(\\vec x^\{(1)\}, y^\{(1)\}), (\\vec x^\{(2)\},y^\{(2)\}),..,(\\vec x^\{(m)\},y^\{(m)\})\}, y\_i \\in \\\\\{-1, +1\\\\\} (二分类问题) , \\vec x^\{(i)\} =(x^\{(i)\}\_1;x^\{(i)\}\_2;...;x^\{(i)\}\_d ) D=(x(1),y(1)),(x(2),y(2)),..,(x(m),y(m)),yi∈−1,\+1(二分类问题),x(i)=(x1(i);x2(i);...;xd(i)) (注意,这里用的是分号, 表示这是一个列向量), SVM做的事情就是试图把一根"木棍"放在最佳位置, 好让"木棍"的两边都有尽可能大的"间隔".

这个"木棍"就叫做"划分超平面", 可以用下面的线性方程来描述:

w ⃗ T x ⃗ + b = 0 \\vec w^T\\vec x + b = 0 wTx\+b=0

, 其中  w ⃗ = ( w 1 ; w 2 ; . . . ; w d ) \\vec w =(w\_1; w\_2;...; w\_d) w=(w1;w2;...;wd) 为  d d d 维法向量(注意,这里用的是分号, 表示这是一个列向量),  x ⃗ \\vec x x 为"木棍"上的点的坐标,  b b b 为位移项.

根据点到"直线"的距离公式,我们可以得到样本空间中任意点  x ⃗ \\vec x x 到超平面  ( w ⃗ , b ) (\\vec w,b) (w,b) 的距离为:

r = ∣ w ⃗ T x ⃗ + b ∣ ∥ w ⃗ ∥ r = \\frac\{|\\vec w^T\\vec x+b|\}\{\\|\\vec w \\|\} r=∥w∥∣wTx\+b∣

∥ w ⃗ ∥ = w 1 2 + w 2 2 + . . . + w d 2 \\|\\vec w\\| = \\sqrt\{w\_1^2 + w\_2^2 + ... + w\_d^2\} ∥w∥=w12\+w22\+...\+wd2 为向量长度(也即向量的L2范式)

**首先假设** 当前的超平面可以将所有的训练样本正确分类, 那么就有如下式子:

\{ w ⃗ T x ⃗ ( i ) + b ≥ 0 , y ( i ) = + 1 w ⃗ T x ⃗ ( i ) + b ≤ 0 , y ( i ) = − 1 \\begin\{cases\} \\vec w^T\\vec x^\{(i)\} + b \\geq 0, & y^\{(i)\} = +1 \\\\ \\vec w^T\\vec x^\{(i)\} + b \\leq 0, & y\_\{(i)\} = -1 \\end\{cases\} \{ wTx(i)\+b≥0,wTx(i)\+b≤0,y(i)=\+1y(i)=−1

上式可以统一写成如下的约束不等式:()

y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) ≥ 0 y^\{(i)\}(\\vec w^T\\vec x^\{(i)\} + b) \\geq 0 y(i)(wTx(i)\+b)≥0

上面的式子其实是冗余的, 因为假设样本点不在超平面上, 所以不可能出现等于0的情况, 又因为超平面方程两边都乘一个不等于0的数,还是 **同一个超平面**, 因此为了简化问题的表述, 我们对  w ⃗ \\vec w w 和  b b b 加上如下约束(这里的1没有什么特别的含义, 可以是任意的常数, 因为这里的点  x ⃗ ( i ) \\vec x^\{(i)\} x(i) 不是超平面上的点, 所以所得值不为0):

min ⁡ i ∣ w ⃗ T x ⃗ ( i ) + b ∣ = 1 \\min\_i|\\vec w^T\\vec x^\{(i)\} +b| = 1 imin∣wTx(i)\+b∣=1

即离超平面最近的正, 负样本距离超平面的距离为:  1 ∥ w ⃗ ∥ \\frac\{1\}\{\\|\\vec w\\|\} ∥w∥1 , 我们将这些距离超平面最近的几个训练样本点为定义"支持向量", 那么, 两个异类支持向量到超平面的距离之和就为  γ = 2 ∥ w ⃗ ∥ \\gamma = \\frac\{2\}\{\\|\\vec w\\|\} γ=∥w∥2 , 我们将这称为"间隔".

同时, 根据此约束, 我们可以消除超分类平面约束的冗余, 得到新的超分类平面约束如下:

y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) ≥ 1 y^\{(i)\}(\\vec w^T\\vec x^\{(i)\} + b) \\geq 1 y(i)(wTx(i)\+b)≥1

SVM的目的就是找到具有"最大间隔"的划分超平面, 也就是要找到满足约束 y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) ≥ 1 y^\{(i)\}(\\vec w^T\\vec x^\{(i)\} + b) \\geq 1 y(i)(wTx(i)\+b)≥1中的参数  w ⃗ , b \\vec w, b w,b , 使得其具有最大的间隔  γ \\gamma γ , 也就:

arg ⁡ max ⁡ w ⃗ , b 2 ∥ w ⃗ ∥ \\arg\\max\_\{\\vec w,b\}\\frac\{2\}\{\\|\\vec w\\|\} argw,bmax∥w∥2  
 s . t . y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) ≥ 1 , i = 1 , . . . , m s.t. y^\{(i)\}(\\vec w^T \\vec x\{(i)\} +b) \\geq 1, i=1,...,m s.t.y(i)(wTx(i)\+b)≥1,i=1,...,m

显然, 为了最大化间隔  γ \\gamma γ , 我们仅需要最大化  ∥ w ⃗ ∥ − 1 \\|\\vec w\\|^\{-1\} ∥w∥−1 , 这就等于最小化  ∥ w ⃗ ∥ 2 \\|\\vec w\\|^2 ∥w∥2, 于是上式等价为:

(1) arg ⁡ min ⁡ w ⃗ , b 1 2 ∥ w ⃗ ∥ 2 = arg ⁡ min ⁡ w ⃗ , b 1 2 w ⃗ T w ⃗ \\arg\\min\_\{\\vec w,b\} \\frac\{1\}\{2\}\\|\\vec w\\|^2 = \\arg\\min\_\{\\vec w,b\} \\frac\{1\}\{2\}\\vec w^T\\vec w \\tag 1 argw,bmin21∥w∥2=argw,bmin21wTw(1)

s . t . y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) ≥ 1 , i = 1 , . . . , m s.t. y^\{(i)\}(\\vec w^T \\vec x\{(i)\} +b) \\geq 1, i=1,...,m s.t.y(i)(wTx(i)\+b)≥1,i=1,...,m

下图即为SVM示意图, 注意,图中的1可以被任意常数替换(只要前面乘上对应的系数即可, =0说明在超分类平面上, !=0说明在两侧)

![d7b90c85ly1fvrusa33dkj20hx0dnmxr.jpg][]

以上就是线性可分时的SVM基本型(现实中大多数问题是线性不可分的, 所以线性可分的SVM没有太多实用价值)

## 1.2 对偶问题求解  w ⃗ \\vec w w 和  b b b ##

### 1.2.1 问题说明 ###

凸二次规划问题(convex quadratix programming): 目标函数是变量的二次函数, 约束条件是变量的线性不等式

对偶问题(dual problem):在求出一个问题解的同时, 也给出了另一个问题的解

我们希望通过求解式(1)来得到具有最大间隔的划分超平面的模型参数,由于该式是一个凸二次规划问题 因此,对该式使用拉格朗日乘子法得到其"对偶问题"

对于式(1)的每条样本点约束添加拉格朗日乘子  α ( i ) ≥ 0 \\alpha^\{(i)\} \\geq 0 α(i)≥0, 则该问题的拉格朗日函数为:

(2) L ( w ⃗ , b , α ) = 1 2 ∥ w ⃗ ∥ 2 + ∑ i = 1 m α ( i ) ( 1 − y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) ) L(\\vec w,b,\\alpha) = \\frac\{1\}\{2\}\\|\\vec w\\|^2 +\\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} (1-y^\{(i)\}(\\vec w^T \\vec x^\{(i)\} +b))\\tag 2 L(w,b,α)=21∥w∥2\+i=1∑mα(i)(1−y(i)(wTx(i)\+b))(2)

其中,  α ⃗ = ( α ( 1 ) , α ( 2 ) , . . . , α ( m ) ) , 每 一 个 α ( i ) 均 为 标 量 \\vec \\alpha = (\\alpha^\{(1)\}, \\alpha^\{(2)\},...,\\alpha^\{(m)\}) ,每一个\\alpha^\{(i)\}均为标量 α=(α(1),α(2),...,α(m)),每一个α(i)均为标量 .接着对  L ( w ⃗ , b , α ⃗ ) L(\\vec w,b,\\vec \\alpha) L(w,b,α) 对  w ⃗ \\vec w w 和  b b b 求偏导, 并令其为0, 可得:

(3) ∂ L ( w ⃗ , b , α ⃗ ) ∂ w ⃗ = w ⃗ − ∑ i = 1 m α ( i ) y ( i ) x ⃗ ( i ) = 0 \\frac\{\\partial L(\\vec w,b,\\vec \\alpha)\}\{\\partial \\vec w\} = \\vec w - \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\}y^\{(i)\}\\vec x^\{(i)\} = 0 \\tag 3 ∂w∂L(w,b,α)=w−i=1∑mα(i)y(i)x(i)=0(3)

(4) ∂ L ( w ⃗ , b , α ⃗ ) ∂ b = − ∑ i = 1 m α ( i ) y ( i ) = 0 \\frac\{\\partial L(\\vec w,b,\\vec \\alpha)\}\{\\partial b\} = -\\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} y^\{(i)\} = 0 \\tag 4 ∂b∂L(w,b,α)=−i=1∑mα(i)y(i)=0(4)

将(3)和(4)代入(2)式中, 消去  w ⃗ \\vec w w 和  b b b ( 注意, 这里  ∑ i = 1 m α ( i ) y ( i ) = 0 \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} y^\{(i)\} = 0 ∑i=1mα(i)y(i)=0, 但是不代表  α ( i ) y ( i ) = 0 \\alpha^\{(i)\} y^\{(i)\} = 0 α(i)y(i)=0 ), 可得:

L ( w ⃗ , b , α ⃗ ) = 1 2 ( ∑ i = 1 m α ( i ) y ( i ) x ⃗ ( i ) ) 2 + ∑ i = 1 m α ( i ) − ∑ i = 1 m α ( i ) y ( i ) ( ∑ j = 1 m α ( j ) y ( j ) x ⃗ ( j ) ) T x ⃗ ( i ) − ∑ i = 1 m α ( i ) y ( i ) b L(\\vec w, b, \\vec \\alpha) = \\frac\{1\}\{2\}\\bigg( \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} y^\{(i)\}\\vec x^\{(i)\} \\bigg)^2 + \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} - \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} y^\{(i)\} \\Big( \\sum\_\{j=1\}^\{m\}\\alpha^\{(j)\} y^\{(j)\} \\vec x^\{(j)\} \\Big)^T \\vec x^\{(i)\} - \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\}b L(w,b,α)=21(i=1∑mα(i)y(i)x(i))2\+i=1∑mα(i)−i=1∑mα(i)y(i)(j=1∑mα(j)y(j)x(j))Tx(i)−i=1∑mα(i)y(i)b

= ∑ i = 1 m α ( i ) − 1 2 ∑ i = 1 m ∑ j = 1 m α ( i ) y ( i ) α ( i ) y ( j ) x ⃗ ( i ) T x ⃗ ( j ) = \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} - \\frac\{1\}\{2\} \\sum\_\{i=1\}^\{m\} \\sum\_\{j=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} \\alpha^\{(i)\} y^\{(j)\} \\vec x^\{(i)T\} \\vec x^\{(j)\} =i=1∑mα(i)−21i=1∑mj=1∑mα(i)y(i)α(i)y(j)x(i)Tx(j)

这里  x ⃗ ( i ) , x ⃗ ( j ) \\vec x^\{(i)\},\\vec x^\{(j)\} x(i),x(j) 位置可互换, 为了好看,我将  x ⃗ ( i ) \\vec x^\{(i)\} x(i) 写在了前面. 到此, 我们就得到了式(2)的对偶问题:

(5) arg ⁡ max ⁡ α ⃗ ( ∑ i = 1 m α ( i ) − 1 2 ∑ i = 1 m ∑ j = 1 m α ( i ) α ( j ) y ( i ) y ( j ) x ⃗ ( i ) T x ⃗ ( j ) ) \\arg\\max\_\{\\vec \\alpha\} \\bigg( \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} - \\frac\{1\}\{2\} \\sum\_\{i=1\}^\{m\} \\sum\_\{j=1\}^\{m\} \\alpha^\{(i)\} \\alpha^\{(j)\} y^\{(i)\} y^\{(j)\} \\vec x^\{(i)T\} \\vec x^\{(j)\} \\bigg) \\tag 5 argαmax(i=1∑mα(i)−21i=1∑mj=1∑mα(i)α(j)y(i)y(j)x(i)Tx(j))(5)  
 s . t . ∑ i = 1 m α ( i ) y ( i ) = 0 , 其 中 α ( i ) ≥ 0 s.t. \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y\{(i)\} = 0, 其中 \\alpha^\{(i)\} \\geq 0 s.t.i=1∑mα(i)y(i)=0,其中α(i)≥0

为了满足原始问题(1) 和对偶问题(5)之间的充分必要条件, 上述推导过程还需要满足KKT(Karush-Kuhn-Tucker)条件(其中前两条已经在上述推导过程中满足) , 即要求:

\{ α ( i ) ≥ 0 ; y ( i ) f ( x ⃗ ( i ) ) − 1 ≥ 0 ; α ( i ) ( y ( i ) f ( x ⃗ ( i ) ) − 1 ) = 0. \\begin\{cases\} \\alpha^\{(i)\} \\geq 0 ; \\\\ y^\{(i)\} f(\\vec x^\{(i)\}) - 1 \\geq 0 ; \\\\ \\alpha^\{(i)\}(y^\{(i)\} f(\\vec x^\{(i)\}) - 1 ) = 0. \\end\{cases\} ⎩⎪⎨⎪⎧α(i)≥0;y(i)f(x(i))−1≥0;α(i)(y(i)f(x(i))−1)=0.

当我们解出上式得到  α ⃗ \\vec \\alpha α 后, 就可以通过求得  w ⃗ \\vec w w 和  b b b 的值, 进而可得到划分超平面对应的模型:

f ( x ⃗ ) = w ⃗ T x ⃗ + b = ∑ i = 1 m α ( i ) y ( i ) x ⃗ ( i ) T x ⃗ + b f(\\vec x) = \\vec w ^T \\vec x +b = \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} \\vec x^\{(i)T\} \\vec x +b f(x)=wTx\+b=i=1∑mα(i)y(i)x(i)Tx\+b

根据KKT条件我们可以轻易得出, 对任意的训练样本  ( x ⃗ ( i ) , y ( i ) ) (\\vec x^\{(i)\} , y^\{(i)\}) (x(i),y(i)) , 总有  α ( i ) = 0 \\alpha^\{(i)\} = 0 α(i)=0 或  y ( i ) f ( x ⃗ ( i ) ) = 1 y^\{(i)\} f(\\vec x^\{(i)\}) = 1 y(i)f(x(i))=1 . 若  α ( i ) = 0 \\alpha^\{(i)\} = 0 α(i)=0 , 则该项对应的样本不会出现在求和项中 ; **若  α ( i ) > 0 \\alpha^\{(i)\} > 0 α(i)>0 , 则必有  y ( i ) f ( x ⃗ ( i ) ) = 1 y^\{(i)\} f(\\vec x^\{(i)\}) = 1 y(i)f(x(i))=1 , 这说明该样本点出现在最大间隔边界上, 是一个支持向量. 这显示出支持向量机的一个重要性质: 训练完成后, 大部分的训练样本都不需要保留(该样本对应的系数  α ( i ) = 0 \\alpha^\{(i)\}=0 α(i)=0 ), 最终模型仅与支持向量有关.**

### 使用SMO算法求对偶问题的解 ###

从(5)式可以看出, 这仍是一个二次规划问题, 可以使用通用的二次规划法来求解, 但是, 该问题的规模正比于训练样本数量, 在实际任务中使用通用解法会造成很大的开销, 因此, 需要使用更高效的算法—SMO(Sequential Minimal Optimization, 序列最小算法)

SMO的基本思路: 先固定  α ( i ) \\alpha^\{(i)\} α(i) 之外的所有参数, 然后求  α ( i ) \\alpha^\{(i)\} α(i) 上的极值. 但是这里由于  α ( i ) \\alpha^\{(i)\} α(i) 之间不是互相独立的, 需要满足约束  ∑ i = 1 m α ( i ) y ( i ) = 0 \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} = 0 ∑i=1mα(i)y(i)=0 , 即一个分量改变, 另一个也要随之改变,因此每次在优化变量中选取两个分量  α ( i ) \\alpha^\{(i)\} α(i) 和  α ( j ) \\alpha^\{(j)\} α(j) ,并将其他参数固定, 然后在参数初始化后, 不断执行如下两个步骤直至收敛:

*  选取一对需要更新的变量  α ( i ) \\alpha^\{(i)\} α(i) 和  α ( j ) \\alpha^\{(j)\} α(j)
 *  固定  α ( i ) \\alpha^\{(i)\} α(i) 和  α ( j ) \\alpha^\{(j)\} α(j) 以外的参数, 求解(5)式更新后的  α ( i ) \\alpha^\{(i)\} α(i) 和  α ( j ) \\alpha^\{(j)\} α(j)

具体的求解过程如下:

首先假设需要优化的参数是  α ( i ) \\alpha^\{(i)\} α(i) 和  α ( j ) \\alpha^\{(j)\} α(j) , 于是我们将剩下的分量  ∑ k = 1 , k ≠ i , j m α ( k ) y ( k ) \\sum\_\{k=1,k\\neq i,j\}^\{m\} \\alpha^\{(k)\} y^\{(k)\} ∑k=1,k̸=i,jmα(k)y(k) 固定, 作为常数处理, 可得下式:

α ( i ) y ( i ) + α ( j ) y ( j ) = − ∑ k = 1 , k ≠ i , j m α ( k ) y ( k ) = C \\alpha^\{(i)\} y^\{(i)\} + \\alpha^\{(j)\} y^\{(j)\} = -\\sum\_\{k=1,k\\neq i,j\}^\{m\} \\alpha^\{(k)\} y^\{(k)\} = C α(i)y(i)\+α(j)y(j)=−k=1,k̸=i,j∑mα(k)y(k)=C

对上式两边同乘以  y ( j ) y^\{(j)\} y(j) ,由于  y ( j ) × y ( j ) = 1 y^\{(j)\}\\times y^\{(j)\} = 1 y(j)×y(j)=1 可得:

α ( j ) = C y ( j ) − α ( i ) y ( i ) y ( j ) = y ( j ) ( C − α ( i ) y ( i ) ) \\alpha^\{(j)\} = Cy^\{(j)\} - \\alpha^\{(i)\} y^\{(i)\} y^\{(j)\} = y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) α(j)=Cy(j)−α(i)y(i)y(j)=y(j)(C−α(i)y(i))

将上式代入(5)式, 消去变量  α ( j ) \\alpha^\{(j)\} α(j) , 得到一个关于  α ( i ) \\alpha^\{(i)\} α(i) 的单变量二次规划问题, 所有的常数项用  C C C 表示, (5)式被转换成如下,:

F ( α ( i ) ) = α ( i ) + ( y ( j ) ( C − α ( i ) y ( i ) ) ) − 1 2 α ( i ) α ( i ) y ( i ) y ( i ) x ⃗ ( i ) T x ⃗ ( i ) − 1 2 ( y ( j ) ( C − α ( i ) y ( i ) ) ) 2 y ( j ) y ( j ) x ⃗ ( j ) T x ⃗ ( j ) F(\\alpha^\{(i)\}) = \\alpha^\{(i)\} + \\Big( y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) - \\frac\{1\}\{2\}\\alpha^\{(i)\} \\alpha^\{(i)\} y^\{(i)\}y^\{(i)\}\\vec x^\{(i)T\}\\vec x^\{(i)\} - \\frac\{1\}\{2\}\\Big( y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) \\Big)^2y^\{(j)\}y^\{(j)\}\\vec x^\{(j)T\}\\vec x^\{(j)\} F(α(i))=α(i)\+(y(j)(C−α(i)y(i)))−21α(i)α(i)y(i)y(i)x(i)Tx(i)−21(y(j)(C−α(i)y(i)))2y(j)y(j)x(j)Tx(j)  
 − α ( i ) ( y ( j ) ( C − α ( i ) y ( i ) ) ) y ( i ) y ( j ) x ⃗ ( i ) T x ⃗ ( j ) - \\alpha^\{(i)\} \\Big( y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) y^\{(i)\}y^\{(j)\}\\vec x^\{(i)T\} \\vec x^\{(j)\} −α(i)(y(j)(C−α(i)y(i)))y(i)y(j)x(i)Tx(j)  
 − α ( i ) y ( i ) ∑ k = 1 , k ≠ i , j m α ( k ) y ( k ) x ⃗ ( i ) T x ⃗ ( k ) − ( y ( j ) ( C − α ( i ) y ( i ) ) ) y ( j ) ∑ k = 1 , k ≠ i , j m α ( k ) y ( k ) x ⃗ ( j ) T x ⃗ ( k ) - \\alpha^\{(i)\}y^\{(i)\}\\sum\_\{k=1,k\\neq i,j\}^\{m\}\\alpha^\{(k)\}y^\{(k)\}\\vec x^\{(i)T\} \\vec x^\{(k)\} - \\Big( y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) y^\{(j)\}\\sum\_\{k=1,k\\neq i,j\}^\{m\}\\alpha^\{(k)\}y^\{(k)\}\\vec x^\{(j)T\}\\vec x^\{(k)\} −α(i)y(i)k=1,k̸=i,j∑mα(k)y(k)x(i)Tx(k)−(y(j)(C−α(i)y(i)))y(j)k=1,k̸=i,j∑mα(k)y(k)x(j)Tx(k)  
 = α ( i ) + ( y ( j ) ( C − α ( i ) y ( i ) ) ) − 1 2 ( α ( i ) ) 2 x ⃗ ( i ) T x ⃗ ( i ) − 1 2 ( C − α ( i ) y ( i ) ) 2 x ⃗ ( j ) T x ⃗ ( j ) − α ( i ) ( ( C − α ( i ) y ( i ) ) ) y ( i ) x ⃗ ( i ) T x ⃗ ( j ) − α ( i ) y ( i ) v ( i ) − ( C − α ( i ) y ( i ) ) v ( j ) + C = \\alpha^\{(i)\} + \\Big( y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) - \\frac\{1\}\{2\}(\\alpha^\{(i)\})^2\\vec x^\{(i)T\}\\vec x^\{(i)\} - \\frac\{1\}\{2\} \\big( C - \\alpha^\{(i)\}y^\{(i)\} \\big)^2 \\vec x^\{(j)T\}\\vec x^\{(j)\} - \\alpha^\{(i)\} \\Big( (C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) y^\{(i)\}\\vec x^\{(i)T\} \\vec x^\{(j)\} - \\alpha^\{(i)\}y^\{(i)\}v^\{(i)\} - \\big(C- \\alpha^\{(i)\}y^\{(i)\} \\big)v^\{(j)\} + C =α(i)\+(y(j)(C−α(i)y(i)))−21(α(i))2x(i)Tx(i)−21(C−α(i)y(i))2x(j)Tx(j)−α(i)((C−α(i)y(i)))y(i)x(i)Tx(j)−α(i)y(i)v(i)−(C−α(i)y(i))v(j)\+C

= α ( i ) + ( y ( j ) ( C − α ( i ) y ( i ) ) ) − 1 2 ( α ( i ) ) 2 K i , i − 1 2 ( C − α ( i ) y ( i ) ) 2 K j , j − α ( i ) ( ( C − α ( i ) y ( i ) ) ) y ( i ) K i , j − α ( i ) y ( i ) v ( i ) − ( C − α ( i ) y ( i ) ) v ( j ) + C = \\alpha^\{(i)\} + \\Big( y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) - \\frac\{1\}\{2\}(\\alpha^\{(i)\})^2K\_\{i,i\} - \\frac\{1\}\{2\} \\big( C - \\alpha^\{(i)\}y^\{(i)\} \\big)^2 K\_\{j,j\} - \\alpha^\{(i)\} \\Big( (C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) y^\{(i)\}K\_\{i,j\} - \\alpha^\{(i)\}y^\{(i)\}v^\{(i)\} - \\big(C- \\alpha^\{(i)\}y^\{(i)\} \\big)v^\{(j)\} + C =α(i)\+(y(j)(C−α(i)y(i)))−21(α(i))2Ki,i−21(C−α(i)y(i))2Kj,j−α(i)((C−α(i)y(i)))y(i)Ki,j−α(i)y(i)v(i)−(C−α(i)y(i))v(j)\+C  
上式为了简便, 将  x ⃗ ( i ) T x ⃗ ( j ) \\vec x^\{(i)T\}\\vec x^\{(j)\} x(i)Tx(j) 简记为  K i , j K\_\{i,j\} Ki,j (后文会用K代表核函数, 这里姑且认为此时的核函数  K K K 为恒等映射),将上式对  α ( i ) \\alpha^\{(i)\} α(i) 求导, 并令其等于0, 可得:

∂ F ( α ( i ) ) ∂ α ( i ) = 1 − y ( i ) y ( j ) − α ( i ) K i , i + y ( i ) ( C − α ( i ) y ( i ) ) K j , j − ( C − α ( i ) y ( i ) − α ( i ) y ( i ) ) y ( i ) K i , j − y ( i ) v ( i ) + y ( i ) v ( j ) \\frac\{\\partial F(\\alpha^\{(i)\})\}\{\\partial \\alpha^\{(i)\}\} = 1 - y^\{(i)\}y^\{(j)\} - \\alpha^\{(i)\}K\_\{i,i\} + y^\{(i)\}(C-\\alpha^\{(i)\} y^\{(i)\})K\_\{j,j\} - \\Big( C-\\alpha^\{(i)\}y^\{(i)\} - \\alpha^\{(i)\} y^\{(i)\} \\Big)y^\{(i)\}K\_\{i,j\} - y^\{(i)\}v^\{(i)\} + y^\{(i)\}v^\{(j)\} ∂α(i)∂F(α(i))=1−y(i)y(j)−α(i)Ki,i\+y(i)(C−α(i)y(i))Kj,j−(C−α(i)y(i)−α(i)y(i))y(i)Ki,j−y(i)v(i)\+y(i)v(j)

= 1 − y ( i ) y ( j ) − α ( i ) ( K i , i + K j , j − 2 K i , j ) + C y ( i ) K j , j − C y ( i ) K i , j − y ( i ) ( v ( i ) − v ( j ) ) = 0 = 1-y^\{(i)\}y^\{(j)\} -\\alpha^\{(i)\} \\Big( K\_\{i,i\} + K\_\{j,j\} - 2K\_\{i,j\}\\Big) + Cy^\{(i)\}K\_\{j,j\} - Cy^\{(i)\}K\_\{i,j\} - y^\{(i)\}\\big(v^\{(i)\} -v^\{(j)\} \\big) = 0 =1−y(i)y(j)−α(i)(Ki,i\+Kj,j−2Ki,j)\+Cy(i)Kj,j−Cy(i)Ki,j−y(i)(v(i)−v(j))=0

下面对上式进行变形, 使得可以用  α o l d ( i ) \\alpha\_\{old\}^\{(i)\} αold(i) 来更新  α n e w ( i ) \\alpha\_\{new\}^\{(i)\} αnew(i) .

因为SVM对数据点的预测值为:  f ( x ⃗ ) = ∑ i = 1 m α ( i ) y ( i ) K ( x ⃗ ( i ) , x ⃗ ) + b f(\\vec x) = \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} y^\{(i)\} K(\\vec x^\{(i)\},\\vec x) + b f(x)=∑i=1mα(i)y(i)K(x(i),x)\+b, 则  v ( i ) v^\{(i)\} v(i) 以及  v ( j ) v^\{(j)\} v(j) 的值可以表示成:

v ( i ) = ∑ k = 1 , k ≠ i , j m α ( k ) y ( k ) K i , k = f ( x ( i ) ) − α ( i ) y ( i ) K i , i − α ( j ) y ( j ) K i , j + b v^\{(i)\} = \\sum\_\{k=1,k\\neq i,j\}^\{m\} \\alpha^\{(k)\} y^\{(k)\} K\_\{i,k\} = f(x^\{(i)\}) - \\alpha^\{(i)\} y^\{(i)\} K\_\{i,i\} - \\alpha^\{(j)\} y^\{(j)\} K\_\{i,j\} + b v(i)=k=1,k̸=i,j∑mα(k)y(k)Ki,k=f(x(i))−α(i)y(i)Ki,i−α(j)y(j)Ki,j\+b

v ( j ) = ∑ k = 1 , k ≠ i , j m α ( k ) y ( k ) K j , k = f ( x ( j ) ) − α ( j ) y ( j ) K j , j − α ( i ) y ( i ) K j , i + b v^\{(j)\} = \\sum\_\{k=1,k\\neq i,j\}^\{m\} \\alpha^\{(k)\} y^\{(k)\} K\_\{j,k\} = f(x^\{(j)\}) - \\alpha^\{(j)\} y^\{(j)\} K\_\{j,j\} - \\alpha^\{(i)\} y^\{(i)\} K\_\{j,i\} + b v(j)=k=1,k̸=i,j∑mα(k)y(k)Kj,k=f(x(j))−α(j)y(j)Kj,j−α(i)y(i)Kj,i\+b

将  α ( j ) = y ( j ) ( C − α ( i ) y ( i ) ) \\alpha^\{(j)\} = y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) α(j)=y(j)(C−α(i)y(i)) 带到上式, 可得到  v ( i ) − v ( j ) v^\{(i)\} - v^\{(j)\} v(i)−v(j) 的表达式为:

v ( i ) − v ( j ) = f ( x ( i ) ) − f ( x ( j ) ) − α ( i ) y ( i ) K i , i + ( y ( j ) ( C − α ( i ) y ( i ) ) ) y ( j ) K j , j − ( y ( j ) ( C − α ( i ) y ( i ) ) ) y ( j ) K i , j + α ( i ) y ( i ) K j , i v^\{(i)\} - v^\{(j)\} = f(x^\{(i)\}) - f(x^\{(j)\}) - \\alpha^\{(i)\} y^\{(i)\} K\_\{i,i\} + \\Big( y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) y^\{(j)\} K\_\{j,j\} - \\Big( y^\{(j)\}(C - \\alpha^\{(i)\} y^\{(i)\}) \\Big) y^\{(j)\}K\_\{i,j\} + \\alpha^\{(i)\}y^\{(i)\}K\_\{j,i\} v(i)−v(j)=f(x(i))−f(x(j))−α(i)y(i)Ki,i\+(y(j)(C−α(i)y(i)))y(j)Kj,j−(y(j)(C−α(i)y(i)))y(j)Ki,j\+α(i)y(i)Kj,i

= f ( x ( i ) ) − f ( x ( j ) ) − α ( i ) y ( i ) K i , i + C K j , j − α ( i ) y ( i ) K j , j − C K i , j + 2 α ( i ) y ( i ) K i , j = f(x^\{(i)\}) - f(x^\{(j)\}) - \\alpha^\{(i)\}y^\{(i)\}K\_\{i,i\} + CK\_\{j,j\} - \\alpha^\{(i)\}y^\{(i)\}K\_\{j,j\} - CK\_\{i,j\} + 2\\alpha^\{(i)\}y^\{(i)\}K\_\{i,j\} =f(x(i))−f(x(j))−α(i)y(i)Ki,i\+CKj,j−α(i)y(i)Kj,j−CKi,j\+2α(i)y(i)Ki,j

= f ( x ( i ) ) − f ( x ( j ) ) − α ( i ) y ( i ) ( K i , i + K j , j − 2 K i , j ) + C K j , j − C K i , j = f(x^\{(i)\}) - f(x^\{(j)\}) - \\alpha^\{(i)\}y^\{(i)\} \\Big( K\_\{i,i\} + K\_\{j,j\} -2K\_\{i,j\} \\Big)+ CK\_\{j,j\} - CK\_\{i,j\} =f(x(i))−f(x(j))−α(i)y(i)(Ki,i\+Kj,j−2Ki,j)\+CKj,j−CKi,j

**注意  v ( i ) − v ( j ) v^\{(i)\} - v^\{(j)\} v(i)−v(j) 中  α ( i ) \\alpha^\{(i)\} α(i) 是更新前初始化的值, 我们将其记作  α o l d ( i ) \\alpha^\{(i)\}\_\{old\} αold(i) ,以便与我们期望获得的更新后的分量  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 相区分** , 将  v ( i ) − v ( j ) v^\{(i)\} - v^\{(j)\} v(i)−v(j) 的表达式代入  ∂ F ( α ( i ) ) ∂ α n e w ( i ) \\frac\{\\partial F(\\alpha^\{(i)\})\}\{\\partial \\alpha^\{(i)\}\_\{new\}\} ∂αnew(i)∂F(α(i)) 中 , 可得到:

∂ F ( α n e w ( i ) ) ∂ α n e w ( i ) = 1 − y ( i ) y ( j ) − α n e w ( i ) ( K i , i + K j , j − 2 K i , j ) + C y ( i ) K j , j − C y ( i ) K i , j − y ( i ) ( f ( x ( i ) ) − f ( x ( j ) ) − α o l d ( i ) y ( i ) ( K i , i + K j , j − 2 K i , j ) + C K j , j − C K i , j ) \\frac\{\\partial F(\\alpha^\{(i)\}\_\{new\})\}\{\\partial \\alpha^\{(i)\}\_\{new\}\} = 1-y^\{(i)\}y^\{(j)\} -\\alpha^\{(i)\}\_\{new\} \\Big( K\_\{i,i\} + K\_\{j,j\} - 2K\_\{i,j\}\\Big) + Cy^\{(i)\}K\_\{j,j\} - Cy^\{(i)\}K\_\{i,j\} - y^\{(i)\}\\bigg (f(x^\{(i)\}) - f(x^\{(j)\}) - \\alpha^\{(i)\}\_\{old\}y^\{(i)\} \\Big( K\_\{i,i\} + K\_\{j,j\} -2K\_\{i,j\} \\Big)+ CK\_\{j,j\} - CK\_\{i,j\} \\bigg) ∂αnew(i)∂F(αnew(i))=1−y(i)y(j)−αnew(i)(Ki,i\+Kj,j−2Ki,j)\+Cy(i)Kj,j−Cy(i)Ki,j−y(i)(f(x(i))−f(x(j))−αold(i)y(i)(Ki,i\+Kj,j−2Ki,j)\+CKj,j−CKi,j)

= ( y ( i ) ) 2 − y ( i ) y ( j ) − y ( i ) f ( x ( i ) ) + y ( i ) f ( x ( j ) ) − α n e w ( i ) ( K i , i + K j , j − 2 K i , j ) + α o l d ( i ) ( K i , i + K j , j − 2 K i , j ) = \\big( y^\{(i)\} \\big)^2 -y^\{(i)\}y^\{(j)\} - y^\{(i)\}f(x^\{(i)\}) + y^\{(i)\}f(x^\{(j)\}) - \\alpha^\{(i)\}\_\{new\} \\Big( K\_\{i,i\} + K\_\{j,j\} - 2K\_\{i,j\}\\Big) + \\alpha^\{(i)\}\_\{old\} \\Big( K\_\{i,i\} + K\_\{j,j\} - 2K\_\{i,j\}\\Big) =(y(i))2−y(i)y(j)−y(i)f(x(i))\+y(i)f(x(j))−αnew(i)(Ki,i\+Kj,j−2Ki,j)\+αold(i)(Ki,i\+Kj,j−2Ki,j)

= f ( x ( j ) ) − y ( j ) − ( f ( x ( i ) ) − y ( i ) ) − α n e w ( i ) ( K i , i + K j , j − 2 K i , j ) + α o l d ( i ) ( K i , i + K j , j − 2 K i , j ) = f(x^\{(j)\}) - y^\{(j)\} - \\big( f(x^\{(i)\}) -y^\{(i)\} \\big) - \\alpha^\{(i)\}\_\{new\} \\Big( K\_\{i,i\} + K\_\{j,j\} - 2K\_\{i,j\}\\Big) + \\alpha^\{(i)\}\_\{old\} \\Big( K\_\{i,i\} + K\_\{j,j\} - 2K\_\{i,j\}\\Big) =f(x(j))−y(j)−(f(x(i))−y(i))−αnew(i)(Ki,i\+Kj,j−2Ki,j)\+αold(i)(Ki,i\+Kj,j−2Ki,j)

我们记  E ( i ) E^\{(i)\} E(i) 为SVM预测值与真实值的误差:  E ( i ) = f ( x ( i ) ) − y ( i ) E^\{(i)\} = f(x^\{(i)\}) - y^\{(i)\} E(i)=f(x(i))−y(i) . 并令  η = K i , i + K j , j − 2 K i , j \\eta = K\_\{i,i\} + K\_\{j,j\} - 2K\_\{i,j\} η=Ki,i\+Kj,j−2Ki,j , 则最终的一阶导数表达式可以简化为:

∂ F ( α n e w ( i ) ) ∂ α n e w ( i ) = − η α n e w ( i ) + η α o l d ( i ) + y ( i ) ( E ( j ) − E ( i ) ) = 0 \\frac\{\\partial F(\\alpha^\{(i)\}\_\{new\})\}\{\\partial \\alpha^\{(i)\}\_\{new\}\} = -\\eta \\alpha^\{(i)\}\_\{new\} + \\eta \\alpha^\{(i)\}\_\{old\} + y^\{(i)\}\\big(E^\{(j)\} - E^\{(i)\} \\big) = 0 ∂αnew(i)∂F(αnew(i))=−ηαnew(i)\+ηαold(i)\+y(i)(E(j)−E(i))=0

由此, 我们可以根据当前的参数值, 直接得到更新后的参数值:

(6) α n e w ( i ) = α o l d ( i ) + y ( i ) ( E ( j ) − E ( i ) ) η = > α n e w , u n c l i p p e d ( i ) \\alpha^\{(i)\}\_\{new\} = \\alpha^\{(i)\}\_\{old\} + \\frac\{y^\{(i)\}\\big(E^\{(j)\} - E^\{(i)\} \\big)\}\{\\eta\} => \\alpha^\{(i)\}\_\{new, unclipped\} \\tag 6 αnew(i)=αold(i)\+ηy(i)(E(j)−E(i))=>αnew,unclipped(i)(6)

这里注意, (6)式的推导过程并未考虑下面的约束, 因此, 我们暂且将(6)式中的  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 记作  α n e w , u n c l i p p e d ( i ) \\alpha^\{(i)\}\_\{new, unclipped\} αnew,unclipped(i), 然后考虑如下约束:

0 ≤ α ( i ) , α ( j ) ≤ C 0 \\leq \\alpha^\{(i)\} , \\alpha^\{(j)\} \\leq C 0≤α(i),α(j)≤C

我们分别以  α ( i ) , α ( j ) \\alpha^\{(i)\}, \\alpha^\{(j)\} α(i),α(j) 为坐标轴, 于是上述约束可以看作是一个方形约束(Bosk constraint), 在二维平面中我们可以看到这是个限制在方形区域中的直线, 如下图所示, 直线在方形区域内滑动(对应不同的截距), 同时  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 的上下边界也在改变:

![d7b90c85ly1fvsu4x9m5hj20ci0a8wel.jpg][] ![d7b90c85ly1fvsu4xaa2nj20ca0ae3yn.jpg][]

当  y ( i ) ≠ y ( j ) y^\{(i)\} \\neq y^\{(j)\} y(i)̸=y(j) 时(如左图), 限制条件可以写成  α ( i ) − α ( j ) = ξ \\alpha^\{(i)\} - \\alpha^\{(j)\} = \\xi α(i)−α(j)=ξ ,根据  ξ \\xi ξ 的正负可以得到不同的上下界, 因此  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 的上下界可以统一表示成:

*  下界:  L = max ⁡ ( 0 , α o l d ( i ) − α o l d ( j ) ) L = \\max(0, \\alpha^\{(i)\}\_\{old\} - \\alpha^\{(j)\}\_\{old\}) L=max(0,αold(i)−αold(j))
 *  上界:  H = min ⁡ ( C , C + α o l d ( i ) − α o l d ( j ) ) H = \\min(C, C + \\alpha^\{(i)\}\_\{old\} - \\alpha^\{(j)\}\_\{old\}) H=min(C,C\+αold(i)−αold(j))

当  y ( i ) = y ( j ) y^\{(i)\} = y^\{(j)\} y(i)=y(j) 时(如右图), 限制条件可以写成  α ( i ) + α ( j ) = ξ \\alpha^\{(i)\} + \\alpha^\{(j)\} = \\xi α(i)\+α(j)=ξ , 于是  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 的上下界为:

*  下界:  L = max ⁡ ( 0 , α o l d ( i ) + α o l d ( j ) − C ) L = \\max(0,\\alpha^\{(i)\}\_\{old\} + \\alpha^\{(j)\}\_\{old\} - C) L=max(0,αold(i)\+αold(j)−C)
 *  上界:  H = min ⁡ ( C , α o l d ( i ) + α o l d ( j ) ) H = \\min(C, \\alpha^\{(i)\}\_\{old\} + \\alpha^\{(j)\}\_\{old\}) H=min(C,αold(i)\+αold(j))

根据得到的上下界, 我们可以得到"修剪"后的  α n e w , c l i p p e d ( i ) \\alpha^\{(i)\}\_\{new,clipped\} αnew,clipped(i) :

(7) α n e w , c l i p p e d ( i ) = \{ H α n e w , u n c l i p p e d ( i ) > H α n e w , u n c l i p p e d ( i ) L ≤ α n e w , u n c l i p p e d ( i ) ≤ H L α n e w , u n c l i p p e d ( i ) < L \\alpha^\{(i)\}\_\{new,clipped\} = \\begin\{cases\} H & \\alpha^\{(i)\}\_\{new,unclipped\} > H \\\\ \\alpha^\{(i)\}\_\{new,unclipped\} & L \\leq \\alpha^\{(i)\}\_\{new,unclipped\} \\leq H \\\\ L & \\alpha^\{(i)\}\_\{new,unclipped\} < L \\end\{cases\} \\tag 7 αnew,clipped(i)=⎩⎪⎨⎪⎧Hαnew,unclipped(i)Lαnew,unclipped(i)>HL≤αnew,unclipped(i)≤Hαnew,unclipped(i)<L(7)

得到了  α n e w , c l i p p e d ( i ) \\alpha^\{(i)\}\_\{new,clipped\} αnew,clipped(i) 以后, 便可以根据  α o l d ( i ) y ( i ) + α o l d ( j ) y ( j ) = α n e w ( i ) y ( i ) + α n e w ( j ) y ( j ) \\alpha^\{(i)\}\_\{old\} y^\{(i)\} + \\alpha^\{(j)\}\_\{old\} y^\{(j)\}= \\alpha^\{(i)\}\_\{new\}y^\{(i)\} + \\alpha^\{(j)\}\_\{new\}y^\{(j)\} αold(i)y(i)\+αold(j)y(j)=αnew(i)y(i)\+αnew(j)y(j) 得到  α n e w ( j ) \\alpha^\{(j)\}\_\{new\} αnew(j) :

(8) α n e w , c l i p p e d ( j ) = α o l d ( j ) + y ( i ) y ( j ) ( α o l d ( i ) − α n e w , c l i p p e d ( i ) ) \\alpha^\{(j)\}\_\{new,clipped\} = \\alpha^\{(j)\}\_\{old\} + y^\{(i)\}y^\{(j)\}\\big( \\alpha^\{(i)\}\_\{old\} - \\alpha^\{(i)\}\_\{new,clipped\} \\big) \\tag 8 αnew,clipped(j)=αold(j)\+y(i)y(j)(αold(i)−αnew,clipped(i))(8)

通过(7)(8)式, 我们便可以高效的计算出更新后的  α ( i ) \\alpha^\{(i)\} α(i) 和  α ( j ) \\alpha^\{(j)\} α(j) .

当更新了一对  α ( i ) \\alpha^\{(i)\} α(i) 和  α ( j ) \\alpha^\{(j)\} α(j) 之后, 我们需要计算偏移项  b b b 注意到, 对于任意支持向量  ( x ⃗ ( s ) , y ( s ) ) (\\vec x^\{(s)\} , y^\{(s)\}) (x(s),y(s)) , 都有  y ( s ) f ( x ( s ) ) = 1 y^\{(s)\} f(x^\{(s)\}) = 1 y(s)f(x(s))=1 , 即:

y ( s ) ( ∑ i ∈ S α ( i ) y ( i ) x ⃗ ( i ) T x ⃗ ( s ) + b ) = 1 y^\{(s)\} \\Big( \\sum\_\{i \\in S\} \\alpha^\{(i)\} y^\{(i)\} \\vec x^\{(i)T\} \\vec x^\{(s)\} + b\\Big) = 1 y(s)(i∈S∑α(i)y(i)x(i)Tx(s)\+b)=1

式中  S S S 为所有支持向量的下标集. 理论上, 可以选取任意支持向量来获得  b b b , 但现实中我们采取更加鲁棒的做法: 使用所有支持向量求解的平均值(式中所有量均已知,  α ⃗ \\vec \\alpha α 使用的是支持向量对应的系数):

b = 1 ∣ S ∣ ∑ s ∈ S ( 1 y ( s ) − ∑ i ∈ S α ( i ) y ( i ) x ⃗ ( i ) T x ⃗ ( s ) ) b = \\frac\{1\}\{|S|\} \\sum\_\{s\\in S\} \\bigg( \\frac\{1\}\{y^\{(s)\}\} - \\sum\_\{i \\in S\} \\alpha^\{(i)\} y^\{(i)\}\\vec x^\{(i)T\} \\vec x^\{(s)\} \\bigg) b=∣S∣1s∈S∑(y(s)1−i∈S∑α(i)y(i)x(i)Tx(s))

还有另一种更新  b b b 的方式是, 只使用当前更新的变量  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 和  α n e w ( j ) \\alpha^\{(j)\}\_\{new\} αnew(j) 来对  b b b 进行更新,如此一来, 为了满足KKT条件, 就有以下几种情况:

*  如果  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 在界内(即此时  0 < α n e w ( i ) < C 0 < \\alpha^\{(i)\}\_\{new\} < C 0<αnew(i)<C , 当前对应样本为支持向量), 则  b = b n e w ( i ) b = b^\{(i)\}\_\{new\} b=bnew(i)
 *  如果  α n e w ( j ) \\alpha^\{(j)\}\_\{new\} αnew(j) 在界内(即此时  0 < α n e w ( j ) < C 0 < \\alpha^\{(j)\}\_\{new\} < C 0<αnew(j)<C , 当前对应样本为支持向量), 则  b = b n e w ( j ) b = b^\{(j)\}\_\{new\} b=bnew(j)
 *  如果  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 和  α n e w ( j ) \\alpha^\{(j)\}\_\{new\} αnew(j) 都在界上,且  L ≠ H L \\neq H L̸=H时, 则  b n e w ( i ) b^\{(i)\}\_\{new\} bnew(i) 和  b n e w ( j ) b^\{(j)\}\_\{new\} bnew(j) 之间的所有的值都符合KKT条件, SMO一般选择终点作为新的偏移量:  b n e w = b n e w ( i ) + b n e w ( j ) 2 b\_\{new\} = \\frac\{b^\{(i)\}\_\{new\} + b^\{(j)\}\_\{new\}\}\{2\} bnew=2bnew(i)\+bnew(j)

以上讨论中,  b n e w ( i ) b^\{(i)\}\_\{new\} bnew(i) 的推导过程为, 当  α n e w ( i ) \\alpha^\{(i)\}\_\{new\} αnew(i) 在界内时, 对应的样本为支持向量 (根据KKT条件得出) , 此时  y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) = 1 y^\{(i)\}(\\vec w^T \\vec x^\{(i)\} +b) = 1 y(i)(wTx(i)\+b)=1 , 两边同时乘上  y ( i ) y^\{(i)\} y(i) ,得到  ∑ k = 1 m α ( k ) y ( k ) K k , i + b = y ( i ) \\sum\_\{k=1\}^\{m\}\\alpha^\{(k)\}y^\{(k)\}K\_\{k,i\} + b = y^\{(i)\} ∑k=1mα(k)y(k)Kk,i\+b=y(i), 将该式展开, 得到:

b n e w ( i ) = y ( i ) − ∑ k = 1 , k ≠ i , j m α ( k ) y ( k ) K k , i − α n e w ( i ) y ( i ) K i , i − α n e w ( j ) y ( j ) K j , i b^\{(i)\}\_\{new\} = y^\{(i)\} - \\sum\_\{k=1,k\\neq i,j\}^\{m\} \\alpha^\{(k)\} y^\{(k)\}K\_\{k,i\} - \\alpha^\{(i)\}\_\{new\}y^\{(i)\}K\_\{i,i\} - \\alpha^\{(j)\}\_\{new\}y^\{(j)\}K\_\{j,i\} bnew(i)=y(i)−k=1,k̸=i,j∑mα(k)y(k)Kk,i−αnew(i)y(i)Ki,i−αnew(j)y(j)Kj,i

其中前两项可以写成:

y ( i ) − ∑ k = 1 , k ≠ i , j m α ( k ) y ( k ) K k , i = − E ( i ) + α o l d ( i ) y ( i ) K i , i + α o l d ( j ) y ( j ) K j , i + b o l d y^\{(i)\} - \\sum\_\{k=1,k\\neq i,j\}^\{m\} \\alpha^\{(k)\} y^\{(k)\}K\_\{k,i\} = -E^\{(i)\} + \\alpha^\{(i)\}\_\{old\}y^\{(i)\}K\_\{i,i\} + \\alpha^\{(j)\}\_\{old\}y^\{(j)\}K\_\{j,i\} + b\_\{old\} y(i)−k=1,k̸=i,j∑mα(k)y(k)Kk,i=−E(i)\+αold(i)y(i)Ki,i\+αold(j)y(j)Kj,i\+bold

于是有:

b n e w ( i ) = − E ( i ) − ( α n e w ( i ) − α o l d ( i ) ) y ( i ) K i , i − ( α n e w ( j ) − α o l d ( j ) ) y ( j ) K j , i + b o l d b^\{(i)\}\_\{new\} = -E^\{(i)\} - \\big( \\alpha^\{(i)\}\_\{new\} - \\alpha^\{(i)\}\_\{old\} \\big)y^\{(i)\} K\_\{i,i\} - \\big(\\alpha^\{(j)\}\_\{new\} - \\alpha^\{(j)\}\_\{old\} \\big)y^\{(j)\}K\_\{j,i\} + b\_\{old\} bnew(i)=−E(i)−(αnew(i)−αold(i))y(i)Ki,i−(αnew(j)−αold(j))y(j)Kj,i\+bold

同理有:  
 b n e w ( j ) = − E ( j ) − ( α n e w ( j ) − α o l d ( j ) ) y ( j ) K j , j − ( α n e w ( i ) − α o l d ( i ) ) y ( j ) K i , j + b o l d b^\{(j)\}\_\{new\} = -E^\{(j)\} - \\big( \\alpha^\{(j)\}\_\{new\} - \\alpha^\{(j)\}\_\{old\} \\big)y^\{(j)\} K\_\{j,j\} - \\big(\\alpha^\{(i)\}\_\{new\} - \\alpha^\{(i)\}\_\{old\} \\big)y^\{(j)\}K\_\{i,j\} + b\_\{old\} bnew(j)=−E(j)−(αnew(j)−αold(j))y(j)Kj,j−(αnew(i)−αold(i))y(j)Ki,j\+bold

### 如何恰当的选取需要更新的变量  α ( i ) \\alpha^\{(i)\} α(i) 和  α ( j ) \\alpha^\{(j)\} α(j) ###

采用启发式的规则来选取, 直觉上我们知道, 我们应该首先优化那些违反KKT条件最严重的样本, 因此我们首先首先遍历所有满足约束条件  0 < α ( i ) < C 0 < \\alpha^\{(i)\} < C 0<α(i)<C 的样本点, 即位于间隔边界上的支持向量点(直觉上也能发现这些点最有可能分类错误), 检验它们是否满足KKT条件. 如果这些样本都满足KKT条件，则遍历整个训练样本集，判断它们是否满足KKT条件，直到找到一个违反KKT条件的变量  α ( i ) \\alpha^\{(i)\} α(i) (即使  α ( i ) \\alpha^\{(i)\} α(i) 位于边界上,也有可能违反KKT条件).

当找到了第一个分量  α ( i ) \\alpha^\{(i)\} α(i) 后, 接下来寻找第二个分类  α ( j ) \\alpha^\{(j)\} α(j), 而选取的标准是使得它有足够大的变化, 也就是说使选取的两变量所对应的样本之间的间隔最大, 一种直观的解释是, 这样的两个变量有很大的差别, 与对两个相似的变量进行更新相比(相似说明有可能属于同一类, 更新意义不大), 对它们进行更新会带给目标函数值更大的变化. 第二个乘子的迭代步长正比于  ∣ E ( i ) − E ( j ) ∣ |E^\{(i)\} - E^\{(j)\}| ∣E(i)−E(j)∣ , 因此, 我们希望选择的乘子能够具有最大的  ∣ E ( i ) − E ( j ) ∣ |E^\{(i)\} - E^\{(j)\}| ∣E(i)−E(j)∣. 即当  E ( i ) E^\{(i)\} E(i) 为正时选择绝对值最大的赋值  E ( j ) E^\{(j)\} E(j) , 反之, 选择正值最大的  E ( i ) E^\{(i)\} E(i)

## 1.3 核函数 ##

在之前的讨论中,我们假设 **训练样本** 是线性可分的, 然而在现实任务中, 原始样本空间内也许并不存在一个能正确划分两类样本的超平面, 对于这样的问题, **可将一样本从原始空间映射到一个更高维的特征空间, 使得样本在这个特征空间内线性可分** .

**需要知道, 如果原始空间是有限维, 即属性数有限, 那么一定存在一个高维特征空间使样本可分**

令  ϕ ( x ⃗ ) \\phi(\\vec x) ϕ(x) 表示将  x ⃗ \\vec x x 映射后的特征向量, 于是, 在特征空间中划分超平面所对应的模型可表示为:

f ( x ⃗ ) = w ⃗ T ϕ ( x ⃗ ) + b f(\\vec x) = \\vec w^T \\phi(\\vec x) + b f(x)=wTϕ(x)\+b

类似式(1), 有:

arg ⁡ min ⁡ w ⃗ , b 1 2 ∥ w ∥ 2 \\arg\\min\_\{\\vec w,b\} \\frac\{1\}\{2\} \\|w\\|^2 argw,bmin21∥w∥2

s . t . y ( i ) ( w ⃗ T ϕ ( x ⃗ ( i ) ) + b ) , i = 1 , 2 , . . , m s.t. y^\{(i)\}\\big( \\vec w^T \\phi (\\vec x^\{(i)\}) + b \\big), i=1,2,..,m s.t.y(i)(wTϕ(x(i))\+b),i=1,2,..,m

其对偶问题为:

(9) arg ⁡ max ⁡ α ⃗ = ∑ i = 1 m α ( i ) − 1 2 ∑ i = 1 m ∑ j = 1 m α ( i ) α ( j ) y ( i ) y ( j ) ϕ ( x ⃗ ( i ) ) T ϕ ( x ⃗ ( j ) ) \\arg\\max\_\{\\vec \\alpha\} = \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} - \\frac\{1\}\{2\}\\sum\_\{i=1\}^\{m\} \\sum\_\{j=1\}^\{m\} \\alpha^\{(i)\} \\alpha^\{(j)\} y^\{(i)\} y^\{(j)\} \\phi(\\vec x^\{(i)\})^T \\phi(\\vec x^\{(j)\}) \\tag 9 argαmax=i=1∑mα(i)−21i=1∑mj=1∑mα(i)α(j)y(i)y(j)ϕ(x(i))Tϕ(x(j))(9)

s . t . ∑ i = 1 m α ( i ) y ( i ) = 0 , α ( i ) ≥ 0 , i = 1 , 2 , . . . , m s.t. \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} = 0, \\alpha^\{(i)\} \\geq 0 , i = 1,2,...,m s.t.i=1∑mα(i)y(i)=0,α(i)≥0,i=1,2,...,m

求解上式涉及到计算  ϕ ( x ⃗ ( i ) ) T ϕ ( x ⃗ ( j ) \\phi(\\vec x^\{(i)\})^T \\phi(\\vec x^\{(j)\} ϕ(x(i))Tϕ(x(j) , 这是样本  x ⃗ ( i ) \\vec x^\{(i)\} x(i) 与  x ⃗ ( j ) \\vec x^\{(j)\} x(j) 映射到特征空间之后的内积, 由于特征空间维数可能很高, 甚至是无穷维, 因此直接计算  ϕ ( x ⃗ ( i ) ) T ϕ ( x ⃗ ( j ) \\phi(\\vec x^\{(i)\})^T \\phi(\\vec x^\{(j)\} ϕ(x(i))Tϕ(x(j) 是很困难的, 为了避开这个障碍, 可以设想这样一个函数:

K ( x ⃗ ( i ) , x ⃗ ( j ) ) = ϕ ( x ⃗ ( i ) ) T ϕ ( x ⃗ ( j ) K \\big(\\vec x^\{(i)\}, \\vec x^\{(j)\} \\big) = \\phi(\\vec x^\{(i)\})^T \\phi(\\vec x^\{(j)\} K(x(i),x(j))=ϕ(x(i))Tϕ(x(j)

**即  x ( i ) x^\{(i)\} x(i) 与  x ( j ) x^\{(j)\} x(j) 在特征空间的内积等于它们在原始样本空间中通过函数  K ( ⋅ , ⋅ ) K(\\cdot, \\cdot) K(⋅,⋅) 计算的结果.** (有可能是先内积再函数映射, 也有可能是求范式再函数映射). 于是(9)式可重写为:

arg ⁡ max ⁡ α ⃗ ∑ i = 1 m α ( i ) − 1 2 ∑ i = 1 m ∑ j = 1 m α ( i ) α ( j ) y ( i ) y ( j ) K ( x ⃗ ( i ) , x ⃗ ( j ) ) \\arg\\max\_\{\\vec \\alpha\} \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\} - \\frac\{1\}\{2\}\\sum\_\{i=1\}^\{m\} \\sum\_\{j=1\}^\{m\}\\alpha^\{(i)\} \\alpha^\{(j)\} y^\{(i)\} y^\{(j)\} K\\big(\\vec x^\{(i)\}, \\vec x^\{(j)\} \\big) argαmaxi=1∑mα(i)−21i=1∑mj=1∑mα(i)α(j)y(i)y(j)K(x(i),x(j))

s . t . ∑ i = 1 m α ( i ) y ( i ) = 0 s.t. \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} = 0 s.t.i=1∑mα(i)y(i)=0

α ( i ) ≥ 0 , i = 1 , 2 , . . . , m \\alpha^\{(i)\} \\geq 0, i=1,2,...,m α(i)≥0,i=1,2,...,m

注意, 前面几个小节的推导过程也用了符号  K K K , 但是就像前面所说的, 前几个小节的  K K K 是为了方便书写而使用的, 你可以把它看作是一个恒等映射的核函数

当我们解出上式得到  α ⃗ \\vec \\alpha α 后, 就可以得到划分超平面对应的模型(式中  x ⃗ \\vec x x 为样本点,  f ( x ⃗ ) f(\\vec x) f(x) 为该样本点的预测结果):

f ( x ⃗ ) = w ⃗ T x ⃗ + b = ∑ i = 1 m α ( i ) y ( i ) K ( x ⃗ , x ⃗ ( j ) ) + b f(\\vec x) = \\vec w ^T \\vec x +b = \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} K\\big(\\vec x, \\vec x^\{(j)\} \\big) +b f(x)=wTx\+b=i=1∑mα(i)y(i)K(x,x(j))\+b

**核函数定理:** 令  χ \\chi χ 为输入空间  K ( ⋅ , ⋅ ) K(\\cdot, \\cdot) K(⋅,⋅)　是定义在　 χ × χ \\chi \\times \\chi χ×χ 上的对称函数, 则  K ( ⋅ , ⋅ ) K(\\cdot, \\cdot) K(⋅,⋅) 是核函数 当且仅当 对于任意数据  D = x ⃗ ( 1 ) , x ⃗ ( 2 ) , . . . , x ⃗ ( m ) D = \\\\\{\\vec x^\{(1)\}, \\vec x^\{(2)\},...,\\vec x ^\{(m)\} \\\\\} D=x(1),x(2),...,x(m) , 核矩阵  K K K 总是半正定的

从以上分析可知, 核函数的选择决定了特征空间的好坏, 因此, 一个合适的核函数,就成为了支持向量机的最大变数.

下面是几种常用的核函数:

<table> 
 <thead> 
  <tr> 
   <th>名称</th> 
   <th>表达式</th> 
   <th>参数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>线性核</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>高斯核</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>拉普拉斯核</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>Sigoid核</td> 
   <td></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

此外,还可以通过函数组合得到:

*  若  K 1 K\_1 K1 和  K 2 K\_2 K2 都是核函数 ,则对任意的正数  γ 1 , γ 2 \\gamma\_1, \\gamma\_2 γ1,γ2 , 其线性组合  γ 1 K 1 + γ 2 K 2 \\gamma\_1 K\_1 + \\gamma\_2 K\_2 γ1K1\+γ2K2 也是核函数
 *  若  K 1 K\_1 K1 和  K 2 K\_2 K2 为核函数, 则函数的直积  K 1 ⊗ K 2 ( x ⃗ , z ⃗ ) = K 1 ( x ⃗ , z ⃗ ) K 2 ( x ⃗ , z ⃗ ) K\_1 \\otimes K\_2 (\\vec x , \\vec z) = K\_1(\\vec x, \\vec z) K\_2(\\vec x, \\vec z) K1⊗K2(x,z)=K1(x,z)K2(x,z)
 *  若  K 1 K\_1 K1 是核函数, 则对任意函数  g ( x ⃗ ) g(\\vec x) g(x),  K ( x ⃗ , z ⃗ ) = g ( x ⃗ ) K 1 ( x ⃗ , z ⃗ ) g ( z ⃗ ) K(\\vec x, \\vec z) = g(\\vec x) K\_1(\\vec x, \\vec z) g(\\vec z) K(x,z)=g(x)K1(x,z)g(z) 也是核函数

## 1.4 软间隔与正则化 ##

在实现任务中, 往往很难确定合适的核函数, 使得训练样本在特征空间中线性可分, 即便是找到了, 也无法断定是否是由于过拟合造成的 , 因此, 我们需要 **允许支持向量机在一些样本上出错** , 以缓解上面的问题.

硬间隔(hard margin)与软间隔(soft margin)的区分:

*  硬间隔: 所有样本都必须分类正确
 *  软间隔: 允许某些样本不满足约束(11)式(即,预测结果和真实结果符号相反,分类错误,或预测结果绝对值小于1,相当于越过了支持向量划定的边界)

我们要在最大化间隔的同时, 使得不满足约束的样本应尽可能的少, 于是, 优化目标可写为:

(10) min ⁡ w ⃗ , b 1 2 ∥ w ∥ 2 + C ∑ i = 1 m l 0 / 1 ( y ( i ) ( w ⃗ T x ( i ) + b ) − 1 ) \\min\_\{\\vec w,b\} \\frac\{1\}\{2\} \\|w\\|^2 + C\\sum\_\{i=1\}^\{m\} l\_\{0/1\} \\big( y^\{(i)\} (\\vec w^T x^\{(i)\}+b) - 1\\big) \\tag \{10\} w,bmin21∥w∥2\+Ci=1∑ml0/1(y(i)(wTx(i)\+b)−1)(10)

(11) y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) ≥ 1 y^\{(i)\} (\\vec w^T \\vec x^\{(i)\} +b) \\geq 1 \\tag \{11\} y(i)(wTx(i)\+b)≥1(11)

其中,  C > 0 C>0 C>0 是一个常数(注意与前几节推导SVM时的常数区分),  l 0 / 1 l\_\{0/1\} l0/1 是 “0/1 损失函数”:

l 0 / 1 ( z ) = \{ 1 , if  z < 0 ; 0 , otherwise . l\_\{0/1\} (z) = \\begin\{cases\} 1, & \\text\{if \} z < 0 ; \\\\ 0, & \\text\{otherwise\}. \\end\{cases\} l0/1(z)=\{ 1,0,if z<0;otherwise.

当C无穷大时, (10)式就会迫使所有样本均满足约束, 也就是令所有训练样本都分类正确(容易产生过拟合), 当C取有限值时, 则允许有一些样本不满足约束(11)式.

但是,  l 0 / 1 l\_\{0/1\} l0/1 非凸, 不连续, 数学性质不好, 因此, 通常使用其他函数来替代, 称为" 替代损失", 下面为三种常用的替代损失:

*  hinge损失:  l h i n g e ( z ) = m a x ( 0 , 1 − z ) l\_\{hinge\}(z) = max(0,1-z) lhinge(z)=max(0,1−z)
 *  指数损失(exponential loss):  l e x p ( z ) = e x p ( − z ) l\_\{exp\}(z) = exp(-z) lexp(z)=exp(−z)
 *  对率损失(logistic loss):  l l o g ( z ) = l o g ( 1 + e x p ( − z ) ) l\_\{log\}(z) = log(1+ exp(-z)) llog(z)=log(1\+exp(−z))

假设采用hinge损失损失, 然后可以引入"松弛变量"(slack variables)  ξ ( i ) ≥ 0 \\xi^\{(i)\} \\geq 0 ξ(i)≥0 ,每一个样本都有一个对应的松弛变量, 用以表征该样本不满足约束(11)的程度 则可将(10)式重写为:

(12) min ⁡ w ⃗ , b , ξ ( i ) 1 2 ∥ w ⃗ ∥ 2 + C ∑ i = 1 m ξ ( i ) \\min\_\{\\vec w, b, \\xi^\{(i)\}\} \\frac\{1\}\{2\} \\|\\vec w\\|^2 + C \\sum\_\{i=1\}^\{m\} \\xi^\{(i)\} \\tag \{12\} w,b,ξ(i)min21∥w∥2\+Ci=1∑mξ(i)(12)

s . t . y ( i ) ( w ⃗ T x ( i ) + b ) ≥ 1 − ξ ( i ) s.t. y^\{(i)\} (\\vec w^T x^\{(i)\} + b) \\geq 1- \\xi ^\{(i)\} s.t.y(i)(wTx(i)\+b)≥1−ξ(i)

ξ ( i ) ≥ , i = 1 , 2 , . . . , m . \\xi^\{(i)\} \\geq , i=1,2,...,m. ξ(i)≥,i=1,2,...,m.

可以看出, 上式是与之前推导相似的二次规划问题, 只不过是约束条件变的宽松了(为了允许一些样本犯错), 因此,同样利用拉格朗日乘子法求解, 首先得到上式的拉格朗日函数:

L ( w ⃗ , b , α ⃗ , ξ ⃗ , μ ⃗ ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ξ ( i ) + ∑ i = 1 m α ( i ) ( 1 − ξ ( i ) − y ( i ) ( w ⃗ T x ⃗ ( i ) + b ) ) − ∑ i = 1 m μ ( i ) ξ ( i ) L(\\vec w, b, \\vec \\alpha, \\vec \\xi, \\vec \\mu) = \\frac\{1\}\{2\} \\|w\\|^2 + C \\sum\_\{i=1\}^\{m\} \\xi^\{(i)\} + \\sum\_\{i=1\}^\{m\}\\alpha^\{(i)\}\\big(1- \\xi^\{(i)\} - y^\{(i)\}(\\vec w^T\\vec x^\{(i)\} +b) \\big) - \\sum\_\{i=1\}^\{m\} \\mu^\{(i)\} \\xi^\{(i)\} L(w,b,α,ξ,μ)=21∥w∥2\+Ci=1∑mξ(i)\+i=1∑mα(i)(1−ξ(i)−y(i)(wTx(i)\+b))−i=1∑mμ(i)ξ(i)

其中,  α ( i ) ≥ 0 , μ ( i ) ≥ 0 \\alpha^\{(i)\} \\geq 0, \\mu^\{(i)\} \\geq 0 α(i)≥0,μ(i)≥0 是拉格朗日乘子, 令  L ( w ⃗ , b , α ⃗ , ξ ⃗ , μ ⃗ ) L(\\vec w, b, \\vec \\alpha, \\vec \\xi, \\vec \\mu) L(w,b,α,ξ,μ) 对  w ⃗ , b , α ⃗ , ξ ⃗ \\vec w, b, \\vec \\alpha, \\vec \\xi w,b,α,ξ 求偏导, 并令其为0 , 可得:

w ⃗ = ∑ i = 1 m α ( i ) y ( i ) x ⃗ ( i ) \\vec w =\\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} \\vec x^\{(i)\} w=i=1∑mα(i)y(i)x(i)

0 = ∑ i = 1 m α ( i ) y ( i ) 0 = \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} 0=i=1∑mα(i)y(i)

C = α ( i ) + μ ( i ) C = \\alpha^\{(i)\} + \\mu^\{(i)\} C=α(i)\+μ(i)

得到(12)式对应的对偶问题如下:

max ⁡ α ∑ i = 1 m α ( i ) − 1 2 ∑ i = 1 m ∑ j = 1 m α ( i ) α ( j ) y ( i ) y ( j ) K i , j \\max\_\{\\alpha\} \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} - \\frac\{1\}\{2\} \\sum\_\{i=1\}^\{m\} \\sum\_\{j=1\}^\{m\} \\alpha^\{(i)\} \\alpha^\{(j)\} y^\{(i)\} y^\{(j)\} K\_\{i,j\} αmaxi=1∑mα(i)−21i=1∑mj=1∑mα(i)α(j)y(i)y(j)Ki,j

s . t . ∑ i = 1 m α ( i ) y ( i ) = 0 s.t. \\sum\_\{i=1\}^\{m\} \\alpha^\{(i)\} y^\{(i)\} = 0 s.t.i=1∑mα(i)y(i)=0

0 ≤ α ( i ) ≤ C , i = 1 , 2 , . . . , m 0 \\leq \\alpha^\{(i)\} \\leq C , i=1,2,...,m 0≤α(i)≤C,i=1,2,...,m

可以看到, 此时,  α ( i ) \\alpha^\{(i)\} α(i) 的约束条件变成了  0 ≤ α ( i ) ≤ C 0 \\leq \\alpha^\{(i)\} \\leq C 0≤α(i)≤C , 上式的KKT条件要求为:

\{ α ( i ) ≥ 0 , μ ( i ) ≥ 0 y ( i ) f ( x ⃗ ( i ) ) − 1 + ξ ( i ) ≥ 0 , α ( i ) ( y ( i ) f ( x ⃗ ( i ) ) − 1 + ξ ( i ) ) = 0 , ξ ( i ) ≥ 0 , μ ( i ) ξ ( i ) = 0 \\begin\{cases\} \\alpha^\{(i)\} \\geq 0, \\mu^\{(i)\} \\geq 0 \\\\ y^\{(i)\}f(\\vec x^\{(i)\}) -1 +\\xi^\{(i)\} \\geq 0, \\\\ \\alpha^\{(i)\} \\big( y^\{(i)\}f(\\vec x^\{(i)\}) - 1 + \\xi^\{(i)\} \\big) = 0, \\\\ \\xi^\{(i)\} \\geq 0, \\mu^\{(i)\} \\xi^\{(i)\} = 0 \\end\{cases\} ⎩⎪⎪⎪⎨⎪⎪⎪⎧α(i)≥0,μ(i)≥0y(i)f(x(i))−1\+ξ(i)≥0,α(i)(y(i)f(x(i))−1\+ξ(i))=0,ξ(i)≥0,μ(i)ξ(i)=0

于是, 从KKT条件中我们可以看出, 对任意的训练样本  ( x ⃗ ( i ) , y ( i ) ) (\\vec x^\{(i)\}, y^\{(i)\}) (x(i),y(i)), 总有  α ( i ) = 0 \\alpha^\{(i)\} = 0 α(i)=0 或  y ( i ) f ( x ⃗ ( i ) ) = 1 − ξ ( i ) y^\{(i)\} f(\\vec x^\{(i)\}) = 1 - \\xi^\{(i)\} y(i)f(x(i))=1−ξ(i).

*  若  α ( i ) = 0 \\alpha^\{(i)\} = 0 α(i)=0, 则该样本不会对  f ( x ⃗ ) f(\\vec x) f(x) 产生影响.
 *  若  α ( i ) > 0 \\alpha^\{(i)\} > 0 α(i)>0, 则必有  y ( i ) f ( x ⃗ ( i ) ) = 1 − ξ ( i ) y^\{(i)\} f(\\vec x^\{(i)\}) = 1 - \\xi^\{(i)\} y(i)f(x(i))=1−ξ(i), 即该样本是支持向量
 *  因为  C = α ( i ) + μ ( i ) C = \\alpha^\{(i)\} + \\mu^\{(i)\} C=α(i)\+μ(i) , 所以, 若  α ( i ) < C \\alpha^\{(i)\} < C α(i)<C , 则有  μ ( i ) > 0 \\mu^\{(i)\} > 0 μ(i)>0 , 进而有  ξ ( i ) = 0 \\xi^\{(i)\} = 0 ξ(i)=0, 即该样本在最大间隔边界上(是否也就是支持向量?)
 *  若  α ( i ) = C \\alpha^\{(i)\} = C α(i)=C , 则有  μ ( i ) = 0 \\mu^\{(i)\} = 0 μ(i)=0, 此时若  ξ ( i ) ≤ 1 \\xi^\{(i)\} \\leq 1 ξ(i)≤1, 则该样本落在最大间隔内部, 若  ξ ( i ) > 1 \\xi^\{(i)\} > 1 ξ(i)>1, 则该样本被错误分类.

以上讨论, 我们可以看出, 最终的模型依然只与支持向量有关, 保持了稀疏性(hinge损失有一块平坦的零区域,这使得SVM的解具有稀疏性)

以上是对使用hinge损失时讨论的情况, 还可以将其替换成别的损失函数以得到其他学习模型, 这些模型的性质与所用的替代函数直接相关, 但它们具有一个共性: 优化目标中的第一项用来描述划分超平面的"间隔"大小, 另一项用来表示训练集上的误差, 可写为更一般的形式:

min ⁡ f Ω ( f ) + C ∑ i = 1 m l ( f ( x ⃗ ( i ) ) , y ( i ) ) \\min\_\{f\} \\Omega(f) + C\\sum\_\{i=1\}^\{m\} l(f(\\vec x^\{(i)\}) , y^\{(i)\}) fminΩ(f)\+Ci=1∑ml(f(x(i)),y(i))

其中,  Ω ( f ) \\Omega(f) Ω(f) 称为"结构风险"(structural risk), 用于描述模型  f f f 自身的性质; 第二项  C ∑ i = 1 m l ( f ( x ⃗ ( i ) ) C\\sum\_\{i=1\}^\{m\} l(f(\\vec x^\{(i)\}) C∑i=1ml(f(x(i)) 称为"经验风险"(empirical risk), 用于描述模型与训练数据的契合程度.  C C C 用于对二者进行折衷.

从预测误差的角度来看, 第二项相当于模型误差, 第一项相当于正则化项, 表述了模型本身的性质, 一方面, 这为引入领域知识和用户意图提供了途径, 另一方面, 该信息有助于消减假设空间, 降低过拟合风险

# 3. 问答 #

## 为什么SVM的分类结果仅依赖于支持向量? ##

百机p53

## 核函数中不同参数的影响 ##

[https://mp.weixin.qq.com/s?\_\_biz=MzU4MjQ3MDkwNA==&mid=2247484495&idx=1&sn=4f3a6ce21cdd1a048e402ed05c9ead91&chksm=fdb699d8cac110ce53f4fc5e417e107f839059cb76d3cbf640c6f56620f90f8fb4e7f6ee02f9&scene=21\#wechat\_redirect][https_mp.weixin.qq.com_s_biz_MzU4MjQ3MDkwNA_mid_2247484495_idx_1_sn_4f3a6ce21cdd1a048e402ed05c9ead91_chksm_fdb699d8cac110ce53f4fc5e417e107f839059cb76d3cbf640c6f56620f90f8fb4e7f6ee02f9_scene_21_wechat_redirect]

## 既然深度学习技术性能表现以及全面超越SVM, SVM还有存在的必要吗? ##

# 6.Reference #

\[1\] [https://mp.weixin.qq.com/s?\_\_biz=MzU4MjQ3MDkwNA==&mid=2247483937&idx=1&sn=84a5acf12e96727b13fd7d456c414c12&chksm=fdb69fb6cac116a02dc68d948958ee731a4ae2b6c3d81196822b665224d9dab21d0f2fccb329&scene=21\#wechat\_redirect][https_mp.weixin.qq.com_s_biz_MzU4MjQ3MDkwNA_mid_2247483937_idx_1_sn_84a5acf12e96727b13fd7d456c414c12_chksm_fdb69fb6cac116a02dc68d948958ee731a4ae2b6c3d81196822b665224d9dab21d0f2fccb329_scene_21_wechat_redirect]

\[2\] 西瓜书

\[3\] [http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html][http_www.cnblogs.com_jerrylead_archive_2011_03_18_1988419.html]

[https://zhuanlan.zhihu.com/p/29212107][https_zhuanlan.zhihu.com_p_29212107]

[d7b90c85ly1fvrusa33dkj20hx0dnmxr.jpg]: /images/20220503/14406024e7b349f6bed415cc72f6cb0b.png
[d7b90c85ly1fvsu4x9m5hj20ci0a8wel.jpg]: https://wx4.sinaimg.cn/mw690/d7b90c85ly1fvsu4x9m5hj20ci0a8wel.jpg
[d7b90c85ly1fvsu4xaa2nj20ca0ae3yn.jpg]: /images/20220503/ca17388d4ebd4888ac6a77d1a92aefd6.png
[https_mp.weixin.qq.com_s_biz_MzU4MjQ3MDkwNA_mid_2247484495_idx_1_sn_4f3a6ce21cdd1a048e402ed05c9ead91_chksm_fdb699d8cac110ce53f4fc5e417e107f839059cb76d3cbf640c6f56620f90f8fb4e7f6ee02f9_scene_21_wechat_redirect]: https://mp.weixin.qq.com/s?__biz=MzU4MjQ3MDkwNA==&mid=2247484495&idx=1&sn=4f3a6ce21cdd1a048e402ed05c9ead91&chksm=fdb699d8cac110ce53f4fc5e417e107f839059cb76d3cbf640c6f56620f90f8fb4e7f6ee02f9&scene=21#wechat_redirect
[https_mp.weixin.qq.com_s_biz_MzU4MjQ3MDkwNA_mid_2247483937_idx_1_sn_84a5acf12e96727b13fd7d456c414c12_chksm_fdb69fb6cac116a02dc68d948958ee731a4ae2b6c3d81196822b665224d9dab21d0f2fccb329_scene_21_wechat_redirect]: https://mp.weixin.qq.com/s?__biz=MzU4MjQ3MDkwNA==&mid=2247483937&idx=1&sn=84a5acf12e96727b13fd7d456c414c12&chksm=fdb69fb6cac116a02dc68d948958ee731a4ae2b6c3d81196822b665224d9dab21d0f2fccb329&scene=21#wechat_redirect
[http_www.cnblogs.com_jerrylead_archive_2011_03_18_1988419.html]: http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
[https_zhuanlan.zhihu.com_p_29212107]: https://zhuanlan.zhihu.com/p/29212107