如何将支持向量机的数学公式转化为二次规划目标函数形式?
如何将支持向量机的数学公式转化为二次规划目标函数形式?
嘿,这个问题其实是把SVM的核心逻辑套进二次规划(QP)的标准框架里,咱们一步步拆解清楚,你就能对应上了:
首先,先回顾下硬间隔SVM的核心目标:
我们要最大化两类样本之间的垂直间隔,也就是你推导出来的$||\lambda|| = 2/||w||$。要最大化这个间隔,等价于最小化$||w||$——不过为了后续计算方便(尤其是求导的时候),我们通常把目标转化为最小化$\frac{1}{2}w^Tw$,因为平方操作不会改变最优解的位置,加个1/2是为了求导后系数更简洁(避免出现多余的2)。
接下来,咱们把这个目标对应到你给出的QP标准形式$\frac{1}{2}w^TQw + c^Tw$:
- 对比一下,这里的$Q$就是单位矩阵$I$,因为$w^Tw = w^TIw$;
- 而$c$是全零向量,因为SVM的目标里没有线性项$c^Tw$。
所以SVM的目标函数放到QP框架里就是:
$$\frac{1}{2}w^TIw + 0^Tw$$
然后是最关键的约束条件部分:
SVM的原始约束是针对每个训练样本$(x_i, y_i)$的($y_i \in {+1, -1}$是样本标签),要求每个样本都在间隔的正确一侧(或者刚好落在间隔边界上),也就是:
$$y_i(w^Tx_i - b) \geq 1$$
把这个式子整理一下,就能适配QP的$Aw \leq d$形式了:
- 先把偏置$b$也当成优化变量,和$w$合并成一个新的变量向量$\tilde{w} = \begin{bmatrix} w \ b \end{bmatrix}$;
- 把每个样本的约束改写为:
$$-y_i[x_i^T, -1]\tilde{w} \leq -1$$
这时候,QP框架里的矩阵$A$的每一行就是$-y_i[x_i^T, -1]$,向量$d$的每个元素都是$-1$。
另外要注意:你给出的QP标准里有$w \geq 0$的约束,但硬间隔SVM本身对$w$没有非负要求,这个是某些特定QP框架的附加条件,SVM转化时可以忽略这个约束,或者说明这不是必须的。
最后,把完整的转化总结一下:
- 优化变量:$\tilde{w} = \begin{bmatrix} w \ b \end{bmatrix}$(包含权重$w$和偏置$b$)
- QP目标函数:$\frac{1}{2}\tilde{w}^T\begin{bmatrix} I & 0 \ 0 & 0 \end{bmatrix}\tilde{w} + 0^T\tilde{w}$
这里的$Q$是块对角矩阵,前半部分对应$w$的单位矩阵,后半部分对应$b$的元素为0(因为目标里没有$b$的平方项) - QP约束条件:对每个训练样本$i$,$\begin{bmatrix} -y_i x_i^T & y_i \end{bmatrix}\tilde{w} \leq -1$,也就是$A\tilde{w} \leq d$,其中$A$的第$i$行是$\begin{bmatrix} -y_i x_i^T & y_i \end{bmatrix}$,$d$的第$i$个元素是$-1$。
如果是允许部分样本违反间隔的软间隔SVM,还会引入松弛变量$\xi_i \geq 0$,目标函数会变成$\frac{1}{2}w^Tw + C\sum_{i=1}^n\xi_i$,约束也会相应调整,但核心的转化逻辑和硬间隔是一致的。
备注:内容来源于stack exchange,提问作者euraad




