机器学习复习之支持向量机SVM

[toc]

一、线性SVM

1. 核心原理

假定有一个二分类数据集 $D={X_i, Y_i}_{i=1}^N$ ，线性是一种用于线性可分数据的分类算法，其核心思想是找到一个最优的线性决策边界（超平面），能够最大程度地将不同类别的样本分开。

  • 超平面：$w^Tx+b=0$ ，其中 $w$ 为法向量，该公式可以由法向量正交于该超平面推导得出。

  • 点 $x_i$ 到超平面的距离
    $$
    d = \frac{|w^Tx_i+b|}{||w||}
    $$

  • 线性可分性：若存在 $w$ 和 $b$，使得
    $$
    \begin{aligned}
    &w^Tx_i+b>0,\text{if}\ y_i = +1 \

    &w^Tx_i+b < 0, \text{if}\ y_i = -1 \
    \rightarrow \quad&y_i(w^Tx_i+b)>0
    \end{aligned}
    $$

  • 间隔Margin: 是指超平面到最近数据点的距离

所以linear SVM的决定函数为
$$
f(x)= Sign(w^Tx+b)
$$
优化方法为最大化间隔法
$$
\begin{aligned}
\max_{w,b}\quad&\frac{1}{||w||}\min|w^Tx_i+b|\ \
\text{s.t.}\quad &y_i(w^Tx_i+b)>0 \ \text{for all} \ i=1,2,\dots,N
\end{aligned}
$$

2. 优化问题

可以看出$|w^Tx_i+b|= y_i(w^Tx_i+b)$ ，并且同时放大缩小 $w$ 和 $b$不影响margin的大小，我们可以取 $\min\ y_i(w^Tx_i+b) = 1$

原式就会变成：
$$
\begin{aligned}
&\max_{w,b} \quad\frac{1}{||w||}\ \text{s.t.} \quad y_i(w^Tx_i+b)\geq 1 \ \text{for all} \ i=1,2,\dots,N \
= &\min_{w,b}\quad \frac{||w||^2}{2}\ \text{s.t.}\quad y_i(w^Tx_i+b)\geq 1 \ \text{for all} \ i=1,2,\dots,N
\end{aligned}
$$

3. 拉格朗日乘数法与KKT条件

3.1 等式约束优化问题

考虑等式约束优化问题：
$$
\begin{aligned}
\min_{x} \quad & f(x) \
\text{s.t.} \quad & h_i(x) = 0, \quad i = 1, \ldots, m
\end{aligned}
$$

拉格朗日函数：
$$
\mathcal{L}(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i h_i(x)
$$

其中 $\lambda_i$ 为拉格朗日乘子。

在局部最优解 $x^*$ 处，存在乘子 $\lambda^*$ 使得：
$$
\begin{aligned}
\nabla_x \mathcal{L}(x^*, \lambda^*) &= 0 \
\nabla_\lambda \mathcal{L}(x^*, \lambda^*) &= 0
\end{aligned}
$$

即：
$$
\begin{aligned}
&\nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla h_i(x^*) = 0 \
&h_i(x^*) = 0, \quad i = 1, \ldots, m
\end{aligned}
$$

几何解释：

在最优解处，目标函数的梯度与约束函数的梯度共线：
$$
\nabla f(x^*) = -\sum_{i=1}^m \lambda_i^* \nabla h_i(x^*)
$$

3.2 KKT条件（不等式约束）

考虑不等式约束优化问题：
$$
\begin{aligned}
\min_{x} \quad & f(x) \
\text{s.t.} \quad & g_i(x) \leq 0, \quad i = 1, \ldots, p \
& h_j(x) = 0, \quad j = 1, \ldots, q
\end{aligned}
$$

拉格朗日函数：
$$
\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i=1}^p \lambda_i g_i(x) + \sum_{j=1}^q \mu_j h_j(x)
$$

其中 $\lambda_i \geq 0$ 为不等式约束乘子，$\mu_j$ 为等式约束乘子。

在满足某些约束规格（如Slater条件）下，局部最优解 $x^*$ 处存在乘子 $\lambda^* \geq 0$, $\mu^*$ 使得：

(1) 平稳性条件（Stationarity）
$$
\nabla f(x^*) + \sum_{i=1}^p \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^q \mu_j^* \nabla h_j(x^*) = 0
$$

