感知机

来自集智百科
跳转到: 导航搜索

该词条由 NeverMoes 翻译编辑,由flynn审校,张江总审校,翻译自Wikipedia词条:Perceptron

机器学习中,感知机 有监督学习中的一种二元分类器(一种输入一个实值向量,判断其是否属于某一个类的函数[1])。


这是一种线性分类器,即一种基于线性预测函数将一组权值与特征向量相结合的分类算法。

机器学习和数据挖掘


目录

历史

参见:人工智能、感知机历史和联结主义的黑暗时代History of artificial intelligence § Perceptrons and the dark age of connectionism人工智能寒冬AI winter § The abandonment of connectionism in 1969

Mark 1 感知机是第一个感知机算法的应用。这个机器与一个使用20x20硫化镉电池的相机相连,能够生成一张400像素的图片。它主要的可视特征就是一块插板,允许不同的输入组合进行试验。右边是电位计,实现权重的更新。[2]

感知机算法由Frank Rosenblatt[3]在1957年在Cornell Aeronautical Laboratory(康奈尔航空实验室)发明,由美国The Office of Naval Research(海军研办公室)资助[4]


感知机的目的是成为一台机器,而不是一个程序,虽然它的第一个实现是在IBM 704的软件中完成的,但是它后来在定制的硬件中实现为"Mark 1 感知机"。这台机器是为图像识别而设计的:它有一个由400个光电池组成的阵列,随机与“神经元”相连。权重在电位器中编码,权重的更新是由电动马达完成的[2]

在1958年由美国海军组织的新闻发布会上,Rosenblatt发表了关于感知机的说明,感知机在新兴的人工智能社区中引起了激烈的讨论。根据Rosenblatt的说明,纽约时报报道这个感知机是一个电子计算机的胚胎,(海军)希望它能够行走、说话、写字、看见。复制自己并意识到自己的存在。[4]


虽然感知机起初看起来前途无量,但是感知机很快就被证明不能被训用来识别很多其他的模式。这使得神经网络的研究领域停滞了很多年直到人们认识到一个有两层及以上的前馈神经网络(也称为多层感知机),其处理能力远远大于单层的(也称为单层感知机)。单层感知机只能学习线性可分的模式。1969年Marvin Minsky和Seymour Papert出版的一本著名的著作《感知机》表明,单层感知机学习一个XOR函数是不可能的。于是人们错误的认为以及推测对于多层感知机也会有类似的结果。然而,这是不对的。因为Minsky 和 Papert 都已经知道多层的感知机可以构造XOR函数。三年后,Stephen Grossberg发布了一系列的论文,介绍了能够对微分,对比增强和XOR函数进行建模的网络。然而,Minsky 和 Papert研究成果中的误导导致了神经网络研究的兴趣下降和资金大幅减少。直到十多年以后的十九世纪八十年代,神经网络研究才又迎来了一次复兴。该书也在1987年进行修订和再版,新版本的《感知机-修订版》对原文中的一些错误进行了说明和指正。

早在1964年,Aizerman等人[5] 就提出了核感知机算法。感知机算法的间距下界的保证首先由Yoav FreundRobert Schapire(1998)[1]在不可分的情况下给出了,最近Mehryar Mohri and Rostamizadeh (2013)推广了先前的结论并给出了新的L1下界[6]


感知机是一个简化的生物神经元模型。虽然生物神经元模型的复杂性是通常是理解神经行为所必须的。但研究表明,类感知机的线性模型也可以产生一些在真实神经元中看到的行为。[7][8].

定义

在现代,感知机是一种二分类学习算法:用一个函数将输入 x(一个实值向量)映射到输出值f(x)(一个二元值):


f(x) = \begin{cases}1 & \text{if }\ \mathbf{w} \cdot \mathbf{x} + b > 0\\0 & \text{otherwise}\end{cases}

这里的 w 是一个实值构成的权重向量,\mathbf{w} \cdot \mathbf{x}是一个点积操作即 \sum_{i=1}^m w_i x_im 是感知机输入值的个数,其中 b 是偏置项。偏置项决定了决策边界相对原点的偏移量,且不依赖于任何输入值。

