支持向量机

Idea

支持向量机(Support Vector Machine)是Vapnik等于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。

SVM是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广(泛化)能力。

对比感知机和SVM，感知机利用误分类样本最少的策略，求得分离超平面，不过这时的解有无穷多个； 线性可分支持向量机利用间隔最大化求最优分离超平面（解是唯一的）。

image-20250531095632446

基本概念

在二分类的样本集中，SVM希望找到一个超平面将不同样本分开，同时希望两边的数据离超平面有尽量大的间隔，以期获得高分类的容忍度；

超平面方程和上下的边界方程如下，对为法向量,为位移项；

假设能将训练样本正确分类，必有：

因此分类预测函数为

在上下边界上使得方程等号成立的点就是支持向量，即每类中距离决策面最近的样本点，上下边界之间的间隔(Margin)如下：

image-20250531095818822

可以看到

  • 在决定分离超平面时，只有支持向量起作用，而其他实例点并不起作用；
  • 移动支持向量将改变所求的解，即改变分离超平面；
  • 移动间隔边界以外的实例点，甚至去掉这些点，解是不会改变的；

Hard Margin SVM

对于线性可分的数据，我们寻求一个最大间隔分离超平面。这个问题可以表示为以下优化问题：

最大化间隔等价于如下最优化问题(primal form)：

这是一个有 个约束条件的凸二次规划问题，解存在且唯一。该形式求解算法的复杂度与样本维度有关；

我们通常将其转化为对偶问题(dual form)。引入拉格朗日乘子 ，构建拉格朗日函数：

根据对偶原理，原始问题的对偶问题可以通过先对拉格朗日函数关于原始变量 求偏导并令其等于零，然后对拉格朗日乘子 求最大化得到。

对 关于 和 求偏导：

将这些关系代回拉格朗日函数，消去 和 ，可以得到只关于 的对偶函数，并对其进行最大化，从而得到对偶问题，满足KKT约束条件，特别地，第三个条件被称为互补松弛性；

这意味着对于最优解 ：

  • 如果 ，由互补松驰性可知， ，样本 位于最大间隔边界，这就是支持向量；
  • 如果 ，即样本 在间隔边界之外，则对应的 ；

从 可以看出，只有当 时，对应的样本 才会对最优的 产生贡献。因此，最终的决策边界只由支持向量决定。

这个问题有许多技巧处理，比如SMO算法，求解算法的复杂度与样本数量（等于拉格朗日算子的数量）有关；

获得对偶问题的解后，存在下标使得,并按照上式获得primal form问题的解

Soft Margin SVM

硬间隔SVM要求所有样本都必须严格满足约束 ，即将所有样本正确且以至少为1的函数间隔分开。

然而，在实际应用中，数据往往不是完全线性可分的，或者包含一些噪声和异常点。对于近似线性可分的数据，即数据集中存在一些异常值，将其去除后，剩下的样本组成的集合是线性可分的。硬间隔SVM在这种情况下无法找到解。为了解决这个问题，引入了软间隔(Soft Margin)的概念。

软间隔SVM允许部分样本违反硬间隔约束，但通过引入惩罚项来控制违反的程度和数量。这通过引入松弛变量（Slack Variables） 来实现，每个样本 对应一个松弛变量。

约束条件放宽为：;

同时，为了惩罚违反约束的样本，将松弛变量的和加入到目标函数中，得到软间隔SVM的原始优化问题：

其中， 是一个惩罚项。C大表示对误分类样本的惩罚大；C小对误分类样本的惩罚小。如果C无穷大，则接近于硬间隔。

image-20250531115503412

构建拉格朗日函数：

求偏导获得

通过将将解约束回代，等价于求解如下优化问题

这个优化问题相比于原始问题，具有如下优秀性质；

  • C只出现在约束条件中， 从目标函数中消失。
  • μ是拉格朗日乘子，在对偶问题中消失。
  • 目标函数同硬间隔SVM一样

