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

字数 3096 2025-11-15 12:18:35

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

我将为您详细讲解高斯核支持向量机（RBF SVM）的完整数学推导和优化过程。

题目描述

高斯核支持向量机是在标准SVM基础上引入径向基函数（RBF）核的非线性分类器，通过核技巧将数据映射到高维特征空间，实现复杂非线性决策边界的构建。

基础概念回顾

首先理解几个关键概念：

支持向量机核心思想：寻找一个超平面，使两类样本之间的间隔最大化
核技巧：避免显式计算高维特征映射，直接通过核函数计算内积
RBF核函数：$K(x_i, x_j) = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)$，其中$\sigma$控制函数的宽度

原始优化问题推导

步骤1：间隔最大化 formulation

对于线性可分情况，SVM优化问题为：

\[\min_{w,b} \frac{1}{2}\|w\|^2 \]

\[\text{subject to } y_i(w^T x_i + b) \geq 1, \quad i=1,\dots,n \]

这里：

$w$是超平面法向量
$b$是偏置项
$y_i \in \{-1, +1\}$是样本标签
$\frac{1}{2}\|w\|^2$是正则化项，防止过拟合

步骤2：引入松弛变量

对于线性不可分情况，引入松弛变量$\xi_i$：

\[\min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C\sum_{i=1}^n \xi_i \]

