模式识别与机器学习-SVM（带软间隔的支持向量机）

SVM（带软间隔的支持向量机）

• 软间隔思想的由来
• 软间隔的引入

谨以此博客作为复习期间的记录。

软间隔思想的由来

在上一篇博客中，回顾了线性可分的支持向量机,但在实际情况中，很少有完全线性可分的情况，大部分线性可分的情况都是整体线性可分，个别样本点无法线性分割开。因此就要避免这极个别样本点对分割平面产生的影响。
线性可分支持向量机

软间隔的引入

在分类过程中，允许极个别数据点“越界”，如何在目标函数中体现这一点呢？
软间隔支持向量机（Soft Margin Support Vector Machine）的数学形式可以通过修改支持向量机（SVM）的优化目标函数和约束条件来实现。软间隔允许一些数据点越界，引入了松弛变量来处理这些点。

首先，我们考虑软间隔的目标函数和约束条件：

1. 目标函数：
   最小化目标函数，同时考虑间隔的最大化和误分类点的惩罚，即：
   min⁡w,b,ξ1 2∥w ∥ 2+C ∑ i=1N ξ i\min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^{N} \xi_i w,b,ξmin​21​∥w∥2+Ci=1∑N​ξi​
   这里 $\mathbf{w}$ 是超平面的法向量，$b$ 是截距，$\mathbf{\xi }$ 是松弛变量，$C>0$ 是一个超参数，用于控制对误分类点的惩罚程度。

2. 约束条件：
   考虑函数间隔大于等于 1 的约束条件，以及松弛变量 $\mathbf{\xi }$ 的非负性约束：
   y i(w⋅ x i+b)≥1− ξ i, i=1,2,…,Nξ i≥0, i=1,2,…,N\begin{align*} & y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 – \xi_i, \quad i = 1, 2, \dots, N \\ & \xi_i \geq 0, \quad i = 1, 2, \dots, N \end{align*} ​yi​(w⋅xi​+b)≥1−ξi​,i=1,2,…,Nξi​≥0,i=1,2,…,N​

线性支持向量机学习算法
输入: 训练数据集 T = { ( x1, y1), ( x2, y2),⋯   , ( xN, yN)} T=\left\{\left(x_1, y_1\right),\left(x_2, y_2\right), \cdots,\left(x_N, y_N\right)\right\}T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}, 其中, xi∈ X = Rn, yi∈x_i \in \mathcal{X}=\mathbf{R}^n, y_i \inxi​∈X=Rn,yi​∈ $\mathcal{Y}=\{-1,+1\},i=1,2,\cdots ,N$;
输出: 分离超平面和分类决策函数.
(1) 选择惩罚参数 $C>0$, 构造并求解凸二次规划问题
min ⁡α1 2 ∑ i=1N ∑ j=1N α i α j y i y j ( xi⋅ xj)− ∑ i=1N α is.t. ∑ i=1N α i y i=0 0⩽ α i⩽C, i=1,2,⋯   ,N\begin{aligned} \min _\alpha & \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j\left(x_i \cdot x_j\right)-\sum_{i=1}^N \alpha_i \\ \text { s.t. } & \sum_{i=1}^N \alpha_i y_i=0 \\ & 0 \leqslant \alpha_i \leqslant C, \quad i=1,2, \cdots, N \end{aligned} αmin​s.t.​21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​i=1∑N​αi​yi​=00⩽αi​⩽C,i=1,2,⋯,N​

求得最优解 α∗=( α1 ∗, α2 ∗, ⋯  , αN ∗)T \alpha^*=\left(\alpha_1{ }^*, \alpha_2{ }^*, \cdots, \alpha_N{ }^*\right)^{\mathrm{T}}α∗=(α1​∗,α2​∗,⋯,αN​∗)T.
(2) 计算 w∗= ∑ i = 1Nαi∗yixi w^*=\sum_{i=1}^N \alpha_i^* y_i x_iw∗=∑i=1N​αi∗​yi​xi​

选择 α∗ \alpha^*α∗ 的一个分量 αj ∗ \alpha_j{ }^*αj​∗ 适合条件 0 < αj∗< C0<\alpha_j^*<C0<αj∗​<C, 计算
b ∗= y j− ∑ i=1N y i α i ∗ ( xi⋅ xj)b^*=y_j-\sum_{i=1}^N y_i \alpha_i^*\left(x_i \cdot x_j\right) b∗=yj​−i=1∑N​yi​αi∗​(xi​⋅xj​)
(3) 求得分离超平面
w ∗⋅x+ b ∗=0w^* \cdot x+b^*=0 w∗⋅x+b∗=0

分类决策函数:
f(x)=sign⁡ ( w∗⋅ x + b∗)f(x)=\operatorname{sign}\left(w^* \cdot x+b^*\right) f(x)=sign(w∗⋅x+b∗)