其它神经网络

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

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


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

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


   背景   


软间隔的损失函数求解原始问题如下:
目标函数:                                 
约束条件: (1) ,      
 (2)                      
一般不直接对该问题求解,而是转为对偶问题,再进行求解




    01. 原问题的对偶问题    


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

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


    对偶问题    


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

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


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


满足以下两个条件
1. 目标函数与约束条件是凸函数                  
2.约束条件里,是严格可执行的(即一定有解)
原问题与对偶问题的解就相等,且两个问题的解满足满足KKT条件
下面检查软间隔SVM求解问题和它的对偶问题是否满足以上两个条件
 (1) 易知, 、 都是凸函数       
(2) 是严格可执行的:                            
很明显,要满足 , 只需将取得足够大即可以 
因此,原问题与对偶问题的解相等,
即      
故原问题求解可转化为对偶问题的求解,
且原问题取得的解与对偶问题的解 满足KKT条件.
 PASS:这很重要,怎么用 推出 ,依据的就是它们满足KKT条件,




   02. 化简对偶问题    


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

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


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


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


    推导过程    


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

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

时,

 备注:这里的都是k维的列向量
(2) 对b偏导,令其为0
(3) 对 偏导,令其为0
中的第i个元素求偏导,并令其为0,有
(4) 利用偏导为0时的结果,化简对偶公式 :
由于在以下条件取得最小值,
      
          
 
对偶问题
优化目标:                                         
 约束条件:                                
等价于
优化目标:                                                 
 约束条件:(1)                                                         
 (2)                                
(3) , 
            (4)                              
           (5)                             

利用约束条件简化
如下:
 

第二个等号参考硬间隔形式的结果            
第三个等号 利用    
(4) 化简后的结果
对偶问题即可化简为:
目标函数:
 约束条件:(1)                                                  
(2)                
备注: 是由  ,    得到
与 两个条件的合并            
也可表述为
 目标函数:
 约束条件: (1)                                          
(2)           



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


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


   对偶解反推原解的公式   


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

  其中b*的求解公式中的下标i,取的下标,
例如
,则即可



   公式推导过程   


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

上面已经推导过,
时,
即有
 
解出b的公式推导
又由KKT条件可知, 
对偶问题的解与原问题的解满足:
(1) "最优解在一阶偏导点为0",即:                                     
           
上面已求得,即有
 
(2) "最优解在每个拉格朗日约束条件均为0" ,即:                           
  
也即:
                           



找出一个满足  的   ,
再 由  ,可知不为0,又,故 
 
代入上面求得的 ,
并由
得到:






 End 











联系老饼