\[\text{subject to } y_i(w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 \]

其中$C > 0$是惩罚参数，控制误分类惩罚与间隔大小的权衡。

对偶问题推导

步骤3：构建拉格朗日函数

引入拉格朗日乘子$\alpha_i \geq 0$和$\mu_i \geq 0$：

\[L(w,b,\xi,\alpha,\mu) = \frac{1}{2}\|w\|^2 + C\sum_{i=1}^n \xi_i - \sum_{i=1}^n \alpha_i[y_i(w^T x_i + b) - 1 + \xi_i] - \sum_{i=1}^n \mu_i \xi_i \]

步骤4：KKT条件与偏导求解

根据KKT条件，求偏导并令其为0：

$\frac{\partial L}{\partial w} = w - \sum_{i=1}^n \alpha_i y_i x_i = 0 \Rightarrow w = \sum_{i=1}^n \alpha_i y_i x_i$
$\frac{\partial L}{\partial b} = -\sum_{i=1}^n \alpha_i y_i = 0 \Rightarrow \sum_{i=1}^n \alpha_i y_i = 0$
$\frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \Rightarrow \alpha_i = C - \mu_i$

步骤5：得到对偶问题

将上述结果代回拉格朗日函数，得到对偶问题：

\[\max_{\alpha} \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 x_i^T x_j \]

\[\text{subject to } 0 \leq \alpha_i \leq C, \quad \sum_{i=1}^n \alpha_i y_i = 0 \]

核技巧引入

步骤6：RBF核函数替换

将对偶问题中的内积$x_i^T x_j$替换为RBF核函数：

\[K(x_i, x_j) = \exp\left(-\gamma \|x_i - x_j\|^2\right) \]

其中$\gamma = \frac{1}{2\sigma^2}$是核参数。

对偶问题变为：

\[\max_{\alpha} \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(x_i, x_j) \]

步骤7：决策函数推导

最终的决策函数为：

\[f(x) = \text{sign}\left(\sum_{i=1}^n \alpha_i y_i K(x_i, x) + b\right) \]

其中$b$通过支持向量计算：

\[b = y_k - \sum_{i=1}^n \alpha_i y_i K(x_i, x_k) \]

对于任意满足$0 < \alpha_k < C$的支持向量$x_k$。

参数优化与求解

步骤8：序列最小优化（SMO）算法

由于对偶问题是凸二次规划，常用SMO算法求解：

启发式选择变量：每次选择违反KKT条件最严重的$\alpha_i$和$\alpha_j$
两变量优化：固定其他变量，优化$\alpha_i$和$\alpha_j$
解析求解：对于选定的两个变量，有闭式解：

\[\alpha_j^{new} = \alpha_j^{old} - \frac{y_j(E_i - E_j)}{\eta} \]

其中$E_i = f(x_i) - y_i$是预测误差，$\eta = 2K(x_i,x_j) - K(x_i,x_i) - K(x_j,x_j)$

剪辑操作：确保$\alpha$在$[0,C]$范围内

\[\alpha_j^{new,clipped} = \begin{cases} H & \text{if } \alpha_j^{new} > H \\ \alpha_j^{new} & \text{if } L \leq \alpha_j^{new} \leq H \\ L & \text{if } \alpha_j^{new} < L \end{cases} \]

更新$\alpha_i$：$\alpha_i^{new} = \alpha_i^{old} + y_i y_j (\alpha_j^{old} - \alpha_j^{new})$

步骤9：超参数调优

RBF SVM有两个关键超参数：

惩罚参数C：控制模型复杂度与训练误差的权衡
核参数$\gamma$：控制RBF函数的宽度，影响决策边界的复杂度

常用网格搜索结合交叉验证进行调优。

算法特性分析

步骤10：RBF核的数学性质

正定性：RBF核是正定核，满足Mercer条件
局部性：$\gamma$越大，核函数越局部化，决策边界越复杂
通用逼近性：RBF核可以逼近任何连续函数

步骤11：计算复杂度分析

训练复杂度：$O(n^3)$（最坏情况），实际中约为$O(n^2)$
预测复杂度：$O(n_{sv})$，其中$n_{sv}$是支持向量数量

这个完整的推导过程展示了RBF SVM从原始优化问题到最终实现的数学基础，以及如何通过核技巧处理非线性分类问题。

高斯核支持向量机（RBF SVM）的数学推导与优化过程我将为您详细讲解高斯核支持向量机（RBF SVM）的完整数学推导和优化过程。题目描述高斯核支持向量机是在标准SVM基础上引入径向基函数（RBF）核的非线性分类器，通过核技巧将数据映射到高维特征空间，实现复杂非线性决策边界的构建。基础概念回顾首先理解几个关键概念：支持向量机核心思想：寻找一个超平面，使两类样本之间的间隔最大化核技巧：避免显式计算高维特征映射，直接通过核函数计算内积 RBF核函数：$K(x_ i, x_ j) = \exp\left(-\frac{\|x_ i - x_ j\|^2}{2\sigma^2}\right)$，其中$\sigma$控制函数的宽度原始优化问题推导步骤1：间隔最大化 formulation 对于线性可分情况，SVM优化问题为： $$\min_ {w,b} \frac{1}{2}\|w\|^2$$ $$\text{subject to } y_ i(w^T x_ i + b) \geq 1, \quad i=1,\dots,n$$ 这里： $w$是超平面法向量 $b$是偏置项 $y_ i \in \{-1, +1\}$是样本标签 $\frac{1}{2}\|w\|^2$是正则化项，防止过拟合步骤2：引入松弛变量对于线性不可分情况，引入松弛变量$\xi_ i$： $$\min_ {w,b,\xi} \frac{1}{2}\|w\|^2 + C\sum_ {i=1}^n \xi_ i$$ $$\text{subject to } y_ i(w^T x_ i + b) \geq 1 - \xi_ i, \quad \xi_ i \geq 0$$ 其中$C > 0$是惩罚参数，控制误分类惩罚与间隔大小的权衡。对偶问题推导步骤3：构建拉格朗日函数引入拉格朗日乘子$\alpha_ i \geq 0$和$\mu_ i \geq 0$： $$L(w,b,\xi,\alpha,\mu) = \frac{1}{2}\|w\|^2 + C\sum_ {i=1}^n \xi_ i - \sum_ {i=1}^n \alpha_ i[ y_ i(w^T x_ i + b) - 1 + \xi_ i] - \sum_ {i=1}^n \mu_ i \xi_ i$$ 步骤4：KKT条件与偏导求解根据KKT条件，求偏导并令其为0： $\frac{\partial L}{\partial w} = w - \sum_ {i=1}^n \alpha_ i y_ i x_ i = 0 \Rightarrow w = \sum_ {i=1}^n \alpha_ i y_ i x_ i$ $\frac{\partial L}{\partial b} = -\sum_ {i=1}^n \alpha_ i y_ i = 0 \Rightarrow \sum_ {i=1}^n \alpha_ i y_ i = 0$ $\frac{\partial L}{\partial \xi_ i} = C - \alpha_ i - \mu_ i = 0 \Rightarrow \alpha_ i = C - \mu_ i$ 步骤5：得到对偶问题将上述结果代回拉格朗日函数，得到对偶问题： $$\max_ {\alpha} \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 x_ i^T x_ j$$ $$\text{subject to } 0 \leq \alpha_ i \leq C, \quad \sum_ {i=1}^n \alpha_ i y_ i = 0$$ 核技巧引入步骤6：RBF核函数替换将对偶问题中的内积$x_ i^T x_ j$替换为RBF核函数： $$K(x_ i, x_ j) = \exp\left(-\gamma \|x_ i - x_ j\|^2\right)$$ 其中$\gamma = \frac{1}{2\sigma^2}$是核参数。对偶问题变为： $$\max_ {\alpha} \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(x_ i, x_ j)$$ 步骤7：决策函数推导最终的决策函数为： $$f(x) = \text{sign}\left(\sum_ {i=1}^n \alpha_ i y_ i K(x_ i, x) + b\right)$$ 其中$b$通过支持向量计算： $$b = y_ k - \sum_ {i=1}^n \alpha_ i y_ i K(x_ i, x_ k)$$ 对于任意满足$0 < \alpha_ k < C$的支持向量$x_ k$。参数优化与求解步骤8：序列最小优化（SMO）算法由于对偶问题是凸二次规划，常用SMO算法求解：启发式选择变量：每次选择违反KKT条件最严重的$\alpha_ i$和$\alpha_ j$ 两变量优化：固定其他变量，优化$\alpha_ i$和$\alpha_ j$ 解析求解：对于选定的两个变量，有闭式解： $$\alpha_ j^{new} = \alpha_ j^{old} - \frac{y_ j(E_ i - E_ j)}{\eta}$$ 其中$E_ i = f(x_ i) - y_ i$是预测误差，$\eta = 2K(x_ i,x_ j) - K(x_ i,x_ i) - K(x_ j,x_ j)$ 剪辑操作：确保$\alpha$在$[ 0,C ]$范围内 $$\alpha_ j^{new,clipped} = \begin{cases} H & \text{if } \alpha_ j^{new} > H \\ \alpha_ j^{new} & \text{if } L \leq \alpha_ j^{new} \leq H \\ L & \text{if } \alpha_ j^{new} < L \end{cases}$$ 更新$\alpha_ i$ ：$\alpha_ i^{new} = \alpha_ i^{old} + y_ i y_ j (\alpha_ j^{old} - \alpha_ j^{new})$ 步骤9：超参数调优 RBF SVM有两个关键超参数：惩罚参数C ：控制模型复杂度与训练误差的权衡核参数$\gamma$ ：控制RBF函数的宽度，影响决策边界的复杂度常用网格搜索结合交叉验证进行调优。算法特性分析步骤10：RBF核的数学性质正定性：RBF核是正定核，满足Mercer条件局部性：$\gamma$越大，核函数越局部化，决策边界越复杂通用逼近性：RBF核可以逼近任何连续函数步骤11：计算复杂度分析训练复杂度：$O(n^3)$（最坏情况），实际中约为$O(n^2)$ 预测复杂度：$O(n_ {sv})$，其中$n_ {sv}$是支持向量数量这个完整的推导过程展示了RBF SVM从原始优化问题到最终实现的数学基础，以及如何通过核技巧处理非线性分类问题。