当前位置：首页 > news >正文

SVM理论推导

news 来源：原创 2025/7/6 5:34:52

本文介绍支持向量机（SVM）的理论推导。

一、SVM 的基本思想

SVM 的目标是找到一个最优超平面，将样本分为不同的类别，并最大化类别间的间隔。

1. 线性可分情况下：

在特征空间中找到一个超平面，使得：

样本之间的分类间隔（margin）最大。
分类误差最小。

超平面可以表示为：
$w^Tx+b=0$
其中：

w 是法向量，决定了超平面的方向。
b 是偏置，决定了超平面到原点的距离。

对于任意样本 $x_i ,y_i)$ ，其中 $y_i$ ∈{−1,1} 表示类别标签，超平面需要满足：
$y_i(w^Tx_i + b) ≥ 1$

1. 优化目标：

最大化间隔（margin）等价于最小化 $\frac{1}{2} \|\vec{w}\|^2$ :
$\min\limits_{w,b} \frac{1}{2} \|\vec{w}\|^2$
约束条件：
$y_i(w^T x_i + b) \gt 1, i = 1, 2, \dots, n$

二、线性不可分情况

在实际问题中，数据通常线性不可分，此时需要引入：

1. 松弛变量 $ξ_i$ ：

允许部分样本点违反约束条件。
目标函数变为：
$\min\limits_{w,b,ξ} \frac{1}{2} \|\vec{w}\|^2 +C\sum\limits_{i=1}^n ξ_i$
其中 C 是惩罚参数，控制误差与间隔的权衡。

2. 核函数：

将低维数据映射到高维特征空间，使其线性可分。
核函数定义为：
$K(x_i, x_j) = ϕ(x_i) \cdot ϕ(x_j)$
常用核函数包括：
线性核： $K(x_i, x_j) = x_i \cdot x_j$
多项式核： $K(x_i, x_j) = (x_i \cdot x_j + c)^d$
高斯核（RBF 核）： $K(x_i, x_j) = exp(−∥x_i − x_j ∥^2 /(2σ^2))$
Sigmoid 核： $K(x_i, x_j) = tanh(αx_i ⋅ x_j +c)$

三、SVM 的优化过程

SVM 的优化问题通常通过 拉格朗日对偶问题 解决：

1. 原始问题：

$\begin{aligned} \min\limits_{w,b,ξ} \quad & \frac{1}{2} \|\vec{w}\|^2 +C\sum\limits_{i=1}^n ξ_i \\ {s.t} \quad & y_i (w^T x_i + b) ≥ 1−ξ_i ,\ & ξ_i ≥ 0, \quad & i = 1, 2, \ldots, n \end{aligned}$

实际上，引入核函数后，优化问题需要用 $\phi(x_i)$ 代替约束条件中的 $x_i$ ,即原始问题变为如下：
$\begin{aligned} \min\limits_{w,b,ξ} \quad & \frac{1}{2} \|\vec{w}\|^2 +C\sum\limits_{i=1}^n ξ_i \\ {s.t} \quad & y_i (w^T \red{\phi(x_i)} + b) ≥ 1−ξ_i \\ & ξ_i ≥ 0 \end{aligned}$

变换一下约束条件的符号，可以得到等价的标准型：
$\begin{aligned} \min\limits_{\omega,b,ξ} \quad & \frac{1}{2} \|\vec{\omega}\|^2 - C\sum\limits_{i=1}^n ξ_i \\ {s.t} \quad & 1 + ξ_i - y_i \omega^T \red{\phi(x_i)} - y_i b \leq 0 \\ & ξ_i \leq 0, \quad & i = 1, 2, \ldots, n \end{aligned}\tag{1}$

由于我们往往不知道 $\phi(x_i)$ 的显示表达，因此我们需要想办法把优化问题转换为没有 $\phi(x_i)$ 的等价问题，因此就引入了对偶问题。
注意：该优化问题强对偶成立，即原始问题的最优解 $p^*$ 等于对偶问题的 $d^*$ 。

