𝑷𝒂𝒊𝒂𝒅

外观

支持向量机

约 1002 字大约 3 分钟

2025-02-28

步骤分析

  1. Step1：分类问题概述
    支持向量机是一种监督学习方法，用于分类或回归任务（主要用于分类）。其目标是找到一个最优超平面，将不同类别的样本分隔开，同时最大化类别之间的间隔（margin）。SVM 通过平衡分类准确性和泛化能力，特别适用于高维数据和非线性可分问题。

  2. Step2：SVM 模型

    • 数据集：X={x1,x2,…,xn}X = \{x_1, x_2, \dots, x_n\}，其中 xi∈Rdx_i \in \mathbb{R}^d 是 dd 维特征向量，yi∈{−1,1}y_i \in \{-1, 1\} 是对应的二分类标签。
    • 超平面：定义为 wTx+b=0w^T x + b = 0，其中 ww 是法向量，bb 是偏置。
    • 支持向量：距离超平面最近的样本点，满足 wTxi+b=±1w^T x_i + b = \pm 1。
    • 间隔（Margin）：两类支持向量之间的距离，计算为 2∥w∥\frac{2}{\|w\|}，其中 ∥w∥=wTw\|w\| = \sqrt{w^T w}。
    • 目标函数：最大化间隔，即最小化 12∥w∥2\frac{1}{2}\|w\|^2，同时满足约束：

      yi(wTxi+b)≥1,i=1,2,…,ny_i (w^T x_i + b) \geq 1, \quad i = 1, 2, \dots, n

    • 优化问题（硬间隔 SVM）：

      min⁡w,b12∥w∥2s.t.yi(wTxi+b)≥1\min_{w, b} \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i (w^T x_i + b) \geq 1

      解释：12∥w∥2\frac{1}{2}\|w\|^2 控制超平面复杂度，约束确保所有样本被正确分类且在间隔外。

  3. Step3：算法流程
    SVM 通过求解优化问题找到最优超平面，主要步骤如下：

    步骤 1：拉格朗日对偶问题
    为解决带约束优化，引入拉格朗日乘子 αi≥0\alpha_i \geq 0，构造拉格朗日函数：

    L(w,b,α)=12∥w∥2−∑i=1nαi[yi(wTxi+b)−1]L(w, b, \alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^n \alpha_i [y_i (w^T x_i + b) - 1]

    对 ww 和 bb 求偏导并令其为零：

    w=∑i=1nαiyixi,∑i=1nαiyi=0w = \sum_{i=1}^n \alpha_i y_i x_i, \quad \sum_{i=1}^n \alpha_i y_i = 0

    代入后转化为对偶问题：

    max⁡α∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxiTxj\max_{\alpha} \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

    约束：αi≥0\alpha_i \geq 0 且 ∑i=1nαiyi=0\sum_{i=1}^n \alpha_i y_i = 0。

    步骤 2：求解 α\alpha

    使用数值优化方法（如 SMO 算法）求解对偶问题，得到最优 αi∗\alpha_i^*。
    其中，αi∗>0\alpha_i^* > 0 的样本为支持向量。

    步骤 3：计算 ww 和 bb

    根据支持向量计算：

    w∗=∑i=1nαi∗yixiw^* = \sum_{i=1}^n \alpha_i^* y_i x_i

    选择一个支持向量 (xs,ys)(x_s, y_s)（满足 αs∗>0\alpha_s^* > 0），计算偏置：

    b∗=ys−w∗Txsb^* = y_s - w^{*T} x_s

    步骤 4：预测
    对新样本 xx，预测类别为：

    f(x)=sign(w∗Tx+b∗)f(x) = \text{sign}(w^{*T} x + b^*)

  4. Step4：软间隔与核技巧

    • 软间隔 SVM（处理线性不可分）：
      引入松弛变量 ξi≥0\xi_i \geq 0 和惩罚参数 CC，优化目标变为：

      min⁡w,b,ξ12∥w∥2+C∑i=1nξi\min_{w, b, \xi} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^n \xi_i

      约束：yi(wTxi+b)≥1−ξi,ξi≥0y_i (w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0。
      对偶问题修改为：

      max⁡α∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxiTxj\max_{\alpha} \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

      约束：0≤αi≤C0 \leq \alpha_i \leq C 且 ∑i=1nαiyi=0\sum_{i=1}^n \alpha_i y_i = 0。
    • 核技巧（处理非线性）：
      将数据映射到高维空间，用核函数 K(xi,xj)K(x_i, x_j) 替代 xiTxjx_i^T x_j：
      对偶问题变为：

      max⁡α∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjK(xi,xj)\max_{\alpha} \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)

      常用核函数： - 线性核：K(xi,xj)=xiTxjK(x_i, x_j) = x_i^T x_j - 多项式核：K(xi,xj)=(xiTxj+1)pK(x_i, x_j) = (x_i^T x_j + 1)^p - 高斯核（RBF）：K(xi,xj)=exp⁡(−γ∥xi−xj∥2)K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)

      解释：软间隔允许一定误分类，核技巧使 SVM 适用于非线性数据。

  5. Step5：优化与评估

    • 参数优化：
      • CC：控制间隔大小与误分类的权衡，CC 越大越强调正确分类。
      • 核参数（如 RBF 的 γ\gamma）：影响模型复杂度，需调优。
    • 评估方法： - 准确率：正确分类的样本比例。 - 混淆矩阵：分析各类别预测效果。 - ROC 和 AUC：评估二分类性能。 - 交叉验证：如 5 折交叉验证，评估泛化能力。

      提示

      SVM 对特征缩放敏感，建议标准化数据；高维数据计算复杂度较高。
      Tips：SVM 实现 可参考 scikit-learn 的 SVC。 :::