支持向量机SVM推导及求解过程

作者:American199062

        支持向量机是属于原创性、非组合的具有明显直观几何意义的分类算法,具有较高的准确率。

        使用SVM算法的思路:(1)简单情况,线性可分情况,把问题转化为一个凸优化问题,可以用拉格朗日乘子法简化,然后用既有的算法解决;(2)复杂情况,线性不可分,用核函数将样本投射到高维空间,使其变成线性可分的情形,利用核函数来减少高纬度计算量。

       一、SVM相关基本概念

       分割超平面

       设C和D为两不相交的凸集,则存在超平面P,P可以将C和D分离。 

        两个集合的距离,定义为两个集合间元素的最短距离。

        做集合C和集合D最短线段的垂直平分线。

          (图像摘自七月算法)


       但是, 如何定义两个集合的"最优"分割超平面?找到集合“边界”上的若干点,以这些点为“基础”计算超平面的方向,以两个集合边界上的这些点的平均作为超平面的“截距”。这些点被称作支持向量,点是可用向量方式表示。

       (图像取自七月算法)

        

        输入数据

        假设给定一个特征空间上的训练数据集

其中,,为第i个实例(若n>1,即x是多维度,具有多个属性特征,此时为向量);

        的类标记,当为+1时,称为正例,当为-1时,称为负例。

       

       线性可分支持向量机

        给定线性可分训练数据集,通过间隔最大化得到的分离超平面为,相应的分类决策函数该决策函数称为线性可分支持向量机。其中,是某个确定的特征空间转换函数,它的作用是将x映射到(更高的)维度,最简单直接的:。事实上,求解分离超平面问题可以等价为求解相应的凸二次规划问题。


      整理符号

        分割平面:

        训练集:

        目标值:

        新数据的分类:


 二、SVM推导过程

       推导目标函数

        根据题设

        有:

      w,b等比例缩放,则t*y的值同样缩放,从而


        最大间隔分离超平面

        目标函数:表示最近点到直线距离尽可能大


(图像取自七月算法)

        函数间隔和几何间隔

       分割平面:  (函数间隔)

       总可以通过等比例缩放w的方法,使得两类点的函数值都满足

             (图像取自七月算法)


     建立目标函数

       1.总可以通过等比例缩放w的方法,使得两类点的函数值都满足

       2.约束条件:

       3.原目标函数:

       4.新目标函数:

                       

       5.目标函数变换一下:

                       

        6.拉格朗日乘子法

                      

         7.原问题是极小极大问题

                      

                       原问题的对偶问题是极大极小问题

         8.将6中的拉格朗日函数分别对w, b 求偏导并令其为0:

                       

           9.计算拉格朗日的对偶函数

                        

         10.继续求的极大

                      

         11.整理目标函数:添加负号

                      

        12.线性可分支持向量机学习算法

               计算结果如下

                      

        13.分类决策函数

                        

       三、线性不可分SVM

         1.若数据线性不可分,则增加松弛因子,使函数间隔加上松弛变量大于等于1,

         则约束条件变成

                         

         目标函数:    (这里是为了保证松弛因子不至于过大)

         2.此时的凸优化为

                        

          3.拉格朗日函数

                         

        4.将三式代入L中,得到

                      

       5. 整理,得到对偶问题的最优化问题

                    

      求得最优解

      6.计算

                   

       实践中往往取支持向量的所有值取平均,作为b*

       7.求得分离超平面

       8.分类决策函数为

     


       核函数:可以使用核函数,将原始输入空间映射到新的特征空间,从而使得原本线性不可分的样本可在核空间可分。

       有多项式核函数

       高斯核函数RBF 

       字符串核函数

        在实际应用中,往往依赖先验领域知识或交叉验证等方案才能选择有效的核函数。没有更多先验信息,则使用高斯核函数。

核函数映射:

                          (图像取自七月算法)

                         (图像取自七月算法)


                  高斯核

                                       (图像取自七月算法)

          粗线是分割超“平面”,其他线是y(x)的等高线,绿色圈点是支持向量点。

          高斯核是无穷维的,因为


          注:SVM和Logistic回归的比较:(1)经典的SVM,直接输出类别,不给出后验概率;(2)Logistic回归,会给出属于哪一个类别的后验概率;(3)比较重点是二者目标函数的异同。

       

发表评论

2个评论

  • m0_37309838

    有一点不太明白 拉格朗日乘子法 到原问题的极小极大问题 那步骤 ,为什么要 MAX(L,W ,a)呢?还请赐教

    2017-03-03 09:24:08回复

  • m0_37309838

    有一点不太明白 拉格朗日乘子法 到原问题的极小极大问题 那步骤 ,为什么要 MAX(L,W ,a)呢?还请赐教

    2017-03-03 09:23:28回复

我要留言×

技术领域:

我要留言×

留言成功,我们将在审核后加至投票列表中!

提示x

人工智能机器学习知识库已成功保存至我的图谱现在你可以用它来管理自己的知识内容了

删除图谱提示×

你保存在该图谱下的知识内容也会被删除,建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗?

删除节点提示×

无法删除该知识节点,因该节点下仍保存有相关知识内容!

删除节点提示×

你确定要删除该知识节点吗?