核支持向量机（Kernel SVM）的数学推导与优化过程

字数 5008 2025-12-09 21:07:18

核支持向量机（Kernel SVM）的数学推导与优化过程

题目描述
核支持向量机（Kernel SVM）是一种用于处理非线性分类问题的经典算法。其核心思想是通过一个非线性映射（即核函数）将原始低维空间中的线性不可分数据映射到高维特征空间，使其在该高维空间中线性可分，从而在高维空间中构建一个线性支持向量机（SVM）分类器。本题将详细阐述核SVM的数学形式、如何通过拉格朗日对偶和核技巧（Kernel Trick）避免显式高维映射计算，并逐步推导其优化求解过程。

解题过程详解

步骤1：问题形式化
设训练集为 \(\{ (\mathbf{x}_i, y_i) \}_{i=1}^{n}\)，其中 \(\mathbf{x}_i \in \mathbb{R}^d\) 是特征向量，\(y_i \in \{-1, +1\}\) 是类别标签。在原始低维空间中，数据可能是线性不可分的。我们希望找到一个非线性决策函数 \(f(\mathbf{x}) = \mathbf{w}^T \phi(\mathbf{x}) + b\)，其中 \(\phi(\cdot)\) 是一个非线性映射函数，将数据映射到高维（甚至无限维）特征空间。目标是在高维特征空间中找到一个分离超平面，使得分类间隔最大。这对应于以下优化问题：

\[\begin{aligned} \min_{\mathbf{w}, b} \quad & \frac{1}{2} \|\mathbf{w}\|^2 \\ \text{s.t.} \quad & y_i \left( \mathbf{w}^T \phi(\mathbf{x}_i) + b \right) \geq 1, \quad i = 1, \dots, n \end{aligned} \]

这就是线性SVM在高维特征空间中的原始优化问题。需要注意的是，由于 \(\phi(\cdot)\) 可能映射到非常高维的空间，直接求解 \(\mathbf{w}\) 是不现实的，因为 \(\mathbf{w}\) 本身的维数会变得非常高。

步骤2：拉格朗日对偶与核技巧引入
为了高效求解，我们引入拉格朗日函数，将其转化为对偶问题。定义拉格朗日乘子 \(\alpha_i \geq 0\)，拉格朗日函数为：

\[L(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^{n} \alpha_i \left[ y_i \left( \mathbf{w}^T \phi(\mathbf{x}_i) + b \right) - 1 \right] \]

对 \(L\) 关于 \(\mathbf{w}\) 和 \(b\) 求偏导并令其为零：

\[\begin{aligned} \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 \end{aligned} \]

将这两个关系代回 \(L\)，得到对偶问题（化简过程省略中间的代入计算）：

\[\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 \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j) \\ \text{s.t.} \quad & \sum_{i=1}^{n} \alpha_i y_i = 0, \quad \alpha_i \geq 0, \quad i = 1, \dots, n \end{aligned} \]

关键观察：在这个对偶问题中，高维特征空间的内积 \(\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)\) 总是以配对形式出现，而从未单独需要 \(\phi(\mathbf{x})\)。因此，我们可以直接定义一个核函数 \(K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)\)，它计算原始空间中两个样本点经映射后的内积。这被称为核技巧。

核函数的条件：根据Mercer定理，任何半正定的对称函数 \(K(\cdot, \cdot)\) 都对应某个特征空间中的内积。常用核函数有：

线性核： \(K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^T \mathbf{x}_j\)
多项式核： \(K(\mathbf{x}_i, \mathbf{x}_j) = (\gamma \mathbf{x}_i^T \mathbf{x}_j + r)^d\)
径向基（RBF）核： \(K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)\)
Sigmoid核： \(K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\gamma \mathbf{x}_i^T \mathbf{x}_j + r)\)

将核函数代入，得到核SVM的对偶优化问题：

\[\boxed{ \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 \alpha_i \geq 0, \quad i = 1, \dots, n \end{aligned}} \]

步骤3：求解对偶问题
这是一个关于 \(\boldsymbol{\alpha}\) 的凸二次规划问题。通常使用序列最小优化（SMO）等算法来高效求解。SMO每次迭代选择两个乘子 \(\alpha_i, \alpha_j\) 进行优化，而固定其他所有乘子，通过解析方法更新这两个乘子，以满足等式约束和边界约束。SMO的收敛性有理论保证。

求解后，大部分 \(\alpha_i\) 为零，对应于非支持向量。非零的 \(\alpha_i\) 对应的样本点 \(\mathbf{x}_i\) 即为支持向量。

权重向量 \(\mathbf{w}\) 的表示：在求解得到 \(\alpha_i\) 后，尽管我们不需要显式计算 \(\mathbf{w}\)，但从步骤2的 \(\mathbf{w} = \sum_{i=1}^{n} \alpha_i y_i \phi(\mathbf{x}_i)\) 可知，\(\mathbf{w}\) 是支持向量在高维空间中的线性组合。

