SVM详解

支持向量机 (Support Vector Machine, SVM) 是一种非常强大且流行的监督学习算法，可用于分类和回归任务。它的核心思想是找到一个最优的超平面，使得不同类别的数据点之间的间隔 (margin) 最大化。

1. SVM 是什么？

想象一下，你有一些数据点，属于两个不同的类别。SVM 的目标是找到一条线（二维情况下）或一个超平面（更高维度情况下），这条线/超平面能够最好地将这两个类别分开。

• 超平面 (Hyperplane)：在 n 维空间中，一个 n-1 维的子空间。例如，在二维空间中，超平面是一条直线；在三维空间中，超平面是一个平面。
• 间隔 (Margin)：超平面与离它最近的任何类别的数据点之间的距离。SVM 的目标是最大化这个间隔。
• 支持向量 (Support Vectors)：那些离超平面最近的数据点，它们“支撑”着这个超平面。如果移动支持向量，超平面也会随之改变。其他数据点则不影响超平面的位置。

核心思想： 找到一个具有“最大间隔”的决策边界。

2. 线性SVM (Linear SVM)

我们首先从数据线性可分的情况开始。

2.1. 线性可分SVM (硬间隔SVM)

2.1.1. 超平面的定义

在特征空间中，超平面可以用以下线性方程来描述：

$$w^{T}x+b=0$$
其中：

• $w=(w_1,w_2,...,w_d)$ 是法向量 (normal vector)，决定了超平面的方向。
• $x=(x_1,x_2,...,x_d)$ 是特征向量。
• $b$ 是偏置项 (bias term)，决定了超平面与原点之间的距离。

一个样本点 $x_i$ 被预测的类别 $y_{p}red$ 可以通过以下函数得到：

$$y_{pred}=\text{sign}(w^T{x}_i+b)$$

其中 $sign()$ 是符号函数。如果 $w^T{x}_i+b>0$，则预测为正类 (通常用 +1 表示)；如果 $w^T{x}_i+b<0$，则预测为负类 (通常用 -1 表示)。

2.1.2. 函数间隔 (Functional Margin)

对于一个给定的训练样本 $(x_i,y_i)$ (其中 y i ∈ { − 1 , + 1 } y_i \in \{-1, +1\} yi​∈{−1,+1}) 和一个超平面 $(w,b)$，我们定义函数间隔为：

$${\hat{\gamma }}_i=y_i(w^T{x}_i+b)$$

• 如果 $y_i=+1$，我们希望 $w^T{x}_i+b$ 是一个大的正数。
• 如果 $y_i=-1$，我们希望 $w^T{x}_i+b$ 是一个大的负数。
• 因此，$y_i(w^T{x}_i+b)$ 总是正的 (对于正确分类的点)，并且值越大，表示分类的确信度越高。

整个训练集的函数间隔定义为所有样本点中最小的函数间隔：

$$\hat{\gamma }=\underset{i=1,...,N}{\min }{\hat{\gamma }}_i$$

问题： 函数间隔可以通过等比例缩放 $w$ 和 $b$ (例如，将它们都乘以2) 来任意增大，而超平面本身并没有改变。这使得函数间隔不适合作为优化的目标。

2.1.3. 几何间隔 (Geometric Margin)

点 $x_i$ 到超平面 $w^{T}x+b=0$ 的几何距离为：

$$\text{distance}=\frac{|w^T{x}_i+b|}{\Vert w\Vert }$$

其中 $||w||$ 是 $w$ 的 L2 范数 (欧几里得长度)。

对于一个正确分类的样本 $(x_i,y_i)$，几何间隔为：

$${\gamma }_i=y_i\left(\frac{w^T{x}_i+b}{\Vert w\Vert }\right)=\frac{{\hat{\gamma }}_i}{\Vert w\Vert }$$

几何间隔不会因为 $w$ 和 $b$ 的等比例缩放而改变，因此它更适合作为优化的目标。

整个训练集的几何间隔定义为所有样本点中最小的几何间隔：

$$\gamma =\underset{i=1,...,N}{\min }{\gamma }_i$$

2.1.4. 最大化间隔 (Maximizing the Margin)

SVM 的目标是找到一个超平面 $(w,b)$，使得几何间隔 $\gamma$ 最大化。
即：

$$\underset{w,b}{\max }\gamma$$
约束条件是，对于所有样本 $i$：
$$y_i\left(\frac{w^T{x}_i+b}{\Vert w\Vert }\right)\ge \gamma$$

