【机器学习理论】人工神经网络之感知器算法_神经网络感知器算法

1 神经元的MP模型

首先，回顾一下上次所讲的神经元的MP模型：
$$y=\varphi (\sum _{i=1}^m{\omega }_i{x}_i+b)$$
其中，
$x_i(i=1,2,...,m)$ 表示第 $i$ 个输入变量(自变量)
$m$ 表示输入变量的个数
${\omega }_i(i=1,2,...,m)$ 表示第 $i$ 个权重，与相同下标的 $x_i$ 相对应
$b$ 表示偏置
$y$ 表示输出变量(因变量)
$\varphi$ 表示一个激活函数，它对线性加权求和的结果进行非线性变换

表示成向量形式：
设 $W=({\omega }_1,{\omega }_2,...,{\omega }_m{)}^T$，$X=(x_1,x_2,...,x_m{)}^T$
则MP模型可以表示成：
$$y=\varphi (W^{T}X+b)$$

2 感知器算法

以上只是一个模型框架，只有当我们确定了模型的参数以后，才能使用这个模型来完成分类任务，因此，我们使用学习算法来让机器学习大量数据来确定这些参数。
1957年，Frank Rosenblatt提出能从一些输入输出对，通过机器学习的方法，自动习得MP模型中的权重向量 $W$ 和偏置 $b$，这个机器学习的方法就是著名的感知器算法(Perceptron Algorithm)。

2.1 二分类问题定义

假设训练集为$\{(X_1,y_1),(X_2,y_2),...,(X_N,y_N)\}$，一共有N个样本
因此，训练样本是$(X_i,y_i)，i=1,2,...,N$
其中，
$X_i$ 表示第 $i$ 个训练样本的特征向量，包含了多个特征，也就是多个输入变量
$y_i$ 表示第 $i$ 个训练样本的标签，也就是输出变量
$N$ 表示训练样本的总数

注：

1. $X_i$ 是一个列向量，$X_i=(x_{i1},x_{i2},...,x_{im}{)}^T$，$x_{ij}$表示第 $i$ 个特征向量的第 $j$ 个分量，每个分量都是一个特征，$m$ 表示特征的数量
2. $y_i$ 是一个数，它的取值只能有两种，要么是+1，要么是-1

任务：
找出一个向量 $W$ 和一个常数 $b$，使得对于$\forall$ $i$($i=1,2,...,N$) ，都有

（1）若 $y_i=+1$，则 $W^T{X}_i+b>0$
（2）若 $y_i=-1$，则 $W^T{X}_i+b<0$

当确定了向量 $W$ 和常数 $b$ 以后，若某个训练样本 $(X_i,y_i)$ 满足上述条件，则称该训练样本$(X_i,y_i)$ 获得了平衡，否则，就称没有获得平衡。

一个训练样本 $(X_i,y_i)$ 没有获得平衡的关系有两种情况：

（1）若 $y_i=+1$，则 $W^T{X}_i+b<0$
（2）若 $y_i=-1$，则 $W^T{X}_i+b>0$
这个任务和支持向量机的任务是完全一致的，我们已经知道当且仅当在训练数据集线性可分的情况下，才能找到一组 $W$ 和 $b$，使得所有 $N$ 个训练样本 $(X_i,y_i)$都获得平衡

2.2 感知器算法的步骤

（1）随机选择 $W$ 和 $b$
（2）取一个训练样本 $(X,y)$
             （i）若 $W^{T}X+b>0$，且 $y=-1$，则：

$W(新)=W(旧)-Xb(新)=b(旧)-1$
             （ii）若 $W^{T}X+b<0$，且 $y=+1$，则：

$W(新)=W(旧)+Xb(新)=b(旧)+1$
（3）再取另外一个训练样本 $(X^{{}^{\prime }},y^{{}^{\prime }})$，回到（2）
（4）终止条件：直到所有训练样本 $(X_i,y_i)$， $i=1,2,...,N$，都不满足（2）中的（i）和（ii）之一，退出循环

2.3 对感知器算法两种情形的分析

2.3.1 对情形（i）的数学分析

