支持向量机SVM——基于分类问题的监督学习算法

支持向量机（SVM，Support Vector Machine）是一种常用于分类问题的监督学习算法，其核心思想是通过寻找一个最佳的超平面来将不同类别的数据点分开，从而实现分类。支持向量机广泛应用于模式识别、文本分类、图像识别等任务。

基本概念

决策超平面：在一个特征空间中，假设我们有一个二维数据集。通过绘制样本点及其对应的标签，我们希望找到一个直线（在二维空间中，这个超平面是线；在三维或更高维空间中，它是一个平面）来分隔这些数据点。对于SVM来说，我们不仅仅关心能分开数据点的任何一条直线，而是希望找到一条具有最大间隔的直线，间隔是指从直线到最近的数据点的距离。
最大间隔： SVM的目标是通过最大化“间隔”来提高模型的泛化能力。间隔定义为从超平面到最近的训练样本点的距离，最近的点称为支持向量。最大化间隔可以帮助模型更好地分类新的、未见过的数据点。
支持向量：支持向量是位于边界上，或距离边界最近的数据点。支持向量在训练过程中起着决定性作用，因为它们直接影响超平面的定义。
线性可分问题：当数据集是线性可分的，即可以找到一个超平面把不同类别的点完全分开时，SVM会寻找那个最大化间隔的超平面。
线性不可分问题：在现实中，数据集往往是线性不可分的。在这种情况下，SVM通过引入核函数将数据映射到更高维的特征空间，使得在高维空间中数据变得线性可分。

线性SVM原理步骤

1、优化问题

假设我们有一个二分类问题，数据集包含 n 个样本，每个样本 $x_{i} \epsilon \mathbb{R}^{d}$ （这个表示xi是一个d维向量，属于d维实数空间），标签 yi∈{−1,+1}。我们希望找到一个超平面，用方程 $w^{T}x+b=0$ 来表示，其中：

w 是超平面的法向量
b 是超平面的偏置。

我们的目标是通过最大化间隔来找到最优的超平面。由于超平面到支持向量的距离为 $\frac{1}{\left \| w \right \|}$ ，

因此我们的优化问题可以转化最小化问题为：

$min\frac{1}{2}\left \| w \right \|^{2}$

同时要满足约束条件：

$y_{i}(w^{T}x_{i}+b)\geqslant 1$ ，对于所有的 i = 1,2, ... , n

这个约束条件确保了每个样本点都被正确分类，并且距离超平面至少有一个单位的间隔。

2、对偶问题

为了通过拉格朗日乘子法来求解这个优化问题，我们构建拉格朗日函数：

$L(w,b,\alpha )=\frac{1}{2}\left \| w \right \|^{2}-\sum_{i=1}^{n}\alpha _{i}[y_{i}(w^{T}x_{i}+b)-1]$

其中， $\alpha _{i}$ 是拉格朗日乘子。

通过对 w 求偏导数并令其为零，可以得到最优的 w，并计算出 b ，从而得到最终的决策超平面。

3、最终的决策函数

最终的决策函数是：

若 f(x) >= 0 ，则预测该类别为 +1 类，否则为 -1 类。

非线性SVM基本原理

当数据不是线性可分时，SVM通过引入核函数将数据映射到高维空间，使得在这个高维空间中数据变得线性可分。

1、非线性原问题：

约束条件：

其中， ϕ(x) 是一个映射函数，用于将一个原始数据映射到高维，变成高维的数据。

举个例子讲解映射函数ϕ(x)

比如，有以下映射函数：

样本 x1=(1,1)映射到 $(1, 1, \sqrt{2})$

样本 x2=(2,−1) 映射到 $(4, 1, -2\sqrt{2})$

通常，直接使用映射后的数据点来求解优化问题通常是不可行的，因为我们并不直接知道映射函数 ϕ(x)的显式形式。然而，通过使用核函数，我们可以通过以下方式计算数据点的内积，进行隐士计算：