SVM

SVM

支持向量机（SVM，Support Vector Machine）是一种强大的监督学习模型，用于分类和回归分析。

SVM的核心思想是找到一个最优的超平面（或决策边界），以最大化不同类别之间的边际

  1. 超平面（Hyperplane）：
    • 在SVM中，超平面是一个决策边界，它可以将数据空间分割成不同的类别。在二维空间中，这个超平面是一条线；在三维空间中，是一个平面；在更高维度中，这个概念被推广到超平面。
  2. 边际（Margin）：
    • 边际是数据点到决策边界的最短距离。SVM的目标是找到最大化边际的超平面，从而在类别之间提供尽可能大的间隔。
  3. 支持向量（Support Vectors）：
    • 支持向量是距离超平面最近的数据点，它们是决定超平面位置和方向的关键元素。这些点实际上“支撑”了边际，因此被称为支持向量。
  4. 核技巧（Kernel Trick）：
    • 在处理非线性可分的数据时，SVM使用核技巧将数据映射到更高维的空间，在这个空间中数据可能是线性可分的。常用的核函数包括多项式核、径向基函数（RBF）或高斯核等。

硬间隔

硬间隔就是要求超平面划分的数据不能有错误

所以硬间隔假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。

我们假设这个超平面是

f(x)=wx+bf(x)=wx+b

其中ww是超平面的法向量，bb是截距
对于每个样本(xi,yi)yi∈(1,−1)(x_i,y_i)\quad y_i\in(1,-1)，硬间隔要求：

