SVM简介

支持向量机（Support Vector Machine，SVM）是一种常用的监督学习算法，用于分类。它的主要思想是找到一个最优的超平面，将不同类别的样本分开，并在最大化分类间隔的同时最小化分类误差。

当然支持向量机也可以用于回归任务，叫做支持向量回归（Support Vector Regression，SVR），支持向量回归通过数据转换、损失函数、边际和间隔等步骤，找到一个回归函数来预测连续的输出变量。

使用情景

支持向量机（Support Vector Machine，SVM）是一种非常强大和灵活的机器学习算法，适用于多种情景。

1. 二分类问题：SVM在二分类问题中表现出色。它可以有效地将具有不同特征的两个类别分开，并且对于小样本和高维数据也能够提供良好的性能。例如，文本分类、图像分类和生物医学领域中的肿瘤分类等。
2. 多分类问题：尽管SVM最初是为二分类设计的，但它可以通过一些技术扩展到多类别分类问题。常见的方法是使用一对多（One-vs-Rest）或一对一（One-vs-One）的策略来训练多个二分类器。多类别问题包括手写数字识别、图像分类和人脸识别等。
3. 高维数据集：SVM对于高维数据集的处理效果很好。由于其基于间隔最大化的原理，SVM可以在高维空间中找到适当的超平面来分隔不同类别的样本。这使得SVM在自然语言处理、生物信息学和基因表达数据分析等领域中得到广泛应用。
4. 非线性问题：通过使用核函数，SVM可以处理非线性问题。核函数可以将输入空间映射到更高维的特征空间，使得原本线性不可分的问题变得可分。常见的核函数包括线性核、多项式核和高斯核等。

总而言之，支持向量机支持多分类，非线性分类和高维数据集，我们使用一个例子来详细解释一下。

我们有红蓝两种小球，使用一刀把它们分开：

你觉得丝毫没有问题：

SVM的原理就是尝试把这个线放到最合适的位置，使得距离红球和蓝球有最大的距离。你的线或许应该是这样的。

你以为SVM就是做这件事吗，下面的这个图，阁下怎么用用一条直线分类呢？

我一生气，啪的一下，我一拳把小球打飞了，小球在空中形成了一个特殊的空间，我手疾眼快，在空中切分一个平面，刚好将两种球分开。

然后回到平面，形成了这样的一个曲线，

这就是我们的SVM要完成的任务了。我们看到了两个问题，首先我们在二维线性任务中，怎么找一个最大间隔的位置；在非线性任务中，怎么让我的数据“飞起”，在高维空间将数据分开。

线性SVM

分类决策函数

我们先来考虑一个线性二分类问题，输入为二维空间的数据集，输出为样本标签，即为“-1和1”。给出该空间下面的数据集，

$$T=\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\dots \dots ,(x_n,y_n)\}$$

其中，x_i是二维空间的样本，y_i是分类标签，有-1和1两个属性。如下图所示:

我们先不管怎么把标签变成-1和1，首当其冲的我们要找一个直线分开两种球，在二维空间中，直线的普通方程可以表示为：

$$wx+b=0$$

那么在直线的上方的值就是正的，直线下方的值就是负的，所以可以取分类决策函数sign()来判断。

蓝球的值都是大于0的，红球的值都是小于0的，那么sign()函数是什么呢，也被称为符号函数，正值为1，负值为-1，如下图所示：

所以分类决策函数可以写成：

$$f(x)=sign(wx+b)$$

函数间隔

如上图所示，它并不一定是二维平面，可能是超平面，三维的或者多维的。有A、B、C三个点，其中C点距离分类平面最近，表示预测该店为正类不那么确信，A点距离分类平面最远，表示预测该点为正类最正确。一个点距离超平面的远近可以表示分类预测的确信程度，其中对于超平面确定的情况下，怎么表示距离呢？如下所示：

$$直线为wx+b=0，点P(x_0,y_0)到直线的距离：d=\frac{|w{x}_0+b|}{|w|}$$

我们这个距离越大表示我们的点到目标平面的距离越大，我们的分类间隔就是等于两倍的点到直线的距离，所以我们求解最大分类间隔就转换为了d的最大化的求解。我们的目标就是最大化上面得到的距离d。

约束条件

我么知道有这样的说法：

