Lecture Notes on Support Vector Machine

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

摘要

The lecture notes provide a comprehensive introduction to Support Vector Machines (SVM), focusing on the theoretical foundations and key concepts. The document begins with the definition of a hyperplane and margin in n-dimensional space, explaining how margin is calculated and its significance in classification. It then details the formulation of SVM, including both hard-margin and soft-margin (regularized) SVM. The notes also discuss kernel methods, which enable SVM to handle non-linearly separable data by mapping it into a higher-dimensional feature space. Mercer's conditions for valid kernels are introduced, along with common kernel functions such as linear, polynomial, and Gaussian kernels. The optimization process and dual formulation of SVM are thoroughly explained, including the role of Lagrange multipliers and the Karush-Kuhn-Tucker (KKT) conditions. The notes conclude with practical considerations for implementing SVM, including the selection of kernels and the interpretation of support vectors.

AI总结

以下是文档内容的中文总结，语言简洁明了，重点突出核心观点和关键信息：

---

### 《Lecture Notes on Support Vector Machine》总结

#### 1. 超平面与Margin
- **超平面定义**：在n维空间中，超平面由方程 $\omega^T x + b = 0$ 定义，其中 $\omega$ 是法向量，$b$ 是偏置项。超平面将空间分为两个半空间 $H^+$ 和 $H^-$。
- **Margin定义**：给定数据点 $x_0$，其与超平面的有符号距离为 $d_0 = \frac{\omega^T x_0 + b}{\|\omega\|}$，其 Margin 为 $\gamma_0 = \text{sign}(\omega^T x_0 + b) \cdot \frac{\omega^T x_0 + b}{\|\omega\|}$。
- **训练集Margin**：对于训练集 $\{(x^{(i)}, y^{(i)})\}_{i=1}^m$，Margin 定义为 $\gamma = \min_i \gamma^{(i)}$，其中 $\gamma^{(i)} = y^{(i)} \cdot \frac{\omega^T x^{(i)} + b}{\|\omega\|}$。

#### 2. 支持向量机（SVM）
- **目标**：SVM 通过最大化 Margin $\gamma$ 来求解最佳分离超平面。
- **优化问题**：在可线性分离的情况下，SVM 的对偶问题为：
\[
\max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j=1}^m y^{(i)} y^{(j)} \alpha_i \alpha_j \langle x^{(i)}, x^{(j)} \rangle
\]
约束条件为 $\sum_{i=1}^m y^{(i)} \alpha_i = 0$ 且 $\alpha_i \geq 0$。
- **核函数扩展**：通过引入核函数 $K(x^{(i)}, x^{(j)}) = \phi(x^{(i)})^T \phi(x^{(j)})$，SVM 可以在高维特征空间中构造线性分离器，从而解决非线性问题。

#### 3. 正则化SVM（Soft-Margin SVM）
- **松弛变量**：允许部分训练样本误分类或落入间隔区域，引入松弛变量 $\xi_i$，约束条件变为 $y^{(i)} (\omega^T x^{(i)} + b) \geq 1 - \xi_i$。
- **KKT条件**：对偶问题中，$\alpha_i$ 的解反映了样本的状态：
- 若 $\alpha_i = 0$，样本被正确分类。
- 若 $\alpha_i = C$，样本被误分类。
- 若 $0 < \alpha_i < C$，样本是支持向量。

#### 4. 核函数与高维特征空间
- **核函数作用**：通过映射数据到高维特征空间，SVM 可以在原空间中构造非线性分离器。常用核函数包括线性核、多项式核、RBF 核等。
- **支持向量**：支持向量是Margin边界上的样本，满足 $y^{(i)} (\omega^T x^{(i)} + b) = 1$，对最终分类器的构造起关键作用。

#### 5. 模型求解与参数计算
- **对偶问题求解**：通过求解对偶问题，得到 $\alpha^\ast$，从而计算出 $\omega^\ast$ 和 $b^\ast$。
- **参数计算**：$b^\ast$ 可通过支持向量计算，$b^\ast = \text{平均}(y^{(i)} - \omega^\ast \cdot x^{(i)})$。
- **分类预测**：对于测试样本 $x$，分类结果为 $y = \text{sign}(\omega^\ast \cdot \phi(x) + b^\ast)$。

---

### 核心观点总结
- SVM 的核心是通过最大化 Margin 寻找最佳分离超平面。
- 通过核函数，SVM 可以在高维特征空间中实现非线性分类。
- 支持向量是 SVM 的关键，决定了模型的边界。
- 正则化 SVM（Soft-Margin SVM）允许部分误分类，增强了模型的鲁棒性。
- 模型求解基于对偶优化，对偶变量 $\alpha$ 的解直接反映了样本的状态（支持向量、误分类样本等）。