526互联

支持向量机 Support Vector Machine

发布时间 2023-12-06 19:37:01作者: 听风者628

b站链接【白板推导系列-支持向量机】

SVM 有三宝：间隔、对偶、核技巧

SVM 分类：

  • hard-margin SVM 硬间隔
  • soft-margin SVM 软间隔
  • kernel SVM 核

硬间隔分类器（最大间隔分类器）max margin

判别模型：

\[f(w)=sign(w^Tx+b) \]

目标是：找到一条最中间的超平面使之离样本点足够远
设样本点 \(\{(x_i,y_i)\}_{i=1}^N\)，其中 \(x_i\in\mathbb{R}^p\)，\(y_i\in\{-1,1\}\)
则分类器需要实现

\[y_i(w^Tx_i+b)>0,\forall i=1,\cdots, N \]

margin（间隔）：\(N\) 个样本点到超平面有 \(N\) 的距离（\(dist_i\)），我们定义间隔为其中最小的一个dist，即距离超平面最近的样本点到超平面的距离

\[margin(w,b)=\min dist(w,b,x_i) \]

而根据点到直线距离公式，样本点 \(x_i\) 到超平面 \(w^Tx+b=0\) 的距离为$$ dist_i=\frac1{||w||}|w^Tx_i+b|$$
所以间隔又可以写为 $$margin(w,b)=\min\frac1{||w||}|w^Tx_i+b|$$

注意样本点 \(x_i\) 是一个向量，可以把它坐标记为 \(x_i=(x^i_1,x^i_2)\)（假设是在二维平面上），此时超平面 \(w^Tx+b=0=\) 是一条直线:\(w_1x_1+w_2x_2+b=0\)。
我们熟悉的点 \((x_0,y_0)\) 到直线 \(Ax+By+C=0\) 距离公式是 \(d=\frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}}\)
二者对应一下就是上面的结果，其中 \(||w||=\sqrt{w_1^2+w_2^2}\) 表示2范数（模长）

于是“最大间隔分类器”的数学表示就是：

\[\left\{\begin{aligned} &\underset{w,b}{\max}\underset{x_i,i=1,\cdots,N}{\min}\frac1{||w||}|w^Tx_i+b|\\ &s.t.y_i(w^Tx_i+b)>0 \end{aligned}\right.\]

也可以写成

\[\left\{\begin{aligned} &\underset{w,b}{\max}\underset{x_i,i=1,\cdots,N}{\min}\frac1{||w||}y_i(w^Tx_i+b)\\ &s.t.y_i(w^Tx_i+b)>0 \end{aligned}\right.\]

因为 \(y_i\in\{-1,1\}\) 不会影响 \(w^Tx_i+b\) 的值并且保证 \(y_i(w^Tx_i+b)>0\)

观察上式 \(\min\) 是对 \(x_i\) 求最小值，而与 \(w\) 无关，所以可以吧 \(\frac1{||w||}\) 提出来：
进一步写成

\[\left\{\begin{aligned} &\underset{w,b}{\max}\frac1{||w||}\underset{x_i,i=1,\cdots,N}{\min}y_i(w^Tx_i+b)\\ &s.t.y_i(w^Tx_i+b)>0 \end{aligned}\right.\]

再观察 \(y_i(w^Tx_i+b)>0\)，因为对于任意的样本 \(x_i\) 都满足这个式子大于0，那么这个式子的最小值一定是大于0的，我们可以把它最小值记为 \(r\)，即 \(\underset{x_i,y_i,i=1,\cdots,N}{\min}y_i(w^Tx_i+b)=r\)，于是 \(y_i(w^Tx_i+b)>0\) 等价于 \(\exist r>0,s.t.\underset{x_i,y_i,i=1,\cdots,N}{\min}y_i(w^Tx_i+b)=r\)
于是上面的式子又可以进一步写成

\[\left\{\begin{aligned} &\underset{w,b}{\max}\frac1{||w||}\cdot r\\ &s.t.\underset{x_i,y_i,i=1,\cdots,N}{\min}y_i(w^Tx_i+b)=r \end{aligned}\right.\]

再来分析这里的 \(r\)：
\(r=\underset{x_i,y_i,i=1,\cdots,N}{\min}y_i(w^Tx_i+b)\)，因为 \(y_i\in\{-1,1\}\) 对于取值没有影响，所以 \(r\) 的取值大小只取决于 \(w^Tx_i+b\) 的最小值
我们知道 \(w^Tx+b=0\) 是分类器的超平面，并且可以发现当我们把这里的参数 \(w,b\) 按同等比例放缩后得到的超平面如 \((2w)^Tx+2b=0\) 或者 \((\frac12w)^Tx+\frac12b=0\) 和原来的超平面是一样的，但是计算最小值时 \(w^Tx_i+b\) 的值的时候就不一样了，于是我们可以找一组合适的参数 \(w_0,b_0\) 使这个最小值 \(w_0^Tx_i+b_0=1\)，也就是 \(r=1\)（整个过程都不考虑正负号的影响了，因为 \(y_i\) 会帮我们平衡正负号）
于是上面的式子最后就化简成了：

\[\left\{\begin{aligned} &\underset{w,b}{\max}\frac1{||w||}\\ &s.t.\underset{x_i,y_i,i=1,\cdots,N}{\min}y_i(w^Tx_i+b)=1 \end{aligned}\right.\]

最后再规范一下写法：

\[\left\{\begin{aligned} &\underset{w,b}{\min}\frac12w^Tw\\ &s.t.y_i(w^Tx_i+b)\geq1,i=1\cdots,N \end{aligned}\right.\]

\(\max\frac1{||w||}\Leftrightarrow\min||w||\)，而 \(||w||=w^Tw\)，前面乘一个系数是为了后面计算方便

上述的问题是一个凸优化问题（convex optimization）：目标函数为二次型，有 N 个约束

下面求解上面的问题
首先考虑拉格朗日乘子法，构造拉格朗日函数

\[L(w,b,\lambda)=\frac12w^Tw+\sum_{i=1}^N\lambda_i(1-y_i(w^Tx_i+b)) \]

于是上面的问题转化为

\[\left\{\begin{aligned} &\underset{w,b}{\min}\underset{\lambda}{\max}L(w,b,\lambda)\\ &s.t.\lambda_i\geq0 \end{aligned}\right.\]

解释一下为什么这两个问题等价（也就是说明 \(\underset{\lambda}{\max}L(w,b,\lambda)=\frac12w^Tw\)）：
首先我们记 \(\Delta=1-y_i(w^Tx_i+b)\)，对于每一个样本 \(x_i\) 和它的分类 \(y_i\)，假设我们选择的超平面参数 \(w,b\) 使 \(\Delta>0\)，由于 \(\lambda_i\geq0\)，所以 \(\underset{\lambda}{\max}L(w,b,\lambda))=\underset{\lambda}{\max}[\frac12w^Tw+\sum_{i=1}^N\lambda_i(1-y_i(w^Tx_i+b))]\) 是会随着 \(\lambda\) 的增大而不断增大，是取不到最大值的，或者是最大值是无穷；
但是如果我们选择的参数 \(w,b\) 使 \(\Delta<0\)，那么只有当 \(\lambda_i=0\) 时才能取得最大值并且最大值 \(\underset{\lambda}{\max}L(w,b,\lambda))=\frac12w^Tw\)

我们把

\[\left\{\begin{aligned} &\underset{w,b}{\min}\frac12w^Tw\\ &s.t.1-y_i(w^Tx_i+b)\leq0 \end{aligned}\right.\]

称为原问题
把

\[\left\{\begin{aligned} &\underset{w,b}{\min}\underset{\lambda}{\max}L(w,b,\lambda)\\ &s.t.\lambda_i\geq0 \end{aligned}\right.\]

称为无约束的原问题

对偶

弱对偶关系：\(\min\max L\geq\max\min L\)（宁为鸡头，不为凤尾）
强对偶关系：\(\min\max L=\max\min L\)
凸优化二次问题天然满足强对偶（证明略）

所以上述问题的对偶问题

\[\left\{\begin{aligned} &\underset{\lambda}{\max}\underset{w,b}{\min}L(w,b,\lambda)\\ &s.t.\lambda_i\geq0 \end{aligned}\right.\]

现在来求解（化简）这个对偶问题
对于 \(\underset{w,b}{\min}L(w,b,\lambda)\)，我们可以用拉格朗日乘数法求解，即令 \(\frac{\partial L}{\partial w}=\frac{\partial L}{\partial b}=0\)，然后把解得的 \(w^*\) 和 \(b^*\) 带入就是 \(\underset{w,b}{\min}L(w,b,\lambda)\)
下面是求解过程，先求 \(\frac{\partial L}{\partial b}\)（因为好求）

\[L(w,b,\lambda)=\frac12w^Tw+\sum_{i=1}^N\lambda_i(1-y_i(w^Tx_i+b))\\ =\frac12w^Tw+\sum_{i=1}^N\lambda_i-\sum_{i=1}^N\lambda_iy_iw^Tx_i-\sum_{i=1}^N\lambda_iy_ib\\ \frac{\partial L}{\partial b}=-\sum_{i=1}^N\lambda_iy_i \]

令其为 0，则 \(-\sum_{i=1}^N\lambda_iy_i=0\)
再求 \(\frac{\partial L}{\partial w}\)，先带入上面的结果

\[L(w,b,\lambda)=\frac12w^Tw+\sum_{i=1}^N\lambda_i-\sum_{i=1}^N\lambda_iy_iw^Tx_i-\sum_{i=1}^N\lambda_iy_ib\\ =\frac12w^Tw+\sum_{i=1}^N\lambda_i-\sum_{i=1}^N\lambda_iy_iw^Tx_i\\ \frac{\partial L}{\partial b}=w-\sum_{i=1}^N\lambda_iy_ix_i \]

令其为 0，解得 \(w^*=\sum_{i=1}^N\lambda_iy_ix_i\)
带入 \(L\) 的表达式就是它的最小值

\[\underset{w,b}{\min}L(w,b,\lambda)=\frac12w^Tw+\sum_{i=1}^N\lambda_i-\sum_{i=1}^N\lambda_iy_iw^Tx_i\\ =\frac12(\sum_{i=1}^N\lambda_iy_ix_i)^T(\sum_{j=1}^N\lambda_jy_jx_j)-\sum_{i=1}^N\lambda_iy_i(\sum_{j=1}^N\lambda_jy_jx_j)^Tx_i+\sum_{i=1}^N\lambda_i\\ =\frac12\sum_{i=1}^N\sum_{j=1}^N\lambda_iy_i\lambda_jy_jx_i^Tx_j-\sum_{i=1}^N\sum_{j=1}^N\lambda_iy_i\lambda_jy_jx_j^Tx_i+\sum_{i=1}^N\lambda_i\\ =-\frac12\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i \]

这里 \(x_i\) 和 \(x_j\) 都是列向量，所以 \(x_i^Tx_j\) 和 \(x_j^Tx_i\) 是一样的

把我们求得的 \(\underset{w,b}{\min}L(w,b,\lambda)\) 代回对偶问题中，于是对偶问题就变成了

\[\left\{\begin{aligned} &\underset{\lambda}{\max}-\frac12\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i\\ &s.t.\sum_{i=1}^N\lambda_iy_i=0，\lambda_i\geq0 \end{aligned}\right.\]