与硬间隔SVM不同，软间隔SVM的支持向量不仅包括恰好位于间隔边界上的点，还包括位于间隔内部（但分类正确）以及被错误分类的点。这些点对确定最终的分类超平面起着关键作用。

具体来说，根据松弛变量 的值，软支持向量可以分为几类：

  • 位于间隔边界上：对应 且 的样本点。

  • 位于间隔内部但分类正确：违反不等式约束的样本，对应 且 的样本点。

  • 被错误分类：对应 且 的样本点（）；

image-20250531121709499

梯度下降

在 硬间隔SVM 中，损失函数本身的目标是最小化权重，从而实现最大间隔，同时惩罚误分类样本（即没有满足约束条件的样本）。硬间隔的损失函数，包括两部分

  • 正则化项：用于控制间隔大小；
  • 约束损失：每个样本应用约束条件，如果该条件没有满足，则需要加入相应的损失；

定义如下合页损失(Hinge Loss)

因此梯度下降的更新规则为,对于每个不满足约束的样本

通过梯度下降法，我们可以逐步更新 SVM 的模型参数 和，使得损失函数逐渐收敛，最终获得一个可以有效分类的模型;

非线性SVM Kernel

对于原始特征空间中线性不可分的数据，SVM通过将样本映射到更高维的特征空间，使得样本在该高维空间中线性可分。这个过程通过核技巧（Kernel Trick）实现。

分类器在高维特征空间中的形式为：

其中 是将样本 映射到高维特征空间的映射函数。

将 代入决策函数，可以得到：

注意到在对偶问题和最终的决策函数中，样本的特征向量总是以内积的形式出现（在映射后的空间中是 或 ）。核函数（Kernel Function） 可以直接计算出在高维空间中的内积，而无需显式地进行映射 。

因此，通过引入核函数，软间隔SVM的对偶问题可以写为：

最终的分类决策函数为：

其中只有对偶变量 的样本（支持向量）对决策函数有贡献。

常见核函数举例：

  • 线性核： (对应原始空间的线性分类)
  • 多项式核：(处理一类比线性数据复杂，但是有规则线性边界的数据)
  • 径向基函数核(RBF)：(处理非线性数据的首选)
  • Sigmoid核：

SVM多分类器

一种是直接法，直接在目标函数上进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。但其计算复杂度比较高，实现起来比较困难，只适合用于小型问题中；

另一种是间接法，主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有one-against-one 和 one-against-all两种。

one-against-one多分类是指，在任意两类样本之间设计一个SVM，因此 n 个类别的样本就需要设计n(n-1)/2 个 SVM分类器。 当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。

one-against-all多分类是指，训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样n 个类别的样本就构造出n个 SVM 分类器。

支持向量回归

支持向量回归(SVR)是指，对所有的样本点，容忍回归模型与真实值 之间存在最大偏差 ，即以 f (x)为 中心，构建一个宽度为 2ε 的隔离带。

image-20250531160744750

若训练样本落入此间隔带，则认 为是被预测正确的。较小的 ϵ 值会使 SVR 模型更加复杂，因为允许的误差范围更小，对误差更敏感；

将SVR形式化为

𝓁

其中，为正则化常数，SVR损失函数选取为不敏感函数；落入中间间隔带的样本不计算损失，以提高模型的稀疏性；

𝓁

优点

  • 处理小样本：由于决策边界只由支持向量决定，SVM在小样本数据集上也能表现良好。
  • 处理非线性和高维识别：通过核技巧可以有效处理原始空间中非线性可分的数据，并且在高维空间中进行运算而避免"维度灾难"。
  • 泛化能力强：SVM建立在结构风险最小化原则上，通过最大化间隔来提高模型的泛化能力。
  • 凸优化问题：硬间隔和软间隔SVM的原始问题及对偶问题都是凸优化问题，可以保证找到全局最优解。