《Andrew Ng 机器学习笔记》这一系列文章文章是我再观看Andrew Ng的Stanford公开课之后自己整理的一些笔记，除了整理出课件中的主要知识点，另外还有一些自己对课件内容的理解。同时也参考了很多优秀博文，希望大家共同讨论，共同进步。
网易公开课地址：http://open.163.com/special/opencourse/machinelearning.html
本篇博文设计课程七：最优间隔分类器问题
主要内容包括：
（1）最优间隔分类器(optimal margin classifier)
（2）原始/对偶优化问题（KKT）（primal/dual optimization problem） （3）SVM对偶(SVM dual)（4）核方法(kernels)(下一篇博文具体分析)
最优间隔分类器
如果训练集是线性可分的， 就是说用超平面可以分隔正负样本. 我们要找到最大的几何间隔. 我们可以转化为下面的优化问题：
即，找到一个超平面，在将正负样本分开的同时，使超平面到正负样本间的距离尽可能大。
由于w和b可随意缩放，约束条件||w||=1，使得函数间隔等于几何间隔。但是这个约束本身是一个非凸性约束。（非凸性：是指系统有多个稳定的平衡态。）要求解的参数w在一个球体表面，如果想得到一个凸优化问题，必须保证如梯度下降算法这种局部最优值搜索算法不会找到局部最优值，而非凸性约束不能满足这个条件，所以需要改变优化问题。因此转化为更好的一个问题：
我们的目标变成要最大化,并且去掉了约束条件||w=1||，但是仍然是非凸性的.
因此，加上规模的限制，对训练集的函数间隔设置为1：
至此，我们得到最终的最优间隔分类器：
此时，我们的优化问题变为一个凸二次目标函数。
原始优化问题
拉格朗日二元性
考虑下式：
即最小化函数f(w)，并满足约束条件hi(w)=0，可以将hi写成0向量，我们可以通过拉格朗日乘数法的方法解决：
1、创建拉格朗日算子：
即等于原始目标函数加限制函数的线性组合，其中参数β称为拉格朗日乘数。
2、对下式求偏导数置为0，即可求出解w和β：
原始问题
拉格朗日乘数法的一般形式，也称为原始问题。
考虑下式：
创建拉格朗日算子：
此时α和β为拉格朗日乘数，定义：
上式中的“p”表示“原始问题”（primal），
如果w违反了约束条件，即，那么上式变成：
分析上式，若gi(w)>0，那么只要使αi无穷大，θp(w)就会无穷大；若hi(w)≠0，只要使βi相应取无穷大（hi(w)>0）或无穷小（hi(w)<0），θp(w)也会无穷大。
反之，若w满足约束条件，那么θp(w) = f(w)，所以可得：
那么，求min f(w)就是求下式的值，定义为p*：
.
对偶问题
与上面原始问题有略微差别，我们定义：
对其取最大值，即给出对偶优化问题，定义为d*：
显然，我们有：
在某些条件下，会有，因此我们可以通过解决原始问题来解决对偶问题.
原始问题和对偶问题获得相同解的条件：
1、令f为凸函数（凸函数的hessian 矩阵是半正定的，H>=0，即开口朝上的碗状函数）
2、假设hi为仿射函数（(affine，和线性是一样的，只不过是加了截距），即
3、假设gi是严格可执行的，即存在w，使得对于所有i，gi(w)<0
在上述条件下，存在w*，α*，β*，其中w*是原始问题的解，α*，β*是对偶问题的解，并且：
此外，还要满足以下条件：
这些条件被称为KKT条件。（KKT是三个人名的缩写），如果满足KKT条件，那么就是原始问题和对偶问题的解。
其中，称为KKT对偶补充条件。即就是：
如果αi>0 ，那么 gi(w*)=0，但是一般来说αi>0 <=> gi(w*)=0。
当gi(w*)=0，称gi(w*)为活动约束。
SVM对偶
前面，我们有了最优间隔分类器如下：
约束条件可以写为：
通过KKT条件，αi>0 => gi(w,b)=0 => y(i)(wTx(i)+b)=1，即函数间隔为1
给出例子如下图：
图中的圈和叉即正负样本，实线即w,b确定的分割的超平面，最小的间隔是离决定边界最近的点，上图中有三个看出有三个样本的函数间隔为1，其他样本的函数间隔大于1，虚线即为函数间隔为1的点所构成的线。
过KKT条件，这些函数间隔为1的样本对应的拉格朗日乘数一般不等于0， (因为根据KKT对偶补充条件，只有，函数边界才等于 1).。这三个点被称为支持向量（support vector），由此可见，支持向量的数量比训练样本数量小很多。
所以，总结为：αi>0。这个函数间隔为1的样本称为支持向量。因为支撑向量数量很少，所以多数的αi=0，那么反推可得，αi=0，对应的样本不是支撑向量。
对最优间隔优化问题构建拉格朗日算子，有：
由于这个问题只有不等式约束，所以没有β。
对w求偏导并设为0：
推出：
w就是输入特征向量的线性组合。对b求偏导：
将w代入拉格朗日算子，得到：
根据对b求偏导的结果，最后一项为0，得到：
将上式表示为W(α)，对偶问题就是：
为了解决这个对偶问题，求出参数α*，而求出α，即可求出w，求出α和w后，容易求出b，因为w决定了超平面的斜率，那么根据最优间隔，将α和w代入原始问题，就容易求出b了，如下式：
再得到：
这个公式的直观理解就是，找到最差的样本（离得最近的正负样本，也就是支持向量），接着，就只需要计算x和支持向量的内积就可以求出超平面的位置。
