感知机学习算法

Ⅰ 感知机算法及收敛性证明

感知机算法其实已经很熟悉了，这次看《统计学习方法》权当复习一遍，然后有一橘念个point对我来说是新的—— 感知机算法实际上采用了随机梯度下降 。这其实是一个很显然的点，但我之前看到的资料都是直接说明了超平面参数的更新方式，并从几何直观上解释了这样做是为了让超平面向误分样本点的方向旋转，而未从梯度的角度来解释，这里补充一下这个角度。

感知机（perceptron）是二分类线性分类模型，其输入空间（特征空间）是 ，输出空间是 ，前伍简由输入空间到输出空间的如下函数：

称为感知机。 和 分别是感知机的权值和偏置。

感知机的损失函数定义为 所有误分类点到超平面的距离慧裤之和 ，即：

其中 表示误分类点的集合，若 固定，则损失函数梯度为：

采用随机梯度下降法，每次随机选取一个误分类点 ，对 进行更新：

其中 称为学习率。

感知机算法流程如下：

（1）选取初值 。
（2）在训练集中选取数据 。
（3）如果 ,则更新参数：

（4）转至（2）直至训练集中无误分点。

所谓感知机算法的收敛性，就是说只要给定而分类问题是线性可分的，那么按上述感知机算法进行操作，在有限次迭代后一定可以找到一个可将样本完全分类正确的超平面。

首先，为了方便推导，我们将偏置 并入权重向量 ,记作 ，同样将输入向量加以扩充，记作 ，显然， 。

既然样本是线性可分的，我们可以假设有一个满足条件 的超平面 将样本点完全正确分开，且存在 ，对所有 ，有：

令 ，则感知机算法在训练集上误分类次数 满足：

证明：

结合上述两个结论，可以得到：

从而感知机算法的收敛性得证。

Ⅱ 感知机的收敛性

感知机是最基础的机器学习模型之一，它的类别为：

该模型本质上是雹丛嫌在输入空间定义了一个分离超平面： ， 为该超平面的法向量， 为该超平面的截距。该超平面将输入空间划分为两部分，位于两侧的点（输入数据）分别属于正负两类。
给定一个线性可分的训练样本集，通过寻找合适的 和 使得训练样本集的数据被正确划分到超平面的两侧，该过程即感知机模型的训练过程。
这里有一个前提“训练样本集线性可分”，即对于训练样本集： ，其中， ，若存在某超平面 ，使得 ，则称 为线性可分数据集。

为了寻找能正确划分训练样本集的超平面，需要定义损失函数，并将损失函数极小化。如何度量损失呢？如下图所示，有A、B、C三点，表示三个样本，都在分离超平面的正侧，距离分离超平面的距离依次减小。距离越远，预测为正类的确信度越大，反之则不那么确信。

在超平面 确定的情况下， 能够相对地表示点 距离超平面的远近，而 的符号与类标记 的符号是否一致能够表示分类是否正确。所以可以用 来表示分类的正确性与确信度，这就是函数间隔（functional margin）的概念。
设 为 上被超平面 误分类的所有点的集合，则
按照机器学习约定俗成的惯例，损失函数为正，对损失函数求极小值。因此，我们将感知机的损失函数定义为 上所有被误分类的点到超平面 的函数间隔的绝对值，即：
感知机的学习策略是在假设空间中选取使上式最小的分离超平面系数 和 。

感知机的学习问题可转化为求解使损失函数最小的最优化问题，即求参数 ，使其为以下极小化问题的解。
其中，M为误分类点的集合。求解该问题可使用梯度下降算法。
损失函数 的梯度为：

如果样本集非常大，梯度下降算法每轮迭代都要计算全局梯度，这需要耗费非常大的计算资源，实际应用中通常使用随机梯度下降算法代替，即每次随机选取一个误分类点 ，对 沿梯度负方向更新。

其中 为步长，又叫做学习率。随机梯度的期望为全局梯度，因此其收敛性与梯度下降算法一致。通过不断迭代以上步骤，可以期待损失函数 不断减小，直到为0.
该算法的直观理解为：当一个实例点被误分类，调整 的值，使分离超郑肆平面向该误分类点移动，减小该误分类点与超平面的距离，直至超平面越过该点，使其被正确分类。
该算法在训练开始时需要选取一个初始分类超平面 ，经过 轮迭代后：

