人工神经网络(感知器算法)

作为文章的结束流量道思考题给大家。

第一,如果训练数据是线性不可分,那么感知器算法是否还收敛呢?请证明你的结论。

第二,如果此时感知器算法不收敛,你能否改造一下这个算法,使它在现行不扣分的情况下能够自动地终止并退出循环呢?

在这一章中,我们将重点介绍美国计算机科学家 Frank Rosenblatt

Frank Rosenblatt

如何对神经元的MP模型进行改造,用以解决二分类问题。
回顾上一节的内容,神经元的MP模型,它的输出y等于 φ i从1加到m。

在一九五七年, Frank Rosenblatt 从纯数学的角度重新考察了这一模型,指出能够从一些输入输出的对,通过机器学习的方法自动地获得权重 ω 和偏置b,并以此他提出了感知去算法Perceptron AIgorithm。这里我们仍然假设输入的训练样本表示为大的Xi yi i等于1到n,这是一个2分类问题。


其中Xi是训练数据,而Yi等于正1或负1分别代表相应的类别。我们的任务是要找出一个向量 ω 和一个常数b,

我们把某个训练数据Xi来满足上述的条件,叫做这个数据获得的平衡。否则,就没有获得平衡。可见,一个数据Xi没有获得平衡的关系也有两种情况,

可以看到,这个任务和前面支持向量机的任务是完全一致的。
我们已经学习过,当且仅当在训练数据及线性可分的情况下才能找到 ω 和B满足是所有的N个训练样本都达到平衡,感知器算法给出了另一种不同于支持向量机寻找 ω 和b的方法。其做法包含如下四个步骤。

第三步再取一个序列样本xy回到2。第四步是终止条件,直到所有输入输出端x、y都不满足2中的1和2任意一个条件之一。那么我们退出循环


我们来看一下这个算法的意思。主要我们看第二步。如果当该等于复印机时,根据前面的分析,我们希望此时我没法转至X加币是小于零到,但是现实中我们却遇到了我没达到专制朋友X加币大于0,这是一个没有达到平衡状态的情况。
因此我们需要对我们和B进行调整,以如下的调整方式,新的我们一个等于就得我们一口气X,新的B等于7.5的B。

至于为什么我们要这样做了?我们来算一下调整之后的我没法转至X加B的值,我们把上面两个式子代入下面就可以得到我们新的专制乘以X加上,并最终经过一些推导,这个式子将会等于我们把旧的专制乘以X加上B就同时减掉X末的平方加一由于X模的平方是一个大于等于0的数。

可以看出,通过更新 ω 和B后, ω 的转制乘以x加B的值比原来至少小了1。这样我们部分地改变了现实,使得X距离平衡状态至少近了一点点。同样,我们来看y等于意义的情况,我们希望此时 ω 转至X加B大于0,但现实却是 ω 转至乘以X加币小于0。

根据算法,我们按照如下的方式对 ω 和B进行调整新到 ω 等于旧 ω 的, ω 加X,新的B等于旧的B加1。我们也可以算一下调整过后的 ω 专制乘以x加币的值。同样的道理, ω 新的专制乘以x加b的新。
经过推导,它将会等于 ω 旧的专制乘以xb的旧再加上X末的平方加1所以,调整过后的 ω 专制乘以x加B的值比原来大了至少1

因此,改变 ω 和B之后,我们也是这种情况下X理平衡状态至少近了一点点。
我们可以看到感知器算法是不断输入训练数据,重复上述的调整步骤,直到最后获得的。 ω 和B队所有的训练样本达到平衡的状态。
算法停止下来,有的同事会问,算法最终能够停下来吗?有没有可能出现? ω B在某一步的变化使某个数据从不平衡状态达到了平衡状态,但同时却是另一个数据从平衡状态变成了不平衡状态呢?
如果是这样,将有可能出现循环永远无法终止的局面。rosenblatt发明感知算法时最具创意的一步是严格的,证明了只要训练数据线性可分,那么感知算法一定可以停下来。在描述这个定理的时候,我们需要做一些定义,对于某个训练数据Xi,我们定义它的增广向量y若1等于1,则x1上面划一个箭头表示xi的增广向量。

它为原来的xx再加上一个维度而这个维度的值是1。这样就形成了一个新的增长的向量。同样,若1等于负1×1的增长向量等于原来的负的新,再加上另一个维度,这个维度的值是负。以定义增向量的目的是简化我们的表达。
原本我们的任务是寻找我们和B4的i等于1到n能够满足下面两个条件有了增长向量这个定义过后,我们可以将上述任务简化表达为寻找一个向量我们,它是由我们和B中得来的,使得对于i等于1到n有我们的转至乘以x2的向量是大于零的。

