线性支持向量机中KKT条件的讨论
线性支持向量机中KKT条件的讨论
此处的模型为训练样本不可分时的线性支持向量机,简称为线性支持向量机。即考虑松弛变量
原始问题
则线性不可分的线性支持向量机的学习问题变成如下的凸二次规划(convex quadratic programming)问题,即原始问题
对偶问题
原始问题的拉格朗日函数为
对偶问题拉格朗日函数的极大极小问题,得到以下等价优化问题
KKT条件
原始问题的解对偶问题的解相同需要满足KKT对偶互补条件,即
对样本
Platt在序列最小优化(SMO)方法1中提到,对正定二次优化问题(a positive definite QP problem)的优化点的充分必要条件为KKT条件(Karush-Kuhn-Tucker conditions)。
对于所有的
其中
KKT条件的推导
下面我们将要讨论如何从式(1)、(2)得到式(3) ~ (5)。
(1)
由
则由式(2)可知,
再由原始问题的约束条件
(2)
将
又
因为
又由式(1),有
(3)
由式(1),有
因为
即可得式(3) ~ (5),KKT条件得以推导。
KKT条件的几何解释
在线性不可分的情况下,将对偶问题的解
如下图所示,分离超平面由实线表示,间隔用虚线表示,正例由“o”表示,负例由“x”表示。实例
软间隔的支持向量
这里可以从两种角度来解释,第一种角度就像李航在《统计学习方法》第113页中用到间隔边界的距离边界
若
α∗i<C ,则ξi=0 ,支持向量xi 恰好落在间隔边界上;
若α∗i=C,0<ξi<1 ,则分类正确,xi 在间隔边界与分离超平面之间;
若α∗i=C,ξi=1 ,则xi 在分离超平面上;
若α∗i=C,ξi>1 ,则xi 位于分离超平面误分一侧。
现在我们要从另外一种角度,也就是KKT条件(式(3)~(5)),通过数学推导来得到上面的结果。
在间隔边界上
由式(3)可知,当
在间隔边界与分离超平面之间
当
则说明
在分离超平面上
当
即
在分离超平面误分一侧
当
则分类错误,
以上就是对线性支持向量机中KKT条件的仔细讨论,从公式推导和几何意义上一同解释了为什么
这是我在看书的时候不是很明白的问题,现在通过理论上的推导能够清楚地得到结果,也希望能够解答其他有同样问题人的疑惑。
问题是越思考越清楚,希望在今后的学习中继续保持这种认真对待知识的态度。
- 李航. 统计学习方法[J]. 清华大学出版社, 北京, 2012. ↩