线性(可分)支持向量机

Support Vector Machines

支持向量机,SVM

SVM应用于二分类问题。

输入空间和特征空间为两个不同的空间。输入空间为欧式空间或离散集合,特征空间为欧式空间或希尔伯特空间。

线性可分SVM和线性SVM在两个空间的元素一一对应,非线性SVM是非线性映射。

本篇中的SVM都指线性可分SVM,其它SVM可能会有一些变化

线性可分支持向量机

假定训练集线性可分。

数据集:假定特征空间上的训练集$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中

$x_i∈\mathbb R^n,y_i∈\{+1,-1\},i=1,2,\cdots,N$,$x_i$为第$i$个特征向量,$y_i$为类标记。当$y_i=+1$,称$x_i$为正例;当当$y_i=-1$,称$x_i$为负例。$(x_i,y_i)$称为样本点

具体举例:如正例点$x_i=(3,5),y_1=+1$,$(3,5)$存在于欧式空间而$(x_1,+1)$存在于特征空间

学习目标:在特征空间上找到一个分离超平面,能将实例分到不同的类。分离超平面对应于方程$w·x+b=0$,由法向量$w$和截距$b$决定,可以用$(w,b)$表示。其将特征空间划分为两部分:法向量指向的一侧为正类,另一侧为负类。

理解这个超平面:$w·x+b=0$中$w,x,b$都是向量,向量中每一个位置都是一个特征维度,可以理解为这个超平面有很多个维度,在每一个维度都有一个分界线,从而整体构成一个高维度的超级分界面。

这个超平面就是分类器

显然这种超平面是有无穷个的。对于感知机,则是使用误分类最小策略来求得超平面;对于线性可分SVM,则使用间隔最大化来求得最优超平面,解是唯一的。

线性可分支持向量机:给定线性可分训练数据集,通过间隔最大化等价地求解相应的凸二次规划问题学习得到的分离超平面为(学习得到的最优参数就是$w^o,b^o$)

对应的分类决策函数为:

也就是:

称为线性可分支持向量机。注意其中的决策函数只有两种取值:$+1,-1$,对应了决策函数通过$f(x)=sign(w^o·x_i+b^o)$来判断点$x_i$是正例还是负例。$sign$是符号函数。

确信度:一个点如果距离超平面越远,那么表示其预测的确信度越高,反之反之。假设一个样本点越正向远离分界面,那么我们越认为其为正例的概率越大,方向远离分界面那么负例的概率越大。

点$x$距离超平面的距离 $=|w·x+b|$

$w·x_i+b$的符号若与训练样本$x_i$的标签$y_i$一致,则分类正确;不一致则分类错误。

从逻辑斯谛回归LR来理解SVM

LR的输出是一个概率输出,LR实际上就是将通过线性分类器$w·x+b,x∈\mathbb R^n$将输入$x$映射到概率空间$(0,1)$上,其越靠近上边界$1$,就认为其标签为$1$的概率越高;其越靠近下边界$0$,就认为其标签为$0$的概率越高,这时候我们可以给一个决策标准$th=0.5$,对于一个样本$x_i$和逻辑斯谛回归分类器$f(w·x+b)$(也可以表示为$P(Y=1|x)$),此时对$x_i$的决策结果就是$f(x_i)=\begin{cases} 1,f(w·x_i+b)≥0.5\\ 0,f(w·x_i+b)<0.5 \end{cases}$

如果我们将LR中的决策标准的阈值改为$0$,分类器改为$f(w·x+b)=w·x+b$,标签从$0,1$改为$-1,+1$,此时对$x_i$的分类结果就是:$f(x)=\begin{cases} +1,w·x_i+b≥0\\ -1,w·x_i+b<0 \end{cases}$。震惊,这不就是个标准的SVM了吗!

LR中的$0$相当于SVM的负例,$1$相当于SVM的正例;

