SVM支持向量机

时间：2024-10-08 14:50:51

向量机可解决分类和回归两种问题，监督学习方法。

SVM起初针对二分类问题提出，1、2、3小节都是针对二分类问题展开理论推导，y取±1！

一、SVM

引入知识

  • 优化目标：间隔（Margin虚线之间）最大化，这靠支持向量确定（3个加黑圈的点为支持向量）。
  • 支持向量确定决策边界（也叫分离超平面，图中实线），该超平面可以将不同类别最优分隔开，即超平面离最近的数据点的距离最大。
  • 除了支持向量，其他数据并没有起到任何作用。因此，SVM 对于数据特征数量远高于数据样本量的情况也有效。
  • 引入“间隔”不只用决策边界（超平面）的原因——①提高模型泛化能力；②以最大化间隔为优化目标，这是一个凸优化问题，解决更加简单。

上图是线性可分问题（硬间隔问题），多数数据线性不可分——引入两种方法：软间隔和核技巧

  • 软间隔：（对于二维数据）还是用一条直线分，但存在缓冲区。即分离数据时，有数据点侵入间隔，甚至超越间隔带。

  • 核技巧（内积核函数）将原始输入数据映射到高维空间，是一种数据升维。例如下面数据升维到3维空间后，很容易找到一个平面（对应二维的直线）将两者分开。

会发现仍有少量蓝点处于间隔带，不是很完美。所以，一般并用软间隔和核技巧两种方法。


 

1、SVM线性可分问题（硬间隔）

①决策边界（超平面）

  • w和b为模型参数，b为一个实数，w为一个列向量（f的梯度向量，垂直于决策边界）；
  • x为数据特征，也是一个列向量；
  • w和x的行数 = 特征数D，当D=2时即为上面的二维平面分类问题

公式展开如下。展开后每个w都是一个实数：

当D=2时（二维平面里的分类问题），公式变为如下。即表示一条直线！！

对于二维平面（D=2）的二分类问题（K=2），处于决策边界上方的数据点f>0，处于决策边界下的数据点f<0。

模型训练好后，w和b确定，然后用决策函数进行对新数据点的分类，以二分类问题为例：

  • q为任意查询点（新数据、测试数据），一个列向量，类比x，实际也表示了该数据点在空间中的坐标位置。
  • sign为符号函数，例如类别1（边界上）映射为+1，类别2（边界下）映射为-1。

②支持向量到决策边界的距离

某一支持向量坐标位置用列向量 q 表达，则q 到决策边界（超平面）的距离：

  • 式中矩阵叉乘可转化为点积，分母为向量w的二次范数（即每个元素平方和的平方根）
  • 分子的绝对值使用时可以去掉，带正负号可判断点与超平面的关系

则支持向量位于硬间隔的上界或下界上，到决策边界的距离为±h。经过推导间隔宽度2h可以用梯度向量w表示：

SVM同时可解决分类和回归问题，两者都与“距离”息息相关：

  • 分类问题中，超平面要尽可能地将不同类别的数据分开，并保持最大的间隔；
  • 回归问题中，要使得超平面尽可能地接近所有数据点，并控制超平面两侧的数据点到超平面的距离

③构造并求解优化问题（拉格朗日乘子法）

SVM优化目标——最大化间隔，下面利用拉格朗日乘子法构造并求解SVM优化问题。（二分类问题y取+1或-1，分别对应位于超平面上和下）

  • 上面是目标函数，下面是约束条件
  • arg max 就是使后面这个式子达到最大值时的变量的取值；subject to简称“s.t.”（译为受制于）
  • i为样本数据点序数，n为样本数据数量
利用拉格朗日乘子法并借用对偶理论，可将上述目标问题转化成一个以 λ 为变量的 无约束优化问题 ：
  • 优化目标：第一个式子最大化化时λ 的取值（λ 代替了w和b）——第一个式子实际就是拉格朗日函数。
  • λ 为拉格朗日乘子构造的列向量
  • 这个优化问题常被称作 拉格朗日对偶问题（对偶问题）

④决策边界变形

利用拉格朗日乘子，决策边界可变形为：

  • 注：行向量 x (i) 为第 i 个数据点，x 为未知量构成的列向量
  • Coefficients结果为行向量

2、SVM线性不可分问题：软间隔方法

软间隔处理的数据呈现“你中有我，我中有你”！具体可 对比上面的图 ，软间隔 SVM 方法的核心思想是 牺牲部分数据点分类准确性，来换取更宽的间隔 。主要有2个参数：
  • 松弛变量\xi：用来模糊间隔边界
  • 惩罚因子C：加入惩罚因子后，优化问题描述为：

3、SVM线性不可分问题：核技巧（将数据映射到高维数据空间）

核技巧 原理——将样本数据映射到高维特征空间中，使数据在高维空间中线性可分（非线性转化为线性可分问题）。
  • 常用的核函数有线性核函数、多项式核函数、Sigmoid核和径向基函数核函数（高斯核）等
  • 不同的核函数适用于不同的数据集和问题类型
  • 用 交叉验证 等技术来选择最佳的核函数和参数
  • 映射函数：x经过特征映射后得到ϕ(x) 向量，ϕ() 即为映射函数，映射过程为一个升维的过程

例如下面的单维度数据被映射到二维空间的例子：

 

二维到三维：

①引入映射函数后决策边界的改变

SVM在解决线性可分问题时（没引入映射函数概念时）决策边界为：

经过映射函数进行特征映射后决策边界如下。一般ϕ(x) 的特征数远多于原始数据 x

②引入映射函数后优化目标拉格朗日函数的改变

代入映射函数，经推导，拉格朗日函数改变的地方即为——核函数：

这一项核函数可以记为如下式。可发现核函数按照某种规则完成“向量 → 标量”的运算。

利用核函数记法，拉格朗日函数可简化记为（可对比线性可分问题）

4、SVM多分类问题

SVM起初针对二分类问题提出，怎样把“二分类”问题拓展到“多分类”问题呢？以“一对多”和“一对一”的思想最为广泛！

①“一对多”思想——多个二分类器代替多分类器

假设训练集（由x、y构成，x为特征向量，y为类别标签）有 m(m>2)个类别 ，样本数为 n。只需将其中一类单独划分，再将剩余分类划分为一类，依次类推 构建 m 个二分类器 如下。

上式包含惩罚因子、松弛变量、映射函数等上面介绍的概念！i可取1、2...m，所以代表了m个SVM二分类器，求解可得m个决策函数：

即类别i与其余类别间的决策边界（最优超平面）为：

  • 上图为理想状态，在实际分类时，经常会有 x 对应多个类别或无类别对应情况，此无法确认 x 正确类别——构建分类器时会出现不可分区域，即阴影部分所示，处于阴影部分的分类样本将无法被正确分类。

②“一对一”思想——多个二分类器+投票

  • 基本思想与“一对多”分类法相同，也是通过多个二分类器解决多分类问题
  • 但具体方式是两两配对，每两个类别构建一个二分类器，最终构建 m(m −1)/ 2 个二分类器
  • m(m-1)/2 个二分类器分析完毕后，通过“投票”的方式对样本进行分类
  • 所有分类器对第 i 、 j 类投票，票数高的那一类就是最终分类结果：

5、SVM回归问题

SVM分类的优化函数为间隔最大化，SVM回归即将间隔距离换为所有点到超平面的距离最小化！

未完待续....

相关文章