SVM（支持向量机）

1. 概述

支持向量机（Support Vector Machine, SVM）是一种经典的二分类模型，其核心思想是在特征空间中寻找最大间隔的分离超平面。SVM因其优秀的泛化能力和坚实的理论基础，在机器学习发展历程中占据重要地位。

1.1 关键概念

• 超平面：在$n$维空间中，超平面是$n-1$维的线性子空间
• 支持向量：距离超平面最近的样本点，它们决定了超平面的位置
• 间隔（margin）：两个平行超平面之间的距离，SVM的目标是最大化这个间隔

1.2 几何直观

        ·                                    ·
    ·        ·                          ·
        ·            ══════════              ·
    ·                    │              ·
        ·                │ (间隔)         ·
    ·        ·           │           ·
        ·                │              ·
    ·        ·            ══════════       ·
        ·                                    ·

如图所示，实线为最优超平面，虚线为穿过支持向量的平行超平面，SVM最大化两个虚线之间的距离。

2. 硬间隔SVM

2.1 问题建模

给定训练数据集：

$$T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$$

其中 $x_i\in {\mathbb{R}}^n$，$y_i\in \{-1,+1\}$。

假设超平面为：

$$w\cdot x+b=0$$

其中 $w$ 是法向量，$b$ 是偏置。

几何间隔定义为：

$${\gamma }_i=y_i\left(\frac{w}{\Vert w\Vert }\cdot x_i+\frac{b}{\Vert w\Vert }\right)$$

2.2 优化目标

硬间隔SVM的优化问题为：

$$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}\Vert w{\Vert }^2\\ \text{s.t.}& y_i(w\cdot x_i+b)\ge 1,i=1,2,\dots ,N\end{array}$$

这是一个凸二次规划问题，存在唯一全局最优解。

2.3 对偶问题

使用拉格朗日乘子法，引入拉格朗日乘子 ${\alpha }_i\ge 0$：

$$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^N{\alpha }_i{y}_i(w\cdot x_i+b)+\sum _{i=1}^N{\alpha }_i$$

对 $w$ 和 $b$ 求偏导并令其为0：

$$\begin{array}{rl}\frac{\partial L}{\partial w}& =0\Rightarrow w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i\\ \frac{\partial L}{\partial b}& =0\Rightarrow \sum _{i=1}^N{\alpha }_i{y}_i=0\end{array}$$

代入原式，得到对偶问题：

$$\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\cdot x_j)\\ \text{s.t.}& \sum _{i=1}^N{\alpha }_i{y}_i=0\\ & {\alpha }_i\ge 0,i=1,2,\dots ,N\end{array}$$

2.4 KKT条件

SVM的解满足KKT条件：

$$\{\begin{array}{l}{\alpha }_i\ge 0\\ y_i(w\cdot x_i+b)-1\ge 0\\ {\alpha }_i(y_i(w\cdot x_i+b)-1)=0\end{array}$$

这意味着：

• 当 ${\alpha }_i=0$ 时，样本不是支持向量
• 当 ${\alpha }_i>0$ 时，$y_i(w\cdot x_i+b)=1$，样本是支持向量

3. 软间隔SVM

3.1 引入松弛变量

硬间隔要求样本线性可分，这在实际中往往不成立。引入松弛变量 ${\xi }_i\ge 0$：

$$\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\cdot x_i+b)\ge 1-{\xi }_i\\ & {\xi }_i\ge 0,i=1,2,\dots ,N\end{array}$$

其中 $C>0$ 是惩罚参数，控制对误分类样本的惩罚程度。

• $C$ 越大，对误分类的惩罚越大，可能导致过拟合
• $C$ 越小，允许更多的误分类，决策边界更平滑

3.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(x_i\cdot x_j)\\ \text{s.t.}& \sum _{i=1}^N{\alpha }_i{y}_i=0\\ & 0\le {\alpha }_i\le C,i=1,2,\dots ,N\end{array}$$

与硬间隔相比，多了 ${\alpha }_i\le C$ 的约束。

4. 核函数

4.1 核技巧

当数据非线性可分时，可以通过**核技巧（Kernel Trick）**将样本映射到高维特征空间，在高维空间中寻找线性超平面。

设 $\varphi (x)$ 是将 $x$ 映射到特征空间的函数，则对偶问题中的内积 $x_i\cdot x_j$ 变为 $\varphi (x_i)\cdot \varphi (x_j)$。

核函数定义为：

$$K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$$

4.2 常用核函数

核函数	表达式	参数
线性核	$K(x_i,x_j)=x_i\cdot x_j$	无
多项式核	$K(x_i,x_j)=(x_i\cdot x_j+1{)}^d$	$d$: 度
高斯核（RBF）	$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$	$\sigma$: 带宽
拉普拉斯核	$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j\Vert }{\sigma }\right)$	$\sigma$: 带宽
Sigmoid核	$K(x_i,x_j)=\tanh (\beta x_i\cdot x_j+\gamma )$	$\beta ,\gamma$

