支持向量机&＃xff08;SVM&＃xff09;是一种二类分类模型&＃xff0c;它的基本模型是定义在特征空间上的间隔最大的线性分类器&＃xff0c;间隔最大使它有别于感知机&＃xff1b;支持向量机还包括核技巧&＃xff0c;这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化&＃xff0c;可形式化为一个求解凸二次规划的问题&＃xff0c;也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

线性可分支持向量机/硬间隔支持向量机

线性可分支持向量机

假设输入空间与输出空间为两个不同的空间&＃xff0c;输入都是由输入空间转换到特征空间&＃xff0c;支持向量机的学习是在特征空间上进行的。当数据线性可分时&＃xff0c;存在无穷多个分类超平面可将两类数据正确分开。感知机利用误分类最小的策略&＃xff0c;这时有无穷多个解&＃xff0c;线性可分支持向量机使用间隔最大化求最优分离超平面&＃xff0c;这时&＃xff0c;解是唯一的。

函数间隔和几何间隔

通常来说&＃xff0c;一个点距离分离超平面的远近可以表示分类预测的确信程度。分离超平面(w,b)关于样本点(xi,yi)(xi,yi)的函数间隔为&＃xff1a;

.定义超平面关于训练数据集T的函数间隔为超平面关于T中所有样本点的函数间隔最小值&＃xff0c;即



对分离超平面的法向量w加某些约束&＃xff0c;如规范化

||w||&＃61;1||w||&＃61;1,使得间隔是确定的。

||w||||w||为向量w的l2范数&＃xff0c;这时函数间隔变为几何间隔。

分离超平面(w,b)关于样本点

(xi,yi)(xi,yi)的几何间隔为&＃xff1a;

.定义超平面关于训练数据集T的函数间隔为超平面关于T中所有样本点的函数间隔最小值&＃xff0c;即

超平面关于样本点的几何距离一般是实例点到超平面的
带符号的距离&＃xff0c;当样本点分类正确时就是样本点到超平面的距离。

间隔最大化

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。
间隔最大化的直观解释是&＃xff1a;对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。
将间隔最大化问题转换为凸二次规划问题&＃xff1a;

化为这个形式之后&＃xff0c;公式中只有w,b变量需要求解。

线性可分训练数据集的最大间隔分离超平面是存在且唯一的。

“间隔”

2||w||2||w||&＃xff0c;“间隔边界”,支持向量&＃xff1a;“使约束条件中等式成立的点”。

在决定分离超平面时只有支持向量起作用&＃xff0c;而其它实例点并不起作用。支持向量的个数一般很少&＃xff0c;所以支持向量机由很少的“重要的”训练样本确定。

学习的对偶算法

将上述的最优化问题作为原始最优化问题&＃xff0c;应用拉格朗日对偶性&＃xff0c;通过求解对偶问题得到原始问题的最优解&＃xff0c;这就是线性可分支持向量机的对偶算法。这样做的优点&＃xff0c;一是对偶问题往往更容易求解&＃xff1b;二是引入核函数&＃xff0c;因而推广到非线性问题。
看了书上关于原始问题与对偶问题的讲述之后&＃xff1a;
1.原始问题可以转换为极小问题
2.与这个最小最大问题相对应的有极大极小问题&＃xff0c;这个极大极小问题就是原始问题的对偶问题&＃xff0c;对偶问题的解并不一定就等于原始问题的解&＃xff0c;但在这种条件下二者相等&＃xff1a;1.f(x)和c(x)均为凸函数&＃xff1b;2.存在x使c(x)满足约束。
但在线性可分的条件下一定满足这两个条件&＃xff0c;因此可以用求对偶问题来求原始问题并得到解。
在求解对偶问题中拉格朗日乘子α∗i>0αi∗>0的实例点称为支持向量。

线性支持向量机/软间隔支持向量机

线性支持向量机

对于线性不可分的训练数据需要修改硬间隔最大化&＃xff0c;使其成为软间隔最大化。
具体做法&＃xff1a;对每一个样本点引入一个松弛变量ξi⩾0ξi⩾0,使函数间隔加上松弛变量大于等于1&＃xff0c;这样约束条件变为&＃xff1a;

,同时&＃xff0c;对每一个松弛变量支付一个代价

ξiξi&＃xff0c;目标函数变为&＃xff1a;

这里

C>0C>0称为惩罚参数。因此&＃xff0c;最小化目标函数包含两层意思&＃xff1a;使

12||w||212||w||2尽量小即间隔尽量大&＃xff0c;同时使误分类点的个数尽量少。

学习的对偶算法

如线性可分支持向量转换为对偶形式一样&＃xff0c;线性支持向量机也可以化为对偶形式。

支持向量

支持向量&＃xff1a;在求解对偶问题中拉格朗日乘子α∗i>0αi∗>0的实例点称为支持向量。
支持向量的位置有α∗i,ξ∗αi∗,ξ∗决定。

合页损失函数

