“学习的同时记录,记录的同时分享,分享的同时交流,交流的同时学习。”
SVM现在主流的有两个方法。一个是传统的推导,计算支持向量求解的方法,一个是近几年兴起的梯度下降的方法。梯度下降方法的核心是使用了hinge loss作为损失函数,所以最近也有人提出的深度SVM其实就是使用hinge loss的神经网络。
本文的目的是讲解传统的推导。
SVM模型的基本原理,就是寻找一个合适的超平面,把两类的样本正确分开。单个SVM只能处理二分类,多分类需要多个SVM。
【什么是超平面?】 超平面就是n维度空间的n-1维度的子空间。换成人话就是2维空间中的1维度的线,三维立体空间的二维平面。
图中总共有5个超平面,那么哪一个是最好的呢?我们认为中间的那个是最好的。因为他对两侧的间隔较大。
超平面我们可以用这个方程来表示:
空间中任意一个点x到这个超平面的垂直距离为:
这里不得不提到一下逻辑回归,对于逻辑回归来说:
就是在超平面一侧的样本,逻辑回归给出的预测类别是1,另外一侧就是0.
但是SVM觉得这样有一些过于绝对了,所以:
不仅仅要一个样本在平面的一侧,还要在平面的这一侧足够远的地方,才能算作某一类的样本。
从图中可以看到,两条虚线之外的点,才是SVM能确定是正样本还是负样本的点。
【什么是支持向量?】图中距离超平面最近的几个训练样本,并且这几个训练样本可以让上式的等号成立。这个点就是支持向量。
【什么是SVM的间隔】两个不同类别的支持向量到超平面的最小距离之和。其实也就是
到这里,我们可以隐隐约约的发现,寻找最优的超平面其实等价于寻找一个最大的间隔,或者说让间隔最大化。所以可以得到:这个的约束条件就是:让SVM给正样本的打分大于1,给负样本的打分小于-1,也就是:
简化一下这个约束条件,可以得到:
一般我们都是求取最小化问题,所以把最大化max问题取倒数,变成最小化问题:这里为了后续的计算方便,最小化
等价于最小化
,所以得到:
总之SVM的基本型就是:
现在求得了基本型。现在可以来进一步优化这个最小化问题。但是首当其冲的问题便是,如何处理这个约束条件。这里用到的方法是拉格朗日乘子法。将约束条件以
的权重加入到优化问题中,所以可以得到:
为了最小化这个问题,对w和b求偏导数,可以得到:
然后把这两个公式代入到:
可以消掉w和b,得到:
约束条件为:
从而根据这个计算出
的取值,然后得到w和b的取值。
【到底如何求解
?】
上面说的最后一步求解alpha,都是理论可以求解,但是实际中如何做到呢?其实这里如何求解
要用到另外一个条件。
就是上述过程要满足一个叫做KKT的条件(KKT具体是什么有点复杂,就不多说了):
等于0,要么
.如果alpha=0,那么意味着这个样本不是支持向量,不应该对SVM超平面起到任何影响,所以是不可能的。所以只有
。
加上了这个条件,我们可以求解出来
的具体数值,然后求解w和b的数值。
假设有3个支持向量,那么就会有三个
,然后根据
可以列出3个关于
的三元一次方程组,然后得到唯一解。
喜欢的话,长按下面的二维码关注下【机器学习炼丹术】,成为炫酷的炼丹师吧!
目前在更:每天一两个AI面试干货知识点。