4.3 核函数选择

实践中，**高斯核（RBF）**是最常用的选择，因为：

• 参数量少（只有一个参数 $\sigma$）
• 具有无限的拟合能力
• 对称正定

5. SMO算法

5.1 算法思想

序列最小优化（Sequential Minimal Optimization, SMO）是最常用的SVM训练算法。其核心思想是每次只优化两个拉格朗日乘子 ${\alpha }_i$ 和 ${\alpha }_j$，将大的优化问题分解为小的子问题。

5.2 选变量策略

1. 外层循环：优先选择违反KKT条件最严重的样本
2. 内层循环：选择使目标函数下降最大的第二个变量

5.3 更新公式

假设选择 ${\alpha }_1$ 和 ${\alpha }_2$ 进行优化，约束为：

$${\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^N{\alpha }_i{y}_i=\zeta$$

则 ${\alpha }_2$ 的更新为：

$${\alpha }_2^{new}={\alpha }_2^{old}+\frac{y_2(E_1-E_2)}{\eta }$$

其中：

• $E_i=f(x_i)-y_i$ 为预测误差
• $\eta =K_{11}+K_{22}-2K_{12}$ 为二阶导数

6. 多分类SVM

6.1 一对多（OvR）

训练 $K$ 个二分类器，第 $k$ 个分类器将第 $k$ 类样本作为正类，其余作为负类。预测时，选择分类器输出值最大的类别。

优点：分类器数量少（$K$个）
缺点：存在类别不平衡问题

6.2 一对一（OvO）

训练 $\frac{K(K-1)}{2}$ 个二分类器，每两个类别之间训练一个分类器。预测时使用投票策略。

优点：每个分类器只用到对应两类的样本
缺点：分类器数量多

7. 代码实现

7.1 线性SVM

import numpy as np
from sklearn.svm import SVC
 
class LinearSVM:
    def __init__(self, C=1.0, learning_rate=0.001, n_iters=1000):
        self.C = C
        self.lr = learning_rate
        self.n_iters = n_iters
        self.w = None
        self.b = None
    
    def fit(self, X, y):
        n_samples, n_features = X.shape
        y_ = np.where(y <= 0, -1, 1)
        
        # 初始化权重
        self.w = np.zeros(n_features)
        self.b = 0
        
        for _ in range(self.n_iters):
            for idx, x_i in enumerate(X):
                condition = y_[idx] * (np.dot(x_i, self.w) + self.b)
                
                # 硬间隔SVM更新（可修改为软间隔）
                if condition >= 1:
                    self.w -= self.lr * (2 * self.C * self.w)
                else:
                    self.w -= self.lr * (2 * self.C * self.w - np.dot(x_i, y_[idx]))
                    self.b -= self.lr * y_[idx]
    
    def predict(self, X):
        return np.sign(np.dot(X, self.w) + self.b)

7.2 使用sklearn

from sklearn.svm import SVC
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
 
# 生成数据
X, y = make_classification(n_samples=1000, n_features=20, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
 
# 训练SVM
svm = SVC(kernel='rbf', C=1.0, gamma='scale')
svm.fit(X_train, y_train)
 
# 预测
y_pred = svm.predict(X_test)
print(f"Accuracy: {accuracy_score(y_test, y_pred):.4f}")
 
# 获取支持向量
print(f"Number of support vectors: {len(svm.support_vectors_)}")

8. 与其他模型的关系

8.1 SVM与感知机

感知机只要求找到一个将正负类分开的超平面，不考虑间隔大小。SVM在此基础上增加了最大间隔约束，因此泛化能力更强。

8.2 SVM与逻辑回归

当使用对数损失函数时，软间隔SVM与L2正则化的逻辑回归非常相似。两者都是通过最大化间隔来进行分类。

8.3 SVM与神经网络的联系

SVM的核函数可以被视为一种固定特征变换，而神经网络通过学习可以自适应地学习特征变换。在某种意义上，核SVM可以看作”一层”的神经网络。

9. 优缺点

优点

• 理论基础扎实：基于结构风险最小化原则
• 泛化能力强：最大间隔原则减少过拟合风险
• 核技巧：可以处理非线性问题
• 稀疏性：只有支持向量决定决策边界，存储和预测效率高

缺点

• 大规模数据下训练困难：时间复杂度介于 $O(N^2)$ 和 $O(N^3)$ 之间
• 核函数选择敏感：需要仔细选择核函数和参数
• 对特征缩放敏感：需要标准化输入特征
• 不适合多分类：需要额外策略

10. 应用场景

SVM在以下场景中表现优秀：

1. 文本分类：特别是高维稀疏数据
2. 图像分类：配合HOG等特征
3. 生物信息学：蛋白质结构预测
4. 异常检测：支持向量数据描述（SVDD）

参考资料