感知机
感知机是一种用来处理二分类的经典线性模型。其原理朴素直观，引入了学习概念，是神经网络的基本构成单元之一。
感知机的定义
假设输入空间为
X
∈
R
n
X\in \Bbb R^n
X∈Rn，输出空间为
Y
=
{
+
1
,
?
1
}
Y=\{+1,-1\}
Y={+1,?1}。输入的
x
∈
X
x\in X
x∈X表示示例中的特征向量，对应于输入空间中的某一点；输出
y
∈
Y
y\in Y
y∈Y表示实例的类别。则称公式 (1) 这种由输入空间到输出空间的函数为感知机模型。
f
(
x
)
=
s
i
g
n
(
w
?
x
+
b
)
(1)
f(x) =sign(w\cdot x+b) \tag{1}
f(x)=sign(w?x+b)(1)
其中，
w
w
w和
b
b
b为感知机模型的参数，
w
∈
R
n
w\in\Bbb R^n
w∈Rn称为权值或权值向量，
b
∈
R
b\in \Bbb R
b∈R称为偏置，
w
?
x
w\cdot x
w?x表示
w
w
w和
x
x
x的内积，
s
i
g
n
sign
sign为符号函数，即：
s
i
g
n
(
x
)
=
{
+
1
,
x
≥
0
?
1
,
x
<
0
(2)
sign(x)=\begin{cases} +1,&x\ge 0\\ -1,&x\lt 0 \end{cases} \tag{2}
sign(x)={+1,?1,?x≥0x<0?(2)
感知机的几何含义
对于给定的样本集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
?
?
,
(
x
N
,
y
N
)
}
T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)}，其中对式 (1) 中出现的线性方程
w
?
x
+
b
=
0
w\cdot x+b=0
w?x+b=0对应于特征空间
R
n
\Bbb R^n
Rn的一个超平面
S
S
S，其中
w
w
w是
S
S
S的法向量，
b
b
b是
S
S
S的截距。若该特征空间线性可分，则该超平面可以恰好将特征空间分为两部分（如图1所示）。位于两部分的特征向量分别对应正负类样本。此时，该超平面𝑆又被称为分离超平面。
感知机的损失函数
综上，感知机的主要目标是确定出一个可以将数据集的正样本和负样本完全分开的超平面，而超平面则主要通过训练时不断调整参数 w w w和 b b b的值来确定。至于 w w w和 b b b则可以通过定义关于 w w w和 b b b的损失函数并将损失函数极小化来得到。
当使用误分类点的个数来作为损失函数时，该损失函数不是关于
w
w
w和
b
b
b的连续可导函数，实际操作时不易优化，因此可以使用所有误分类点到超平面
S
S
S的总距离来作为损失函数。输入空间
R
n
\Bbb R^n
Rn中任意一点
x
0
x_0
x0?到超平面
S
S
S的距离为：
1
∣
∣
w
∣
∣
∣
w
?
x
+
b
∣
(3)
\frac{1}{||w||}|w\cdot x+b| \tag{3}
∣∣w∣∣1?∣w?x+b∣(3)
当样本标签
y
i
y_i
yi?为
+
1
+1
+1时，
w
?
x
i
+
b
>
0
w\cdot x_i+b\gt 0
w?xi?+b>0表示分类正确；当样本标签
y
i
y_i
yi?为
?
1
?1
?1时，
w
?
x
i
+
b
<
0
w\cdot x_i+b\lt 0
w?xi?+b<0表示分类正确，因此将两式整合如下：
{
y
i
(
w
?
x
i
+
b
)
>
0
,
分类正确
y
i
(
w
?
x
i
+
b
)
<
0
,
分类错误
(4)
\begin{cases} y_i(w\cdot x_i+b)\gt0,&\text{分类正确}\\ y_i(w\cdot x_i+b)\lt0,&\text{分类错误} \end{cases} \tag{4}
{yi?(w?xi?+b)>0,yi?(w?xi?+b)<0,?分类正确分类错误?(4)
因此此时误分类点
x
i
x_i
xi?到超平面
S
S
S的距离是：
?
1
∣
∣
w
∣
∣
y
i
(
w
?
x
i
+
b
)
(5)
-\frac{1}{||w||}y_i(w\cdot x_i+b) \tag{5}
?∣∣w∣∣1?yi?(w?xi?+b)(5)
不妨设超平面
S
S
S的误分类点集合为
M
M
M，那么全体误分类点到超平面
S
S
S的总距离为：
?
1
∣
∣
w
∣
∣
∑
x
i
∈
M
y
i
(
w
?
x
i
+
b
)
(6)
-\frac{1}{||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b)\tag{6}
?∣∣w∣∣1?xi?∈M∑?yi?(w?xi?+b)(6)
不再考虑
1
∣
∣
w
∣
∣
\frac{1}{||w||}
∣∣w∣∣1?，就得到感知机学习训练时的损失函数
L
(
w
,
b
)
L(w,b)
L(w,b)：
L
(
w
,
b
)
=
?
∑
x
i
∈
M
y
i
(
w
?
x
i
+
b
)
(7)
L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b) \tag{7}
L(w,b)=?xi?∈M∑?yi?(w?xi?+b)(7)
感知机的学习算法
已知感知机的学习目标是得到使损失函数值最小时的参数
w
w
w和
b
b
b，即：
min
?
w
,
b
L
(
w
,
b
)
=
?
∑
x
i
∈
M
y
i
(
w
?
x
i
+
b
)
(8)
\min_{w,b}L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b) \tag{8}
w,bmin?L(w,b)=?xi?∈M∑?yi?(w?xi?+b)(8)
由于
L
(
w
,
b
)
L(w,b)
L(w,b)是一个自变量为
w
w
w和
b
b
b的简单线性函数，且由于损失函数中只有误分类点参与了计算，因此不需要对所有的点都求导。故感知机所采用的下降方法是随机梯度下降（Stochastic Gradient Descent,SGD）。
在随机梯度下降法中，每次迭代只随机选取一个样本，如果该样本在当前超平面下分类正确，则不进行操作；如果分类错误，则对这个误分类样本
x
i
x_i
xi?求梯度：
?
w
=
?
?
y
i
(
w
?
x
i
+
b
)
?
w
=
?
y
i
x
i
(9)
\nabla w = \frac{\partial-y_i(w\cdot x_i+b)}{\partial w}=-y_ix_i \tag{9}
?w=?w??yi?(w?xi?+b)?=?yi?xi?(9)
?
b
=
?
?
y
i
(
w
?
x
i
+
b
)
?
b
=
?
y
i
x
i
(10)
\nabla b=\frac{\partial-y_i(w\cdot x_i+b)}{\partial b}=-y_ix_i \tag{10}
?b=?b??yi?(w?xi?+b)?=?yi?xi?(10)
利用求解的梯度对
w
w
w和
b
b
b进行更新，得：
w
←
w
+
η
y
i
x
i
(11)
w\leftarrow w+\eta y_ix_i \tag{11}
w←w+ηyi?xi?(11)
b
←
w
+
η
y
i
(12)
b \leftarrow w+\eta y_i \tag{12}
b←w+ηyi?(12)
其中， η \eta η为学习率，代表学习速度的快慢，一般取 0 ～ 1 0～1 0～1之间。再由Novikoff定理可知，经过有限次迭代后可以使得损失函数尽可能地小，直到为零，此时即可得到 w w w和 b b b的值，进而得到超平面 S S S。
感知机模型的缺陷与改进
感知机模型在进行二分类问题时简单直观且计算简单，但其具有很大的局限性，即只能处理线性可分问题。以逻辑学中的异或问题为例，对于输入 { A , B } ? \{A,B\}? {A,B}?，当 A = B ? A=B? A=B?时输出为 1 ? 1? 1?，当 A ≠ B ? A\ne B? A?=B?时输出为 0 ? 0? 0?。以 0 , 0 ? {0,0}? 0,0?、 0 , 0 ? {0,0}? 0,0?、 1 , 0 ? {1,0}? 1,0?， 1 , 1 ? {1,1}? 1,1?为例，输出结果如表1所示：
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
异或问题看似非常简单，但其为非线性可分问题，因此对于感知机模型来说，该问题比较复杂。将表1在二维坐标上展示结果如图2所示。
由图2所示，由于去值相同的点分别占据了对角，因此无论如何都无法找到一个直线（超平面）使两类分开。当然，倘若使用两个感知机模型问题似乎就迎刃而解了。如图2所示，两个感知机模型对应的分割超平面就是图中的两条实线。设感知机1为 f 1 ( x ) = s i g n ( w 1 ? x + b 1 ) f_1 (x)=sign(w_1?x+b_1) f1?(x)=sign(w1??x+b1?)；感知机2为 f 2 ( x ) = s i g n ( w 2 ? x + b 2 ) f_2 (x)=sign(w_2?x+b_2) f2?(x)=sign(w2??x+b2?)。并令感知机1对应的超平面右下方和感知机2对应的超平面左上方输出为 + 1 +1 +1；感知机1对应的超平面右上方和感知机2对应的超平面右下方输出为 ? 1 -1 ?1。
此时继续添加感知机3以整合感知机1与感知机2的输出结果，不妨设感知机3为 f 3 ( x 3 ) = s i g n ( w 3 ? x 3 + b 3 ) f_3 (x_3)=sign(w_3?x_3+b_3) f3?(x3?)=sign(w3??x3?+b3?)。其中， w 3 = [ 1 , 1 ] w_3=[1,1] w3?=[1,1]， x 3 = [ f 1 ( x ) , f 2 ( x ) ] x_3=[f_1 (x),f_2 (x)] x3?=[f1?(x),f2?(x)]， b 3 = ? 1 b_3=-1 b3?=?1。
显然，当感知机3输出为
+
1
+1
+1时，表示该样本属于正类；输出为
?
1
-1
?1时，表示该样本属于负类。这三个感知机的运行架构图如图3所示：
实际上，异或问题只需两个感知机叠加值来判别就能解决，感知机3只是为了统一输出而添加的。推广来看，当问题更加复杂的时候，可以考虑用更多的感知机模型进行组合堆叠。虽然一个感知机能力有限，但是一旦感知机进行多层堆叠之后，其能力就会大大增强。实际应用中，为了更好的解决线性不可分的问题，感知机模型走向了多层化的道路，由此成为了各种神经网络的基石。这种每层神经元与下一层神经元全部相互连接，且不存在同层或跨层连接的神经网络结构被称为多层感知机或多层前馈神经网络。