[数据结构与算法] 《统计学习方法》第七章

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

-> 数据结构与算法 -> 《统计学习方法》第七章 -> 正文阅读

[数据结构与算法]《统计学习方法》第七章

好久没上来写总结了，旅完游回来继续补上

这一章主要讲的是支持向量机SVM，基本模型就是定义在特征空间上的间隔最大的线性分类器，主要的框架就是支持向量机是怎么工作的，其中的核函数，核技巧的作用和实现细节。学习策略就是使得间隔最大化=求解凸二次规划=正则化的合页损失函数的最小化问题。

支持向量机可以分为三种情况，线性可分SVM，线性SVM，非线性SVM

当数据是线性可分的情况，我们通过硬间隔可以直接分类，称为线性可分支持向量机

当数据是近似地线性可分的情况，我们通过软间隔最大化来提高容错几率，从而实现“线性可分”的情况，称为线性支持向量机

当数据是线性不可分的情况，我们将定义在输入空间的特征，通过核函数的映射，map到高维的特征空间上，然后使用硬间隔的方法达到“线性可分”的情况，称为非线性支持向量机

1.1 线性可分支持向量机

? ? ? ? 这里讨论一个二分类的问题，假设输入空间和特征空间是两个不同的空间。输入空间是一个欧式空间/离散的集合，特征空间是一个希尔伯特的空间（后面会解释到希尔伯特空间有什么特点）。

????????假设我们有很多个样本 $T=\left \{ (x_{1},y_{1}),(x_{2},y_{2}),......,(x_{n},y_{n}) \right \}$ ，其中输出 $y_{i}=+1/-1$ ，代表二分类的类别，并且假设样本是一个线性可分的情况

? ? ? ? 我们可以想象得出，当我们数据的线性可分的情况，我们有无数个超平面可以实现数据的划分，但是正因为有无数个，所以我们需要找出一个最优的超平面来去区分。那么怎么定义什么情况下是最优的呢，这里定义道：两边里超平面最近的点，也就是有两个点，这两个点离超平面的距离越远越好，最远的情况就是最优的。

1.1.1 函数间隔和几何间隔

? ? ? ? 首先要理解点距离超平面的意思，我们称为间隔，这个间隔可以理解为置信度，距离越大（间隔越大）代表着这个样本更有把握地分到某一类。

? ? ? ? 我们定义好超平面， $w*x+b=0$ ， $\left | w*x+b \right |$ 代表着点x道超平面的距离，而 $w*x+b$ 的符号与标记 $y$ 的符号是否一致可以代表着这个点是否被份分类正确。