(2) 原始可行性条件（Primal Feasibility）
$$
\begin{aligned}
g_i(x^*) &\leq 0, \quad i = 1, \ldots, p \
h_j(x^*) &= 0, \quad j = 1, \ldots, q
\end{aligned}
$$

(3) 对偶可行性条件（Dual Feasibility）
$$
\lambda_i^* \geq 0, \quad i = 1, \ldots, p
$$

(4) 互补松弛条件（Complementary Slackness）
$$
\lambda_i^* g_i(x^*) = 0, \quad i = 1, \ldots, p
$$

$g_i(x) \leq 0$ 时，有两种情况

  • $g_i(x) < 0, \text{那么约束条件时松弛的}，\lambda^*_i = 0$
  • $g_i(x) = 0, 那么就是等式约束$

4. 求解线性SVM优化问题

4.1 SVM的原始问题

$$
\begin{aligned}
\min_{w,b,\xi} \quad & \frac{1}{2}|w|^2 \
\text{s.t.} \quad & y_i(w^T x_i + b) \geq 1 , \quad i = 1, \ldots, n \
\end{aligned}
$$

4.2 拉格朗日函数

$$
\mathcal{L}(w,b,\alpha) = \frac{1}{2}|w|^2 - \sum_{i=1}^n \alpha_i[y_i(w^T x_i + b) - 1]
$$

4.3 KKT条件

平稳性条件：
$$
\begin{aligned}
\frac{\partial \mathcal{L}}{\partial w} &= w - \sum_{i=1}^n \alpha_i y_i x_i = 0 \
\frac{\partial \mathcal{L}}{\partial b} &= -\sum_{i=1}^n \alpha_i y_i = 0 \
\end{aligned}
$$

原始可行性：
$$
\begin{aligned}
y_i(w^T x_i + b) &\geq 1\
\end{aligned}
$$

对偶可行性：
$$
\alpha_i \geq 0
$$

互补松弛性：
$$
\begin{aligned}
\alpha_i[y_i(w^T x_i + b) - 1] &= 0 \
\end{aligned}
$$

要求解这个问题，要把原问题转化成对偶问题，对偶函数定义为原始变量最小化拉格朗日函数：
$$
\theta(\alpha) = \min_{w,b} \mathcal{L}(w,b,\alpha)
$$

第一项：
$$
\frac{1}{2}|w|^2 = \frac{1}{2} \left|\sum_{i=1}^n \alpha_i y_i x_i\right|^2 = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x_i^T x_j
$$

第二项：
$$
-\sum_{i=1}^n \alpha_i[y_i(w^T x_i + b) - 1] = -\sum_{i=1}^n \alpha_i y_i w^T x_i - b\sum_{i=1}^n \alpha_i y_i + \sum_{i=1}^n \alpha_i
$$

由于 $\sum_{i=1}^n \alpha_i y_i = 0$，且：
$$
\sum_{i=1}^n \alpha_i y_i w^T x_i = \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x_i^T x_j
$$

合并所有项：
$$
\theta(\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
$$

4.4 最终对偶问题

$$
\begin{aligned}
\max_{\alpha} \quad & \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{s.t.} \quad & \sum_{i=1}^n \alpha_i y_i = 0 \
& 0 \leq \alpha_i, \quad i = 1, \ldots, n
\end{aligned}
$$

4.5 从对偶解 $\alpha_i$ 恢复原始解

  • 权重向量 $w$

$$
w = \sum_{i=1}^n \alpha_i y_i x_i
$$

  • 偏置项 $b$

$$
b = 1 - \sum_{i=1}^n \alpha_i y_i x_i^T x_j
$$

  • 决策函数

$$
f(x) = \text{sign}\left(\sum_{i=1}^n \alpha_i y_i x_i^T x + b\right)
$$

5. 对偶问题的优势

5.1 核技巧应用

对偶问题只依赖内积 $x_i^T x_j$，$x$可替换为 $\Phi(x)$ 核函数就可以处理非线性数据：
$$
\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)
$$

5.2 支持向量识别

最优解中：

  • $\alpha_i = 0$：对应非支持向量

  • $0 < \alpha_i$：对应边界支持向量

二、软间隔（Soft Margin）SVM

1. 硬间隔的局限性

硬间隔SVM假设数据是线性可分的：

实际问题：

  • 现实数据通常有噪声和异常值
  • 数据可能不是完美线性可分的，可能会有交叉
  • 硬间隔容易过拟合噪声，缺少泛化能力

2. 软间隔的直观理解

