支持向量机（4）支持向量回归 & 多分类

SVM 是一个非常优雅的算法，具有完善的数学理论，虽然如今工业界用到的不多，但还是决定花点时间去写篇文章整理一下。

本质：SVM 想要的就是找到各类样本点到超平面的距离最远，也就是找到最大间隔超平面。为了对数据中的噪声有一定的容忍能力。以几何的角度，在丰富的数据理论的基础上，简化了通常的分类和回归问题。

几何意义：找到一个超平面将特征空间的正负样本分开，最大分隔（对噪音有一定的容忍能力）；

间隔表示：划分超平面到属于不同标记的最近样本的距离之和；

一、支持向量回归 SVR

https://blog.csdn.net/ch18328071580/article/details/94168411

支持向量在隔代之外

1.1 SVR与一般线性回归的区别

SVR	线性回归
数据在间隔带内则不计算损失，当且仅当f(x)与y之间的差距的绝对值大于ϵ才计算损失	只要f(x)与y不相等时，就计算损失
通过最大化间隔带的宽度与最小化总损失来优化模型	通过梯度下降之后求均值来优化模型

岭回归：

支持向量回归：我们假设f(x)与y之间最多有一定的偏差，大于偏差才计数损失

$$\begin{array}{}\text{(1)}& \underset{w,b}{min}\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^m{l}_{ϵ}(f\left(x_i\right),y_i)\end{array}$$ 其中C为正则化常数, $l_{ϵ}$ 是图中所示的 $ϵ$-不敏感损失 ( $ϵ$-insensitive loss)函数: $$\begin{array}{}\text{(2)}& l_{ϵ}(\mathrm{z})=\{\begin{array}{ll}0,& \text{ if }|z|\le ϵ\\ |z|-ϵ,& \text{ otherwise }\end{array}\end{array}$$ 引入松弛变量 ${\xi }_i$ 和 $\left({\xi }_i\right)$, 可将式重写为: $$\begin{array}{}\text{(3)}& \begin{array}{ll}\underset{w,b,{\xi }_i,{\xi }_i}{min}& \frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^m({\xi }_i,{\hat{\xi }}_i)\\ \text{ s.t. }& f\left(x_i\right)-y_i\le ϵ+{\xi }_i\\ & y_i-f\left(x_i\right)\le ϵ+{\hat{\xi }}_i\\ & {\xi }_i\ge 0,{\hat{\xi }}_i\ge 0,i=1,2,\dots m\end{array}\end{array}$$ 引入拉格朗日乘子 ${\mu }_i$,

$L(w,b,\alpha ,\hat{\alpha },\xi ,\hat{\xi },\mu ,\hat{\mu })$ $=\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^m({\xi }_i+{\hat{\xi }}_i)-\sum _{i=1}^m{\xi }_i{\mu }_i-\sum _{i=1}^m{\hat{\xi }}_i\widehat{{\mu }_i}$ $+\sum _{i=1}^m{\alpha }_i(f\left(x_i\right)-y_i-ϵ-{\xi }_i)+\sum _{i=1}^m\widehat{{\alpha }_i}(y_i-f\left(x_i\right)-ϵ-{\hat{\xi }}_i)$

再令 $L(w,b,a,\hat{a},\xi ,\hat{\xi },\mu ,\mu )$ 对 $w,b,{\xi }_i,{\hat{\xi }}_i$ 的偏导为零可得: $$\begin{array}{}\text{(4)}& w=\sum _{i=1}^m(\widehat{{\alpha }_i}-{\alpha }_i)x_i\end{array}$$ 上述过程中需满足KKT条件, 即要求: $$\begin{array}{}\text{(5)}& \{\begin{array}{c}{\alpha }_i(f\left(x_i\right)-y_i-ϵ-{\xi }_i)=0\\ \widehat{{\alpha }_i}(y_i-f\left(x_i\right)-ϵ-{\hat{\xi }}_i)=0\\ {\alpha }_i\widehat{{\alpha }_i}=0,{\xi }_i{\hat{\xi }}_i=0\\ (C-{\alpha }_i){\xi }_i=0,(C-\widehat{{\alpha }_i}){\hat{\xi }}_i=0.\end{array}\end{array}$$

二、多分类 SVM

2.1 多分类问题

• 多分类问题拆解成若干个二分类问题，对于每个二分类训练一个分类器。
  • one vs one 拆解：K(K-1)/2 个分类器。
  • one vs Rest 拆解：K个分类器

2.2 多分类线性SVM

• 层次支持向量机

• 回顾二分类

$$\begin{array}{}\text{(6)}& \begin{array}{rl}& \underset{\mathit{w},b}{min}\frac{1}{m}\sum _{i=1}^{m}max(1-y_i({\mathit{w}}^{\mathrm{\top }}{\mathit{x}}_i+b,0)+\frac{\lambda }{2}\Vert \mathit{w}{\Vert }^2\\ =& \underset{\mathit{w},b}{min}\frac{1}{m}\sum _{i=1}^{m}max(1-y_{i}s\left({\mathit{x}}_i\right),0)+\frac{\lambda }{2}\Vert \mathit{w}{\Vert }^2.\end{array}\end{array}$$

• 多分类线性SVM

$$\begin{array}{}\text{(7)}& \underset{\mathit{W},\mathit{b}}{min}\frac{1}{m}\sum _{i=1}^m\sum _{k=1}^K\mathbb{I}(k\ne y_i)\cdot max(1-s{\left({\mathit{x}}_i\right)}_{y_i}+s{\left({\mathit{x}}_i\right)}_k,0)+\frac{\lambda }{2}\sum _{k=1}^K{\Vert {\mathit{w}}_k\Vert }^2,\end{array}$$