感知器

感知机(Perceptron)是一种二元线性分类器,是最简单的前向人工神经网络.1957由Rosenblatt在康奈尔航空研究室提出,受到心理学家McCulloch和数理逻辑学家Watt Pitts关于人工神经元数学模型的启发,开发出的模仿人类具有感知能力的试错,调整的机器学习方法.

算法

感知机有多种算法,比如最基本的感知机算法,感知机边界算法和多层感知机.我们这里介绍最基本的感知机算法.

以一组线性可分的二元d维数据集$ X =\{ (\vec{x_i}, y_t):y_t \in \{-1,1 \}, i \in [1,n]\}$为训练集,我们寻找一个分隔超平面$\vec{w^*} \cdot \vec{x} = 0$.

1. 初始化$\vec{w_0} = \vec{0}$,记$t=0$
2. 从$X$中拿出一个数据点$\vec{x_i}$,如果$\vec{w^*} \cdot \vec{x}> 0$,预测$\hat{y_i} = 1$,否则$\hat{y_i} = -1$
3. 如果$ y_i \neq \hat{y_i}$,更新一次 $\vec{w_t+1} = \vec{w_t} + y_i * \vec{x_i}, t=t+1 $
4. 重复2和3,直到遍历$X$

收敛性和复杂度

由Novikoff定理可知,最多经过$ \frac{R^2}{\gamma ^2}$步迭代就会收敛,其中$R,\gamma $分别为数据集中元素的长度的最大值和到分割超平面的最小几何距离.

感知机算法复杂度是$O(n)$

优缺点

感知机最大的特点是简单,并且错误边界可控.但基本感知机算法无法处理非线性可分数据集和亦或(XOR)问题,因为基本感知机算法只是在平面画条线,无法把$\{ (-1,-1), (1,1)\}$和$\{ (1,-1), (1,-1)\}$区分开.

发展

模仿神经科学,我们可以把感知机刻画成一个只有输入层和输出层的神经网络. Rosenblatt等人意识到引入隐藏层,也就是在输入层和输出层之间加入新的层并加入激活函数,可以解决线性不可分的问题.加上上世纪80年代,反向算法的提出,带动了神经网络,以至于现在如火如荼的深度学习的研究.