软间隔允许一些样本违反间隔条件,我们需要引入 $\xi$
$$
y_i(w^T x_i + b) ≥ 1 - ξ_i\ ξ_i ≥ 0
$$
$ξ_i $ 称为”松弛变量”(slack variable)，表示第i个样本的违反程度

$\xi_i = \max[0, 1-y_i(w^Tx_i+b)]$

$ξ_i = 0$: 样本正确分类且在间隔外

$0 < ξ_i < 1$: 样本正确分类但在间隔内

$ξ_i ≥ 1$: 样本被误分类

3. 软间隔SVM的数学形式

3.1 原始优化问题

$$
\begin{aligned}
\min_{w,b,\xi} \quad & \frac{1}{2}|w|^2 + C\sum_{i=1}^n \xi_i \
\text{s.t.} \quad & y_i(w^T x_i + b) \geq 1 - \xi_i, \quad i = 1, \ldots, n \
& \xi_i \geq 0, \quad i = 1, \ldots, n
\end{aligned}
$$

  • $C$: 正则化参数，控制间隔宽度与误分类的权衡，$C$越大，惩罚力度就越大，如果$C = \infty$，那么就是硬间隔问题。
  • $\xi_i$: 松弛变量，度量第i个样本的间隔违反程度

3.2 软间隔的对偶问题

  • 拉格朗日函数

$$
\mathcal{L}(w,b,\xi,\alpha,\beta) = \frac{1}{2}|w|^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 \beta_i \xi_i
$$

  • KKT条件

$$
\frac{\partial L}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}i = 0 \quad \Rightarrow \quad \mathbf{w} = \sum{i=1}^{n} \alpha_i y_i \mathbf{x}_i
$$

这个结果与硬间隔SVM一致，说明最优超平面的法向量仍然是支持向量的线性组合。
$$
\frac{\partial L}{\partial b} = - \sum_{i=1}^{n} \alpha_i y_i = 0 \quad \Rightarrow \quad \sum_{i=1}^{n} \alpha_i y_i = 0
$$
这个约束也与硬间隔SVM一致。
$$
\frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \quad \Rightarrow \quad \alpha_i + \mu_i = C
$$
这是一个新的重要关系式。由于 $\alpha_i \geq 0$ 和 $\mu_i \geq 0$，我们可以得到：
$$
0 \leq \alpha_i \leq C
$$
这个条件收紧了对 (\alpha_i) 的限制。

我们将上面三个求导结果代入拉格朗日函数 (L)，以消去原变量 $\mathbf{w}, b, \boldsymbol{\xi}$ 和 $\boldsymbol{\mu}$。