为了简化问题，我们可以固定函数间隔 $\hat{\gamma }=1$ (因为 $w$ 和 $b$ 可以等比例缩放而不改变超平面，所以我们可以选择一个特定的缩放使得支持向量上的函数间隔为1)。
这时，对于支持向量 $x_s$，有 $y_s(w^T{x}_s+b)=1$。
那么，几何间隔就变成了 $\gamma =1/||w||$。

最大化 $1/||w||$ 等价于最小化 $||w||$，也等价于最小化 $(1/2)||w|{|}^2$ (为了方便求导)。

所以，原始优化问题 (Primal Problem) 变为：

$$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}\Vert w{\Vert }^2\\ \text{subject to}& y_i(w^T{x}_i+b)\ge 1,\forall i=1,...,N\end{array}$$

这是一个带约束的凸二次规划问题。
那些使得 $y_i(w^T{x}_i+b)=1$ 的点就是支持向量。

2.2. 线性不可分SVM (软间隔SVM)

在实际应用中，数据往往不是完全线性可分的，或者存在一些噪声点/异常点。硬间隔SVM在这种情况下无法工作。
为了解决这个问题，我们引入软间隔 (Soft Margin) 的概念，允许一些点不满足间隔约束 $y_i(w^T{x}_i+b)\ge 1$。

2.2.1. 松弛变量 (Slack Variables)

为每个样本点 $x_i$ 引入一个松弛变量 ${\xi }_i\ge 0$ (读作 “ksi”)。
约束条件变为：

$$y_i(w^T{x}_i+b)\ge 1-{\xi }_i,\forall i=1,...,N$$

• 如果 ${\xi }_i=0$：点 $x_i$ 在正确的间隔边界之外（被正确分类且满足间隔）。
• 如果 $0<{\xi }_i<1$：点 $x_i$ 在间隔边界之内，但在正确的分类一侧（被正确分类，但间隔不足）。这些点也是支持向量。
• 如果 ${\xi }_i=1$：点 $x_i$ 恰好在超平面上。
• 如果 ${\xi }_i>1$：点 $x_i$ 在超平面的错误一侧（被错误分类）。

2.2.2. 软间隔的优化问题

我们希望松弛变量 ${\xi }_i$ 的值尽可能小。因此，在目标函数中加入对松弛变量的惩罚项：

$$\begin{array}{rl}\underset{w,b,\xi }{\min }& \frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^N{\xi }_i\\ \text{subject to}& y_i(w^T{x}_i+b)\ge 1-{\xi }_i,\forall i=1,...,N\\ & {\xi }_i\ge 0,\forall i=1,...,N\end{array}$$

其中：

• $C>0$ 是惩罚参数或正则化参数。它控制了对误分类样本的惩罚程度。
  • $C$ 很大时：算法会尝试将尽可能多的点正确分类，即使这意味着间隔会变小。模型可能过拟合。
  • $C$ 很小时：算法会更容忍误分类，以获得更大的间隔。模型可能欠拟合。

$C$ 是一个需要通过交叉验证等方法来调整的超参数。

3. 对偶问题 (Duality)

直接求解上述带约束的优化问题比较困难。通常我们会将其转换为对偶问题 (Dual Problem) 来求解。对偶问题有两个主要好处：

1. 更容易求解。
2. 自然地引入了核技巧 (Kernel Trick)，使得SVM可以处理非线性问题。

3.1. 拉格朗日乘子法

对于软间隔SVM的原始问题：
$$\begin{array}{rl}\underset{w,b,\xi }{\min }& \frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^N{\xi }_i\\ \text{s.t.}& y_i(w^T{x}_i+b)\ge 1-{\xi }_i\\ & {\xi }_i\ge 0\end{array}$$
我们可以将其改写为标准形式的不等式约束：

1. $1-{\xi }_i-y_i(w^T{x}_i+b)\le 0$
2. $-{\xi }_i\le 0$

引入拉格朗日乘子 ${\alpha }_i\ge 0$ 和 ${\mu }_i\ge 0$。构造拉格朗日函数 $L(w,b,\xi ,\alpha ,\mu )$：