步骤4：计算偏置 \(b\) 与决策函数
对于任意支持向量 \(\mathbf{x}_s\)（满足 \(0 < \alpha_s < C\)，其中 \(C\) 是软间隔惩罚参数，若为硬间隔则 \(0 < \alpha_s\)），其满足等式 \(y_s f(\mathbf{x}_s) = 1\)，即：

\[y_s \left( \sum_{i=1}^{n} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}_s) + b \right) = 1 \]

由于 \(y_s^2 = 1\)，解得：

\[b = y_s - \sum_{i=1}^{n} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}_s) \]

为了数值稳定，通常对所有满足 \(0 < \alpha_s < C\) 的支持向量计算 \(b\) 后取平均值。

最终的非线性决策函数为：

\[f(\mathbf{x}) = \sum_{i=1}^{n} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b \]

注意，求和只需对支持向量（\(\alpha_i > 0\) 的样本）进行，因此预测时计算量与支持向量数量成正比。

分类规则为：\(\text{sign}(f(\mathbf{x}))\)。

步骤5：扩展到软间隔与松弛变量
实际数据常有噪声或重叠，需要软间隔。引入松弛变量 \(\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 \left( \mathbf{w}^T \phi(\mathbf{x}_i) + b \right) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad i = 1, \dots, n \end{aligned} \]

其中 \(C > 0\) 是惩罚参数，控制间隔宽度与分类错误之间的权衡。同样构造拉格朗日函数（引入 \(\alpha_i \geq 0\) 和 \(\mu_i \geq 0\)），最终得到的软间隔核SVM对偶问题为：

\[\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} \]

与硬间隔相比，仅多了上界约束 \(\alpha_i \leq C\)。求解方法和决策函数形式完全相同，只是支持向量的判定条件有所变化（\(\alpha_i = C\) 的样本可能是位于间隔内或误分类的支持向量）。

总结
核SVM的关键在于通过核技巧隐式地将数据映射到高维空间，并在对偶形式中避免直接计算高维映射，从而有效处理非线性分类。优化过程转化为求解一个带线性约束的凸二次规划，常用SMO算法求解。最终模型仅由支持向量线性组合而成，决策函数也只需计算测试点与支持向量之间的核函数值。

核支持向量机（Kernel SVM）的数学推导与优化过程题目描述核支持向量机（Kernel SVM）是一种用于处理非线性分类问题的经典算法。其核心思想是通过一个非线性映射（即核函数）将原始低维空间中的线性不可分数据映射到高维特征空间，使其在该高维空间中线性可分，从而在高维空间中构建一个线性支持向量机（SVM）分类器。本题将详细阐述核SVM的数学形式、如何通过拉格朗日对偶和核技巧（Kernel Trick）避免显式高维映射计算，并逐步推导其优化求解过程。解题过程详解步骤1：问题形式化设训练集为 \( \{ (\mathbf{x} i, y_ i) \} {i=1}^{n} \)，其中 \(\mathbf{x}_ i \in \mathbb{R}^d\) 是特征向量，\(y_ i \in \{-1, +1\}\) 是类别标签。在原始低维空间中，数据可能是线性不可分的。我们希望找到一个非线性决策函数 \(f(\mathbf{x}) = \mathbf{w}^T \phi(\mathbf{x}) + b\)，其中 \(\phi(\cdot)\) 是一个非线性映射函数，将数据映射到高维（甚至无限维）特征空间。目标是在高维特征空间中找到一个分离超平面，使得分类间隔最大。这对应于以下优化问题： \[ \begin{aligned} \min_ {\mathbf{w}, b} \quad & \frac{1}{2} \|\mathbf{w}\|^2 \\ \text{s.t.} \quad & y_ i \left( \mathbf{w}^T \phi(\mathbf{x}_ i) + b \right) \geq 1, \quad i = 1, \dots, n \end{aligned} \] 这就是线性SVM在高维特征空间中的原始优化问题。需要注意的是，由于 \(\phi(\cdot)\) 可能映射到非常高维的空间，直接求解 \(\mathbf{w}\) 是不现实的，因为 \(\mathbf{w}\) 本身的维数会变得非常高。步骤2：拉格朗日对偶与核技巧引入为了高效求解，我们引入拉格朗日函数，将其转化为对偶问题。定义拉格朗日乘子 \(\alpha_ i \geq 0\)，拉格朗日函数为： \[ L(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_ {i=1}^{n} \alpha_ i \left[ y_ i \left( \mathbf{w}^T \phi(\mathbf{x}_ i) + b \right) - 1 \right ] \] 对 \(L\) 关于 \(\mathbf{w}\) 和 \(b\) 求偏导并令其为零： \[ \begin{aligned} \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 \end{aligned} \] 将这两个关系代回 \(L\)，得到对偶问题（化简过程省略中间的代入计算）： \[ \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 \phi(\mathbf{x}_ i)^T \phi(\mathbf{x} j) \\ \text{s.t.} \quad & \sum {i=1}^{n} \alpha_ i y_ i = 0, \quad \alpha_ i \geq 0, \quad i = 1, \dots, n \end{aligned} \] 关键观察：在这个对偶问题中，高维特征空间的内积 \(\phi(\mathbf{x}_ i)^T \phi(\mathbf{x}_ j)\) 总是以配对形式出现，而从未单独需要 \(\phi(\mathbf{x})\)。因此，我们可以直接定义一个核函数 \(K(\mathbf{x}_ i, \mathbf{x}_ j) = \phi(\mathbf{x}_ i)^T \phi(\mathbf{x}_ j)\)，它计算原始空间中两个样本点经映射后的内积。这被称为核技巧。核函数的条件：根据Mercer定理，任何半正定的对称函数 \(K(\cdot, \cdot)\) 都对应某个特征空间中的内积。常用核函数有：线性核： \(K(\mathbf{x}_ i, \mathbf{x}_ j) = \mathbf{x}_ i^T \mathbf{x}_ j\) 多项式核： \(K(\mathbf{x}_ i, \mathbf{x}_ j) = (\gamma \mathbf{x}_ i^T \mathbf{x}_ j + r)^d\) 径向基（RBF）核： \(K(\mathbf{x}_ i, \mathbf{x}_ j) = \exp(-\gamma \|\mathbf{x}_ i - \mathbf{x}_ j\|^2)\) Sigmoid核： \(K(\mathbf{x}_ i, \mathbf{x}_ j) = \tanh(\gamma \mathbf{x}_ i^T \mathbf{x}_ j + r)\) 将核函数代入，得到核SVM的对偶优化问题： \[ \boxed{ \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 \alpha_ i \geq 0, \quad i = 1, \dots, n \end{aligned}} \] 步骤3：求解对偶问题这是一个关于 \(\boldsymbol{\alpha}\) 的凸二次规划问题。通常使用序列最小优化（SMO）等算法来高效求解。SMO每次迭代选择两个乘子 \(\alpha_ i, \alpha_ j\) 进行优化，而固定其他所有乘子，通过解析方法更新这两个乘子，以满足等式约束和边界约束。SMO的收敛性有理论保证。求解后，大部分 \(\alpha_ i\) 为零，对应于非支持向量。非零的 \(\alpha_ i\) 对应的样本点 \(\mathbf{x}_ i\) 即为支持向量。权重向量 \(\mathbf{w}\) 的表示：在求解得到 \(\alpha_ i\) 后，尽管我们不需要显式计算 \(\mathbf{w}\)，但从步骤2的 \(\mathbf{w} = \sum_ {i=1}^{n} \alpha_ i y_ i \phi(\mathbf{x}_ i)\) 可知，\(\mathbf{w}\) 是支持向量在高维空间中的线性组合。步骤4：计算偏置 \(b\) 与决策函数对于任意支持向量 \(\mathbf{x}_ s\)（满足 \(0 < \alpha_ s < C\)，其中 \(C\) 是软间隔惩罚参数，若为硬间隔则 \(0 < \alpha_ s\)），其满足等式 \(y_ s f(\mathbf{x}_ s) = 1\)，即： \[ y_ s \left( \sum_ {i=1}^{n} \alpha_ i y_ i K(\mathbf{x}_ i, \mathbf{x}_ s) + b \right) = 1 \] 由于 \(y_ s^2 = 1\)，解得： \[ b = y_ s - \sum_ {i=1}^{n} \alpha_ i y_ i K(\mathbf{x}_ i, \mathbf{x}_ s) \] 为了数值稳定，通常对所有满足 \(0 < \alpha_ s < C\) 的支持向量计算 \(b\) 后取平均值。最终的非线性决策函数为： \[ f(\mathbf{x}) = \sum_ {i=1}^{n} \alpha_ i y_ i K(\mathbf{x}_ i, \mathbf{x}) + b \] 注意，求和只需对支持向量（\(\alpha_ i > 0\) 的样本）进行，因此预测时计算量与支持向量数量成正比。分类规则为：\(\text{sign}(f(\mathbf{x}))\)。步骤5：扩展到软间隔与松弛变量实际数据常有噪声或重叠，需要软间隔。引入松弛变量 \(\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 \left( \mathbf{w}^T \phi(\mathbf{x}_ i) + b \right) \geq 1 - \xi_ i, \quad \xi_ i \geq 0, \quad i = 1, \dots, n \end{aligned} \] 其中 \(C > 0\) 是惩罚参数，控制间隔宽度与分类错误之间的权衡。同样构造拉格朗日函数（引入 \(\alpha_ i \geq 0\) 和 \(\mu_ i \geq 0\)），最终得到的软间隔核SVM对偶问题为： \[ \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} \] 与硬间隔相比，仅多了上界约束 \(\alpha_ i \leq C\)。求解方法和决策函数形式完全相同，只是支持向量的判定条件有所变化（\(\alpha_ i = C\) 的样本可能是位于间隔内或误分类的支持向量）。总结核SVM的关键在于通过核技巧隐式地将数据映射到高维空间，并在对偶形式中避免直接计算高维映射，从而有效处理非线性分类。优化过程转化为求解一个带线性约束的凸二次规划，常用SMO算法求解。最终模型仅由支持向量线性组合而成，决策函数也只需计算测试点与支持向量之间的核函数值。