【机器学习】升维的线性划分:SVM

发表于 | 分类于 |

支持向量机(SVM)教程。

支持向量机（SVM）

支持向量机（SVM）介绍

SVM是一种监督学习算法，主要用于分类和回归分析。 它在解决小样本、非线性和高维问题上表现出色。

线性可分性

线性可分性是指数据集可以通过一条直线（二维）或超平面（多维）完全分开。

数学定义：存在向量$ \mathbf{w} $ 和实数$ b $ ，使得对于所有属于类别$ D_0 $ 的点$ \mathbf{x}_i $ ，都有$ \mathbf{w}^T\mathbf{x}_i + b > 0 $ ；对于所有属于类别$ D_1 $ 的点$ \mathbf{x}_j $ ，则有$ \mathbf{w}^T\mathbf{x}_j + b < 0 $ 。

支持向量

支持向量是距离超平面最近的一组样本点。

最大间隔超平面

最大间隔超平面是指能够以最大间隔将两类样本分开的超平面。

  • 其中间隔 (Margin) 是超平面两侧最近点到超平面的距离。
  • 支持向量(两侧距离超平面最近的样本点)到超平面的距离最大。

SVM的优化问题

SVM的目标是找到最大间隔超平面。

超平面可以用以下线性方程表示： \(w^Tx + b = 0\) 其中，$ \mathbf{w} $ 是权重向量，$ x $ 是数据点，$ b $ 是偏置项。

在高维空间中，点 $ \mathbf{x} $ 到超平面 $ \mathbf{w}^T\mathbf{x} + b = 0 $ 的距离 $ d $ 是： \(d = \frac{|\mathbf{w}^T\mathbf{x} + b|}{\|\mathbf{w}\|}\) 其中，$ |\mathbf{w}| $ 是权重向量的欧几里得范数。

超平面两侧被分为两类，可以设为任意的正数和负数对。 这里设 $y_1= 1$ 和 $y_2=-1$, 使得两侧的所有点到超平面的距离 $ d $ 可以如下表示： \(d = \frac{|\mathbf{w}^T\mathbf{x} + b|}{\|\mathbf{w}\|} = \frac {y(\mathbf{w}^T\mathbf{x} + b)}{\|\mathbf{w}\|}\)

这个距离最大的参数对应最优的超平面。

如果有约束如下： \(y(\mathbf{w}^T\mathbf{x} + b) \ge 1\)

优化问题变成 $ max(1/ \mathbf{w}|) $ 即为 $ min( \mathbf{w}|) $.

为方便计算，可以改写成 $ \frac {min(|\mathbf{w}|^2)}{2} $.

拉格朗日乘子法

为了解决这个优化问题，可以使用拉格朗日乘子法。

首先定义拉格朗日函数 $ L $： \(L(\mathbf{w}, b, \alpha) = \frac{1}{2}\|\mathbf{w}\|^2 + \sum_{i=1}^{n} \lambda_i \left( 1 - y_i(\mathbf{w}^T\mathbf{x}_i + b) \right)\) 其中，$ \lambda_i $ 是拉格朗日乘子，$ y_i $ 是第 $ i $ 个样本的真实标签。

为了找到最大间隔超平面，需要最小化拉格朗日函数 $ L $，同时满足KKT条件。

对参数 w 和 b 求偏导数，带入拉格朗日函数计算即可。

易知结果是二次规划问题，问题规模正比于训练样本数。

通常使用SMO（Sequential Minimal Optimization）算法或其变种来求解。

软间隔

对于线性不可分或含有噪声的数据，引入松弛变量 $ \xi_i \geq 0 $ 来允许一些样本点违反间隔条件。

这样，优化问题变为： \(\min_{w,b,\xi} \left( \frac{1}{2}||w||^2 + C\sum_{i=1}^{m}\xi_i \right)\) 受约束于： \(y^{(i)} (w^T x^{(i)} + b) \geq 1 - \xi_i, \quad \forall i\) \(\xi_i \geq 0, \quad \forall i\)