LR中的阈值$0.5$,而SVM的阈值为$0$,即在SVM中,分类器的输出$≥0$,就判断为正例,$<0$就判断为负例;分类器输出越大则样本为正例的概率越大(确信度越高),输出越小则样本为负例的概率越大(确信度越高)。(SVM分类器输出的绝对值乘以标签($+1 or-1$):$y_i|w·x_i+b|$即为函数间隔

LR的分类器输出在$(0,1)$上,且决策阈值为$0.5$;而SVM的分类器输出可以在$(-∞,+∞)$,决策阈值为$0$。为什么分类器输出差别这么大?因为LR的输出值是线性分类器$w·x+b$的逻辑斯谛分布作为映射,就是它将输出映射到了$(0,1)$上,其恰好就是概率。而线性SVM的分类器就直接是一个线性函数映射,它的输出映射到了整个实域

结论:LR和SVM本质是一样的。借LR可以更好地理解SVM(这段写得有点啰嗦)。

间隔表示

前面引出了间隔,这里具体定义。对于样本点$(x_i,y_i)∈T$到超平面$(w,b)$。

某点到超平面面的函数间隔:

样本集$T$所有点到面的函数间隔:这就是前面所说的我们最想要的最优超平面的标准(见上):

如果$w,b$成比例改变,那么实际上超平面$\lambda w·x_i+\lambda b=0=w·x_i+b=0$并没有变,但是函数间隔却番倍了,所以我们要统一让超平面的参数标准化,使得该间隔确定。所以标准化后,得:

某点到超平面面的几何间隔:(其实就是欧式空间中的点到平面的距离公式再加个正负来判断分类正确性)

样本集$T$所有点到面的几何间隔:

函数间隔和几何间隔的特点:同时表示了分类的「正确性」和「确信度」(确信度见上文理解,正确性是因为如果分类错误,那么算出来的间隔会是;分类正确才会得出正值,根据式子容易看出来)

函数间隔无论如何改变,几何间隔都是不变的。表征特征空间上的关系的是几何间隔。(也就是SVM最常见的那个图)

显然有函数间隔$\hat \gamma$与几何间隔$\gamma$的关系:$\gamma_i=\frac{\hat \gamma_i}{||w||},\gamma=\frac{\hat \gamma}{||w||}$

($||w||$为向量$w$的第二范数,即$||w||=\sqrt{w_1^2+w_2^2+\cdots+w_n^2} $),后面取其平方以去掉根号方便计算)

硬间隔最大化

学习SVM的过程就是学习最优超平面的过程,也就是确定超平面$w·x+b$的参数$w,b$

什么是我们想要的最优的超平面(分类器):「尽可能提高难以分类的点的分类确信度」。

从几何角度解释:使得离超平面最近的样本点到超平面的距离最大的超平面,「也就是说要尽量扩大超平面离超平面最近点间隔」。这就是间隔最大化

间隔最大化可以表述为:(推导起点,从最大化几何间隔开始)

即:尽量提高几何间隔的下限

需求解使得目标函数最优的参数$w,b$

为了由$\gamma_i=\frac{\hat \gamma_i}{||w||},\gamma=\frac{\hat \gamma}{||w||}$,可把问题改写(但实际还是几何间隔)为用函数间隔表示为:

$\max_{w,b}\frac{\hat\gamma}{||w||}$

$s.t.\quad y_i(w·x_i+b)≥\hat\gamma,i=1,2,\cdots,N$

前面说过,函数间隔不会影响解的结果,也就是将$w,b$按比例改变,函数间隔虽然变了,但超平面是没变的。

于是,我们想到直接将函数间隔人为设定为1,就相当于让$w,b$以一个比例缩放,使得函数间隔$\hat\gamma=1$,这个乘上的比例因子是多少我们不需要求它,因为即使$w,b$以一个未知的比例等比缩放了,求得的超平面还是一样的,约束优化问题还是等价的,(此时几何间隔为$\gamma=\frac{1}{||w||}$),也就是将问题等价简化为

