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

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

本文背景   

SVM硬间隔模型损失函数求解的原始问题如下：

目标函数：                                 

约束条件：,  

一般不直接对该问题求解，而是转为对偶问题，再进行求解。也即是说，SVM所有与求解相关的内容，都不是面向以上损失函数，而是面向损失函数的对偶问题，本文讲解如何推导SVM硬间隔损失函数的对偶问题和推导结果。

提示：阅读前请先了解拉格朗日乘子法以及KKT条件，可参阅《拉格朗日乘子法-带约束优化》

一、原问题的对偶问题

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

1.1. 对偶问题

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

其中，

原问题的优化目标为： 

原问题 :

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

对偶问题 :

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

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

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

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

原问题与对偶问题的解就相等，且两个问题的解满足KKT条件。

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

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

(1) 易知，   和 是凸函数

(2) 是严格可执行的：

     由于假设数据是线性可分的，故一定存在一组w,b, 满足：   。

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

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

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

二、化简对偶问题

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

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

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

(一) 对偶问题

上面得到对偶问题如下：

目标函数：

约束条件:                                                                                                                 

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

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

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

目标函数：   ,

约束条件:  (1)    ,                                            

                 (2)              ,                                           

2.2. 对偶问题化简-推导过程

目的: 去除 部分

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

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

对w中的第j个元素求偏导，有

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

当时，

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

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

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

由于在,  时取得最小值，因此：

对偶问题

优化目标：           

约束条件：  ,     

等价于：

优化目标：                  

 约束条件：(1)                  

        (2) 

                  (3), 

利用约束条件简化如下(下面省去max,min前缀)：

* 第二个等号利用了
* 第五个等号利用了
* 第六个等号是把第五个等号改写为向量形式。

Step-4.  化简后的结果

对偶问题即可化简为：

目标函数：

 约束条件：(1)                                                  

(2) ,               

也可表述为：

目标函数：  

约束条件： (1)                                              

(2) ,           

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

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

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

通过对偶问题的解求原问题解 可用如下公式：

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

3.2. 公式推导过程

(一) w的公式推导

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

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

 

(二) b的公式推导

又由KKT条件可知，满足"最优解在每个拉格朗日约束条件均为0"，如下：

即有：

  , 

找出一个不为0的项，则有：

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

补充证明：必有一个不为0，如果全为0，则  为0，而不是原问题的解，因为不满足约束条件：将代入原问题约束条件得到 ，而 有{-1，+1} 两种取值，必有不满足约束条件的时候。

四、SVM-硬间隔-支持向量的定义

w,b的公式如下：

从公式来看，w是由的样本加权组成，b也是由 的样本组成，总的来说，模型最后其实就是由这些的样本组成，所以，的样本就是关键样本，称的样本为“支持向量”。

这些的样本有什么特性呢？

对于的样本，

由：

即，它要么为1，要么为-1，这说明所对应的样本只落在支持平面上，之前所定义的“落在支持平面的样本称为支持向量”，就是“的样本是支持向量”的几何定义。

结束语

总的来说，SVM是先把原始损失函数转换为拉格朗日乘子法中的对偶问题，然后通过求解对偶问题，从而得到原始损失函数中的解。本文讲述的是硬间隔模型的损失函数的对偶问题，事实上这是为了理解软间隔模型所做的铺垫，因为它们的思想是相同的，在理解硬间隔模型的基础上再理解软间隔模型，相对容易一些。