其中 \(C > 0\) 是惩罚参数，决定了违反间隔条件的样本点的影响程度。

处理方法和之前一致，可以使用拉格朗日乘子法和SMO算法求解。（只是多了个约束条件）

核技巧

在低维空间中，如果数据不是线性可分的，即不存在一条直线（在高维中为超平面）能将不同类别的数据点完全分开，那么在原始特征空间中直接应用线性分类器如线性SVM将无法达到良好的分类效果。

为了使数据变得线性可分，需要将数据从低维空间映射到一个更高维的空间，在那里数据可能成为线性可分的。

理论上，可以手动设计一个映射函数，将数据映射到一个更高维的空间。 然而，直接在高维空间中进行计算会非常复杂和耗时，因为维度的增加会导致计算量急剧上升。

核函数 (K(x, x’) = \phi(x)^T \phi(x’)) 允许在不显式地知道映射函数 (\phi) 的情况下计算映射后的数据点之间的内积，即高维空间中数据点相似度。

以下是几种常见的核函数：

  1. 线性核函数（Linear Kernel） \(K(x, x') = x^T x'\) 这是最简单的核函数，相当于没有进行任何映射，直接在原始空间中计算两个向量的内积。

  2. 多项式核函数（Polynomial Kernel） \(K(x, x') = (\gamma x^T x' + r)^d\) 其中，$\gamma$ 和 $r$ 是参数，$d$ 是多项式的次数。这个核函数将数据映射到一个 $d$ 维的多项式空间。

  3. 高斯径向基函数核（Gaussian Radial Basis Function Kernel 或 RBF Kernel） \(K(x, x') = \exp(-\gamma||x - x'||^2)\) 高斯RBF核函数是SVM中最常用的核函数之一，它使用指数函数来衡量两个向量之间的相似度。参数 $\gamma$ 控制着高斯核的宽度。

  4. 拉普拉斯核函数（Laplacian Kernel） \(K(x, x') = \exp(-\gamma||x - x'||)\) 这个核函数类似于RBF核，但是使用了绝对值距离而不是平方欧几里得距离。

选择哪种核函数取决于具体的问题和数据的特性。

通常情况下，高斯RBF核函数因其灵活性和在许多数据集上的良好表现而被广泛使用。 不过对于简单线性可分的数据集，线性核函数足够满足要求的同时计算成本也会更低。

在选择核函数时，通常需要通过交叉验证来调整参数和评估性能。

优点

  1. 可解释性：SVM有严格的数学理论支撑，通过最大间隔原则确定决策边界，这使得模型的决策过程相对直观和可解释。

  2. 关键样本识别：SVM仅依赖于支持向量（即那些最靠近决策边界的样本点）进行决策，这有助于减少模型的复杂度并提高泛化能力。

  3. 非线性问题处理：通过核技巧，SVM能够处理非线性可分问题，无需显式地将数据映射到高维空间，避免了维度爆炸带来的计算困难。

  4. 避免维数灾难：由于决策依赖于支持向量而非全部样本，SVM在高维数据上的表现优于依赖于样本空间维数的其他算法。

缺点

  1. 训练时间：SVM的训练时间较长，特别是对于大规模数据集，因为需要求解一个二次规划问题。尽管序列最小优化（SMO）算法改进了这一点，但时间复杂度仍与样本数量相关。

  2. 存储需求：使用核技巧时，需要存储核矩阵，这可能导致较高的空间复杂度，尤其是当数据集规模增大时。

  3. 预测速度：预测阶段的速度取决于支持向量的数量，如果支持向量很多，预测时间可能会较长。

  4. 参数选择：SVM的性能高度依赖于选择合适的核函数及其参数，这可能需要大量的试验和调优。

  5. 适用范围限制：虽然SVM在小到中等规模的数据集上表现优异，但对于非常大的数据集（例如数百万或更多样本），其计算效率和存储需求可能成为瓶颈。