同学们可以验证一下。如果真向量是这样定义的,那么这两种任务的描述是完全等价的。下面就是基于增广向量的简化版的感知去算法最初是随机的寻找一个我们一个。接下来如果对于1等于1到n的某一个I,若我们知道的转至乘以2的增长向量是小于等于0到那么我们将等于我们大家傻X的增长向量一次循环直到对于所有的i等于1到n。

我们的专制的向量都大于零为止。也可以证明基于真向量的去算法和原来的感知去算法也是完全等价的。接下来我们利用基于真向量的感知去算法来证明赶出去算法的收敛定理。

这个定理描述如下如果我们有n个向量x1x2一直到3,如果存在一个权重向量,我们把opt使得对于每一个i等于1到n有,我们把OPT转至x1的增长向量是大于零到那么运用上述赶出去算法,我们一定能够在有限不内找到一个我们使得对于所有的i等于1道森也有我们的转至乘以2的中向量是大于领导需要注意的是这个定理的一个条件,即存在一个权重向量。
ω opt使得对于每一个80的向量由 ω OPT的转制成的向量大于0这个条件因为训练数据是线性可分是完全等价的。另外需要注意,当训练数据是线性可分的情况下,最终在有限步内找到的 ω 不一定是 ω OPT
回顾线性扣分的定义。
如果存在一个超平面分开两类,则一定存在无数多个超平面分开两类。而 ω 与 ω OPT是从无数多个超平面中的两个感知器收敛定理证明如下。首先,我们假设 ω OPT的模等于零,等于为什么我们可以这样讲呢?是的,前面讲过的内容, ω 和 ω 代表的是同一个平面,因此我们一定可以用某一个A去加权。

ω OPT使得 ω OPT的模等于1。接下来我们定义我们一打开为D开一次改变后权重向量的值。那么会有以下两种情况。

情况1。如果对所有的i等于1到n都有,我们一打开都转至乘以x的向量大于0,那么所有的点都已经达到了平衡。
赶出去算法已经收敛了情况2。

如果存在某一个i时,我们可以都转至乘以x的向量小于等于0。那么根据感知去算法下一个循环下我们一个可以加1将会等于我们一打开加上新的向量。我们将上述式子两边同时减去a倍的 ω OPT。我们将会得到下面这个式子。
需要再次指出的是ab的 ω OPT与 ω OPT代表的是同一个超平面,将上面释出起毛并展开合并后会得到下面的数字,我们可以加1减掉一倍到 ω OPT末的平方,将会等于我们也可以减掉一倍的。我们OPT抹的平方加上X2的真向量的平方,再加上两倍到我们1块的专制乘以2的增长向量,再减去二A,我们把OPT的专制乘以x1的增光向量。

分析一下这个式子,由于我们可以一个专制乘以2的增长向量是小于等于0的,因此我们就用下面这个不等式,我们可以加1减掉一倍的。我们一个opt毛的平方,它将小于等于我们也可以减掉一倍的。 ω opt抹的平方加上x1真向量的平方减掉二a。
ω OPT转至中广向量又由于对任意的i等于1到n我们有。 ω OPT的专制乘以X11的增长向量是大于零到而xy的增长向量模的平方又是一个有限的值,那么我们一定可以取一个足够大的A使得x的向量的平方减掉二a。

ω opt的转至乘以的向量是小于复一道。在这个时候我们将会有我们把可以加1减掉一倍的我们OPT的平方,它小于等于我们打开减掉一倍到 ω OPT期末的平方。在线1可见我们的值每更新一次卡管理一倍的敏感OPT。其中a是一个足够大的正数,它的距离将至少减少一个单位。

假设 ω 初值为我们零,那么最多经过 ω 展平减掉一倍的。 ω OPT抹到平方。这么多次迭代, ω 一定会收敛到一百到 ω T。当然,更有可能的情况是没有经过这么多次迭代感知算法已经收敛并退出循环了。以上我们完成的赶出去算法的证明,这里我们演示感知去算法收敛的matlab程序。

此时我们可以看到这是一个二维特征空间线性可分的例子。我们只最初的我们如这幅图上的直线手势。接着我们要用感知去算法不断的更新这条直线的方程。

可以看到这条直线以一种无规律的方式不断运动,似乎看不到它收敛的时候但是感知去算法收敛定理保证了只要训练数据是线性可分,就一定能收敛。
最后经过多年的迭代后,它收敛到了这里,完全的分开了两个类别作为文章的结束流量道思考题给大家。
第一,如果训练数据是线性不可分,那么感兴趣算法是否还收敛呢?请证明你的结论。
第二,如果此时感知算法不收敛,你能否改造一下这个算法,使它在现行不扣分的情况下能够自动地终止并退出循环呢?
本讲的内容就到这里,谢谢同学们。

发表评论

邮箱地址不会被公开。 必填项已用*标注