支持向量机（SVM）的数学推导与核函数应用
题目描述
支持向量机（SVM）是一种经典的二分类模型，其核心思想是找到一个最优超平面，使得两类数据点到该平面的间隔最大化。本题要求：
- 推导线性可分SVM的数学形式，包括间隔定义、优化目标建立和对偶问题转化；
- 解释核函数的作用，并说明如何通过核方法处理非线性分类问题。
解题过程
1. 间隔的定义与优化目标
（1）超平面与函数间隔
- 超平面表达式为 \(\mathbf{w}^T \mathbf{x} + b = 0\)，其中 \(\mathbf{w}\) 是法向量，\(b\) 是偏置。
- 对于样本点 \((\mathbf{x}_i, y_i)\)（\(y_i \in \{-1, +1\}\)），其函数间隔定义为：
\[ \hat{\gamma}_i = y_i (\mathbf{w}^T \mathbf{x}_i + b) \]
函数间隔可反映分类的正确性和置信度，但存在缩放不变性问题（例如等比例放大 \(\mathbf{w}\) 和 \(b\) 时间隔会变大但超平面不变）。
（2）几何间隔与最大化目标
- 几何间隔是函数间隔除以 \(\|\mathbf{w}\|\)，即：
\[ \gamma_i = \frac{\hat{\gamma}_i}{\|\mathbf{w}\|} = \frac{y_i (\mathbf{w}^T \mathbf{x}_i + b)}{\|\mathbf{w}\|} \]
- SVM的目标是找到使最小几何间隔最大的超平面。假设所有样本分类正确，优化问题可写为：
\[ \max_{\mathbf{w}, b} \min_i \gamma_i \quad \text{s.t.} \quad y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq \hat{\gamma}, \ \forall i \]
通过固定函数间隔 \(\hat{\gamma}=1\)（不影响优化效果），问题转化为：
\[ \max_{\mathbf{w}, b} \frac{1}{\|\mathbf{w}\|} \quad \text{s.t.} \quad y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1, \ \forall i \]
等价于更简洁的凸优化问题：
\[ \min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{s.t.} \quad y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1, \ \forall i \]
2. 拉格朗日对偶问题
（1）引入拉格朗日乘子
- 为处理约束条件，构建拉格朗日函数：
\[ L(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^n \alpha_i \left[ y_i (\mathbf{w}^T \mathbf{x}_i + b) - 1 \right] \]
其中 \(\alpha_i \geq 0\) 是拉格朗日乘子。
（2）转化为对偶问题
- 先求 \(L\) 对 \(\mathbf{w}\) 和 \(b\) 的极小值：
\[ \frac{\partial L}{\partial \mathbf{w}} = 0 \Rightarrow \mathbf{w} = \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i \]
\[ \frac{\partial L}{\partial b} = 0 \Rightarrow \sum_{i=1}^n \alpha_i y_i = 0 \]
- 将结果代回 \(L\)，消去 \(\mathbf{w}\) 和 \(b\)，得到对偶问题：
\[ \max_{\boldsymbol{\alpha}} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j \]
\[ \text{s.t.} \quad \alpha_i \geq 0, \ \sum_{i=1}^n \alpha_i y_i = 0 \]
- 关键性质：只有支持向量（满足 \(y_i (\mathbf{w}^T \mathbf{x}_i + b) = 1\) 的样本）对应的 \(\alpha_i > 0\)，其余样本的 \(\alpha_i=0\)。
3. 核函数处理非线性问题
（1）线性不可分情况
- 若数据线性不可分，可引入松弛变量 \(\xi_i \geq 0\)，将约束放宽为：
\[ y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i \]
优化目标变为 \(\min \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_i \xi_i\)，其中 \(C\) 是惩罚参数。
（2）核技巧（Kernel Trick）
- 对偶问题中出现了内积 \(\mathbf{x}_i^T \mathbf{x}_j\)。通过映射 \(\phi(\mathbf{x})\) 将数据映射到高维空间，内积变为 \(\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)\)。
- 核函数 \(K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)\) 直接计算映射后的内积，避免显式构造 \(\phi(\cdot)\)（维数可能无限）。
- 常用核函数：
- 多项式核： \(K(\mathbf{x}, \mathbf{z}) = (\mathbf{x}^T \mathbf{z} + c)^d\)
- 高斯核（RBF）： \(K(\mathbf{x}, \mathbf{z}) = \exp(-\gamma \|\mathbf{x} - \mathbf{z}\|^2)\)
（3）最终分类决策函数
- 利用核函数，决策函数表示为：
\[ f(\mathbf{x}) = \sum_{i \in SV} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b \]
其中 \(SV\) 是支持向量集合。只需计算支持向量与新样本的核函数，即可实现非线性分类。
总结
SVM通过最大化间隔提高泛化能力，对偶形式使问题更易求解，核技巧巧妙解决了非线性分类问题。实际应用中需注意核函数选择和参数调优（如 \(C\) 和 \(\gamma\)）。