【转载】干货|SVM（一）·最全面的感知机总结——太棒了！无论如何都要down下来系列

SVM(一) 感知机

感知机是个相当简单的模型，但它既可以发展成支持向量机（通过简单地修改一下损失函数）、又可以发展成神经网络（通过简单地堆叠），所以它也拥有一定的地位。

为方便，我们统一讨论二分类问题，并将两个类别的样本分别称为正、负样本

1感知机能做什么

感知机能（且一定能）将线性可分的数据集分开。

什么叫线性可分？在二维平面上、线性可分意味着能用一条线将正负样本分开，在三维空间中、线性可分意味着能用一个平面将正负样本分开。

可以用两张图来直观感受一下线性可分（上图）和线性不可分（下图）的概念：

那么一个感知机将会如何分开线性可分的数据集呢？

下面这两张动图或许能够给观众老爷们一些直观感受：

看上去挺捉急的，不过我们可以放心的是：只要数据集线性可分，那么感知机就一定能“荡”到一个能分开数据集的地方（文末会附上证明）

那么反过来，如果数据集线性不可分，那么感知机将如何表现？

相信聪明的观众老爷们已经猜到了：它将会一直“荡来荡去”（最后停了是因为到了迭代上限）（然后貌似动图太大导致有残影……不过效果也不差所以就将就着看一下吧 ( σ'ω')σ）：

2 如何搭建感知机模型

为了搭建感知机模型，我们需要知道高维数据的线性可分是指什么。

为此我们需要定义“超平面”的概念：        

   

其中、都是n维向量，则是中的超平面。对于二维平面来说

，上式就可以化为：

此即直线方程。有了中超平面的定义后，线性可分的概念也就清晰了：对于一个数据集（为输入，为标签），如果存在一个超平面，能够将中正负样本（对于某个样本，若则称其为正样本，若则称其为负样本，且标签只能取正负 1 这两个值）分开，那么就称是线性可分的。

否则，就称是线性不可分的。

对于感知机模型来说，以上的这些信息就足够了。

事实上，感知机模型只有和这两个参数，我们要做的就是根据样本的信息来逐步更新和、从而使得对应的超平面能够分开。

3  如何训练感知机模型

上一节已经说过，感知机模型只有和这两个参数，其中是一个维向量（）、则是一个标量（）。

为了保证收敛性，我们需要将初始化为零向量、将初始化为 0：

上面这个 fit 函数中有个 lr 和 epoch，它们分别代表了梯度下降法中的学习速率和迭代上限（p.s. 由后文的推导我们可以证明，对感知机模型来说、其实学习速率不会影响收敛性【但可能会影响收敛速度】）

梯度下降法我们都比较熟悉了。简单说，梯度下降法包含如下两步：

• 求损失函数的梯度（求导）

• 梯度是函数值增长最快的方向我们想要最小化损失函数我们想让函数值减少得最快将参数沿着梯度的反方向走一步

那么对于感知机模型来说，损失函数是什么呢？注意到我们感知机对应的超平面为而我们的样本为正负样本，一个自然的想法就是：

（从几何直观来说，上述定义等价为“在的上方”、“在的下方”）

注意我们前文提到过

那么一个朴素的损失函数就比较容易写出来了：

综上所述、就有：

从而易知只有错分类的点才会给贡献梯度（因为正确分类的点及其“周围”的的值为常数 0，从而梯度为 0）。

所以训练感知机时，我们只需挑选使得损失函数最大的一个样本、用它来计算梯度、然后梯度下降即可（注意如果是被正确分类的话，说明所有样本都已被正确分类，所以此时应该停止模型的训练【事实上也训练不动了……】）

由于的形式简洁，所以其求导是平凡的（注意对错分类样本而言，）：

体现在代码上即为：

至此，感知机模型就大致介绍完了，剩下的则是一些纯数学的东西，大体上不看也是没问题的。

4  相关数学理论

从数学的角度来说，线性可分性还有一个比较直观的等价定义：正负样本点集的凸包彼此不交。所谓凸包的定义如下：若集合由N个点组成：

那么的凸包即为：

比如，上文给出过的两个二维数据集的凸包将如下图所示：

