感知机：从原理到训练

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

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

感知机能做什么？

感知机能（且一定能）将线性可分的数据集分开。什么叫线性可分？在二维平面上、线性可分意味着能用一条线将正负样本分开，在三维空间中、线性可分意味着能用一个平面将正负样本分开。可以用两张图来直观感受一下线性可分（上图）和线性不可分（下图）的概念：

那么一个感知机将会如何分开线性可分的数据集呢？下面这两张动图或许能够给观众老爷们一些直观感受：

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

那么反过来，如果数据集线性不可分，那么感知机将如何表现？相信聪明的观众老爷们已经猜到了：它将会一直 “荡来荡去”（最后停了是因为到了迭代上限）（然后貌似动图太大导致有残影…… 不过效果也不差所以就将就着看一下吧 ( σ'ω')σ）：

如何搭建感知机模型？

为了搭建感知机模型，我们需要知道高维数据的线性可分是指什么。为此我们需要定义 “超平面” 的概念：

其中 w、x 都是 n 维向量，Π 则是 Rⁿ中的超平面。对于二维平面来说 n=2，上式就可以化为：

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

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

如何训练感知机模型？

上一节已经说过，感知机模型只有 w 和 b 这两个参数，其中 w 是一个 n 维向量（）、则是一个标量（）。为了保证收敛性，我们需要将 w 初始化为零向量、将 b 初始化为 0：

class Perceptron:
    def __init__(self):
        self._w = self._b = None
    def fit(self, x, y, lr=0.01, epoch=1000):
        # 将输入的 x、y 转为 numpy 数组
        x, y = np.asarray(x, np.float32), np.asarray(y, np.float32)
        self._w = np.zeros(x.shape[1])
        self._b = 0

上面这个 fit 函数中有个 lr 和 epoch，它们分别代表了梯度下降法中的学习速率和迭代上限
（p.s. 由后文的推导我们可以证明，对感知机模型来说、其实学习速率设为多少都无关紧要）

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

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

（这也是为何梯度下降法有时被称为最速下降法的原因。梯度下降法被普遍应用于神经网络、卷积神经网络等各种网络中，如有兴趣、可以参见这篇文章）

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

（x，y）是正样本
（x，y）是负样本

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

注意我们前文提到过

（x，y）是正样本
（x，y）是负样本

那么一个朴素的损失函数L（x，y）就比较容易写出来了：

若，则
若，则

综上所述、就有：

损失函数可写为
（x，y）被正确分类

从而易知只有错分类的点才会给 L（x，y）贡献梯度（因为正确分类的点及其 “周围” 的 L（x，y）的值为常数 0，从而梯度为 0）。所以训练感知机时，我们只需挑选使得损失函数 L（x，y）最大的一个样本（x_i，y_i）、用它来计算梯度、然后梯度下降即可（注意如果（x_i，y_i）是被正确分类的话，说明所有样本都已被正确分类，所以此时应该停止模型的训练【事实上也训练不动了……】）

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

体现在代码上即为：

for _ in range(epoch):    # 计算 w·x+b
    y_pred = x.dot(self._w) + self._b    # 选出使得损失函数最大的样本
    idx = np.argmax(np.maximum(0, -y_pred * y))    # 若该样本被正确分类，则结束训练
    if y[idx] * y_pred[idx] > 0:  
    break   # 否则，让参数沿着负梯度方向走一步
    delta = lr * y[idx]
    self._w += delta * x[idx]
    self._b += delta

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

相关数学理论

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

那么 S 的凸包 conv(S) 即为：

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

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

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

1）线性可分 → 凸包不交：线性可分意味着存在 w* 和 b*，使得对任意成立。如果凸包相交的话，就意味着存在某个样本（x*，y*）、使得x*既是正样本输入数据的线性组合、又是负样本输入数据的线性组合：

从而

（式 1）

注意到：

yi=1 时，
yi=-1 时，

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

这与式 1 矛盾。

2）凸包不交 → 线性可分：严谨证明需要用到一些奇怪的东西，这里就只提供一个（非常）不严谨的直观说明（欢迎观众老爷们提供更好的证明，现在这个说明我看上去觉得很像是错的）（喂）：在正样本点集凸包的边界上取一个离负样本点集凸包 “最近” 的点x*⁽¹⁾并假设负样本点集凸包边界上离x*⁽¹⁾“最近” 的点为x*⁽²⁾。过x*⁽¹⁾画一个超平面、使得Π与x*⁽¹⁾、x*⁽²⁾的连线垂直。由凸包的几何性质可知此时（除了x*⁽¹⁾外）正样本点集都被分到了Π的同一侧、且x*⁽²⁾是离Π“最近” 的点，这样只需把Π稍微往负样本点集那边挪一点（什么鬼！）就行了。

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

将其展开的话、就是

所以我们可以将其改写为

其中

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

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

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

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

且

（式 2）

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

从而

亦即训练步数k是有上界的，这意味着收敛性。而且中不含学习速率η，这说明对感知机模型来说、学习速率设为多少都无关紧要。

最后简单介绍一个非常重要的概念：拉格朗日对偶性（Lagrange Duality）。我们在前三小节介绍的感知机算法，其实可以称为 “感知机的原始算法”；而利用拉格朗日对偶性，我们可以得到感知机算法的对偶形式。鉴于拉格朗日对偶性的原始形式太过纯数学，所以我打算结合具体的算法来介绍、而不打算叙述其原始形式，感兴趣的观众老爷可以参见这里。

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

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

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

其中、E是当前被误分类的样本点的集合；可以看见、参数的更新是完全基于样本点的。考虑到我们要将参数w和b表示为样本点的线性组合，一个自然的想法就是记录下在核心步骤中、各个样本点分别被利用了多少次、然后利用这个次数来将w和b表示出来。比如说，若设样本点一共在上述核心步骤中被利用了n_i次、那么就有（假设初始化参数时）：