本站原创文章,转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com
SVM软间隔模型损失函数的求解较为困难,一般是转为对偶问题再进行求解
本文讲解SVM软间隔模型损失函数对偶问题的推导和相关意义
背景
软间隔的损失函数求解原始问题如下:
目标函数:
约束条件: (1) ,
(2)
一般不直接对该问题求解,而是转为对偶问题,再进行求解
本节使用拉格朗日函数的方法,直接获得原始问题的对偶问题
本节只为获得对偶问题,本节得到的对偶问题在形式上较为原始,下节再进行化简
对偶问题
原问题中带有约束条件,
一般先转为拉格朗日函数形式,
再通过交换拉格朗日函数形式中的优化顺序来获得对偶问题
拉格朗日函数形式:
其中
原问题的优化目标为:
原问题 :
交换优化顺序即可获得对偶问题
对偶问题 :
原问题转为对偶问题的可行性
满足以下两个条件
1. 目标函数与约束条件是凸函数
2.约束条件里,是严格可执行的(即一定有解)
原问题与对偶问题的解就相等,且两个问题的解满足满足KKT条件
下面检查软间隔SVM求解问题和它的对偶问题是否满足以上两个条件
(1) 易知, 、和 都是凸函数
(2) ,是严格可执行的:
很明显,要满足 , 只需将取得足够大即可以
因此,原问题与对偶问题的解相等,
即
故原问题求解可转化为对偶问题的求解,
且原问题取得的解与对偶问题的解 满足KKT条件.
PASS:这很重要,怎么用 推出 ,依据的就是它们满足KKT条件,
本节将上节获得的对偶问题进行化简,使问题更易解决,
本节获得的对偶问题形式,就是求解时使用的形式
对偶问题的化简思想和结果
化简对偶问题 主要是通过求导去除 部分,
最终得到的化简结果如下:
目标函数:
约束条件: (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) ,
本节讲解如何使用对偶最优解反推出原问题的最优解,包括转换的公式和推导的过程
对偶解反推原解的公式
通过对偶问题的解求原问题解 :
其中b*的求解公式中的下标i,取的下标,
例如,则取即可
公式推导过程
解出w的公式推导
由KKT条件可知,
对偶问题的解与原问题的解
满足"最优解在一阶偏导点为0",如下:
上面已经推导过,
当时,
即有
解出b的公式推导
又由KKT条件可知,
对偶问题的解与原问题的解满足:
(1) "最优解在一阶偏导点为0",即:
上面已求得,即有
(2) "最优解在每个拉格朗日约束条件均为0" ,即:
也即:
找出一个满足 的 ,
再 由 ,可知不为0,又,故
代入上面求得的 ,
并由
得到:
End