前言

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

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

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

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

1.1 间隔与支持向量

给定训练样本集 $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做的事情就是试图把一根"木棍"放在最佳位置, 好让"木棍"的两边都有尽可能大的"间隔".

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

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

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

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

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

$\|\vec w\| = \sqrt{w_1^2 + w_2^2 + ... + w_d^2}$∥w∥=w12​+w22​+...+wd2​​ 为向量长度(也即向量的L2范式)

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

$\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)}(\vec w^T\vec x^{(i)} + b) \geq 0$y(i)(wTx(i)+b)≥0

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

$\min_i|\vec w^T\vec x^{(i)} +b| = 1$imin​∣wTx(i)+b∣=1

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

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

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

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

$\arg\max_{\vec w,b}\frac{2}{\|\vec w\|}$argw,bmax​∥w∥2​
$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$γ , 我们仅需要最大化 $\|\vec w\|^{-1}$∥w∥−1 , 这就等于最小化 $\|\vec w\|^2$∥w∥2, 于是上式等价为:

$\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,bmin​21​∥w∥2=argw,bmin​21​wTw(1)

$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说明在两侧)

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

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

1.2.1 问题说明

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

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

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

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

$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)

其中, $\vec \alpha = (\alpha^{(1)}, \alpha^{(2)},...,\alpha^{(m)}) ,每一个\alpha^{(i)}均为标量$α=(α(1),α(2),...,α(m)),每一个α(i)均为标量 .接着对 $L(\vec w,b,\vec \alpha)$L(w,b,α) 对 $\vec w$w 和 $b$b 求偏导, 并令其为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)

$\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)式中, 消去 $\vec w$w 和 $b$b ( 注意, 这里 $\sum_{i=1}^{m}\alpha^{(i)} y^{(i)} = 0$∑i=1m​α(i)y(i)=0, 但是不代表 $\alpha^{(i)} y^{(i)} = 0$α(i)y(i)=0 ), 可得:

$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

$= \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)−21​i=1∑m​j=1∑m​α(i)y(i)α(i)y(j)x(i)Tx(j)

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

$\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)−21​i=1∑m​j=1∑m​α(i)α(j)y(i)y(j)x(i)Tx(j))(5)
$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)条件(其中前两条已经在上述推导过程中满足) , 即要求:

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

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

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

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

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

具体的求解过程如下:

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

$\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)}\times y^{(j)} = 1$y(j)×y(j)=1 可得:

$\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)式, 消去变量 $\alpha^{(j)}$α(j) , 得到一个关于 $\alpha^{(i)}$α(i) 的单变量二次规划问题, 所有的常数项用 $C$C 表示, (5)式被转换成如下,:

$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)
$- \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)
$- \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)
$= \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

$= \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
上式为了简便, 将 $\vec x^{(i)T}\vec x^{(j)}$x(i)Tx(j) 简记为 $K_{i,j}$Ki,j​ (后文会用K代表核函数, 这里姑且认为此时的核函数 $K$K 为恒等映射),将上式对 $\alpha^{(i)}$α(i) 求导, 并令其等于0, 可得:

$\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)} -\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

下面对上式进行变形, 使得可以用 $\alpha_{old}^{(i)}$αold(i)​ 来更新 $\alpha_{new}^{(i)}$αnew(i)​ .

因为SVM对数据点的预测值为: $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^{(j)}$v(j) 的值可以表示成:

$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)} = \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

将 $\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)} = 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)}) - \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)}) - \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) 中 $\alpha^{(i)}$α(i) 是更新前初始化的值, 我们将其记作 $\alpha^{(i)}_{old}$αold(i)​ ,以便与我们期望获得的更新后的分量 $\alpha^{(i)}_{new}$αnew(i)​ 相区分 , 将 $v^{(i)} - v^{(j)}$v(i)−v(j) 的表达式代入 $\frac{\partial F(\alpha^{(i)})}{\partial \alpha^{(i)}_{new}}$∂αnew(i)​∂F(α(i))​ 中 , 可得到:

$\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​)

$= \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)} - \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) 为SVM预测值与真实值的误差: $E^{(i)} = f(x^{(i)}) - y^{(i)}$E(i)=f(x(i))−y(i) . 并令 $\eta = K_{i,i} + K_{j,j} - 2K_{i,j}$η=Ki,i​+Kj,j​−2Ki,j​ , 则最终的一阶导数表达式可以简化为:

