[数据结构与算法] Datawhale吃瓜教程-task5学习笔记（第六章）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Datawhale吃瓜教程-task5学习笔记（第六章） -> 正文阅读

[数据结构与算法]Datawhale吃瓜教程-task5学习笔记（第六章）

6.1 间隔与支持向量

支持向量：假设超平面 $(\omega ,b)$ 能将训练样本正确分类，即对于 $(x_{i},y_{i})\epsilon D$ ,若 $y_{i}=+1$ ，则有 $\omega ^{T }+b>0$ ;若 $y_{i}=-1$ ，则有 $\omega ^{T}+b<0$ 。令

?如图所示，距离超平面最近的这几个训练样本使上式等号成立，则被称为“支持向量”。

间隔：两个异类支持向量超平面的距离之和 $\gamma =\frac{2}{\left \| w \right \|}$ 称为间隔。

支持向量机（SVM）基本型：为了最大化间隔，仅需最大化 $\left \| w \right \|^{-1}$ ，等价于最小化 $\left \| w \right \|^{2}$ ，目标函数如下：

SVM算法原理：从几何角度，对于线性可分数据集，支持向量机就是找距离正负样本都最远的超平面，相比于感知机，其解释是唯一的，且不偏不倚，泛化性能更好。

?6.2对偶问题

支持向量机基本型的拉格朗日函数形式：

?其中 $\alpha =(\alpha _{1};\alpha _{2};\cdots ;\alpha _{m})$ .

支持向量机基本型的对偶问题与KKT条件：

对偶问题

?上述过程需满足KKT条件，即要求

支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。

?SMO算法：SMO算法是求解对偶问题这种二次规划问题的高效算法，其基本思路是先固定 $\alpha _{i}$ 之外的所有参数，然后求 $\alpha _{i}$ 上的极值。由于存在约束 $\sum_{i=1}^{m}\alpha _{i}y_{i}=0$ ，若固定 $\alpha _{i}$ 之外的其他变量，则 $\alpha _{i}$ 可由其他变量导出。于是，SMO每次选择两个变量 $\alpha _{i}$ 和 $\alpha _{j}$ ，并固定其他参数。在参数初始化后，SMO不断执行如下两个步骤直至收敛：

(1)选取一对需更新的变量 $\alpha _{i}$ 和 $\alpha _{j}$ ；

(2)固定 $\alpha _{i}$ 和 $\alpha _{j}$ 以外的参数，求解对偶问题获得更新后的 $\alpha _{i}$ 和 $\alpha _{j}$ 。

值得注意的是，SMO 采用了一个启发式:使选取的两变量所对应样本之间的问隔最大。这样的两个变量有很大的差别，与对两个相似的变量进行更新相比，对它们进行更新会带给目标函数值更大的变化。

6.3核函数

?核函数的概念：原始样本空间内也许并不存在一个能正确划分两类样本的超平面，此时可将样本从原始空间映射到一个高维的特征空间，使得样本在这个空间内线性可分。令 $\phi (x)$ 表示将 $x$ 映射后的特征向量，于是在特征空间中划分超平面所对应的模型可表示为

?然而，求解上述模型的目标函数涉及到 $\phi (x_{i})^{T}\phi (x_{j})$ ，直接计算十分困难。因此，为了避免这个障碍，可以设想这样一个函数：

?即 $x_{i}$ 和 $x_{j}$ 在特征空间的内积等于它们在原始样本空间中通过函数 $k(\cdot ,\cdot )$ 计算的结果。函数 $k(\cdot ,\cdot )$ 就是“核函数”。

核函数的定理：令 $X$ 为输入空间， $k(\cdot ,\cdot )$ 是定义在 $X\times X$ 上的对称矩阵，则 $k$ 是核函数当且仅当对于任意数据 $D=\left \{ x_{1},x_{2},\cdots ,x_{m} \right \}$ ，“核矩阵” $K$ 总是半正定的：

该定理表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。

几种常用的核函数：
?

?6.4软间隔与正则化

?软间隔的概念：允许某些样本不满足约束

?当然，在最大化间隔的同时，不满足约束的样本应尽可能少。

?软间隔条件下的新目标函数：

?其中 $C>0$ 是一个常数， $l_{0/1}$ 是“0/1损失函数”

?当 $C$ 无穷大时，所有样本满足约束；当 $C$ 取有限值时，上式允许一些样本不满足约束。

替代损失函数：由于 $l_{0/1}$ 数学性质不太好，所以人们常用其他函数来代替 $l_{0/1}$ ，称为“替代损失函数”。这种替代损失函数一般具有较好的数学性质，如是凸的连续函数且是 $l_{0/1}$ ? 的上界。常用的替代损失函数如下：

?软间隔支持向量机目标函数：

?其中 $\xi _{i}$ 是松弛变量，表示该样本不满足约束的程度。

软间隔支持向量机的拉格朗日函数形式：
?

?其中 $\alpha _{i}\geqslant 0,\mu _{i}\geqslant 0$ 是拉格朗日乘子。

软间隔支持向量机的对偶问题与KKT条件：
?

?可以看出，软间隔与硬间隔下的对偶问题的唯一差别在于对偶变量的约束不同，前者是 $0\leqslant \alpha _{i}\leqslant C$ ，后者是 $0\leqslant \alpha _{i}$ 。

上述过程需满足KKT条件，即要求

?软间隔支持向量机的最终模型仅与支持向量有关，即通过采用hinge损失函数仍保持了稀疏性。

?正则化：

其中 $\Omega (f)$ 称为“结构风险”，用于描述模型 $f$ 的某些性质；第二项 $\sum_{i=1}^{m}l(f(x_{i}),y_{i})$ 称为“经验风险”，用于描述模型与训练数据的契合程度； $C$ 用于对二者折中。从另一个角度看，上式也可以称为在“正则化”问题， $\Omega (f)$ 称为正则化项， $C$ 称为正则化常数。