在二分类问题中,f(x) 的值(0或1)用来将 x 分为正例或者负例。如果 b 是负的,那么输入和权重的结合生成的正值必须比 |b|大,从而使得分类的神经元大于0阈值。从空间上来说,偏置项改变了决策边界的位置(而不是方向)。如果训练集不是线性可分的,那么感知机学习算法就不会停止。如果向量不是线性可分的,那么学习将永远不会收敛到所有向量都分类正确的结果。感知机算法的局限性的最著名的例子就是线性不可分的情况,比如XOR问题。对于所有二分类函数的决策边界解的空间和学习表现的研究都在这个参考中[9]

在神经网络的场景中,感知机是一个以单位阶跃函数为激活函数的人工神经元。感知机算法也被称为单层感知机。这个术语用于区分多层感知机即一个更加复杂的神经网络。作为一个线性分类器,单层感知机是一类最简单的前馈神经网络

学习算法

下面是一个介绍单层感知机学习算法的例子。对于存在隐层的多层感知机,必须使用诸如反向传播等更加复杂的算法。尽管下面的方法也是可行,但如果在函数是非线性且可微的情况下,那么可以使用链式法则等方法解决问题。

当多个感知机在一个人工神经网络中组合应用时,每个输出神经元都独立于其他神经元运行。因此,学习的每一个输出都可以单独考虑。
一副图展示了感知机算法在新的训练数据加入时是如何更新它的线性边界的。

定义

我们先定义这些变量:

  • y = f(\mathbf{z}) 表示感知对于某个输入向量 \mathbf{z} 的输出。
  • D = \{(x_1,d_1),\dots,(x_s,d_s)\} 训练集 s 的样本, 其中:
    • x_jn维 输入向量。
    • d_j 是感知对应输入的期望输出值。

我们用如下方式表示特征值:

  • x_{j,i} 是输入向量的第 j 个样本的第 i 个特征。
  • x_{j,0} = 1 .

权重的表示:

  • w_i 是权重向量的第 i 个值,这是为了表示和第 i 个输入特征相乘。
  • 因为 x_{j,0} = 1 w_0 实际上表示的是偏置项也就是常量 b

为了表示每一轮独立的 \mathbf{w} ,这里使用如下符号:

  • w_i(t) 是第 t 轮训练中的权重 i

不像Logistic回归这样的线性分类算法,在感知机学习算法中没有学习速率 。这是因为通过乘以常数的更新只是放缩了权重,但不会改变预测结果的符号[10]

适当的权重被应用到输入,然后产生加权和传递给一个生成输出o的函数。

步骤

  1. 初始化权重与阈值。权重初始化为全0或者一个很小的随机值。在下面的例子中我们使用0作为初始化值。
  2. 对于数据集 D 中每一个样本 j ,对输入 x_j 执行以下的步骤,并得到期望的输出 d_j
    1. 计算以下的输出:\begin{align}
y_j(t) &= f[\mathbf{w}(t)\cdot\mathbf{x}_j] \\
&= f[w_0(t)x_{j,0} + w_1(t)x_{j,1} + w_2(t)x_{j,2} + \dotsb + w_n(t)x_{j,n}]
\end{align}
    2. 更新权重:w_i(t+1) = w_i(t) + r\cdot(d_j - y_j(t)) x_{j,i}, 0 < i < n,其中 r是学习速率。
  3. 对于离线学习,第二步需要重复直到迭代误差\frac{1}{s} \sum_{j=1}^s |d_j - y_j(t)| 小于一个用户定于的误差阈值\gamma,或者预定于的迭代轮数已经完成,这里的 s 是是样本集的大小。

这个算法在2.1和2.2步骤后更新了权重。这些权重会立即反应到训练数据中,并且随后进行更新,并不是等所有步骤结束后才更新的。

收敛性

感知机是一种线性分类器,因此如果数据集 D 是非线性可分的话,那么它永远无法让所以的输入向量分类正确,即正负的样本不能被一个线性超平面所分割。标准算法在这种情况下时是无法逐渐达到一个近似解的,并导致学习过程会直接失效。所以,如果我们不能事先知道数据集是否是线性可分的,则应该使用下面的变种。

如果训练集是线性可分的,那么感知机可以确保其收敛性。此外,感知机在训练过程中调整自身权重的次数是有上限的。