2. 对偶问题：

将约束条件引入优化目标，得到对偶形式：
$\begin{aligned} \max\limits_{α} \quad & \sum\limits_{i=1}^n α_i - \frac{1}{2} \cdot \sum\limits_{i=1}^n \sum\limits_{j=1}^n α_i α_j y_i y_j K(x_i, x_j) \\ {s.t} \quad & 0 \leq α_i \leq C , \quad \sum\limits_{i=1}^n α_i y_i = 0 \end{aligned}\tag{2}$
其中 $α_i$ 是拉格朗日乘子。

3. 优化算法：

对偶问题通常通过 SMO（序列最小优化）或其他数值方法求解。

补充：对偶函数推导：

式（1）的拉格朗日函数为：
$\begin{aligned} L(\omega, \alpha, \beta) = & \frac{1}{2} \|\vec{w}\|^2 - C\sum\limits_{i=1}^n ξ_i + \sum\limits_{i=1}^n \alpha_i(1 + ξ_i - y_i \omega^T \red{\phi(x_i)} - y_i b) \\ & + \sum\limits_{i=1}^n \beta_iξ_i \\ \end{aligned}\tag{3}$

在给定 $\alpha,\beta$ 对偶函数的值，实质上就是对于多有 $(\omega,ξ_i, b)$ 求最小值。即对偶问题为：
$\begin{aligned} \max\limits_{\alpha, \beta} \quad & \theta(\alpha,\beta) = \inf\limits_{\omega,ξ_i, b} L(\omega, \alpha, \beta) \\ {s.t} \quad & \alpha_i \geq 0, \quad \beta_i \geq 0, \quad i = 1, 2, \ldots, n \end{aligned}\tag{4}$

其中 $in f$ 是极小化的意思。
注意：该问题没有等式约束，这里的 $\alpha_i, \beta_i$ 都是原始优化问题的不等式约束的拉格朗日乘子。

为了求得拉格朗日函数（式子3）的最小值，需要在对应变量求一阶偏导等于0 即可，可得：
$\begin{aligned} \frac{\partial L}{\partial \omega} = 0 & \Rightarrow \quad \omega = \sum\limits_{i=1}^n \alpha_iy_i\phi(x_i) \\ \frac{\partial L}{\partial ξ_i} = 0 & \Rightarrow \quad \alpha_i + \beta_i = C \\ \frac{\partial L}{\partial b} = 0 & \Rightarrow \quad \sum\limits_{i=1}^n \alpha_iy_i = 0 \end{aligned}$

可得：
$\begin{aligned} \frac{1}{2} \|\vec{w}\|^2 & = \frac{1}{2} \omega^T\omega \\ &=\frac{1}{2} (\sum\limits_{i=1}^n \alpha_iy_i\phi(x_i))^T(\sum\limits_{j=1}^n \alpha_jy_j\phi(x_j)) \\ &= \frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{j=1}^n \alpha_i\alpha_jy_iy_j\red{\phi(x_i)^T\phi(x_j)} \end{aligned}$

又有：
$\begin{aligned} -\sum\limits_{i=1}^n \alpha_iy_i \omega^T \phi(x_i) & = -\sum\limits_{i=1}^n \alpha_iy_i (\sum\limits_{j=1}^n \alpha_jy_j\phi(x_j))^T \phi(x_i) \\ & = - \sum\limits_{i=1}^n\sum\limits_{j=1}^n \alpha_i\alpha_jy_iy_j\red{\phi(x_j)^T\phi(x_i)} \end{aligned}$

注意红色部分可以用核函数 $K(x_i, x_j)$ 替换。（妙啊）

带入到式子（4）中，得：
$\theta(\alpha,\beta) = \sum\limits_{i=1}^n \alpha_i - \frac{1}{2} \sum\limits_{i=1}^n\sum\limits_{j=1}^n \alpha_i\alpha_jy_iy_j\red{K(x_i,x_j)}$

