统计学习精要(The Elements of Statistical Learning)课堂笔记（二十）：SVM

这节课主要是讲线性优化的对偶问题。感觉这东西貌似在运筹学的时候被折腾过一遍，现在又来了-_-||

附赠个老的掉牙的段子...

有人问经济学家一个数学问题，经济学家表示不会解...

然后那个人把这个数学问题转成了一个等价的最优化问题，经济学家立马就解出来了...

好吧，我还是乖乖的赘述一遍对偶问题吧，表示被各种经济学最优化问题折磨过的孩子这点儿真是不在话下。

--------------------------------------------------------------------

1. 对偶问题的一般情况

1) 优化问题

一个典型的最优化问题形如：

(不等式约束)

（等式约束）

2) 优化问题的Lagrange （拉格朗日）函数

3) 对偶函数

称为该优化问题的对偶函数。此时，

，显然这个时候一阶偏导数为0。

4) 对偶问题

我们称为原优化问题的对偶问题，可化为最优化问题的标准形式。

如果原优化问题为凸优化，则必为凹函数，从而最终的标准形式依旧是一个凸优化问题。

5) 弱对偶性

令为原问题的解，则，且，.

令为对偶问题的解，则; .

定理（弱对偶性）：，即对偶问题的优化值必然小于等于原问题优化值。

6) 强对偶性

当时，两者具有强对偶性；满足该条件的称之为constraint qualifications，如Sliter定理。

强对偶性满足的时候，原优化问题就可以化为一个二步优化问题了。

7) KTT条件（库恩-塔克条件）

局部最优化成立的必要条件：

（一阶条件）

注：SVM满足强对偶性，所以可以直接解对偶问题。

2. 对偶问题应用于SVM

1) SVM的最优化问题

上节课可知，SVM的最优化问题为：

写成标准形式就是

这样这里总计有2N个约束条件。

对应的Lagrange函数为：

这样一阶条件就是

这样最后我们有.

3) 对偶函数

这里的对偶函数就是

4) 对偶问题

5) KKT条件

6) SVM分类器

• 解对偶问题，得到,
• 计算
• 计算：找到一个（非边界上），从而满足。由，我们可得
• 平面分类器: , ，故只与内积有关。

这样下节课就会讲到解对偶问题的方法，以及SVM和kernel methods的联系。