假设分属于两个类的输入向量可以被一个线性超平面分割成两个类,且样本到超平面的间距为 \gamma 。即存在一个权重向量 \mathbf{w}||\mathbf{w}||=1,以及一个偏置项 b 使得对于所有的 d_j=1 对应 j 有 \mathbf{w}\cdot\mathbf{x}_j > \gamma  d_j=0对应的 j 有 \mathbf{w}\cdot\mathbf{x}_j < -\gamma 。且如果引入 R 表示输入向量最大的维度。Novikoff (1962)证明了感知机可以在 O(R^2 \gamma^2)轮迭代中完成收敛。证证明的思路是权重向量可以被有负点积的约束值在一个方向上修正,因此可以被 Osqrt{t} 的下界约束,这里的 t 是权重向量更新的次数。然而,它也可以被  O(t) 的上界约束。因为如果存在一个未知的满足条件的权重向量,那么在这个方向上每一次权重向量的改变都只取决于输入向量。

当感知机算法在训练集线性可分的条件下会在某个解中达到收敛,而且会在多个质量不同且满足条件的解中任意选一个。[11]最佳稳定性感知机现在一般称为SVM支持向量机,就是设计用来解决这个问题的。[12]

两种种类的点和无限多的可以分割它们的线性边界。即使这两条线性边界是直角相对的,感知机算法也无法从其中选择。

变种

渐进的pocket算法(Gallant, 1990)通过保留最近的最佳解解决了感知机学习过程中的稳定性问题。pocket算法接下来返回保存最佳的解而不是迭代的最后一个解。它也可以被用于线性不可分的数据集,那么感知机的学习目的就是找一个使得误分类数量最小的解。然而这些解是完全随机出现的,因此pocket算法不能在学习的过程中最终得到这些解也不能保证在给定的迭代次数中找到这些解。

Maxover算法 (Wendemuth, 1995)[13] 在某种意义上是稳健的(robust),因为无论是否事先知道数据集线性可分,它都会达到收敛。在线性可分的情况下,即使具有最佳的稳定性(即类之间达到最大间距)也能很好解决训练问题。对于线性不可分的数据集,它会返回一个少量误分类的解。在所有的情况下,该算法在学习过程中会逐渐接近解而不会存储先前的状态,也不会随机跳跃。收敛性是指线性可分数据集的全局最优解和非线性可分数据的局部最优解。

投票感知机 (Freund and Schapire, 1999),是一种使用多权重的感知机的变种。每当一个例子被错误的分类时,算法会启动一个新的感知机,然后使用最后的感知机的权重作为现在感知机的初始化权重。每次分类错误感知机都会被给予另外的权重直到所以样本分类正确。最后得到所有感知机加权投票的结果。

在线性可分问题中,感知机的训练目标在于在样本之间找到最大的间距分割两个类。所谓的最优稳定性感知机可以通过迭代训练和优化策略来确定,比如Min-Over算法 (Krauth and Mezard, 1987)[12] 或者AdaTron算法 (Anlauf and Biehl, 1989))。[14] AdaTron利用了问题对应的二次优化是凸的这一条件。最佳稳定性感知机加上核方法,这是SVM支持向量机概念的基础。

\alpha-感知机使用了带有阈值输出单元的固定随机权重的预处理层。这使得感知机能够通过投影二元空间类似的模式进行分类。实际上对于一个维度足够高的的投影空间,模式就会变得线性可分了。

解决线性不可分问题的另一种方法是使用高阶的网络(sigma-pi unit)。在这种类型的网络中,每个输入向量的元素都会使用复杂输入(二阶)组合来拓展到高纬。这可以使其拓展到一个n阶网络。

但是,我们应该牢记,最好的分类器不需要完美分类所有训练数据。实际上,如果我们有先验性的约束,即数据据来自于高斯分布。那么输入空间的线性解是最佳的,而非线性解是过拟合的。

其他的线性分类算法包括了WinnowSVM支持向量机,和Logistic回归

多分类感知机

类似于其他训练线性分类器的技巧,感知机可以很自然地泛化成多分类分类器。这里的输入 x 和输出 y 是从任意集合中得到的。特征表示函数f(x,y)将每一个可能的输入/输出对映射到一个有限维的实值特征向量上。与之前相同,特征向量乘以一个权重向量 w,但是现在该结果的值将被用于选择许多可能输出结果的其中之一:

\hat y = \operatorname{argmax}_y f(x,y) \cdot w.

同样通过在样本的迭代来完成学习,预测每一个输出的结果,当预测和实际结果匹配时不更新权重,反之则更新。更新方式就是:

 w_{t+1} = w_t + f(x, y) - f(x,\hat y).

