【机器学习】支持向量机 | 支持向量机理论全梳理 对偶问题转换，核方法，软间隔与过拟合

支持向量机走的路和之前介绍的模型不同

之前介绍的模型更趋向于进行函数的拟合，而支持向量机属于直接分割得到我们最后要求的内容

1 支持向量机SVM基本原理

当我们要用一条线（或平面、超平面）将不同类别的点分开时，我们希望这条线尽可能地远离最靠近它的点。这些最靠近线的点被称为支持向量。而这条线到最靠近它的点的距离被称为间隔。支持向量机就是要找到一个最大间隔的线（或平面、超平面），这样可以更好地区分不同类别的点。

以下是支持向量机的一些关键概念和特性：

1. 超平面：在二维空间中，超平面是一条直线；在三维空间中，它是一个平面；在更高维的空间中，超平面是一个超平面。对于一个二分类问题，超平面将特征空间划分为两个部分，每个部分对应一个类别。
2. 支持向量：支持向量是离超平面最近的那些点。在SVM中，这些点对定义超平面起着重要作用，因为它们决定了超平面的位置。
3. 间隔：支持向量到超平面的距离称为间隔。SVM的目标是找到具有最大间隔的超平面，这样可以更好地对新样本进行分类。

2 支持向量分类

2.1 支持向量机求解——对偶问题转换

在机器学习中，对偶问题是指将原始优化问题转化为另一个形式的问题。对于支持向量机（SVM）来说，对偶问题是通过对原始问题的拉格朗日函数进行求解得到的。

具体来说，原始的SVM优化问题是要最小化带有正则化项的损失函数。这个损失函数包括两部分：一部分是要使得分类间隔最大化，另一部分是要保证分类的准确性。直接求解这个问题可能比较复杂。为了简化求解过程，可以将原始问题转化为对偶问题。通过引入拉格朗日乘子，我们可以得到对偶问题。在对偶问题中，我们需要最大化一个关于拉格朗日乘子的函数，同时满足一些约束条件。

通过求解对偶问题，我们可以得到支持向量的拉格朗日乘子的最优解，然后可以使用这些乘子来计算权重向量和偏置，从而得到最终的分类超平面。

对偶问题满足KKT条件，KKT条件如下

KKT（Karush-Kuhn-Tucker）条件是最优化问题中的一组条件，用于描述在某些条件下最优解的性质。对于支持向量机（SVM）的对偶问题，KKT条件可以描述如下：

1. 对偶互补条件：对于所有的$i$，有${\alpha }_i[y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1+{\xi }_i]=0$，即对所有的支持向量，乘子${\alpha }_i$不为零的条件下，$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1+{\xi }_i=0$，这表示支持向量的函数间隔与几何间隔之差等于1。

2. 互补松弛条件：对于所有的$i$，有${\beta }_i{\xi }_i=0$，即对所有的支持向量，松弛变量${\xi }_i$不为零的条件下，${\beta }_i=0$，表示松弛变量与${\beta }_i$之间的关系。

3. KKT条件：对于所有的$i$，有${\alpha }_i\ge 0$，$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1+{\xi }_i\ge 0$，${\beta }_i\ge 0$，${\alpha }_i[y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1+{\xi }_i]=0$，${\beta }_i{\xi }_i=0$。

KKT条件告诉我们，在最优解处，拉格朗日乘子和变量的取值必须满足这些条件。

基于KKT条件，更好求SVM的最优解

2.2 非线性问题——核方法

核方法是一种机器学习中常用的技术，特别是在支持向量机（SVM）等算法中经常使用。它的基本思想是通过一个非线性映射将原始的输入特征空间映射到一个更高维的特征空间，使得原本在低维空间中不可分的样本变得可分。这个非线性映射称为核函数，它可以避免在高维空间中进行实际的特征转换，从而节省计算成本。

在SVM中，核方法的主要作用是将样本从原始特征空间映射到一个更高维的空间，在这个高维空间中找到一个线性超平面来分割不同类别的样本。常用的核函数包括线性核、多项式核、高斯核（也称为径向基函数核）等，它们可以根据数据的特点选择合适的核函数来提高分类的准确性。

核方法的优势在于能够处理非线性可分的数据，同时避免了在高维空间中进行实际的特征转换，从而降低了计算复杂度。因此，核方法在机器学习中被广泛应用于分类、回归和聚类等任务中。

映射的时候，我们需要核函数进行映射

