SVM 数学描述的推导

2019-01-13 14:49:26   最后更新: 2019-01-14 15:52:11   访问数量:226




此前我们介绍了一个最优化分类算法 -- logistic 回归

Logistic 回归数学公式推导

本文中,我们再来介绍另一个最优化分类算法 -- SVM

 

SVM 是 Support Vector Machines 的缩写,一般称为“支持向量机”或“支持矢量机”

我们有下图这些点,如何将红点和蓝点分开呢?

 

下面两图中的线都可以做到让区分两类点的目的:

 

 

图中 A 和 B 两条线都实现了红蓝点分类的目的,A 和 B 就称为“决策面”,显而易见,因为数据是二维的,所以决策面是一维的线,如果数据是三维的,那么决策面将会是一个二维的平面,也就是说,决策面总是数据维度数 - 1 维的,因此也叫“分隔超平面”

 

那么上图中的 A 和 B 究竟哪个分类方法的效果更好呢?

目前的情况来看,分类器A和B都可以做到完全划分,其效果是相同的,但假设我们再添加一个点,这个点是否仍然可以被 A、B 正确分类呢?

 

A 顺利完成了对新点的划分,而 B 决策面则划分错误,这是为什么呢?

因为我们假定新的点仍然在原来类别的范围附近,那么,很容易理解,决策面离原有数据越远,则划分准确性越高

注意观察你会发现,上图中在决策面的左右各有一条虚线,这两条虚线分别与两侧最近的样本点相交,且平行于决策面,虚线与决策面的距离就是“分类间隔”,显然每一个可能把数据集正确分开的方向都有一个最优决策面,而不同方向的最优决策面的分类间隔通常是不同的,那个具有“最大间隔”的决策面就是SVM要寻找的最优解

而这个真正的最优解对应的两侧虚线所穿过的样本点,就是SVM中的支持样本点,称为”支持向量”

 

优点

既然我们知道了 SVM 的原理,SVM 的优点就非常明显了:

  1. 错误率低
  2. 计算开销不大
  3. 结果容易理解
  4. 可视化

 

缺点

  1. 对参数调节和核函数敏感
  2. 原始分类器只能处理二分类问题

 

 

这样,我们推导出了 n 维坐标系内决策面方程,我们称之为“超平面方程”

 

 

 

根据本文开头的描述可知,分类效果最好的超平面是分类间隔 2d 最大的超平面,我们已经成功将问题推导为求解当 d 取最大值时 ω 的取值

 

求解 d 取最大值时 ω 的取值存在以下两个约束条件:

  1. 如何判断超平面是否将样本点正确分类
  2. 如何在众多样本点中选取支持向量上的点

 

 

 

 

我们成功将求解 d 的最大值问题推导为求解 ||ω|| 最小值问题

 

我们将 SVM 优化问题转化为了一个有不等式约束的优化问题,这类方法通常使用 KKT 条件求解

 

无约束优化问题

 

通常使用的方法是费马引理,即求取函数f(x)的导数,然后令其为零,可以求得候选最优值,再在候选最优值集合中取值验证从而得到最优解

 

有等式约束的优化问题

 

这类问题通常使用拉格朗日乘子法,把等式约束h(x)用一个系数与f(x)写为一个式子,称为拉格朗日函数,而系数则被称为拉格朗日乘子

通过拉格朗日函数对各个变量求导,令其为零,可以求得候选值集合,然后验证求得最优值

 

有不等式约束的优化问题

 

这类问题的求解通常使用 KKT 条件

把所有的等式、不等式约束与f(x)写为一个式子,也叫拉格朗日函数

通过一些条件,可以求出最优值的必要条件,这个条件称为KKT条件

 

那么如何用拉格朗日函数与 KKT 条件求解我们的目标函数呢?敬请关注下一篇文章

 

欢迎关注微信公众号,以技术为主,涉及历史、人文等多领域的学习与感悟,每周三到七篇推文,全部原创,只有干货没有鸡汤

 

 

《机器学习实战》

https://zhuanlan.zhihu.com/p/24638007

http://blog.pluskid.org/?page_id=683

https://blog.csdn.net/c406495762/article/details/78072313

 






算法      机器学习      最优化      svm      支持向量机      高等数学     


京ICP备15018585号