从感知机到支持向量机

tammypi tammypi
2019-01-23 09:42
307
0

感知机,核心思路就是找到一个超平面将一堆数据分隔开来。如下图所示就是在二维空间的一个示例:

争取用最简单的语言来讲述清楚这个算法到底是咋回事。

如果我们把这个可以区分数据的超平面,记为:

需要注意的是,这里的W和X都是向量,而b和y是标量。如果在二维空间里,W可以是(a),而X可以是,那么其实它就是个直线公式:

a是直线的斜率,而b则是直线的截距。在多维空间里(比如n维),只是在多维空间里,y由直线变成了超平面,W由斜率变成了法向量,而b则依旧是截距。我们这里讨论的是二分类问题,所以y的值要么为1,要么为-1。如果是正确分类的情况下,如果Xi属于正类,那么必定对于实际值yi=1时,WXi+b>0;如果Xi属于负类,那么必定对于实际值yi=-1时,WXi+b<0

与之相对应的,如果分类错误了,那么对于实际值yi=1时,WXi+b<0;而在实际值yi=-1时,WXi+b>0

那么每个误分类点到超平面的距离为:(关键:﹣号使得整个公式的值恒为正,这也正符合距离的特征)。

那么一个最优秀的感知机模型,就是使得所有误分类点到这个超平面的总距离之和最小,即:

关键:为了简化公式,我们去掉了||W||)。

知道了好模型的特征之后,我们如何找到这样一个模型呢?首先,初始化一个随机的W0和b0,然后再将训练数据中的一个代入公式,如果属于误分类,就调整W和b的值,直至模型可以对于所有训练数据正确分类(或者达到最大迭代次数为止)。

如何调整W和b呢?

新W=旧W+W的梯度

新b=旧b+b的梯度

那么这个梯度又是啥意思呢?按照学术上的解释,就是方向表示某一函数在该点处的方向导数沿着该方向取得最大值。说人话的意思,就是对于它求偏导,W的梯度就是W的偏导,b的梯度就是b的偏导。

所以:

新W=旧W+W的偏导=旧W+n*yi*Xi

新b=旧b+b的偏导=旧b+n*yi

n是学习率,可以设一个较小的值,n的取值介于0和1之间。

以上,就非常通俗易懂的讲解清楚感知机了。找超平面,让我们非常容易想起支持向量机,那么支持向量机与感知机到底有啥区别呢?其实支持向量机同感知机一样,都是找超平面,只是支持向量机是在最优超平面,即这个超平面不仅可以将数据点分成两部分,而且还与两边的点的距离最大。

即对于如上图所示的数据,感知机模型可能会是找到的a、c以及a,c之间的无数个超平面;而支持向量机模型则是找到的b这个超平面。

依旧可以用:来表示点到超平面的距离,只是期望每一个正确分类的点到超平面的距离都大于一个间隔r:

如果我们把W和b都同时放大N倍,其实可以发现超平面是没有变的(因为如果可以正确分类,就算把W和b都放大N倍,Xi代入应该为正类时还是>0,Xi代入时应该为负类还是<0)。但是,把W和b都放大N倍时,函数间隔却放大了N倍。为了避免这个问题,我们可以将函数间隔除以W的L2范数。

即变为:这样,就不会受到W和b比例成倍增加的影响了。

我们将问题定义为:

即让每个正确分类的点都与超平面的距离大于r这个间隔,且最大化r这个间隔。(请注意,最大化正确分类点的这个间隔,同时也是最小化误分类点的间隔

由于函数间隔不再会有影响(如果r提升n倍,势必意味着W和b也会提升n倍,最后就会被约掉),所以可以将r定为1。公式就变形为:

而我们知道,要让足够大,势必要让||W||足够小,所以max (1/||W||)是等价的。所以公式进一步变形为:

这样就演变成了一个凸二次规划问题。此时已经完全等价于数学领域的凸二次规划求解问题,可以使用拉格朗日对偶对于该问题的对偶问题进行求解,从而拿到原始问题的解。

注:其实我个人觉得以上的所有推导和变形都只是可以自圆其说而已,毫不严谨。这也是机器学习的很多理论并不被纯数学研究者看得起的一个很大原因。

 

发表评论

验证码: