本周内容总结
1.间隔与支持向量
分类学习的基本思想：基于训练集在样本空间中找到分区超平面，不划分同类样本。
特点：寻找两种训练样本“中间”的分区超平面
原因：该超平面对训练样本局部扰动的“容忍”性最好，结果分类结果最鲁棒，罕见泛化能力最强。
在样本空间中，分割超平面可以用方程描述，其中是法向量，决定超平面的方向。 b是位移项，决定超平面和原点之间的距离。
样本空间内任意点到超平面的距离可以写如下。
假设超平面可以准确分类训练样本，则对于任意样本都是训练样本集。
如果有；
如果有。
令
如下图所示，离超平面最近的这些训练样本点成立了上式的等号，它们被称为“支撑向量”，两个异种支撑向量到超平面的距离之和被称为“间隔”。
要找到具有“最大间隔”的分区超平面，请找到满足的约束参数，然后选择最大(即
很明显，为了使间隔最大化，只需要最大化即可，这等价于最小化。 于是，就有了
这是支持向量机的基本类型。
2.对偶问题
关于一般优化问题
为了得到最大间隔分割超平面，用拉格朗日乘子法得到其“对偶问题”。 也就是说，如果在各约束中追加拉格朗日乘子，这个问题的拉格朗日函数可以写如下
其中。
零的偏导就能得到
把求出的导数拿来，就可以消除参数和，得到对偶问题
对偶问题公式
求解，求参数之和得到模型
从对偶问题中求解的是拉格朗日函数的拉格朗日乘子，这正好对应于训练样本。
请注意，支持向量机的基本类型存在不等式约束。 因此，上述过程必须满足kkt(karush-kuhn-Tucker )条件，即要求
于是，对于任意的样品，总是有。
那样的话，那个样本不会出现在的合计中，没有任何影响；
如果是，则对应的样本点必须位于最大间隔边界上且为支持向量。
这表明了支持向量机的重要性质。 培训完成后，大多数培训样本不需要保留，最终模型仅与支持向量相关。
如何解决对偶问题？
这里采用了smo (sequentialminimaloptimization )算法
SMO的基本想法是先固定除固定以外的所有参数，再求出上面的极值。
因为有约束，所以非固定变量可以从其他变量导出。 因此，SMO每次都会选择两个变量和，并固定其他参数。 因此，在参数初始化后，重复以下两个步骤直到收敛。
1 )需要更新对的变量和；
2 )固定和以外的参数，求解对偶问题得到更新的和。
3.核函数
以前的讨论假设训练样本是线性的、可分离的。 也就是说，存在可以正确分类训练样本的超平面。 然而，在现实任务中，原始样本空间中可能不存在可以准确分割两个样本的超平面。
如果样本在原始空间中线性不可分离，则样本可以被从原始空间映射到高维特征空间，使得样本可以在该特征空间中线性分离。 如上图所示，将二维空间映射到适当的三维空间，可以找到适当的分割超平面。 另外，在原始空间为有限维的情况下，即在属性数有限的情况下，一定存在能够分离样本的高维特征空间。
使其表示映射的特征向量。 然后，与在特征空间中分割的超平面相对应的模型可以表示为
支持向量机的最基本形式是
那个对偶问题
引入这种映射，求解的对偶问题
的求解中，无需求解真正的映射函数，而只需要知道其核函数。即与在特征空间的内积等于它们在原始空间中通过函数计算的结果。有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中的内积，于是，对偶问题可重写为
求解后即可得到
这里的函数就是“核函数”（kernel function）。
若已知映射，则可写出核函数。但在现实任务中我们通常不知道是什么形式，那么，合适的核函数是否一点存在？
什么样的函数能做核函数？
只要一个对称函数所对应的核矩阵半正定，它就能作为核函数。
事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射。
我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。然而在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，而核函数也就是隐式地定义了这个空间。于是，核函数的选择 成了支持向量机的最大变数。在实际处理过程的，选取不同的核函数进行尝试对比来选取核函数的。
此外，还可通过函数组合得到，例如
若为核函数，则核函数的直积也是核函数；
若为核函数，则对于任意正数，其线性组合也是核函数；
若为核函数，则对于任意函数，也是核函数。
4.软间隔与正则化
前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；同时，即使找到哦啊了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。
缓解该问题的一个办法是允许支持向量机在一些样本上出错。为此，引入“软间隔”(soft margin)的概念。
因此若所有样本都必须划分正确，这称为“硬间隔”(hard margin)，而软间隔是允许某些样本不满足约束。
当然，在最大化间隔的同时，不满足约束的样本应尽可能少。于是，优化目标可写为
其中是一个常数，是“0/1损失函数”
当取有限值时，允许一些样本不满足约束；当为无穷大时，则所有样本均满足约束。
非凸、非连续，数学性质不太好，使得目标函数不易求解。于是，通常用其他一些函数来代替，称为“替代损失”(surrogate loss)。替代损失函数一般具有较好的数学性质，如他们通常是凸的连续函数且是的上界。
以下是三种常用的替代损失函数：
若采用higne损失，则目标函数变为
引入“松弛变量”（slack variable），则目标函数重写为
这就是常用的“软间隔支持向量机”。
软间隔支持向量机中每个样本都有一个对应的松弛变量，用以表征该样本不满足约束的程度。
同理，我们可通过拉格朗日乘子法得到软间隔支持向量机的拉格朗日函数
其中，是拉格朗日乘子。
令对，， 的偏导为零可得
其中
将上面求得的结果带入软间隔支持向量机的拉格朗日函数中
所以
故其对偶问题为
该软间隔与硬间隔的队友问题对比可看出，两个唯一的差别就在对偶变量的约束不同，前者是，后者是。同样可采用SMO算法求解该目标函数；在引入核函数也能得到与硬间隔同样的支持向量展式。
对软间隔支持向量机，KKT条件要求
对于，对于任意训练样本，总有或.
若，则该样本不会对有任何影响
若，则必有，即该样本是支持向量
若，则有，进而有，即该样本恰在最大间隔边界上
若，则有，此时若，则该样本落在最大间隔内部，若，则该样本被错误分类。
由此可以看出，软间隔支持向量机的最终模型仅与支持向量有关，即通过采用hinge损失函数仍保持了稀疏性。
5.支持向量回归
对样本，传统回归模型通常直接基于模型输出与真实输出之间的差别来计算损失，当且仅当与完全相同时，损失才为零。与此不同，支持向量回归(Support Vector Regression，简称SVR)假设我们能容忍与之间最多有的偏差，即当与之前的差别绝对值大于时才计算损失。如图6.6所示，这相当于以为中心，构建了一个宽度为的间隔带，若训练样本落入此间隔带，则认为是被预测正确的。
于是，SVR问题可形式化为
其中为正则化常数，是图6.7所示的-不敏感损失(-insensitive loss)函数
引入松弛变量 和 ，则可将SVR重写为
类似地，通过引入拉格朗日乘子，由拉格朗日乘子罚可得到SVR的拉格朗日函数
将带入上式，再令的偏导数为零可得
将求导结果带入拉格朗日函数中，即可得到SVR的对偶问题
上述过程中需满足KKT条件，即要求
将
的约束条件全部恒等变形为小于等于0的形式可得
又由
从KKT条件可以看出，当且仅当时，能取到非零值，当且仅当时，能取到非零值。
换言之，仅当样本不落入-间隔带中，相应的 和 才能取非零值。
此外，约束和不能同时成立，因此 和中至少有一个为零。
将带入中，则SVR的解形如
能使上式中的的样本即为SVR的支持向量，它们必落在-间隔带之外。
参考南瓜书中推导https://datawhalechina.github.io/pumpkin-book/#/chapter6/chapter6