盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

[学习笔记] [机器学习] 10. 支持向量机 SVM（SVM 算法原理、SVM API介绍、SVM 损失函数、SVM 回归、手写数字识别）

作者：盐析白兔 | 2024-06-20 18:48:34

踩

支持向量机

视频链接
数据集下载地址：无需下载

学习目标：

了解什么是 SVM 算法
掌握 SVM 算法的原理
知道 SVM 算法的损失函数
知道 SVM 算法的核函数
了解 SVM 算法在回归问题中的使用
应用 SVM 算法实现手写数字识别器

1. SVM 算法简介

学习目标：

了解 SVM 算法的定义
知道软间隔和硬间隔

1.1 SVM 算法导入

在很久以前的情人节，英雄要去救他的爱人，但魔鬼和他玩了一个游戏。魔鬼在桌子上似乎有规律放了两种颜色的球，说：“你用一根棍分开它们。要求：尽量在放更多球之后，仍然适用。”。

在这里插入图片描述

于是英雄这样放。似乎干的不错？

在这里插入图片描述

然后魔鬼又在桌上放了更多的球，但似乎有一个球站错了阵营。

在这里插入图片描述

那怎么办？

英雄试图通过在棍子的两侧留出尽可能大的间隙来将棍子放在最佳位置。

在这里插入图片描述

SVM 就是试图把棍放在最佳位置，好让在棍的两边有尽可能大的间隙

现在即使魔鬼放了更多的球，棍仍然是一个好的分界线。

在这里插入图片描述

然后，在 SVM 工具箱中有另一个更加重要的技巧（trick）。魔鬼看到英雄已经学会了一个trick，于是魔鬼给了英雄一个新的挑战。

在这里插入图片描述

现在，英雄没有棍可以很好帮他分开两种球了，现在怎么办呢？

当然像电影中一样，英雄桌子一拍，球飞到空中。然后，凭借英雄的轻功抓起一张纸，插到了两种球的中间。

在这里插入图片描述

现在，从魔鬼的角度看这些球，这些球看起来像是被一条曲线分开了。

在这里插入图片描述

再之后，无聊的大人们，把上面的物体起了别名：

球 —— 「data」数据
棍子 ―― 「classifier」分类器
最大间隙 ―― 「optimization」最优化方法
拍桌子 ―― 「kernelling」核方法
纸 ―― 「hyperplane」超平面

案例来源: Support Vector Machines explained well

支持向量机直观感受：SVM with polynomial kernel visualization

1.2 SVM 定义

SVM 全称是 Supported Vector Machine（支持向量机），即寻找到一个超平面使样本分成两类，并且间隔最大。

SVM 能够执行①线性或非线性分类、②回归，甚至是③异常值检测任务。它是机器学习领域最受欢迎的模型之一。

SVM 特别适用于中小型复杂数据集的分类。

Q：SVM 只能做二分类吗？
A：SVM 最初是为二分类问题设计的，但它也可以用于多分类问题。目前，构造 SVM 多类分类器的方法主要有两类：一类是直接法，直接在目标函数上进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。另一类是间接法，主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有 one-against-one（一对一）和 one-against-all（一对多）两种。

在这里插入图片描述

1.3 超平面最大间隔介绍

在这里插入图片描述

上左图显示了三种可能的线性分类器的决策边界：

虚线（模型）的表现非常糟糕，甚至都无法正确实现分类。
其余两个实线（模型）在这个训练集上表现堪称完美。但它们的决策边界与实例过于接近，导致在面对新实例时，表现可能不会太好。

对于左图的两个实现模型而言，如果数据集稍微有一点小变动，那么就分错了，所以泛化性能可能有些不理想

右图中的实线代表 SVM 分类器的决策边界（具体是怎么分开的），两条虚线之间的距离表示最大间隔。实现模型不仅分离了两个类别，且尽可能远离最近的训练实例。

SVM 不仅仅要找到划分的线，而且要求线离两个实例的举例越大越好，这样就有足够的距离，从而提升对新数据集的包容。

1.4 硬间隔和软间隔

1.4.1 硬间隔分类

在上面我们使用超平面进行分割数据的过程中，如果我们严格地让所有实例都不在最大间隔之间，并且位于正确的一边，这就是硬间隔分类。

简单来说，硬间隔就是要求百分百分对！

硬间隔分类有两个问题：

它只在数据是线性可分离的时候才有效
它对异常值非常敏感

举例：当鸢尾花数据存在一个额外异常值时，

左图的数据根本找不出硬间隔（没有办法保证百分百分对）
右图最终显示的决策边界与我们之前所看到的无异常值时的决策边界也大不相同，可能无法很好地泛化

在这里插入图片描述

1.4.2 软间隔分类

要避免硬间隔因异常值出现的不可分的问题，最好使用更灵活的模型。目标是：尽可能在保持最大间隔宽阔和限制间隔违例（即位于最大间隔之上，甚至在错误的一边的实例）之间找到良好的平衡（tradeoff），这就是软间隔分类。