$\max_{w,b}\frac{1}{||w||}$

$s.t.\quad y_i(w·x_i+b)≥1,i=1,2,\cdots,N$

显然$\max_{w,b}\frac{1}{||w||}$等价于$\min_{w,b}\frac{1}{2}||w||^2$,则原问题改写为一个易于求解的凸二次规划问题

求得该凸二次规划问题即可得到最优解$w^o,b^o$。注意这里是不等式约束问题,而前面比如在MEM中的是等式约束问题。

由此得到分离超平面$w^o·x+b^o=0$,分类决策函数$f(x)=sign(w^o·x+b^o)$

这个求解过程就是线性可分SVM的学习算法:最大间隔法(maximum margin method)

线性可分SVM的最大间隔分离超平面存在唯一(证略)


支持向量(support vector):训练数据集中的样本点与分离超平面距离最近的样本点的实例

支持向量点$(x_i,y_i)$是使得约束条件取等号:$y_i(w·x_i+b)-1=0$的点

对于正例:$y_i=+1,支持向量在超平面\quad w·x+b=1$上;

对于负例:$y_i=-1,支持向量在超平面\quad w·x+b=-1$上

支持向量到超平面的距离就是几何间隔$\gamma=\frac{\hat \gamma}{||w||}$,由于设定了$\hat \gamma=1$,则$\gamma=\frac{1}{||w||}$

两个超平面的距离称为间隔(margin)。$\therefore 间隔 =\frac{2}{||w||}$,两个超平面称为间隔边界。

支持向量在确定分离超平面上取决定性作用,SVM实际上是由很少的重要的训练样本——支持向量所确定的,所以才得名支持向量机(Support Vector Machines)

通过拉格朗日对偶性求解硬间隔最大化

也叫线性可分SVM的对偶算法(dual alogorithm)。这样做①对偶问题往往更容易求解②自然引入核函数,可以进而推广到非线性SVM

见前面拉格朗日乘子与对偶性专题,这里就不详细解释了。

对于上一节的凸二次规划问题,首先引入拉格朗日函数(这里$w,b$是我们的目标变量,相当于标准形式中的$x$)

这里是减去拉格朗日乘子项(加乘子项也可以,但推理表示会麻烦一些,所以记得用减乘子项!)

注意这里设置减去算子项,是为了后面用KKT条件的时候,构造出$\alpha_i≥0$(不等式约束的乘子$\alpha$要规定$\alpha≥0$,是为了满足后文KKT的对偶可行条件)

根据拉格朗日对偶性,KKT条件是凸问题的充要条件,转换为等价对偶问题

于是求内部问题$\min_{w,\beta}L(w,b,\alpha)$:

对两个独立变量的子式使用零导数法:

$\nabla_w L(w,b,\alpha)=w-\sum_{i=1}^N\alpha_iy_ix_i=0$(注意第二范数求导:见后记2)

$\nabla_b L(w,b,\alpha)=-\sum_{i=1}^N\alpha_iy_i=0$

$\therefore w=\sum_{i=1}^N\alpha_iy_ix_i$

$\sum_{i=1}^N\alpha_iy_i=0$(不能丢,作为对偶问题的约束条件!除非是像第一个能够将原式所有的$w$全部替换的形式,这样该约束条件实质就已经被完全包含在代入后的式子中而失效了,才可以丢)

回代$L(w,b,\alpha)$得:

$L(w,b,\alpha)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i·x_j)-\sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jy_jx_j)·x_i+b)+\sum_{i=1}^N\alpha_i$

$=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i·x_j)+\sum_{i=1}^N\alpha_i$

这里注意①2-范数运算,见后记3 ②无关求和代入的时候,求和符号的迭代变量要换一个以免重合

内部问题求解出来了,于是问题等价为外部问题,求:

$\max_\alpha-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i·x_j)+\sum_{i=1}^N\alpha_i$

