支持向量机(SVM)核心原理与实战求解详解

1. 支持向量机核心思想与数学基础

支持向量机（SVM）作为机器学习中的经典算法，其核心思想是通过寻找最优分类超平面来实现数据分类。与感知器和逻辑回归不同，SVM不仅追求分类正确，更注重分类间隔的最大化，这种特性使其具有优秀的泛化能力。

1.1 间隔最大化的数学表达

给定训练数据集D={(x₁,y₁),(x₂,y₂),...,(xₙ,yₙ)}，其中xᵢ∈Rⁿ，yᵢ∈{-1,1}。分类超平面可表示为wᵀx + b = 0。对于线性可分数据，存在多个能将两类数据分开的超平面，而SVM选择的是具有最大几何间隔的那个。

几何间隔的定义为：
γ = min(γ₁, γ₂, ..., γₙ)
其中γᵢ = yᵢ(wᵀxᵢ + b)/||w||

因此，最大化间隔等价于：
max (2/||w||)
s.t. yᵢ(wᵀxᵢ + b) ≥ 1, ∀i

为方便求解，通常转化为等效的凸优化问题：
min (1/2)||w||²
s.t. yᵢ(wᵀxᵢ + b) ≥ 1, ∀i

注意：这里使用1/2||w||²而非||w||是为了后续求导方便，且不影响最优解的位置。

1.2 拉格朗日对偶问题

引入拉格朗日乘子αᵢ ≥ 0，构造拉格朗日函数：
L(w,b,α) = (1/2)||w||² - Σαᵢ[yᵢ(wᵀxᵢ + b) - 1]

原始问题为min_{w,b} max_α L(w,b,α)，其对偶问题为max_α min_{w,b} L(w,b,α)。通过求解对偶问题，我们可以：

1. 自然地引入核技巧处理非线性问题
2. 减少优化变量数量（从d+1个到n个）
3. 更容易识别支持向量（αᵢ > 0的样本）

2. 例题详细求解过程

2.1 问题描述与数据准备

给定训练样本：
正例：x₁=(3,3)ᵀ, x₂=(4,3)ᵀ (y=+1)
负例：x₃=(1,1)ᵀ (y=-1)

我们需要找到最优分类超平面wᵀx + b = 0，使得间隔最大化。

2.2 构建拉格朗日函数

根据前述理论，构建拉格朗日函数：
L(w,b,α) = (1/2)(w₁² + w₂²) - [α₁(w₁x₁₁ + w₂x₁₂ + b - 1) + α₂(w₁x₂₁ + w₂x₂₂ + b - 1) + α₃(-w₁x₃₁ - w₂x₃₂ - b - 1)]

代入具体数值：
L = (1/2)(w₁² + w₂²) - [α₁(3w₁ + 3w₂ + b - 1) + α₂(4w₁ + 3w₂ + b - 1) + α₃(-w₁ - w₂ - b - 1)]

2.3 求导并建立KKT条件

对w₁,w₂,b求偏导并令其为零：

∂L/∂w₁ = w₁ - 3α₁ - 4α₂ + α₃ = 0 ⇒ w₁ = 3α₁ + 4α₂ - α₃
∂L/∂w₂ = w₂ - 3α₁ - 3α₂ + α₃ = 0 ⇒ w₂ = 3α₁ + 3α₂ - α₃
∂L/∂b = -α₁ - α₂ + α₃ = 0 ⇒ α₃ = α₁ + α₂

将w和b的表达式代入拉格朗日函数，得到仅关于α的对偶问题：

W(α) = (1/2)(w₁² + w₂²) - (α₁ + α₂ + α₃)
= 4α₁² + (13/2)α₂² + 10α₁α₂ - 2α₁ - 2α₂

约束条件：
α₁ + α₂ - α₃ = 0
α₁, α₂, α₃ ≥ 0

2.4 求解对偶问题

利用α₃ = α₁ + α₂消去α₃，得到简化问题：

min W(α) = 4α₁² + (13/2)α₂² + 10α₁α₂ - 2α₁ - 2α₂
s.t. α₁, α₂ ≥ 0

求导寻找极值点：
∂W/∂α₁ = 8α₁ + 10α₂ - 2 = 0
∂W/∂α₂ = 13α₂ + 10α₁ - 2 = 0

解得：α₁ = 3/2, α₂ = -1

由于α₂ = -1不满足非负约束，最优解必在边界上：

情况1：设α₁ = 0
W = (13/2)α₂² - 2α₂
极小点在α₂ = 2/13，W = -2/13

情况2：设α₂ = 0
W = 4α₁² - 2α₁
极小点在α₁ = 1/4，W = -1/4

比较两种情况，第二种的W值更小，因此最优解为：
α₁ = 1/4, α₂ = 0, α₃ = 1/4

2.5 确定支持向量与分类超平面