对于线性支持向量机学习来说&＃xff0c;其模型为分离超平面w∗⋅x&＃43;b∗&＃61;0w∗⋅x&＃43;b∗&＃61;0,决策函数f(x)&＃61;sign(w∗⋅x&＃43;b∗)f(x)&＃61;sign(w∗⋅x&＃43;b∗),其学习策略为软间隔最大化&＃xff0c;学习算法为凸二次规划。
线性支持向量机的学习还有另外一种解释&＃xff0c;就是最小化以下目标函数&＃xff1a;

目标函数的第一项是经验损失或经验风险&＃xff0c;函数

L(y(w⋅x&＃43;b))&＃61;[1−y(w⋅x&＃43;b)]&＃43;L(y(w⋅x&＃43;b))&＃61;[1−y(w⋅x&＃43;b)]&＃43;称为合页损失函数。下标&＃43;表示取正值的函数。

合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的&＃xff0c;直接优化由其构成的目标函数比较困难&＃xff0c;可以认为线性支持向量机是优化由0-1损失函数的上界&＃xff08;合页损失函数&＃xff09;构成的目标函数。这时的上界损失函数又称为代理损失函数。

当与感知机的损失函数

[−yi(w⋅xi&＃43;b)]&＃43;[−yi(w⋅xi&＃43;b)]&＃43;对比,合页损失函数不仅要分类正确&＃xff0c;而且置信度足够高时损失才是0.也就是说合页损失函数对学习有更高的要求。

非线性支持向量机与核函数

本节叙述非线性支持向量机&＃xff0c;主要特点是利用核技巧。

核技巧

非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。如果能用RnRn的一个超曲面将正负例正确分开&＃xff0c;则称这类问题为非线性可分问题。
用线性分类方法求解非线性分类问题分为两步&＃xff1a;首先使用一个变换将原空间的数据映射到新空间&＃xff1b;然后在新空间使用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。
核技巧应用到支持向量机&＃xff0c;其基本想法就是通过一个非线性变换将输入空间&＃xff08;欧式空间或离散集合&＃xff09;对应于一个特征空间&＃xff08;希尔伯特空间&＃xff09;&＃xff0c;使得在输入空间中的超曲面模型对应于特征空间中的超平面模型。

正定核

半正定矩阵

常用核函数

1.多项式核函数
K(x,z)&＃61;(x⋅z&＃43;1)pK(x,z)&＃61;(x⋅z&＃43;1)p为p次多项式分类器
2.高斯核函数
K(x,z)&＃61;exp(−||x−z||22δ2)K(x,z)&＃61;exp(−||x−z||22δ2)

非线性支持向量机

将线性支持向量机扩展到非线性支持向量机&＃xff0c;只需要将线性支持向量机中对偶形式中的内积换成核函数。

序列最小最优化算法SMO

SMO是一种启发式算法&＃xff0c;其基本思路是&＃xff1a;如果所有变量的解多满足此最优化问题的KKT条件&＃xff0c;那么这个最优化问题的解就得到了&＃xff0c;否则选择两个变量&＃xff0c;固定其他变量&＃xff0c;针对这两个变量构建一个二次规划问题。其中至少一个变量是违反KKT条件的&＃xff0c;另一个变量的值有约束条件自动确定&＃xff0c;第二个变量的选择标准是能够使它有较大的变化。

面试中常问问题&＃xff1a;
1.SVM如何解决多类分类问题&＃xff1f;
SVM算法最初是为二值分类问题设计的&＃xff0c;当处理多类问题时&＃xff0c;就需要构造合适的多类分类器。目前&＃xff0c;构造SVM多类分类器的方法主要有两类&＃xff1a;一类是直接法&＃xff0c;直接在目标函数上进行修改&＃xff0c;将多个分类面的参数求解合并到一个最优化问题中&＃xff0c;通过求解该最优化问题“一次性”实现多类分类。这种方法看似简单&＃xff0c;但其计算复杂度比较高&＃xff0c;实现起来比较困难&＃xff0c;只适合用于小型问题中&＃xff1b;另一类是间接法&＃xff0c;主要是通过组合多个二分类器来实现多分类器的构造&＃xff0c;常见的方法有one-against-one和one-against-all两种。
a.一对多法&＃xff08;one-versus-rest,简称1-v-r SVMs&＃xff09;。训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类&＃xff0c;这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
b.一对一法&＃xff08;one-versus-one,简称1-v-1 SVMs&＃xff09;。其做法是在任意两类样本之间设计一个SVM&＃xff0c;因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时&＃xff0c;最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。
c.层次支持向量机&＃xff08;H-SVMs&＃xff09;。层次分类法首先将所有类别分成两个子类&＃xff0c;再将子类进一步划分成两个次级子类&＃xff0c;如此循环&＃xff0c;直到得到一个单独的类别为止。
对c和d两种方法的详细说明可以参考论文《支持向量机在多类分类问题中的推广》&＃xff08;计算机工程与应用。2004&＃xff09;
d.其他多类分类方法。除了以上几种方法外&＃xff0c;还有有向无环图SVM&＃xff08;Directed Acyclic Graph SVMs&＃xff0c;简称DAG-SVMs&＃xff09;和对类别进行二进制编码的纠错编码SVMs。