本站原创文章，转载请说明来自《老饼讲解-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