此前我们介绍了一个最优化分类算法 — logistic 回归。 Logistic 回归数学公式推导 本文中,我们再来介绍另一个最优化分类算法 — SVM。
SVM 是 Support Vector Machines 的缩写,一般称为“支持向量机”或“支持矢量机”。 我们有下图这些点,如何将红点和蓝点分开呢?
下面两图中的线都可以做到让区分两类点的目的:
图中 A 和 B 两条线都实现了红蓝点分类的目的,A 和 B 就称为“决策面”,显而易见,因为数据是二维的,所以决策面是一维的线,如果数据是三维的,那么决策面将会是一个二维的平面,也就是说,决策面总是数据维度数 - 1 维的,因此也叫“分隔超平面”。
那么上图中的 A 和 B 究竟哪个分类方法的效果更好呢? 目前的情况来看,分类器A和B都可以做到完全划分,其效果是相同的,但假设我们再添加一个点,这个点是否仍然可以被 A、B 正确分类呢?
A 顺利完成了对新点的划分,而 B 决策面则划分错误,这是为什么呢? 因为我们假定新的点仍然在原来类别的范围附近,那么,很容易理解,决策面离原有数据越远,则划分准确性越高。 注意观察你会发现,上图中在决策面的左右各有一条虚线,这两条虚线分别与两侧最近的样本点相交,且平行于决策面,虚线与决策面的距离就是“分类间隔”,显然每一个可能把数据集正确分开的方向都有一个最优决策面,而不同方向的最优决策面的分类间隔通常是不同的,那个具有“最大间隔”的决策面就是SVM要寻找的最优解。 而这个真正的最优解对应的两侧虚线所穿过的样本点,就是SVM中的支持样本点,称为”支持向量”。
既然我们知道了 SVM 的原理,SVM 的优点就非常明显了:
这样,我们推导出了 n 维坐标系内决策面方程,我们称之为“超平面方程”。
根据本文开头的描述可知,分类效果最好的超平面是分类间隔 2d 最大的超平面,我们已经成功将问题推导为求解当 d 取最大值时 ω 的取值。
求解 d 取最大值时 ω 的取值存在以下两个约束条件:
我们成功将求解 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。