$\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

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

$\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)式中的 $\alpha^{(i)}_{new}$αnew(i)​ 记作 $\alpha^{(i)}_{new, unclipped}$αnew,unclipped(i)​, 然后考虑如下约束:

$\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

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

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

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

• 下界: $L = \max(0, \alpha^{(i)}_{old} - \alpha^{(j)}_{old})$L=max(0,αold(i)​−αold(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) 时(如右图), 限制条件可以写成 $\alpha^{(i)} + \alpha^{(j)} = \xi$α(i)+α(j)=ξ , 于是 $\alpha^{(i)}_{new}$αnew(i)​ 的上下界为:

• 下界: $L = \max(0,\alpha^{(i)}_{old} + \alpha^{(j)}_{old} - C)$L=max(0,αold(i)​+αold(j)​−C)
• 上界: $H = \min(C, \alpha^{(i)}_{old} + \alpha^{(j)}_{old})$H=min(C,αold(i)​+αold(j)​)

根据得到的上下界, 我们可以得到"修剪"后的 $\alpha^{(i)}_{new,clipped}$αnew,clipped(i)​ :

$\alpha^{(i)}_{new,clipped} = \begin{cases} H &amp; \alpha^{(i)}_{new,unclipped} &gt; H \\ \alpha^{(i)}_{new,unclipped} &amp; L \leq \alpha^{(i)}_{new,unclipped} \leq H \\ L &amp; \alpha^{(i)}_{new,unclipped} &lt; 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)

得到了 $\alpha^{(i)}_{new,clipped}$αnew,clipped(i)​ 以后, 便可以根据 $\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) 得到 $\alpha^{(j)}_{new}$αnew(j)​ :

$\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)式, 我们便可以高效的计算出更新后的 $\alpha^{(i)}$α(i) 和 $\alpha^{(j)}$α(j) .

当更新了一对 $\alpha^{(i)}$α(i) 和 $\alpha^{(j)}$α(j) 之后, 我们需要计算偏移项 $b$b 注意到, 对于任意支持向量 $(\vec x^{(s)} , y^{(s)})$(x(s),y(s)) , 都有 $y^{(s)} f(x^{(s)}) = 1$y(s)f(x(s))=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 为所有支持向量的下标集. 理论上, 可以选取任意支持向量来获得 $b$b , 但现实中我们采取更加鲁棒的做法: 使用所有支持向量求解的平均值(式中所有量均已知, $\vec \alpha$α 使用的是支持向量对应的系数):

$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∣1​s∈S∑​(y(s)1​−i∈S∑​α(i)y(i)x(i)Tx(s))

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

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