$$L(w,b,\xi ,\alpha ,\mu )=\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^N{\xi }_i-\sum _{i=1}^N{\alpha }_i[y_i(w^T{x}_i+b)-1+{\xi }_i]-\sum _{i=1}^N{\mu }_i{\xi }_i$$
其中 $\alpha =({\alpha }_1,...,{\alpha }_N)$ 和 $\mu =({\mu }_1,...,{\mu }_N)$ 是拉格朗日乘子向量。

原始问题等价于：
$$\underset{w,b,\xi }{\min }\underset{\alpha \ge 0,\mu \ge 0}{\max }L(w,b,\xi ,\alpha ,\mu )$$
其对偶问题是：
$$\underset{\alpha \ge 0,\mu \ge 0}{\max }\underset{w,b,\xi }{\min }L(w,b,\xi ,\alpha ,\mu )$$

3.2. 求解对偶问题

首先，固定 $\alpha$ 和 $\mu$，让 $L$ 对 $w,b,{\xi }_i$ 求偏导并令其为0：

1. 对 $w$ 求偏导：
   $$\frac{\partial L}{\partial w}=w-\sum _{i=1}^N{\alpha }_i{y}_i{x}_i=0⟹w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i$$

2. 对 $b$ 求偏导：
   $$\frac{\partial L}{\partial b}=-\sum _{i=1}^N{\alpha }_i{y}_i=0⟹\sum _{i=1}^N{\alpha }_i{y}_i=0$$

3. 对 ${\xi }_i$ 求偏导：
   $$\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0⟹C-{\alpha }_i-{\mu }_i=0$$

将这些结果代回到拉格朗日函数 $L$ 中：

经过化简（这里省略详细代数步骤，但主要思路是将 $w$ 代入 $(1/2)||w|{|}^2$ 和 $\sum {\alpha }_i{y}_i{w}^T{x}_i$，并利用 $\sum {\alpha }_i{y}_i=0$ 和 $C-{\alpha }_i-{\mu }_i=0$），得到对偶问题的目标函数：

$$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^T{x}_j)\\ \text{subject to}& \sum _{i=1}^N{\alpha }_i{y}_i=0\\ & 0\le {\alpha }_i\le C,\forall i=1,...,N\end{array}$$
注意，${\mu }_i\ge 0$ 和 $C-{\alpha }_i-{\mu }_i=0$ 意味着 $C-{\alpha }_i\ge 0$，即 ${\alpha }_i\le C$。结合 ${\alpha }_i\ge 0$，得到约束 $0\le {\alpha }_i\le C$。

这是一个关于 ${\alpha }_i$ 的二次规划问题。

3.3. KKT 条件

对于原始问题和对偶问题，最优解必须满足 Karush-Kuhn-Tucker (KKT) 条件：

1. 主问题可行性：$y_i(w^T{x}_i+b)\ge 1-{\xi }_i$, ${\xi }_i\ge 0$
2. 对偶问题可行性：${\alpha }_i\ge 0$, ${\mu }_i\ge 0$ (已经通过 $0\le {\alpha }_i\le C$ 体现)
3. 梯度为零：$w=\sum {\alpha }_i{y}_i{x}_i$, $\sum {\alpha }_i{y}_i=0$, $C-{\alpha }_i-{\mu }_i=0$
4. 互补松弛条件 (Complementary Slackness)：
   • ${\alpha }_i[y_i(w^T{x}_i+b)-1+{\xi }_i]=0$
   • ${\mu }_i{\xi }_i=0$

从 KKT 条件可以得到重要结论：

• 由 ${\alpha }_i[y_i(w^T{x}_i+b)-1+{\xi }_i]=0$：
  • 如果 ${\alpha }_i>0$，则 $y_i(w^T{x}_i+b)-1+{\xi }_i=0$。这些点是支持向量。
  • 如果 ${\alpha }_i=0$，则该点不是支持向量，对模型没有影响。
• 由 ${\mu }_i{\xi }_i=0$ 和 $C-{\alpha }_i-{\mu }_i=0$：
  • 如果 $0<{\alpha }_i<C$：则 ${\mu }_i>0$，因此 ${\xi }_i=0$。这意味着 $y_i(w^T{x}_i+b)=1$。这些点是严格在间隔边界上的支持向量。
  • 如果 ${\alpha }_i=C$：则 ${\mu }_i=0$ (不一定，也可能 ${\mu }_i>0$ 如果 $C-{\alpha }_i=0$)。这时 ${\xi }_i\ge 0$。
    • 如果 ${\xi }_i<1$，点在间隔内但正确分类。
    • 如果 ${\xi }_i\ge 1$，点被错误分类或在超平面上。
  • 如果 ${\alpha }_i=0$：则 ${\mu }_i=C>0$，所以 ${\xi }_i=0$。这意味着 $y_i(w^T{x}_i+b)\ge 1$。这些点在间隔边界之外，被正确分类。

