史上最详尽的感知机教程:从原理到实践
AI 研习社按:本文原作者射命丸咲,原载于其知乎专栏Python与机器学习,雷锋网 AI 研习社已获授权。
(这里是本章会用到的 Jupyter Notebook 地址)
感知机是个相当简单的模型,但它既可以发展成支持向量机(通过简单地修改一下损失函数)、又可以发展成神经网络(通过简单地堆叠),所以它也拥有一定的地位
为方便,我们统一讨论二分类问题,并将两个类别的样本分别称为正、负样本
感知机能做什么?
感知机能(且一定能)将线性可分的数据集分开。什么叫线性可分?在二维平面上、线性可分意味着能用一条线将正负样本分开,在三维空间中、线性可分意味着能用一个平面将正负样本分开。可以用两张图来直观感受一下线性可分(上图)和线性不可分(下图)的概念:
那么一个感知机将会如何分开线性可分的数据集呢?下面这两张动图或许能够给观众老爷们一些直观感受:
看上去挺捉急的,不过我们可以放心的是:只要数据集线性可分,那么感知机就一定能 “荡” 到一个能分开数据集的地方(文末会附上证明)
那么反过来,如果数据集线性不可分,那么感知机将如何表现?相信聪明的观众老爷们已经猜到了:它将会一直 “荡来荡去”(最后停了是因为到了迭代上限)(然后貌似动图太大导致有残影…… 不过效果也不差所以就将就着看一下吧 ( σ'ω')σ):
如何搭建感知机模型?
为了搭建感知机模型,我们需要知道高维数据的线性可分是指什么。为此我们需要定义 “超平面” 的概念:
其中 w、x 都是 n 维向量,Π 则是 Rn 中的超平面。对于二维平面来说 n=2,上式就可以化为:
此即直线方程。有了 Rn 中超平面的定义后,线性可分的概念也就清晰了:对于一个数据集
对于感知机模型来说,以上的这些信息就足够了。事实上,感知机模型只有 w 和 b 这两个参数,我们要做的就是根据样本的信息来逐步更新 w 和 b、从而使得对应的超平面 Π 能够分开 D。
如何训练感知机模型?
上一节已经说过,感知机模型只有 w 和 b 这两个参数,其中 w 是一个 n 维向量(
上面这个 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)最大的一个样本(xi,yi)、用它来计算梯度、然后梯度下降即可(注意如果(xi,yi)是被正确分类的话,说明所有样本都已被正确分类,所以此时应该停止模型的训练【事实上也训练不动了……】)
由于 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至此,感知机模型就大致介绍完了,剩下的则是一些纯数学的东西,大体上不看也是没问题的(趴。
相关数学理论
从数学的角度来说,线性可分性还有一个比较直观的等价定义:正负样本点集的凸包彼此不交。所谓凸包的定义如下:若集合
那么 S 的凸包 conv(S) 即为:
比如,上文给出过的两个二维数据集的凸包将如下图所示:
左图正负样本点集的凸包不交、所以数据集线性可分,右图的橙色区域即为正负样本点集凸包的相交处、所以数据集线性不可分。
该等价性的证明可以用反证法得出:
1)线性可分 → 凸包不交:线性可分意味着存在 w* 和 b*,使得
从而
(式 1)
注意到:
yi=1 时
, yi=-1 时,
所以(注意由凸包的定义我们有
这与式 1 矛盾。
2)凸包不交 → 线性可分:严谨证明需要用到一些奇怪的东西,这里就只提供一个(非常)不严谨的直观说明(欢迎观众老爷们提供更好的证明,现在这个说明我看上去觉得很像是错的)(喂):在正样本点集凸包的边界上取一个离负样本点集凸包 “最近” 的点x*(1)并假设负样本点集凸包边界上离x*(1)“最近” 的点为x*(2)。过x*(1)画一个超平面
然后是前文遗留下来的、感知机模型收敛性的证明。我们知道感知机对应的超平面为:
将其展开的话、就是
所以我们可以将其改写为
其中
如果数据集线性可分的话,就意味着存在
现在我们初始化
1)假设
2)否则,取被
且
(式 2)
注意
从而
亦即训练步数k是有上界的,这意味着收敛性。而且
最后简单介绍一个非常重要的概念:拉格朗日对偶性(Lagrange Duality)。我们在前三小节介绍的感知机算法,其实可以称为 “感知机的原始算法”;而利用拉格朗日对偶性,我们可以得到感知机算法的对偶形式。鉴于拉格朗日对偶性的原始形式太过纯数学,所以我打算结合具体的算法来介绍、而不打算叙述其原始形式,感兴趣的观众老爷可以参见这里。
在有约束的最优化问题中,为了便于求解、我们常常会利用它来将比较原始问题转化为更好解决的对偶问题。对于特定的问题,原始算法的对偶形式也常常会有一些共性存在。比如对于感知机和后文会介绍的支持向量机来说,它们的对偶算法都会将模型的参数表示为样本点的某种线性组合、并把问题转化为求解线性组合中的各个系数。
虽说感知机算法的原始形式已经非常简单,但是通过将它转化为对偶形式、我们可以比较清晰地感受到转化的过程,这有助于理解和记忆后文介绍的、较为复杂的支持向量机的对偶形式。
考虑到原始算法的核心步骤为:
其中
如果进一步设
此即感知机模型的对偶形式。需要指出的是,在对偶形式中、样本点里面的x仅以内积的形式(
注意到对偶形式的训练过程常常会重复用到大量的、样本点之间的内积,我们通常会提前将样本点两两之间的内积计算出来并存储在一个矩阵中;这个矩阵就是著名的 Gram 矩阵、其数学定义即为:
从而在训练过程中如果要用到相应的内积、只需从 Gram 矩阵中提取即可,这样在大多数情况下都能大大提高效率。
延伸阅读:无监督聚类问题中,如何决定簇的最优数量?
关注 AI 研习社后,回复【1】获取
【千G神经网络/AI/大数据、教程、论文!】
百度云盘地址!
开发者专场 | 英伟达深度学习学院现场授课
英伟达 DLI 高级工程师现场指导,理论结合实践,一举入门深度学习!
课程链接:mooc.ai