间隔违例：指位于最大间隔之上，甚至在错误的一边的实例。

简单来说，硬间隔（hard margin）是指在 SVM 中，我们假设数据是线性可分的，也就是说，我们可以找到一个超平面将不同类别的数据完全分开。但是，在现实世界中，数据往往不是线性可分的。为了解决这个问题，我们引入了软间隔（soft margin）的概念。软间隔允许一些数据点被错误分类，以便更好地拟合数据。这样，我们就可以在最大化间隔的同时，尽量减少不满足约束的样本数量。

在 Scikit-Learn 的 SVM 类中，可以通过超参数 C 来控制这个平衡：

C 值越小，则间隔越宽，但是间隔违例也会越多

超参数 C 我们可以理解为是一个惩罚项。C 越大，惩罚越重，间隔违例就越少，说明间隔宽度越小；C 越小，惩罚越轻，间隔违例就越多，说明间隔宽度就越大。

在这里插入图片描述

上图显示了在一个非线性可分离数据集上，两个软间隔 SVM 分类器各自的决策边界和间隔。

左边使用了高 C 值，分类器的错误样本（间隔违例）较少，但是间隔也较小。
右边使用了低 C 值，间隔大了很多，但是位于间隔上的实例也更多。

看起来第二个分类器的泛化效果更好，因为大多数间隔违例实际上都位于决策边界正确的一边，所以即便是在该训练集上，它做出的错误预测也会更少。

小结：

SVM 算法定义【了解】：寻找到一个超平面使样本分成两类，并且间隔最大。
硬间隔和软间隔【知道】
- 硬间隔：要求百分百分对
  - 只有在数据是线性可分离的时候才有效
  - 对异常值非常敏感
- 软间隔：尽可能在保持最大间隔宽阔和限制间隔违例之间找到良好的平衡，允许有分错的样本

2. SVM 算法 API 初步使用

学习目标：

知道 SVM 算法 API 的用法

from sklearn import svm
1

作用：from sklearn import svm 这行代码是从 sklearn 库中导入 svm 模块。svm 模块中主要有 LinearSVC、NuSVC 和 SVC 三种方法，用于支持向量机分类（这三种方法都是基于支持向量机思想的分类器，但它们在模型的选择和参数调整方面有所不同。选择哪种方法主要取决于数据的特点和问题的需求）。
1. LinearSVC：LinearSVC 是一种线性支持向量机分类器（Linear Support Vector Classifier）。它使用线性核函数，适用于解决线性可分的问题。它的目标是找到一个超平面，将不同类别的样本分隔开。LinearSVC在训练过程中使用了一系列的优化算法，以最小化分类错误率。
2. NuSVC：NuSVC 是一种非线性支持向量机分类器（Nu-Support Vector Classifier），它使用了非线性核函数，适用于解决非线性可分的问题。NuSVC 通过使用核函数将数据映射到高维空间，使得在高维空间中可以找到一个线性超平面来分隔不同的类别。NuSVC 在训练过程中通过调整参数 nu 来平衡支持和错分样本的数量。
3. SVC：SVC 是一种支持向量机分类器（Support Vector Classifier），它提供了更灵活的核函数选择和参数调整。SVC 可以根据不同的问题选择适合的核函数，例如线性核函数、多项式核函数、高斯核函数等。此外，SVC 还提供了参数调整的灵活性，例如正则化参数、错误容忍度等。通过调整这些参数，可以更好地适应不同类型的数据和问题。
方法一：LinearSVC 方法（Linear Support Vector Classification，意为线性支持向量分类）
- 作用：线性支持向量分类器，用于处理线性可分的数据集。它使用线性核函数，可以处理大规模的数据集。
- 参数：
  - penalty: 正则化参数，可选值为 ‘l1’ 和 ‘l2’，仅适用于 LinearSVC。
  - loss: 损失函数，可选值为 ‘hinge’ 和 ‘squared_hinge’。其中
    - ‘hinge’ 是 SVM 的标准损失
    - ‘squared_hinge’ 是 ‘hinge’ 的平方
  - dual: 是否转化为对偶问题求解，默认为 True。
  - tol: 残差收敛条件，默认为 0.0001。
  - C: 惩罚系数，用来控制损失函数的惩罚系数。
  - multi_class: 负责多分类问题中分类策略制定，可选值为 ‘ovr’ 和 ‘crammer_singer’。
  - fit_intercept: 是否计算截距。
  - class_weight: 用来处理不平衡样本数据的，可以直接以字典的形式指定不同类别的权重，也可以使用 ‘balanced’ 参数值。
  - verbose: 是否冗余，默认为 False。
  - random_state: 随机种子的大小。
  - max_iter: 最大迭代次数，默认为 1000。
- 返回值：
  - coef_: 各特征的系数（重要性）。
  - intercept_: 截距的大小（常数值）。
