感知器

感知器(Perceptron)1957年提出,是一种广泛使用的线性分类器。感知器可谓是最简单的人工神经网络,只有一个神经元。

1. 概述

感知器是对生物神经元的简单数学模拟,有与生物神经元相对应的部件,如权重(突触)、偏置(阈值)及激活函数(细胞体),输出为 +1 或-1

感知器是一种简单的两类线性分类模型。(分段函数)
\hat{y}=sgn(w^Tx).\tag{1.1}

2 参数学习

感知器学习算法也是一个经典的线性分类器的参数学习算法。

给定N个样本的训练集:{(x^{(n)}, y^{(n)})}^N_{n=1},其中y^{(n)} ∈ \{ +1, −1 \},感知器学习算法试图找到一组参数w^∗,使得对于每个样本(x^{(n)}, y^{(n)})
y^{(n)}w^{*T}x^{(n)}>0, \forall n\in[1, N]\tag{2.1}

感知器的学习算法是一种错误驱动的在线学习算法。先初始化一个权重向量w \leftarrow 0(通常是全零向量),然后每次分错一个样本(x,y) 时,即yw^Tx<0,就用这个样本来更新权重。

w \leftarrow w + yx \tag{2.2}

根据感知器的学习策略,可以反推出感知器的损失函数为:
L(w;x,y)=max(0, -yw^Tx) \tag{2.3}

采用随机梯度下降,其每次更新的梯度为
\frac{\partial L(w;x,y)}{\partial w}=\begin{cases} 0, & \mbox{if } yw^Tx>0 \\ -yx, & \mbox{if } yw^Tx \leq0 \end{cases}\tag{2.4}

图3.5给出了感知器参数学习的更新过程,其中红色实心点为正例,蓝色空心点为负例。黑色箭头表示权重向量,红色虚线箭头表示权重的更新方向。

2.5 感知器参数学习的更新过程

3 感知器的收敛性

Novikoff [1963]证明对于两类问题,如果训练集是线性可分的,那么感知器算法可以在有限次迭代后收敛。然而,如果训练集不是线性分隔的,那么这个算法则不能确保会收敛

当数据集是两类线性可分时,对于训练集D = \{(x^{(n)},y^{(n)})\}^N_{n=1},其中x^{(n)} 为样本的增广特征向量,y^{(n)} ∈ \{−1,1 \},那么存在一个正的常数\gamma(\gamma > 0) 和权重向量w^∗,并且||w^*|| = 1,对所有n都满足(w^∗)^T(y^{(n)}x^{(n)}) ≥ \gamma。我们可以证明如下定理。

定理3.1–感知器收敛性:给定一个训练集D = \{(x^{(n)},y^{(n)})\}^N_{n=1}, 假设 R 是训练集中最大的特征向量的模,

R = \max_n \parallel x(n)\parallel.
如果训练集 D 线性可分,感知器学习算法3.1的权重更新次数不超
\frac{R^2}{γ^2}。

证明. 感知器的权重向量的更新方式为
w_k=w_{k+1}+y^{(k)}x^{(k)}\tag{3.2}
其中x^{(k)},y^{(k)}表示第k个错误分类的样本。

因为初始权重向量为0,在第K次更新时感知器的权重向量为
w_K=\sum_{k=1}^{K}y^{(k)}x^{(k)}\tag{3.3}

分别计算\parallel w_K\parallel^2的上下界:

(1)\parallel w_K\parallel^2的上界为:

y_kw^T_{K−1}x^{(K)} ≤ 0.

\parallel w_K\parallel^2 = \parallel w_{K−1} + y^{(K)}x^{(K)}\parallel^2\tag{3.4}
= ∥w_{K−1}∥^2 + ∥y^{(K)}x^{(K)}∥^2 + 2y^{(K)}w_{K−1}^Tx^{(K)} \tag{3.5}
≤ ∥w_{K−1}∥^2 + R^2\tag{3.6}
≤ ∥w_{K−2}∥^2 + 2R^2\tag{3.7}
≤ KR^2\tag{3.8}

(2)\parallel w_K\parallel^2的下界为:

∥w^*∥=1.
两个向量内机的平方一定小于等于这两个向量的模的乘积
{w^*}^T(y^{(n)}x^{(n)})\geq\gamma,\forall n.

∥w_K∥^2=∥w^*∥^2·∥w_K∥^2\tag{3.9}
\geq\parallel{w^*}^Tw_K\parallel^2\tag{3.91}
=\parallel{w^*}^T\sum_{k=1}^{K}(y^{(k)}x^{(k)})\parallel^2\tag{3.92}
=\parallel\sum_{k=1}^{K}{w^*}^T(y^{(k)}x^{(k)})\parallel^2\tag{3.93}
\geq K^2\gamma^2\tag{3.94}

由公式(3.8)和(3.94),得到
K^2\gamma^2\leq\parallel w_K\parallel^2\leq KR^2\tag{3.95}

取最左和最右的两项,进一步得到,K^2\gamma^2\leq KR^2\。然后两边除以K,最终得到
K\leq\frac{R^2}{\gamma^2}\tag{3.96}

因此,在线性可分的条件下,算法3.1会在\frac{R^2}{\gamma^2} 步内收敛。

虽然感知器在线性可分的数据上可以保证收敛,但其存在以下不足之处:

  1. 在数据集线性可分时,感知器虽然可以找到一个超平面把两类数据分开, 但并不能保证能其泛化能力。
  2. 感知器对样本顺序比较敏感。每次迭代的顺序不一致时,找到的分割超平面也往往不一致。
  3. 如果训练集不是线性可分的,就永远不会收敛[Freund and Schapire, 1999]。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。