6.1 间隔与支持向量
开倍速观看视频之后，对课本所说的会更加了解。
支持向量机讲解:https://www.bilibili.com/video/av77638697?p=6
给定一个数据集D={(x1,y1),(x2,y2),……,(xm,ym)}，yi∈{-1,+1}。对于分类学习来说，最基本的想法就是找出一个超平面，能够把不同类别的样本分开。
直觉上，我们会选择超平面1(红色线)。因为该超平面对训练样本局部扰动的"容忍性"好。如果选择超平面3，当有一个正例在超平面3的上方之外的话，那么就会分类错误，超平面3就不容忍这个正例，所以说超平面1的容忍性好。换句话说，就是超平面1所产生的分类结果是最鲁棒的，就是对新样例的泛化能力强。
在样本空间中，超平面的线性方程如下：
其中w = (w1,w2,……,wd)为法向量，决定了超平面的方向；b为位移项(截距)，决定了超平面与原点之间的距离。划分超平面最终由w和b确定，记为(w,b)。
样本空间中样本点到超平面的距离如下：
假设超平面(w,b)能将训练样本正确分类，则对于(xi,yi)∈D，
若yi=1，则wTxi+b>0；若yi= -1，则有wTxi+b < 0，令
6.2 对偶问题
原始问题与对偶问题以及KKT条件的关系解释https://blog.csdn.net/fkyyly/article/details/86488582
原始问题与对偶问题的视频讲解:https://www.bilibili.com/video/av77638697?p=11
原始问题转化为对偶问题:https://www.bilibili.com/video/av77638697?p=12
上面这三个链接对于对偶问题有较好的解释。
对于上式，是一个凸函数二次规划的问题。我们可以对上式使用拉格朗日乘子法得到原始问题的对偶问题。
对每个约束条件添加拉格朗日乘子αi，且αi≥0，则该问题的优化函数为
SMO基本思路：先固定αi之外的所有参数，然后求αi上的极值。
SMO步骤：每次选择两个变量αi和αj，并固定其他参数，分别对αi和αj求偏导为0，得到αi和αj，若符合约束条件就不用算，若不符合约束条件，再更新αi和αj，代入对偶问题的目标函数，直到符合条件。
那么b该如何计算呢？
使用所有支持向量求解的平均值
设支持向量表示为(xs,ys)
设S= { i | αi>0,i = 1,2,3……,m}为所有支持向量的下标集。
支持向量机的代码实现：
https://blog.csdn.net/qq_43608884/article/details/88658216
6.3 核函数
在前面的讨论中，我们假设训练样本都是线性可分的，上述SVM也只是在处理线性可分的数据。事实上，我们很多数据都是非线性可分的。
对于非线性的情况，SVM 的处理方法是选择一个核函数 κ(⋅,⋅) ，通过将数据映射φ到高维空间，来解决在原始空间中线性不可分的问题。
具体来说，在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。
如图所示，一堆数据在二维空间无法划分，从而映射到三维空间里划分：
这里的函数K(·,·)，就是核函数。
于是，对偶问题可以重写为
常用的核函数K(·,·)有以下几种
关于核函数，有下面三个关系：
- 若k1和k2为核函数，则对于任意正数γ1和γ2，其线性组合γ1k1+γ2k2也为核函数
- 若k1和k2为核函数，则核函数的直积也为核函数核函数的直积
- 若k1和k2为核函数，则对于任意函数g(x)也是核函数
支持向量机的非线性代码实现
https://blog.csdn.net/kt513226724/article/details/80413018
6.4 软间隔与正则化
在上述中的支持向量机中，我们要求所有样本都要满足约束，即都被划分正确，这叫做"硬间隔"。可实际上，很难确定合适的核函数使得样本在特种空间中线性可分，不允许分类错误的样本。
缓解这一个问题的办法就是允许支持向量机在一些样本上出错，
为此，引入"软间隔"。
而式子中的
然而"0/1损失函数"的不可微、不连续，数学性质较差，于是我们可以用其他函数替代损失函数，称为"替代损失函数"，通常数学性质较好，通常有以下三种替代损失函数：
首先对训练集的每个样本(xi,yi)引入一个松弛变量ξi≥0，使函数间隔加上松弛变量大于等于1，也就是说，约束条件变为
接着我们对软间隔支持向量机进行目标函数的优化。通过拉格朗日乘子法得到
对于上述过程，也需要满足KKT条件
1）若α=0，那么yi(wTxi+b)-1≥0，即样本在间隔边界之外，即被正确分类。
2）若0<α<C，那么ξi=0，yi(wTxi+b)-1=0，即样本在间隔边界上。
3）若α=C，则μi=0，该样本点是有可能正确分类、也有可能分类错误，此时考试ξi。
① 如果0≤ξi≤1，那么样本点在超平面和间隔边界之间，但是被正确分类。
② 如果ξi=1，那么样本点在超平面上，无法被正确分类。
③ 如果ξi＞1，样本点被分类错误。
对于，允许误差的优化目标函数，我们可以写为更加一般的形式
第二项的Σml(f(xi),yi)称为"经验风险"，用于描述模型与训练数据的契合度。
C称为正则化常数，用于对结构风险和经验风险进行折中。
上式被称为"正则化问题"，Ω(f)称为正则化项，C为正则化常数。
6.5 支持向量回归(SVR)
上面讲到的SVM是用于分类任务的，而对于回归任务，我们使用SVR。
SVM分类，就是找到一个平面，让两个分类集合的支持向量或者所有的数据离分类平面最远；
SVR回归，就是找到一个回归平面，让一个集合的所有数据到该平面的距离最近。
SVR假设f(x)与y之间最多有ε的偏差，即以f(x)为中心，允许f(x)+ε和f(x)-ε的误差，构建一个2ε的间隔。
令L对w、b、ξi、ξ^i的偏导为0，可得到
将上面求得的w代入我们原来的模型f(x) = wTx + b，得到SVR的解
由KKT可以看出，对每个样本(xi,yi)有:
1）(C - αi)ξi=0 ，2）αi(f(xi) - yi - ε - ξi)=0。
于是通过SMO算法得到αi之后，若0<αi<C，则必有ξi=0，可以得到b
若考虑映射到高维空间则有
6.6 核方法
对于SVM和SVR，它们的优化问题都是类似下面的式子
人们基于核函数的学习方法，称为"核方法"。最常见的，是通过引入核函数来将线性学习扩展为非线性。
下面以"核线性判别分析"(KLDA)为例，演示如何引入核函数进行非线性扩展。
把J(w)作为式子6.57中的损失函数，令Ω=0，有
