1、课程主要内容
介绍向量机的对偶形式，上次讲述了线性支持向量机，找到可以正确分类中最“胖”的那条分隔面，越胖分类器就越健壮。
对偶支持向量机是线性支持向量机的另外一种形式。
2、原始SVM的复习，使用对偶形式的SVM的动机或者好处
非线性支持向量机的原始问题：
通过对原有数据的非线性变换后替换原有的的x到z空间上，从而得到非线性的支持向量机，其解法也是使用二次规划：
其中d为w的维度，如果存在一个线性的支持向量机后配合非线性变换Φ(x)就可以得到一个非线性的支持向量机。
为什么要这么做？通过边界可以控制复杂度，同时可以得到一个非线性的分类器；
但是在使用二次归化算法时，w的维度是和数据的特征的个数有关系的，如果数据的特征比较多或者是无无限多的那该怎么办？
目标：
将SVM的变量与w维度有关的变换到只与数据输入量有关：
基本工具就是拉格朗日乘子法，解决有约束条件下的优化问题。在正则化时，其基本问题如下：
在约束条件下进行求解最小的Ein时，采用拉格朗日乘子法将约束条件加入到优化目标函数中，通过
(1) 在优化过程中检查优化状态达到限制条件C与λ的对等
(2) 解最优化问题时通过给定λ来代替C使得优化算法的易实现性
但是在对偶形式的支持向量机中，我们不把λ作为已知量，而是作为一个未知量看待，这是与正则化的区别。思考一下λ的数量，由于原始问题中的限制条件是由每个点被正确分类所限制的，因此在数据数据规模为N时，限制条件的个数为N，因此λ的数量也是N个，为了方便我们可以建立一个N维 的向量保存每一个λ。
通过拉格朗日函数将原始的带有约束条件的SVM转化成没有约束条件的SVM：
原始的SVM问题即带有约束条件的SVM问题：
通过使用拉格朗日函数可以得到下面的函数：
函数说明：
第一部分：最小化目标；
第二部分：将N个限制条件合在一起加入到函数中。
假设SVM问题如下：
该表达式的意思：在给定的w和b的条件下计算拉格朗日函数的最大值，然后通过调整w和b在这些最大值中挑选一个最小的最为SVM的优化解。这样做合理吗？
(1)、当w和b不满足约束条件时，即
不满足，那么拉格朗日函数中的后面的求和项每一项都是正的，那么第二项的最大值必然是无穷大；
(2) 当w和b满足条件时，拉格朗日函数的求和项全部都是负的，因此其最大值必然为0，此时拉格朗日函数的最后的结果还是原有的优化目标。
综上两个条件可知，整个拉格朗日函数最的最优结果选择的是最小min因此在w和b不满足时为无穷大，在满足时为原有的优化目标，这样就把限制条件隐藏到了整个函数内，达到了从有明显的限制到隐藏的限制的目的。
3、 拉格朗日的进一步优化
由于对α的最大化操作，因此在一个w和b确定下，对于一个固定的α都有上式必然成立。同样对于右侧的式子来说，左侧的式子大于右侧的式子那么必然也大于右侧式子的最大值，因此便有了以下的结论：
有趣的是min和max换了位置，这个问题就是拉格朗日对偶问题，导出了原有目标优化的一个下限值。
原有SVM的等价形式与拉格朗日对偶形式的SVM之间的关系：
(1) 
弱对偶关系
(2) 
当两者关系是相等时表示是强对偶，但是对于二次规划问题来说，满足以上三个条件：凸优化，数据线性可分有解，线性的限制条件时就是限制条件满足，此时也是强对偶关系，即可以通过解右侧的函数达到左侧函数的目标。
对偶形式的SVM的进一步简化：
对于这个问题，首先考虑min最小化的部分，此部分针对w和b进行求解，当某一组w和b为解时，根据梯度下降可知在解处拉格朗日函数对w和b的微分值都为0，那么有：
此时如果将上述推导的拉格朗日函数关于b的微分作为一个限制条件加入到优化函数中，必然不会影响原有解，同时对第二项进行展开可以得到一个优化条件项，此时就把b消除掉：
相同的套路针对w的微分，得到w关于α，x，y的表达式，同样将该表达式作为条件带入到原有的表达式中
得到：
KKT 优化条件：
(1) 数据可分
(2) 满足对偶乘子的条件
(3) 对偶的内在条件，通过微分求出的
(4) 原始条件的内在条件，即与乘子相乘后的值必须为0，那么乘子的值为0，要不后面的表达式为0，当乘子不为0时，那么后面的表达式就是0，那么表示该数据点到分隔面的距离为1，也就是到分隔面的最小距离，此时该点就是支持向量。
4、 对偶形式的SVM的解法
经过上面的推导可以得出对偶形式的SVM为：
那么在对以上的形式做出变化，即由最大化变为最小化，当式子大于0时可以采用取倒数，在式子小于0 时可以取负号，于是整个式子可以变为：
同时把限制条件拿出来单列出来，同时不考虑w和a的关系，此条件为隐藏条件，不考虑，此时共有N+1个条件，N个a变量；
使用二次规划来解该问题四个二次归化参数的对应关系：
计算过程中的问题：
Q矩阵会很大：
因此需要一个专有的SVM解法程序：
因此优先选择专用的解法程序。
5、找到w和b
根据KKT优化准则：
对于w来说KKT条件的第三条可以i知道w和a的关系：
那么怎么计算b，从上面的KKT条件可知，，知道w后可以根据KKT的第一条准则：
可以计算出一个关于b的一个范围，但是不是定值，因此此条件不能用。对于准则4，只有有一个α>0，那么可以得到：
便可以通过此式得到：
推导此式用到了1/y = y，因为y = {-1, +1};同时该点就是支持向量，他就在那个胖胖的边界上。
6、关于支持向量
上面在解b的时候推导出：
也就是说输入向量的第n个数据就是一个支持向量，此时我们可以根据α的取值来找到那些真正的支持向量：在边界上同时α>0，一个点可能在边界上但是α=0那么这个点就不是支持向量。
支持向量的作用：
SVM与PLA之间的关系
7、下一讲
通过对偶形式的SVM将d个变量变成了N个变量，看似与d 无关了，但是在计算Q矩阵时zn、zm都是d维的，那么这样计算还是与d有关，那么怎么才能与d无关，只能在Q矩阵的计算方法上做改进，下一讲告诉你。