????????所以我们可以用 $y((w*x+b)$ 来表示分类的正确性以及置信度，这就是函数间隔的概念

? ? ? ? 函数间隔用 $\hat{\gamma _{i}}=y_{i}(w*x_{i}+b)$ 来表示，其中w就是这个超平面的法向量，b就是这个平面的截距。

? ? ? ? 定义某个超平面中，所有样本点的函数间隔的最小值为： $\hat{\gamma }=min\hat{\gamma _{i}},i=1,2,3,...,n$ ，可以发现，目前就是要最大化这个最小值才行。

? ? ? ? 但是我们也发现，虽然我们要最大化，但是只要我们成比例地改变w和b，就出现一种情况，超平面一直都是那一个没有改变，只有函数间隔变大，显然这不是我们想要的，所以我们要采取某些办法来阻止这个情况发生，于是我们对w添加一些约束，对w进行规范化处理，令 $\left \| w \right \|=1$ （w的L2范数等于1），此时，函数间隔就变成了几何间隔。

? ? ? ? 于是点到超平面的距离变成： $\gamma_{i}=\frac{w}{\left \| w \right \|}*x_{i}+\frac{b}{\left \| w \right \|}$

? ? ? ? 几何间隔的表达形式就是： $\gamma_{i}=y_{i}\left ( \frac{w}{\left \| w \right \|}*x_{i}+\frac{b}{\left \| w \right \|} \right )$

? ? ? ? 同理，我们也是求所有样本点 $(x_{i},y_{i})$ 到超平面的几何间隔中最小的那个：

$\gamma=min \gamma_{i}$

? ? ? ? 函数间隔和几何间隔的关系就是：函数间隔 / w的L2范数 = 几何间隔

1.1.2 间隔最大化

? ? ? ? 我们知道了间隔的定义后，可以发现这个对于所有点，每个点的间隔总是越大越好的。越是，我们就可以将找平面的问题等效变成一个找所有间隔里最小的间隔的最大化问题：也就是一个约束的最优化问题：

$max \frac{\hat{\gamma}}{\left \| w \right \|}$

$s.t. y_{i}(w*x_{i}+b)\geq \hat{\gamma}, i=1,2,...,n$

? ? ? ? 上述那个gama是函数间隔哈，除以L2范数就变成了几何间隔，我们取函数间隔等于1，其中为什么让他等于1呢，查了网上很多说法，都是似是而非，感觉怪怪的。最后我找到一个最在理的，我看了很多解释都是解释不到点子上。

? ? ? ? 当我们找到了合适的超平面后，我们相当于找到了所有样本点中离超平面最近的一个点了，暂且理解为 $X_{j}$ 这个点是最近的点，于是此时的超平面也是最大值了，但是我们发现，在那个最大值的超平面上，也有很多种w和b的组合可是表示这个超平面，也是我们就引入了函数间隔等于1这个条件来确定唯一的一组w和b来表示这个最大值的超平面。之前引入w的L2范数（w的膜）是为了避免我们在修改w和b的时候发生同时按比例（这里先保留着，后面再补充，在网上找了很多资料，发现说的都不怎么正确）但是我觉得估计是前面书上有一点东西我没看仔细

? ? ? ? 先暂且我们令函数间隔的长度都是1，于是上式就变成求 $\frac{1}{\left \| w \right \|}$ 的的最大值，于是我们简化一下，变成求 $\frac{1}{2}\left \| w \right \|^{2}$ 的最小值，因为原始w是在分母，求最小等同于分母最大化，平方且加1/2是为了后面求导方便

? ? ? ?? $min \frac{1}{2}\left \| w \right \|^{2}$

$s.t. y_{i}(w*x_{i}+b)-1\geq 0, i=1,2,3...n$

1.1.3 支持向量和间隔边界

?? ? ? ?在线性可分的情况下，注意，一定是线性可分的情况下，训练数据的样本点中与分离超平面距离最近的样本点称为支持向量。支持向量是使约束条件式s.t.大于等于0中的等号成立。

? ? ? ? 即当前这个点带入超平面中会使得那个式子输出等于1，

? ? ? ? 对于 $y_{i}=+1$ 的正例点，支持向量在超平面 $w*x+b=1$ 上

? ? ? ? 对于 $y_{i}=-1$ 的负例点，支持向量在超平面 $w*x+b=-1$ 上

? ? ? ? 例如图上的H1和H2虚线上的点就是支持向量：

? ? ? ? H1和H2之间形成一条长带，分离超平面与他们两个平行，H1和H2之间的距离称为间隔，间隔依赖于分离超平面的法向量w，H1和H2两个虚线?称为间隔边界

????????在决定分离超平面的位置时，只有支持向量在起作用，其他实例点不起作用，因为我们都是计算的是距离超平面最近的点等于1的平面，所以其他远离超平面的点不会参与计算当中

1.1.4 对偶求解

? ? ? ? 这里先介绍某些问题怎么求最优解

? ? ? ? 第一种情况是没有约束条件：那我们就直接求导等于0，来获得极小值极大值的点

? ? ? ? 第二种情况是有约束条件，但是约束条件是一个等式，此时我们将原始函数和约束条件一并引入拉格朗日函数里面。将所有式子变换成一个拉格朗日函数

? ? ? ? 第三种情况是有约束条件，且约束条件是一个不等式，这时候，也需要构建拉格朗日函数且用KKT条件帮忙求最优解

? ? ? ? 根据1.1.2节的最后一个表达式，我们构建出拉格朗日函数

$L(w,b,\alpha)=\frac{1}{2}\left \| w \right \|^{2}-\sum ^{N}_{I=1}a_{i}y_{i}(w*x_{i}+b)+\sum ^{N}_{i=1}a_{i}$

? ? ? ? 原始问题是求上式第一项的最小值，再变换成为拉格朗日式后，我们先获得原式，也就是先求上式的max，为什么呢？

? ? ? ? 因为我们subject to的约束，大于等于0，而且拉格朗日这里是减去这个大于等于0的东西，那么我们为了得到原式：1/2||w||^2 ，所以就是求这个大于等于0的最小值，也就是求整式的最大值，所以就是求max。

? ? ? ? 然后原来是求min，那么我们在求max的基础上，再添一层min，就构成了：

$minmaxL(w,b,a)$

? ? ? ? 那么与之对应的对偶形式的解，就是求：

$maxminL(w,b,a)$

? ? ? ? 首先我们先求min，这是一个可求导的函数，于是我们先对变量求导，上式是一个关于w和b的函数，于是对w和b求偏导，并令他们等于0:

$\triangledown _wL(w,b,a)=w-\sum_{i=1}^{N}a_{i}y_{i}x_{i}=0$

$\triangledown _bL(w,b,a)=-\sum^{N}_{i=1}a_{i}y_{i}=0$

? ? ? ? 将所得的结果带入到拉格朗日函数中：

?????????求得最小值后，我们对上式求极大：

? ? ? ? 最后可求得 $a^{*}$ ，使得上式求得最小值，于是我们可得出最佳的w和b，记为：

???????? $w^{*}=\sum^{N}_{i=1}a_{i}^{*}y_{i}x_{i}$ ?

$b^{*}=y_{j}-\sum^{N}_{i=1}a_{i}^{*}y_{i}(x_{i}*x_{j})$

所以，对应超平面是： $\sum^{N}_{i=1}a_{i}^{*}y_{i}(x*x_{i})+b^{*}=0$

1.2 线性支持向量机（不是严格的线性可分）和软间隔最大化

?? ? ? ?当数据中有一些特异点，将这些特异点出去后，剩下的大部分的样点组成的集合是线性可分的，这个时候就需要将我们上述的硬间隔修改为软间隔。

? ? ? ? 线性不可分一位置某些样本点 $(x_{i},y_{i})$ 不能满足函数间隔大于等于1的约束条件，为了解决这个问题，我们对每个样本点引入一个松弛变量 $\xi _{i}\geq 0$ 。使得函数间隔加上松弛变俩个大于等于1，此时，约束条件变成：

$y_{i}(w*x_{i}+b)\geq 1-\xi_{i}$

? ? ? ? 于是，我们目标函数由原来的 $\frac{1}{2}\left \| w \right \|^{2}$ ?变成 $\frac{1}{2}\left \| w \right \|^{2}+C\sum^{N}_{i=1}\xi_{i}$ ，怎么理解后面这一项呢，我们可以理解为这是一个惩罚项，允许出现错误的距离，对没错，这个 $\xi_{i}$ 其实是一个距离来的，具体的表现方式就是，因为我们只有硬间隔的距离是1，所以，现在没满足这个条件，也就是这些点会出现在小于1的范围里，于是，我们就计算到超平面（等于0）的距离。

? ? ? ?? $\left\{\begin{matrix} y_{i}(w*x_{I}+b) \geq 1 & \xi_{i}=0 \\ y_{i}(w*x_{I}+b) < 1 & \xi_{i}=1-y_{i}(w*x_{I}+b) \end{matrix}\right.$

? ? ? ? 这里的C称为惩罚参数，C值越大，对误分类的惩罚就越大，相反惩罚就越小。C就是一个参数，调整C就是为了找到整体项的值尽可能小，同时误分类的样本点也尽可能得少

? ? ? ? 于是，软间隔的学习过程就变成如下的形式：

$min \frac{1}{2}\left \| w \right \|^{2}+C\sum_{i=1}^{N}\xi _{i}$

$s.t. y_{i}(w*x_{i}+b)\geq 1-\xi_{i}$

$\xi_{i}\geq 0$

? ? ? ? 对应的拉格朗日函数是：

$L(w,b,\xi,\alpha,\mu )=\frac{1}{2}\left \| w \right \|^{2}+C\sum_{i=1}^{N}\xi_{I}-\sum_{i=1}^{N}a_{i}(y_{i}(w*x_{i}+b)-1+\xi_{i})-\sum_{i=1}^{N}\mu_{i}\xi_{i}$

? ? ? ? 就是把st条件也放到了函数内，并且用拉格朗日乘子相乘后相加

? ? ? ? 原函数是求min，那么换成拉格朗日函数后，我们首先求max获得原问题，然后再求min复现出来，所以对应的对偶问题就是先求min，后求max。

? ? ? ? 求min的话，首先求各个变量的偏导，然后再代入回拉格朗日式。直接引用书上原话：

? ? ? ? 先把非拉格朗日乘子的相关变量都先求偏导：

? ? ? ? 通过7.43，代入C，可以消掉之前所的惩罚项里代表距离的未知量 $\xi_{i}$ ，于是得出最后一个式子

? ? ? ? 因为 $\xi_{i}$ 别削掉了，所以拉格朗日函数剩下就剩一个关于 $\alpha _{i}$ 的函数，于是我们剩下求最大值也是根据KKT条件最后求得 $\alpha^{*}$ ，于是我们可以求得最佳的w和b

???????? $w^{*}=\sum^{N}_{i=1}a_{i}^{*}y_{i}x_{i}$

$b^{*}=y_{j}-\sum^{N}_{i=1}y_{i}a_{i}^{*}(x_{i}*x_{j})$ ?

1.2.1 线性支持向量机下的支持向量

? ? ? ? 有多少个训练样本点，我们就有多少个 $\alpha$ ，于是，对于那些 $\alpha > 0$ 的样本点，我们称为支持向量?

? ? ? ? 软间隔的支持向量 $x_{i}$ 或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面的误分类一侧。

? ? ? ? 若 $\alpha^{*}_{i}< C, \xi_{i}=0$ ，支持向量恰好落在间隔边界上

? ? ? ? 若 $\alpha^{*}_{i}=C,0<\xi_{i}<1$ ，支持向量落在了间隔边界与分离超平面之间

? ? ? ? 若 $\alpha^{*}_{i}=C,\xi_{i}=1$ ，支持向量落在了分离超平面上

? ? ? ? 若 $\alpha^{*}_{i}=C,\xi_{i}>1$ ，支持向量落在了分离超平面误分类的一侧

1.2.2 合页损失函数

1.3 非线性支持向量机与核函数

? ? ? ??有时候，我们的训练样本并不是线性可分的。也就是既不符合硬间隔的条件，也不符合软间隔的条件，此时就需要核函数，核技巧去将数据映射到高维空间实现线性可分，从而可以使用硬间隔的方法去实现分类。

? ? ? ? 设原空间 $X$ ， $x=(x^{(1)},x^{(2)})$ ，新空间 $Z$ ， $z=(z^{(1)},z^{(2)})$ ，定义从原空间到新空间的变换：

$z=\phi (x)=((x^{(1)})^(2),(x^{(2)})^(2))^{T}$

? ? ? ? 用一个变换将原空间的数据映射到新空间，然后在新空间里用线性分类学习方法从训练数据中学习分裂模型，这就是核技巧的定义了

? ? ? ? 设 $X$ 是输入空间（欧式空间的自己/离散集合）， $\nu$ 为特征空间（希尔伯特空间），如果存在一个从 $X\rightarrow \nu$ 的映射， $\phi(x)=X->\mu$ ，使得对所有的x，函数 $K(x,z)$ 满足 $K(x,z)=\phi(x)*\phi(z)$

? ? ? ? 那么就称 $K(x,z)$ 为核函数， $\phi(x)$ 为映射函数，其中 $\phi(x)*\phi(z)$ 就是内积

? ? ? ? 重点来了！！！

? ? ? ? 核技巧的想法是我们只定义和函数，也就是映射后的结果，而不定义映射这个过程（函数），因为映射函数我们不好把握，有可能数据非常复杂，我们需要映射到很高纬度才能到达线性可分的条件，所以我们做的预设的这个映射可以映射到无限维，于是映射这个计算就会变得很难计算了。从而引导出我们只管映射后的结果就好了。书上有例子可以看看。

????????

? ? ? ? 下面也是重点来了！！！

? ? ? ? 我们可以返回去看上面线性支持向量机/线性可分的支持向量机，到了后面的对偶函数的最后一步求max的时候，我们都可以找到 $x_{i}*x_{j}$ 的影子，这其实就是样本之间的内积，那我们又在看一下核函数的定义，也是两个样本映射后的内积 $\phi(x_{i})*\phi(x_{j})$ ，所以我们干脆就用核函数来代替上面的对偶函数最后一步求max的内积算了：