Support Vector Machines - Part 1
支持向量机 - SVM(Support Vector Machines)Part 1
支持向量机 - SVM(Support Vector Machines)Part 1
- 线性可分支持向量机学习算法 - 最大间隔法
- 线性可分支持向量机的对偶算法
支持向量机 - SVM(Support Vector Machines)Part 2
- 线性支持向量机
- 核函数及非线性支持向量机
- 常用的核函数及其特点
支持向量机 - SVM(Support Vector Machines)Part 3
- 序列最小最优化(SMO)算法
支持向量机 - SVM(Support Vector Machines)Part 4
- 支持向量回归 - SVR
目录
- 基本概念
- 线性可分支持向量机学习算法 - 最大间隔法
- 线性可分支持向量机的对偶算法
- 特点
1. 基本概念
定义函数间隔(用$\hat{\gamma}$表示)为:
超平面$(w,b)$关于训练数据集$T$中所有样本点$ (x_i, y_i) $的函数间隔最小值,即为超平面$ (w,b) $关于训练数据集$T$的函数间隔:
其中$n$表示样本点数量。[问题:将$w$和$b$成比例改变为$\lambda w$和$\lambda b$,函数间隔的值也会变化为原来的$\lambda$倍],因此自然地引出几何间隔的概念。
定义几何间隔(用$\gamma$表示)为:
其中$||w||$为$w$的$L_2$范数。
由上可知,
即,几何间隔等于函数间隔与$w$二阶范数的商。
回到原始的问题中,我们需要最大间隔(几何间隔)分离超平面,即:
考虑几何间隔和函数间隔的关系,可以将上面的问题改写成:
由于函数间隔$ \hat{\gamma} $的取值并不影响最优化问题的解[可以认为函数间隔通过$\lambda$放缩后变为1,这样最优化问题中含有一个常数因子], 这样令函数间隔$\hat{\gamma}=1$代入上面的最优化问题,同时,$ \max \frac{\hat{\lambda}}{||w||} $、$ \max \frac{1}{|| \lambda w ||} $与$ \min \frac{1}{2} ||w||^2 $是等价的。 所以上述最优化问题最终可以归结为以下最优化问题:
现在目标函数和约束条件都是连续可微的凸函数,所以可以通过拉格朗日对偶性,通过求解与对偶问题等价的对偶问题得到原始问题的最优解, 这样的优点:一、对偶问题往往更容易求解;二、自然的引入核函数,推广到非线性分类问题。
2. 线性可分支持向量机学习算法 - 最大间隔法
输入:线性可分训练数据集$T=\lbrace(x_1,y_1),(x_2,y_2),…,(x_n,y_n)\rbrace $,其中$ x_i \in \chi=R^n, y_i \in \mathcal{y} = \lbrace -1, +1 \rbrace, i=1,2,…,n$
输出:最大间隔分离超平面和分类决策函数
(1)构造并求解约束最优化问题
求的最优解$ w^{\ast},b^{\ast} $。
(2)由此得到分离超平面:
分类决策函数
3. 线性可分支持向量机的对偶算法
首先由最优化问题$式(9) \sim 式(10)$,构建拉格朗日函数,引入拉格朗日乘子$ \alpha_i \geq 0, i=1,2,…,n $
其中$ \alpha = (\alpha_1, \alpha_2, …, \alpha_n)^T $。
根据拉格朗日对偶性,原始问题:
[这个地方有点绕,注意内部的极大后等价与原约束问题,理解拉格朗日对偶性]
对偶问题:
求解对偶问题
(1)求 $ \min_{w,b} L(w,b,\alpha)$
插播二范数的求导公式如下:
将拉格朗日函数$L(w,b,\alpha)$分别对$w,b$求偏导数并令其等于0.
得
将式(21)代入拉格朗日函数(15),并利用式(22),即得
倒数第5步推导倒数第4步利用了线性代数的转置运算,由于$\alpha_i$和$y_i$都是实数,因此转置后与自身一样。 倒数第4步到倒数第3步使用了$ (a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+… $的乘法运算规则。
即:
(2)求$ \min_{w,b} l(w,b,\alpha) $对$\alpha$的极大,即是对偶问题:
将式(25)的目标函数由求极大转化为求极小,就得到下面与之等价的对偶最优化问题:
$式(28) \sim 式(30)$要解决的是在参数$( \alpha_1, \alpha_2, …, \alpha_n )^T$上求极值的问题,我们需要利用序列最小最优化(SMO)算法解决。 限于篇幅及知识递进程度,具体SMO算法在Support Vector Machines - Part 3详细描述。
(3)求参数$w^{\ast}, b^{\ast}$
这样假设已经求出了$ \alpha^{\ast}=(\alpha_1^{\ast}, \alpha_2^{\ast}, …, \alpha_n^{\ast})^T $后,从而根据$KKT$条件得:
在$y=-1, y=1$的类别中,支持向量处于边界上,根据$KKT$条件$ \alpha_i^{\ast}(y_i(w^{\ast}x_i+b)-1)=0 $, 至少有一个$\alpha_j^{\ast}>0$[反证法,假设$\alpha^{\ast}=0$,则$w^{\ast}=0$,而$w^{\ast}=0$不是原始最优化问题的解,产生矛盾!], 所以,对此$j$有
即可求出$w^{\ast},b^{\ast}$,最终得出分离超平面
分类决策函数
4. 特点
SVM 函数间隔(functional margin)为$ \hat{\gamma}=y(wx+b)=yf(x) $,其中的$y$是只取1和-1吗?$y$的唯一作用就是确保函数间隔(functional margin)的非负性?
(1)二分类问题中,$y$只取两个值,而且这两个值是可以任意取的;
(2)求解的超平面分开的两侧的函数值的符号是刚好相反的;
(3)为了问题简单化,取了$y$的值为$1$和$-1$。
在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量(support vector),支持向量是使约束条件$ y_i(w\cdot x_i +b) -1=0 $成立的点,如下图$H_1和H_2$上的点。
在决定分离超平面时,只有支持向量起作用,其他样本点并不起作用。如果移动支持向量,将会改变分离超平面,移动其他样本点则无影响。支持向量一般个数较少。
为什么令函数间隔为1?
函数间隔可以表征样本被分到某一类的置信度,比如说$y_i=+1$时,如果$f(x_i) = w \cdot x_i +b >0$且很大,说明$(x_i,y_i)$离分类边界很远,我们有理由相信$x_i$是正类。
另外我们知道成比例改变$w,b$,分离超平面不变,几何间隔也不改变
因此可以做变量替换,将最优化问题改变为函数间隔为1。这样,在不影响最优化问题的前提下,改变了最优化函数并简化了计算。
参考
July - 支持向量机通俗导论
李航 - 《统计学习方法》