- 方法：
  - decision_function(X): 获取数据集 X 到分离超平面的距离。
  - fit(X, y): 在数据集 (X,y) 上使用 SVM 模型。
  - get_params([deep]): 获取模型的参数。
  - predict(X): 预测数据值 X 的标签。
  - score(X,y): 返回给定测试集和对应标签的平均准确率。
方法二：NuSVC 方法（ Nu-Support Vector Classification，意为 Nu-支持向量分类）
- 作用：是一种支持向量分类器，它允许用户控制支持向量的数量。它可以处理非线性可分的数据集，但对于大规模的数据集，拟合时间可能会很长。
- 参数：
  - nu: 训练误差部分的上限和支持向量部分的下限，取值在（0，1）之间，默认为 0.5。
  - kernel: 核函数，可选值为 ‘linear’、‘poly’、‘rbf’、‘sigmoid’ 和 ‘precomputed’。
  - degree: 当核函数为多项式核函数时，用来控制函数的最高次数。
  - gamma: 核函数系数，默认为 ‘auto’。
  - coef0: 核函数常数值，只有 ‘poly’ 和 ‘sigmoid’ 核函数有，默认值为 0。
  - shrinking: 是否采用启发式收缩，默认为 True。
  - probability: 是否使用概率估计，默认为 False。
  - tol: 停止拟合容忍度，默认为 0.001。
  - cache_size: 缓冲大小，默认为 200MB。
  - class_weight: 各类权重，与其他模型中参数含义类似，也是用来处理不平衡样本数据的，可以直接以字典的形式指定不同类别的权重，也可以使用 ‘balanced’ 参数值。
  - verbose: 是否冗余，默认为 False。
  - max_iter: 最大迭代次数，默认为 -1。
  - decision_function_shape: 与 ‘multi_class’ 参数含义类似。
  - random_state: 随机种子的大小。
- 返回值：
  - support_: 以数组的形式返回支持向量的索引。
  - support_vectors_: 返回支持向量。
  - n_support_: 每个类别支持向量的个数。
  - dual_coef_: 支持向量系数。
  - coef_: 每个特征系数（重要性），只有核函数是 LinearSVC 的时候可用。
  - intercept_: 截距值（常数值）。
方法三：SVC 方法（C-Support Vector Classification，意为 C-支持向量分类）
- 作用：是一种支持向量分类器，它可以处理非线性可分的数据集。与 NuSVC 类似，它也可以使用不同的核函数来处理非线性问题，但对于大规模的数据集，拟合时间可能会很长。
- 参数：
  - C: 惩罚系数。与 NuSVC 方法基本一致，唯一区别就是损失函数的度量方式不同（NuSVC 中的 nu 参数和 SVC 中的 C 参数）。
- 方法：
  - 与上述相同。

举例：

from sklearn import svm


# 1. 准备数据
X = [[0, 0], [1, 1]]
y = [0, 1]

# 2. 定义模型
clf = svm.SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0, 
              decision_function_shape="ovr", degree=3, gamma="scale", kernel="rbf", 
              max_iter=-1, probability=False, random_state=None, shrinking=True, 
              tol=0.001, verbose=False)

# 3. 模型训练
clf.fit(X, y)

# 4. 预测
clf.predict([[2, 2]])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

array([1])
1

3. SVM 算法原理

学习目标：

知道 SVM 中线性可分支持向量机
知道 SVM 中目标函数的推导过程
了解朗格朗日乘子法、对偶问题
知道 SVM 中目标函数的求解过程

3.1 定义输入数据

假设给定一个特征空间上的训练集为：

$T = \{ (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) \}$

\begin{aligned} x_{i} \in R^{n} (实 数) \\ y_{i} \in {+ 1, - 1} \\ i = 1, 2, . . ., N \end{aligned}

$\begin{aligned} & x_i \in R^n(实数)\\ & y_i \in \{ +1, -1 \}\\ & i = 1, 2, ..., N \end{aligned}$

x_{i} \in R^{n} (实数) y_{i} \in {+ 1, - 1} i = 1, 2, ..., N

其中， $x_i, y_i)$ 称为样本点。

$x_i$ 为第 $i$ 个实例（样本）
$y_i$ 为 $x_i$ 的标记：
- 当 $y_i=+1$ 时， $x_i$ 为正例
- 当 $y_i = -1$ 时， $x_i$ 为负例

Q：为什么正负用 $(- 1, 1)$ 表示呢？
A：其实这里没有太多原理，就是一个标记，你也可以用 $(2, - 3)$ 来标记，只是为了方便。
使用 $(- 1, 1)$ 则在 $\frac{y_i}{y_j} = y_i * y_j$ 的过程中刚好可以相等，便于之后的计算。

3.2 线性可分支持向量机

给定了上面提出的线性可分训练数据集，通过间隔最大化得到分离超平面，为：