分析（2）的（i）情形，即满足 $W^{T}X+b>0$，且 $y=-1$时，此时，$W(新)=W(旧)-X,b(新)=b(旧)-1$
那么$W$ 和 $b$ 修改前后的模型之间关系是什么呢？

W ( 新 ) T X + b ( 新 ) = [ W ( 旧 ) − X ] T X + b ( 旧 ) − 1 = [ W ( 旧 ) T X + b ( 旧 ) ] − ( X T X + 1 ) = [ W ( 旧 ) T X + b ( 旧 ) ] − ( ∣ ∣ X ∣ ∣ 2 + 1 ) 其中， ∣ ∣ X ∣ ∣ 2 ≥ 0 ≤ [ W ( 旧 ) T X + b ( 旧 ) ] − 1

$$\begin{align*} &W(新)^TX+b(新)\\ =[&W(旧) -X]^TX+b(旧)-1\\ =[&W(旧)^TX+b(旧)]-(X^TX+1)\\ =[&W(旧)^TX+b(旧)]-(||X||^2+1) \quad\quad 其中，||X||^2\ge0\\ \le[&W(旧)^TX+b(旧)]-1\\ \end{align*}$$ =[=[=[≤[​W(新)TX+b(新)W(旧)−X]TX+b(旧)−1W(旧)TX+b(旧)]−(XTX+1)W(旧)TX+b(旧)]−(∣∣X∣∣2+1)其中，∣∣X∣∣2≥0W(旧)TX+b(旧)]−1​

根据这个不等式，在情形（i）下，每次对 $W$ 和 $b$ 的更新都使得 $W^{T}X+b$ 的值比原来至少减小了1，若 $W^{T}X+b$ 的值减少到小于0时，当前的训练样本 $X$ 就获得了平衡；否则，还需要等待继续改变。总之，这种变化多多少少使得当前训练样本 $X$ 距离平衡状态近了一些，但可能会使得其它训练样本离平衡状态远一些或者近一些，对于其它训练样本来说是不确定的，只能保证当前训练样本 $X$ 一定能距离平衡状态近一些。

2.3.2 对情形（ii）的数学分析

分析（2）的（ii）情形，即满足 $W^{T}X+b<0$，且 $y=+1$时，此时，$W(新)=W(旧)+X,b(新)=b(旧)+1$
同理可得
W ( 新 ) T X + b ( 新 ) = [ W ( 旧 ) + X ] T X + b ( 旧 ) + 1 = [ W ( 旧 ) T X + b ( 旧 ) ] + ( X T X + 1 ) = [ W ( 旧 ) T X + b ( 旧 ) ] + ( ∣ ∣ X ∣ ∣ 2 + 1 ) 其中， ∣ ∣ X ∣ ∣ 2 ≥ 0 ≥ [ W ( 旧 ) T X + b ( 旧 ) ] + 1

$$\begin{align*} &W(新)^TX+b(新)\\ =[&W(旧) +X]^TX+b(旧)+1\\ =[&W(旧)^TX+b(旧)]+(X^TX+1)\\ =[&W(旧)^TX+b(旧)]+(||X||^2+1) \quad\quad 其中，||X||^2\ge0\\ \ge[&W(旧)^TX+b(旧)]+1\\ \end{align*}$$ =[=[=[≥[​W(新)TX+b(新)W(旧)+X]TX+b(旧)+1W(旧)TX+b(旧)]+(XTX+1)W(旧)TX+b(旧)]+(∣∣X∣∣2+1)其中，∣∣X∣∣2≥0W(旧)TX+b(旧)]+1​
因为$W^{T}X+b<0$，每次对 $W$ 和 $b$ 的更新都使得$W^{T}X+b$ 的值比原来至少增大了1，所以这使得当前训练样本 $X$ 距离平衡状态近了一些，若 $W^{T}X+b$ 的值增大到超过0的值时，当前的训练样本 $X$ 就获得了平衡。

3 基于增广向量的感知器算法

基于增广向量的感知器算法和原来的感知器算法是等价的，是对原算法的简化。