以上讨论中, $b^{(i)}_{new}$bnew(i)​ 的推导过程为, 当 $\alpha^{(i)}_{new}$αnew(i)​ 在界内时, 对应的样本为支持向量 (根据KKT条件得出) , 此时 $y^{(i)}(\vec w^T \vec x^{(i)} +b) = 1$y(i)(wTx(i)+b)=1 , 两边同时乘上 $y^{(i)}$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^{(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)} - \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^{(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^{(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​

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

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

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

1.3 核函数

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

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

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

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

类似式(1), 有:

$\arg\min_{\vec w,b} \frac{1}{2} \|w\|^2$argw,bmin​21​∥w∥2

$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

其对偶问题为:

$\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)−21​i=1∑m​j=1∑m​α(i)α(j)y(i)y(j)ϕ(x(i))Tϕ(x(j))(9)

$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

求解上式涉及到计算 $\phi(\vec x^{(i)})^T \phi(\vec x^{(j)}$ϕ(x(i))Tϕ(x(j) , 这是样本 $\vec x^{(i)}$x(i) 与 $\vec x^{(j)}$x(j) 映射到特征空间之后的内积, 由于特征空间维数可能很高, 甚至是无穷维, 因此直接计算 $\phi(\vec x^{(i)})^T \phi(\vec 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^{(j)}$x(j) 在特征空间的内积等于它们在原始样本空间中通过函数 $K(\cdot, \cdot)$K(⋅,⋅) 计算的结果. (有可能是先内积再函数映射, 也有可能是求范式再函数映射). 于是(9)式可重写为:

$\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αmax​i=1∑m​α(i)−21​i=1∑m​j=1∑m​α(i)α(j)y(i)y(j)K(x(i),x(j))

$s.t. \sum_{i=1}^{m} \alpha^{(i)} y^{(i)} = 0$s.t.i=1∑m​α(i)y(i)=0

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

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

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

$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(\cdot, \cdot)$K(⋅,⋅)　是定义在　$\chi \times \chi$χ×χ 上的对称函数, 则 $K(\cdot, \cdot)$K(⋅,⋅) 是核函数 当且仅当 对于任意数据 $D = \\{\vec x^{(1)}, \vec x^{(2)},...,\vec x ^{(m)} \\}$D=x(1),x(2),...,x(m) , 核矩阵 $K$K 总是半正定的

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

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

名称	表达式	参数
线性核
高斯核
拉普拉斯核
Sigoid核

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

• 若 $K_1$K1​ 和 $K_2$K2​ 都是核函数 ,则对任意的正数 $\gamma_1, \gamma_2$γ1​,γ2​ , 其线性组合 $\gamma_1 K_1 + \gamma_2 K_2$γ1​K1​+γ2​K2​ 也是核函数
• 若 $K_1$K1​ 和 $K_2$K2​ 为核函数, 则函数的直积 $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$K1​ 是核函数, 则对任意函数 $g(\vec x)$g(x), $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,相当于越过了支持向量划定的边界)

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

$\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,bmin​21​∥w∥2+Ci=1∑m​l0/1​(y(i)(wTx(i)+b)−1)(10)

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

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

$l_{0/1} (z) = \begin{cases} 1, &amp; \text{if } z &lt; 0 ; \\ 0, &amp; \text{otherwise}. \end{cases}$l0/1​(z)={1,0,​if z<0;otherwise.​

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

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

• hinge损失: $l_{hinge}(z) = max(0,1-z)$lhinge​(z)=max(0,1−z)
• 指数损失(exponential loss): $l_{exp}(z) = exp(-z)$lexp​(z)=exp(−z)
• 对率损失(logistic loss): $l_{log}(z) = log(1+ exp(-z))$llog​(z)=log(1+exp(−z))

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

$\min_{\vec w, b, \xi^{(i)}} \frac{1}{2} \|\vec w\|^2 + C \sum_{i=1}^{m} \xi^{(i)} \tag {12}$w,b,ξ(i)min​21​∥w∥2+Ci=1∑m​ξ(i)(12)

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

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

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

$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)

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

$\vec w =\sum_{i=1}^{m} \alpha^{(i)} y^{(i)} \vec x^{(i)}$w=i=1∑m​α(i)y(i)x(i)

$0 = \sum_{i=1}^{m} \alpha^{(i)} y^{(i)}$0=i=1∑m​α(i)y(i)

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

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

$\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}$αmax​i=1∑m​α(i)−21​i=1∑m​j=1∑m​α(i)α(j)y(i)y(j)Ki,j​

$s.t. \sum_{i=1}^{m} \alpha^{(i)} y^{(i)} = 0$s.t.i=1∑m​α(i)y(i)=0

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

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

$\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条件中我们可以看出, 对任意的训练样本 $(\vec x^{(i)}, y^{(i)})$(x(i),y(i)), 总有 $\alpha^{(i)} = 0$α(i)=0 或 $y^{(i)} f(\vec x^{(i)}) = 1 - \xi^{(i)}$y(i)f(x(i))=1−ξ(i).

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

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

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

$\min_{f} \Omega(f) + C\sum_{i=1}^{m} l(f(\vec x^{(i)}) , y^{(i)})$fmin​Ω(f)+Ci=1∑m​l(f(x(i)),y(i))

其中, $\Omega(f)$Ω(f) 称为"结构风险"(structural risk), 用于描述模型 $f$f 自身的性质; 第二项 $C\sum_{i=1}^{m} l(f(\vec x^{(i)})$C∑i=1m​l(f(x(i)) 称为"经验风险"(empirical risk), 用于描述模型与训练数据的契合程度. $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

既然深度学习技术性能表现以及全面超越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

[2] 西瓜书

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

https://zhuanlan.zhihu.com/p/29212107