Lecture Notes on Support Vector Machine

• 语言: 英语
• 格式: .pdf
• 来源: funglee.github.io

摘要

文档系统介绍了支持向量机（SVM）的基本原理和相关理论。首先，定义了超平面及其在分类中的作用，并引入了间隔的概念。接着，讨论了支持向量的概念及其在分类中的重要性。通过拉格朗日乘数法，推导了SVM的对偶问题，并引入核函数以处理非线性分类问题。文档还详细阐述了正则化SVM，允许部分训练样本位于间隔内，通过引入松弛变量和惩罚参数C来平衡分类错误与间隔大小。最后，讨论了SMO算法及其优化过程。

AI总结

# 支持向量机（SVM）学习笔记总结

## 1. 超平面与间隔
- **超平面定义**：在n维空间中，超平面由 $\omega^{T}x + b = 0$ 定义，其中 $\omega$ 是法向量，$b$ 是偏置项。
- **分类依据**：通过 $\operatorname{sign}(\omega^{T}x + b)$ 可以判断点 $x$ 所在的半空间。
- **间隔计算**：点 $x_0$ 到超平面的无符号几何距离为 $\gamma_0 = \frac{y_0(\omega^{T}x_0 + b)}{\|\omega\|}$，其中 $y_0$ 是点的标签（$1$ 或 $-1$）。
- **训练集的间隔**：对于给定的训练集 $\{(x^{(i)}, y^{(i)})\}_{i=1,\ldots,m}$，间隔 $\gamma$ 定义为所有样本间隔的最小值。

---

## 2. 支持向量机（SVM）
- **基本思想**：SVM 通过最大化间隔 $\gamma$ 来选择最佳的超平面，从而提高分类性能。
- **优化目标**：在所有满足约束条件的超平面中，选择使间隔最大的那个。
- 线性可分情况下的优化问题：
$$
\begin{aligned}
&\max_{\gamma, \omega, b} \quad \gamma \\
&\text{s.t.} \quad y^{(i)}(\omega^{T}x^{(i)} + b) \geq \gamma \|\omega\|, \quad \forall i
\end{aligned}
$$
- 通过缩放 $\omega$ 和 $b$，问题可以转化为最小化 $\|\omega\|^2$ 的形式：
$$
\min_{\omega, b} \quad \frac{1}{2}\|\omega\|^2
$$
$$
\text{s.t.} \quad y^{(i)}(\omega^{T}x^{(i)} + b) \geq 1, \quad \forall i
$$
- **对偶问题**：通过拉格朗日对偶，SVM 的对偶形式为：
$$
\max_{\alpha} \quad \sum_{i=1}^{m}\alpha_{i} - \frac{1}{2}\sum_{i,j=1}^{m} y^{(i)}y^{(j)}\alpha_{i}\alpha_{j}K_{ij}
$$
$$
\text{s.t.} \quad \sum_{i=1}^{m} \alpha_{i}y^{(i)} = 0, \quad \alpha_{i} \geq 0
$$

---

## 3. 核化 SVM
- **核方法的基本思想**：通过核函数将数据映射到高维特征空间，使得非线性问题可以线性化。
- **常用核函数**：
- 线性核：$K(x, z) = x^{T}z$
- 多项式核：$K(x, z) = (x^{T}z)^d$
- 高斯核：$K(x, z) = \exp\left(-\frac{\|x - z\|^2}{2\sigma^2}\right)$
- Sigmoid 核：$K(x, z) = \tanh(\alpha x^{T}z + c)$
- **核化 SVM 的优势**：无需显式计算高维特征向量，直接通过核函数计算内积。

---

## 4. 正则化 SVM（软间隔 SVM）
- **问题背景**：当数据线性不可分时，允许部分样本进入间隔区域（即允许一定的误分类）。
- **软间隔引入**：通过引入松弛变量 $\xi_i$，约束条件变为：
$$
y^{(i)}(\omega^{T}x^{(i)} + b) \geq 1 - \xi_i, \quad \xi_i \geq 0
$$
- **优化目标**：最小化 $\frac{1}{2}\|\omega\|^2 + C\sum_{i=1}^{m}\xi_i$，其中 $C$ 是调节参数，控制间隔与分类误差之间的权衡。
- **对偶形式**：通过拉格朗日乘子 $\alpha_i$ 和 $r_i$，对偶问题为：
$$
\max_{\alpha, r} \quad \sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{m} y^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}
$$
$$
\text{s.t.} \quad \sum_{i=1}^{m} \alpha_i y^{(i)} = 0, \quad 0 \leq \alpha_i \leq C
$$

---

## 5. 拉格朗日对偶与求解
- **拉格朗日函数**：通过构造拉格朗日函数，将原问题转换为对偶问题。
- **对偶变量**：$\alpha_i$ 和 $r_i$ 分别对应原问题的不等式约束。
- **最优解的性质**：最优解满足 KKT 条件，包括互补松弛性等。
- **求解方法**：可以通过现成的凸优化求解器（如 CVXOPT、CPLEX 等）求解对偶问题。

---

## 核心观点总结
1. SVM 的核心目标是最大化间隔，从而提高分类性能。
2. 核方法通过核函数将非线性问题转化为线性问题，扩展了 SVM 的应用范围。
3. 软间隔 SVM 允许部分样本进入间隔区域，适用于线性不可分的情况。
4. 对偶形式的引入使得 SVM 的优化问题更加高效，且便于核化的实现。

通过以上内容，可以全面理解 SVM 的基本原理、核化方法以及正则化策略。