其中， 为第 轮迭代时随机选取的误分类点。当 时，第 轮迭代时的超平面方程为：

可以看出，学习速率 可以被约去，说明当 时，算法收敛速度与 无关。下面证明感知机训练算法收敛性，证明过程可进一步验证该结论。

证明感知机训练算法是收敛的，即证明训练过程可在有限轮迭代内完成，即迭代次数 存在一个上界。
为了便于叙述，将偏置 并入权重向量 ，记作 ，同时对输入向量 进行扩充，记作 ，显然 。

证明：
训练数据集线性可分，则存在能将数据集完全正确分开的分离超平面，对任一满足源手要求的分离超平面 ，存在 ，对所有 ：

初始时， ，随机选取某样本，若被误分类，则更新权重。令 是第 次迭代时的扩充权重向量，此次迭代随机选择的第 个误分类样本满足条件：

迭代时进行如下更新：

联合(2)(4)式，有：

联合(3)(4)式，有：

联合(5)(6)式，有：

定理得证。
从(7)式可知，迭代次数 存在上界，这说明当训练数据集线性可分时，感知机学习算法是收敛的。
进一步地，通过调整 可以改变 的取值。算法经过 次迭代结束后得到分离超平面 ，由(1)式可知， ，令 ，则可使得 ，从而得到感知机迭代次数收敛上界的精简形式：

Ⅲ 神经网络算法

20 世纪五、六⼗年代，科学家 Frank Rosenblatt其受到 Warren McCulloch 和 Walter Pitts早期的⼯作的影响，发明了感知机（Perceptrons）。

⼀个感知器接受⼏个⼆进制输⼊， ，并产⽣⼀个⼆进制输出：

如上图所示的感知机有三个输⼊： 。通常可以有更多或更少输⼊。 我们再引⼊权重： ，衡量输入对输出的重要性。感知机的输出为0 或者 1，则由分配权重后的总和 ⼩于等于或者⼤于阈值决定。和权重⼀样，阈值（threshold）是⼀个实数，⼀个神经元的参数。⽤更精确的代数形式如下：

给三个因素设置权重来作出决定：

可以把这三个因素对应地⽤⼆进制变量 来表⽰。例如，如果天⽓好，我们把

，如果不好， 。类似地，如果你的朋友陪你去， ，否则 。 也类似。

这三个对于可能对你来说，“电影好不好看”对你来说最重要，而天气显得不是那么的重要。所以你会这样分配权值： ，然后定义阈值threshold=5。

现在，你可以使⽤感知器来给这种决策建⽴数学模型。

例如：

随着权重和阈值的变化，你可以得到不同的决策模型。很明显，感知机不是⼈做出决策使⽤的全部模型。但是这个例⼦说明了⼀个感知机如何能权衡不同的依据来决策。这看上去也可以⼤致解释⼀个感知机⽹络有时确实能够做出一些不错的决定。

现在我们队上面的结构做一点变化，令b=-threshold，即把阈值移到不等号左边，变成偏置， 那么感知器的规则可以重写为:

引⼊偏置只是我们描述感知器的⼀个很⼩的变动，但是我们后⾯会看到它引导更进⼀步的符号简化。因此，我们不再⽤阈值，⽽总是使⽤偏置。

感知机是首个可以学习的人工神经网络，它的出现引起的神经网络的第一层高潮。需要指出的是，感知机只能做简单的线性分类任务，而且Minsky在1969年出版的《Perceptron》书中，证明了感知机对XOR（异或）这样的问题都无法解决。但是感知机的提出，对神经网络的发展是具有重要意义的。

通过上面的感知机的观察我们发现一个问题，每个感知机的输出只有0和1，这就意味着有时我们只是在单个感知机上稍微修改了一点点权值w或者偏置b，就可能造成最终输出完全的反转。也就是说，感知机的输出是一个阶跃函数。如下图所示，在0附近的时候，输出的变化是非常明显的，而在远离0的地方，我们可能调整好久参数也不会发生输出的变化。