3.1 二分类问题的简化表达

虽然每次更新当前训练样本 $X$ 距离平衡状态近了一些，但有可能使得其它训练样本距离平衡状态更远一点，有人因此说，感知器算法有可能永远停不下来，但是，ROSENBLATT提出了一个定理：只要训练数据线性可分，感知器算法就一定可以停下来。
对于某个 $X_i$，我们定义它的增广向量为：
（1）若 $y_i=+1$，则${\vec{X}}_i=(X_i,1{)}^T$
（2）若 $y_i=-1$，则${\vec{X}}_i=(-X_i,-1{)}^T$
这个定义是为了简化表达
原任务：
找出一个向量 $W$ 和一个常数 $b$，使得对于$\forall$ $i$($i=1,2,...,N$) ，都有

（1）若 $y_i=+1$，则 $W^T{X}_i+b>0$
（2）若 $y_i=-1$，则 $W^T{X}_i+b<0$
引入增广向量以后，将原任务转化为新任务
简化表达后的新任务：
寻找 $W=(W,b{)}^T$，使得对于 $\forall$ $i$( $i=1,2,...,N$) ，有
$$W^T{\vec{X}}_i>0$$

3.2 基于增广向量的感知器算法伪代码

根据引入的增广向量，对感知器算法进行了简化，如下所示。

图3.1 基于增广向量的感知器算法伪代码

3.3 基于增广向量的感知器算法步骤

（1）随机选择 $W$ 和 $b$
（2）取一个训练样本 $(X,y)$
             （i）若 $W^T{\vec{X}}_i\le 0$，则：

$W(新)=W(旧)+{\vec{X}}_i$

（3）再取另外一个训练样本$(X^{{}^{\prime }},y^{{}^{\prime }})$，回到（2）
（4）终止条件：直到所有训练样本$(X_i,y_i)$，$i=1,2,...,N$，都不满足（2）中的（i），退出循环

4 感知器算法收敛定理

4.1 定理内容

对于 $N$ 个增广向量 ${\vec{X}}_1,{\vec{X}}_2,...,{\vec{X}}_N$，如果存在一个权重向量$W_{opt}$，使得对于每一个$i=1,2,...,N$，有
$$W_{opt}^T{\vec{X}}_i>0$$
那么运用上述感知器算法，一定能在有限步内找到一个 $W$，使得对于每一个$i=1,2,...,N$，有
$$W^T{\vec{X}}_i>0$$
注：

1. 该定理的条件（即存在权重向量对于$\forall i$ 满足$W_{opt}^T{\vec{X}}_i>0$）与训练数据集线性可分等价
2. 该定理在有限步内找到的 $W$ 不一定和条件中的权重向量 $W_{opt}$ 是同一个向量，因为回顾线性可分的定义，如果存在一个超平面分开两类，则一定存在无限个超平面分开两类，而 $W$ 和 $W_{opt}$ 往往是无限个超平面中的两个。

4.2 定理证明

首先，我们假设 $||W_{opt}||=1$
为什么可以这么假设？
理由： 向量 $W$ 和 $aW$ 代表的是同一个平面$W^T{\vec{X}}_i=0$（$W$ 和 ${\vec{X}}_i$ 均是增广向量），因此我们可以用一个 $a$ 去加权 $W_{opt}$ ，使得$||W_{opt}||=1$
下面继续证明该定理
定义 $W(k)$为第 $k$ 次改变后的权重向量值，分为以下两种情况：
情况1：
如果对所有的 $i=1,2,...,N$，都有 $W(k{)}^T{\vec{X}}_i>0$，那么所有的点都已经达到了平衡，感知器算法收敛。
情况2：
如果存在某个 $i$，使得 $W(k{)}^T{\vec{X}}_i\le 0$，那么根据感知器算法，有 $$W(k+1)=W(k)+{\vec{X}}_i$$
将这个式子两边同时减去 $a{W}_{opt}$，我们将会得到
$$W(k+1)-a{W}_{opt}=W(k)-a{W}_{opt}+{\vec{X}}_i$$
将这个式子展开并取模，我们将会得到
∣ ∣ W ( k + 1 ) − a W o p t ∣ ∣ 2 = ∣ ∣ W ( k ) − a W o p t + X ⃗ i ∣ ∣ 2 = ∣ ∣ W ( k ) − a W o p t ∣ ∣ 2 + 2 W ( k ) T X ⃗ i − 2 a W o p t T X ⃗ i