关键点： 只有支持向量 (对应的 ${\alpha }_i>0$) 才对最终的 $w$ 和 $b$ 有贡献。

3.4. 求解 $w$ 和 $b$

一旦求解出 ${\alpha }_i$，$w$ 可以通过以下公式计算：

$$w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i$$
(实际上，只需要对 ${\alpha }_i>0$ 的支持向量求和)

$b$ 的计算：选择任何一个 ${\alpha }_j$ 满足 $0<{\alpha }_j<C$ 的支持向量 $x_j$ (这些点满足 ${\xi }_j=0$ 且 $y_j(w^T{x}_j+b)=1$)。
那么：
$$y_j(w^T{x}_j+b)=1⟹y_j^2(w^T{x}_j+b)=y_j⟹w^T{x}_j+b=y_j$$
所以：
$$b=y_j-w^T{x}_j=y_j-\sum _{i=1}^N{\alpha }_i{y}_i(x_i^T{x}_j)$$
为了稳健性，通常对所有满足 $0<{\alpha }_j<C$ 的支持向量计算 $b$，然后取平均值。

3.5. 预测

对于新的数据点 $x_{t}est$，预测其类别：
$$y_{pred}=\text{sign}(w^T{x}_{test}+b)=\text{sign}\left(\sum _{i=1}^N{\alpha }_i{y}_i(x_i^T{x}_{test})+b\right)$$
注意，求和只需要对支持向量进行。

4. 核技巧 (Kernel Trick)

对于非线性可分的数据，线性SVM表现不佳。核技巧是一种聪明的方法，可以在不显式地将数据映射到高维空间的情况下，在高维空间中执行线性SVM。

4.1. 非线性映射

基本思想：将原始特征空间中的数据 $x$ 通过一个非线性映射函数 $\varphi (x)$ 映射到一个更高维（甚至无限维）的特征空间 $\mathcal{H}$，使得数据在 $\mathcal{H}$ 中变得线性可分（或近似线性可分）。

例如，原始数据 $x=(x_1,x_2)$，映射函数 $\varphi (x)=(x_1^2,x_2^2,\sqrt{2}{x}_1{x}_2)$。

在新的特征空间中，SVM的对偶问题变为：
$$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(\varphi (x_i{)}^T\varphi (x_j))\\ \text{subject to}& \sum _{i=1}^N{\alpha }_i{y}_i=0\\ & 0\le {\alpha }_i\le C,\forall i=1,...,N\end{array}$$
预测函数变为：
$$y_{pred}=\text{sign}\left(\sum _{i=1}^N{\alpha }_i{y}_i(\varphi (x_i{)}^T\varphi (x_{test}))+b\right)$$

问题： $\varphi (x)$ 可能维度非常高，甚至无限维，直接计算 $\varphi (x)$ 和 $\varphi (x_i{)}^T\varphi (x_j)$ 可能非常困难或不可能。

4.2. 核函数 (Kernel Function)

核技巧的关键在于，我们发现对偶问题和预测函数中，$\varphi (x)$ 总是以内积 $\varphi (x_i{)}^T\varphi (x_j)$ 的形式出现。
如果我们能找到一个核函数 $K(x_i,x_j)$，使得：

$$K(x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$$

那么我们就不需要显式地计算 $\varphi (x)$，只需要计算 $K(x_i,x_j)$ 即可。这大大简化了计算。

4.3. 常用的核函数

1. 线性核 (Linear Kernel)：
   $$K(x_i,x_j)=x_i^T{x}_j$$
   这对应于原始的线性SVM，$\varphi (x)=x$。

2. 多项式核 (Polynomial Kernel)：
   $$K(x_i,x_j)=(x_i^T{x}_j+c{)}^d$$
   其中 $d$ 是多项式的次数，$c$ 是常数。它将数据映射到 $\left(\genfrac{}{}{0ex}{}{n+d}{d}\right)$ 维空间（近似）。

3. 高斯核 / 径向基函数核 (Gaussian Kernel / RBF Kernel)：
   $$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)=\exp (-\gamma \Vert x_i-x_j{\Vert }^2)$$
   其中 $\sigma$ (或 $\gamma =1/(2{\sigma }^2)$)是核的宽度参数。这是最常用的核函数之一，它可以将数据映射到无限维空间。它能够处理复杂的非线性关系。

   • $\gamma$ 越大，高斯分布越窄，模型越倾向于只关注近邻点，容易过拟合。
   • $\gamma$ 越小，高斯分布越宽，模型越平滑，容易欠拟合。