{ifyi=1,wxi+b>=1ifyi=−1,wxi+b<=−1\begin{cases} if & y_i=1, wx_i+b>=1\\ if & y_i=-1, wx_i+b<=-1\\ \end{cases}

所以需要满足yi(wxi+b)>=1y_i(wx_i+b)>=1,确保所有数据点被正确分类

在这里插入图片描述

接着就是确定哪根线才是我们想要的了，图中被圈出来的点就是支持向量，因为超过了这些点，分类线就没办法完美分类了，在二维空间中，点xx到直线f(x)=wx+bf(x)=wx+b的距离为：

r=∣wtx+b∣∣∣w∣∣r=\frac{|w^tx+b|}{||w||}

则，异类支持向量的距离为：

r=1∣∣w∣∣r=\frac{1}{||w||}

异类支持向量的距离也被称为间隔，不难看出，当间隔最大时，该分类线是最优的，鲁棒性最强，比如，我们在一座海上大桥上行驶，当然是行驶在最中间是最安全的。

即，我们要找到能满足式中约束的参数 ww 和 bb ， 使得 rr 最大，也就是ww最小，为了方便计算化作12∣∣w∣∣2\frac{1}{2}||w||^2，求ww最大的形式

构建拉格朗日函数

L(w,b,α)=12∣∣w∣∣2−∑i=1nai[yi(w⋅xi+b)−1]L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^{n}a_i[y_i(w·x_i+b)-1]

对L(w,b,α)L(w,b,\alpha)分别对ww和bb求偏导，并令他为0
对ww：

∇wL=w−∑i=1naiyixi=0∂L∂b=−∑i=1naiyi=0\nabla_wL=w-\sum_{i=1}^{n}a_iy_ix_i=0\\ \frac{\partial L}{\partial b}=-\sum_{i=1}^{n}a_iy_i=0

得到对偶问题

L~(α)=∑i=1nαi−12∑i,j=1nyiyjαiαjxi⋅xj\tilde{L}(\alpha) = \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{n} y_i y_j \alpha_i \alpha_j x_i \cdot x_j

对偶问题的约束

αi≥0∑i=1nαiyi=0\alpha_i \geq 0 \\ \sum_{i=1}^{n} \alpha_i y_i = 0

求解对偶问题

使用数值优化方法（如序列最小优化算法，SMO）求解 aia_i

计算ww和bb

  • 使用求得的 aia_i计算 ∑i=1nαiyixi=0\sum_{i=1}^{n} \alpha_i y_i x_i= 0。
  • 选择任意一个支持向量xj,yjx_j,y_j 并使用条件 yj(w⋅xj+b)=1y_j(w·x_j+b)=1 计算 bb

得到最终的超平面

软间隔

所以现实任务中很难使得训练样本在特征空间中线性可分。所以引入“松弛变量”(slack variables) 来实现软间隔，软间隔就是允许超平面划分的数据可以有错误。

松弛变量

在硬间隔SVM中本应该是在虚线内侧没有任何的样本点的，而在软间隔SVM中，因为不是完全的线性可分，所以虚线内侧存在有样本点，通过向每一个在虚线内侧的样本点添加松弛变量ξi\xi_i，将这些样本点搬移到支持向量虚线上。而本身就是在虚线外的样本点的松弛变量则可以设为0。 于是，给每一个松弛变量赋予一个代价ξi\xi_i，我们的目标函数就变成了：

f(W,ξ)12∥w∥2+C∑i=1nξii=1,2,…,Nf(W,\xi) \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n \xi_i\\ i=1,2,\dots,N

惩罚参数C

上方公式中的CC称为惩罚参数，C值大的时候对误分类的惩罚增大，C值小的时候对误分类的惩罚减小。上方公式有两层含义：使得12∥w∥2\frac{1}{2} \|w\|^2尽量小即是间隔尽可能大，同时使得误分类的数量尽量小，C是调和两者的系数，是一个超参数。 于是我们的软间隔SVM的问题可以描述为：

\begin{align} \min_{w, b, \xi} \quad & \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n \xi_i \\ \text{s.t.} \quad & y_i (w \cdot x_i + b) \geq 1 - \xi_i, \quad i = 1, \ldots, n \\ & \xi_i \geq 0, \quad i = 1, \ldots, n \end{align}

hinge损失函数

它是用于评估分类的性能的一个标准方法

Hinge损失函数的定义

对于一个给定的数据点和分类器，Hinge损失函数定义如下：

L(y,f(x))=max(0,1−y⋅f(X))L(y,f(x))=max(0,1-y · f(X))

  • yy 是实际的类别标签，通常为 +1 或 -1。
  • f(x)f(x)是分类器对数据点 xx的预测值。
  • L(y,f(x))L(y,f(x)) 是针对单个数据点计算的损失。

Hinge损失函数的目标是确保正确分类的数据点的预测值和实际类别标签之间的乘积大于等于1。如果这个条件得到满足，损失就是0；否则，损失随着预测值偏离正确分类的界限而增加。

在支持向量机中，Hinge损失函数用于找到能够最大化两个类别间隔的超平面。同时，它也考虑到可能存在的分类错误或数据点无法完美分离的情况。通过最小化Hinge损失，SVM尝试找到一个折中方案，既保持间隔宽度，又控制分类错误。

优点

  • 间隔最大化：Hinge损失鼓励找到具有最大间隔的决策边界，这有助于模型的泛化能力。
  • 稀疏解：在SVM中，Hinge损失通常导致稀疏解，这意味着模型只由少数支持向量定义，从而提高了计算效率。

缺点

  • 不是平滑函数：Hinge损失不是处处可导的，这可能使得使用某些优化算法（如梯度下降）时更加复杂。
  • 对异常值敏感：Hinge损失对于异常值比较敏感，可能需要额外的处理来管理噪声和异常值。

线性不可分

核技巧是处理非线性可分数据的最有效方法之一。通过使用核函数，可以将数据映射到更高维的空间，其中数据可能变得线性可分。接下来介绍三个老师要求的核函数。

假设x,x′x,x'是两个数据点

高斯核(径向基函数)

定义：

K(x,x′)=exp(−γ∥x−x′∥2)K(x,x')=exp(-\gamma\|x-x'\|^2)

RBF核可以映射特征到无限维的空间，非常适合处理各种复杂的非线性关系。
γ\gamma 是一个可调参数，用于控制核的宽度。
∥x−x′∥2\|x-x'\|^2表示两个点之间的欧氏距离的平方。

高斯核的基本思想是测量数据点之间的相似度。如果两个点非常接近，则它们的核值将接近1；如果它们相距很远，则核值将快速趋近于0。这种性质使得高斯核能够创建一个非常灵活的决策边界，适应数据中的非线性模式。

参数 γ\gamma 的作用

  • 如果 γ\gamma 很大，核的宽度将变窄，这意味着只有非常接近的点才被认为是相似的。这可能导致模型过拟合。
  • 如果 γ\gamma 很小，核的宽度将变宽，这意味着即使是相距较远的点也被认为是相似的。这可能导致模型欠拟合。

线性核

定义：

K(x,x′)=xTx′K(x,x')=x^Tx'

线性核是最简单的核函数，它仅计算输入向量的内积。适用于线性可分的数据集。
xTx′x^Tx'表示 xTx^T 和 x′x' 的点积（即内积）。

线性核实际上不涉及任何映射到高维空间的操作，它仅仅计算数据点在原始空间中的相似度。如果两个点在特征空间中方向相同或相似，它们的内积（点积）将会较大；如果它们正交或方向不同，则内积较小。

与非线性核（如高斯核、多项式核）相比，线性核有以下特点：

  • 计算效率高：由于不需要映射到高维空间，线性核的计算复杂度较低。
  • 易于解释：线性核生成的模型易于理解和解释，因为它直接在原始特征空间中操作。
  • 过拟合风险低：在特征维数非常高的情况下，使用线性核可以减少过拟合的风险。

多项式核

定义：

K(x,x′)=(γxTx′+r)dK(x,x')=(\gamma x^Tx'+r)^d

这里的 dd 是多项式的度数，γ\gamma 和 rr 是可调参数。多项式核可以映射特征到一个高维空间，适合处理非线性可分的数据。

  1. γ\gamma 是一个可调参数，用于控制核的宽度。决定了原始特征空间中数据点的影响范围。较小的 γ\gamma 使得决策边界更加平滑，而较大的 γ\gamma 可以捕捉更精细的数据结构。

    例子：假设我们有二维数据（特征 x1x_1 和 x2x_2）, 在同样的二维数据中，如果γ\gamma很小，那么即使x1x_1 和 x2x_2的值较大，其对核函数值的贡献也较小，这可能导致更平滑的决策边界。相反，如果较γ\gamma大，即使是小的变化也会对核函数值产生较大影响，这可能导致模型在数据中捕捉到更细微的模式。

  2. rr是独立项（independent term），有时被称为偏置项（bias）。允许在更高维度空间中调整核函数的偏置。这有助于优化决策边界的位置。

    **例子：**如果rr 较大，那么即使两个数据点在原始空间中不相似，它们在高维空间中的内积（即核函数值）也可能较大。这可以帮助模型在原始特征空间中不明显的模式上产生更高的响应

  3. dd是核的度数，它决定了映射到高维空间的复杂性。控制着核函数的复杂性和高维映射的非线性程度。较高的 dd值意味着更高的复杂性，可以捕捉更复杂的模式，但也增加了过拟合的风险。

    例子：如果选择 d=2d=2，多项式核将包括 x12x_1^2、x22x_2^2和 x1x@x_1x_@ 等项。这允许模型不仅捕捉每个特征的平方效应，还有特征之间的交互效应。但如果数据实际上是线性可分的，那么 d=2d=2 可能就过于复杂，导致不必要的模型复杂度。

多项式核通过计算数据点的内积，并将其映射到更高的维度，从而能处理非线性关系。当 d>1d>1 时，多项式核能捕捉数据点间的更复杂的相互作用。

综合例子

假设我们正在处理一个分类问题，数据集包含了不同学生的学习时间和考试成绩。我们希望使用SVM模型来预测学生是否会通过考试。如果我们选择多项式核，那么：

  • 选择较高的 dd 可以帮助模型捕捉学习时间和考试成绩之间复杂的非线性关系。
  • 调整 γ\gamma 可以帮助模型确定这些特征的细微变化对预测结果的影响程度。
  • 设置合适的 rr 可以进一步调整模型在特征空间中的灵活性。

结束