NLP自然语言处理系列5-支持向量机(SVM)

释放双眼,带上耳机,听听看~!

1.什么是支持向量机

  支持向量机(Support Vector MachineSVM)是一种经典的分类模型,在早期的文档分类等领域有一定的应用。了解SVM的推导过程是一个充满乐趣和挑战的过程,耐心的看完整个过程,你会受益良多。所以,小Dream也决定好好讲一讲SVM的推导过程,还是跟此前一样,讲解务必追求通俗易懂,深入浅出。

  首先要说的是,支持向量机最主要是用于分类。假设有一个训练样本集D={x1,y1),(x2,y2),(x3,y3),...xn,yn},支持向量机分类学习最主要的思想就是基于训练集D在样本空间中,找到一个划分超平面,将不同类别的样本分开。

NLP自然语言处理系列5-支持向量机(SVM)

类别划分超平面

 

  如图一所示,那些能够将+-两类样本分开的直线(超平面),都是合理的分类器。那么,哪个分类器是最优的呢?我们可以看到,当一个新的样本(样本可能有扰动)出现在图中4个红色圆圈所在位置时,分类器1245就极有可能把他分错。根据图一,肉眼可见,分类器3是图中的最优分类器,因为它忍受样本干扰的能力是最强的,用术语说,就是最鲁棒的。那么怎么从数学上来定义这个最优的超平面呢?

 

  在样本空间中,假设划分超平面是这样的一个平面:

 

         NLP自然语言处理系列5-支持向量机(SVM)                   1

  NLP自然语言处理系列5-支持向量机(SVM)称为超平面的法向量,b定义了超平面到空间远点的距离,回忆一下高中的立体几何,我们知道,超平面可以由NLP自然语言处理系列5-支持向量机(SVM)b唯一确定。那么。怎么样的一个超平面是最优的呢?

  首先,我问这样一个问题,样本空间中任意一个样本,到该划分超平面的距离应该怎么表示?(赶紧回忆一下,点到平面的距离

 NLP自然语言处理系列5-支持向量机(SVM)    (2

 

  我们先假设超平面NLP自然语言处理系列5-支持向量机(SVM)能够将所有的样本正确的进行分类。对任意NLP自然语言处理系列5-支持向量机(SVM)如果样本属于正类,则有yi=+1,且NLP自然语言处理系列5-支持向量机(SVM);如果样本属于负类,则有yi=-1,且NLP自然语言处理系列5-支持向量机(SVM)

  我们可以选择合适的b,使得离超平面最近的哪一类点满足如下的条件:NLP自然语言处理系列5-支持向量机(SVM),这些点就称为支持向量。那么所有样本可以这样表示:

NLP自然语言处理系列5-支持向量机(SVM)(3)

  如图二所示,支持向量用圈圈圈住了。两个异类的支持向量的距离可以表示为:NLP自然语言处理系列5-支持向量机(SVM)   (4)

  NLP自然语言处理系列5-支持向量机(SVM)图二 支持向量与间隔

  那么选择最优的划分超平面就可以转为成如下的数学表达式:

                                  NLP自然语言处理系列5-支持向量机(SVM)        (5)

 

  为了计算简便,(5)式等价于如下:

                                  NLP自然语言处理系列5-支持向量机(SVM)        (6)

  怎么样,这就是SVM的基本型了,有没有感受到数学语言的魅力?简洁、明确而又优美。

  

2. 支持向量机如何学习

  

  既然我们明确了SVM是个怎么样的问题,接下来要考虑的就是如何利用数据集D求得上述的超平面。

  我们期望根据式6,获得一个模型:

                                  NLP自然语言处理系列5-支持向量机(SVM)             (7)

  

  式6是一个凸二次规划问题,可能会有相关的优化计算包可以求解。但是SVM有自己的更为高效的求解方式,我们来好好说一下。

 

  求解这种带限制条件的极值问题,用的最多的应该式拉格朗日乘子法。我们对式6的每个约束条件乘以拉格朗日乘子NLP自然语言处理系列5-支持向量机(SVM):

                  NLP自然语言处理系列5-支持向量机(SVM)            (8)

  其中NLP自然语言处理系列5-支持向量机(SVM)为拉格朗日乘子向量,注意向量的长度和数据集D中样本的数目相同。根据拉格朗日极值法,分别对wb求偏导,并取极值得到:

                            NLP自然语言处理系列5-支持向量机(SVM)                    (9)

                            NLP自然语言处理系列5-支持向量机(SVM)                     (10)

  将式(9)(10)带入式(8),可以得到:

                          NLP自然语言处理系列5-支持向量机(SVM)

  

  参考https://blog.csdn.net/zlsjsj/article/details/80522650

  我们可以得到式6的对偶问题:

                              NLP自然语言处理系列5-支持向量机(SVM)      (11)

  

  这么多公式,相信大家看到都有点烦了,这里总结一下,理一理思路。

  我们得到式6SVM基本型之后,想要用一种高效的方式来求解SVM的划分超平面。在限定条件下的极值问题,我们想到了拉格朗日乘子法。通过求偏导、解极值之后,我们消去wb,问题变成了解决式6的对偶问题式11。这样的话,求解wb就转化成了求解拉格朗日乘子NLP自然语言处理系列5-支持向量机(SVM)。将所有拉格朗日乘子求出之后,就得到了模型:

                              NLP自然语言处理系列5-支持向量机(SVM)

  

  这里我们注意,拉格朗日乘子的个数与数据集样本的个数相同。

  那么,式11该如何高效的求解呢?下面我们SMOSequential Minimal Optimization)算法就登场了。

  SMO算法的基本思路是各个击破,逐个参数优化求解。具体来说就是,先选定一个参NLP自然语言处理系列5-支持向量机(SVM),然后固定除NLP自然语言处理系列5-支持向量机(SVM)之外的所有其他参数,这样就可以根据式11求极值,求得合适的NLP自然语言处理系列5-支持向量机(SVM)。具体来说,是这样的,先选定两个参数NLP自然语言处理系列5-支持向量机(SVM)NLP自然语言处理系列5-支持向量机(SVM),根据式11的限制条件会有:

                              NLP自然语言处理系列5-支持向量机(SVM)      (12)

  其中,NLP自然语言处理系列5-支持向量机(SVM)

  可以用式12NLP自然语言处理系列5-支持向量机(SVM)NLP自然语言处理系列5-支持向量机(SVM)来表示,带入到式11中,得到一个关于NLP自然语言处理系列5-支持向量机(SVM)的单变量二次规划(二次函数求极值)问题,就可以高效的进行求解了。

  

2. SVM中的核函数

  上述的SVM问题的定义及求解过程中,隐含了一个假设,就是存在一个超平面,能够将两类样本分开,即问题是线性可分的。那么,如果问题不是线性可分的呢?例如,很简答的“异或”问题就是线性不可分的。

  NLP自然语言处理系列5-支持向量机(SVM)

                                图三 线性不可分问题及其非线性映射

  

  如图三所示,在二维空间中,没有办法找到一条直线,将“异或”问题进行正确的区分。那么如何解决线性不可分的问题呢?在图三中,将四个样本经过一个映射函数,映射到三维空间中,就可以通过一个平面将该问题划分开了。

  这样我们就有了利用SVM去分类线性不可分问题的思路了。我们可以通过一个映射函NLP自然语言处理系列5-支持向量机(SVM),将样本从原空间映射到高维空间,再利用上面章节的SVM原理进行分类就可以了。

 

  下面我们再简单说一下利用升维的办法用SVM进行分类的过程。

  训练样本集NLP自然语言处理系列5-支持向量机(SVM)经过NLP自然语言处理系列5-支持向量机(SVM)进行映射,变成了NLP自然语言处理系列5-支持向量机(SVM),那么我们要获得这样一个模型:

                                NLP自然语言处理系列5-支持向量机(SVM)              (13)

  在如下的限制条件下:

                                NLP自然语言处理系列5-支持向量机(SVM)            (14)

  同样,得到它的对偶问题:

                              NLP自然语言处理系列5-支持向量机(SVM)   (15)

  同样,问题的本质并没有改变,我们其实还是可以用SMO算法求解向量NLP自然语言处理系列5-支持向量机(SVM)。只是多了一步,要计算NLP自然语言处理系列5-支持向量机(SVM),当样本空间的维度很大时,这个计算量时很大的。为了简化计算,我们聪明的算法专家提出了核函数的概念,所谓核函数,就是为了简化上述计算而设计出来的函数,它满足如下要求:

                              NLP自然语言处理系列5-支持向量机(SVM)     (16)

  那么式15就可以改写为:

                              NLP自然语言处理系列5-支持向量机(SVM)     (17)

  

  我们仔细回顾下抑或问题的映射过程,可以发现,其实映射过程不是唯一的,只要满足一定的性质,映射函数可以很多,同样核函数也可以很多。

 

  我们先列出来常用的核函数:

    NLP自然语言处理系列5-支持向量机(SVM)

                                    图四 常用核函数列表

  那么,加入我们使用的高斯核,则式17可以表示为:

                        NLP自然语言处理系列5-支持向量机(SVM)       (18)

  

  我们可以看到加入核函数后,能够顺利解决线性不可分的问题,但是计算过程却并没有因此而变得复杂。

 

  关于核函数的选择以及过拟合的处理,可以用软间隔的技术,大体的思想就是在最大化间隔的同时,允许一些样本出现在间隔里。感兴趣的同学可以出门百度一下,这里不再详述。

  这篇博客可能没有太多原创的思考,但是都是小Dream根据自己的理解一个字一个字码的,可能在遣词造句上没有教科书那么严谨。但是我觉得技术博客存在意义就在于用一种朴实易懂的语言介绍一些在实际工作中非常实用的技巧、经验和技术。

  

---------------------------------------------------------------------------------------------------------------------------------

分享时刻:

 

  你要记住,人生聚散起伏太常见。生命太短,铭记那些温暖与真诚吧,倒掉那些凉掉的茶水。

  NLP自然语言处理系列5-支持向量机(SVM)

 

 

 

给TA打赏
共{{data.count}}人
人已打赏
随笔日记

ASP.NET Core中自定义路由约束

2020-11-9 3:58:41

随笔日记

【springboot】之自动配置原理

2020-11-9 3:58:44

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索