决策边界

机器学习中监督学习的任务就是如何找出决策边界。

在训练集中，有正负样本，任何监督学习算法就是为了找出区分正负样本的决策边界。如下图，决策边界是平行于坐标轴y，是决策树学出来的决策边界。通过新的点在决策边界的不同区域，将它预测为正或负类。

不同的算法，就是为了确定不同的决策边界长什么样。

再比如神经网络（非线性模型）的决策边界：

所有监督学习算法都是为了确定一个边界。

SVM核心思想

KeyIdea1

第一个keyidea跟确定决策边界相关，如下图

有1、2、3，三条决策边界，哪一条决策边界会好点呢？

我们先看1，由于1决策边界过于靠近负样本，一旦出现一点扰动（噪音）就很容易导致模型将负样本预测为正样本，即泛化性能不强。

再看2，对比3，2的抗扰动能力有所不足。

所以，综上，3作为决策边界更为恰当。

SVM的目标就是找到区别正负样本的边界，使得正负样本到达这条边界的范围最大（模型泛化能力最好）。

那么我们如何以数学形式，计算这出这条最宽的路呢？

上图中橙色的线line是我们想要的那条线，假设这条线的一个法向量为：

已知，直线上任意点x都垂直于法线，有：

假设新来一样本u，将样本u的向量投影到法向量w所在的方向，看看u在线的左边还是右边，则决策公式：

也可以理解为：

w*u即向量u在w方向上的投影距离。

c可以视为原点到决策边界的距离，如果小于c，则为负样本，大于c则为正样本。

上面的w和b其实就是机器学习算法要学习得出的参数。根据输入的数据坐标，学出来w和b时，只需要用新点与向量w做点乘（投影距离，定义），再判断距离与c的大小，就可确定数据是正样本还是负样本。

至此，就确定了我们优化的目标——最大边界范围。

KeyIdea2

看到下图，根据keyidea1，我们知道了我们优化的目标就是找到最宽的那条“路”，“站”在路边的样本，我们称其为支持向量。

对于这些站在街边的向量，我们对其提出要求，在训练集中，处于街边位置的样本，有：

要注意，上面的向量x都属于训练集。

对于那些不处于街边的向量，如果是正样本，则有：

数值是大于1，越大越好。

对于负样本：

数值是小于-1，越小越好。

这就是我们对“街宽”的要求，通过对街宽进行normalize，归一化后，每一半的街道宽是1。

在训练集中，不允许有点在街道的范围内，通过这条路把训练集中的数据分开。

我们也可以将keyidea2的两个式子给简化成一个式子，通过加入辅助变量：

通过以上变化，就可以将keyidea2的式子简化为一个表达式。

相对应的，对于支持向量的判断的表达式也可以被简化为：

最后，要注意，我们的keyidea2是针对训练集的要求，keyidea1是对任何的样本点。

KeyIdea3

接着，再回顾一下我们keyidea2的目标——找到最宽的那条路。

那么我们如何求“路”的宽呢？

从上图可知，正负样本的支持向量之差得出的向量在法向量w方向上的投影就是我们所要求的“路”的宽度。

即：

这里做个简单推导：

结合上式1-4与1-3可得：

可推得：

同理可得：

接着结合result1和result2有：

根据式子1-5，可以发现，这条街道得宽度和训练集本身没有任何关系，只要知道了这条街的法向量，那么这个街道的宽度就是以这条“街道”法向量的模为分母，2为分子的分式的值。

我们可以发现，要使得这条街越宽，则法向量的模要尽可能小。

即：

综上，我们要找到一个法向量w，使得其同时满足式子1-3和1-6。

KeyIdea4

拉格朗日求解求导

拉格朗日能够把带限制条件的函数极值算法给变成一个不带条件的函数极值算法。

可知上面式子1-6求极值，需要满足：

通过拉格朗日方法，将带条件的求函数极值转化为不带条件的函数极值求解问题，减少了计算的限制条件。

由此可得拉格朗日函数：

根据拉格朗日乘数法，式1-7中，未知数为w、b，对其求偏导使其等于0，有：

由上式可以发现，向量w其实是训练集中xi的线性组合，因为yi要么+1，要么-1，alpha_i大部分是0。

可以看作支持向量的线性组合。

带入计算可得：(ij符号意义相同，不必太过在意)

现在的目的就是，找到一些alpha_i的值，使得L最大。

即式子里的alpha不为0，即取决于xi和xj的点乘。

即训练集中，不需要告诉x是什么，只需要告诉所有训练集中两两x点乘的结果。（通向核方法的关键发现）

KeyIdea5

由keyidea1有：

结合keyidea4中：

可得：

在上式中，大部分的alphai都为0，只有少部分的alphai不为0，这些不为0的alpha_i对应的xi就是支持向量。

核方法推导

上面的决策边界都是线性的，但是大部分的分类问题都是非线性的，如下图：

我们很难找到一条直线，将正负样本分开。这个时候，如果有一个变换(phi)，将二维坐标系变换成另一个坐标系，如下图：

将每一个数做非线性变化，在变换后的空间中做一个线性的分类，就能够顺利的将其分开。

也就是说，我们要找到一个非线性变换，使得xi，在变换后的空间里线性可分。

但这并不是核方法。如果我们要用非线性变化的方式，我们不需要对每一个点做非线性变化。在KeyIdea4中，我们发现要求函数极值，我们只需要对训练的样本向量两两求点乘，我们只需要将两两之间的变换之后的点乘，不需要告诉这个变换是什么。

变换之后的点乘，仍然是xi,xj的函数，即：

即只需要定义出，它在某一个空间中，进行了某种变换后，在这个空间里的两两之间点乘的结果，这个函数就叫kernel（核函数）。

举个例子，假设非线性变化后的点乘结果：

有了核函数后，在所有的预测过程中，我们只需要将两两点乘换为k（核函数）的值即可。

为什么使用kernel方法会比找变换的函数方法更高效呢?

假设我们用的是RBF核函数，非线性变换会映射到无穷维高的，这个是无法描述的，但是我们可以求在这个无穷维空间里两个向量点的点乘，所以核方法更为优秀。

关键就是让优化目标跟决策函数具备一种非线性变换的能力。

如何求alpha

coordinateascent

这里只简单的讲个大概，大家能理解就理解，不理解也没关系，因为前面已经讲完了重点——SVM的核心思想了。

coordinateascent是smo算法的一种基础思想。

在上式中，只有alpha是变量，我们将式子抽象为求n个变量aplha的最大点：

多个变量的函数求极值比较难做，但是单个变量求极值就比较简单。那么，我们如何用单个变量求极值的方法来做多个变量求极值呢？

用上面的方法，依次拿一个alpha当变量，求式子1-8的alpha值仍然无法求出alpha的值，还需要对上述方法进行一定的改进，需要一次拿两个变量来求。

之前keyidea4中有涉及到，单单一个alpha是可以被其他alpha线性表达的，所以需要有两个alpha变量。

好了，今天分享的内容就到这里，希望对大家有所

转载请注明:http://www.aideyishus.com/lkgx/3792.html