核函数是支持向量机（SVM）中的重要概念，它允许在高维空间中进行非线性分类。在SVM中，我们希望找到一个最优超平面来将不同类别的数据点分开。如果数据在原始特征空间中不是线性可分的，那么就需要使用核函数将数据映射到一个高维特征空间，使得数据在该空间中线性可分。

核函数的主要思想是，我们可以通过一个函数来计算两个向量在高维空间中的内积，而不必显式地计算它们在高维空间中的表示。这样做的好处是，可以避免在高维空间中显式地存储和计算数据，而是利用核函数的性质，只需计算原始特征空间中的内积，就可以得到在高维空间中的内积。这种技术称为“核技巧”。

常用的核函数包括：

1. 线性核函数：$K({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathbf{x}}_i^T{\mathbf{x}}_j$，直接计算两个向量在原始特征空间中的内积。
2. 多项式核函数：$K({\mathbf{x}}_i,{\mathbf{x}}_j)=(\gamma {\mathbf{x}}_i^T{\mathbf{x}}_j+r{)}^d$，将数据映射到多项式特征空间。
3. 高斯核函数（径向基函数核）：$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma \Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2)$，将数据映射到无穷维的特征空间，适用于非线性可分的情况。

通过使用核函数，SVM可以在高维空间中进行复杂的非线性分类，而不必显式地计算和存储高维数据。核函数的选择通常基于对数据特征的理解和试验结果。

2.3 防止过拟合——软间隔与正则化

软间隔是支持向量机（SVM）中的概念，用于处理线性不可分的情况。在标准的线性可分SVM中，我们希望找到一个最优超平面，将不同类别的数据点完全分开。然而，在现实应用中，数据往往不是完全线性可分的，即存在一些噪音或异常点。为了处理这种情况，引入了软间隔的概念。

软间隔允许一些数据点位于超平面的错误一侧，但是通过引入一个惩罚项，希望这些错误被最小化。具体来说，软间隔SVM的优化问题包括两部分：最小化误分类点的数量（间隔违例）和最大化间隔。

软间隔SVM的优化问题可以形式化如下：
$mi{n}_{\mathbf{w},b,\xi }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C{\sum }_{i=1}^m{\xi }_i$

$\text{subject to }{y}_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0,\forall i$

其中，$\mathbf{w}$是超平面的法向量，$b$是偏置项，${\xi }_i$是松弛变量，$C$是正则化参数，用于控制间隔违例的惩罚力度。优化问题的目标是要找到一个最优的超平面，以及对应的${\xi }_i$，使得误分类的点尽量少，同时间隔尽量大。

软间隔SVM通过调节正则化参数$C$可以在偏向于过拟合（$C$较小）和偏向于欠拟合（$C$较大）之间进行平衡，从而在实际应用中取得更好的性能。

2 支持向量回归

支持向量回归（Support Vector Regression，SVR）是支持向量机（SVM）的一种应用，用于解决回归问题。与传统的线性回归方法不同，SVR可以处理非线性关系，并且对异常值具有较强的鲁棒性。

SVR的基本思想与支持向量分类（SVC）类似，都是通过寻找一个最优的超平面（或者称为回归器）来拟合数据。与SVC不同的是，SVR的目标是最小化预测误差，而不是最大化间隔。

SVR的优化问题可以形式化如下：

${\min }_{\mathbf{w},b,\xi ,{\xi }^{\ast }}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C{\sum }_{i=1}^m({\xi }_i+{\xi }_i^{\ast })$

$\text{subject to }\{\begin{array}{l}{y}_i-{\mathbf{w}}^T\varphi ({\mathbf{x}}_i)-b\le \epsilon +{\xi }_i^{\ast }\\ {\mathbf{w}}^T\varphi ({\mathbf{x}}_i)+b-y_i\le \epsilon +{\xi }_i\\ {\xi }_i,{\xi }_i^{\ast }\ge 0\end{array}$

其中，$\mathbf{w}$是回归器的权重向量，$b$是偏置项，${\xi }_i$和${\xi }_i^{\ast }$是松弛变量，$\epsilon$是一个预先指定的参数，称为容忍度，$C$是正则化参数。

SVR的核心思想是通过最小化间隔违例（${\xi }_i$和${\xi }_i^{\ast }$）的同时，尽可能保持间隔边缘，从而找到一个最优的超平面来拟合数据。支持向量是那些落在间隔边缘上的数据点，它们对于定义超平面和拟合模型起着关键作用。

总的来说，SVR通过引入间隔违例和正则化参数，可以在保持模型简单性的同时，有效地拟合非线性关系，并且对异常值具有较好的鲁棒性。