$$\{\begin{array}{ccc}w{x}_i+b>0& y_i>0& 圆圈\\ w{x}_i+b<0& y_i<0& 叉叉\end{array}$$

我们假设向量到达样本的最近距离为d，可以进一步转换为下面的公式：

$$\{\begin{array}{cc}\frac{w{x}_i+b}{|w|}>=d& y_i=1\\ \frac{w{x}_i+b}{|w|}<=-d& y_i=-1\end{array}$$

将等式两侧同时除以d，得到下面的公式：

$$\{\begin{array}{cc}{w}_d{x}_i+d_d>=1& y_i=1\\ w_d{x}_i+d_d<=-1& y_i=-1\end{array}其中w_d=\frac{w}{|w|d}，d_d=\frac{d}{|w|d}$$

所以我们来看上面的两个公式，就是表示的是同一个直线

$$\{\begin{array}{c}w{x}_i+d=0\\ w_d{x}_i+d_d=0\end{array}$$

进一步我们加上标签y，如果分类正确wx_i+b和y_i的正负性一致，所以就是一个公式：

$$y_i(x_d{x}_i+d_d)>=1$$

这个就是我们的约束条件。

问题描述

下面考虑如何求得集合分割最大的分离超平面。

我们最大化d，而且有

$$y_i(\frac{w}{|w|x_i}+\frac{b}{|w|})>=d$$

我们希望最大化超平面(w,b)的几何间隔d，约束条件是上面的公式。我们可以将这个问题改写为

$$ma{x}_{(w,b)}\frac{d^{\prime }}{|w|}最大化几何间隔$$

那么它的约束函数是什么呢？

$$y_i(w{x}_i+b)>=d^{\prime }$$

我们可以取函数间隔为d’=1，就转换为了下面的约束条件：

$$ma{x}_{w,b}\frac{1}{|w|}且y_i(w{x}_i+b)>=1$$

也转换为了最小化1/2|w|^2^。因为这个函数是凸函数，所以这个问题是凸二次规划问题。

这个地方比较绕,总的来说就是放缩变换：

$$对于决策方程（w,b）可以通过放缩使得结果值|Y|>=1，y_i(w{x}_i+b)>=1$$

要求最优化目标是：

$$ar{g}_{w,b}max\{\frac{1}{|w|}min[y(w{x}_i+b)]\}$$

总的来说，最内部的min找到距离决策线最小的点，我们可以通过缩放让y(wx~i~+b)>=1，然后只需要考虑1/|w|

凸函数

什么是凸函数，凸函数表示的是函数任意两点连线的值大于对应自变量处的函数值。对于凸函数来说可以获取全局最优解，而对于非凸函数来说，只能获得局部最优解。通常我们求解最优化问题有下面几类：

• 无约束优化问题：

$$minf(x)$$

• 有等式约束问题优化：

$$minf(x)且h(x)=0$$

• 有不等式约束的问题优化

$$minf(x)且h(x)>0$$

对于无约束问题，通常使用求导数，然后令导数等于0，可以求得最优质，然后带入验证。

对于有等式约束的问题优化，常使用拉格朗日乘子法，把等式约束h(x)和目标函数f(x)写成一个式子，然后通过拉格朗日函数对各个变量求导，令其为零，得到候选值集合，验证求得最优值。

对于不等式约束的问题优化，需要满足KKT条件，然后使用拉格朗日方程继续计算w和b，KKT条件描述如下：

1. 约束条件满足：所有的约束条件都被满足。
2. 梯度条件满足：拉格朗日函数对变量的梯度为零。
3. 互补松弛条件满足：每个约束条件的松弛变量（拉格朗日乘子）与约束条件的乘积为零。
4. 非负性条件满足：松弛变量和变量的取值都必须非负。

拉格朗日函数

拉格朗日模板：有带约束的问题如下。

$$minf(x)subjectto{f}_i(x)<=0,i=1\dots \dots m{h}_j(x)=0,j=1\dots \dots q$$

可以转换为：

$$minL(x,\lambda ,v)=f(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{j=1}^q{v}_i{h}_i(x)$$

所以我们上面的式子可以写为：

$$mi{n}_{w,b}{L}_{\alpha }(w,b,\alpha )=\frac{1}{2}|w{|}^2-\sum _{i=1}^n{\alpha }_i(y_i(w_i{x}_i+b)-1)$$

要求w和b在约束条件下的关系，但是在约束条件下不太好求，我们转换为求w和alpha以及求b和alpha的关系，把alpha求出来，然后根据w和alpha以及b的关系，求出w和b的关系。下面我们分别对w和b求偏导，令偏导为0得到极值。

$$\frac{\mathrm{\partial }L}{\mathrm{\partial }w}=0⟹w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i,\frac{\mathrm{\partial }L}{\mathrm{\partial }b}=0⟹\sum _{i=1}^n{\alpha }_i{y}_i=0$$

我们将得到的关系式带入到原式子中：

$$L(w,b,\alpha )=\frac{1}{2}|w{|}^2-\sum _{i=1}^n{\alpha }_i(y_i(w_i{x}_i+b)-1)$$

得到结果：

$$argma{x}_{\alpha }(\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i{x}_j)条件：\sum _{i=1}^n{\alpha }_i{y}_i=0且{\alpha }_i>=0$$

得到这样的式子，我很为难，下面就是把数据，数据集的点带进去。下面我们要求w和b，就要先求出来$alpha$，这个$alpha$不一定是一个值，如果你取距离决策边界最近的两个点，那么一定是$alpha$~1~和$alpha$~2~，并且距离远离决策边界的点的$alpha$一定为0。还有这两个点就叫做支持向量，所以这个算法名称叫做支持向量机。但是机器学习中的是怎么计算w和b的呢？那就是使用SMO算法。

这张图可以清晰看到支持向量就是边界点，起到支撑作用。

SMO算法

这个有点难，暂时不看了，以下是SMO算法的基本步骤：

1. 初始化：选择合适的参数，如正则化参数C、容错率等，并初始化拉格朗日乘子α和偏差b。
2. 选择两个变量：在每次迭代中，选择两个变量作为优化的目标。SMO算法采用一种启发式的方法来选择这两个变量，以便能够在每次迭代中最大限度地改善优化问题的解。
3. 优化子问题：固定其他变量，通过求解一个二次规划子问题来最大化或最小化目标函数。这个子问题的目标是在约束条件下更新两个变量的值。
4. 更新参数：根据求解得到的两个变量的值，更新拉格朗日乘子α和偏差b。
5. 终止条件：通过一些终止条件判断是否满足停止迭代的条件，例如达到最大迭代次数或收敛判据。
6. 重复步骤2-5：如果终止条件不满足，继续选择下一对变量进行优化，重复执行步骤2-5，直到满足终止条件为止。

软间隔

有时候数据中有一些噪音点，如果考虑它们的话线就不好了，之前的方法有一个要求，那就是下面的式子：
$$y_i(w{x}_i+b)>=0$$
就是所有的点都要求分类正确，但是考虑这样一个问题

我们的线已经扭曲了，所以我们应该适当放松一点，为了解决这个问题，我们引入松弛因子
$$y_i(w{x}_i+b)>=1-{\sigma }_i$$
其中$sigma$大于0，告诉模型不大于1的你也糊弄过去，别那么认真嘛。

所以我们可以修改目标函数为：
$$min(\frac{1}{2}|w{|}^2+C\sum _{i=1}^n{\sigma }_i)$$
当C很大的时候：意味着$sigma$小，说明，分类更加严格；当C很小的时候，一位这$sigma$很大，意味着有更大的错误容忍。

核函数

先做内积然后然后带入到高维，比先带入到高维再做内积计算复杂度更低。那么这个f(x)是随便写的吗？找一个低维空间先内积映射到高维空间中等于高维空间再内积的函数，没有几个。

最常用的函数是高斯核函数，就用这个就行了，我们不用想科学家都想不到的东西哦。

可以看到线性核函数不能分开，而高斯核函数可以分开，支持向量机和神经网络的相似在于它是一个非线性的决策边界，神经网络也能得到右侧的效果。高斯核函数可以将特征映射到无限维，数据维度越大，边界更清晰，相当于拟合更好。

优缺点

1. 有效处理高维空间：SVM可以将低维的非线性问题映射到高维空间，从而使其在高维空间中线性可分。
2. 能够处理非线性问题：通过使用核函数，SVM可以处理非线性分类问题，允许在非线性特征空间中进行分类。
3. 具有较好的泛化能力：SVM通过最大化分类间隔来选择决策边界，从而降低了过拟合的风险，具有较好的泛化能力。

缺点：

1. 对大规模数据集需要较长的训练时间：在大规模数据集上，SVM的训练时间较长，特别是当使用复杂的核函数时。
2. 对于多类分类问题需要额外扩展：原始的SVM算法是二分类算法，对于多类分类问题需要进行额外的扩展，如使用一对多（One-vs-Rest）或一对一（One-vs-One）策略。

参考链接

1.使用情景的例子来自：Support Vector Machines explained well | Byte Size Biology

2.拉格朗日求解方法：拉格朗日方程 – 知乎 (zhihu.com)

3.核函数：沽泡AI