SVM是机器学习中神一般的存在，虽然自深度学习以来有被拉下神坛的趋势，但不得不说SVM在这个领域有着举足轻重的地位。本文从Hard SVM 到 Dual Hard SVM再引进Kernel Trick，然后推广到常用的Soft Kernel SVM。
一、Hard SVM
SVM本身是从感知机算法演变而来，感知机算法是在一个线性可分的数据集中找到一个分类超平面，尽可能的将数据集划分开，理论上这样的超平面有无数多个，但是从直觉上，我们知道离两侧数据都比较远的超平面更适合用于分类，于是我们选择了一个比较“胖”的边界的超平面作为分类界，这就是SVM。
我们知道一个超平面wx+b=0，w是这个超平面的法向量，则平面外一点到这个平面的距离为：d=1/||W||*|Wx+b|（解析几何的知识）。绝对值符号会导致函数不平滑，又因为数据集是线性可分的，所以我们可以把距离公式改写为：d=1/||W||*y·(Wx+b)（具体可以参考感知机）。那么我们就有了最基本的优化对象：
max margin(b,w)
subject to:for every n y·(Wx+b)>0
margin(b,w) = min d
我们知道同时放缩一个超平面的系数并不会改变这个超平面，such as 3wx+3b=0=wx+b，所以我们可以假设离我们超平面最近的那个向量到平面的距离为1，即让y·(Wx+b)=1，那么原来的优化问题就变为了：
max 1/||W||
subject to:for every n y·(Wx+b)>0 (已经满足)
min y·(Wx+b)≥1
最大化问题不是很好解决，我们可以转换为我们熟悉最小化问题：
min 0.5*W*W
subject to:min y·(Wx+b)≥1
很明显这是一个二次规划问题，我们有成熟的算法如SMO，来解决这样的问题。
二、Dual SVM
对于一个已经解决的问题，为什么我们还要考虑它的对偶问题？这是因为化作对偶问题后会更容易求解，同样也方便引入Kernel Trick。
考虑原始SVM问题：
min 0.5*W*W
subject to:all i y·(Wx+b)≥1
我们改变其形式，转化为：
min(max 0.5*W*W+∑α(1-y·(Wx+b)))
我们发现如果满足了条件α的值会变成0，如果不满足就会变成+∞，以此来约束我们的条件。然后我们从极小极大的问题转换为极大极小的问题。
min(max 0.5*W*W+∑α(1-y·(Wx+b))) ≥ min(0.5*W*W+∑α(1-y·(Wx+b))
min(0.5*W*W+∑α(1-y·(Wx+b))≥max(min 0.5*W*W+∑α(1-y·(Wx+b)))
而max(min 0.5*W*W+∑α(1-y·(Wx+b)))就是我们的Lagrange Dual Problem。这是我们原问题的一个下界，那么什么时候能够取得等号呢？根据拉格朗日对偶问题，当优化函数和条件是凸函数时，对偶问题是原问题的解的充要条件即为KKT 条件。然后我们求解对偶问题的极小问题，对w，b求偏导，令其等于0，得到结果为
L(w,b,α)=-0.5*||∑αyx||+∑α
我们就可以来解决极大问题了，原始优化问题就可以转化为：
max -0.5*||∑αyx||+∑α
这显然又是一个二次规划问题！所以就可以求解了，然后用KKT条件来求解w,b。这就是对偶问题的求解方案。
三、Kernel Trick
当数据不是线性可分的，那么SVM就失去了作用，但是我们可以寻找一种函数将数据映射到更高维的空间中，以此把问题变成一个线性可分的问题，但是这会带来维度的急剧上升，使得模型求解效率大大下降，而Kernel Trick就是为了解决这样的问题而出现的！（下回补完！）
四、Soft SVM