基本概念
划分超平面：通过一个线性方程来分类训练样本
支持向量：使划分超平面的划分结果正确的距离超平面最近的训练样例
间隔： 两个异类支持向量到超平面的距离之和
SVM（支持向量机）基本型
如何为这个分类学习器找到一个超平面
按照一贯的先限定模型，再用训练样本和算法确定参数的方法，我们先为划分超平面限定一个模型
X是多个不同属性的值构成的向量
W是为每个属性赋予的权重值所构成的向量
b为位移项，决定了超平面与原点之间的距离
所以这个超平面可扩展为
在能将训练样本分类正确的前提下找到对训练样本局部扰动容忍性(最鲁棒)的超平面
我们需要运算一个条件极值
当这个超平面使各类训练样本集到它的距离之和最大时，该超平面作为阈值最合适，但为了使样本被正确分类我们还需要一个约束条件。
样本空间中任意点到超平面的距离可由平面内点到直线的距离公式推广而来
分母为向量w的模
我们人为规定被划分为正类的标志值为1，负类为-1
被划分正确的训练样本满足
(一个训练集线性可分）
当我们令
两个异类支持向量到超平面的距离和
所以该目标超平面满足条件
为了方便计算，等价于
（svm的基本型）
求解这个基本型可得到满足条件的参数w和b，即正确且唯一的模型
如何求解
二次规划问题：目标函数二次项，限制条件一次项
而svm的基本型很明显就是一个二次规划问题，我们采用拉格朗日乘子法求解
因此我们可以得到关系式
把关系式代入原拉格朗日函数
因此求解原问题就变成了求解对偶问题
而原模型可根据关系式变形为
由于原问题有不等式约束，所以其对偶问题需要增加KKT条件
显然，这个条件的解为
观察刚刚得到的线性模型表达式可知，最终模型仅与支持向量有关。
通用的二次规划算法不够高效，在这里我们
采用SMO：先固定两个乘子之外的所有参数，然后求这两个乘子上的极值.为什么是两个而不是一个，因为我们之前计算出 当原函数值最大时所有乘子和其对应标志值的乘积之和为0，所以如果每次选择一个作为变量，则这个乘子可由其他已经被固定的乘子导出。
如何选取这两个参数
直观来看，KKT 条件违背的程度越大，则 变量更新后可能导致的目标函数值减幅越大.也就是逼近解的速度越快，第二个变量应选择一个使目标函数值减小最快的变量，但 由于比较各变量所对应的目标函数值减幅的复杂度过高，因此 SMO 采用了一 个启发式:使选取的两变量所对应样本之间的间隔最大. 种直观的解释是，这 样的两个变量有很大的差别，与对两个相似的变量进行更新相比，对它们进行 更新会带给目标函数值更大的变化.
用约束条件
消去其中一个变量，得到一个关于ai的单变量二次规划问题，求解得到ai aj
对于b,我们使用所有样本求解的平均值（注意这里标志值y只能是1，-1）所以最终b的表达式为
即可确定目标参数及超平面线性方程。
处理非线性问题
如果样本空间非线性可分，则svm基本型的限制条件不成立
将样本高维映射可使样本在这个特征空间内线性可分(降维打击）
例如：
映射后的模型可表示为
例如：
而我们要找的超平面则相应的也从二维变成五维
针对处理非线性问题改造svm基本型
同理可得其对偶问题
为了简化运算，我们用核函数替换
核函数:用一个函数通过低维的向量值直接计算出高维向量的内积 而不需要知道高维向量的具体形态
核函数使高维映射又变回低维运算
怎么确定核函数?
核函数成立的充要条件：
1.可替换
2.半正定
只要一个对称函数所对应的核矩阵半正定，就能作为核函数使用
常用的核函数
软间隔与正则化
由于在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分;退一步说即使恰好找到了 某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的
所以我们允许支持向量机在一些样本上出错.
这种不要求所有样本被正确分类的向量机形式被称为软间隔，即不满足约束
因此我们原来构造的拉格朗日函数就不适用，但为了使优化目标变为 在最大化间隔的同时，不满足约束的样本也要尽可能少，我们将原来的条件函数映射成一个损失函数，使其大小与不被正确分类的标志数量成正比
因此优化目标可写为
显然，求解该函数需要综合考虑间隔大，出错少两个条件，分别称为结构风险(间隔）和经验风险（误差）
为了易求解，我们通常采用数学性质更好的函数替代，称为"替代损失"
被划分错误的样本距离超平面越远 损失函数的自变量z越小，1-z越大
这个约束条件由损失函数的定义推导而来
这同样是一个二次规划问题，同理可得到它的对偶问题及KKT条件
由KKT条件用同样的方法可推出软间隔支持向量机的 最终模型仅与支持向量有关。
同样用smo求解得到超平面
优化目标由间隔大小和误差程度构成，可写为更一般的形式
称为正则化问题
支持向量回归
假设我们能容忍 f(x) 与 y之间最多有 一定 的偏差，即仅当 f(x) 与 y 之间的差别绝对值大于这个值时才计算损失
用不敏感损失函数衡量损失程度，SVR 问题可形式化为
引入松弛变量
同样用拉格朗日乘子法得到对偶问题和其KKT条件
由求偏导得到的关系式可将超平面扩展为
考虑上面提到的非线性可分情况下的特征映射形式，则表示为
总结
这章讨论了在4种情况下如何确定支持向量机
1.硬间隔 即样本训练集不允许有误差
首先确定两个条件，1）被分类正确2）间隔最大，于是得到一个条件极值的运算，接着用拉格朗日乘子法得到关系式，变形成对对偶问题的求解，加入KKT条件，最后用SMO对对偶问题求解。
2.线性不可分 即无法用一个线性模型对训练样本进行分类
用高维映射的方法解决这个问题，将样本从原始空间映射到一个更高维的特征空间，使其线性可分，为了简化计算我们引入核函数，用以代替高维特征空间中样本的内积。只要一个对称函数所对应的核矩阵半正定，就能作为核函数使用。
3. 软间隔 即允许部分样本不满足约束（不被正确分类）
在这个问题上引入损失函数以衡量样本不满足约束的程度，综合考虑两个维度进行优化（结构风险和经验风险），接着便用和解决硬间隔一样的推算方法得到软间隔问题的超平面，将软间隔的目标优化写为更一般的形式则得到正则化问题。
4.回归问题
有别于传统回归模型，支持向量回归假设我们能容忍一定的偏差，在这个偏差之外才被认为错误，因此在构造目标优化时引入不敏感损失函数。接着又是一样的推算方法得到SVR的解型，同样的在考虑特征映射时引入核函数。