$$
\begin{aligned}
L(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) &= \frac{1}{2} |\mathbf{w}|^2 + C \sum_{i=1}^{n} \xi_i - \sum_{i=1}^{n} \alpha_i \big[ y_i(\mathbf{w}^T \mathbf{x}i + b) - 1 + \xi_i \big] - \sum{i=1}^{n} \mu_i \xi_i \
&= \frac{1}{2} |\mathbf{w}|^2 - \sum_{i=1}^{n} \alpha_i y_i \mathbf{w}^T \mathbf{x}i - b \sum{i=1}^{n} \alpha_i y_i + \sum_{i=1}^{n} \alpha_i + \sum_{i=1}^{n} \xi_i (C - \alpha_i - \mu_i)
\end{aligned}
$$
代入上式：
$$
\begin{aligned}
L &= \frac{1}{2} \left( \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}i \right)^T \left( \sum{j=1}^{n} \alpha_j y_j \mathbf{x}j \right) - \sum{i=1}^{n} \alpha_i y_i \left( \sum_{j=1}^{n} \alpha_j y_j \mathbf{x}j \right)^T \mathbf{x}i - 0 + \sum{i=1}^{n} \alpha_i + 0 \
&= \frac{1}{2} \sum{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j \mathbf{x}i^T \mathbf{x}j - \sum{i=1}^{n} \sum{j=1}^{n} \alpha_i \alpha_j y_i y_j \mathbf{x}i^T \mathbf{x}j + \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 \mathbf{x}i^T \mathbf{x}j + \sum{i=1}^{n} \alpha_i
\end{aligned}
$$
因此，我们得到了对偶问题，即最大化：
$$
\begin{aligned}
\max{\boldsymbol{\alpha}}& \quad \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 \mathbf{x}_i^T \mathbf{x}j \
\text{s.t.}&\sum{i=1}^{n} \alpha_i y_i = 0 \
& 0 \leq \alpha_i \leq C, \quad i = 1, \dots, n
\end{aligned}
$$
与硬间隔SVM的对偶问题相比，唯一的区别是约束条件 (\alpha_i \geq 0) 变成了 (0 \leq \alpha_i \leq C)。

3.3 KKT互补松弛条件与支持向量

KKT条件中的互补松弛条件为我们提供了关于支持向量的重要信息：
$$
\begin{aligned}
\alpha_i \big[ y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 + \xi_i \big] &= 0 \
\mu_i \xi_i &= 0
\end{aligned}
$$
结合关系式 $\alpha_i + \mu_i = C$，我们可以分析出样本点的类型：

  • $\alpha_i = 0$:

    • 由条件1，这不对约束1产生影响。
    • 此时 $\mu_i = C$，可得 $\xi_i = 0$。
    • 这意味着 $ y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1 $。该样本被正确分类且位于间隔之外，是非支持向量。

  • $0 < \alpha_i < C$:

    • 由条件1，必须有 $y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 + \xi_i = 0$。

    • 此时 $\mu_i = C - \alpha_i > 0$，可得 $\xi_i = 0$。

    • 因此 $y_i(\mathbf{w}^T \mathbf{x}_i + b) = 1$。该样本恰好落在间隔边界上，是标准支持向量。我们可以利用这些样本来计算 $b$：
      $$
      b = y_i - \mathbf{w}^T \mathbf{x}i = y_i - \sum{j=1}^{n} \alpha_j y_j \mathbf{x}_j^T \mathbf{x}_i
      $$

  • $\alpha_i = C$:

    • 由条件1，必须有 $y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 + \xi_i = 0$。
    • 此时 $\mu_i = C - C = 0$，条件2对 $\xi_i$ 没有约束。
    • 因此 (y_i(\mathbf{w}^T \mathbf{x}_i + b) = 1 - \xi_i)。
    • 由于 $\xi_i \geq 0$，所以 $y_i(\mathbf{w}^T \mathbf{x}_i + b) \leq 1$。
      • 如果 $0 \leq \xi_i < 1$，样本位于间隔内部，但在正确的一侧。
      • 如果 $\xi_i \geq 1$，样本被错误分类。
    • 这些样本被称为边界支持向量。

最终，决策函数与硬间隔SVM形式相同：
$$
f(\mathbf{x}) = \text{sign}\left( \mathbf{w}^T \mathbf{x} + b \right) = \text{sign}\left( \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i^T \mathbf{x} + b \right)
$$
其中，只有支持向量（即 $\alpha_i > 0$ 的样本）对求和有贡献。

三、SVM的优缺点

1. 优点

  1. 在高维空间中有效
  • 原理：SVM的核心是寻找最大间隔超平面，其性能依赖于数据点之间的内积（或核函数计算），而不是空间的维度本身。
  • 例子：在文本分类中，特征维度（词汇量）可能高达数万维，但SVM依然能很好地工作。
  1. 特征数大于样本数时仍然有效
  • 适用场景：在生物信息学、基因表达数据分析中，通常有成千上万个基因（特征），但只有几十或几百个样本。
  • 对比：其他算法（如决策树、基于距离的方法）在这种情况下容易过拟合，但SVM通过最大化间隔来控制模型复杂度。
  1. 内存高效（使用支持向量）
  • 实际意义：训练完成后，只需要存储支持向量而不是全部训练数据，对于大规模应用非常节省内存。
  1. versatile（核函数灵活）

常用核函数：

  • 线性核：K(xi, xj) = xiᵀxj（适用于线性可分数据）
  • 多项式核：K(xi, xj) = (γxiᵀxj + r)^d
  • RBF核：K(xi, xj) = exp(-γ||xi - xj||²)（最常用）
  • Sigmoid核：K(xi, xj) = tanh(γxiᵀxj + r)

2. 缺点

  1. 特征数远大于样本数时的过拟合风险
  • 解决方案：
    • 优先选择线性核
    • 增加正则化强度（减小C值）
    • 进行特征选择降维
  1. 概率估计需要额外计算

问题所在

内部实现原理：

  1. 对每个类别进行5折交叉验证
  2. 使用Platt缩放（sigmoid函数）将决策函数值转换为概率
  3. 这个过程相当于训练了多个模型，非常耗时