第二层、深入SVM
2.1、从线性可分到线性不可分
2.1.1、从原始问题到对偶问题的求解
虽然上文1.4节给出了目标函数,却没有讲怎么来求解。现在就让我们来处理这个问题。回忆一下之前得到的目
标函数(subject to导出的则是约束条件):
由于求 的最大值相当于求 的最小值,所以上述问题等价于(w由分母变成分子,从而也有原来的max
问题变为min问题,很明显,两者问题等价):
1. 到这个形式以后,就可以很明显地看出来,它是一个凸优化问题,或者更具体地说,它是一个二次优化问
题——目标函数是二次的,约束条件是线性的。这个问题可以用任何现成的 QP (Quadratic
Programming) 的优化包进行求解;
2. 但虽然这个问题确实是一个标准的 QP 问题,但是它也有它的特殊结构,通过 Lagrange Duality 变换到对偶变量 (dual
variable) 的优化问题之后,可以找到一种更加有效的方法来进行求解,而且通常情况下这种方法比直接使用通用的 QP 优化
包进行优化要高效得多。
也就说,除了用解决QP问题的常规方法之外,还可以应用拉格朗日对偶性,通过求解对偶问题得到最优解,这
就是线性可分条件下支持向量机的对偶算法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然
的引入核函数,进而推广到非线性分类问题。
ok,接下来,你将看到“对偶变量dual variable的优化问题”等类似的关键词频繁出现,便是解决此凸优化问
题的第二种更为高效的解--对偶变量的优化求解。
至于上述提到,关于什么是Lagrange duality?简单地来说,通过给每一个约束条件加上一个 Lagrange
multiplier(拉格朗日乘值),即引入拉格朗日对偶变量 ,如此我们便可以通过拉格朗日函数将约束条件融和到目标
函数里去(也就是说把条件融合到一个函数里头,现在只用一个函数表达式便能清楚的表达出我们的问题):
然后我们令
容易验证,当某个约束条件不满足时,例如 ,那么我们显然有 (只要令
即可)。而当所有约束条件都满足时,则有 ,亦即我们最初要最小化的量。因此,
在要求约束条件得到满足的情况下最小化 ,实际上等价于直接最小化 (当然,这里也有约束
条件,就是 ) ,因为如果约束条件没有得到满足, 会等于无穷大,自然不
会是我们所要求的最小值。具体写出来,我们现在的目标函数变成了:
这里用 表示这个问题的最优值,这个问题和我们最初的问题是等价的。不过,现在我们来把最小和最大的
位置交换一下(稍后,你将看到,当下面式子满足了一定的条件之后,这个式子d 便是上式P 的对偶形式表示):
当然,交换以后的问题不再等价于原问题,这个新问题的最优值用 来表示。并且,我们有 ≤ ,这
在直观上也不难理解,最大值中最小的一个总也比最小值中最大的一个要大吧! 总之,第二个问题的最优值
在这里提供了一个第一个问题的最优值 的一个下界,在满足某些条件的情况下,这两者相等,这个时候我们
就可以通过求解第二个问题来间接地求解第一个问题。
上段说“在满足某些条件的情况下”,这所谓的“满足某些条件”就是要满足KKT条件。那KKT条件的表现形式是什么呢?