SVM的本质:从直观理解到数学原理

SVM的本质

从直观理解到数学原理

1. 基础:分类问题与决策边界

x₁ x₂ 非线性决策边界 任何线性决策边界都无法有效分离

当我们面对分类问题时,本质上是在寻找一个决策边界,将不同类别的数据分隔开。对于复杂的数据集,往往需要非线性的决策边界(图中黑色曲线)。然而,这些复杂边界往往难以数学表达,且容易导致过拟合。

SVM(支持向量机)提出了一个优雅的解决方案:

  1. 寻找最优线性边界,即能最大化类别间边际的超平面
  2. 通过核技巧(Kernel Trick)处理非线性可分的数据

2. 线性SVM:最大边际的数学本质

w·x + b = 0 超平面 (Hyperplane) 边际 = 2/||w||

图2:SVM的几何解释 - 最大边际超平面

线性SVM的数学表达如下:对于一个训练样本集 {(x₁, y₁), (x₂, y₂), …, (xₙ, yₙ)},其中 xᵢ 是特征向量,yᵢ ∈ {-1, 1} 是类别标签,SVM 尝试找到一个超平面:

wx+b=0w \cdot x + b = 0

这里的 w 是法向量,决定了超平面的方向;b 是偏置项,决定了超平面的位置。SVM 的目标是使这个超平面满足:

对所有 yi=1 的样本:wxi+b1\text{对所有 } y_i = 1 \text{ 的样本:} w \cdot x_i + b \geq 1

对所有 yi=1 的样本:wxi+b1\text{对所有 } y_i = -1 \text{ 的样本:} w \cdot x_i + b \leq -1

这可以简化为一个约束:

yi(wxi+b)1, 对所有样本 iy_i(w \cdot x_i + b) \geq 1, \text{ 对所有样本 } i

几何解释:两个边际超平面之间的距离是 2/w2/||w||。因此,最大化边际等价于最小化 w||w||,或者更常见的,最小化 (1/2)w²(1/2)||w||²

这导致了线性SVM的原始优化问题:

min12w2\min \frac{1}{2}||w||^2

约束条件:yi(wxi+b)1, 对所有样本 i\text{约束条件:} y_i(w \cdot x_i + b) \geq 1, \text{ 对所有样本 } i

支持向量的精确定义

支持向量是那些恰好满足 yi(wxi+b)=1y_i(w \cdot x_i + b) = 1 的点,它们位于边际超平面上。这些点是唯一决定最优超平面的样本点,移除其他点不会改变解。

3. 拉格朗日对偶与KKT条件

为什么要使用对偶形式? 有三个主要原因:

  1. 对偶问题往往更容易求解
  2. 便于引入核函数处理非线性问题
  3. 提供了对支持向量的数学解释

SVM的原始问题可以转化为拉格朗日对偶问题:

L(w,b,α)=12w2iαi[yi(wxi+b)1]L(w, b, \alpha) = \frac{1}{2}||w||^2 - \sum_i \alpha_i[y_i(w \cdot x_i + b) - 1]

其中 αi0\alpha_i \geq 0 是拉格朗日乘子。对偶问题是:

maxW(α)=iαi12ijαiαjyiyj(xixj)\max W(\alpha) = \sum_i \alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i\alpha_jy_iy_j(x_i \cdot x_j)

约束条件:αi0 且 iαiyi=0\text{约束条件:} \alpha_i \geq 0 \text{ 且 } \sum_i \alpha_iy_i = 0

根据KKT条件,我们可以得到:

  1. w=iαiyixiw = \sum_i \alpha_iy_ix_i
  2. 对支持向量:αi>0\alpha_i > 0yi(wxi+b)=1y_i(w \cdot x_i + b) = 1
  3. 对非支持向量:αi=0\alpha_i = 0yi(wxi+b)>1y_i(w \cdot x_i + b) > 1
α₁ > 0 α₂ > 0 α₃ = 0 α₄ = 0 w = Σᵢ αᵢyᵢxᵢ

图3:拉格朗日乘子与支持向量的关系

这一结果令人惊叹:w 可以表示为支持向量的线性组合。对于非支持向量,α = 0,因此它们对决策边界没有贡献。

SVM的稀疏性:最终模型仅由支持向量定义,其数量通常远少于总样本数,这使得SVM即使在大数据集上也能高效运行。

4. 核技巧:处理非线性分类问题的数学原理

原始特征空间 (二维) x₁ x₂ 无法线性分隔 映射函数 Φ Φ: ℝ² → ℝ³ (x₁,x₂) → (x₁²,√2x₁x₂,x₂²) 高维特征空间 (三维) z₁=x₁² z₂=√2x₁x₂ z₃=x₂² 线性可分! 核函数的魔力 K(x,z) = (x·z)² = Φ(x)·Φ(z) 无需显式计算高维坐标,即可获得高维空间中的内积!

当数据在原始空间中非线性可分时,我们引入映射函数 Φ,将数据映射到更高维的特征空间:Φ: x → Φ(x)。在这个新空间中,数据可能变得线性可分。

在对偶表示中,SVM的决策函数变为:

f(x)=sign(iαiyiΦ(xi)Φ(x)+b)f(x) = \text{sign}\left(\sum_i \alpha_iy_i\Phi(x_i) \cdot \Phi(x) + b\right)

核技巧的关键在于:我们并不需要显式计算 Φ(x)!只需要定义一个核函数 K:

K(x,z)=Φ(x)Φ(z)K(x, z) = \Phi(x) \cdot \Phi(z)

这样,决策函数简化为:

f(x)=sign(iαiyiK(xi,x)+b)f(x) = \text{sign}\left(\sum_i \alpha_iy_iK(x_i, x) + b\right)

常用核函数及其隐含的特征空间

  • 线性核: K(x, z) = x·z
  • 多项式核: K(x, z) = (γx·z + r)^d
    隐含了包含所有d阶及以下的单项式的特征空间
  • RBF核(高斯核): K(x, z) = exp(-γ||x-z||²)
    隐含了无限维的特征空间
  • Sigmoid核: K(x, z) = tanh(γx·z + r)
    类似于神经网络的激活函数

核技巧的数学基础是Mercer定理:任何半正定核函数都可以表示为某个特征空间中的内积。这保证了我们可以找到对应的映射函数Φ。

5. 软边际SVM:处理噪声与异常值

ξ₁ ξ₂ C参数:控制边际最大化与错误分类的平衡

图5:软边际SVM - 允许一定程度的错误分类

现实世界的数据集往往包含噪声和异常值,严格的线性可分条件可能导致过拟合。软边际SVM引入松弛变量(ξᵢ),允许一定程度的错误分类:

min12w2+Ciξi\min \frac{1}{2}||w||^2 + C \cdot \sum_i \xi_i

约束条件:yi(wxi+b)1ξi 且 ξi0, 对所有样本 i\text{约束条件:} y_i(w \cdot x_i + b) \geq 1 - \xi_i \text{ 且 } \xi_i \geq 0, \text{ 对所有样本 } i

参数C控制了两个目标的平衡:

  • 最大化边际(结构风险最小化)
  • 最小化分类错误(经验风险最小化)

C的选择是SVM中最重要的超参数调优之一:

  • C较大:模型对训练错误敏感,倾向于减少错误分类,但可能过拟合
  • C较小:模型更注重边际最大化,容忍更多错误,但泛化能力可能更强

损失函数视角

从损失函数的角度看,SVM使用的是合页损失(Hinge Loss):

L(y,f(x))=max(0,1yf(x))L(y, f(x)) = \max(0, 1 - y \cdot f(x))

当样本被正确分类且距离边际足够远时,损失为0;否则,损失随着点越过边际线的程度线性增加。

6. SVM的算法实现与优化

虽然SVM的数学表述优雅,但其计算实现面临挑战,特别是大规模数据集。现代SVM实现采用了多种优化策略:

6.1 序列最小优化(SMO)算法

SMO是解决SVM二次规划问题的高效算法,其核心思想是:

  1. 每次只优化两个拉格朗日乘子α,保持其他乘子不变
  2. 对这两个变量的子问题有封闭解,无需使用二次规划求解器
  3. 重复选择变量对并优化,直至收敛

6.2 核函数计算优化

为提高计算效率,实际应用中常采用:

  • 核矩阵缓存:预计算并存储核矩阵中的元素
  • 低秩近似:对大型核矩阵使用Nyström方法等进行低秩近似
  • 随机特征映射:对某些核函数(如RBF),可使用随机特征映射近似高维特征空间

6.3 参数选择与模型选择

SVM的性能高度依赖于参数选择:

  • C参数:控制错误惩罚力度
  • 核函数参数:如RBF核的γ参数(控制高斯函数宽度)

实践中,使用网格搜索+交叉验证是最常用的参数选择方法,但也有贝叶斯优化等更高效的方案。

7. SVM的理论基础:VC维度与结构风险最小化

SVM的理论基础源于统计学习理论,特别是VC维度和结构风险最小化原则。

VC维度(Vapnik-Chervonenkis维度)衡量一个分类器族的复杂度。对于具有边际γ的线性分类器,VC维度与特征维度(n)和边际成反比:

VC-dimmin(R2/γ2,n)+1\text{VC-dim} \leq \min(\lceil R^2/\gamma^2 \rceil, n) + 1

其中R是数据点的最大范数。这说明,具有大边际的分类器复杂度更低,泛化能力更强。

从结构风险最小化的角度看,SVM通过最大化边际来控制VC维度,从而在保持经验误差低的同时,最小化泛化误差上界。

SVM的本质与优雅之处

回顾SVM的整个理论体系,我们可以看到其优雅之处在于:

  1. 数学基础扎实:基于凸优化、统计学习理论等深厚的数学基础
  2. 稀疏表示:只依赖于支持向量,模型表示高效
  3. 核方法的灵活性:不必显式计算高维特征,能够处理各种复杂非线性模式
  4. 结构风险最小化:通过最大化边际来保证泛化能力
  5. 全局最优解:与神经网络不同,SVM的优化问题是凸的,保证了全局最优解

SVM在机器学习中的地位不仅因其在实际应用中的强大表现,更在于它将复杂的分类问题转化为优雅的数学形式,展示了应用数学之美。

尽管深度学习在近年来表现出色,SVM依然在中小规模数据集、特征明确的问题、高维数据分析等领域保持其价值,特别是当训练数据有限或对模型理解至关重要时。


SVM的本质:从直观理解到数学原理
http://xcq.ink/2023/06/03/SVM的本质:从直观理解到数学深度/
作者
Xander Xu
发布于
2023年6月3日
许可协议