左图正负样本点集的凸包不交、所以数据集线性可分，右图的橙色区域即为正负样本点集凸包的相交处、所以数据集线性不可分

该等价性的证明可以用反证法得出：

1）线性可分->凸包不交：线性可分意味着

对任意成立。如果凸包相交的话，就意味着存在某个样本、使得既是正样本输入数据的线性组合、又是负样本输入数据的线性组合：

从而

注意到

所以（注意由凸包的定义我们有且

这与式 1 矛盾

2）凸包不交->线性可分：严谨证明需要用到一些奇怪的东西，这里就只提供一个（非常）不严谨的直观说明（欢迎观众老爷们提供更好的证明，现在这个说明我看上去觉得很像是错的）（喂）

在正样本点集凸包的边界上取一个离负样本点集凸包“最近”的点并假设负样本点集凸包边界上离“最近”的点为。过画一个超平面、使得与的连线垂直。

由凸包的几何性质可知此时（除了外）正样本点集都被分到了的同一侧、且是离“最近”的点，这样只需把稍微往负样本点集那边挪一点（什么鬼！）就行了

然后是前文遗留下来的、感知机模型收敛性的证明。我们知道感知机对应的超平面为：

将其展开的话、就是

所以我们可以将其改写为

其中

如果数据集线性可分的话，就意味着存在、使得对任意、都有；注意到的 scale 不影响超平面、所以我们不妨假设。同时由于数据集中的样本是有限的，所以这又意味着、使得总有

现在我们初始化，并开始感知机模型的训练（假设现在是第k步）：

1）假设已经将所有样本正确分类，则已证毕

2）否则，取被误分类的样本，进行参数的更新：。由此易知（注意）：

且

注意是被误分类的、且只能取正负 1，所以，从而由式 2 可以推出：

从而

亦即训练步数是有上界的，这意味着收敛性。而且中不含学习速率，这说明对感知机模型来说、学习速率不会影响收敛性

最后简单介绍一个非常重要的概念：拉格朗日对偶性（Lagrange Duality）。

我们在前三小节介绍的感知机算法，其实可以称为“感知机的原始算法”；而利用拉格朗日对偶性，我们可以得到感知机算法的对偶形式。

鉴于拉格朗日对偶性的原始形式太过纯数学，所以我打算结合具体的算法来介绍、而不打算叙述其原始形式，感兴趣的观众老爷可以参见这里

在有约束的最优化问题中，为了便于求解、我们常常会利用它来将比较原始问题转化为更好解决的对偶问题。

对于特定的问题，原始算法的对偶形式也常常会有一些共性存在。比如对于感知机和后文会介绍的支持向量机来说，它们的对偶算法都会将模型的参数表示为样本点的某种线性组合、并把问题转化为求解线性组合中的各个系数

虽说感知机算法的原始形式已经非常简单，但是通过将它转化为对偶形式、我们可以比较清晰地感受到转化的过程，这有助于理解和记忆后文介绍的、较为复杂的支持向量机的对偶形式

考虑到原始算法的核心步骤为：

其中、是当前被误分类的样本点的集合；可以看见、参数的更新是完全基于样本点的。

考虑到我们要将参数表示为样本点的线性组合，一个自然的想法就是记录下在核心步骤中、各个样本点分别被利用了多少次、然后利用这个次数来将表示出来。

比如说，若设样本点共在上述核心步骤中被利用了次、那么就有（假设初始化参数时：

如果进一步设，则有：

此即感知机模型的对偶形式。

需要指出的是，在对偶形式中、样本点里面的仅以内积的形式出现；这是一个非常重要且深刻的性质，利用它和后文将进行介绍核技巧、能够将许多算法从线性算法“升级”成为非线性算法

注意到对偶形式的训练过程常常会重复用到大量的、样本点之间的内积，我们通常会提前将样本点两两之间的内积计算出来并存储在一个矩阵中；这个矩阵就是著名的 Gram 矩阵、其数学定义即为：

从而在训练过程中如果要用到相应的内积、只需从 Gram 矩阵中提取即可，这样在大多数情况下都能大大提高效率。