$w^T\Phi(x) + b$

其中：

$y (x)$ 表示样本 $x$ 到分离超平面的距离。

相应的分类决策函数为：

$\mathrm{sign}(w^T\Phi(x) + b)$

其中 $\mathrm{sign}$ 函数表示符号函数。

以上的决策函数就称为线性可分支持向量机。

这里解释一下 $\Phi$ ：

这是某个确定的特征空间转换函数，它的作用是将 $x$ 映射到更高的维度，它有一个以后我们经常会见到的专有称号“核函数（Kernel Function）”。

比如我们看到的特征有 2 个，即 $x_1, x_2$ 组成最先见到的线性函数 $w_1x_1 + w_2 x_2$ 。

但也许这两个特征并不能很好地描述数据，于是我们进行维度的转化，转化到五维特征空间，变成：

$w_1x_1 + w_2x_2 + w_3x_1x_2 + w_4x_1^2 + w_5x_2^2$

于是我们多了三个特征。

以上就是笼统地描述 $\Phi$ 是如何对 $x$ 映射的。

$\Phi$ 最简单的映射就是：

$\Phi(x) = x$

即不进行任何映射。

以上就是线性可分支持向量机的模型表达式。我们要去求出这样一个模型，或者说这样一个超平面 $y (x)$ ，它能够最优地分离两个集合。

其实也就是我们要去求一组参数 $(w, b)$ 使其构建的超平面函数能够最优地分离两个集合。

核函数 $\Phi$ 是已知的，不需要我们求。

如下就是一个最优超平面：

在这里插入图片描述

硬间隔分类

又比如说这样：

在这里插入图片描述

阴影部分是一个“过渡带”，“过渡带”的边界是集合中离超平面最近的样本点落在的地方。

软间隔分类

3.3 SVM 的计算过程与算法步骤

3.3.1 推导目标函数

我们知道了支持向量机是个什么东西了。现在我们要去寻找这个支持向量机，也就是寻找一个最优的超平面。于是我们要建立一个目标函数。那么如何建立呢？

再来看一下我们的超平面表达式：

$w^T\Phi(x) + b$

其中 $y (x)$ 表示样本 $x$ 到分离超平面的距离。

为了方便，我们让核函数不进行映射，即 $\Phi(x) = x$ 。那么在样本空间中，划分超平面可通过如下线性方程来描述：

$w^Tx+b = 0$

我们知道：

$w=(w_1, w_2,..., w_d)$ 为法向量，决定了超平面的方向
$b$ 为位移项，决定了超平面和原点之间的距离

要让点到线的距离最近，要垂直，所以称为法向量。

显然，划分超平面可被法向量 $w$ 和位移 $b$ 确定，我们把其记为 $(w, b)$ 。

于是，样本空间中任意点 $x$ 到超平面 $(w, b)$ 的距离可写成：

$\frac{|w^Tx + b|}{||w||}$

$∣∣ w ∣∣$ 就是求向量 $w$ 的 2-范数。

范数的说明：【文间跳转】范数说明

假设超平面 $(w, b)$ 能将训练样本正确分类，即对于 $(x_i, y_i) \in D$ ：

若 $y_i = +1$ ，则有 $w^T x_i + b > 0$
若 $y_i = -1$ ，则有 $w^T x_i + b < 0$

令