x 是一个实值向量,这个多分类的更新公式会退化到原始的感知机的更新公式。即 y\{0,1\}中的一个,f(x,y) = y x

对于某些问题,可以选择输入/输出和特征的表示。所以即使 y 是一个非常大或者无限集合中的元素。 \mathrm{argmax}_y f(x,y) \cdot w 也可以被高效地找到。

在最近的几年,感知机的训练已经成为了自然语言处理的热门话题,比如语音标记语法分析等任务(Collins, 2002)。

参考

  1. 1.0 1.1 Freund, Y.; Schapire, R. E.(1999), "Large margin classification using the perceptron algorithm" . Report 37 (3): 277–296, doi:10.1023/A:1007662407062.
  2. 2.0 2.1 Bishop, Christopher M. (2006), Pattern Recognition and Machine Learning. Springer.
  3. Rosenblatt, Frank (1957), The Perceptron--a perceiving and recognizing automaton. Report 85-460-1, Cornell Aeronautical Laboratory.
  4. 4.0 4.1 Mikel Olazaran (1996). " A Sociological Study of the Official History of the Perceptrons Controversy". Social Studies of Science. 26 (3): 611–659 doi:10.1177/030631296026003005. JSTOR 285702.
  5. Aizerman, M. A.; Braverman, E. M.; Rozonoer, L. I. (1964). "Theoretical foundations of the potential function method in pattern recognition learning". Automation and Remote Control 25: 821–837.
  6. Mohri, Mehryar and Rostamizadeh, Afshin (2013). Perceptron Mistake Bounds arXiv:1305.0208, 2013.
  7. Morel, D., Singh, C. & Levy, W.B. J Comput Neurosci (2018). http://rdcu.be/FDUo
  8. Cash, Sydney, and Rafael Yuste. "Linear summation of excitatory inputs by CA1 pyramidal neurons." Neuron 22.2 (1999): 383-394.APA
  9. Liou, D.-R.; Liou, J.-W.; Liou, C.-Y. (2013). Learning Behaviors of Perceptron. iConcept Press. ISBN978-1-477554-73-9.
  10. Genevieve B. Orr. "The Perceptron". Willamette University. Retrieved 3 March 2017.
  11. Bishop, Christopher M. "Chapter 4. Linear Models for Classification". Pattern Recognition and Machine Learning. Springer Science+Business Media, LLC. p. 194. ISBN 978-0387-31073-2.
  12. 12.0 12.1 W. Krauth and M. Mezard. Learning algorithms with optimal stability in neural networks. J. of Physics A: Math. Gen. 20: L745-L752 (1987)
  13. A. Wendemuth. Learning the Unlearnable. J. of Physics A: Math. Gen. 28: 5423-5436 (1995)
  14. J.K. Anlauf and M. Biehl. The AdaTron: an Adaptive Perceptron algorithm. Europhysics Letters 10: 687-692 (1989)

深入阅读

  • Aizerman, M. A. and Braverman, E. M. and Lev I. Rozonoer. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821–837, 1964.
  • Rosenblatt, Frank (1958), The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain, Cornell Aeronautical Laboratory, Psychological Review, v65, No. 6, pp. 386–408. doi:10.1037/h0042519.
  • Rosenblatt, Frank (1962), Principles of Neurodynamics. Washington, DC:Spartan Books.
  • Minsky M. L. and Papert S. A. 1969. Perceptrons. Cambridge, MA: MIT Press.
  • Gallant, S. I. (1990). Perceptron-based learning algorithms. IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179–191.
  • Mohri, Mehryar and Rostamizadeh, Afshin (2013). Perceptron Mistake Bounds arXiv:1305.0208, 2013.
  • Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.
  • Widrow, B., Lehr, M.A., "30 years of Adaptive Neural Networks: Perceptron, Madaline, and Backpropagation," Proc. IEEE, vol 78, no 9, pp. 1415–1442, (1990).
  • Collins, M.2002. Discriminative training methods for hidden Markov models: Theory and experiments with the perceptron algorithm in Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP '02).
  • Yin, Hongfeng (1996), Perceptron-Based Algorithms and Analysis, Spectrum Library, Concordia University, Canada

外部链接

本词条内容翻译自 wikipedia.org,遵守 CC3.0协议。

个人工具
名字空间
操作
导航
工具箱