作者:mobiledu2502917953 | 来源:互联网 | 2023-09-18 10:35
1.线性SVM对两类点的划分问题,这里对比下逻辑回归和SVM的区别:逻辑回归的思想是,将所有点到决策平面的距离作为损失来进行训练,目标是到决策平面的距离和最小SVM的思想是,只
1. 线性SVM
对两类点的划分问题,这里对比下逻辑回归和SVM的区别:
- 逻辑回归的思想是,将所有点到决策平面的距离作为损失来进行训练,目标是到决策平面的距离和最小
- SVM的思想是,只关注支持向量(图中圈出的点)到决策平面的距离,最大化这个距离。
对于所有样本点 \(\{(x_i,y_i)\}, i = 1,2,\cdots, m\) ,SVM划分正负样本,即 \(y\in\{1,-1\}\) ,则有:
\[ \begin{align} \begin{cases} y_i = +1, w^Tx_i +b >0\\ y_i = -1, w^Tx_i +b<0 \end{cases} \end{align} \]
这里对式子(1)进行一个放缩变换。超平面由参数对 \((w,b)\) 决定,若超平面 \((w',b')\) 能将样本正确分类,那么总存在一个放缩变换 \(\zeta w \mapsto w'\) 和 \(\zeta b \mapsto b'\) 使得下列式子成立:
\[ \begin{align} \begin{cases} y_i = +1, w^Tx_i +b \geq1\\ y_i = -1, w^Tx_i +b\leq1 \end{cases} \end{align} \]
其中,正负样本中各有几个样例使得(2)的等号成立,这些样例被称为 支持向量。
SVM的优化目标即是最大化间隔,而两个异类的支持向量到决策平面的距离是:
\[ \begin{align} \gamma = \frac{2}{||w||} \end{align} \]
同时,该优化目标函数具有约束,即式子(2),整理后写在一起:
\[ \notag \begin{array}{l} \max \limits_{w,b}\frac{2}{||w||}\\ s.t. y_i(w^Tx_i +b)\geq1, i=1,2,\cdots,n \end{array} \]
这等价于最小化 \(w\) 的范数:
\[ \begin{align} \begin{array}{l} \min \limits_{w,b}\frac{1}{2}||w||^2\\ s.t. y_i(w^Tx_i +b)\geq1, i=1,2,\cdots,m \end{array} \end{align} \]
式(4)就是SVM的基本型。
2. 对偶问题
式子(4)是一个不等式优化问题,有 \(m\) 个约束条件和 1 个 优化目标,对于这类问题,可以用拉格朗日乘数法来解决。
引入乘数因子 $\alpha $ :
\[ \begin{align} L(w,b,\alpha) = \frac{1}{2}||w||^2+\sum_i^m\alpha_i (1-y_i(w^Tx_i +b)) \end{align} \]
我们令:
\[ \begin{align} \theta(w)=\max \limits_{\alpha_i\geq0}L(w,b,\alpha) \end{align} \]
结合(5)(6)来说,如果 \(y_i(w^Tx_i+b)\geq1\) 和\(\alpha_i\geq0\) 有任何一个不满足,则 \(\theta(w)=+\infty\) ,所以当约束条件满足时,则有 \(\theta(w)=\frac{1}{2}||w||^2\), 即我们要最小化的目标。因此我们最初的目标函数变成了:
\[ \begin{align} \min \limits_{w,b}\frac{1}{2}||w||^2=\min \limits_{w,b}\theta(w)=\min \limits_{w,b}\max \limits_{\alpha_i\geq0}L(w,b,\alpha)=p^* \end{align} \]
这就是由拉格朗日乘数法引出的原问题。我们假定它的最优值时 \(p^*\)。
现在我们把$\min $ 和 \(\max\) 倒置一下,得到它的 对偶问题:
\[ \begin{align} \max \limits_{\alpha_i\geq0} \min \limits_{w,b}L(w,b,\alpha)=d^* \end{align} \]
同样我们假定它的最优值时 \(d^*\)。对比一下原问题和对偶问题:
- 原问题:一个函数最大值中最小的一个值 \(p^*\)
- 对偶问题: 一个函数最小值中最大的一个 \(d^*\)
显然有 \(d^*\leq p^*\)。即原问题的对偶问题确定了原问题的下界。当然,在满足Slater条件和KKT条件的情况下 \(d^*=q^*\),我们称之强对偶性。看一下Slater条件的定义:
Slater条件:如果主问题是凸优化问题,即不等式约束为凸函数,等式约束为仿射函数(线性变换),且可行域中至少有一点使得不等式约束严格成立,则强对偶性成立。
Slater条件保证鞍点的存在。而KKT条件保证函数可微。这样鞍点就可通过拉格朗日函数求导得到。
再讲KKT条件前,看一下对偶问题的求解:
对于内层最小化,求 \(L\) 关于 \(w, b\) 的偏导为0,解得的结果如下:
\[ \begin{align} w &= \sum \alpha_i y_i x_i\\ 0 &=\sum \alpha_i y_i \end{align} \]
带回式子(5),消去 \(w,b\),得到最终的优化函数为:
\[ \begin{align} \notag \max \limits_{\alpha}\sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}a_ia_jy_iy_jx_i^Tx_j\\ s.t. 0 =\sum \alpha_i y_i ,\\ \notag \alpha \geq 0 \end{align} \]
3. KKT条件
KKT是在满足一些有规则的条件下,一个非线性规则问题能有最优解的一个充分必要条件。也就是说,只要约束条件按照这个KKT给出的规则列出,然后符合KKT条件的,就可以有最优解。这是一个广义化拉格朗日乘数的成果。
对于不等式约束,需要满足KKT条件,这里讲一下KKT条件是怎么来的。
上图展示了一个2不等式约束优化问题,简单起见,这里在2维空间内讨论。
- 右下角方是优化目标函数\(f(x)\)的等高线。
- 左上方灰色部分是两个约束 \(g_1(x), g_2(x)\) 组成可行解区域。
假定在约束条件下,最优解为 \(x^*\) 。显然该点是2个约束条件以及某条等高线相交点。在该点处有3个梯度,分别用三个箭头表示:
- 红色箭头代表等高线梯度,它的方向代表优化目标函数值增大的方向,即 \(\nabla f(x^*)\)
- 绿色箭头代表约束在边缘处的负梯度,代表约束曲线值缩小的方向。
红色箭头必然加载俩绿色箭头中间(如果红色箭头不满足这个条件,那么必然存在更小的等高线穿过可行解区域),即 \(\nabla f(x^*)\) 必然可以由 \(-\nabla g_1(x^*)\) 和 \(-\nabla g_x(x^*)\) 线性表示,且系数一定为正。
于是引出了第一二个KKT条件:
\[ \begin{align} \nabla f(x^*)+\mu_1\nabla g_1(x^*)+\mu_2\nabla g_2(x^*)=0\\ \mu_1\geq0,\mu_2\geq0 \end{align} \]
然而,不一定所有的约束条件都对最优解起作用,比如下图的三约束优化问题:
显然 \(g_3(x)\) 对最优解不起作用。此时,最优解在 \(g_1(x)\) 和 \(g_2(x)\) 上,而不在 \(g_3(x)\) 上。此时,对于前两个KKT条件,有:
\[ \begin{align} \mu_1\geq0,\mu_2\geq0,\mu_3\geq0\\ \nabla f(x^*)+\mu_1 \nabla g_1(x^*)+\mu_2\nabla g_2(x^*)+\mu_3\nabla g_3(x^*)=0 \end{align} \]
对于(13)来说,我们不想让 \(g_3(x)\) 起作用,可以加入一个条件,使得 \(\mu_3=0\) 即可。于是引入第三个KKT条件:
\[ \begin{align} \mu_1g_1(x^*)+\mu_2g_2(x^*)+\mu_3g_3(x^*)=0 \end{align} \]
由于 \(g_1(x^*)=g_2(x^*)=0\), 那么自然的 \(\mu_3=0\),其实条件(16)等价于\(\mu_kg_k(x^*)=0\)
推广到多维等式\(h_j(x)\)和不等式约束\(g_k(x)\):
\[ \begin{align} \nabla f(x^*)+\sum_{j=1}^{m}\lambda_j\nabla h_j(x^*)+\sum_{k=1}^{m}\,u_k\nabla g_k(x^*)=0\\ h_j(x^*)=0, g_k(x^*)\leq0\\ \lambda_j\neq0, \mu_k\geq0, \mu_kg_k(x^*)=0 \end{align} \]
式子(17)(18)(19)合称KKT条件。
回顾我们的SVM优化问题, 注意,在SVM基本型中,参数空间是由\((w,b)\)构成的,而\((x,y)\)对都是已知的。
添加上SVM基本型,即公式(4)的条件:
\[ \begin{align} \max \limits_{\alpha}\sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}a_ia_jy_iy_jx_i^Tx_j\\ s.t. 0 =\sum \alpha_i y_i ,\\ \alpha \geq 0\\ y_if(x_i)-1\geq0 \end{align} \]
式子(18)是由 \(L(w,b,\alpha)\) 对\(w,b\)偏导为0求出,即满足了KKT条件(2),最终整理得,优化目标为:
\[ \begin{align} \max \limits_{\alpha}\sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}a_ia_jy_iy_jx_i^Tx_j\\ s.t. \sum \alpha_i y_i=0 ,\\ \alpha \geq 0\\ \end{align} \]
然后KKT要求这一过程满足:
\[ \begin{align} \begin{cases} \alpha_i\geq0\\ y_if(x_i)-1\geq0\\ \alpha_i(y_if(x_i)-1)=0 \end{cases} \end{align} \]
注意公式(27)的第三个式子 ,对于任意的训练样本\((x_i,y_i)\) 总满足\(\alpha_i=0\) 或 \(y_if(x_i)=1\), 若 \(\alpha_i=0\), 那么它就不会在优化目标(24)中出现,若\(y_if(x_i)=1\),那么它就是一个支持向量。这就引出了SVM的重要性质:训练完成后,大部分训练样本都不需要保留,最终模型只跟支持向量有关。
4. 解的形式
使用二次规划或者SMO算法解出 \(\alpha\) 后,SVM的解的由以下形式给出
\[ \begin{align} w = \sum \alpha_i y_i x_i \end{align} \]
而注意到 对于任意的支持向量\((x_s, y_s)\),都有 \(y_sf(x_s)=1\),即:
\[ y_s\left( \sum_{i\in S}\alpha_iy_ix_i^Tx_s+b\right)=1 \]
其中 \(S\) 是所有支持向量的下标集合。理论上可以选择任意的支持向量通过求解(29)得到,但现实任务一般采用更鲁棒的形式,即使用所有支持向量求均值:
\[ \begin{align} b=\frac{1}{|S|}\sum_{s\in S}\left(y_s-\sum_{i\in S}\alpha_iy_ix_i^Tx_s\right) \end{align} \]
5. 参考资料
1. 如何通俗地讲解对偶问题?尤其是拉格朗日对偶lagrangian duality? - 彭一洋的回答 - 知
2. 理解支持向量机三层境界