感知器算法

基本概念

感知器算法是神经网络的前身, 也是深度学习中最基础最核心也是最底层的思想支撑, 所以我们如果要学习深度学习, 首先要了解感知器算法
现在我们要介绍的是神经元的概念, 神经网络最开始是生物学的概念, 输入一个生物电信号, 然后从突触那里输出, 我们如果要模拟人的思考方式, 我们很容易想到的是模拟神经元之间传递信息的方式来构建模型

根据这个概念, 在1943年建立了单个神经元的数学模型(MP模型)

然后在1957年, 科学家从纯数学的角度来描述问题:
给定一些输入输出对 ，其中 ,求一个函数，使：
设 , 从一堆(X, y)中学习参数,使函数能正确分类

注: sign(x)叫做符号函数，在数学和计算机运算中，其功能是取某个数的符号（正或负）：

感知器算法

简单来说, 就是输入 能够从一些输入输出对 中通过学习算法, 获得权重 和 , 从而获得和人一样的对物品的分类能力, 这个学习算法就是感知器算法
具体步骤:
①随机选择 和
②取一个训练样本
(1)若 且
则
(2)若 且
则
③再取另一个 回到②
④终止条件: 直到所有的输入输出对都不满足②中条件之一, 退出循环

可能上面的步骤看着不是很直观, 我们举一个例子:
若 且 目前的 和 对 x 不能正确分类
则用以下的方式调整:

变形后得到下面的式子为调整 和 b

实际上就是不断调整 使它能够正确分类, 我们这个模型就算是完成了
注: 上面的那个两条竖线的符号是矩阵的F范数, 这个范数表达的意思就是矩阵各个位置做平方和然后开根号:

所表达的意义就是对向量长度的推广, 可以理解为是矩阵的长度

定义问题

以上为最通俗的解释, 如果我们要对感知器进行重新证明, 需要重新对这个式子进行数学定义:
为了证明和描述的简便, 定义一个增广向量 , 在向量x的第二维加上一个1, 这样设的好处是, 可以将 转化成两个矩阵相乘, 使计算变得简便:
①若y=+1, 则
②若y=-1, 则 下面会介绍为啥这个向量里会这样设
定义增广的 如下: …打不出来大号的omega, 那就用W代替吧
此时的输入如果是单个样本就变成了 下面的参数 W, X都是矩阵
所以现在我们要建立感知机的目的就是要找到一个 使下面的式子成立:

目的是要找W, 使得 无论使正样本还是负样本都满足这个式子:

所以这里可以看出定义负样本的时候设成-x和-1会让整个式子也满足大于等于0的条件, 这样定义会让证明变得简单, 因为只要让式子满足一个条件即可, 而不用分大于0小于0两种情况讨论了

算法步骤

现在我们重新写一下定义后得感知器算法的步骤:
输入
①随机取 W
②挑一个, 若 , 则
③回到②直到所有的X都不成立时退出

证明

然后我们定义这个问题, 然后来证明这个问题:
感知器算法收敛定理:
输入 , 如果线性可分, 即存在W, 使

opt: optimize,这里面表示一个比较优的W参数,可以将整个(超)平面较好地分开
则利用上述感知器算法, 经过有限步后, 得到一个使

大家可以观察一下上述两个式子的差别, 实际上和有极小的可能是同一个值, 为理想的情况, 而我们得到的这个一直在逼近这个

现在我们开始正式证明这个定理:
不失一般性, 设 , 因为Wopt与aWopt是同一平面(a>0), 只有系数的差别, 所以我们为了简化这样定义
假设第k步的W是 且有一个 使得

也就是说第k步没有被正确分类
根据感知器算法:

同时取模,也就是取矩阵的范数, 然后再平方

取模之后这里直接按照平方和公式展开了, 把上面的结果抄下来

然后我们可以看到上面的式子中第三项与我们最开始的假设的(1)是一样的,所以这一项一定小于0
第四项中由感知器收敛定理里面可知Wopt和向量X的内积大于0, 后两项的和一定小于0, 所以此时我们可以看出a取足够大, 后三项的和小于0
所以, 若 的话, 一定可以取一个很大的a, 使

%7D-aW%7Bopt%7D%20%5Cright%5C%7C%5E%7B2%7D%20%3C%20%5Cleft%5C%7C%20W%7B(k)%7D-aW%7Bopt%7D%20%5Cright%5C%7C%5E%7B2%7D%0A#card=math&code=%5Cleft%5C%7C%20W%7B%28k%2B1%29%7D-aW%7Bopt%7D%20%5Cright%5C%7C%5E%7B2%7D%20%3C%20%5Cleft%5C%7C%20W%7B%28k%29%7D-aW_%7Bopt%7D%20%5Cright%5C%7C%5E%7B2%7D%0A&id=MBeVe)

由上面的式子我们可以看出来, 比 更收敛于 的, 但是我们并不知道它收敛的节奏有多快, 所以我们需要定量取一个a, 来计算它收敛的快慢, 所以我们有如下的定义:

然后我们设 , 所以我们至多经过步有限步骤, 将变成0, W将会收敛至aWopt

所以得证,感知机算法是可以收敛的