SVM

Support Vector Machine.

1. 线性SVM分类原理

线性SVM分类的核心思想是找到一个超平面，将不同类别的数据点分隔开，并且尽量使得分类边界到支持向量的距离最大。线性SVM适用于数据线性可分的场景。

• 超平面：假设我们有一组二维数据，SVM的目标是找到一条直线来分割这组数据。在高维空间中，这条直线就是超平面，定义为：

  \[ w \cdot x + b = 0 \]

  其中，\(w\) 是超平面的法向量，\(x\) 是输入数据，\(b\) 是偏置。

• 分类边界：为了实现分类，SVM希望找到一个能最大化分类边界的超平面。理想情况下，不同类别的数据点位于超平面两侧，即：

  • \(w \cdot x_i + b \geq 1\) 对于正类样本
  • \(w \cdot x_i + b \leq -1\) 对于负类样本

• 边距最大化：SVM通过优化问题来最大化支持向量到超平面的边距，保证模型的泛化能力。优化问题为：

  \[ \min \frac{1}{2} \|w\|^2 \]

  同时满足约束条件： \[ y_i(w \cdot x_i + b) \geq 1 \quad \forall i \]

其中，\(y_i\) 是数据点 \(x_i\) 的类别标签（+1或-1），通过求解该优化问题得到的超平面能够最大化分类边界。

2. 带松弛变量的SVM

在实际问题中，数据通常是线性不可分的，可能会存在一些误分类的数据点。为了应对这种情况，SVM引入了松弛变量（slack variable）来允许一定程度的误分类，从而处理非线性可分的数据。

• 松弛变量 \(\xi_i\)：SVM通过引入松弛变量 \(\xi_i \geq 0\) 来度量误分类样本的程度。对于每个数据点，松弛变量允许分类边界与样本之间有一定误差。

  约束条件变为： \[ y_i(w \cdot x_i + b) \geq 1 - \xi_i \quad \forall i \]

  这样，SVM能够处理非线性可分的数据，同时通过优化问题最小化误分类。

• 目标函数：SVM的目标是同时最小化分类误差和边距。带松弛变量的SVM的优化问题为： \[ \min \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n \xi_i \]

  其中，\(C\) 是惩罚参数，用来控制误分类样本的惩罚程度。较大的 \(C\) 值会导致模型对误分类更敏感。

3. 对偶问题

对偶问题是优化问题的一种变换形式，通过将原始的优化问题（主问题）转化为对偶形式，简化计算。SVM的对偶问题引入拉格朗日乘子，用于将原问题转化为约束优化问题。

拉格朗日函数 \(L(w, b, \alpha)\) 定义为：

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

其中，\(\alpha_i \geq 0\) 是对应于每个约束条件的拉格朗日乘子。为了最小化拉格朗日函数 \(L(w, b, \alpha)\)，我们需要对 \(w\) 和 \(b\) 进行最优化。首先分别对 \(w\) 和 \(b\) 求偏导并令其等于0。

对 \(w\) 求导：

\[ \frac{\partial L(w, b, \alpha)}{\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 \]

这表明 \(w\) 是所有支持向量（即 \(\alpha_i > 0\) 的数据点）的线性组合。

对 \(b\) 求导：

\[ \frac{\partial L(w, b, \alpha)}{\partial b} = - \sum_{i=1}^{n} \alpha_i y_i = 0 \]

因此有：

\[ \sum_{i=1}^{n} \alpha_i y_i = 0 \]

这表明支持向量的权重满足该等式。

将 \(w = \sum_{i=1}^{n} \alpha_i y_i x_i\) 代入拉格朗日函数 \(L(w, b, \alpha)\)，消去 \(w\) 和 \(b\)，我们得到新的目标函数：

\[ L(\alpha) = \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{n} \alpha_i \]

注意，此时我们将优化变量从 \(w\) 和 \(b\) 转化为了 \(\alpha_i\)。

对偶问题的目标是最大化拉格朗日函数 \(L(\alpha)\)，即：

\[ \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 \cdot x_j) \]

同时满足以下约束条件：

\[ \sum_{i=1}^{n} \alpha_i y_i = 0, \quad 0 \leq \alpha_i \leq C \]

其中 \(C\) 是控制松弛变量的参数，在引入松弛变量时会用到。

通过求解对偶问题，我们可以获得拉格朗日乘子 \(\alpha_i\)。这些乘子对应的 \(\alpha_i > 0\) 的样本就是支持向量，这些支持向量决定了最终的分类超平面。

4. 核化SVM模型

核化SVM用于处理线性不可分的数据。通过核函数将数据从低维映射到高维空间，使得在高维空间中数据变得线性可分。

核函数 \(K(x_i, x_j)\) 用来计算两个样本点在映射到高维空间后的内积。常见的核函数有：

• 线性核（Linear Kernel
  • 公式：\(K(x_i, x_j) = x_i \cdot x_j\)
  • 适用于线性可分的数据。
• 多项式核（Polynomial Kernel
  • 公式：\(K(x_i, x_j) = (x_i \cdot x_j + 1)^d\)
  • 其中，\(d\) 是多项式的阶数。多项式核适用于处理非线性数据。
• 径向基函数核（Radial Basis Function, RBF Kernel）
  • 公式：\(K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)\)
  • \(\gamma\) 是参数，控制高斯函数的宽度。RBF核用于处理局部模式的非线性数据，是SVM中常用的核函数。
• Sigmoid核（Sigmoid Kernel）
  • 公式：\(K(x_i, x_j) = \tanh(\kappa x_i \cdot x_j + \theta)\)
  • Sigmoid核类似于神经网络中的激活函数，适用于一些特殊的非线性数据。

5. SMO序列最小优化算法

SMO（Sequential Minimal Optimization）是解决SVM对偶问题的高效算法，能够快速训练SVM模型。SMO通过将优化问题分解为一系列的二次子问题，并分别对两个拉格朗日乘子进行优化。

基本步骤：

1. 选择两个拉格朗日乘子：每次选择两个乘子 \(\alpha_1\) 和 \(\alpha_2\) 进行优化。
2. 优化这两个乘子：将其他乘子固定，对 \(\alpha_1\) 和 \(\alpha_2\) 进行优化更新。
3. 更新模型参数：根据更新后的 \(\alpha_1\) 和 \(\alpha_2\) 计算新的超平面参数 \(w\) 和 \(b\)。
4. 重复迭代：不断重复以上步骤，直到达到收敛条件。

SMO算法的优点在于它避免了计算整个核矩阵，显著提高了大规模数据集上SVM的训练速度。

6. SVR

SVM回归（SVR）通过寻找一个函数来预测连续变量，主要用于回归分析。与SVM分类类似，SVR通过控制误差边界来最小化预测误差。

• ε-不敏感损失函数：SVR允许在误差范围内的预测值被忽略，使用不敏感损失函数控制误差。
• 目标函数：SVR的目标是最小化函数复杂度和预测误差，优化问题为： \[ \min \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n (\xi_i + \xi_i^*) \] 其中，\(\xi_i\) 和 \(\xi_i^*\) 是松弛变量，表示上下边界的误差，\(ε\) 控制误差的范围。