这样阶跃的跳变并不是我们想要的，我们需要的是当我们队权值w或者偏置b做出微小的调整后，输出也相应的发生微小的改变。这同时也意味值我们的输出不再只是0和1，还可以输出小数。由此我们引入了S型神经元。

S型神经元使用 S 型函数，也叫Sigmoid function函数，我们用它作为激活函数。其表达式如下：

图像如下图所示：

利⽤实际的 σ 函数，我们得到⼀个，就像上⾯说明的，平滑的感知器。 σ 函数的平滑特性，正是关键因素，⽽不是其细部形式。 σ 的平滑意味着权重和偏置的微⼩变化，即 ∆w 和 ∆b，会从神经元产⽣⼀个微⼩的输出变化 ∆output。实际上，微积分告诉我们

∆output 可以很好地近似表⽰为：

上面的式子是⼀个反映权重、偏置变化和输出变化的线性函数。这⼀线性使得我们可以通过选择权重和偏置的微⼩变化来达到输出的微⼩变化。所以当 S 型神经元和感知器本质上是相同的，但S型神经元在计算处理如何变化权重和偏置来使输出变化的时候会更加容易。

有了对S型神经元的了解，我们就可以介绍神经网络的基本结构了。具体如下：

在⽹络中最左边的称为输⼊层，其中的神经元称为输⼊神经元。最右边的，即输出层包含有输出神经元，在图中，输出层只有⼀个神经元。中间层，既然这层中的神经元既不是输⼊也不是输出，则被称为隐藏层。

这就是神经网络的基本结构，随着后面的发展神经网络的层数也随之不断增加和复杂。

我们回顾一下神经网络发展的历程。神经网络的发展历史曲折荡漾，既有被人捧上天的时刻，也有摔落在街头无人问津的时段，中间经历了数次大起大落。

从单层神经网络（感知机）开始，到包含一个隐藏层的两层神经网络，再到多层的深度神经网络，一共有三次兴起过程。详见下图。

我们希望有⼀个算法，能让我们找到权重和偏置，以⾄于⽹络的输出 y(x) 能够拟合所有的 训练输⼊ x。为了量化我们如何实现这个⽬标，我们定义⼀个代价函数：

这⾥ w 表⽰所有的⽹络中权重的集合， b 是所有的偏置， n 是训练输⼊数据的个数，
a 是表⽰当输⼊为 x 时输出的向量，求和则是在总的训练输⼊ x 上进⾏的。当然，输出 a 取决于 x, w和 b，但是为了保持符号的简洁性，我没有明确地指出这种依赖关系。符号 ∥v∥ 是指向量 v 的模。我们把 C 称为⼆次代价函数；有时也称被称为均⽅误差或者 MSE。观察⼆次代价函数的形式我们可以看到 C(w, b) 是⾮负的，因为求和公式中的每⼀项都是⾮负的。此外，代价函数 C(w,b)的值相当⼩，即 C(w; b) ≈ 0，精确地说，是当对于所有的训练输⼊ x， y(x) 接近于输出 a 时。因

此如果我们的学习算法能找到合适的权重和偏置，使得 C(w; b) ≈ 0，它就能很好地⼯作。相反，当 C(w; b) 很⼤时就不怎么好了，那意味着对于⼤量地输⼊， y(x) 与输出 a 相差很⼤。因此我们的训练算法的⽬的，是最⼩化权重和偏置的代价函数 C(w; b)。换句话说，我们想要找到⼀系列能让代价尽可能⼩的权重和偏置。我们将采⽤称为梯度下降的算法来达到这个⽬的。

下面我们将代价函数简化为C(v)。它可以是任意的多元实值函数， 。
注意我们⽤ v 代替了 w 和 b 以强调它可能是任意的函数，我们现在先不局限于神经⽹络的环境。

为了使问题更加简单我们先考虑两个变量的情况，想象 C 是⼀个只有两个变量 和 的函数，我们的目的是找到 和 使得C最小。

