感知机

弄清感知机（Perceptron）是学好支持向量机和神经网络的基础，本文试图对何为感知机（即感知机模型的表示），如何训练感知机（找到最佳的感知机模型参数）这两个问题作出清楚的回答。

什么是感知机？

感知机的数学表达：

感知机由Rosenblatt在1957年提出,是一种二类线性分类模型。输入一个实数值的n维向量（特征向量），经过线性组合，如果结果大于某个数，则输出1，否则输出-1.具体地：

其中的w0,w1,....wn权重，W向量称为权向量（本文中粗体代表向量）。权重决定每个输入分类对最终输出的贡献率。为了更简洁地表示，我们加入一个x0=1，则可以将上面的式子写成符号函数（输入大于零的时候为1，其他为-1）：

。

这就是感知机的数学表达，其中W*X为内积，即向量对应元素相乘，然后求和。

感知机的几何解释：

可以把感知机看成n维实例空间的决策超平面：W*X=0.这个超平面将空间中的点分为正负两类。如果给定的杨莉集线性可分，则可以将每个样例准确地分为两类，称为分类超平面。而其中（w1,w2，...,wn）为这个超平面的法向量，w0称为截距。

布尔函数的感知机表示：

一个感知机单元可以用来表示许多（不是全部）布尔函数。例如AND函数可以设置感知机的权向量为（-0.8, 0.5，0.5），OR函数可以将权向量设为（-0.3，0.5, 0.5）。我们这里说可以设为这样一组值，言下之意就是还可以设为其他值，也就是感知机模型中的参数可以有多种情况同时满足条件。在这里，可以把AND和OR函数看做是m-of-n函数的一种。所谓的m-of-n函数，就是要使得函数输出为真（+1），那么感知机的输入至少要有m个为真。AND函数必须全部为真，即m=n。而OR函数只要其中一个为真即可，即m=1.任意的m-of-n函数都可以用感知机来表示。感知机可以表示所有的原子布尔函数，但是另外一些布尔函数则无法通过单个感知机表示，比如异或函数（当两个输入不相等时为真），异或函数用下图表示：

很明显，异或函数的数据点线性不可分（不是m-of-n函数），因此不能通过单个感知机表示（两层的感知机网络就可以）。

------------------------------------------------------------------------------------------------------------------------------------------

弄清了感知机的数学表达，紧接着的问题就是如何从给定的数据样本中，学习模型的参数，即权向量W，使得感知机的分类准确率达到最高。

感知机学习算法

感知机学习算法的目标是找到使得所有样本正确分类的分离超平面，很显然，评价是否达到这一目的的标准就是全部样本是否都被正确分类。至于寻找这一超平面的过程，不同的算法则有不同的实现。

Rosenblatt感知机算法

第一个感知机迭代算法由Rosenblatt提出。定义样本点X到超平面的函数间隔为|y（WX+b）|，其中W与上文的W相比，去掉了W0，而b就相当于w0.将损失函数定义为所有误分类的点到超平面的函数间隔之和。

我们知道，如果样本被错误分类，则y（WX+b）<0,所有绝对值加负号即可。如果所有样本被正确分类，则上面式子等于0.因此我们的目标就是找到使上式为0的W和b。这里采用随机梯度下降方法。

对上式求偏导数得到：

因此随机梯度下降在这里的具体过程描述如下：遍历所有的样本，如果遍历的当前样本错误分类，则对参数W和b作如下更新：

直到没有误分样本，体制遍历。

----------------------------------------------------------------

感知机训练法则（perceptron training rule）

寻找最佳W的一种方法是：首先给权向量的每个分类赋一个随机的权值，然后将这个感知机（此时模型参数已经有了）反复应用到所有的样本，如果样本分类错误（当前权向量的感知机的输出结果），则修改权向量，直到所有样本被正确分类。【这么做其实是基于经验风险最小化，也就是是模型最好滴拟合训练样本（模型参数可能有多种情况）。至于是如何找到拟合效果最好的模型参数，则有不同的方法和过程，后文会提到】。每一步当中如何来修改权值？根据感知机训练法则。

