人工神经网络—感知器算法
感知器算法1.回顾2.感知器算法2.1感知器算法的实现步骤2.2算法能停得下来吗？2.3基于增广向量的感知器算法2.4感知器算法收敛定理3.感知器算法收敛的MATLAB程序演示参考资料在这一讲中，我们将重点介绍美国科学家FrankRosenblatt(1928-1971)如何对神经元的MP模型进行改造，用于解决二分类的问题。
图1FrankRosenblatt(1928-1971)1.回顾回顾上一讲的内容，神经元的MP模型：
图2神经元生理结构示意图图3神经元的数学模型示意图它的输出
2.感知器算法1957年，FrankRosenblatt从纯数学的度重新考察这一模型，指出能够从一些输入输出对(X,y)中通过机器学习算法自动获得权重W和偏置b，以此，他提出感知器算法(PerceptronAlgorithm)。
2.1感知器算法的实现步骤这里我们仍然假设输入的样本表示为给定一些输入输出对(XiX_iXi,yiy_iyi)，iii=1~N，这是一个二分类问题，其中，XiX_iXi是训练数据；yi=±1y_i=±1yi=±1，分别代表相应的类别。
我们的任务是要找一个向量W和一个常数b，使得对i=1⋅⋅⋅Ni=1···Ni=1⋅⋅⋅N，有（1）yi=+1y_i=+1yi=+1，则WTXi+b>0W^TX_i+b>0WTXi+b>0（2）yi=−1y_i=-1yi=−1，则WTXi+b0WTX+b>0且y=−1y=-1y=−1，则： w=W−X,b=b−1w=W-X,b=b-1w=W−X,b=b−1 (ii)若WTX+b0（2）yi=−1y_i=-1yi=−1，则WTXi+b0
2.3基于增广向量的感知器算法最初是随机的寻找一个W，接下来如果对于i=1⋅⋅⋅Ni=1···Ni=1⋅⋅⋅N的某一个iii，若WTx⃗i≤0W^Tvecx_i≤0WTxi≤0，那么w=w+x⃗iw=w+vecx_iw=w+xi，以此循环直到对于所有的i=1⋅⋅⋅Ni=1···Ni=1⋅⋅⋅N，WTx⃗i>0W^Tvecx_i>0WTxi>0为止。
可以证明基于增广向量的感知器算法和原来的感知器算法也是完全等价的。下面利用增广向量的感知器算法来证明感知器算法收敛定理。
2.4感知器算法收敛定理对于NNN个增广向量x⃗1,x⃗2,⋅⋅⋅,x⃗Nvecx_1,vecx_2,···,vecx_Nx1,x2,⋅⋅⋅,xN，如果存在一个权重向量woptw_{opt}wopt，使得对于每一个i=1⋅⋅⋅Ni=1···Ni=1⋅⋅⋅N，有woptTx⃗i>0w_{opt}^Tvecx_i>0woptTxi>0运用上述感知器算法，在有限步内找到一个www，使得对所有的i=1⋅⋅⋅Ni=1···Ni=1⋅⋅⋅N，有wTx⃗i>0w^Tvecx_i>0wTxi>0。
需要注意的是这个定理的一个条件，即存在一个权重向量woptw_{opt}wopt使得对于每一个x⃗ivecx_ixi的增广向量有wopttx⃗i>0w_{opt}^tvecx_i>0wopttxi>0，这个条件与训练数据集线性可分是完全等价的。另外需要注意，当训练数据集线性可分的情况下，最终在有限步内找到的www不一定是woptw_{opt}wopt，回顾线性可分的定义，如果存在一个超平面分开两类，则一定存在无数个平面分开两类，而www与woptw_{opt}wopt是这无数多个超平面中的两个。
感知器收敛定理证明如下：
首先我们假设∣∣wopt∣∣=1||w_{opt}||=1∣∣wopt∣∣=1（向量W⃗vecWW和aW⃗avecWaW代表的是同一个平面，因此我们可以用一个aaa去加权woptw_{opt}wopt，使∣∣wopt∣∣=1||w_{opt}||=1∣∣wopt∣∣=1）
定义w(k)w(k)w(k)为第kkk次改变后的权重向量值，那么会有以下两种情况：
情况1： 如果w(k)Tx⃗i>0{w(k)}^Tvecx_i>0w(k)Txi>0对所有i=1⋅⋅⋅Ni=1···Ni=1⋅⋅⋅N，那么所有点已经达到平衡，感知器算法收敛。
情况2： 如果存在某个iii，使得w(k)Tx⃗i≤0{w(k)}^Tvecx_i≤0w(k)Txi≤0，那么根据感知器算法w(k+1)=w(k)+x⃗iw(k+1)=w(k)+vecx_iw(k+1)=w(k)+xi
将这个式子两边同时减去awoptaw_{opt}awopt，得
w(k+1)−awopt=w(k)−awopt+x⃗iw(k+1)-aw_{opt}=w(k)-aw_{opt}+vecx_iw(k+1)−awopt=w(k)−awopt+xi
注：awoptaw_{opt}awopt与woptw_{opt}wopt代表的是同一个超平面。
取模并展开∣∣w(k+1)−awopt∣∣2=∣∣w(k)−awopt+x⃗i∣∣2=∣∣w(k)−awopt∣∣2+∣∣x⃗i∣∣2+2w(k)Tx⃗i−2awoptTx⃗i||w(k+1)-aw_{opt}||^2=||w(k)-aw_{opt}+vecx_i||^2=||w(k)-aw_{opt}||^2+||vecx_i||^2+2w(k)^Tvecx_i-2aw_{opt}^Tvecx_i∣∣w(k+1)−awopt∣∣2=∣∣w(k)−awopt+xi∣∣2=∣∣w(k)−awopt∣∣2+∣∣xi∣∣2+2w(k)Txi−2awoptTxi因为w(k)Tx⃗i≤0{w(k)}^Tvecx_i≤0w(k)Txi≤0，因此有：
∣∣w(k+1)−awopt∣∣2≤∣∣w(k)−awopt∣∣2+∣∣x⃗i∣∣2−2awoptTx⃗i||w(k+1)-aw_{opt}||^2≤||w(k)-aw_{opt}||^2+||vecx_i||^2-2aw_{opt}^Tvecx_i∣∣w(k+1)−awopt∣∣2≤∣∣w(k)−awopt∣∣2+∣∣xi∣∣2−2awoptTxi
又由于：对任意的i=1⋅⋅⋅Ni=1···Ni=1⋅⋅⋅N，woptT>⃗0w_{opt}^Tvec>0woptT>0，而∣∣x⃗i∣∣2||vecx_i||^2∣∣xi∣∣2是一个有界的值，那么我们一定可以取一个足够大的aaa，使得∣∣x⃗i∣∣2−2awoptTx⃗i