如上图所示，我们的目的就是找到局部最小值。对于这样的一个问题，一种方法就是通过微积分的方法来解决，我们可以通过计算导数来求解C的极值点。但是对于神经网络来说，我们往往面对的是非常道的权值和偏置，也就是说v的维数不只是两维，有可能是亿万维的。对于一个高维的函数C(v)求导数几乎是不可能的。

在这种情况下，有人提出了一个有趣的算法。想象一下一个小球从山顶滚下山谷的过程， 我们的⽇常经验告诉我们这个球最终会滚到⾕底。我们先暂时忽略相关的物理定理， 对球体的⾁眼观察是为了激发我们的想象⽽不是束缚我们的思维。因此与其陷进物理学⾥凌乱的细节，不如我们就这样问⾃⼰：如果我们扮演⼀天的上帝，能够构造⾃⼰的物理定律，能够⽀配球体可以如何滚动，那么我们将会采取什么样的运动学定律来让球体能够总是滚落到⾕底呢？

为了更精确地描述这个问题，让我们思考⼀下，当我们在 和 ⽅向分别将球体移动⼀个很⼩的量，即 ∆ 和 ∆ 时，球体将会发⽣什么情况。微积分告诉我们 C 将会有如下变化：

也可以用向量表示为

现在我们的问题就转换为不断寻找一个小于0的∆C，使得C+∆C不断变小。

假设我们选取：

这⾥的 η 是个很⼩的正数（称为学习速率），于是

由于 ∥∇C∥2 ≥ 0，这保证了 ∆C ≤ 0，即，如果我们按照上述⽅程的规则去改变 v，那么 C
会⼀直减⼩，不会增加。

所以我们可以通过不断改变v来C的值不断下降，是小球滚到最低点。

总结⼀下，梯度下降算法⼯作的⽅式就是重复计算梯度 ∇C，然后沿着相反的⽅向移动，沿着⼭⾕“滚落”。我们可以想象它像这样：

为了使梯度下降能够正确地运⾏，我们需要选择合适的学习速率η，确保C不断减少，直到找到最小值。

知道了两个变量的函数 C 的梯度下降方法，我们可以很容易的把它推广到多维。我们假设 C 是⼀个有 m 个变量 的多元函数。 ∆C 将会变为：

其中， ∇C为

∆v为：

更新规则为：

在回到神经网络中，w和b的更新规则为：

前面提到神经⽹络如何使⽤梯度下降算法来学习他们⾃⾝的权重和偏置。但是，这⾥还留下了⼀个问题：我们并没有讨论如何计算代价函数的梯度。这里就需要用到一个非常重要的算法：反向传播算法（backpropagation）。

反向传播算法的启示是数学中的链式法则。

四个方程：

输出层误差方程：

当前层误差方程：

误差方程关于偏置的关系：

误差方程关于权值的关系

算法描述：

检视这个算法，你可以看到为何它被称作反向传播。我们从最后⼀层开始向后计算误差向量δ。这看起来有点奇怪，为何要从后⾯开始。但是如果你认真思考反向传播的证明，这种反向移动其实是代价函数是⽹络输出的函数的结果。为了理解代价随前⾯层的权重和偏置变化的规律，我们需要重复作⽤链式法则，反向地获得需要的表达式。

参考链接： http://neuralnetworksanddeeplearning.com/

Ⅳ 感知机（Perceptron）

在之前的文章中我们已经讲过了逻辑回归分类器，现在趁热打铁总结一下与逻辑回归非常相似的感知机模型。感知机模型是一个非常古老的分类算法，现在很少会单独使用它，但是它的原理简单有效，很值得学习和理解，从原理上来说，感知机模型是神经网络和支持向量机的基础，理解了感知机有利于理解支持向量机和神经网络的原理。

在 广义线性模型（4）逻亩旁辑回归 中我们说逻辑回归可以视为包含一个线性回归和一个值域映射两个过程，如果拿逻辑回归与感知机作比较的话，可以说感知机也同样包括这两个过程，只不过它的值域映射比逻辑回归简单很多，感知机直接将线性模型的输出映射为+1和-1，即需要预测的两个类别上，正可谓简单粗暴。所以说，感知机也是线性模型，用来处理线性可分的二分类问题，同样属于判别模型。