4. Sigmoid 核 (Sigmoid Kernel)：
   $$K(x_i,x_j)=\tanh (\kappa x_i^T{x}_j+\theta )$$
   其中 $\kappa$ 和 $\theta$ 是参数。在某些情况下，它的表现类似两层神经网络。

Mercer 定理：一个对称函数 $K(x_i,x_j)$ 可以作为核函数的充要条件是，对于任意数据集 $x_1,...,x_m$，其对应的核矩阵 $K$ (其中 $K_{ij}=K(x_i,x_j)$) 是半正定的。

4.4. 使用核函数的SVM

将对偶问题中的内积 $x_i^T{x}_j$ 替换为核函数 $K(x_i,x_j)$：
$$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)\\ \text{subject to}& \sum _{i=1}^N{\alpha }_i{y}_i=0\\ & 0\le {\alpha }_i\le C,\forall i=1,...,N\end{array}$$
预测函数变为：
$$y_{pred}=\text{sign}\left(\sum _{i\in SV}{\alpha }_i{y}_{i}K(x_i,x_{test})+b\right)$$
其中 $SV$ 表示支持向量的集合。
$b$ 的计算也类似，选择 $0<{\alpha }_j<C$ 的支持向量 $x_j$：
$$b=y_j-\sum _{i\in SV}{\alpha }_i{y}_{i}K(x_i,x_j)$$

5. SMO 算法 (Sequential Minimal Optimization)

求解上述带核函数的对偶问题仍然是一个二次规划问题。当训练样本数量很大时，通用的QP求解器效率不高。
SMO 算法是一种高效的求解 SVM 对偶问题的方法。
其核心思想是：

1. 每次迭代选择两个拉格朗日乘子 ${\alpha }_i$ 和 ${\alpha }_j$ 进行优化。
2. 固定其他所有 ${\alpha }_k$ ($k\ne i,j$)。
3. 由于约束 $\sum {\alpha }_k{y}_k=0$，${\alpha }_i$ 和 ${\alpha }_j$ 之间存在线性关系，可以将问题简化为单变量优化问题。
4. 解析地求解这两个变量，并根据约束 $0\le {\alpha }_k\le C$ 进行裁剪。
5. 重复此过程，直到收敛。

SMO 算法通过启发式方法选择要优化的 ${\alpha }_i$ 和 ${\alpha }_j$，以加速收敛。

6. SVM 的优缺点

优点：

1. 高维空间表现好：即使特征维度高于样本数量，SVM 仍然有效。
2. 内存高效：决策函数只依赖于支持向量，而不是所有训练数据。
3. 通用性：通过不同的核函数，可以解决各种线性和非线性问题。
4. 间隔最大化：理论上具有较好的泛化能力。
5. 鲁棒性：对于非支持向量的噪声不敏感（软间隔一定程度上缓解了对支持向量附近噪声的敏感性）。

缺点：

1. 计算复杂度高：当样本数量非常大时，训练时间较长 (尤其是在使用核函数时，需要计算 $NxN$ 的核矩阵)。
2. 对参数和核函数的选择敏感：$C$、核函数类型、核函数参数 ($\gamma$, $d$ 等) 的选择对性能影响很大，通常需要交叉验证来调优。
3. 不直接提供概率估计：SVM 的原始输出是类别标签，而不是概率。虽然可以通过 Platt Scaling 等方法进行校准，但不是其原生特性。
4. 对缺失数据敏感。
5. “黑盒”模型：解释性不如决策树等模型。

7. SVM 应用场景

• 文本分类 (如垃圾邮件检测)
• 图像分类
• 生物信息学 (如基因分类)
• 手写数字识别
• 人脸检测

总结

SVM 是一种强大的分类算法，其核心在于最大化类别间的间隔。通过引入软间隔和核技巧，SVM 能够处理线性不可分和复杂非线性问题。虽然参数选择和计算效率可能是一些挑战，但其优秀的泛化能力和在高维空间中的有效性使其成为机器学习工具箱中的重要一员。