根据KKT条件，只有αᵢ > 0对应的样本才是支持向量。本例中：

• x₁(α₁=1/4 > 0)
• x₃(α₃=1/4 > 0)

计算w：
w₁ = 3*(1/4) + 40 - (1/4) = 1/2
w₂ = 3(1/4) + 3*0 - (1/4) = 1/2

计算b：
利用x₁的支持向量条件：y₁(wᵀx₁ + b) = 1
1*[(1/2)*3 + (1/2)*3 + b] = 1 ⇒ b = -2

最终分类超平面：
(1/2)x₁ + (1/2)x₂ - 2 = 0

决策函数：
f(x) = sign((1/2)x₁ + (1/2)x₂ - 2)

3. 关键概念深度解析

3.1 拉格朗日乘子法的直观理解

拉格朗日乘子αᵢ可以理解为每个样本点对最终分类器影响的"权重"。在SVM中：

• αᵢ = 0：对应样本不影响分类器
• 0 < αᵢ < C：对应样本位于间隔边界上（支持向量）
• αᵢ = C：对应样本位于间隔内部或分类错误（软间隔情况）

在例题中，只有x₁和x₃的αᵢ > 0，说明它们决定了最终的分类超平面位置。

3.2 KKT条件的实际意义

KKT条件确保了原始问题与对偶问题解的一致性。最重要的互补松弛条件：

αᵢ[yᵢ(wᵀxᵢ + b) - 1] = 0

这意味着：

1. 如果αᵢ > 0，则yᵢ(wᵀxᵢ + b) = 1（支持向量）
2. 如果yᵢ(wᵀxᵢ + b) > 1，则αᵢ = 0（非支持向量）

3.3 对偶问题的优势

相比原始问题，对偶形式具有以下优势：

1. 计算效率：当特征维度d远大于样本数n时更高效
2. 核技巧：只需计算xᵢᵀxⱼ，便于引入核函数
3. 支持向量识别：通过αᵢ值可直接识别关键样本

4. 实际应用中的注意事项

4.1 线性不可分情况的处理

当数据线性不可分时，可采用以下方法：

1. 软间隔SVM：引入松弛变量ξᵢ，允许部分样本分类错误
   min (1/2)||w||² + CΣξᵢ
   s.t. yᵢ(wᵀxᵢ + b) ≥ 1 - ξᵢ, ξᵢ ≥ 0

2. 核方法：通过非线性映射φ(x)将数据映射到高维空间
   K(xᵢ,xⱼ) = φ(xᵢ)ᵀφ(xⱼ)

常见核函数：

• 多项式核：K(x,z) = (γxᵀz + r)^d
• RBF核：K(x,z) = exp(-γ||x-z||²)

4.2 参数选择经验

1. 正则化参数C：

   • 较小C：允许更多分类错误，间隔较大
   • 较大C：严格要求分类正确，间隔较小
   • 通常通过交叉验证选择

2. 核参数（如RBF核的γ）：

   • 较大γ：模型更复杂，可能过拟合
   • 较小γ：模型更简单，可能欠拟合

4.3 计算优化技巧

对于大规模数据，直接求解可能效率低下，可采用：

1. SMO算法：每次优化两个αᵢ，保持其他固定
2. 随机梯度下降：适用于大规模线性SVM
3. 采样方法：先在小样本上训练，再逐步增加支持向量

5. 扩展与变种

5.1 多类SVM

原始SVM是二分类器，多类问题可通过以下方式解决：

1. 一对多（One-vs-Rest）：训练K个分类器
2. 一对一（One-vs-One）：训练K(K-1)/2个分类器
3. 直接多类：修改目标函数同时考虑所有类

5.2 支持向量回归（SVR）

SVM的回归版本，目标是找到一个函数f(x)，使得大部分样本位于f(x)±ε的"管道"内。优化问题为：
min (1/2)||w||² + CΣ(ξᵢ + ξᵢ*)
s.t. -ε - ξᵢ* ≤ yᵢ - wᵀxᵢ - b ≤ ε + ξᵢ
ξᵢ, ξᵢ* ≥ 0

5.3 结构化SVM

处理结构化输出问题（如序列标注、解析树等），通过定义联合特征映射φ(x,y)和损失函数Δ(y,ŷ)，优化：
min (1/2)||w||² + CΣξᵢ
s.t. wᵀφ(xᵢ,yᵢ) - wᵀφ(xᵢ,y) ≥ Δ(yᵢ,y) - ξᵢ, ∀y ≠ yᵢ
ξᵢ ≥ 0

在实际应用中，我发现理解SVM的几何直观比死记公式更重要。通过可视化工具观察不同参数下分类边界和支持向量的变化，能更直观地掌握算法行为。此外，对于中小规模数据集，libsvm或sklearn.svm已经提供了高效实现，重点应放在特征工程和参数调优上。