SVM是机器学习中神一般的存在,虽然自深度学习以来有被拉下神坛的趋势,但不得不说SVM在这个领域有着举足轻重的地位。本文从Hard SVM 到 Dual Hard SVM再引进Kernel Trick,然后推广到常用的Soft Kernel SVM。

 

  一、Hard SVM

  SVM本身是从感知机算法演变而来,感知机算法是在一个线性可分的数据集中找到一个分类超平面,尽可能的将数据集划分开,理论上这样的超平面有无数多个,但是从直觉上,我们知道离两侧数据都比较远的超平面更适合用于分类,于是我们选择了一个比较“胖”的边界的超平面作为分类界,这就是SVM。

  我们知道一个超平面wx+b=0w是这个超平面的法向量,则平面外一点到这个平面的距离为:d=1/||W||*|WTx+b|(解析几何的知识)。绝对值符号会导致函数不平滑,又因为数据集是线性可分的,所以我们可以把距离公式改写为:d=1/||W||*yi·(WTxi+b)(具体可以参考感知机)。那么我们就有了最基本的优化对象:

                              maxw,b  margin(b,w)

                        subject to:for every n yi·(WTxi+b)>0

                            margin(b,w) = minw,b d

  我们知道同时放缩一个超平面的系数并不会改变这个超平面,such as 3wx+3b=0=wx+b,所以我们可以假设离我们超平面最近的那个向量到平面的距离为1,即让yi·(WTxi+b)=1,那么原来的优化问题就变为了:

                                   maxw,b  1/||W||

                        subject to:for every n yi·(WTxi+b)>0 (已经满足)

                               mini yi·(WTxi+b)≥1

  最大化问题不是很好解决,我们可以转换为我们熟悉最小化问题:

 

                                    minw,b  0.5*WT*W

                               subject to:mini   yi·(WTxi+b)≥1

  很明显这是一个二次规划问题,我们有成熟的算法如SMO,来解决这样的问题。

 

  二、Dual SVM    

  对于一个已经解决的问题,为什么我们还要考虑它的对偶问题?这是因为化作对偶问题后会更容易求解,同样也方便引入Kernel Trick。

  考虑原始SVM问题:      

                                   minw,b  0.5*WT*W

                             subject to:all i   yi·(WTxi+b)≥1

  我们改变其形式,转化为:

                          minw,b(maxall α>0  0.5*WT*W+∑α(1-yi·(WTxi+b)))

  我们发现如果满足了条件α的值会变成0,如果不满足就会变成+∞,以此来约束我们的条件。然后我们从极小极大的问题转换为极大极小的问题。  

     minw,b(maxall α>0  0.5*WT*W+∑α(1-yi·(WTxi+b))) ≥ minw,b(0.5*WT*W+∑α(1-yi·(WTxi+b))

    minw,b(0.5*WT*W+∑α(1-yi·(WTxi+b))≥maxall α>0(minw,b  0.5*WT*W+∑α(1-yi·(WTxi+b)))

  maxall α>0(minw,b  0.5*WT*W+∑α(1-yi·(WTxi+b)))就是我们的Lagrange Dual Problem。这是我们原问题的一个下界,那么什么时候能够取得等号呢?根据拉格朗日对偶问题,当优化函数和条件是凸函数时,对偶问题是原问题的解的充要条件即为KKT 条件。然后我们求解对偶问题的极小问题,对w,b求偏导,令其等于0,得到结果为

                              L(w,b,α)=-0.5*||∑αyx||2+∑α

  我们就可以来解决极大问题了,原始优化问题就可以转化为:

                             maxall α>0∑yα = 0 w=∑αyx   -0.5*||∑αyx||2+∑α

  这显然又是一个二次规划问题!所以就可以求解了,然后用KKT条件来求解w,b。这就是对偶问题的求解方案。

 

  三、Kernel Trick

  当数据不是线性可分的,那么SVM就失去了作用,但是我们可以寻找一种函数将数据映射到更高维的空间中,以此把问题变成一个线性可分的问题,但是这会带来维度的急剧上升,使得模型求解效率大大下降,而Kernel Trick就是为了解决这样的问题而出现的!(下回补完!)

 

  四、Soft SVM