即推导出了对偶问题的目标函数式子（2）。

四、求解

对偶问题通常通过 SMO（序列最小优化）或其他数值方法求解。

到这里思考一个问题：
我们的目标是求分割平面的 $\omega,b$ ，但是求对偶问题得到的是 $\alpha$ , 这要怎么办？

目前已经有对偶问题得到了其解 $\alpha$ , 我们又有
$\omega = \sum\limits_{i=1}^n \alpha_iy_i\phi(x_i)$
是否可以推出 $\omega$ 呢？答案是否定的，因为这里又出现了一个 $\phi(x_i)$ ，大前提是我们并不知道 $\phi(x_i)$ 的具体显示表达。

测试流程（a）

测试样本 $x$ 输入，有

若 $\omega^T\phi(x) + b \geq 0$ 则 y = +1 ,属于第一类，或正例；
若 $\omega^T\phi(x) + b \lt 0$ 则 y = -1, 属于第二类，或负例；

对于实际场景，我们并不需要具体的 $\omega$ , 如果知道 $\omega^T\phi(x) + b$ 也是可以的，这样就跳过了具体的 $\phi(x)$ 。

那么我们继续看，上述中我们已经求得了 $\omega$ 的表达式，带入可得：
$\begin{aligned} \omega^T\phi(x) &= (\sum\limits_{i=1}^n \alpha_iy_i\phi(x_i))\phi(x) \\ &= \sum\limits_{i=1}^n \alpha_iy_i\red{\phi(x_i)\phi(x)} \\ &= \sum\limits_{i=1}^n \alpha_iy_i\red{K(x_i, x)} \end{aligned}$

问题又来了， $\omega^T\phi(x) + b$ 中的 b 怎么得到？

我们继续看，回到对偶问题上，对偶问题的解一定满足 KKT 条件，而 KKT 条件中的互补松弛 条件：
$\sum\limits_{i=1}^n \lambda_if_i = 0, \quad \lambda \geq 0, f_i \leq 0$

对应本示例（结合式子3）表明：
对于 $\forall i = 1, 2, \ldots, n$

要么 $\alpha_i=0$ ，要么 $ξ_i - y_i \omega^T \red{\phi(x_i)} - y_i b = 0$
要么 $\beta_i = 0$ ，要么 $\xi_i = 0$

那么我们可以取一个 $\alpha_i$ 满足 $\lt \alpha_i \lt C$ ，则 $\beta_i = C - \alpha_i \gt 0$ ，此时有:
$\beta_i = C - \alpha_i \gt 0 \quad \Rightarrow \quad \xi_i = 0$
同样的：
$\alpha_i \neq 0 \quad \Rightarrow \quad 1 + ξ_i - y_i \omega^T \red{\phi(x_i)} - y_i b = 0$

可以得到 b 的表达式为：
$\begin{aligned} b &= \frac{1 - y_i \red{\omega^T\phi(x_i)} }{y_i} \\ &= \frac{1 - y_i \red{\sum\limits_{j=1}^n \alpha_jy_j\red{K(x_j, x_i)} }}{y_i} \end{aligned}$

至此 b 就算出来了。实际中可以把所有的满足 $\lt \alpha_i \lt C$ 中的 $\alpha_i$ , 按照上面方法求出对应的 b, 然后求平均。

测试流程（b）

有了上面的推论，我们可以得到最终的测试流程：

输入测试样本 $x$ ,

若 $\sum\limits_{i=1}^n \alpha_iy_iK(x_i, x) + b \geq 0$ ，则 y = +1
若 $\sum\limits_{i=1}^n \alpha_iy_iK(x_i, x) + b \lt 0$ ，则 y = -1

总结：整个算法学习过程和测试流程都无需知道 $\phi(x)$ , 只需要知道 $K(x_i, x_j)$ 就可以完成。

（至此，结束）