高斯核支持向量机（Gaussian SVM）的KKT条件与拉格朗日对偶优化过程
1. 题目描述
我们考虑一个二分类问题，给定训练数据集 \(\{ (\mathbf{x}_i, y_i) \}_{i=1}^n\)，其中 \(\mathbf{x}_i \in \mathbb{R}^d\) 为特征向量，\(y_i \in \{-1, +1\}\) 为标签。高斯核支持向量机（也称为径向基函数核SVM）通过将数据映射到无限维特征空间，在该空间中寻找一个最大间隔超平面来进行非线性分类。本题目详细讲解其基于拉格朗日对偶的优化过程，特别是KKT（Karush-Kuhn-Tucker）条件在优化中的作用，以及如何通过对偶问题求解得到最终分类决策函数。
2. 问题建模与原始优化问题
2.1 非线性分类的映射
由于数据可能线性不可分，我们引入一个非线性映射 \(\phi(\mathbf{x})\) 将原始特征映射到高维特征空间。在这个空间里，我们希望找到一个超平面：
\[\mathbf{w}^\top \phi(\mathbf{x}) + b = 0 \]
使得两类样本被正确分开，且间隔（margin）最大。
2.2 软间隔与原始优化问题
考虑到噪声或重叠数据，我们引入松弛变量 \(\xi_i \geq 0\)，允许部分样本违反间隔条件。原始优化问题为：
\[\begin{aligned} \min_{\mathbf{w}, b, \boldsymbol{\xi}} &\quad \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \\ \text{s.t.} &\quad y_i(\mathbf{w}^\top \phi(\mathbf{x}_i) + b) \geq 1 - \xi_i, \quad i=1,\dots,n \\ &\quad \xi_i \geq 0, \quad i=1,\dots,n \end{aligned} \]
其中：
- \(\frac{1}{2} \|\mathbf{w}\|^2\) 是正则化项，控制模型复杂度；
- \(C > 0\) 是惩罚参数，平衡间隔最大化和分类错误；
- 约束条件确保每个样本的函数间隔至少为 \(1 - \xi_i\)。
3. 拉格朗日函数与对偶问题
3.1 引入拉格朗日乘子
为处理约束，我们构造拉格朗日函数：
\[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}^\top \phi(\mathbf{x}_i) + b) - 1 + \xi_i \big] - \sum_{i=1}^n \mu_i \xi_i \]
其中：
- \(\alpha_i \geq 0\) 是对应于间隔约束的拉格朗日乘子；
- \(\mu_i \geq 0\) 是对应于 \(\xi_i \geq 0\) 的拉格朗日乘子。
3.2 原始问题的KKT条件
原始问题的最优解必须满足KKT条件：
- 平稳性条件（梯度为零）：
\[ \frac{\partial L}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^n \alpha_i y_i \phi(\mathbf{x}_i) = 0 \quad \Rightarrow \quad \mathbf{w} = \sum_{i=1}^n \alpha_i y_i \phi(\mathbf{x}_i) \]
\[ \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 \]
\[ \frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \quad \Rightarrow \quad \alpha_i + \mu_i = C \]
- 原始可行性：
\[ y_i(\mathbf{w}^\top \phi(\mathbf{x}_i) + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 \]
- 对偶可行性：
\[ \alpha_i \geq 0, \quad \mu_i \geq 0 \]
- 互补松弛条件：
\[ \alpha_i \big[ y_i(\mathbf{w}^\top \phi(\mathbf{x}_i) + b) - 1 + \xi_i \big] = 0 \]
\[ \mu_i \xi_i = 0 \]
3.3 推导对偶问题
将 \(\mathbf{w} = \sum_i \alpha_i y_i \phi(\mathbf{x}_i)\) 和 \(\mu_i = C - \alpha_i\) 代入拉格朗日函数，消去 \(\mathbf{w}, \boldsymbol{\xi}, \boldsymbol{\mu}\)：
\[\begin{aligned} L &= \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j) + C \sum_i \xi_i \\ &\quad - \sum_i \alpha_i y_i \big( \sum_j \alpha_j y_j \phi(\mathbf{x}_j)^\top \phi(\mathbf{x}_i) \big) - b \sum_i \alpha_i y_i \\ &\quad + \sum_i \alpha_i (1 - \xi_i) - \sum_i (C - \alpha_i) \xi_i \end{aligned} \]
利用 \(\sum_i \alpha_i y_i = 0\) 和 \(\sum_i (C - \alpha_i) \xi_i - C \sum_i \xi_i + \sum_i \alpha_i \xi_i = 0\)，化简后得到对偶问题：
\[\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 K(\mathbf{x}_i, \mathbf{x}_j) \\ \text{s.t.} &\quad \sum_{i=1}^n \alpha_i y_i = 0 \\ &\quad 0 \leq \alpha_i \leq C, \quad i=1,\dots,n \end{aligned} \]
其中 \(K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)\) 是核函数。对于高斯核（RBF核）：
\[K(\mathbf{x}_i, \mathbf{x}_j) = \exp\left(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2\right) \]
4. 对偶问题的求解与KKT条件的应用
4.1 对偶问题的结构
- 这是一个凸二次规划问题，有 \(n\) 个变量 \(\alpha_i\)，以及线性约束和边界约束。
- 由于高斯核满足Mercer条件，核矩阵 \(K = [K(\mathbf{x}_i, \mathbf{x}_j)]\) 是半正定的，确保对偶问题是凸的。
4.2 利用KKT条件分类支持向量
根据互补松弛条件，我们可以将样本分为三类：
- 间隔边界上的支持向量：\(\alpha_i = 0\)。此时样本在间隔边界外且分类正确，\(\xi_i = 0\)。
- 间隔边界上的支持向量：\(0 < \alpha_i < C\)。此时样本恰好落在间隔边界上，\(\xi_i = 0\)，满足：
\[ y_i(\mathbf{w}^\top \phi(\mathbf{x}_i) + b) = 1 \]
- 违反间隔的支持向量：\(\alpha_i = C\)。此时样本可能落在间隔内或分类错误，\(\xi_i > 0\)。
4.3 计算偏置 \(b\)
利用任意一个满足 \(0 < \alpha_i < C\) 的样本，根据条件 \(y_i(\mathbf{w}^\top \phi(\mathbf{x}_i) + b) = 1\) 和 \(\mathbf{w} = \sum_j \alpha_j y_j \phi(\mathbf{x}_j)\)，得到：
\[b = y_i - \sum_{j=1}^n \alpha_j y_j K(\mathbf{x}_j, \mathbf{x}_i) \]
为数值稳定，通常用所有满足 \(0 < \alpha_i < C\) 的样本计算 \(b\) 的平均值。
5. 决策函数与预测
最终的决策函数为：
\[f(\mathbf{x}) = \operatorname{sign}\left( \sum_{i=1}^n \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b \right) \]
其中求和实际上只对支持向量（\(\alpha_i > 0\)）进行，因为非支持向量的 \(\alpha_i = 0\)。
6. 总结：KKT条件的关键作用
- 识别支持向量：KKT的互补松弛条件决定了哪些样本是支持向量，从而简化模型。
- 保证最优性：KKT条件是原始问题与对偶问题最优解的桥梁，确保解满足间隔最大化和分类约束。
- 计算偏置：通过 \(0 < \alpha_i < C\) 的样本精确计算超平面位置。
- 处理非线性：高斯核通过核技巧隐式映射到高维空间，而KKT条件确保在这个空间中的优化仍然有效。
通过以上步骤，我们完成了高斯核SVM从原始问题建模、拉格朗日对偶转化、KKT条件分析到最终决策函数构建的全过程，深入理解了其优化机制。