421
个编辑
更改
跳到导航
跳到搜索
创建页面，内容为“{{#seo: |keywords=感知机,感知器,集智,集智俱乐部 |description=感知机,感知器,集智,集智俱乐部 }} 在机器学习中，'''感知机'''是…”
{{#seo:
|keywords=感知机,感知器,集智,集智俱乐部
|description=感知机,感知器,集智,集智俱乐部
}}
在[[机器学习]]中，'''感知机'''是[[ 有监督学习]]中的一种[https://en.wikipedia.org/wiki/Binary_classification 二元分类器]（一种输入一个实值向量，判断其是否属于某一个类的函数<ref name = "T1">[https://en.wikipedia.org/wiki/Yoav_Freund Freund, Y.]; [https://en.wikipedia.org/wiki/Robert_Schapire Schapire, R. E.](1999), [https://cseweb.ucsd.edu/~yfreund/papers/LargeMarginsUsingPerceptron.pdf "Large margin classification using the perceptron algorithm" .] Report 37 (3): 277–296, [https://link.springer.com/article/10.1023%2FA%3A1007662407062 doi:10.1023/A:1007662407062].</ref>）。
这是一种[https://en.wikipedia.org/wiki/Linear_classifier 线性分类器]，即一种基于[https://en.wikipedia.org/wiki/Linear_predictor_function 线性预测函数]将一组权值与特征向量相结合的分类算法。
[[File:Kernel_Machine.svg.png|300px|thumb|right|机器学习和数据挖掘]]
==历史==
参见：[https://en.wikipedia.org/wiki/History_of_artificial_intelligence#Perceptrons_and_the_dark_age_of_connectionism 人工智能、感知机历史和联结主义的黑暗时代History of artificial intelligence § Perceptrons and the dark age of connectionism] 和[https://en.wikipedia.org/wiki/AI_winter#The_abandonment_of_connectionism_in_1969 人工智能寒冬AI winter § The abandonment of connectionism in 1969]
===来源===
感知机算法由Frank Rosenblatt<ref>Rosenblatt, Frank (1957), The Perceptron--a perceiving and recognizing automaton. Report 85-460-1, Cornell Aeronautical Laboratory.</ref>在1957年在[https://en.wikipedia.org/wiki/Calspan Cornell Aeronautical Laboratory(康奈尔航空实验室)]时所发明的一种[[人工神经网络]]，它可以被视为一种最简单形式的[[前馈神经网络]]，是一种二元[[线性分类器]]。由美国[https://en.wikipedia.org/wiki/Office_of_Naval_Research The Office of Naval Research(海军研办公室)]资助<ref name= "office">Mikel Olazaran (1996). " A Sociological Study of the Official History of the Perceptrons Controversy". Social Studies of Science. 26 (3): 611–659 [http://journals.sagepub.com/doi/10.1177/030631296026003005 doi:10.1177/030631296026003005]. [https://en.wikipedia.org/wiki/JSTOR JSTOR] [https://www.jstor.org/stable/285702 285702]. </ref>。
Frank Rosenblatt给出了相应的感知机学习算法，常用的有感知机学习、最小二乘法和梯度下降法。譬如，感知机利用梯度下降法对损失函数进行极小化，求出可将训练数据进行线性划分的分离超平面，从而求得感知机模型。
[[File:Complete neuron cell diagram zh.png|thumb|right|300px|神经细胞结构示意图]]
感知机是生物[[神经细胞]]的简单抽象。神经细胞结构大致可分为：[[树突]]、[[突触]]、[[细胞体]]及[[轴突]]。单个神经细胞可被视为一种只有两种状态的机器——激动时为『是』，而未激动时为『否』。神经细胞的状态取决于从其它的神经细胞收到的输入信号量，及突触的强度（抑制或加强）。当信号量总和超过了某个阈值时，细胞体就会激动，产生电脉冲。电脉冲沿着轴突并通过突触传递到其它神经元。为了模拟神经细胞行为，与之对应的感知机基础概念被提出，如权量（突触）、偏置（阈值）及激活函数（细胞体）。
虽然[生物神经元模型]的复杂性是通常是理解神经行为所必须的。但研究表明，类感知机的线性模型也可以产生一些在真实神经元中看到的行为。<ref>Morel, D., Singh, C. & Levy, W.B. J Comput Neurosci (2018). http://rdcu.be/FDUo</ref><ref>Cash, Sydney, and Rafael Yuste. "Linear summation of excitatory inputs by CA1 pyramidal neurons." Neuron 22.2 (1999): 383-394.APA</ref>.
感知机的目的是成为一台机器，而不是一个程序，虽然它的第一个实现是在[IBM 704]的软件中完成的，但是它后来在定制的硬件中实现为"Mark 1 感知机"。这台机器是为图像识别而设计的：它有一个由400个[ 光电池]组成的阵列，随机与“神经元”相连。权重在[电位器]中编码，权重的更新是由电动马达完成的<ref name = "update">Bishop, Christopher M. (2006), Pattern Recognition and Machine Learning. Springer.</ref>。
在1958年由美国海军组织的新闻发布会上，Rosenblatt发表了关于感知机的说明，感知机在新兴的[[人工智能]]社区中引起了激烈的讨论。根据Rosenblatt的说明，[纽约时报]报道这个感知机是一个电子计算机的胚胎，(海军)希望它能够行走、说话、写字、看见。复制自己并意识到自己的存在。<ref name= "office">Mikel Olazaran (1996). " A Sociological Study of the Official History of the Perceptrons Controversy". Social Studies of Science. 26 (3): 611–659 [http://journals.sagepub.com/doi/10.1177/030631296026003005 doi:10.1177/030631296026003005]. [https://en.wikipedia.org/wiki/JSTOR JSTOR] [https://www.jstor.org/stable/285702 285702]. </ref>
===发展===
[[File:Mark_I_perceptron.jpeg|180px|thumb|right|Mark 1 感知机是第一个感知机算法的应用。这个机器与一个使用20x20硫化镉电池的相机相连，能够生成一张400像素的图片。它主要的可视特征就是一块插板，允许不同的输入组合进行试验。右边是电位计，实现权重的更新。<ref name = "update">Bishop, Christopher M. (2006), Pattern Recognition and Machine Learning. Springer.</ref> ]]
1943年，心理学家[[沃伦·麦卡洛克]]和数理逻辑学家[[沃尔特·皮茨]]在合作的《A logical calculus of the ideas immanent in nervous activity》<ref>Warren S. McCulloch and Walter Pitts (1943), A logical calculus of the ideas immanent in nervous activity</ref>论文中提出并给出了[[人工神经网络]]的概念及人工[[神经元]]的数学模型，从而开创了人工神经网络研究的时代。1949年，心理学家[[唐纳德·赫布]]在《The Organization of Behavior》<ref>Donald Hebb (1949) The Organization of Behavior: A Neuropsychological Theory</ref>论文中描述了神经元学习法则——[[赫布型学习]]。
人工神经网络更进一步被美国神经学家弗兰克·罗森布拉特 Frank Rosenblatt 所发展。他提出了可以模拟人类感知能力的机器，并称之为『感知机』。1957年，在Cornell航空实验室中，他成功在IBM 704机上完成了感知机的仿真。两年后，他又成功实现了能够识别一些英文字母、基于感知机的[[神经计算机]]——[[Mark1]]，并于1960年6月23日，展示与众。首个有关感知机的成果，由弗兰克·罗森布拉特于1958年发表在《The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain》<ref>Rosenblatt, Frank. x. (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}}</ref>的文章里。1962年，他又出版了《Principles of Neurodynamics: Perceptrons and the theory of brain mechanisms》<ref>Rosenblatt, Frank. x. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. Spartan Books, Washington DC, 1961</ref>一书，向大众深入解释感知机的理论知识及背景假设。此书介绍了一些重要的概念及[[定理]]证明，例如感知机收敛定理。
为了『教导』感知机识别图像，弗兰克·罗森布拉特在[[Hebb学习法则]]的基础上，发展了一种迭代、试错、类似于人类学习过程的学习算法——感知机学习。除了能够识别出现较多次的字母，感知机也能对不同书写方式的字母图像进行概括和归纳。但是，由于本身的局限，感知机除了那些包含在训练集里的图像以外，不能对受干扰（半遮蔽、不同大小、平移、旋转）的字母图像进行可靠的识别。
虽然最初被认为有着良好的发展潜能，但感知机最终被证明不能处理诸多的[[模式识别]]问题。这使得神经网络的研究领域停滞了很多年直到人们认识到一个有两层及以上的[[前馈神经网络]]（也称为[[多层感知机]]），其处理能力远远大于单层的（也称为[[单层感知机]]）。单层感知机只能学习线性可分的模式。1969年Marvin Minsky和Seymour Papert出版的一本著名的著作[[《感知机》]]表明，单层感知机学习一个[[XOR]]函数是不可能的。于是人们错误的认为以及推测对于多层感知机也会有类似的结果。然而，这是不对的。因为Minsky 和 Papert 都已经知道多层的感知机可以构造XOR函数。三年后，[https://en.wikipedia.org/wiki/Stephen_Grossberg Stephen Grossberg]发布了一系列的论文，介绍了能够对[http://cns.bu.edu/Profiles/Grossberg/Gro1973StudiesAppliedMath.pdf 微分，对比增强和XOR函数进行建模的网络]。然而，Minsky 和 Papert研究成果中的误导导致了神经网络研究的兴趣下降和资金大幅减少。直到十多年以后的十九世纪八十年代，[[神经网络]]研究才又迎来了一次复兴。该书也在1987年进行修订和再版，新版本的《感知机-修订版》对原文中的一些错误进行了说明和指正。
由于弗兰克·罗森布拉特等人没能够及时推广感知机学习算法到多层神经网络上，又由于《Perceptrons》在研究领域中的巨大影响，及人们对书中论点的误解，造成了人工神经领域发展的长年停滞及低潮，直到人们认识到[[多层感知机]]没有单层感知机固有的缺陷及[[反向传播算法]]在80年代的提出，才有所恢复。1987年，书中的错误得到了校正，并更名再版为《Perceptrons - Expanded Edition》。
1964年，Aizerman等人<ref>{{cite journal |last1=Aizerman |first1=M. A. |last2=Braverman |first2=E. M. |last3=Rozonoer |first3=L. I. |year=1964 |title=Theoretical foundations of the potential function method in pattern recognition learning |url=|journal=Automation and Remote Control |volume=25 |issue=|pages=821–837 }}</ref> 就提出了[[核感知机]]算法。在Freund及Schapire（1998）使用[[核技巧]]改进感知机学习算法之后，愈来愈多的人对感知机学习算法产生兴趣。感知机算法的间距下界的保证首先由Yoav [https://en.wikipedia.org/wiki/Yoav_Freund Freund]和[https://en.wikipedia.org/wiki/Robert_Schapire Robert Schapire](1998)<ref name = "T1"></ref>在不可分的情况下给出了，最近Mehryar [https://en.wikipedia.org/wiki/Mehryar_Mohri Mohri] and Rostamizadeh (2013)推广了先前的结论并给出了新的L1下界<ref>Mohri, Mehryar and Rostamizadeh, Afshin (2013). [https://arxiv.org/pdf/1305.0208.pdf Perceptron Mistake Bounds] arXiv:1305.0208, 2013.</ref>。后来的研究表明除了二元分类，感知机也能应用在较复杂、被称为structured learning类型的任务上（Collins, 2002），又或使用在分布式计算环境中的大规模机器学习问题上（McDonald, Hall and Mann, 2011）。
==结构==
[[File:Ncell.png|thumb|300px]]
设有<math>n</math>维输入的单个感知机（如右图示），<math>{a}_1</math>至<math>{a}_n</math>为<math>n</math>维输入[[向量]]的各个分量，<math>{w}_1</math>至<math>{w}_n</math>为各个输入分量连接到感知机的权量（或称权值），<math>{b}</math>为偏置，<math>f(.)</math>为激活函数（又曰激励函数或传递函数），<math>t</math>为标量输出。输出<math>t</math>的数学描述为：
:<math>
t = f(\sum_{i=1}^{n}{{w}_i {x}_i + b})
= f(\mathbf{w}^T \mathbf{x})
\qquad\qquad(1)</math>
其中<math>\mathbf{w} = [w_1 \; w_2 \; ... \; w_n \; b]^T</math>，<math>\mathbf{x} = [x_1 \; x_2 \; ... \; x_n \; 1]^T</math>及<math>f(x)</math>为[[反对称]]的[[符号函数]]，其定义为：
:<math>
f(n) = \begin{cases}+1 & \text{if }n \geq 0\\-1 & \text{otherwise}\end{cases}
\qquad\qquad(2)</math>
从式(1)可知，偏置被引申为权量，而对应的输入值为<math>1</math>。故，一感知机的输出行为是求得输入向量与权向量的[[内积]]后，经一个激活函数所得一个标量结果。
设输入向量与权向量的内积为零，可得出<math>(n+1)</math>维的超平面。平面的[[法向量]]为<math>\mathbf{w}</math>，并经过<math>(n+1)</math>维输入空间的原点。法向量指向的输入空间，其输出值为<math>+1</math>，而与法向量反向的输入空间，其输出值则为<math>-1</math>。故可知这个超平面定义了[[决策边界]]，并把输入空间划分为二。
==准则函数==
设一训练集为<math>D = \{(\mathbf{p}_1, \; t_1), \;\dots\;, (\mathbf{p}_m, \; t_m)\}</math>，其中<math>\mathbf{p}_i</math>表示输入，而<math>{t}_i</math>是对应的目标输出。由于符号函数的[[不连续性]]，如果采用标准的[[均方误差]]，所得[[误差函数]]必然是不连续的，因而基于[[梯度]]的学习算法也就不能被使用。为此，Rosenblatt提出了感知机准则函数：
:<math>
E(\mathbf{w}) = -\sum_{\mathbf{p}_i \in M}^{}{(\mathbf{w}^T\mathbf{p}_i) \; {t}_i}
\qquad\qquad(3)</math>
其中<math>M</math>是被当前<math>\mathbf{w}</math>错误分类的的输入向量集合。当<math>\mathbf{w}^T\mathbf{p}_i \geq 0</math>时，<math>{t}_i</math>为<math>-1</math>，而当<math>\mathbf{w}^T\mathbf{p}_i < 0</math>时，<math>{t}_i</math>为<math>+1</math>。故，误差函数<math>E(\mathbf{w})</math>是一组正数的和，又或当训练集里所有输入都被正确分类时，等于零。
== 定义 ==
在现代，感知机是一种二分类学习算法：用一个函数将输入 <math>x</math>（一个实值向量）映射到输出值<math>f(x)</math>（一个二元值）：
:<math>
f(x) = \begin{cases}1 & \text{if }\ \mathbf{w} \cdot \mathbf{x} + b > 0\\0 & \text{otherwise}\end{cases}
</math>
这里的 <math>w</math> 是一个实值构成的权重向量，<math>\mathbf{w} \cdot \mathbf{x}</math>是一个[https://en.wikipedia.org/wiki/Dot_product 点积]操作即 <math>\sum_{i=1}^m w_i x_i</math>， <math>m</math> 是感知机输入值的个数，其中 <math>b</math> 是偏置项。偏置项决定了决策边界相对原点的偏移量，且不依赖于任何输入值。
在二分类问题中，<math>f(x)</math> 的值（0或1）用来将 <math>x</math> 分为正例或者负例。如果 <math>b</math> 是负的，那么输入和权重的结合生成的正值必须比 <math>|b|</math>大，从而使得分类的神经元大于0阈值。从空间上来说，偏置项改变了[[决策边界]]的位置（而不是方向）。如果训练集不是[[线性可分]]的，那么感知机学习算法就不会停止。如果向量不是[[线性可分]]的，那么学习将永远不会收敛到所有向量都分类正确的结果。感知机算法的局限性的最著名的例子就是线性不可分的情况，比如XOR问题。对于所有二分类函数的[[决策边界]]解的空间和学习表现的研究都在这个参考中<ref name = "T9">Liou, D.-R.; Liou, J.-W.; Liou, C.-Y. (2013). Learning Behaviors of Perceptron. iConcept Press. [https://en.wikipedia.org/wiki/International_Standard_Book_Number ISBN]</ref>。
在神经网络的场景中，感知机是一个以[[单位阶跃函数]]为激活函数的[[人工神经元]]。感知机算法也被称为'''单层感知机'''。这个术语用于区分[[多层感知机]]即一个更加复杂的神经网络。作为一个线性分类器，单层感知机是一类最简单的[[前馈神经网络]]。
==学习算法==
下面是一个介绍单层感知机学习算法的例子。对于存在隐层的多层感知机，必须使用诸如[[反向传播]]等更加复杂的算法。尽管下面的方法也是可行，但如果在函数是非线性且可微的情况下，那么可以使用[[链式法则]]等方法解决问题。
当多个感知机在一个人工神经网络中组合应用时，每个输出神经元都独立于其他神经元运行。因此，学习的每一个输出都可以单独考虑。[[File:Perceptron example.svg.png|500px|thumb |right|一副图展示了感知机算法在新的训练数据加入时是如何更新它的线性边界的。]]
=== 定义 ===
我们先定义这些变量:
*<math>y = f(\mathbf{z}) </math> 表示感知对于某个输入向量 <math>\mathbf{z}</math> 的输出。
*<math>D = \{(x_1,d_1),\dots,(x_s,d_s)\} </math> 训练集 <math>s</math> 的样本， 其中:
**<math>x_j</math> 是 <math>n</math>维 输入向量。
** <math>d_j </math> 是感知对应输入的期望输出值。
我们用如下方式表示特征值：
*<math>x_{j,i} </math> 是输入向量的第 j 个样本的第 <math>i</math> 个特征。
*<math>x_{j,0} = 1 </math>.
权重的表示：
*<math>w_i </math> 是权重向量的第 <math>i</math> 个值，这是为了表示和第 <math>i</math> 个输入特征相乘。
*因为 <math>x_{j,0} = 1 </math>， <math>w_0 </math> 实际上表示的是偏置项也就是常量 <math>b</math>。
为了表示每一轮独立的 <math>\mathbf{w}</math> ，这里使用如下符号：
*<math>w_i(t) </math> 是第 <math>t</math> 轮训练中的权重 <math>i</math> 。
不像[[Logistic回归]]这样的线性分类算法，在感知机学习算法中没有''学习速率 。''这是因为通过乘以常数的更新只是放缩了权重，但不会改变预测结果的符号<ref name = "T10"> Genevieve B. Orr. [https://www.willamette.edu/~gorr/classes/cs449/Classification/perceptron.html "The Perceptron"]. Willamette University. Retrieved 3 March 2017.</ref>。
[[Image:Perceptron.svg.png|300px|right|thumb|居中|500px|适当的权重被应用到输入，然后产生加权和传递给一个生成输出o的函数。]]
=== 步骤===
# 初始化权重与阈值。权重初始化为全0或者一个很小的随机值。在下面的例子中我们使用0作为初始化值。
# 对于数据集 <math>D </math> 中每一个样本 j ，对输入 <math>x_j </math> 执行以下的步骤，并得到期望的输出 <math>d_j </math>：
## 计算以下的输出：<math>\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}</math>
## 更新权重：<math>w_i(t+1) = w_i(t) + r\cdot(d_j - y_j(t)) x_{j,i}, 0 < i < n</math>，其中 <math>r</math>是学习速率。
# 对于[https://en.wikipedia.org/wiki/Offline_learning 离线学习]，第二步需要重复直到迭代误差<math>\frac{1}{s} \sum_{j=1}^s |d_j - y_j(t)| </math>小于一个用户定于的误差阈值<math>\gamma</math>，或者预定于的迭代轮数已经完成，这里的 <math>s</math> 是是样本集的大小。
这个算法在2.1和2.2步骤后更新了权重。这些权重会立即反应到训练数据中，并且随后进行更新，并不是等所有步骤结束后才更新的。
=== 简单实现与演示 ===
摘自李航博士的《统计学习方法》，对于训练数据集，其中正例点是<math>x_1=(3,3)T</math>，<math>x_2=(4,3)T</math>，负例点为<math>x_3=(1,1)T</math>，用感知机学习算法的原始形式求感知机模型<math>f(x)=w·x+b</math>。这里<math>w=(w(1),w(2))T，x=(x(1),x(2))T</math>
<syntaxhighlight lang="python">
import numpy as np
training_set = [[3,3],[4,3],[1,1]]
Y = [1,1,-1]
w = [0,0]
b = 0
n = 1
#check给出w，b，找到一个此时的误分点，如果没有，说明算法收敛
def check(w,b):
C = []
for e in training_set:
x1 = np.array(e).reshape((-1,1))
w1 = np.array(w)
c = np.dot(w1,x1)
y = Y[training_set.index(e)]
if y*(c+b)<=0:
C.append(e[0])
C.append(e[1])
break
else:
continue
return C
def update(C,w,b):
D = []
y = Y[training_set.index(C)]
x = np.array(C)
D.append(w + n*y*x)
D.append(b + n*y)
return D
while True:
C = check(w, b)
if len(C)==0:
break
else:
w = update(C,w,b)[0]
b = update(C,w,b)[1]
print('算法已经收敛')
print('y = sign(%d*x1 + %d*x2 + %d)'%(w[0],w[1],b))
</syntaxhighlight>
得到结果
<syntaxhighlight lang="python">
算法已经收敛
y = sign(1*x1 + 1*x2 + -3)
</syntaxhighlight>
===收敛性===
感知机是一种[[线性分类器]]，因此如果数据集 <math>D</math> 是非[https://en.wikipedia.org/wiki/Linearly_separable 线性可分]的话，那么它永远无法让所以的输入向量分类正确，即正负的样本不能被一个线性超平面所分割。标准算法在这种情况下时是无法逐渐达到一个近似解的，并导致学习过程会直接失效。所以，如果我们不能事先知道数据集是否是线性可分的，则应该使用下面的变种。
如果训练集是线性可分的，那么感知机可以确保其收敛性。此外，感知机在训练过程中调整自身权重的次数是有上限的。
假设分属于两个类的输入向量可以被一个线性超平面分割成两个类，且样本到超平面的间距为 <math>\gamma </math>。即存在一个权重向量 <math>\mathbf{w}</math> 且 <math>||\mathbf{w}||=1</math>，以及一个偏置项 <math>b</math> 使得对于所有的 <math>d_j=1</math> 对应 j 有 <math>\mathbf{w}\cdot\mathbf{x}_j > \gamma </math> 和 <math> d_j=0</math>对应的 j 有 <math>\mathbf{w}\cdot\mathbf{x}_j < -\gamma </math> 。且如果引入 <math>R</math> 表示输入向量最大的维度。Novikoff (1962)证明了感知机可以在 <math>O(R^2 \gamma^2)</math>轮迭代中完成收敛。证证明的思路是权重向量可以被有负[https://en.wikipedia.org/wiki/Dot_product 点积]的约束值在一个方向上修正，因此可以被 <math>Osqrt{t}</math> 的下界约束，这里的 <math>t</math> 是权重向量更新的次数。然而，它也可以被 <math> O(t)</math> 的上界约束。因为如果存在一个未知的满足条件的权重向量，那么在这个方向上每一次权重向量的改变都只取决于输入向量。
当感知机算法在训练集线性可分的条件下会在某个解中达到收敛，而且会在多个质量不同且满足条件的解中任意选一个。<ref>Bishop, Christopher M. "Chapter 4. Linear Models for Classification". Pattern Recognition and Machine Learning. Springer Science+Business Media, LLC. p. 194. ISBN [https://en.wikipedia.org/wiki/Special:BookSources/978-0387-31073-2 978-0387-31073-2].</ref>''最佳稳定性感知机''现在一般称为[[SVM支持向量机]]，就是设计用来解决这个问题的。<ref name="KrauthMezard87">W. Krauth and M. Mezard. Learning algorithms with optimal stability in neural networks. J. of Physics A: Math. Gen. 20: L745-L752 (1987)</ref>
[[File:Perceptron cant choose.svg.png|thumb|300px|两种种类的点和无限多的可以分割它们的线性边界。即使这两条线性边界是直角相对的，感知机算法也无法从其中选择。]]
== 变种 ==
渐进的pocket算法(Gallant, 1990)通过保留最近的最佳解解决了感知机学习过程中的稳定性问题。pocket算法接下来返回保存最佳的解而不是迭代的最后一个解。它也可以被用于线性不可分的数据集，那么感知机的学习目的就是找一个使得误分类数量最小的解。然而这些解是完全随机出现的，因此pocket算法不能在学习的过程中最终得到这些解也不能保证在给定的迭代次数中找到这些解。
Maxover算法 (Wendemuth, 1995)<ref>A. Wendemuth. [http://www.iikt.ovgu.de/iesk_media/Downloads/ks/publications/papers/1995/wendemuth1995_learning_unlearnable-p-1452.pdf Learning the Unlearnable]. J. of Physics A: Math. Gen. 28: 5423-5436 (1995)</ref> 在某种意义上是[[稳健的(robust)]]，因为无论是否事先知道数据集线性可分，它都会达到收敛。在线性可分的情况下，即使具有最佳的稳定性（即类之间达到[[最大间距]]）也能很好解决训练问题。对于线性不可分的数据集，它会返回一个少量误分类的解。在所有的情况下，该算法在学习过程中会逐渐接近解而不会存储先前的状态，也不会随机跳跃。收敛性是指线性可分数据集的全局最优解和非线性可分数据的局部最优解。
投票感知机 (Freund and Schapire, 1999)，是一种使用多权重的感知机的变种。每当一个例子被错误的分类时，算法会启动一个新的感知机，然后使用最后的感知机的权重作为现在感知机的初始化权重。每次分类错误感知机都会被给予另外的权重直到所以样本分类正确。最后得到所有感知机加权投票的结果。
在线性可分问题中，感知机的训练目标在于在样本之间找到最大的间距分割两个类。所谓的最优稳定性感知机可以通过迭代训练和优化策略来确定，比如Min-Over算法 (Krauth and Mezard, 1987)<ref name="KrauthMezard87" /> 或者AdaTron算法 (Anlauf and Biehl, 1989))。<ref>J.K. Anlauf and M. Biehl. The AdaTron: an Adaptive Perceptron algorithm. Europhysics Letters 10: 687-692 (1989)</ref> AdaTron利用了问题对应的二次优化是凸的这一条件。最佳稳定性感知机加上[[核方法]]，这是[[SVM支持向量机]]概念的基础。
<math>\alpha</math>-感知机使用了带有阈值输出单元的固定随机权重的预处理层。这使得感知机能够通过投影[[二元空间]]对[[类似]]的模式进行分类。实际上对于一个维度足够高的的投影空间，模式就会变得线性可分了。
解决线性不可分问题的另一种方法是使用高阶的网络(sigma-pi unit)。在这种类型的网络中，每个输入向量的元素都会使用复杂输入(二阶)组合来拓展到高纬。这可以使其拓展到一个n阶网络。
但是，我们应该牢记，最好的分类器不需要完美分类所有训练数据。实际上，如果我们有先验性的约束，即数据据来自于高斯分布。那么输入空间的线性解是最佳的，而非线性解是[[过拟合]]的。
其他的线性分类算法包括了[[Winnow]]，[[SVM支持向量机]]，和[[Logistic回归]]。
== 多分类感知机 ==
类似于其他训练线性分类器的技巧，感知机可以很自然地泛化成[[多分类]]分类器。这里的输入 <math>x</math> 和输出 <math>y</math> 是从任意集合中得到的。特征表示函数f(x,y)将每一个可能的输入/输出对映射到一个有限维的实值特征向量上。与之前相同，特征向量乘以一个权重向量 <math>w</math>，但是现在该结果的值将被用于选择许多可能输出结果的其中之一：
:<math>\hat y = \operatorname{argmax}_y f(x,y) \cdot w.</math>
同样通过在样本的迭代来完成学习，预测每一个输出的结果，当预测和实际结果匹配时不更新权重，反之则更新。更新方式就是：
:<math> w_{t+1} = w_t + f(x, y) - f(x,\hat y).</math>
当 <math>x</math> 是一个实值向量，这个多分类的更新公式会退化到原始的感知机的更新公式。即 <math>y</math> 为 <math>\{0,1\}</math>中的一个，<math>f(x,y) = y x</math>。
对于某些问题，可以选择输入/输出和特征的表示。所以即使 <math>y</math> 是一个非常大或者无限集合中的元素。 <math>\mathrm{argmax}_y f(x,y) \cdot w</math> 也可以被高效地找到。
在最近的几年，感知机的训练已经成为了[[自然语言处理]]的热门话题，比如[[语音标记]]和[[语法分析]]等任务(Collins, 2002)。
==参考==
<references />
==深入阅读==
* 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. [http://psycnet.apa.org/doiLanding?doi=10.1037%2Fh0042519 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). [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=80230 Perceptron-based learning algorithms.] IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179–191.
* Mohri, Mehryar and Rostamizadeh, Afshin (2013). [https://arxiv.org/pdf/1305.0208.pdf 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.
* [https://en.wikipedia.org/wiki/Bernard_Widrow 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).
* [https://en.wikipedia.org/wiki/Michael_Collins_(computational_linguist) 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
== 外部链接 ==
* [http://www.mathworks.com/matlabcentral/fileexchange/32949-a-perceptron-learns-to-perform-a-binary-nand-function/content/PerceptronImpl.m A Perceptron implemented in MATLAB to learn binary NAND function]
* Chapter 3 [http://page.mi.fu-berlin.de/rojas/neural/chapter/K3.pdf Weighted networks - the perceptron] and chapter 4 [http://page.mi.fu-berlin.de/rojas/neural/chapter/K4.pdf Perceptron learning] of [http://page.mi.fu-berlin.de/rojas/neural/index.html.html ''Neural Networks - A Systematic Introduction''] by [https://en.wikipedia.org/wiki/Raúl_Rojas Raúl Rojas] ([https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-60505-8 ISBN|978-3-540-60505-8])
* [http://www.csulb.edu/~cwallis/artificialn/History.htm History of perceptrons]
* [http://www.cis.hut.fi/ahonkela/dippa/node41.html Mathematics of perceptrons]
* [http://www.tecnohobby.net/ppal/index.php/inteligencia-artificial/redes-neuronales/11-perceptron Explanation and Java implementation example (in Spanish)]
* [http://numerentur.org/perceptron/ Perceptron (in Spanish)]
[[category:人工智能]]
[[category:机器学习]]
本词条内容翻译自 wikipedia.org，遵守 CC3.0协议。
|keywords=感知机,感知器,集智,集智俱乐部
|description=感知机,感知器,集智,集智俱乐部
}}
在[[机器学习]]中，'''感知机'''是[[ 有监督学习]]中的一种[https://en.wikipedia.org/wiki/Binary_classification 二元分类器]（一种输入一个实值向量，判断其是否属于某一个类的函数<ref name = "T1">[https://en.wikipedia.org/wiki/Yoav_Freund Freund, Y.]; [https://en.wikipedia.org/wiki/Robert_Schapire Schapire, R. E.](1999), [https://cseweb.ucsd.edu/~yfreund/papers/LargeMarginsUsingPerceptron.pdf "Large margin classification using the perceptron algorithm" .] Report 37 (3): 277–296, [https://link.springer.com/article/10.1023%2FA%3A1007662407062 doi:10.1023/A:1007662407062].</ref>）。
这是一种[https://en.wikipedia.org/wiki/Linear_classifier 线性分类器]，即一种基于[https://en.wikipedia.org/wiki/Linear_predictor_function 线性预测函数]将一组权值与特征向量相结合的分类算法。
[[File:Kernel_Machine.svg.png|300px|thumb|right|机器学习和数据挖掘]]
==历史==
参见：[https://en.wikipedia.org/wiki/History_of_artificial_intelligence#Perceptrons_and_the_dark_age_of_connectionism 人工智能、感知机历史和联结主义的黑暗时代History of artificial intelligence § Perceptrons and the dark age of connectionism] 和[https://en.wikipedia.org/wiki/AI_winter#The_abandonment_of_connectionism_in_1969 人工智能寒冬AI winter § The abandonment of connectionism in 1969]
===来源===
感知机算法由Frank Rosenblatt<ref>Rosenblatt, Frank (1957), The Perceptron--a perceiving and recognizing automaton. Report 85-460-1, Cornell Aeronautical Laboratory.</ref>在1957年在[https://en.wikipedia.org/wiki/Calspan Cornell Aeronautical Laboratory(康奈尔航空实验室)]时所发明的一种[[人工神经网络]]，它可以被视为一种最简单形式的[[前馈神经网络]]，是一种二元[[线性分类器]]。由美国[https://en.wikipedia.org/wiki/Office_of_Naval_Research The Office of Naval Research(海军研办公室)]资助<ref name= "office">Mikel Olazaran (1996). " A Sociological Study of the Official History of the Perceptrons Controversy". Social Studies of Science. 26 (3): 611–659 [http://journals.sagepub.com/doi/10.1177/030631296026003005 doi:10.1177/030631296026003005]. [https://en.wikipedia.org/wiki/JSTOR JSTOR] [https://www.jstor.org/stable/285702 285702]. </ref>。
Frank Rosenblatt给出了相应的感知机学习算法，常用的有感知机学习、最小二乘法和梯度下降法。譬如，感知机利用梯度下降法对损失函数进行极小化，求出可将训练数据进行线性划分的分离超平面，从而求得感知机模型。
[[File:Complete neuron cell diagram zh.png|thumb|right|300px|神经细胞结构示意图]]
感知机是生物[[神经细胞]]的简单抽象。神经细胞结构大致可分为：[[树突]]、[[突触]]、[[细胞体]]及[[轴突]]。单个神经细胞可被视为一种只有两种状态的机器——激动时为『是』，而未激动时为『否』。神经细胞的状态取决于从其它的神经细胞收到的输入信号量，及突触的强度（抑制或加强）。当信号量总和超过了某个阈值时，细胞体就会激动，产生电脉冲。电脉冲沿着轴突并通过突触传递到其它神经元。为了模拟神经细胞行为，与之对应的感知机基础概念被提出，如权量（突触）、偏置（阈值）及激活函数（细胞体）。
虽然[生物神经元模型]的复杂性是通常是理解神经行为所必须的。但研究表明，类感知机的线性模型也可以产生一些在真实神经元中看到的行为。<ref>Morel, D., Singh, C. & Levy, W.B. J Comput Neurosci (2018). http://rdcu.be/FDUo</ref><ref>Cash, Sydney, and Rafael Yuste. "Linear summation of excitatory inputs by CA1 pyramidal neurons." Neuron 22.2 (1999): 383-394.APA</ref>.
感知机的目的是成为一台机器，而不是一个程序，虽然它的第一个实现是在[IBM 704]的软件中完成的，但是它后来在定制的硬件中实现为"Mark 1 感知机"。这台机器是为图像识别而设计的：它有一个由400个[ 光电池]组成的阵列，随机与“神经元”相连。权重在[电位器]中编码，权重的更新是由电动马达完成的<ref name = "update">Bishop, Christopher M. (2006), Pattern Recognition and Machine Learning. Springer.</ref>。
在1958年由美国海军组织的新闻发布会上，Rosenblatt发表了关于感知机的说明，感知机在新兴的[[人工智能]]社区中引起了激烈的讨论。根据Rosenblatt的说明，[纽约时报]报道这个感知机是一个电子计算机的胚胎，(海军)希望它能够行走、说话、写字、看见。复制自己并意识到自己的存在。<ref name= "office">Mikel Olazaran (1996). " A Sociological Study of the Official History of the Perceptrons Controversy". Social Studies of Science. 26 (3): 611–659 [http://journals.sagepub.com/doi/10.1177/030631296026003005 doi:10.1177/030631296026003005]. [https://en.wikipedia.org/wiki/JSTOR JSTOR] [https://www.jstor.org/stable/285702 285702]. </ref>
===发展===
[[File:Mark_I_perceptron.jpeg|180px|thumb|right|Mark 1 感知机是第一个感知机算法的应用。这个机器与一个使用20x20硫化镉电池的相机相连，能够生成一张400像素的图片。它主要的可视特征就是一块插板，允许不同的输入组合进行试验。右边是电位计，实现权重的更新。<ref name = "update">Bishop, Christopher M. (2006), Pattern Recognition and Machine Learning. Springer.</ref> ]]
1943年，心理学家[[沃伦·麦卡洛克]]和数理逻辑学家[[沃尔特·皮茨]]在合作的《A logical calculus of the ideas immanent in nervous activity》<ref>Warren S. McCulloch and Walter Pitts (1943), A logical calculus of the ideas immanent in nervous activity</ref>论文中提出并给出了[[人工神经网络]]的概念及人工[[神经元]]的数学模型，从而开创了人工神经网络研究的时代。1949年，心理学家[[唐纳德·赫布]]在《The Organization of Behavior》<ref>Donald Hebb (1949) The Organization of Behavior: A Neuropsychological Theory</ref>论文中描述了神经元学习法则——[[赫布型学习]]。
人工神经网络更进一步被美国神经学家弗兰克·罗森布拉特 Frank Rosenblatt 所发展。他提出了可以模拟人类感知能力的机器，并称之为『感知机』。1957年，在Cornell航空实验室中，他成功在IBM 704机上完成了感知机的仿真。两年后，他又成功实现了能够识别一些英文字母、基于感知机的[[神经计算机]]——[[Mark1]]，并于1960年6月23日，展示与众。首个有关感知机的成果，由弗兰克·罗森布拉特于1958年发表在《The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain》<ref>Rosenblatt, Frank. x. (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}}</ref>的文章里。1962年，他又出版了《Principles of Neurodynamics: Perceptrons and the theory of brain mechanisms》<ref>Rosenblatt, Frank. x. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. Spartan Books, Washington DC, 1961</ref>一书，向大众深入解释感知机的理论知识及背景假设。此书介绍了一些重要的概念及[[定理]]证明，例如感知机收敛定理。
为了『教导』感知机识别图像，弗兰克·罗森布拉特在[[Hebb学习法则]]的基础上，发展了一种迭代、试错、类似于人类学习过程的学习算法——感知机学习。除了能够识别出现较多次的字母，感知机也能对不同书写方式的字母图像进行概括和归纳。但是，由于本身的局限，感知机除了那些包含在训练集里的图像以外，不能对受干扰（半遮蔽、不同大小、平移、旋转）的字母图像进行可靠的识别。
虽然最初被认为有着良好的发展潜能，但感知机最终被证明不能处理诸多的[[模式识别]]问题。这使得神经网络的研究领域停滞了很多年直到人们认识到一个有两层及以上的[[前馈神经网络]]（也称为[[多层感知机]]），其处理能力远远大于单层的（也称为[[单层感知机]]）。单层感知机只能学习线性可分的模式。1969年Marvin Minsky和Seymour Papert出版的一本著名的著作[[《感知机》]]表明，单层感知机学习一个[[XOR]]函数是不可能的。于是人们错误的认为以及推测对于多层感知机也会有类似的结果。然而，这是不对的。因为Minsky 和 Papert 都已经知道多层的感知机可以构造XOR函数。三年后，[https://en.wikipedia.org/wiki/Stephen_Grossberg Stephen Grossberg]发布了一系列的论文，介绍了能够对[http://cns.bu.edu/Profiles/Grossberg/Gro1973StudiesAppliedMath.pdf 微分，对比增强和XOR函数进行建模的网络]。然而，Minsky 和 Papert研究成果中的误导导致了神经网络研究的兴趣下降和资金大幅减少。直到十多年以后的十九世纪八十年代，[[神经网络]]研究才又迎来了一次复兴。该书也在1987年进行修订和再版，新版本的《感知机-修订版》对原文中的一些错误进行了说明和指正。
由于弗兰克·罗森布拉特等人没能够及时推广感知机学习算法到多层神经网络上，又由于《Perceptrons》在研究领域中的巨大影响，及人们对书中论点的误解，造成了人工神经领域发展的长年停滞及低潮，直到人们认识到[[多层感知机]]没有单层感知机固有的缺陷及[[反向传播算法]]在80年代的提出，才有所恢复。1987年，书中的错误得到了校正，并更名再版为《Perceptrons - Expanded Edition》。
1964年，Aizerman等人<ref>{{cite journal |last1=Aizerman |first1=M. A. |last2=Braverman |first2=E. M. |last3=Rozonoer |first3=L. I. |year=1964 |title=Theoretical foundations of the potential function method in pattern recognition learning |url=|journal=Automation and Remote Control |volume=25 |issue=|pages=821–837 }}</ref> 就提出了[[核感知机]]算法。在Freund及Schapire（1998）使用[[核技巧]]改进感知机学习算法之后，愈来愈多的人对感知机学习算法产生兴趣。感知机算法的间距下界的保证首先由Yoav [https://en.wikipedia.org/wiki/Yoav_Freund Freund]和[https://en.wikipedia.org/wiki/Robert_Schapire Robert Schapire](1998)<ref name = "T1"></ref>在不可分的情况下给出了，最近Mehryar [https://en.wikipedia.org/wiki/Mehryar_Mohri Mohri] and Rostamizadeh (2013)推广了先前的结论并给出了新的L1下界<ref>Mohri, Mehryar and Rostamizadeh, Afshin (2013). [https://arxiv.org/pdf/1305.0208.pdf Perceptron Mistake Bounds] arXiv:1305.0208, 2013.</ref>。后来的研究表明除了二元分类，感知机也能应用在较复杂、被称为structured learning类型的任务上（Collins, 2002），又或使用在分布式计算环境中的大规模机器学习问题上（McDonald, Hall and Mann, 2011）。
==结构==
[[File:Ncell.png|thumb|300px]]
设有<math>n</math>维输入的单个感知机（如右图示），<math>{a}_1</math>至<math>{a}_n</math>为<math>n</math>维输入[[向量]]的各个分量，<math>{w}_1</math>至<math>{w}_n</math>为各个输入分量连接到感知机的权量（或称权值），<math>{b}</math>为偏置，<math>f(.)</math>为激活函数（又曰激励函数或传递函数），<math>t</math>为标量输出。输出<math>t</math>的数学描述为：
:<math>
t = f(\sum_{i=1}^{n}{{w}_i {x}_i + b})
= f(\mathbf{w}^T \mathbf{x})
\qquad\qquad(1)</math>
其中<math>\mathbf{w} = [w_1 \; w_2 \; ... \; w_n \; b]^T</math>，<math>\mathbf{x} = [x_1 \; x_2 \; ... \; x_n \; 1]^T</math>及<math>f(x)</math>为[[反对称]]的[[符号函数]]，其定义为：
:<math>
f(n) = \begin{cases}+1 & \text{if }n \geq 0\\-1 & \text{otherwise}\end{cases}
\qquad\qquad(2)</math>
从式(1)可知，偏置被引申为权量，而对应的输入值为<math>1</math>。故，一感知机的输出行为是求得输入向量与权向量的[[内积]]后，经一个激活函数所得一个标量结果。
设输入向量与权向量的内积为零，可得出<math>(n+1)</math>维的超平面。平面的[[法向量]]为<math>\mathbf{w}</math>，并经过<math>(n+1)</math>维输入空间的原点。法向量指向的输入空间，其输出值为<math>+1</math>，而与法向量反向的输入空间，其输出值则为<math>-1</math>。故可知这个超平面定义了[[决策边界]]，并把输入空间划分为二。
==准则函数==
设一训练集为<math>D = \{(\mathbf{p}_1, \; t_1), \;\dots\;, (\mathbf{p}_m, \; t_m)\}</math>，其中<math>\mathbf{p}_i</math>表示输入，而<math>{t}_i</math>是对应的目标输出。由于符号函数的[[不连续性]]，如果采用标准的[[均方误差]]，所得[[误差函数]]必然是不连续的，因而基于[[梯度]]的学习算法也就不能被使用。为此，Rosenblatt提出了感知机准则函数：
:<math>
E(\mathbf{w}) = -\sum_{\mathbf{p}_i \in M}^{}{(\mathbf{w}^T\mathbf{p}_i) \; {t}_i}
\qquad\qquad(3)</math>
其中<math>M</math>是被当前<math>\mathbf{w}</math>错误分类的的输入向量集合。当<math>\mathbf{w}^T\mathbf{p}_i \geq 0</math>时，<math>{t}_i</math>为<math>-1</math>，而当<math>\mathbf{w}^T\mathbf{p}_i < 0</math>时，<math>{t}_i</math>为<math>+1</math>。故，误差函数<math>E(\mathbf{w})</math>是一组正数的和，又或当训练集里所有输入都被正确分类时，等于零。
== 定义 ==
在现代，感知机是一种二分类学习算法：用一个函数将输入 <math>x</math>（一个实值向量）映射到输出值<math>f(x)</math>（一个二元值）：
:<math>
f(x) = \begin{cases}1 & \text{if }\ \mathbf{w} \cdot \mathbf{x} + b > 0\\0 & \text{otherwise}\end{cases}
</math>
这里的 <math>w</math> 是一个实值构成的权重向量，<math>\mathbf{w} \cdot \mathbf{x}</math>是一个[https://en.wikipedia.org/wiki/Dot_product 点积]操作即 <math>\sum_{i=1}^m w_i x_i</math>， <math>m</math> 是感知机输入值的个数，其中 <math>b</math> 是偏置项。偏置项决定了决策边界相对原点的偏移量，且不依赖于任何输入值。
在二分类问题中，<math>f(x)</math> 的值（0或1）用来将 <math>x</math> 分为正例或者负例。如果 <math>b</math> 是负的，那么输入和权重的结合生成的正值必须比 <math>|b|</math>大，从而使得分类的神经元大于0阈值。从空间上来说，偏置项改变了[[决策边界]]的位置（而不是方向）。如果训练集不是[[线性可分]]的，那么感知机学习算法就不会停止。如果向量不是[[线性可分]]的，那么学习将永远不会收敛到所有向量都分类正确的结果。感知机算法的局限性的最著名的例子就是线性不可分的情况，比如XOR问题。对于所有二分类函数的[[决策边界]]解的空间和学习表现的研究都在这个参考中<ref name = "T9">Liou, D.-R.; Liou, J.-W.; Liou, C.-Y. (2013). Learning Behaviors of Perceptron. iConcept Press. [https://en.wikipedia.org/wiki/International_Standard_Book_Number ISBN]</ref>。
在神经网络的场景中，感知机是一个以[[单位阶跃函数]]为激活函数的[[人工神经元]]。感知机算法也被称为'''单层感知机'''。这个术语用于区分[[多层感知机]]即一个更加复杂的神经网络。作为一个线性分类器，单层感知机是一类最简单的[[前馈神经网络]]。
==学习算法==
下面是一个介绍单层感知机学习算法的例子。对于存在隐层的多层感知机，必须使用诸如[[反向传播]]等更加复杂的算法。尽管下面的方法也是可行，但如果在函数是非线性且可微的情况下，那么可以使用[[链式法则]]等方法解决问题。
当多个感知机在一个人工神经网络中组合应用时，每个输出神经元都独立于其他神经元运行。因此，学习的每一个输出都可以单独考虑。[[File:Perceptron example.svg.png|500px|thumb |right|一副图展示了感知机算法在新的训练数据加入时是如何更新它的线性边界的。]]
=== 定义 ===
我们先定义这些变量:
*<math>y = f(\mathbf{z}) </math> 表示感知对于某个输入向量 <math>\mathbf{z}</math> 的输出。
*<math>D = \{(x_1,d_1),\dots,(x_s,d_s)\} </math> 训练集 <math>s</math> 的样本， 其中:
**<math>x_j</math> 是 <math>n</math>维 输入向量。
** <math>d_j </math> 是感知对应输入的期望输出值。
我们用如下方式表示特征值：
*<math>x_{j,i} </math> 是输入向量的第 j 个样本的第 <math>i</math> 个特征。
*<math>x_{j,0} = 1 </math>.
权重的表示：
*<math>w_i </math> 是权重向量的第 <math>i</math> 个值，这是为了表示和第 <math>i</math> 个输入特征相乘。
*因为 <math>x_{j,0} = 1 </math>， <math>w_0 </math> 实际上表示的是偏置项也就是常量 <math>b</math>。
为了表示每一轮独立的 <math>\mathbf{w}</math> ，这里使用如下符号：
*<math>w_i(t) </math> 是第 <math>t</math> 轮训练中的权重 <math>i</math> 。
不像[[Logistic回归]]这样的线性分类算法，在感知机学习算法中没有''学习速率 。''这是因为通过乘以常数的更新只是放缩了权重，但不会改变预测结果的符号<ref name = "T10"> Genevieve B. Orr. [https://www.willamette.edu/~gorr/classes/cs449/Classification/perceptron.html "The Perceptron"]. Willamette University. Retrieved 3 March 2017.</ref>。
[[Image:Perceptron.svg.png|300px|right|thumb|居中|500px|适当的权重被应用到输入，然后产生加权和传递给一个生成输出o的函数。]]
=== 步骤===
# 初始化权重与阈值。权重初始化为全0或者一个很小的随机值。在下面的例子中我们使用0作为初始化值。
# 对于数据集 <math>D </math> 中每一个样本 j ，对输入 <math>x_j </math> 执行以下的步骤，并得到期望的输出 <math>d_j </math>：
## 计算以下的输出：<math>\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}</math>
## 更新权重：<math>w_i(t+1) = w_i(t) + r\cdot(d_j - y_j(t)) x_{j,i}, 0 < i < n</math>，其中 <math>r</math>是学习速率。
# 对于[https://en.wikipedia.org/wiki/Offline_learning 离线学习]，第二步需要重复直到迭代误差<math>\frac{1}{s} \sum_{j=1}^s |d_j - y_j(t)| </math>小于一个用户定于的误差阈值<math>\gamma</math>，或者预定于的迭代轮数已经完成，这里的 <math>s</math> 是是样本集的大小。
这个算法在2.1和2.2步骤后更新了权重。这些权重会立即反应到训练数据中，并且随后进行更新，并不是等所有步骤结束后才更新的。
=== 简单实现与演示 ===
摘自李航博士的《统计学习方法》，对于训练数据集，其中正例点是<math>x_1=(3,3)T</math>，<math>x_2=(4,3)T</math>，负例点为<math>x_3=(1,1)T</math>，用感知机学习算法的原始形式求感知机模型<math>f(x)=w·x+b</math>。这里<math>w=(w(1),w(2))T，x=(x(1),x(2))T</math>
<syntaxhighlight lang="python">
import numpy as np
training_set = [[3,3],[4,3],[1,1]]
Y = [1,1,-1]
w = [0,0]
b = 0
n = 1
#check给出w，b，找到一个此时的误分点，如果没有，说明算法收敛
def check(w,b):
C = []
for e in training_set:
x1 = np.array(e).reshape((-1,1))
w1 = np.array(w)
c = np.dot(w1,x1)
y = Y[training_set.index(e)]
if y*(c+b)<=0:
C.append(e[0])
C.append(e[1])
break
else:
continue
return C
def update(C,w,b):
D = []
y = Y[training_set.index(C)]
x = np.array(C)
D.append(w + n*y*x)
D.append(b + n*y)
return D
while True:
C = check(w, b)
if len(C)==0:
break
else:
w = update(C,w,b)[0]
b = update(C,w,b)[1]
print('算法已经收敛')
print('y = sign(%d*x1 + %d*x2 + %d)'%(w[0],w[1],b))
</syntaxhighlight>
得到结果
<syntaxhighlight lang="python">
算法已经收敛
y = sign(1*x1 + 1*x2 + -3)
</syntaxhighlight>
===收敛性===
感知机是一种[[线性分类器]]，因此如果数据集 <math>D</math> 是非[https://en.wikipedia.org/wiki/Linearly_separable 线性可分]的话，那么它永远无法让所以的输入向量分类正确，即正负的样本不能被一个线性超平面所分割。标准算法在这种情况下时是无法逐渐达到一个近似解的，并导致学习过程会直接失效。所以，如果我们不能事先知道数据集是否是线性可分的，则应该使用下面的变种。
如果训练集是线性可分的，那么感知机可以确保其收敛性。此外，感知机在训练过程中调整自身权重的次数是有上限的。
假设分属于两个类的输入向量可以被一个线性超平面分割成两个类，且样本到超平面的间距为 <math>\gamma </math>。即存在一个权重向量 <math>\mathbf{w}</math> 且 <math>||\mathbf{w}||=1</math>，以及一个偏置项 <math>b</math> 使得对于所有的 <math>d_j=1</math> 对应 j 有 <math>\mathbf{w}\cdot\mathbf{x}_j > \gamma </math> 和 <math> d_j=0</math>对应的 j 有 <math>\mathbf{w}\cdot\mathbf{x}_j < -\gamma </math> 。且如果引入 <math>R</math> 表示输入向量最大的维度。Novikoff (1962)证明了感知机可以在 <math>O(R^2 \gamma^2)</math>轮迭代中完成收敛。证证明的思路是权重向量可以被有负[https://en.wikipedia.org/wiki/Dot_product 点积]的约束值在一个方向上修正，因此可以被 <math>Osqrt{t}</math> 的下界约束，这里的 <math>t</math> 是权重向量更新的次数。然而，它也可以被 <math> O(t)</math> 的上界约束。因为如果存在一个未知的满足条件的权重向量，那么在这个方向上每一次权重向量的改变都只取决于输入向量。
当感知机算法在训练集线性可分的条件下会在某个解中达到收敛，而且会在多个质量不同且满足条件的解中任意选一个。<ref>Bishop, Christopher M. "Chapter 4. Linear Models for Classification". Pattern Recognition and Machine Learning. Springer Science+Business Media, LLC. p. 194. ISBN [https://en.wikipedia.org/wiki/Special:BookSources/978-0387-31073-2 978-0387-31073-2].</ref>''最佳稳定性感知机''现在一般称为[[SVM支持向量机]]，就是设计用来解决这个问题的。<ref name="KrauthMezard87">W. Krauth and M. Mezard. Learning algorithms with optimal stability in neural networks. J. of Physics A: Math. Gen. 20: L745-L752 (1987)</ref>
[[File:Perceptron cant choose.svg.png|thumb|300px|两种种类的点和无限多的可以分割它们的线性边界。即使这两条线性边界是直角相对的，感知机算法也无法从其中选择。]]
== 变种 ==
渐进的pocket算法(Gallant, 1990)通过保留最近的最佳解解决了感知机学习过程中的稳定性问题。pocket算法接下来返回保存最佳的解而不是迭代的最后一个解。它也可以被用于线性不可分的数据集，那么感知机的学习目的就是找一个使得误分类数量最小的解。然而这些解是完全随机出现的，因此pocket算法不能在学习的过程中最终得到这些解也不能保证在给定的迭代次数中找到这些解。
Maxover算法 (Wendemuth, 1995)<ref>A. Wendemuth. [http://www.iikt.ovgu.de/iesk_media/Downloads/ks/publications/papers/1995/wendemuth1995_learning_unlearnable-p-1452.pdf Learning the Unlearnable]. J. of Physics A: Math. Gen. 28: 5423-5436 (1995)</ref> 在某种意义上是[[稳健的(robust)]]，因为无论是否事先知道数据集线性可分，它都会达到收敛。在线性可分的情况下，即使具有最佳的稳定性（即类之间达到[[最大间距]]）也能很好解决训练问题。对于线性不可分的数据集，它会返回一个少量误分类的解。在所有的情况下，该算法在学习过程中会逐渐接近解而不会存储先前的状态，也不会随机跳跃。收敛性是指线性可分数据集的全局最优解和非线性可分数据的局部最优解。
投票感知机 (Freund and Schapire, 1999)，是一种使用多权重的感知机的变种。每当一个例子被错误的分类时，算法会启动一个新的感知机，然后使用最后的感知机的权重作为现在感知机的初始化权重。每次分类错误感知机都会被给予另外的权重直到所以样本分类正确。最后得到所有感知机加权投票的结果。
在线性可分问题中，感知机的训练目标在于在样本之间找到最大的间距分割两个类。所谓的最优稳定性感知机可以通过迭代训练和优化策略来确定，比如Min-Over算法 (Krauth and Mezard, 1987)<ref name="KrauthMezard87" /> 或者AdaTron算法 (Anlauf and Biehl, 1989))。<ref>J.K. Anlauf and M. Biehl. The AdaTron: an Adaptive Perceptron algorithm. Europhysics Letters 10: 687-692 (1989)</ref> AdaTron利用了问题对应的二次优化是凸的这一条件。最佳稳定性感知机加上[[核方法]]，这是[[SVM支持向量机]]概念的基础。
<math>\alpha</math>-感知机使用了带有阈值输出单元的固定随机权重的预处理层。这使得感知机能够通过投影[[二元空间]]对[[类似]]的模式进行分类。实际上对于一个维度足够高的的投影空间，模式就会变得线性可分了。
解决线性不可分问题的另一种方法是使用高阶的网络(sigma-pi unit)。在这种类型的网络中，每个输入向量的元素都会使用复杂输入(二阶)组合来拓展到高纬。这可以使其拓展到一个n阶网络。
但是，我们应该牢记，最好的分类器不需要完美分类所有训练数据。实际上，如果我们有先验性的约束，即数据据来自于高斯分布。那么输入空间的线性解是最佳的，而非线性解是[[过拟合]]的。
其他的线性分类算法包括了[[Winnow]]，[[SVM支持向量机]]，和[[Logistic回归]]。
== 多分类感知机 ==
类似于其他训练线性分类器的技巧，感知机可以很自然地泛化成[[多分类]]分类器。这里的输入 <math>x</math> 和输出 <math>y</math> 是从任意集合中得到的。特征表示函数f(x,y)将每一个可能的输入/输出对映射到一个有限维的实值特征向量上。与之前相同，特征向量乘以一个权重向量 <math>w</math>，但是现在该结果的值将被用于选择许多可能输出结果的其中之一：
:<math>\hat y = \operatorname{argmax}_y f(x,y) \cdot w.</math>
同样通过在样本的迭代来完成学习，预测每一个输出的结果，当预测和实际结果匹配时不更新权重，反之则更新。更新方式就是：
:<math> w_{t+1} = w_t + f(x, y) - f(x,\hat y).</math>
当 <math>x</math> 是一个实值向量，这个多分类的更新公式会退化到原始的感知机的更新公式。即 <math>y</math> 为 <math>\{0,1\}</math>中的一个，<math>f(x,y) = y x</math>。
对于某些问题，可以选择输入/输出和特征的表示。所以即使 <math>y</math> 是一个非常大或者无限集合中的元素。 <math>\mathrm{argmax}_y f(x,y) \cdot w</math> 也可以被高效地找到。
在最近的几年，感知机的训练已经成为了[[自然语言处理]]的热门话题，比如[[语音标记]]和[[语法分析]]等任务(Collins, 2002)。
==参考==
<references />
==深入阅读==
* 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. [http://psycnet.apa.org/doiLanding?doi=10.1037%2Fh0042519 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). [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=80230 Perceptron-based learning algorithms.] IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179–191.
* Mohri, Mehryar and Rostamizadeh, Afshin (2013). [https://arxiv.org/pdf/1305.0208.pdf 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.
* [https://en.wikipedia.org/wiki/Bernard_Widrow 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).
* [https://en.wikipedia.org/wiki/Michael_Collins_(computational_linguist) 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
== 外部链接 ==
* [http://www.mathworks.com/matlabcentral/fileexchange/32949-a-perceptron-learns-to-perform-a-binary-nand-function/content/PerceptronImpl.m A Perceptron implemented in MATLAB to learn binary NAND function]
* Chapter 3 [http://page.mi.fu-berlin.de/rojas/neural/chapter/K3.pdf Weighted networks - the perceptron] and chapter 4 [http://page.mi.fu-berlin.de/rojas/neural/chapter/K4.pdf Perceptron learning] of [http://page.mi.fu-berlin.de/rojas/neural/index.html.html ''Neural Networks - A Systematic Introduction''] by [https://en.wikipedia.org/wiki/Raúl_Rojas Raúl Rojas] ([https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-60505-8 ISBN|978-3-540-60505-8])
* [http://www.csulb.edu/~cwallis/artificialn/History.htm History of perceptrons]
* [http://www.cis.hut.fi/ahonkela/dippa/node41.html Mathematics of perceptrons]
* [http://www.tecnohobby.net/ppal/index.php/inteligencia-artificial/redes-neuronales/11-perceptron Explanation and Java implementation example (in Spanish)]
* [http://numerentur.org/perceptron/ Perceptron (in Spanish)]
[[category:人工智能]]
[[category:机器学习]]
本词条内容翻译自 wikipedia.org，遵守 CC3.0协议。