比如，现在将其中一个样本x应用到当前的感知机，我们对权值作如下修改：

（式1）

其中，wi表示权向量的第i个分量，t为样本的标签输出（也就是样本本该属于的类型），而o为当前感知机所作出的预测，xi为样本的第i个分量，那个不知道如何读的成为学习速率（本文用A表示0<A<=1，怪CSDN公式编辑无比困难），也称为步长。

为了有更直观的感觉，举个简单的实例：

假设：当前权向量为（0，0, 0）,迭代的样本为（1，3， 3）【加入了第零个元素】，样本的标签为+1.

现在感知机的输出为sgn（0+0+0）=-1，很遗憾，预测的结果与真正的结果不同。对于权向量的第二个分量w1，我们作出如下修改，w1=0+A（+1-（-1））*3=6A，假设A为0.1，则w2=0.6.同理更新其他分量，得到新的权向量为（0.2,0.6,0.6）。再看看这时候感知机对刚才样本的预测为sgn(0.2+1.8+1.8)=1.很好，修正过来了。

几点说明：

1）修正了一个样本是否有可能使本来分类正确的变成错误的呢？是的，这是一个不断循环往复的过程，否则的话，迭代的次数就不会超过样本容量）。比如我们来看一个例子，样本如下：

（最后一个样本应该是-1）我们看看在整个迭代过程中各个样本的分类对错的变化过程，如下图：

（备注：上图绿色的线之所以出现0的分类，是因为matlab的sign函数把0独立出来，也就是输入为0时，输出也为0，跟上面的符号函数定义略有不同）

上面的图很清楚地显示，一次迭代修正了一个样本，可能是其他的样本分类有对变错，但最终所有样本都是正确的。

2）上面提到最红的权重向量可能有多种情况。如果权重初值不同，结果可能不同。甚至样本迭代的顺序都会影响最终结果。比如，上面的样本如果从左到右迭代，经过24次更新后得到最终结果为（0.5，-0.4，-0.2）。但是如果从右到左，则经过32次跌倒之后得到（0.6，-0.3，-0.4）。

3）在对样本进行迭代的过程中，有没有可能使样本分类错得更离谱？还是一定能得到修正（靠近正确的类别）？

》如果正确分类，也就是t=o，则不需要更新。

》如果t=1，而o=-1，也就是本来样本应该属于正类，但是感知机预测成负类，那么为了更靠近正类，也就是要让W*X的值变大。

可以看到，修正之后W*X增大了，也就是更靠近正确的分类1了。

》如果t=-1，而o=1，同理，对权值向量作更新会使得内积减小，也就是更靠近负类（正确分类）。

我们看到都在向正确的分类靠近，那么是靠近（不一定纠正过来）还是一次性就把它完全纠正过来呢？下图是其中两个样本分类对错情况和W*X的变化图：

在上图中，可以看到每次对一个样本进行迭代时，如果样本错误，都能够纠正过来，同时有可能使其他样本由对变错。那么是不是真的每次迭代都能把错误分类的样本纠正过来，需要进一步考证（研究之后补充）。

4）可以证明，如果样本集线性可分，并且使用了充分小的学习速率A，那么在有限次的迭代中，就能找到一个把所有样本正确分类的权向量。（Minskey & Papert 1969）。如果不是线性可分，则不能保证收敛，即完全正确分类。

相关的matlab代码如下（为了调试方面，代码不是很规范）

function [weight_store, num_loop] = perceptron(X,y)
%% wieght: the final weight vector
%% num_loop: number of loop
%% X:training samples 
%% y: label  s by 1

