感知机模型是一个二分类的模型，它通过形如
y
=
w
x
+
b
y=wx+b
y=wx+b的式子将实例x转换为类别，取+1和-1表示，从而将实例进行划分。它是简单并且容易实现的一个模型。 感知机模型主要用来将平面上线性可分的数据集进行划分，对于线性不可分的数据集，感知机无法收敛。 感知机模型的输入输出由以下函数进行映射，其中w是n维空间的一个向量，b是偏置，sign是符号函数。
f
(
x
)
=
s
i
g
n
(
w
x
+
b
)
.
.
.
.
.
.
.
.
.
.
(
1
)
s
i
g
n
(
x
)
=
{
+
1
x
≥
0
−
1
x
<
0
.
.
.
.
.
.
.
.
.
.
(
2
)
f(x)=sign(wx+b)..........(1) \\ sign(x)= \begin{cases} +1 & x \ge 0 \\ -1 & x \lt 0 \end{cases}..........(2)
f(x)=sign(wx+b)..........(1)sign(x)={+1−1x≥0x<0..........(2) 对于感知机的学习策略，我们可以考虑当一个实例点被误分类，则调整w，b的值 ，使分离超平面向该误分类点的一侧移动，减少该误分类点与超平面的距离，直至超平面越过该误分类点使其正确分类。于是有感知机的损失函数
L
(
w
,
b
)
=
−
∑
x
i
∈
M
y
i
(
w
⋅
x
i
+
b
)
.
.
.
.
.
.
.
.
.
.
(
3
)
L(w,b)=-\sum_{x_i \in M}y_i(w·x_i+b)..........(3)
L(w,b)=−xi∈M∑yi(w⋅xi+b)..........(3) 其中M为误分类点的集合。可以发现
−
y
i
(
w
⋅
x
i
+
b
)
-y_i(w·x_i+b)
−yi(w⋅xi+b)恒为正数，当所有点都完全分类正确时，损失函数为0。对于一个误分类的样本点来说，式子(3)是w，b的连续可导函数。所以采用随机梯度下降法进行学习。感知机学习算法的原始形式如下：
定义初始的
w
0
,
b
0
w_0,b_0
w0,b0。
扫描训练集，若
y
i
(
w
⋅
x
i
+
b
)
≤
0
y_i(w·x_i+b) \le 0
yi(w⋅xi+b)≤0，则更新
w
=
w
+
η
y
i
x
i
,
b
=
b
+
η
y
i
w=w+\eta y_ix_i,b=b+\eta y_i
w=w+ηyixi,b=b+ηyi
重复2，直至不存在误分类点。
c不同的初始值，或者误分类点的选取顺序不同，都可能使得最后得到的w和b不同。
2. 收敛性证明（Novikoff定理）
我们如何保证在算法原始模型中，经过有限次的迭代后一定会收敛呢？下面我们进行收敛性的证明。首先令
w
^
x
^
=
w
⋅
x
+
b
\hat w \hat x=w·x+b
w^x^=w⋅x+b。假设最终得到的超平面
w
^
o
p
t
⋅
x
^
=
w
o
p
t
⋅
x
+
b
o
p
t
=
0
\hat w_{opt}·\hat x=w_{opt}·x+b_{opt}=0
w^opt⋅x^=wopt⋅x+bopt=0，使
∣
∣
w
^
o
p
t
∣
∣
=
1
||\hat w_{opt}||=1
∣∣w^opt∣∣=1，因此对于所有的样本i，有
y
i
(
w
^
o
p
t
⋅
x
^
i
)
>
0
y_i(\hat w_{opt}·\hat x_i) \gt 0
yi(w^opt⋅x^i)>0 存在
γ
=
min
i
{
y
i
(
w
o
p
t
⋅
x
i
+
b
o
p
t
)
}
\gamma =\min_{i}\{y_i(w_{opt}·x_i+b_{opt})\}
γ=imin{yi(wopt⋅xi+bopt)} 使得
y
i
(
w
^
o
p
t
⋅
x
^
i
)
≥
γ
.
.
.
.
.
.
.
.
.
.
(
4
)
y_i(\hat w_{opt}·\hat x_i) \ge \gamma..........(4)
yi(w^opt⋅x^i)≥γ..........(4) 选择初值
w
^
0
\hat w_0
w^0，令
w
^
k
−
1
\hat w_{k-1}
w^k−1是第k个误分类实例之前的权重向量，则第k个误分类实例的条件是
y
i
(
w
^
k
−
1
⋅
x
^
i
)
=
y
i
(
w
k
−
1
⋅
x
i
+
b
k
−
1
)
≤
0.........
(
5
)
y_i(\hat w_{k-1}·\hat x_i)=y_i(w_{k-1}·x_i+b_{k-1}) \le 0.........(5)
yi(w^k−1⋅x^i)=yi(wk−1⋅xi+bk−1)≤0.........(5) 假如样本
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi)被误分类，则更新权重和偏置
w
k
=
w
k
−
1
+
η
y
i
x
i
b
k
=
b
k
−
1
+
η
y
i
w_k=w_{k-1}+\eta y_ix_i \\ b_k=b_{k-1}+\eta y_i
wk=wk−1+ηyixibk=bk−1+ηyi 即
w
^
k
=
w
^
k
−
1
+
η
y
i
x
^
i
.
.
.
.
.
.
.
.
.
.
(
6
)
\hat w_{k}=\hat w_{k-1}+\eta y_i\hat x_i..........(6)
w^k=w^k−1+ηyix^i..........(6) 由式子4和6得
w
^
k
w
^
o
p
t
=
w
^
k
−
1
⋅
w
^
o
p
t
+
η
y
i
w
^
o
p
t
⋅
x
^
i
≥
w
^
k
−
1
⋅
w
^
o
p
t
+
η
γ
.
.
.
.
.
.
.
.
.
.
(
7
)
\begin{aligned} \hat w_k \hat w_{opt} &=\hat w_{k-1}· \hat w_{opt} + \eta y_i \hat w_{opt} · \hat x_i \\ &\ge \hat w_{k-1}· \hat w_{opt} +\eta \gamma..........(7) \end{aligned}
w^kw^opt=w^k−1⋅w^opt+ηyiw^opt⋅x^i≥w^k−1⋅w^opt+ηγ..........(7) 因此可得
w
^
k
\hat w_k
w^k和
w
^
k
−
1
\hat w_{k-1}
w^k−1之间的递推式，从而有
w
^
k
w
^
o
p
t
≥
w
^
k
−
1
⋅
w
^
o
p
t
+
η
γ
≥
w
^
k
−
2
⋅
w
^
o
p
t
+
2
η
γ
≥
.
.
.
≥
k
η
γ
.
.
.
.
.
.
.
.
.
.
(
8
)
\hat w_k \hat w_{opt} \ge \hat w_{k-1}· \hat w_{opt} +\eta \gamma \ge \hat w_{k-2}· \hat w_{opt} +2\eta \gamma \ge ... \ge k\eta \gamma..........(8)
w^kw^opt≥w^k−1⋅w^opt+ηγ≥w^k−2⋅w^opt+2ηγ≥...≥kηγ..........(8) 令
R
=
max
1
≤
i
≤
N
∣
∣
x
i
∣
∣
R=\max\limits_{1 \le i \le N}||x_i||
R=1≤i≤Nmax∣∣xi∣∣，又由式子5和6推得
∣
∣
w
^
k
∣
∣
2
=
∣
∣
w
^
k
−
1
∣
∣
2
+
2
η
y
i
w
^
k
−
1
⋅
x
^
i
+
η
2
∣
∣
x
^
i
∣
∣
2
≤
∣
∣
w
^
k
−
1
∣
∣
2
+
η
2
∣
∣
x
^
i
∣
∣
2
≤
∣
∣
w
^
k
−
1
∣
∣
2
+
η
2
R
2
≤
∣
∣
w
^
k
−
2
∣
∣
2
+
2
η
2
R
2
≤
.
.
.
≤
k
η
2
R
2
.
.
.
.
.
.
.
.
.
.
(
9
)
\begin{aligned} ||\hat w_k||^2 &=||\hat w_{k-1}||^2 + 2\eta y_i \hat w_{k-1}·\hat x_i+\eta ^2 ||\hat x_i||^2 \\ &\le ||\hat w_{k-1}||^2 +\eta ^2 ||\hat x_i||^2 \\ &\le ||\hat w_{k-1}||^2 +\eta ^2 R^2 \\ &\le ||\hat w_{k-2}||^2 +2\eta ^2 R^2 \\ &\le ... \\ &\le k\eta ^2 R^2 ..........(9) \end{aligned}
∣∣w^k∣∣2=∣∣w^k−1∣∣2+2ηyiw^k−1⋅x^i+η2∣∣x^i∣∣2≤∣∣w^k−1∣∣2+η2∣∣x^i∣∣2≤∣∣w^k−1∣∣2+η2R2≤∣∣w^k−2∣∣2+2η2R2≤...≤kη2R2..........(9) 结合8和9，得到
k
η
γ
≤
w
^
k
⋅
w
^
o
p
t
≤
∣
∣
w
^
k
∣
∣
∣
∣
w
^
o
p
t
∣
∣
≤
k
η
R
k\eta \gamma \le \hat w_{k} · \hat w_{opt} \le ||\hat w_k||||\hat w_{opt}|| \le \sqrt{k}\eta R
kηγ≤w^k⋅w^opt≤∣∣w^k∣∣∣∣w^opt∣∣≤kηR 于是
k
≤
(
R
γ
)
2
.
.
.
.
.
.
.
.
.
.
(
10
)
k \le \left(\frac{R}{\gamma}\right)^2..........(10)
k≤(γR)2..........(10) 根据10，我们知道误分类次数k是有上界的，也就是说经过有限次分类我们一定能找到将训练数据完全分开的超平面。
3. 感知机对偶形式
假设w和b初始值均为0，对于误分类点通过
w
=
w
+
η
y
i
x
i
w=w+\eta y_ix_i
w=w+ηyixi和
b
=
b
+
η
y
i
b=b+\eta y_i
b=b+ηyi逐步修改，设修改N次，则最后学习到的w和b分别是
w
=
∑
i
=
1
N
a
i
y
i
x
i
b
=
∑
i
=
1
N
a
i
y
i
w=\sum_{i=1}^Na_iy_ix_i \\ b=\sum_{i=1}^Na_iy_i
w=i=1∑Naiyixib=i=1∑Naiyi 其中
a
i
=
n
i
η
a_i=n_i\eta
ai=niη，
n
i
n_i
ni表示第i个实例点由于被误分而更新的次数。则我们的感知机模型可以表示为
f
(
x
)
=
s
i
g
n
(
∑
j
=
1
N
a
j
y
j
x
j
⋅
x
+
b
)
f(x)=sign\left(\sum\limits_{j=1}^Na_jy_j x_j·x+b\right)
f(x)=sign(j=1∑Najyjxj⋅x+b) 感知机算法的对偶形式总结如下：
初始化
a
⃗
=
0
，
b
=
0
\vec a=0，b=0
a=0，b=0
遍历训练集，如果当前样本
y
i
(
∑
j
=
1
N
a
j
y
j
x
j
⋅
x
+
b
)
≤
0
y_i\left(\sum\limits_{j=1}^Na_jy_j x_j·x+b\right) \le 0
yi(j=1∑Najyjxj⋅x+b)≤0，则更新
a
i
=
a
i
+
η
，
b
=
b
+
η
y
i
a_i=a_i+\eta，b=b+\eta y_i
ai=ai+η，b=b+ηyi
投票感知器记录第k 次更新后得到的权重
w
k
w_k
wk 在之后的训练过程中正确分类样本的次数
c
k
c_k
ck 。这样最后的分类器形式为:
y
=
s
g
n
(
∑
k
=
1
K
c
k
s
g
n
(
w
k
T
x
)
)
y = sgn(\sum_{k=1}^Kc_ksgn(w^T_kx))
y=sgn(k=1∑Kcksgn(wkTx)) 投票感知机需要保存K个权重向量，带来额外开销。
5.2 平均感知机
为了降低开销，对投票感知机的式子进行简化，得到
y
=
s
g
n
(
∑
k
=
1
K
(
c
k
w
k
)
T
x
)
=
s
g
n
(
w
ˉ
T
x
)
\begin{aligned} y & = sgn(\sum_{k=1}^K(c_kw_k)^Tx) \\ & = sgn(\bar w^Tx) \end{aligned}
y=sgn(k=1∑K(ckwk)Tx)=sgn(wˉTx)
