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

2023-12-28 10:24:53

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

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

软间隔思想的由来

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

软间隔的引入

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

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

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

  2. 约束条件：
    考虑函数间隔大于等于 1 的约束条件，以及松弛变量 ξ \boldsymbol{\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 = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ? ? , ( x N , y N ) } 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?)}, 其中, x i ∈ X = R n , y i ∈ x_i \in \mathcal{X}=\mathbf{R}^n, y_i \in xi?∈X=Rn,yi?∈ Y = { ? 1 , + 1 } , i = 1 , 2 , ? ? , N \mathcal{Y}=\{-1,+1\}, \quad i=1,2, \cdots, N Y={?1,+1},i=1,2,?,N;
输出: 分离超平面和分类决策函数.
(1) 选择惩罚参数 C > 0 C>0 C>0, 构造并求解凸二次规划问题
min ? α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ? x j ) ? ∑ i = 1 N α i ?s.t.? ∑ i = 1 N α 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 = 1 N α i ? y i x i w^*=\sum_{i=1}^N \alpha_i^* y_i x_i w?=∑i=1N?αi??yi?xi?

选择 α ? \alpha^* α? 的一个分量 α j ? \alpha_j{ }^* αj?? 适合条件 0 < α j ? < C 0<\alpha_j^*<C 0<αj??<C, 计算
b ? = y j ? ∑ i = 1 N y i α i ? ( x i ? x j ) 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 ? = 0 w^* \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?)

文章来源:https://blog.csdn.net/Kilig___/article/details/135247140
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。