Machine Learning Techniques 笔记：2-4 Soft-Margin Support Vector Machine
有效率：像linear的方向走。
想要弯弯曲曲的复杂边界：网Gaussian kernel方向走。
Kernel：把转换与算内积两个步骤合起来，可以用dual SVM解决很多维度，可以实现无限多维转换。
SVM也可能会overfit，一部分可能来源于很强的转换，另一部分也可能来自你坚持一定坚持要完美的分开。
Pocket：找不到完美的线分来，我们找一个错误最少的线。 放弃对零差错的追求
Hard-margin svm：所有的点分对，而且要求1/2wTw最小的，即w的长度最小的。
做错的点不管，大于等于-inf
做对的点，大于等于1.
像pocket那样，找到犯错最小，又好满足svm，w越短越好? 如何权衡：找一个C代表犯错的重要度，C越大，代表不要犯错越好，C小，代表找到的w越短越好。 究竟是重视margin，还是重视分数（正确分类）？
缺点：因为里面有boolean的运算，已经不是一个线性问题===》不再是一个QP问题，之前推到的dual，kernel均不再适合。
今天的犯错，如果跟正确相比之相差一点点，与边界很接近，几乎要对，上面的公式无法区分小错与大错。
把犯错数量，记录在kesi中，距离1很远，大错。距离1很近，小错。
记录惩罚的错误项：犯错的程度，而不是犯错的数目。这样转化以后，看起来还是一个QP问题。
小C：可能有更多的错，但是margin较大。
N个变数：每个点到底违反了多少margin
多了N个条件。
kesi 1，违反边界的数量。
Lagrange函数，与之前hard margin Lagrange 函数类似。
利用KKT条件进行简化。 用beta = C - Alpha，则可以消除后面的与kesi 相关的那一项，让式子变简单，这样就之需要考虑alpha即可。藏起来的条件是（beta = C - Alpha）
此时，就得到了跟原来hard-margin的对偶问题几乎一样的式子，只是alpha多了一个上限：C
alpha 有N个变数
每个alpha 有一个下限0，一个上限C，结合一个线性条件，共有2N+1个限制条件。
C+2，alpha的限制也会从10变成12
Kernel SVM：与原来的SVM相比，增加了upper-bound（从C参数而来）的限制条件
在这个问题中，算b的方式与Hard-margin中的方法一样吗？
soft-margin是实际上最常用的SVM形式
hard-margin：alpha，与后面的（1-y（wx+b））不能同时为0
beta = C - alpha ，==》（C-alpha）kesi = 0
如果kesi = 0，则alpha 不能等于C
绝大多数情形，都有free-support-vector的情形。如果没有，则从得到的一大堆b中做选择。
C越大，资料上犯错越来越少，对杂讯的容忍度越来越低。
即便是soft-margin SVM，也有可能会overfit，需要很仔细的选择参数
Free support vector：kesi = 0，就是方框，刚好在胖胖的边界上的点。
kesi = 0，没有违反胖胖边界的点。这些点，大多数在胖胖的边界外面。
alpha = C，代表kesi = 1-y-y（wz+b），则对应了三角形的情形，刚好违反。 小小的违反：没有错误分类，只是不满足margin要求。 严重的违反：已经远离边界。
最好的情况：Ein = 0
最差的情况：所有的点全部越界，1000/10000 = 0.1
选参数很重要。如何选？validation
利用cross-validation error最小的模型。
通常只能考到送进去的c与gama的性能如何，无法对C与gama做最优化。
拿掉non-support vector，对胖胖的边界无影响。
每次留1笔作为validation，其余都做 training
leave one out CV error会小于support vector的比例。
此处，只是一个上限，而不是真正得到了一个好的边界。
通常只是用于排除危险的点。 leave one out》 得到support vector的上限。
我们希望不要坚持一定要把xxoo分开，加上了一个large margin的惩罚项kesi。推到的时候发现这还是一个QP问题，因而可以推导它的QP的对偶问题，发现它跟hard-margin几乎一样，只是alpha上面压着一个C而已。
他告诉我们，透过soft-margin SVM，可以把data分成三种，不是support vector,不重要的，边界上的，bounded的，可能违反了边界的胖胖的support vector,对于我们资料的分析很重要。
可以用leave one out作为模型的选择。