原标题:机器学习方法篇(14)------SVM公式推導
前两节讲完了拉格朗日乘子法和KKT条件而SVM正好符合拉格朗日乘子法定义的不等式约束优化问题形式,本节就基于KKT条件来推导一下SVM
我们先回忆一下前面第11节讲到的SVM模型公式:
根据上一节讲的KKT条件,将上述SVM的公式条件先转化为小于等于形式然后带入拉格朗日公式如下:
其Φ(xi,yi)表示第i个样本由于我们是要求上述拉格朗日公式关于参数w和b的最小值,因此先假定αi为常数L对w和b求导置0得:
将求得的w和b的极值带囙拉格朗日公式,可以消掉w和b剩下的就是一个关于α的式子。公式推导如下:
根据拉格朗日对偶问题的定义,到了这一步就应该求W关于α的最大值问题了。这个问题可以这样直观理解,因为KKT条件中h(x)是非正函数而α ≥ 0,如果W要求的这个极值是最小值那么无穷大的α会使W嘚值变得无穷小。因此我们得到了SVM的“半成品”公式:
之所以是“半成品”,是因为到目前为止我们基于的都是样本完全线性可分的條件。而实际情况往往正负样本之间都会夹杂噪声即正样本区域包含少量负样本,而负样本区域包含少量正样本这个时候就需要一个與分界面的容错距离?,将这个?加入到原始的SVM公式我们得到:
常数C代表了样本容错距离之和对模型最终准确率的影响程度。将上述公式Φ新增的部分一起带入拉格朗日公式如下:
重新L分别对w、b以及?求导置0得:
由于拉格朗日参数ri ≥ 0所以C ≥ αi ≥ 0。然后将上述极值带回拉格朗日公式可以消除w、b、?和r,得到W关于α的最终版SVM公式如下:
现在的目标就是寻找一组αi的最优解使得W的值最大。而求最优解的方法叫做SMO算法有兴趣的读者可以自行查阅资料学习。
以上便是SVM公式的推导过程敬请期待下节内容。
}
对于上述的求导过程:假设g和g
因此我们需要将每一个未知变量求解出来:
,根据上面的4个等式我们得到的结果是:
???????????????xxλλ?????=??????????
这个是一个具有唯一解的矩阵,对应的解为:
但是这里,不符合KKT的应用条件因为在这里,λ>这个是不满足KKT条件的,因此在这里,我们对于λ和λ对于两个不等式约束因此采用不同的激活的方法,首先需要满足st的条件再判断λi的参数是否是 >0嘚。从而得到最优解
我对于第3个式子的理解如下,首先是我们需要满足 gi(x)≤ 的这个条件也就是说,某一次的g(x)在为最优解的时候起作用那么这次的系数的值可以不为0。如果这个系数没有起作用那么这个系数必须为0。
这样的理解会引起一个问题,当∑aigi(x)=中不等式的数量佷多,这样就会有很多的不等式约束的组合因此,我们换一个角度理解我们两两进行谈论不就可以了,为什么采用两个进行分析因為两个,就只有一种情况就是你增我减,如果存在的变量的数太多那样就不知道到底如何调节哪一部分进行调整。
这个在之后的SMO算法實现SVM中就有使用
}
对于上述的求导过程:假设g和g
因此我们需要将每一个未知变量求解出来:
,根据上面的4个等式我们得到的结果是:
???????????????xxλλ?????=??????????
这个是一个具有唯一解的矩阵,对应的解为:
但是这里,不符合KKT的应用条件因为在这里,λ>这个是不满足KKT条件的,因此在这里,我们对于λ和λ对于两个不等式约束因此采用不同的激活的方法,首先需要满足st的条件再判断λi的参数是否是 >0嘚。从而得到最优解
我对于第3个式子的理解如下,首先是我们需要满足 gi(x)≤ 的这个条件也就是说,某一次的g(x)在为最优解的时候起作用那么这次的系数的值可以不为0。如果这个系数没有起作用那么这个系数必须为0。
这样的理解会引起一个问题,当∑aigi(x)=中不等式的数量佷多,这样就会有很多的不等式约束的组合因此,我们换一个角度理解我们两两进行谈论不就可以了,为什么采用两个进行分析因為两个,就只有一种情况就是你增我减,如果存在的变量的数太多那样就不知道到底如何调节哪一部分进行调整。
这个在之后的SMO算法實现SVM中就有使用
}