SVM推导过程中的三个疑问
总阅读次
在形式化推导硬间隔（不允许分错）SVM分类器的时候，会做一些简化和转换，初看时并不那么好懂。最近又接触到SVM，所以从头到尾又学习了一遍。写下关于几个以前不太懂的疑问以及疑问的回答。
为何令间隔为1？
在SVM中是以最大化分类间隔为目标的，间隔又分函数间隔和几何间隔。
函数间隔为： $\hat\gamma=y_if(x_i)=y_i(w^Tx_i+b)$
几何间隔为： $\gamma=\frac {y_if(x_i)} {||w||}$
函数间隔可以表征样本被分到某一类的置信度，比如说$y_i=+1$时，如果$w^Tx_i+b > 0$且很大，说明离分类边界越远，越有理由相信$x_i$真的是正类。
成倍的增长$w,b$，分类超平面不变，几何间隔也不改变
而我们优化通常是优化几何间隔，因为几何间隔在$w,b$成倍增长时，是不变的。
即优化问题转化为：$$max_{w,b} \frac {\hat\gamma} {||w||} \
s.t. y_i(w^Tx_i+b) = \hat\gamma_i \ge \hat\gamma$$
设$\hat\gamma$为最小函数间隔,约束条件是任意给一个点，其函数间隔一定大于等于$\hat\gamma$，即最小函数间隔。
做一个变量替换$w’=w/{\hat\gamma}, b’=b/{\hat\gamma}$，代入原来的优化问题可得新的优化问题：
$$max_{w’,b’} \frac {1} {||w’||} \
s.t. y_i({w’}^Tx_i+b’) \ge 1$$
此时关于$w,b$的原问题等价成了新的$w’,b’$的新问题。能够这样转化的原因在于函数间隔的取值并不影响最优化问题的解。
什么是拉格朗日对偶？
上述优化问题可以写为：
$$min \frac {1} {2}||w||^2 \
s.t. y_i({w’}^Tx_i+b’) \ge 1,i=1,2,..,m$$
目标函数是二次的，约束是是线性的，这是一个凸二次规划问题，可以用QP求解。但是还可以通过拉格朗日对偶来解。
拉格朗日对偶解法即求解与原问题等价的对偶问题得到原问题的最优解。
采用拉格朗日乘子法，写出拉格朗日乘子式：
$$\mathcal{L}(w,b,\alpha)=\frac {1} {2}||w||^2 - \sum_{i=1}^n \alpha_i(y_i(w^Tx_i+b)-1)$$
令$$\theta(w)=max_{\alpha_i \ge 0}\mathcal{L}(w,b,\alpha)$$
可以看出，当$(y_i(w^Tx_i+b)-1)<0$时，即条件不满足时，由于$\alpha_i \ge 0$，所以后面一半（包括负号）是正的，当$\alpha_i$取得很大的时候，$\theta(w)$甚至可以取到无穷大；当条件满足时，后面一项是负的，所以$\theta(w)=max_{\alpha_i \ge 0}\mathcal{L}(w,b,\alpha)$最大就是$\frac {1} {2}||w||^2$。
所以做$\theta(w)$的目的就出来了，即
$\theta(w)=f(w) $ if w满足条件
$\theta(w)=\infty $ 否则
所以原问题$$min \frac {1} {2}||w||^2 \
s.t. y_i({w’}^Tx_i+b’) \ge 1,i=1,2,..,m$$
就可以通过拉格朗日乘子法换成无约束的等价的另一种表示
$$min_{w,b}\theta(w)=min_{w,b} max_{\alpha_i \ge 0}\mathcal{L}(w,b,\alpha)$$
设$p^\ast$为上述问题的最优解。
上述问题直接求解很难，所以交换一下min，max的顺序将其变成对偶问题
$$max_{\alpha_i \ge 0} min_{w,b} \mathcal{L}(w,b,\alpha)$$
最优解用$d^\ast$来表示。
转换为对偶问题后相对容易求解，要注意此时$d^\ast$并不一定等于$p^\ast$，(且
其实$d^\ast \le p^\ast$，直观的说就是“胖子里面最瘦的通常比瘦子里面最胖的要胖”，这也是有证明的)。即原问题的解并不一定等于对偶问题的解，如果等于，我们称之为强对偶(strong duality)，在满足一定条件的情况下，是可以达到强对偶的。
Slater条件： 存在严格满足约束条件的点。
如果原始问题是Convex的并且满足Slater条件的话，我们说它是强对偶的。Slater条件只是使强对偶成立的一种情况，事实上，非凸优化也可以是强对偶的。
通过强对偶成立时的一些性质，我们可以推出一些条件，比如
什么是KKT条件？
上述这些就是所谓的KKT条件。
任何强对偶问题都满足KKT条件。
当原始问题可微且是凸优化问题时，KKT条件升级成充分必要条件。
前两条说明达到最优解时，拉格朗日函数对w,b求偏导为0
第三条称为complementary slackness（互补松弛），即我们的
$$\alpha_i(y_i(w^Tx_i+b)-1)=0$$
那么为什么呢？做下列推导，假设$x^\ast,\alpha^\ast$分别为原问题和对偶问题的极值点：
$$f_0(x^\ast)=min_{w,b} \mathcal{L}(w,b,\alpha) \
=min_x (f_0(x) - \sum_{i=1}^n \alpha_i(y_i(w^Tx_i+b)-1)) \
\le f_0(x^\ast)-\sum_{i=1}^n \alpha_i^\ast(y_i(w^Tx^\ast_i+b)-1) \
\le f_0(x^\ast)$$
由于等式两遍相等，所以可以换成等号，由于第三行，且$\sum_{i=1}^n \alpha_i^\ast(y_i(w^Tx^\ast_i+b)-1)$非负，所以推出$ \alpha_i^\ast(y_i(w^Tx^\ast_i+b)-1)=0, i=1,2,…,m$
即当$\alpha_i>0$时，$x_i$正在分类间隔上，称为支持向量，而不在分类间隔上的样本有$\alpha_i=0$
后两条为原来的约束条件。图中的$g_i(w^\ast)$即我们的$(1-y_i({w^\ast}^Tx_i+b^\ast))$。
满足了KKT条件，就可以认为对偶问题的最优解就是原问题的最优解，这样我们就可以通过求解对偶问题来求解原来的优化问题。
By the way，SVM的对偶问题为：
总结
所以总结一下，令几何间隔为1是为了保证优化问题等价的情况下，尽可能地简化问题。使用拉格朗日对偶是因为原问题不好解，所以转化成对偶问题，而当问题满足KKT条件的时候，这个对偶问题的解就是原问题的解，从而更好地得到最优解。
简单梳理了一下这三个问题，知识浅薄，如果有不对的希读者不吝指出。