{\begin{cases} w^{T} x_{i} + b \geq + 1, & y_{i} = + 1; \\ w^{T} x_{i} + b \leq - 1, & y_{i} = - 1; \end{cases}

$\begin{cases} w^Tx_i + b \ge +1, & y_i = +1; \\ w^Tx_i + b \le -1, & y_i = -1; \\ \end{cases}$

{w^{T} x_{i} + b \geq + 1, w^{T} x_{i} + b \leq - 1, y_{i} = + 1; y_{i} = - 1;

如图所示，距离超平面最近的几个训练样本点使上式等号成立，他们被称为“支持向量”，则两个异类支持向量到超平面的距离之和为： $\frac{2}{||w||}$ ，它被称为“间隔”。

支持向量才是真正决定间隔的数据。

在这里插入图片描述

想要找到具有最大间隔的划分超平面，也就是要找到能满足下式中约束的参数 $w$ 和 $b$ ，使得 $r$ 最大。

{\begin{cases} w^{T} x_{i} + b \geq + 1, & y_{i} = + 1 \\ w^{T} x_{i} + b \leq - 1, & y_{i} = - 1 \end{cases}

$\begin{cases} w^Tx_i + b \ge +1, & y_i = +1\\ w^Tx_i + b \le -1, & y_i = -1 \end{cases}$

{w^{T} x_{i} + b \geq + 1, w^{T} x_{i} + b \leq - 1, y_{i} = + 1 y_{i} = - 1

即：

$\underset{w, b}{\max} = \frac{2}{||w||} \quad \text{s.t.} \quad y_i(w^Tx_i + b) \ge +1, \quad i=1, 2, ..., m$

在数学公式中，“s.t.” 是 “such that” 的缩写，意为“使得”或“满足条件”。它用来引入一些限制条件或约束条件。
例如，在优化问题中，我们通常会看到这样的形式： $\min_x f(x) \quad \text{s.t.} \quad g(x) \leq 0$
这表示我们要最小化目标函数 $f (x)$ ，使得 $\leq 0$ 这个约束条件得到满足。

所以上式的意思就是：求得 $\frac{2}{||w||}$ 的最大值，使得 $y_i(w^Tx_i + b) \ge 1$ 满足。

显然，为了最大化间隔，仅需要最大化 $w||^{-1}$ ，这等价于最小化 $w||^2$ 。于是上式可以重写为：

$\underset{w, b}{\max} = \frac{1}{2}||w||^2 \quad \text{s.t.} \quad y_i(w^Tx_i + b) \ge +1, \quad i=1, 2, ..., m$

这就是支持向量机的基本型。

3.3.2 目标函数的求解

到这一步，终于把目标函数给建立起来了。那么下一步自然是去求目标函数的最优值。因为目标函数带有一个约束条件，所以我们可以用拉格朗日乘子法求解。

3.3.2.1 朗格朗日乘子法

拉格朗日乘子法（Lagrange multipliers）是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子，可将有 $d$ 个变量与 $k$ 个约束条件的最优化问题转化为具有 $d + k$ 个变量的无约束优化问题求解。

【文间跳转】拉格朗日乘子法举例复习

经过朗格朗日乘子法，我们可以把目标函数转换为：

$\alpha) = \frac{1}{2} ||w||^2 - \sum_{i=1}^n \alpha_i(y_i(w^T \cdot \Phi(x_i) + b) - 1)$

其中，上式后半部分：

$-\sum_{i=1}^n \alpha_i(y_i(w^T \cdot \Phi(x_i) + b) - 1) = 0$

走到这一步，这个目标函数还是不能开始求解，现在我们的问题是极小极大值问题。

3.3.2.2 对偶问题

我们要将其转换为对偶问题，变成极大极小值问题：

$\min \max L(w, b, \alpha) \quad 变为 \quad \underset{\alpha}{\max} \underset{w, b}{\min} L(w, b, \alpha)$

在最优化问题中，对偶问题是指通过转换原问题来求解最优目标函数的一种方法。通俗来讲，对偶问题就是使求解更加高效且目标函数值不变，通过先消去 $w$ ， $b$ ，得到关于 $\alpha$ 的函数，然后单独计算 $\alpha$ ，通过得到的 $\alpha$ 反求 $w$ ， $b$ ，最后获得超平面的参数，相比于先对 $\alpha$ 的不等式约束进行计算，对偶的方式使得计算更加便捷。

简单来说：对于一个函数而言，它的极大值中的极小值就是极小值中的极大值（注意，这句话其实是有很大问题的，这里主要是为了理解）。

参考资料: 运筹学_8 对偶问题概念转换方法

如何获取对偶函数？

首先我们对原目标函数的 $w$ 和 $b$ 分别求导：

原目标函数： $\alpha) = \frac{1}{2} ||w||^2 - \sum_{i=1}^n \alpha_i(y_i(w^T \cdot \Phi(x_i) + b) - 1)$
对 $w$ 求偏导： $\frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^n \alpha_i y_i \Phi(x_n)$
对 $b$ 求偏导： $\frac{\partial L}{\partial b} = 0 \rightarrow 0 = \sum_{i=1}^n \alpha_i y_i$

然后将以上 $w$ 和 $b$ 的求导函数重新代入原目标函数的 $w$ 和 $b$ 中，得到的就是原函数的对偶函数：

\begin{aligned} L (w, b, α) & = \frac{1}{2} | | w | |^{2} - \sum_{i = 1}^{n} α_{i} (y_{i} (w^{T} \cdot Φ (x_{i}) + b) - 1) \\ = \frac{1}{2} w^{T} w - w^{T} \sum_{i = 1}^{n} α_{i} y_{i} Φ (x_{i}) - b \sum_{i = 1}^{n} α_{i} y_{i} + \sum_{i = 1}^{n} α_{i} \\ = \frac{1}{2} w^{T} \sum_{i = 1}^{n} α_{i} y_{i} Φ (x_{i}) - w^{T} \sum_{i = 1}^{n} α_{i} y_{i} Φ (x_{i}) - b \cdot 0 + \sum_{i = 1}^{n} α \\ = \sum_{i = 1}^{n} α_{i} - \frac{1}{2} {(\sum_{i = 1}^{n} α_{i} y_{i} Φ (x_{i}))}^{T} \sum_{i = 1}^{n} α_{i} y_{i} Φ (x_{i}) \\ = \sum_{i = 1}^{n} α_{i} - \frac{1}{2} \sum_{i = 1}^{n} α_{i} α_{j} y_{i} y_{j} Φ^{T} (x_{i}) Φ (x_{j}) \end{aligned}

$\begin{aligned} L(w, b, \alpha) & = \frac{1}{2} ||w||^2 - \sum_{i=1}^n \alpha_i(y_i(w^T \cdot \Phi(x_i) + b) - 1)\\ & = \frac{1}{2}w^T w - w^T\sum_{i=1}^n\alpha_i y_i \Phi(x_i) - b\sum_{i=1}^n \alpha_i y_i + \sum_{i = 1}^n \alpha_i\\ & = \frac{1}{2}w^T \sum_{i = 1}^n \alpha_i y_i \Phi(x_i) - w^T\sum_{i = 1}^n \alpha_i y_i \Phi(x_i) - b \cdot 0 + \sum_{i=1}^n\alpha\\ & = \sum_{i = 1}^n \alpha_i - \frac{1}{2}\left( \sum_{i=1}^n \alpha_i y_i \Phi(x_i) \right)^T \sum_{i=1}^n \alpha_i y_i \Phi(x_i)\\ & = \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \alpha_i \alpha_j y_i y_j \Phi^T(x_i)\Phi(x_j) \end{aligned}$

L (w, b, α) = \frac{1}{2} ∣∣ w ∣ ∣^{2} - i = 1 \sum n α_{i} (y_{i} (w^{T} \cdot Φ (x_{i}) + b) - 1) = \frac{1}{2} w^{T} w - w^{T} i = 1 \sum n α_{i} y_{i} Φ (x_{i}) - b i = 1 \sum n α_{i} y_{i} + i = 1 \sum n α_{i} = \frac{1}{2} w^{T} i = 1 \sum n α_{i} y_{i} Φ (x_{i}) - w^{T} i = 1 \sum n α_{i} y_{i} Φ (x_{i}) - b \cdot 0 + i = 1 \sum n α = i = 1 \sum n α_{i} - \frac{1}{2} (i = 1 \sum n α_{i} y_{i} Φ (x_{i}))^{T} i = 1 \sum n α_{i} y_{i} Φ (x_{i}) = i = 1 \sum n α_{i} - \frac{1}{2} i = 1 \sum n α_{i} α_{j} y_{i} y_{j} Φ^{T} (x_{i}) Φ (x_{j})

这个对偶函数其实求的是 $\underset{\alpha}{\max} \underset{w, b}{\min} L(w, b, \alpha)$ 中的 $\min L(w, b)$ 部分（因为对 $w$ 和 $b$ 求了偏导）。于是现在要求的是这个函数的极大值 $\max(a)$ ，写成公式就是：

$a^* = \underset{\alpha}{\text{argmax}} \left( \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \alpha_i \alpha_j y_i y_j \Phi^T(x_i)\Phi(x_j) \right)$

好了，现在我们只需要对上式求出极大值 $a$ ，然后将 $a$ 代入 $w$ 求偏导的那个公式：

$\sum_{i = 1}^n \alpha_i y_i \Phi(x_n)$

从而求出 $w$ 。再将 $w$ 代入超平面的表达式，计算 $b$ 值。

现在的 $w$ 和 $b$ 就是我们要寻找的最优超平面的参数。

3.3.2.3 整体流程确定

我们用数学表达式来说明上面的过程：

第一步：首先是求 $\underset{w, b}{\min}L(w, b, \alpha)$ 的极大值，即：

$\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 \left( \Phi^T(x_i)\Phi(x_j) \right)\\$

\begin{aligned} s.t. & \sum_{i = 1}^{n} α_{i}, y_{i} = 0 \\ α_{i} \geq 0, i = 1, 2, . . ., n \end{aligned}

$\begin{aligned} \text{s.t.} \quad & \sum_{i=1}^n \alpha_i, y_i = 0\\ & \alpha_i \ge 0, \quad i = 1, 2, ..., n \end{aligned}$

α max i = 1 \sum n α_{i} - \frac{1}{2} i = 1 \sum n j = 1 \sum n α_{i} α_{j} y_{i} y_{j} (Φ^{T} (x_{i}) Φ (x_{j})) s.t. i = 1 \sum n α_{i}, y_{i} = 0 α_{i} \geq 0, i = 1, 2, ..., n

注意有两个约束条件。

对目标函数添加符号，转换成求极小值：

$\underset{\alpha}{\min}\frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_j y_i y_j \left( \Phi^T(x_i)\Phi(x_j) \right) - \sum_{i=1}^n \alpha_i \\$

\begin{aligned} s.t. & \sum_{i = 1}^{n} α_{i}, y_{i} = 0 \\ α_{i} \geq 0, i = 1, 2, . . ., n \end{aligned}

$\begin{aligned} \text{s.t.} \quad & \sum_{i=1}^n \alpha_i, y_i = 0\\ & \alpha_i \ge 0, \quad i = 1, 2, ..., n \end{aligned}$

α min \frac{1}{2} i = 1 \sum n j = 1 \sum n α_{i} α_{j} y_{i} y_{j} (Φ^{T} (x_{i}) Φ (x_{j})) - i = 1 \sum n α_{i} s.t. i = 1 \sum n α_{i}, y_{i} = 0 α_{i} \geq 0, i = 1, 2, ..., n

第二步：计算上面式子的极值求出 $\alpha^*$

第三步：将 $\alpha^*$ 代入，计算 $w$ 和 $b$ ：

\begin{aligned} w^{*} = \sum_{i = 1}^{n} α_{i}^{*} y_{i} Φ (x_{i}) \\ b^{*} = y_{i} - \sum_{i = 1}^{n} α_{i}^{*} y_{i} (Φ (x_{i}) \cdot Φ (x_{j})) \end{aligned}

$\begin{aligned} & w^* = \sum_{i = 1}^n \alpha_i^* y_i \Phi(x_i)\\ & b^* = y_i - \sum_{i = 1}^n \alpha_i^* y_i \left( \Phi(x_i) \cdot \Phi(x_j) \right) \end{aligned}$

w^{*} = i = 1 \sum n α_{i}^{*} y_{i} Φ (x_{i}) b^{*} = y_{i} - i = 1 \sum n α_{i}^{*} y_{i} (Φ (x_{i}) \cdot Φ (x_{j}))

第四步：求得超平面 $w^* \Phi(x) + b^* = 0$

第五步：求得分类决策函数 $\mathrm{sign}(w^*\Phi(x) + b^*)$

3.4 举例

给定 3 个数据点：正例点 $x_1 = (3,3)$ ， $x_2 = (4, 3)$ ，负例点 $x_3 = (1, 1)$ ，求线性可分支持向量机。我们把这三个点画出来：

在这里插入图片描述

第一步：首先确定目标函数

求解： $\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^n \alpha_i$
约束条件：
${\begin{cases} α_{1} + α_{2} - α_{3} = 0 \\ α_{i} \geq 0, i = 1, 2, 3 \end{cases}$ $\begin{cases} \alpha_1 + \alpha_2 - \alpha_3 = 0\\ \alpha_i \ge 0, \quad i = 1, 2, 3 \end{cases}$ ${α_{1} + α_{2} - α_{3} = 0 α_{i} \geq 0, i = 1, 2, 3$

第二步：求得目标函数的极值

原式： $\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^n \alpha_i$
把数据代入： $\frac{1}{2}\left( 18\alpha^2_1 + 25\alpha^2_2 + 2\alpha^2_3 + 42\alpha_1\alpha_2 - 12\alpha_1\alpha_3 -14\alpha_2\alpha_3 \right) - \alpha_1 - \alpha_2 - \alpha_3$

其中：

\begin{aligned} 18 = 3^{2} + 3^{2} \\ 25 = 4^{2} + 3^{2} \\ 2 = 1^{2} + 1^{2} \\ 42 = (3 \times 4 + 3 \times 3) \times 2 \\ 12 = (3 \times 1 + 3 \times 1) \times 2 \\ 14 = (4 \times 1 + 3 \times 1) \times 2 \end{aligned}

$\begin{aligned} & 18 = 3^2 + 3^2\\ & 25 = 4^2 + 3^2\\ & 2 = 1^2 + 1^2\\ & 42 = (3 \times 4 + 3 \times 3) \times 2\\ & 12 = (3 \times 1 + 3 \times 1) \times 2\\ & 14 = (4 \times 1 + 3 \times 1) \times 2\\ \end{aligned}$

18 = 3^{2} + 3^{2} 25 = 4^{2} + 3^{2} 2 = 1^{2} + 1^{2} 42 = (3 \times 4 + 3 \times 3) \times 2 12 = (3 \times 1 + 3 \times 1) \times 2 14 = (4 \times 1 + 3 \times 1) \times 2

由于 $\alpha_1 + \alpha_2 = \alpha_3$ ，化简可得：

$\alpha^2_1 + \frac{13}{2}\alpha^2_2 + 10 \alpha_1 \alpha_2 - 2\alpha_1 - 2\alpha_2$

对 $\alpha_1$ 和 $\alpha_2$ 求偏导并令其为0可知： $s(\alpha_1, \alpha_2)$ 在点 $(1.5, - 1)$ 处取极值。但是该点不满足条件 $\alpha_2 \ge 0$ （约束条件说了， $\alpha_i \ge 0$ ），所以最小值在边界上达到。

当 $\alpha_1 = 0$ 时，最小值 $\frac{2}{13}) = -0.1538$
当 $\alpha_2 = 0$ 时，最小值 $s(\frac{1}{4}, 0) = \frac{1}{4} = -0.25$

因为 $s(\frac{1}{4}, 0) = -0.25 < s(0, \frac{2}{13}) = -0.1538$ ，所以 $s(\alpha_1, \alpha_2)$ 在 $\alpha_1 = \frac{1}{4}, \alpha_2 = 0$ 时达到最小，此时：

$\alpha_3 = \alpha_1 + \alpha_2 = \frac{1}{4}$

第三步：将求得到极值代入，从而求得最优参数 $w$ 和 $b$

$\alpha_1 = \alpha_3 = \frac{1}{4}$ 对应的点 $x_1, x_3)$ 就是支持向量机。

对于公式：

$\sum_{i=1}^n \alpha_iy_i\Phi(x_n)$

将 $\alpha$ 的结果代入可知：

\begin{aligned} w = \frac{1}{4} \times 1 \times (3, 3) + \frac{1}{4} \times (- 1) \times (1, 1) = (\frac{1}{2}, \frac{1}{2}) \\ b = y_{i} - \sum_{i = 1}^{n} \sum_{j = 1}^{n} α_{i} y_{i} (x_{i} \cdot x_{j}) = 1 - (\frac{1}{4} \times 1 \times 18 + \frac{1}{4} \times (- 1) \times 6) = - 2 \end{aligned}

$\begin{aligned} & w = \frac{1}{4} \times 1 \times (3,3) + \frac{1}{4} \times (-1) \times (1, 1) = (\frac{1}{2}, \frac{1}{2})\\ & b = y_i - \sum_{i=1}^n\sum_{j=1}^n \alpha_i y_i (x_i\cdot x_j) = 1 - (\frac{1}{4} \times 1 \times 18 + \frac{1}{4} \times( -1) \times 6) = -2 \end{aligned}$

w = \frac{1}{4} \times 1 \times (3, 3) + \frac{1}{4} \times (- 1) \times (1, 1) = (\frac{1}{2}, \frac{1}{2}) b = y_{i} - i = 1 \sum n j = 1 \sum n α_{i} y_{i} (x_{i} \cdot x_{j}) = 1 - (\frac{1}{4} \times 1 \times 18 + \frac{1}{4} \times (- 1) \times 6) = - 2

因此可知，平面方程为：

$0.5x_1 + 0.5x_2 - 2 = 0$

第四步：分离超平面

故可知分离超平面为：

$0.5x_1 + 0.5x_2 - 2 = 0$

第五步：分离决策函数

由于分离超平面可知，故分离决策函数也可知：

$\mathrm{sign}(0.5x_1 + 0.5x_2 - 2)$

另一种计算方式（参考）：SVM-求解最大间隔分离超平面

小结：

SVM 中目标函数： $\underset{w, b}{\max} = \frac{1}{2}||w||^2 \quad \text{s.t.} \quad y_i(w^Tx_i + b) \ge +1, \quad i=1, 2, ..., m$
SVM 中目标函数的求解过程：
1. 首先是求 $\underset{w, b}{\min}L(w, b, \alpha)$ 的极大值，即： $\begin{aligned} s.t. & \sum_{i = 1}^{n} α_{i}, y_{i} = 0 \\ α_{i} \geq 0, i = 1, 2, . . ., n \end{aligned}$ 注意有两个约束条件。
  对目标函数添加符号，转换成求极小值： $\begin{aligned} s.t. & \sum_{i = 1}^{n} α_{i}, y_{i} = 0 \\ α_{i} \geq 0, i = 1, 2, . . ., n \end{aligned}$
2. 计算上面式子的极值求出 $\alpha^*$
3. 将 $\alpha^*$ 代入，计算 $w$ 和 $b$ ： $\begin{aligned} w^{*} = \sum_{i = 1}^{n} α_{i}^{*} y_{i} Φ (x_{i}) \\ b^{*} = y_{i} - \sum_{i = 1}^{n} α_{i}^{*} y_{i} (Φ (x_{i}) \cdot Φ (x_{j})) \end{aligned}$
4. 求得超平面 $w^* \Phi(x) + b^* = 0$
5. 求得分类决策函数 $\mathrm{sign}(w^*\Phi(x) + b^*)$

4. SVM 的损失函数

学习目标：

了解 SVM 的损失函数
知道 SVM 中的 Hinge 损失函数

SVM 之所以这么成功，主要取决于两个因素：

损失函数
核函数

在 SVM 中，我们主要讨论三种损失函数：

0/1 损失
Hinge 损失函数
Logistic 损失函数

Hinge：英[hɪndʒ] 美[hɪndʒ]
n. 铰链; 合叶;
vt. 给(某物)装铰链;

在这里插入图片描述

绿色：0/1 损失：

当正例的点落在 $y = 0$ 这个超平面的下边，说明是分类正确。无论距离超平面所远多近，误差都是0。
当这个正例的样本点落在 $y = 0$ 的上方的时候，说明分类错误。无论距离多远多近，误差都为1。
图像就是上图绿色线。

简单来讲，分对了误差为0，分错了误差为1，就是这么绝对，就是这么二极管
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/740685