$$\begin{align*} &||W(k+1)-aW_{opt}||^2\\ =&||W(k)-aW_{opt}+\vec{X}_i||^2\\ =&||W(k)-aW_{opt}||^2+2W(k)^T\vec{X}_i-2aW_{opt}^T\vec{X}_i \end{align*}$$ ==​∣∣W(k+1)−aWopt​∣∣2∣∣W(k)−aWopt​+X i​∣∣2∣∣W(k)−aWopt​∣∣2+2W(k)TX i​−2aWoptT​X i​​
由于$W(k{)}^T{\vec{X}}_i\le 0$，因此有
$$||W(k+1)-a{W}_{opt}|{|}^2\le ||W(k)-a{W}_{opt}|{|}^2+||{\vec{X}}_i|{|}^2-2a{W}_{opt}^T{\vec{X}}_i$$
又由于对$\forall i(i=1,2,...,N)$，$W_{opt}^T{\vec{X}}_i>0$，而 $||{\vec{X}}_i|{|}^2$ 是一个有界的值，那么我们一定可以取一个足够大的 $a$ ，使得 $||{\vec{X}}_i|{|}^2-2a{W}_{opt}^T{\vec{X}}_i<-1$，因此我们有
$$||W(k+1)-a{W}_{opt}|{|}^2\le ||W(k)-a{W}_{opt}|{|}^2-1$$
可见 $W$ 的值每更新一次，它离$a{W}_{opt}$ 的距离至少减少一个单位
假设 $W$ 的初值是 $W(0)$，最多经过 $||W(0)-a{W}_{opt}|{|}^2$ 次迭代，$W$ 就一定会收敛到 $a{W}_{opt}$
当然，更有可能的是，没有经过 $||W(0)-a{W}_{opt}|{|}^2$ 次迭代，感知器算法就已经收敛并退出循环了

5 感知器算法收敛的MATLAB程序

用MATLAB实现感知器算法，并实现了感知器算法的收敛，模型完美地将两类样本分割开来。

5.1 收敛结果

图5.1 感知器收敛结果 代码请参考 胡浩基的机器学习网课

6 感知器算法的意义

感知器算法的实质是在训练数据集线性可分的情况下，寻找分类的超平面，这与支持向量机做的事情是一样的。
但是由于支持向量机是基于所有的训练数据，寻找最大化间隔的超平面，而感知器算法随意找一个分开两类的超平面，因此，大多数时候支持向量机画出的分类面比感知器算法好一点。如图6.1所示。

图6.1 感知器算法和支持向量机的超平面比较
感知器算法是1957年提出的，支持向量机是1995年提出的，支持向量机的分类效果要远好于感知器。

虽然感知器算法性能不太好，我们现在也很少使用它，但是它在机器学习这一领域的发展过程中有重要历史意义。事实上，Rosenblatt首次提出机器学习标准框架。

6.1 框架简介

这种意义表现在，感知器首先提出了一套机器学习算法的框架，如下图所示

图6.2 机器学习框架