% # of samples
s = length(y);
num_loop = 0;
% learning rate
r=0.1;
X = [ones(s,1), X]';
weight = [0;0;0];
weight_store = weight';
while true
   fprintf('----------------------\n');
   error_count = 0; 
   for i = 1:s
       result = sign(sum(weight.*X(:,i)));
       if (result ~= y(i) )
           fprintf('result:%f   error!\n',result);
           error_count = error_count+ 1;
           weight = weight + (r*(y(i)-result)*X(:,i)); %update
       else
           fprintf('result:%f  right\n',result);
       end
       num_loop = num_loop +1;
       weight_store = [weight_store;weight'];
       fprintf('current weight:%f   ,%f   ,%f  \n',weight(1),weight(2),weight(3));
   end
   fprintf('error count: %f\n',error_count);
   if error_count == 0
       break;
   end
end

% all weights
all_weight = weight_store * X; % num_loop+1 by s
weight1 = sign(all_weight(:,1));
fprintf('numloop: %f\n',num_loop);
fprintf('size of weight1:  %f\n', length(weight1));
hold on
set(gca,'xtick',[0:1:num_loop ])
grid on
%plot(0:num_loop,weight1,'y');
%plot(0:num_loop,all_weight(:,1),'r');
xlabel('迭代次数')
ylabel('类别（1或者-1）')
title('各样本分类情况随着迭代次数的变化')

%weight2 = sign(all_weight(:,2));
%plot(0:num_loop,weight2');
%plot(0:num_loop,all_weight(:,2),'r*');

%weight3 = sign(all_weight(:,3));
%plot(0:num_loop,weight3','b');
%plot(0:num_loop,all_weight(:,3),'r*');

weight4 = sign(all_weight(:,4));
%fprintf('5th of sample 4: %f',all_weight(6,4))
plot(0:num_loop,weight4','g');
plot(0:num_loop,all_weight(:,4),'ro')
%legend('sample1','sample2','sample3','sample4')



end

------------------------------------------------------------------------------------------------------------------------------------------

梯度下降法：

上面的第一种算法（感知机训练法则）在样本集线性可分时，能够找到最佳的权重向量，使得所有样本均被正确分类。但是如果线性不可分，则不能收敛。（不能收敛，也无法找到一个权向量使得分类错误率最小吗？疑问）。而采用梯度下降法，能够在训练样本线性不可分的情况下，找到目标的最佳近似，即分类错误率最小。感知机训练法则使得线性可分的样本集得到完全正确的分类（完美拟合）。梯度下降法，在线性可分时能够达到一样的效果（全部正确分类），而且在线性不可分时，能够找到使分类错误率最小的最佳拟合。

我们先来看线性单元，线性单元输入输出关系如下：

对于一个给定的样本集，我们定义一个训练误差（training error），这个误差有多种定义方法，最常用的如下式：

注意上式各个部分，在给定样本的情况下，这个函数只把权重向量当做变量，合情合理。D是训练样本的集合，td表示样本d的分类。od表示感知机给出的预测值。对应每个权值向量，训练误差也确定。在权值向量为2维的情况下，E和w1，w2在三维空间中会是一个抛物面，而且抛物面只有一个全局最小值。如下图所示：

那么，如何找到这个全局的最小值误差呢？梯度下降法从最初的权向量开始，在曲面上沿着最陡峭下降的方向修改权值向量，重复这个过程直到训练误差最小。这个最快的下降方向就是梯度的反方向。对于训练误差E，它对于W的梯度计算如下：

也就是E在W每个方向上的偏导数。（至于为什么沿着梯度方向函数上升最快（因此反方向下降最快），参考高等数学教材）。因此，梯度下降方法中，权值向量的更新如下：

这里学习速率还是记为A，负号代表我们在下降最快的方向进行搜索，A决定每次更新多大程度，也称为步长。按每个分量分解则：

也就是说，在各个方向上按照上式移动，将权值向量移到下一个曲面上的点。将E带入后求得偏导数如下：

（G1）

其中，xid表示样本d的第i个分量xi。因此权重更新法则如下：

注意到这里每个权重分量的一次更新时基于所有样本的（而感知机训练法则中每次更新时基于一个样本）。因此，梯度下降法则概况如下：初始化一个权重向量，然后基于所有样本计算每个权重分量的修正量，然后更新权重向量，直到找到曲面的最低点（误差最小）。误差曲面只有一个全局最小值，因此只要步长足够小，无论数据集是否线性可分，都能够找到使误差最小的权重向量。

随机梯度下降（stochastic gradient descent）

梯度下降方法在许多场合都用到，用于搜索假设空间，如果具备

（1）假设空间包含连续参数化的假设（如线性单元中的权值）；（2）误差定义对这些假设参数可微。

都可以使用梯度下降方法来搜索假设空间。在线性单元中，由于误差曲面只有一个最小值，所以可以找到全局最小值。但在其他场合可能存在以下问题：

（1）如果误差曲面有多个局部最小值，那么不能保证找到这个全局最小值。（2）收敛时间长，即迭代次数可能很大。

随机梯度下降，也叫增量（incremental）梯度下降，可以缓解这些问题（缓解？不能完全解决？）。前面重点提到，梯度下降法中权值的更新时基于所有样本的，在随机梯度下降中，权值的更新则基于单个样本，以此来得到近似的梯度下降搜索。将更新法则修改为下式：

（式2）

也就是说，每次权值向量的更新都基于单独一个样本，上式的更新就基于单独样本xi，称为增量法则。随机梯度下降相当于为每个样本定义一个单独的误差：

总结一下，随机梯度下降遍历样本集D中的每个样本d，根据样本d的误差梯度来改变权值。每个单独样本的更新综合起来得到原来误差梯度下降的合理近似。如果是步长A足够小，可以得到任意精度的近似。比较一下梯度下降和随机梯度下降：

梯度下降与随机梯度下降：

#标准的梯度下降每次权值更新时基于所有样本，而随机梯度下降每次更新只基于一个单独的样本。

#标准梯度下降每次更新需要更多的计算，因为是基于所有样本。而且使用的步长往往比随机梯度下降大。

#如果误差曲面有多个局部最小值，随机梯度下降可能避免陷入这些局部最小值。原因在于随机梯度下降采用单个样本的误差梯度来引导搜索。

需要注意的是，虽然感知机训练法则中的（式1）和随机梯度下降中的（式2）看起来一样，但是其实不同。式1中的o=sgn（W*X）,而式2中的o为线性单元的输出，即o=W*X.

------------------------------------------------------------------------------------------------------------------------------------

重点区别

#在感知机训练法则中，我们使用阈值化（threshold）的感知机输出误差来更新权值，也就是（t-o）是经过符号函数(sgn(W*X))计算的。而在随机梯度下降中，我们是根据非阈值化（unthreshold）的线性组合输出来更新权值的，即（t-o）是线性组合(W*X)的结果。

#感知机训练法则在线性可分时能够找到理想的权值正确分类所有样本，前提是线性可分。而随机梯度下降则收敛到误差最小，无论是否线性可分。当随机梯度下降用于线性可分的样本集时，找到的权值向量不仅能够正确分类所有样本，还能使两类之间的距离最大。

-------------------------------------------------------------------------------------------------------------------------------------

线性规划

找到最佳权重向量的另一种方法是线性规划（linear programming）。线性异化常用于解线性不等式方程组。在感知机模型当中，如果样本属于正类，则对应不等式W*X>0。如果属于负类，则对应W*X<=0.如果我们有S个样本，就得到S个线性不等式，联合起来得到不等式方程组。这个不等式方程组的所有解就是符合的权值向量。但是，只有在数据集线性可分时，不等式方程组才能得到解。

有一种适合于线性不可分的方法，具体参考（Duda & Hart 1973，P.168）。无论哪种线性规划方法，都无法拓展到多层感知机网络中，因此在SVM和神经网络中无法使用。而基于增量法则的随机梯度下降则可以简单地拓展到多层网络。

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

总结

本文试图回答什么是感知机（模型表示）和如何找到对样本集最佳拟合的模型参数（学习算法）。在介绍感知机的数学表达后，介绍了用于学习模型参数的感知机训练法则。然后引出了线性单元，进而介绍了梯度下降和随机梯度下降模型学习算法，简单描述了线性规划的求解方法。

参考资料：

1）《统计学习方法》 李航

2）《机器学习》 Tom Mitchell

3） 感知机维基百科词条：http://en.wikipedia.org/wiki/Perceptron

版权所有，转载请注明原出处。欢迎讨论、指出文章错误。