SVM中的软间隔问题

我们今天将详细讨论支持向量机（SVM）软间隔问题的数学推导，特别是引入损失函数后的优化问题。软间隔 SVM 引入了损失函数和松弛变量，使得它可以处理不可分数据，即允许某些数据点在分类时出现错误或违反间隔条件。

1. 软间隔 SVM 的基本思想

首先，回顾一下软间隔 SVM 的基本思想。在现实数据中，完全线性可分的情况较少，或者即使通过核函数映射到高维空间，也可能出现部分数据无法线性可分的情况。软间隔 SVM 允许一些数据点越过间隔边界或被错误分类，即允许违反硬间隔 SVM 的严格分类规则。

为了描述这些错误，我们引入了松弛变量 ${\xi }_i$ 来表示第 $i$ 个样本违反间隔的程度，并引入一个损失函数来量化这些错误。目标是最小化间隔最大化和分类错误之间的折中。

2. 软间隔 SVM 的优化问题

软间隔 SVM 的优化目标是：

1. 最大化分类间隔，即最小化 $\Vert w{\Vert }^2$；
2. 最小化分类错误，即引入损失函数来惩罚违反分类间隔的样本。

为了结合这两个目标，我们引入一个平衡参数 $C$，用来控制间隔最大化和分类错误之间的折中。

原始优化问题（Primal Problem）

首先，给定一个训练集 $\{(x_i,y_i){\}}_{i=1}^n$，其中 $x_i\in {\mathbb{R}}^d$ 表示第 $i$ 个样本， y i ∈ { − 1 , 1 } y_i \in \{-1, 1\} yi​∈{−1,1} 表示其类别标签。软间隔 SVM 的优化问题可以表示为：

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i$$

其中：

• $\frac{1}{2}\Vert w{\Vert }^2$ 是为了最大化间隔；
• $C{\sum }_{i=1}^n{\xi }_i$ 是为了惩罚分类错误（通过损失函数的形式体现分类误差），$C$ 控制了分类误差的权重；
• ${\xi }_i\ge 0$ 是松弛变量，表示样本违反分类间隔的程度。

约束条件：

为了使 SVM 能正确分类样本，我们要求每个样本 $x_i$ 满足：
$$y_i(w^T{x}_i+b)\ge 1-{\xi }_i,\forall i$$

• 当 ${\xi }_i=0$ 时，样本严格位于分类间隔外；
• 当 $0<{\xi }_i<1$ 时，样本位于分类间隔内部，但没有被错误分类；
• 当 ${\xi }_i\ge 1$ 时，样本被错误分类。

同时，要求 ${\xi }_i\ge 0$，以确保松弛变量的非负性。

3. 引入损失函数

为了处理分类错误和违反分类间隔的样本，SVM 引入了一种特殊的损失函数，称为合页损失函数（Hinge Loss），其定义如下：

合页损失函数：

$$L(y_i,f(x_i))=\max (0,1-y_{i}f(x_i))$$

这里，$f(x_i)=w^T{x}_i+b$ 是分类器的预测函数，$y_i$ 是真实标签。

• 当 $y_{i}f(x_i)\ge 1$ 时，样本被正确分类且位于间隔外，损失为零；
• 当 $y_{i}f(x_i)<1$ 时，样本位于间隔内部或被错误分类，损失为 $1-y_{i}f(x_i)$。

合页损失函数可以通过优化问题中的松弛变量 ${\xi }_i$ 表达为：
$${\xi }_i=\max (0,1-y_{i}f(x_i))$$

因此，我们可以将软间隔 SVM 的目标函数重新写成如下形式：

4. 软间隔 SVM 的优化问题（引入损失函数后的形式）

引入合页损失函数后，软间隔 SVM 的优化问题为：

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n\max (0,1-y_i(w^T{x}_i+b))$$

该目标函数包含两个部分：

1. $\frac{1}{2}\Vert w{\Vert }^2$：控制分类间隔，倾向于最大化间隔；
2. $C{\sum }_{i=1}^n\max (0,1-y_{i}f(x_i))$：合页损失函数，惩罚分类错误。

5. 对偶问题的推导

为了方便求解，我们通常将 SVM 的原始问题转化为对偶问题。对偶问题的推导步骤如下：

构造拉格朗日函数

首先，我们构造拉格朗日函数，引入拉格朗日乘子 ${\alpha }_i\ge 0$ 来处理不等式约束 $y_i(w^T{x}_i+b)\ge 1-{\xi }_i$，并引入乘子 ${\mu }_i\ge 0$ 来处理松弛变量的非负性约束 ${\xi }_i\ge 0$：

$$L(w,b,\xi ,\alpha ,\mu )=\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i-\sum _{i=1}^n{\alpha }_i[y_i(w^T{x}_i+b)-1+{\xi }_i]-\sum _{i=1}^n{\mu }_i{\xi }_i$$

求偏导并消去变量

为了得到对偶问题，我们需要对拉格朗日函数求偏导，并消去原始变量 $w$、$b$ 和 ${\xi }_i$。

1. 对 $w$ 求导：
   $$\frac{\partial L}{\partial w}=w-\sum _{i=1}^n{\alpha }_i{y}_i{x}_i=0$$
   得：
   $$w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i$$

2. 对 $b$ 求导：
   $$\frac{\partial L}{\partial b}=-\sum _{i=1}^n{\alpha }_i{y}_i=0$$
   得：
   $$\sum _{i=1}^n{\alpha }_i{y}_i=0$$

3. 对 ${\xi }_i$ 求导：
   $$\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0$$
   得：
   $${\alpha }_i\le C$$

得到对偶优化问题

将这些结果代入拉格朗日函数中，消去 $w$、$b$ 和 ${\xi }_i$ 后，对偶问题可以表示为：

$$\underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

约束条件：

1. $0\le {\alpha }_i\le C$
2. ${\sum }_{i=1}^n{\alpha }_i{y}_i=0$

在对偶问题中，优化变量是 ${\alpha }_i$，并且拉格朗日乘子 ${\alpha }_i$ 受到约束 $0\le {\alpha }_i\le C$，这与正则化参数 $C$ 直接相关，$C$ 控制了软间隔的宽松程度。

6. 优化后的决策函数

一旦我们通过求解对偶问题得到了拉格朗日乘子 ${\alpha }_i$，分类器的最终决策函数可以写成：

$$f(x)=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i^{T}x+b$$

原文地址：https://blog.csdn.net/handsomeboysk/article/details/143067186

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！