其中，$X$ 是输入，$Y$ 是输出，$f(X,\theta )$ 是机器学习的模型，其中 $\theta$ 是待学习的参数。
现在有一组训练数据集 $\{(X_1,y_1),(X_2,y_2),...,(X_N,y_N)\}$，训练样本为$(X_i,y_i)，i=1,2,...,N$
学习的目的是寻找预测函数 $y=f(X,\theta )$
其中，$f$ 的形式是人为指定的，$\theta$ 是待求的变量。
机器学习的过程就是运用训练数据集来求出 $\theta$
对于任意测试样本，可以直接通过 $f(X,\theta )$ 计算输出 $y$，从而完成对测试样本的输出预测。
在感知器算法中：(特别分析一下感知器算法)
待估计参数 $\theta =(W,b)$，而 $f(X,\theta )=sgn(W^{T}X+b)$
假设 $X$ 是 $M$ 维度的特征向量，那么待估计 参数 $\theta$ 是 $M+1$ 维的向量，也就是说，我们将估计 $M+1$ 个参数，其中 $W$ 中有 $M$ 个参数，$b$ 也是 $1$ 个参数。
回到机器学习框架本身，这个机器学习框架包含了所有分类和回归问题，也包含了强化学习、无监督学习等机器学习其它领域的问题。这是一个相当广泛的算法框架。下面讲述一下对这个框架一些直观的感觉和认识。

6.2 欠拟合和过拟合

首先，训练数据的复杂度应该和预测函数 $f$ 的复杂度相匹配。

图6.3 模型的评估

在第一张图中，训练数据的分布相对复杂，但 $f$ 是一个简单的线性函数，那么我们无论算出的 $\theta$ 是多少，都不可能全面模拟训练数据的分布。
我们把训练数据比预测函数更复杂的情况叫做模型欠拟合(underfit)
第二张图，是训练数据的复杂度和预测函数 $f$ 的复杂度相适应的情况，这时模型的预测能力很好。
第三张图中，训练数据的复杂度低于预测函数 $f$ 的复杂度，其结果是预测函数能相当精确地拟合训练数据，但是在没有训练数据的区域，预测函数会“人为的”制造出复杂的函数值的分布，之所以说是“人为的”，是因为这种复杂的分布是由预测函数 $f$ 的具体形式决定的。而 $f$ 的具体形式是设计算法者人为指定的，它并不反映数据在空间分布的真实情况。
我们把预测函数复杂度高于训练数据复杂度的情况叫做模型过拟合(overfit)
在过拟合的情况下，会出现预测函数在训练数据上预测地非常精确，但在测试数据上预测地很糟糕。
一般来说， 在现实生活中的机器学习问题中，训练数据的分布是非常复杂的，因此我们要设计复杂的预测函数 $f$，使他与训练数据的复杂程度相适应。在复杂的预测函数中，待求的变量 $\theta$ 的维度也非常高。

6.3 Facebook人脸识别简介

图6.4 Facebook人脸识别

由于人脸识别是一个复杂的任务，训练数据的分布极其复杂，Facebook用400万张标注好的人脸数据进行训练，识别算法是深度学习的网络模型，深度学习也是一种人为指定了预测函数 $f$ 的形式。
在这个预测函数f的形式中，待求参数 $\theta$ 的维度是1800多万维。也就是说，我们要通过400多万张人脸图片去求出 $\theta$ 的1800多万个分量。目前的机器学习的任务和解决任务的方法复杂到了这样的程度。
但是，Rosenblatt提出的这套算法框架仍然适用。

6.4 感知器和支持向量机的比较

我们再看看感知器算法：

图6.5 感知器算法

我们能看出，相比于支持向量机，感知器算法有什么优势吗？优势在于消耗的计算资源和内存资源非常少。
我们看到在感知器算法中，我们只需要储存 $W$ 和 $b$，针对每次输入的训练样本 $(X,y)$，不断地调整 $W$ 和 $b$ 的值，调整的函数也是非常简单的加减法。
而支持向量机中，却是把所有的训练数据输入进计算机，让计算机解一个全局优化问题，其计算机量和存储量与感知器算法不可同日而语。
目前的机器学习领域，由于训练数据非常多，这种每次只送一小部分数据去训练，然后不断循环的算法，越来越受到大家的欢迎，而像支持向量机针对所有数据进行全局优化的算法，反而不占优势了。感知器算法是这类算法的先驱，具有重要的历史地位。

6.5 小结

我们在机器学习算法框架方面和感知器算法自身特点方面论述了感知器算法的重要历史意义，并在预测函数和训练数据复杂度匹配性方面作了初步的探讨，提出了欠拟合(underfit)和过拟合(overfit)。

参考资料： 机器学习 胡浩基 浙江大学