感知机假设数据线性可分的，希望通过学习得到一个线性的决策边界，将训练数据集正样本点和负样本点完全正确分开的分离，在决策边界一侧为正样本，另一侧为负样本，这个思路跟逻辑回归是一样的。

感知机模型可以表示为下式，其中 函数将线性模型的输出映射为预测类别：

由点到超平面的距离计算方法可知： 代表了样本点到决策边界的距离（文章没有用 的形式，抛弃了常数项的问题，其实是不准确的，若有看官，还请不要介意）；

同时我们可知， 的样本类别输出值取为1，满足 的样本类别输出值取为-1，因此正确分类的样本满足 ，而错误分类的样本满足 ， 表示了错误分类的样本到决策超平面的距离，感知机损失函数的优化目标，就是期望使错误分类的所有样本到超平面的距离之和最小（正样本+1，负样本-1这样的定义方式使得定义损失函数变得很方便），损失函数为：

式中，M为样本中所有错误分类样本点的集合。实际上，我们会把损失函数中参数的L2正则项 扔掉，认为它不会影响优化结果，即得到损失函数：

为什么可以不考虑 呢？ 搜索解空间的时候， 会一直在变化啊？我觉得这个挺难理解的，根据资料及猜测，我觉得勉强能接受的原因为：

确定了损失函数的形式，接下来就要进行损失函数的优化，还是使用梯度下降，由于损失函数中只有错误分类的样本点才参与计算，所以不需要使用普通的批量梯度下降了，我们选择使用 随机梯度下降 ， 每次迭代只使用一个错误分类的样本来对参数进行更新 。

感知机的学习算法的原始形式即直接使用梯度下降，其学习过程为：

可以发现，在原始形式中，每一轮迭代都需要判断各个样本点是不是错误分类点，既对于每个样本点 都需要计算 ，向量内积 的时间复杂度为 ，因此总的时间复杂度为 ，其中N为样本点数量，k为迭代次数（虽然每次迭代不需要全部遍历N个样本，不过表达时间复杂度时可以去掉因子保留变量，表示成 ），这个时间复杂度还是比较高的，有没有更快捷的计算方法呢？我们来看看感知机的学习算法的对偶形式。

什么叫对偶形式？这里的对偶可不是“三尺剑，六钧弓”的意思，优化理论中的对偶问题是指每一个线性规划问题（称为原始问题）有一迅余橡个与它对应的对偶线性规划问题（称为对偶问题），原始问题与对偶问题的解是对应的，得出一个问题的解，另一个问题的解也就得到了，可以简单的理解为从不同角度看待同一个问题，通过改变这个问题的形式使得我们更好求解。

根据感知机学习算法的原始形式可知，只有错误分类的样本点才会用于梯度下降计算，对于被 次误分类而更新的样本 ，它参与 迭代的次数同样为 。如果令参数 初始值为 ， 这样我们的 的表达毁汪式可以写为：

表示对全部样本 中的每个个样本点进行 次梯度下降，其中没被错误分类过的样本点 。引用知乎上一个答案对 的理解：

这样参数 的学习问题就转变成了样本错误分类次数 的学习问题，此之谓“对偶”也。这样做的好处是什么呢？原始形式的痛点在于 中的内积运算，在对偶问题中转变为：

由内积 转变为内积 ，区别是 是已知的，可以提前通过矩阵运算得到Gram矩阵保存下来重用，样本循环和迭代的时间复杂度不变， 个 维向量的内积计算提前，所以时间复杂度大概可以表示为 ，与 倒不太好比较，不过这里按矩阵运算的时间复杂度完全没有优化来计算的，实际肯定比这小得多，并且工程上矩阵运算都是高度优化过的，非常快，所以对偶形式在使用效率上是很有优势的。

对偶形式的学习过程为：

感知机算法原理很简单，但其中很多思路很棒，所以由它发展出了神经网络、支持向量机这样的更复杂、更准确的算法，搞懂了感知机模型的基本原理，接下来我们就来写一写跟它很相似的支持向量机~

主要参考

《统计学习方法》 李航
感知机的损失函数为什么可以采用函数间隔(忽略1/||w||)?
如何理解感知机学习算法的对偶形式？