老饼讲解-神经网络 机器学习 神经网络 深度学习
SVM支持向量机

【硬间隔】SVM硬间隔损失函数的对偶问题

作者 : 老饼 发表日期 : 2022-11-05 15:37:31 更新日期 : 2022-11-14 13:42:29
本站原创文章,转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com



SVM硬间隔模型损失函数的求解较为困难,一般是转为对偶问题再进行求解

本文讲解SVM硬间隔模型损失函数对偶问题的推导和相关意义



   背景   


硬间隔的损失函数求解原始问题如下:
目标函数:                                 
约束条件:,  
一般不直接对该问题求解,而是转为对偶问题,再进行求解
 也即是说,SVM所有与求解相关的内容,
都不是面向以上损失函数,而是面向损失函数的对偶问题,

 本文讲解如何推导SVM硬间隔损失函数的对偶问题和推导结果




    01. 原问题的对偶问题    


本节使用拉格朗日函数的方法,直接获得原始问题的对偶问题

本节只为获得对偶问题,本节得到的对偶问题在形式上较为原始,下节再进行化简


    对偶问题    


原问题中带有约束条件,
一般先转为拉格朗日函数形式,
再通过交换拉格朗日函数形式中的优化顺序来获得对偶问题
拉格朗日函数形式:
 
 
其中
 原问题的优化目标为: 
原问题 :

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



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


满足以下两个条件
1. 目标函数与约束条件是凸函数                  
2.约束条件里,是严格可执行的(即一定有解)
原问题与对偶问题的解就相等,且两个问题的解满足满足KKT条件
下面检查硬间隔SVM求解问题和它的对偶问题是否满足以上两个条件
 (1) 易知,   和 是凸函数          
(2) 是严格可执行的:                            
由于假设数据是线性可分的                                   
故一定存在一组w,b, 满足   
因此,原问题与对偶问题的解相等,
即      
故原问题求解可转化为对偶问题的求解,
且原问题取得的解与对偶问题的解 满足KKT条件.
 PASS:这很重要,怎么用 推出 ,依据的就是它们满足KKT条件,



   02. 化简对偶问题    


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

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


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


对偶问题
上面得到对偶问题如下
目标函数:
约束条件:                                                                                                               
对其进行化简,化简过程主要是通过求导去除 部分
对偶问题的化简结果
对偶问题最终得到的化简结果如下(推导过程见下文):
目标函数:   ,
约束条件:  (1)    ,                                         
 (2)              ,                       



   对偶问题化简的推导过程    


目的与思路
 目的: 去除 部分                                                                                     
思路: 可以让对w,b求导,取得取最小值时,w,b的值      
(1) 对w偏导,令其为0
对w中的第j个元素求偏导,有
 

推广到w的所有元素, 则有 :
时,

 备注:这里的都是k维的列向量
(2) 对b偏导,令其为0
(3) 利用偏导为0时的结果,化简对偶公式 :
由于 时取得最小值,
对偶问题
优化目标:                           
 约束条件:                       
等价于
优化目标:                                   
 约束条件:(1)                                    
 (2)             
            (3)              
利用约束条件简化如下(下面省去max,min前缀):
 
                    
 

----------------------------------------------------------
由 可知
----------------------------------------------------------
                                               
                                                     ----写成向量乘法      
(4) 化简后的结果
对偶问题即可化简为:
目标函数:
 约束条件:(1)                                                  
(2)                
也可表述为
 目标函数:
 约束条件: (1)                                          
(2)      




   03. 对偶解 反推 原问题的解   


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


   对偶解反推原解的公式   


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


  其中b*的求解公式中的下标i,取不为0的任意一项即可,
例如
不为0,则即可



   公式推导过程   


解出w的公式推导
由KKT条件可知,
对偶问题的解与原问题的解
满足"最优解在一阶偏导点为0",如下:
 
 

上面已经推导过,
时,
即有
 
解出b的公式推导
又由KKT条件可知, 满足
"最优解在每个拉格朗日约束条件均为0",如下:
 

即有
  , 

找出一个不为0的项,则有:

 
代入上面求得的 ,
并由
得到:
✍️补充 
必有一个不为0,如果全为0, 则  为0, 
不是原问题的解,
因为不满足约束条件:
代入原问题约束条件得到 
 有{-1,+1} 两种取值,必有不满足约束条件的时候



   04. 一些相关定义补充   



    支持向量的定义   


w,b的公式如下,
                    
 
从公式来看,w是由的样本加权组成
b也是由 的样本组成,
总的来说,模型最后其实就是由这些的样本组成,
所以,的样本就是关键样本,
的样本为“支持向量”
这些的样本有什么特性呢?
对于的样本


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





 End 










联系老饼