$s.t.\quad \quad\sum_{i=1}^N\alpha_iy_i=0,\quad \alpha_i≥0,\quad i=1,2,\cdots,N$

转化为易求的$\min$形式,此为求解算法的第一步公式:

于是这里就用通用的算法来求解此二次规划问题(用SMO求解,见后面的专题)

假设已经求出对偶最优化的最优解为$\alpha^o$,于是可以求得原始最优化对$(w,b)$的解:$w^o,b^o$

KKT条件是凸问题的充要条件,则原始问题与对偶问题完全等价,$w^o,b^o$就是最优解(前面已经说明过等价,这里再强调一下)

于是可以得到:可以由等价关系得:拉格朗日表达式对$w$求导得到见上求对偶问题最小化的时候,就已经求出来了内部极值$w^o,b^o$与$\alpha$的关系表达式;也可以由对偶问题的KKT的$w$梯度条件:

$\nabla_wL(w^o,\beta^o,\alpha^o)=0$得到)(顺便后记-6附上了这里的所有KKT条件表达式):

对于$\alpha_i≥0$,至少存在一个$\alpha_j>0$(反证法,若全$=0$,则回代上面公式得$w=0$,非解,矛盾;另外该乘子对应的样本点就是支持向量

将此$\alpha_j$代入$y_j(w^o·x_j+b^o)-1=0$中,又由于$y_j^2=1$,$y_i$取值只有$1或-1$,则:

根据前面原始问题中超平面的定义,将两个参数代入超平面公式和决策函数公式即可,

支持向量的导出:将训练数据集中对应于$\alpha^o_i>0$的样本点$(x_i,y_i)$的实例$x_i∈\mathbb R^n$称为支持向量

(容易知道,因为仅对$\alpha_i^o>0$的实例有$y_i(w^o·x_i+b^o)-1=0$,则该点$x_i$一定在间隔边界上)

可以看到:

①分类决策函数只依赖于输入$x$和训练样本中的支持向量的内积

②训练的时候,$b^o,w^o$的取值只与$\alpha_i^o>0$的样本$x_i$有关,也就是只和支持向量有关。

这与前面定义的概念相符

线性可分SVM学习算法总结

由上可得,线性可分支持向量机学习算法:略(整理整理就是了)

线性支持向量机

我们引入松弛变量$\epsilon_i≥0$,使得$y_i(w·x_i+b)+\epsilon_i≥1$,也即$y_i(w·x_i+b)≥1-\epsilon_i$

同时目标函数变为$\frac{1}{2}||w||^2+C\sum_{i=1}^N\epsilon_i$(引入目的是使得对每个松弛变量$\epsilon_i$都支付一个代价$\epsilon_i$,代价也可以设定为$\epsilon^2$等)

$C>0$是惩罚参数,值越大则对误分类的惩罚越大,反之反之

$C$是需要自己设定的

问题变成了软间隔最大化

需求解使得目标函数最优的参数$w,b,\epsilon$

此目标函数即包含了①前项表使得间隔尽量小②后项表使得误分类点尽量少,$C$即是二者的调和系数

注意用拉格朗日乘子法依然是减去乘子项,依然注意求得的对偶问题约束条件

对于求得的对偶约束条件被用来消去之后,$C-\alpha_i-\mu_i=0,\alpha_i≥0,\mu_i≥0$会被合写为$0≤\alpha_i≤C$,且可以证得不能取等号,即为:$0<\alpha_i<C$

最后推得的结果会发现,与线性可分SVM的区别在于约束条件多了一个限制:$0<\alpha_i<C,i=1,2,\cdots,N$,在计算$w^o$的时候,选取的$\alpha^o_j$需要考虑此条件(也就是说不符合此条件的$\alpha^o_j$对应的$x_j$会被忽略掉,或者说不拿来训练模型这些点就是不可分点、误分类点、非支持向量点。我们可以类比线性可分SVM,在线性可分SVM中计算$w$时候,选$\alpha_j$的约束条件为$\alpha^o_j>0$,也就是说只获取支持向量(事实上此约束不成立的点即$\alpha^o_j=0$,回代$w$即发现$x_j$与原式无关,自然也就等同于“选择$\alpha^o_j>0$”,但在线性SVM的约束$0<\alpha_i<C,i=1,2,\cdots,N$中,就真的是要选择了))

具体来说:对于实例$x_i$到间隔边界的距离为$\frac{\epsilon_i}{||w||}$。

若$\alpha^o_i<C$,则$\epsilon_i=0$,支持向量$x_i$恰好落在间隔边界上;

若$\alpha^o_i=C,0<\epsilon_i<1$,则分类正确,$x_i$在间隔边界与分离超平面之间;

若$\alpha^o_i=C,\epsilon_i=1$,则$x_i$在分离超平面上;若$\alpha^o_i=C,\epsilon_i>1$,则$x_i$位于分离超平面误分类一侧。

$b$的解可能不是唯一的(但一般实践只会出现一种情况)

整体推导方法和线性可分SVM差不多,这里

合页损失函数是线性SVM的另一种结束,这里

后记

  1. 凸二次规划问题

    其中目标函数$f(w)$和约束函数$g_i(w)$都是$\mathbb R^n$上的连续可微凸函数,约束函数$h_i(w)$是$\mathbb R^n$上的仿射函数。

    在此之上,当目标函数$f(w)$是二次函数且约束函数$g_i(w)$是仿射函数时,上述凸最优化问题转化为凸二次规划问题。

    凸二次规划问题满足拉格朗日对偶性中的Slater条件和KKT条件

  2. 2-范数求导

    $\frac{\partial\frac{1}{2}||w||^2}{\partial w}=\frac{\frac{1}{2} \partial(\sqrt{w_1^2+w_2^2+\cdots+w_n^2})^2}{\partial (w_1,w_2,\cdots,w_n)}=\frac{\frac{1}{2} \partial (w_1^2+w_2^2+\cdots+w_n^2)}{\partial (w_1,w_2,\cdots,w_n)}$

    $=(\frac{\frac{1}{2} \partial w_1^2}{\partial (w_1,w_2,\cdots,w_n)},\frac{\frac{1}{2} \partial w_2^2}{\partial (w_1,w_2,\cdots,w_n)},\cdots,\frac{\frac{1}{2} \partial w_n^2}{\partial (w_1,w_2,\cdots,w_n)})$

    对于每个子分子中的求导变量$w_i$,分母中只有$w_i$为对应维度的变量,所以是对每个维度分别求导

    $\therefore 原式 = (w_1,w_2,\cdots,w_n)=w$

  3. 范数计算

    $x$是向量,$x$的2-范数:$||x||=||x·x^T||$

    $\therefore ||w||^2=w^Tw$

    $\therefore ||\sum_{i=1}^N\alpha_iy_ix_i||=(\sum_{i=1}^N\alpha_iy_ix_i)·(\sum_{j=1}^N\alpha_jy_jx_j)^T=\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i·x_j)$

    和式就两两交叉相点乘

    这个式子中只有$x$是向量,$\alpha,y$都视为$x$向量的系数

  4. 注意求和函数的作用域,如果作用域内还有迭代变量,不能直接局部求和

  5. $w·x=w^Tx$

  6. 上面学习算法中对偶问题的KKT表达式

    $\nabla_w(w^o,b^o,\alpha^o)=w^o-\sum_{i=1}^N\alpha_i^oy_ix_i=0$

    $\nabla_b(w^o,b^o,\alpha^o)=-\sum_{i=1}^N\alpha_i^oy_i=0$

    $\alpha_i^o(y_i(w^o·x_i+b^o)-1)=0\quad,i=1,2,\cdots,N$

    $y_i(w^o·x_i+b^o)-1≥0\quad,i=1,2,\cdots,N$

    $\alpha_i^o≥0\quad,i=1,2,\cdots,N$