【模型】SVM-损失函数-对偶问题(软)

SVM软间隔模型损失函数的求解较为困难，一般是转为对偶问题再进行求解，本文讲解SVM软间隔模型损失函数对偶问题的推导和相关意义。

本文背景

软间隔的损失函数求解原始问题如下：

目标函数：                          

约束条件： (1) ,      

(2)                    

一般不直接对该问题求解，而是转为对偶问题，再进行求解。

一、原问题的对偶问题

本节使用拉格朗日函数的方法，直接获得原始问题的对偶问题，本节只为获得对偶问题，下节再进行化简。

1.1. 对偶问题

原问题中带有约束条件，一般先转为拉格朗日函数形式，再通过交换拉格朗日函数形式中的优化顺序来获得对偶问题。原问题所对应的拉格朗日函数形式为：

其中

原问题的优化目标为： 

原问题 :

交换优化顺序即可获得对偶问题：

对偶问题 :

1.2. 原问题转为对偶问题的可行性

已知，满足以下两个条件：

   1. 目标函数与约束条件是凸函数

   2. 约束条件里，是严格可执行的(即一定有解)

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

下面检查硬间隔SVM求解问题和它的对偶问题是否满足以上两个条件。

(1) 易知， 、和 都是凸函数。

(2) ，是严格可执行的。

     很明显，要满足 , 只需将取得足够大即可以。

因此，原问题与对偶问题的解相等，即：

故原问题求解可转化为对偶问题的求解，且原问题取得的解与对偶问题的解 满足KKT条件。

PASS：这很重要，怎么用 推出 ，依据的就是它们满足KKT条件。

二、化简对偶问题

本节将上节获得的对偶问题进行化简，使问题更易解决。

本节获得的对偶问题形式，就是求解时使用的形式。

2.1. 对偶问题的化简思想和结果

(一) 对偶问题

上面得到对偶问题如下：

目标函数：

约束条件：                                                                                 

对其进行化简，化简过程主要是通过求导去除 部分。

(二) 对偶问题的化简结果

对偶问题最终得到的化简结果如下(推导过程见下文)：

目标函数： 

约束条件:  (1)                                            

    (2)     , 

2.2. 推导过程

目的: 去除 部分

思路: 可以让对求导,取得取最小值时 的值。

Step-1：对w偏导，令其为0

对中的第个元素求偏导，并令其为0，有：

推广到w的所有元素，则有 ：

当时，

备注：这里的和都是k维的列向量。

Step-2：对b偏导，令其为0

Step-3：对 偏导，令其为0

对中的第i个元素求偏导，并令其为0，有：

Step-4：利用偏导为0时的结果，化简对偶公式：

由于在符合以上条件取得最小值，

因此，对偶问题

优化目标：                               

约束条件：  ,                     

等价于

优化目标：                                      

约束条件：(1)                                              

(2)                       

     (3) , 

(4) ,             

(5) ,             

进一步，利用约束条件简化如下(这里忽略max前缀)：

* 第二个等号参考硬间隔形式的结果。
* 第三个等号 利用  。

Step-5：化简后的结果

对偶问题即可化简为：

目标函数：

约束条件：(1)                                                  

(2) ,        

备注： 是由 ,  ,  得到。
由于，而，从而，再结合 ，则有。

也可表述为：

目标函数：

约束条件： (1)                                            

  (2) ,  

三、对偶解 反推 原问题的解

本节讲解如何使用对偶最优解反推出原问题的最优解，包括转换的公式和推导的过程。

3.1. 对偶解反推原解的公式

通过对偶问题的解求原问题解 ：

其中的求解公式中的下标，取任意一项满足的即可，例如，则取即可。

3.2. 公式推导过程

(一) 解出w的公式推导

由KKT条件可知，对偶问题的解与原问题的解满足"最优解在一阶偏导点为0"，如下：

上面已经推导过，当时，，即有：

 

(二) 解出b的公式推导

又由KKT条件可知，对偶问题的解与原问题的解满足如下条件：

(1) "最优解在一阶偏导点为0"，即：

上面已求得，即有：

(2) "最优解在每个拉格朗日约束条件均为0" ，即：

也即：

找出一个满足  的   ，再 由  ,可知不为0，又,故 ，因此有：

代入上面求得的 ，并由，得到：

四、支持向量

最后，我们一起来看看SVM软间隔模型的支持向量是什么。

4.1. 软间隔模型-支持向量

与硬间隔模型类似，由于模型的表示为：

可知，模型的均是由的样本所构成，所以将的样本称为“支持向量”。

4.2. 软间隔模型-支持向量-是哪些样本

在讲述前，先晒一下相关公式：

当取得最优解时，满足如下三式(详见上文内容)：

(一) ξ的意义

接下来，我们来看一下当时的意义。

由(3)式可得，可知和分别是样本与判别面、支持面的距离。

(二) 支持向量是哪些样本

由上面的内容可知，，但只有的才是支持向量，事实上，它分为两种情况，一种是，另一种是，下面分别看这两种情况下的支持向量分别是什么。

【1】当样本的时，必为0，此时样本落在支持面上。

推导：由(1)式可得，时，，再由(2)式就可得到。

【2】当样本的时，必大于0，此时样本落在支持面的错误一侧。

推导：只需要证明时就可以了，这只需从目标函数分析即可：
                 目标函数：
从目标函数中可以看到，如果，将会消掉最后一项，而要令目标函数最优，必是越小越好，因此必不会取到C，具体需要详细分步讨论，这里不再展开。

4.3. 软间隔模型-支持向量-总结

总的来说，的样本就是支持向量：

它共包含了两类样本：

当样本的时，必为0，此时样本落在支持面上。
当样本的时，必大于0，此时样本落在支持面的错误一侧。

整体上，就是除了落了支持面正确一侧的样本，其余的都是支持向量。

结束语

总的来说，SVM软间隔的对偶问题的推导和硬间隔在思路上基本是一致的，只不过软间隔更为复杂繁琐一些，这主要是加入了更多的约束条件，但不管怎么样，它们都是用拉格朗日乘子法，来消除约束条件，并通过对偶问题来求得原问题的最优解，只要耐心些，软间隔的推导也不难理解。